第2章数据结构线性表

2.1

线性表的概念

一、线性表的结构特性二、线性表的抽象数据类型

2.2

顺序表及其运算

一、什么是顺序表二、顺序表的运算

2.3线性表的链式存储

一、线性链表的概念二、线性链表及其结点的结构定义三、线性链表的运算2.1线性表的概念

一、线性表的结构特性属性相同的数据元素按某种关系排列的表例：

农历节气表

(

立春,雨水,惊蛰,春分,清明,……,大雪,冬至,小寒,大寒

)

——表中元素是字符

抗灾衣被捐赠登记表——

按捐赠时间先后

(

单位,姓名,棉被,棉衣裤,毛衣裤,帽类)

奥运会各国家队奖牌数统计表——

按金牌、银牌、铜牌数多少

(

国家,金牌数,银牌数,铜牌数)——表中元素为记录2.1线性表的概念

线性表(

LinearList)——具有相同特性数据元素的有限序列；

可描述为：B=(D,R)

D={

ai

|i=1,2,…,n

};

R={

(ai,ai+1)|i=1,2,…,n-1

}

；

也可以简单表示为：

B=(

a1,a2,…,ai,…,an

)

表中元素个数

n——

表长度，

n=0

时称为空表；

结构特性：①元素之间具有线性关系

(元素在位置上有序)；②元素在表中的位置由其序号决定；③表长度可变；

2.1线性表的概念二、线性表的抽象数据类型

数据部分：

数据元素，数据元素之间的关系描述；

操作部分：

根据应用需要确定

按照功能可以归纳为以下基本类型：

•

属性设置：确定类型的基本属性值；

•

读取属性：读取类型的属性值；

•

插入：在对象的指定位置加入新的数据元素；

•

删除：删除对象中的指定数据元素；

•

查找：在对象查找满足条件的数据元素；

•

遍历：按某种方式不重复地访问对象中所有数据元素；

•

关系访问：访问对象中有特定关系的元素；2.1线性表的概念ADTLIST{数据：

线性表

L=(a0,a1,…,an),n≥0；

操作：

voidInitList(*L);//初始化

L指向的线性表

ElemTypeGetElemlist(*L,intpos);//得到表中第pos个元素

intFindList(*L,ElemTypeitem);//查找给定关键字元素

//修改表中指定元素

intModifyList(*L,ElemTypeitem);2.1线性表的概念intInsertList(*L,ElemTypeitem);//向表中插入元素

intDeleteList(*L,ElemTypeitem);//删除表中元素

intLenthList(*L);//求表的长度

voidSortList(*L);//按关键字值对表元素排序

voidTraverseList(*L);//对表进行遍历并输出

voidClearList(*L);//清除表中所有元素

}2.2顺序表及其运算

一、什么是顺序表

顺序表——线性表的顺序存储（向量式存储）

存储方法:

表中元素按逻辑顺序依次放在连续存储空间中;

每个元素所占存储单元长度相同；

例：

在C语言中，用数组来实现连续存储单元。所以，可以利用数组实现线性表的顺序存储,要求：数组长度

>表长度

表中元素地址计算：

ADR(ai)=ADR(a1)+(i-1)*k

k——为每个元素所占字节数；

a1

an-1

a2

a3

an

:

:

a41234::n

2.2顺序表及其运算

二、顺序表的运算

若对表示顺序表的数组空间采用动态分配，对顺序表结构作如下定义：

#defineMaxSize100

typedefstruct{ElemTypelist[MaxSize];//存储线性表的数组

intlen;//线性表长度

}SeqList；

数据结构操作的实现与具体的存储结构有关以下考虑以SeqList为类型的顺序表基本操作（运算）的实现

最基本的操作（运算）：(1)

在表中插入一个元素

(2)

删除表中某个元素

#defineMaxSize100

typedefstruct{ElemTypelist[MaxSize];//存储线性表的数组

intlen;//线性表长度

}SeqList；如要动态分配空间，顺序表的结构类型应定义如下：#defineMaxSize100

typedefstruct{ElemType*list;//存储线性表的数组

intlen;//线性表长度

}SeqList；

2.2顺序表及其运算

1.顺序表初始化为存储线性表动态分配数组空间，置初始线性表为空

void

InitList(SeqList*L){//动态分配存储空间

L->List=(ElemType*)malloc(MaxSize*sizeof(ElemType))；

if(!L->list){printf("Memoryallocationfailure!\n")；

exit(1)；

}L->len=0；//置初始线性表为空

}2.2顺序表及其运算

2.顺序表的插入运算

在表中第

i个位置插入一个元素

item

设表长为

len

插入前：A=(

a0,a1,…,ai-1,ai,…,alen-1

)

表长为

len

插入后：A=(

a0,a1,…,ai-1,ai,ai+1,…,alen

)

表长为

len+1

表首元素位置不变，表向后增长

ak0≤k<i

A与A的关系：ak

=

itemk=iak-1

i<k≤len

实现算法：

考虑因素：☛

表长不能超出给定空间——上溢处理

☛

若所给插入位置不合理，要处理

☛

正常插入操作后表长应增加1

{2.2顺序表及其运算

算法描述：

voidinsertlist(SeqList*L,ElemTypeitem,inti)

{intj;if(L->len==MaxSeze)//若表空间满，不能插入

{printf("表满！\n")

；

exit(1)；

}if(i<0)i=0；//处理不合理的插入位置

elseif(i>L->len-1)i=L->len；

for(j=L->len-1;j>=i;j--)L->list[j+1]=L->list[j]；

L->list[i]=item；

L->len++；

}2.2顺序表及其运算

算法分析：

①时间复杂度：

决定本算法执行时间的主要操作：数据元素移动次数；

设表长为n，表中第i个位置插入，移动元素次数为：

n–i

设在各位置插入数据元素的概率为Pi

，平均移动次为：

设各位置插入的概率相等，即：

Pi=1/(n+1)，则有：

即：插入一元素的时间复杂度为：O(n)

②

空间复杂度：原地工作(inplace)2.2顺序表及其运算

3.顺序表的删除运算

在表中删除第pos个元素

删除前：(b0，b1，…，bi，bi+1

，…，bn-1)

表长为

n

；

删除后：(b0'，b1'，…，bi-1'，bi+1'，…，bn-2'

)

表长为

n-1

；

算法考虑：表空(L->len=0)不能做删除——下溢处理；

指定的删除位置不存在，要处理；

正常删除操作，表长

n

减

1；

算法描述：参考教材

算法分析：与插入运算类似；平均时间复杂度：

O(n)；

空间复杂度：原地工作

思考：在有序顺序表中删除指定元素，算法？2.2顺序表及其运算4.顺序表的查找从线性表中查找具有给定值的第一个元素设L为无序表，实现算法：

intFindList(SeqList*L,ElemTypeitem)

{inti;for(i=0;i<L->len;i++)if(L->list[i]==item)returni;return-1;//-1查找失败标志

}2.2顺序表及其运算

算法复杂度：

※时间复杂度：

算法运行时间主要由比较元素的次数决定，当查找

元素在表中第

i

个位置时，其比较次数为：

i+1

设表长为

n

，若表中各元素被查找的概率相等，元素值不等，

则查找一个元素的平均比较次数为：

若没有查到所查元素（查找失败）比较次数为：n

即：其时间复杂度为：O(n)

※空间复杂度：

原地工作

(inplace)

其他运算(操作)算法参考教材

2.2顺序表及其运算

顺序表的主要优点：

◊

容易实现；

◊直观、易理解；

顺序表的限制：

◊

对存储空间有要求；

◊

插入、删除操作的效率较低

；

在长度为n的顺序表的第i个位置上插入一个元素(1<=i<=n+1)，元素的移动次数为____A)n–i+1B)n–iC)iD)i–1顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为____次。3.1线性表的链式存储一、线性链表的概念

线性链表——线性表的链式存储。

1.为什么提出链表结构

①存储空间不能满足线性表要求;

线性表长n>连续的存储空间大小。②事先不能确定线性表所需要的存储空间的大小如,多项式的表示与运算:A(x)=a0+a1x+a2x+…+anxB(x)=b0+b1x+…+bmx

运算前后有哪些项？③线性表长经常发生变化如,空闲单元管理——应用程序经常要取用和释放所占用的存储空间。3.1线性表的链式存储

2.线性链表的结构形式

结构特点:①用一组任意的存储单元存储线性表中的元素②存储数据元素之间的关系

好处:

灵活利用存储空间,提高插入、删除运算效率

数据元素的存储映像——结点

结点

结点的图形表示：

元素

指针数据域指针域3.1线性表的链式存储

例如,线性表

(a1，a2，……ai，……，an),结点链接：

pdatapnext

空指针

二、线性链表及其结构定义

结点类型的定义:

typedef

structLNode

{ElemTypedata；//结点值域

struct

LNode*next；//结点指针

}LNode;

表结构类型:

structLinkList

{

LNode*head；

//定义单链表头指针

};a1a2

an∧头指针

H结点

P……在线性表的链式存储结构中,结点之间的关系用节点之间的指针表示.a1a2p

q线性表中的两个结点为a1和a2。链表中的两个结点为p和q。a1和a2的关系用p和q的如下关系式表达：p->next=q3.1线性表的链式存储

三、线性链表的运算

1.线性链表的初始化

voidInitList(LinkList*HL)

{

HL.head=NULL；//置线性链表的头指针为空

}

2.

求线性链表长度

intListlen(LinkList*HL) {LNode*p=HL.head；intlen=0；//len存链表长度

while(p) {p=p->next；len++；} returnlen；//返回链表长度

} 3.1线性表的链式存储

3.线性链表的插入运算

在头指针为

head的线性链表中，在元素

b的结点之前插入一个新元素a,如：

b

∧e…ad

fb

∧eac…headd

fchead插入后:3.1线性表的链式存储运算步骤：

•

分配一个空闲结点

p，令

P→data=a；

•

寻找元素

b的前一个结点

s；

•

将结点

p插入到

s与

s→next

之间；主要问题：如何寻找元素

b

的前一个结点

s?注意特殊情况：•

HL为空表；a为第1个结点

•

b处于第1个结点；a为第1个结点

•b不在HL中；a为最后一个结点3.1线性表的链式存储d

fc

∧eak…head找不到b?head=NULL链表空d

fc

∧eab…head插入在第1个结点位置3.1线性表的链式存储

实现算法：

voidInsertList(LinkList*HL,ElemTypeb,ElemTypea)

//在线性链表HL中的元素b

之前插入元素

a

{LNode*newp,*p,*q;newp=(LNode*)malloc(sizeof(LNode))；//

分配一个新结点

if(!newp)

{printf(〃内存动态空间分配失败！\n″)；

exit(1)；

}

newp->data=a；//

置a

到新结点的值域

if(HL->head==NULL‖HL->head->data=b)//

处理空表或元

{newp->next=HL->head；//

素b

处于第一个结点的情况

HL->head=newp；

return；

}

3.1线性表的链式存储q=HL->head;p=q->next；//从第2个结点开始查找元素b

while(p!=NULL&&p->data!=b)

{q=p；

p=p->next；

}

newp->next=q->next；//若找到元素b，把元素a插入到

b之前

q->next=newp；//

若b不在表中，则把元素a插入到链尾。

}

主要操作——查找元素b所在结点

平均时间复杂度为:

O(n)

若不要查找插入位置(指定插入位置)，则时间复杂度为

O(1)

3.1线性表的链式存储

4.线性链表的删除运算

在头指针为

head的线性链表中删除元素b所在的结点d

bf

∧ec…head运算步骤：

☛寻找元素

b的前一个结点；

☛删除元素b的结点；☛释放被删除结点；算法考虑：①

b在第1个结点中；②空表情况、找不到b；③正常删除，释放空闲结点；实现算法：删除后：dcheadf

∧e…3.1线性表的链式存储intDeleteList(LinkList*HL,ElemTypeb)

//b为指定删除的元素

{LNode*p=HL->head,*q=NULL；//

q为p的前件结点

while(p!=NULL)

//在表中找查元素b

{if(p->data==b)break；

q=p；

p=p->next；

} if(p==NULL)return0；//没有找到b，删除失败

if(q==NULL)HL->head=p->next;//处理b在第一个结点中的情况

elseq->next=p->next；//

其他情况做正常删除

free(p)；//

释放被删除的结点

return1；//

返回删除成功标志

}

平均时间复杂度：

O(n)3.1线性表的链式存储5.线性链表的查找

查找具有给定值的元素

(若有相同元素则为第一个)

LNode*FindList(LinkList*HL,ElemTypeitem) {LNode*p=HL->head；

while(p!=NULL) {if(p->data==item) returnp；

elsep=p->next；

}

printf("表中不存在指定元素

\n")；

returnNULL；

}

平均时间复杂度：

O(n)3.1线性表的链式存储6.清除表中所有元素,释放链表

voidClearList(linkList*HL) {LNode*p=HL->head,*q；

while(p!=NULL) {q=p；

p=p->next；

free(q)；

} HL->head=NULL；

}

时间复杂度:

O(n)3.1线性表的链式存储7.线性链表的合并与分解运算

(1)

合并运算

问题：设有线性链表

x=(x1,x2,…,xn)

和

y=(y1,y2,…,ym)

按以下要求把两个链表合并为一个线性链表Z

∧…x2y1x1x1x2x3∧xn…HX.heady1y2y3∧ym…HY.headHZ.head3.1线性表的链式存储分析：

•设待合并的两个链表的结构类型对象为：HX，HY•两个已知链表的表长

n，m为任意

•合并时两个链表结点间的位置关系给定算法思路：

•以X

链为基本链，把Y

链的结点逐个插到

X

链中；

•当两个链表都还有后续结点，插入操作重复进行；

•把未合并部分接在已合并部分之后；3.1线性表的链式存储

实现算法:voidLinkUnion(linkList*HX,linkList*HY,linkList*HZ){//HX和HY为已知链表，HZ为合并后链表

LNode*p,*q,*m,*n;InitList(HZ)；//

初始化z链表

if(HX->head==NULL)HZ->head=HY->head；//

X

链空

elseif(HY->head==NULL)HZ->head=HX->head；//

Y

链空

else {HZ->head=HX->head；//

两个链都不空

p=HX->head;q=HY->head；//

取x1为z链的第一个结点

3.1线性表的链式存储while(p!=NULL&&q!=NULL)//X、Y链都还有未合并的结点

{//

使yi所在结点链接到xi所在结点之后

m=p->next；n=q->next；

p->next=q；

//

若x

链还有未合并结点，则把xi+1接在yi之后

if(m!=NULL)q->next=m；

p=m；q=n；//

对x、y

链的下一个结点做链接

} }

HX->head=NULL;

HY->head=NULL;}3.1线性表的链式存储

时间复杂度：O(m+n)注意：运算中不能产生断链情况x1x2x3y1y2y3∧ym…HZn<mx1x2x3∧xny1y2…HZn≥m合并结果：3.1线性表的链式存储

(2)

分解运算

问题：

头指针为

head的线性链表，结点值为正整数且按值从大到小链接。要求分解为两个链表，一个为奇数链，另一个为偶数链，其结点值都按从小到大链接。

算法考虑：

•

原链表为空的情况；

•分解后其中一链表为空的情况；

•

根据结点值的奇偶性,将其插入相应的链头；

•

原链表还有后续结点作为重复操作的条件；

•

保证分解后的表尾结点指针为空；

3.1线性表的链式存储

实现算法：

voidLink_sol(LinkList*HL,LinkList*HO,LinkList*HE)

{LNode*p=HL->head,*q；//

p

指向链头

InitList(HO)；//

初始化奇数链链表

InitList(HE)；//

初始化偶数链链表

while(p!=NULL) {q=p；//q

为从原链上拆下的结点

p=p->next；

if(q->data%2==0)//

若结点值为偶数，插入到偶数链头

{q->next=HE->head；HE->head=q；}

else//

否则，插入到奇数链头

{q->next=HO->head；HO->head=q；} }

HL->head=NULL；//

置原链表为空

}3.1线性表的链式存储分解运算图示：

86666775

⋀HL.h…8686

⋀HE.h77

∧HO.h66686

∧HL.h…577

∧HO.h…6686

∧HL.h┆┆思考：算法的时间复杂度？3.1线性表的链式存储86666775

⋀868666

∧86666

∧77

∧775

∧86

⋀HL.h…HE.hHL.hHL.hHO.hHO.h…┆┆…若要求分解后的链表结点值仍按从大到小链接，其算法？图示：3.1线性表的链式存储算法思路:

1.从HL的第1个结点开始拆分

——判断奇偶、拆下结点；

2.

拆下的结点

——链接到（偶数链或奇数链的）链尾；

——需要设置指示分解链尾的指针；

3.重复操作条件

——HL还有结点；

要注意处理：

•

HL为空表——

分解后两链表头指针为空；

•

分解后有一个链表为空表——

其头指针为空；

•分解后的链表——

表尾结点指针域为空；带头结点的线性表的链式存储

例如,线性表

(a1，a2，……ai，……，an),结点链接：

头结点pdatapnext

空指针

∧a1

an∧头指针

H结点

P……带头结点的空线性表∧∧头指针

H不带头结点的单链表head为空的判定条件是____A)head==NULLB)head->next==NULLC)head->next==headD)head!=NULL带头结点的单链表head为空的判定条件是____A)head==NULLB)head->next==NULLC)head->next==headD)head!=NULL在单链表指针为p的结点之后插入指针为s的结点，正确的操作是____A)p->next=s；s->next=p->nextB)s->next=p->next；p->next=s;C)p->next=s；p->next=s->nextD)p->next=s->next；p->next=s3.3循环链表一、循环链表的结构特点1.循环链表的结构◈在线性链表的基础上增加一个特殊结点——表头结点;◈最后一个结点的指针指向表头结点；

循环链表为空H结构形式：a1a2an…表头结点H3.3循环链表2.循环链表的特点top×H∧…可利用栈top…循环链表××××循环链表为空H②空表与非空表运算一致;③对于静态链表,释放全链表很方便；①可从任意结点出发扫描全表；3.3循环链表二、循环链表的基本运算循环链表运算的思路与线性链表类似，但操作上有差别：①空表情况不需要单独处理；②判断表尾结点的条件：p->next=HL->head?

1.插入运算

在元素

b之前插入元素

a

算法思路同线性链表，算法：voidInsertClist(CylList*HL,ElemTypeb,ElemTypea)

3.3循环链表{LNode*newp,*p,*q;newp=(LNode*)malloc(sizeof(LNode))；//分配一个新结点

if(!newp) {printf("动态空间分配失败！\n"); exit(1); } newp->data=a;//置a到新结点的值域

p=HL->head；q=p->next;//p表头结点,q第一个结点

while(q!=HL->head&&q->data!=b)//找a的插入位置

{p=p->next；q=p->next；}//找到b把新结点插入到它之前，若未找b，新结点插入到表尾

newp->next=p->next;p->next=newp;

}

思考：算法的时间复杂度？3.3循环链表2.删除运算

在循环链表中，删除包含元素b的结点步骤：①在循环链表中找到包含元素b的前一个位置；②删除b所在的元素；③释放所删除的结点；注意： ①空表与非空表操作一致；

②若表中找不到元素b,要给出必要信息，退出执行；思考：

实现算法？算法的复杂度？3.3循环链表3.合并运算

问题：设AH、BH为两个有序循环链表，

要求把它们合并为一个有序循环链表CH。kij……AH.headBH.headCH.head3.3循环链表算法思路:①设定A链、B链、C链结点值均为非递减有序；②设k指向C链尾结点，i、j分别指向A链、B链第一个结点；③以A链为基本链，通过比较把B链中结点逐个插入到A链中；④以两链都还有未合并的结点为重复操作的条件；⑤结点插入过程结束后，处理某一链中未插入的部分，并将AH和BH置为空表；注意:

B链结点向A链插入过程中，始终保持A为有序循环链表；

参考算法:

3.3循环链表voidMergClist(CyList*AH,CyList*BH,CyList*CH){//i.j指向A链、B链当前要比较的结点，k指向C链的尾结点

LNode*k,*i,*j;k=CH->head;i=AH->head->next;j=BH->head->next; k->next=i;//使A链第1个结点接在C

链表头结点后

while(i!=AH->head&&j!=BH->head)//两个表都还有未合并的结点

{if(j->data<=i->data)//B链当前结点值小

{k->next=j;k=j;j=j->next;k->next=i;} else{k=i;i=i->next;}//A链当前结点值小

}3.3循环链表

if(j!=BH->head)//B链还有剩余结点

{k->next=j;//接到已合并部分的最后

//找到链尾结点

while(j->next!=BH->head)j=j->next;//使链尾结点的指针指向C链表头结点

j->next=CH->head; }

else//处理A链还有剩余结点

{while(i->next!=AH->head)i=i->next;i->next=CH->head;

}

AH->head->next=AH->head;BH->head->next=BH->head;}3.3循环链表4.分解运算

循环链表分解运算思路与线性链表类似，但要注意：

☆

空表非空表统一考虑；

☆

要申请新的结点作为分解后增加的循环链表的表头结点；考虑：

一个有序循环链表(正整数)分解为两个有序循环链表

(奇、偶数)的算法？链表操作要注意:

☼

操作过程中不要产生“断链”；

☼

链表结点一致(共享空间)，需要——取，空闲——释放；

☼

注意循环链表与线性链表的区别；3.3循环链表5.循环链表应用例(1)用循环链表表示多项式

好处：有效利用存储空间，有利于运算；

表示方法：

☞仅表示出非0系数项；☞每个非0系数项构成链表中的一个结点，结构：结点的数据项有两个域：指数域、系数域

expcoffnext3.3循环链表设仅表示非0系数项的多项式：

Pm(x)=amxem+am-1xem-1

+…+a1xe1

其中，ak

0(k=1,2,…,m)em>em-1>…>e1≥0其循环链表的表示为：

——多项式链表-1emam

e1a1…3.3循环链表多项式链表的结点结构定义：

typedefstructDNode{intexp;doubecoef;structDNode*next;}DNode;多项式链表运算主要包括：

☛多项式链表生成；☛多项式链表释放；☛多项式的输出；☛多项式的相加；☛多项式链相乘；3.3循环链表(2)多项式相加

设有多项式：

其中：

ai≠0(i=1,2,…,m),bj≠0(j=1,2,…,n)

且

em

>em-1

>…>e1≥0,en

>en-1

>…>e1≥0

求和多项式C(x):C(x)=Am(x)+Bn(x)3.3循环链表设AH、BH和CH分别表示多项式Am(x)、Bn(x)

和C(x)结构类型的对象，多项式相加运算的规则：

①从AH、BH第一个结点开始(作为“当前”结点)依次

检测每个结点，并处理检测结果：

►

若两个多项式中“当前”结点的指数值相等，两系数相加：

若：系数和≠0，则生成一个新结点，其指数值为当前结点的指数，系数值为两系数的和，将其链入

CH的链尾，继续检测

AH、BH的下一结点；

如果：系数和=0，直接继续检测

AH、BH的下一结点；

3.3循环链表►

若两个多项式中对应结点的指数值不相等，

则取指数值大的结点的指数、系数值构成一个新结点，将其链入

CH的链尾。继续检测指数值大者的下一结点、指数值小者的当前结点。②重复①，直到两链表的所有结点检测完；思考：实现算法？3.3循环链表(3)求解约瑟夫(Josephu)问题

有n个人围成一个园圈坐下，从某个人开始对所有围坐的人依次编号为1，2，3，…，n，从编号为1的人开始沿围坐的园圈顺序报数，报数为m

的人即出列，于是第m+1个人就与第m-1个人紧挨着；下一个人(第m+1个)又从1开始沿围坐的园圈顺序报数，再报数到m

的人便是第二个出列的人。如此重复下去，直到最后一个人出列为止，于是便得到一个出列的顺序。例如，当n=8，m=4时，若从第一个位置数起，则出列的次序为4、8、5、2、1、3、7、6

；

称为约瑟夫问题。3.3循环链表简单方法：①循环报数

n个人的编号1,2,…,

n

依次存放在数组中②当有人出列以后，数组中的元素置-1

01234567812345678012345678123-156784号出列后不再参与报数初始数组voidJosephu1(inta[],intb[],intn,intm){inti,j,s=0;for(i=1;i<=n;i++)a[i]=i;for(i=1;i<=n;i++){for(j=1;j<=m;j++){s++;if(s>8)s=1;while(a[s]==-1){s++;if(s>8)s=1;}}b[i]=s;a[s]=-1;}}算法如下：3.3循环链表求解思路：①循环报数

n个人的编号1,2,…,

n

组织成一个环形结构②当有人出列以后，留下的人要仍然保持一个环形结构可以采用不同的方式组织报数的人:

采用数组将报数的人构成一个环形实现方式：若用用数组a[n+1]存放n个人的编号例如，a[i]=i+1,i=1,2,…,n-1a[n]=1

一个人的编号为p，那么他下一个人的编号为a[p]

假设，当前出列的数为k，其前一数为pre,则：

k出列前：…,pre,k,a[k],…k出列后：…,pre,a[k],…3.3循环链表每一轮报数过程中做：pre=k,k=a[k]数k出列：b[i]=k,a[pre]=a[k],k=a[k]——出列者存于数组b[n+1]中算法描述：

Josephu1(inta[],intb[],intn,intm)//a[1]a[n]放n个人的编号

{inti,k,j,pre;for(i=1;i<=n;i++)a[i]