1、1第第2章章 线性表线性表 本章学习内容2.6 算法应用举例2.5 顺序表与链表的比较2.4 一元多项式的表示及相加2.3 线性表的链式存储结构2.2 线性表的顺序存储结构2.1 线性表的定义及其运算22.1 线性表的定义及其运算2.1.1 线性表的定义在实际应用中，线性表是最常用而且是最简单的一种数据结构。例如，一副扑克牌的点数是一个线性表，可表示为（2,3,4,5,6,7,8,9,1 0,J,Q,K,A），一些城市的名字是一个线性表，可表示为（Changsha,Beijing,Shanghai,Guangzhou,Wuhan）。1线性表的定义线性表（linear list）是n（n0）个数
2、据元素a1，a2，an组成的有限序列。其中n 称为数据元素的个数或线性表的长度，当n=0时称为空表，当n0时称为非空表。通常将非空的线性表记为（a1，a2，an），其中的数据元素ai（1in）是一个抽象的符号，其具体含义在不同情况下是不同的，即它的数据类型可以根据具体情况而定，本书中，我们将它的类型设定为elemtype，表示某一种具体的已知数据类型。32线性表的特征从线性表的定义可以看出线性表的特征：（1）有且仅有一个开始结点（表头结点）a1，它没有直接前驱，只有一个直接后继；（2）有且仅有一个终端结点（表尾结点）an，它没有直接后继，只有一个直接前驱；（3）其他结点都有一个直接前驱和直接后
3、继；（4）元素之间为一对一的线性关系。因此，线性表是一种典型的线性结构，用二元组表示为：linear_list=(A,R)其中A=ai 1in,n0,aielemtypeR=rr=1in-1对应的逻辑结构图如下所示。a1 a2 an 42.1.2 线性表的运算给出了线性表的逻辑结构后，就可以直接定义它的一些基本运算，但这些运算要实现，还必须依赖于具体的存储结构。常见线性表的运算有：（1）置空表 setnull(&L)：将线性表L置成空表。（2）求长度 Length(L)：求给定线性表L的长度。（3）取元素 Get（L,i）：若1ilength(L)，则取第i个位置上的元素，否则取得的元素为NU
4、LL。（4）求直接前驱 Prior(L,x)：求线性表L中元素值为x的直接前驱，若x为第一个元素，前驱为NULL。（5）求直接后继 Next（L,x）：求线性表L中元素值为x的直接后继，若x为最后一个元素，后继为NULL。（6）定位函数 Locate(L,x)：在线性表L中查找值为x的元素位置，若有多个值为x，则以第一个为准，若没有，位置为0。（7）插入 Insert(&L,x,i)：在线性表L中第i个位置上插入值为x的元素。（8）删除 Dele（&L,i）：删除线性表L中第i个位置上的元素。52.1.3 线性表的抽象数据类型描述上述这些操作可用抽象数据类型描述为：ADT Linearlist
5、 isData:一个线性表L定义为L=(a1,a2,an)，当L=()时定义为一个空表。Operation:void setnull(&L)/将线性表L置成空表int Length(L)/求给定线性表L的长度elemtype Get(L,i)/取线性表L第i个位置上的元素elemtype Prior(L,x)/求线性表L中元素值为x的直接前驱elemtype Next(L,x)/求线性表L中元素值为x的直接后继int Locate(L,x)/在线性表L中查找值为x的元素位置void Insert(&L,x,i)/在线性表L中第i个位置上插入值为x的元素void Dele(&L,i)/删除线性表
6、L中第i个位置上的元素END Linearlist6【例2-1】假设线性表L=(23,56,89,76,18)，i=3，x=56，y=88，则对L的一组操作及结果如下：Length(L)/所得结果为5Get(L,i)/所得结果为89Prior(L,x)/所得结果为23Next(L,x)/所得结果为89Locate(L,x)/所得结果为2Insert(&L,y,i)/所得结果为(23,56,88,89,76,18)Dele(&L,i+1)/所得结果为(23,56,88,76,18)72.2 线性表的顺序存储结构2.2.1 顺序表结构线性表的顺序存储结构，也称为顺序表。其存储方式为：在内存中开辟一
7、片连续存储空间，但该连续存储空间的大小要大于或等于顺序表的长度，然后让线性表中第一个元素存放在连续存储空间的第一个位置，第二个元素紧跟在第一个之后，其余依此类推。显然，利用顺序表来存储线性表，表中相邻的元素存储在计算机内的位置也相邻，故可以借助数据元素在计算机内的物理位置相邻来表示线性表中数据元素之间线性逻辑关系。假设线性表中元素为(a1,a2,.,an)，设第一个元素a1的内存地址为LOC(a1)，而每个元素在计算机内占d个存储单元，则第i个元素ai的地址为LOC(ai)=LOC(a1)+(i-1)d （其中1in）。8从上面的公式可知，该存储结构类似于高级语言中的一维数组存储结构（即向量结
8、构），适合于随机访问，于是可用C+语言描述为：const int maxsize=Maxlen；/Maxlen表示线性表允许的最大长度class sequenlist public:elemtype amaxsize;/表示线性表(a1,a2,an,aMaxlen),elemtype表示某种具体数据类型 int len;/len表示线性表的实际长度 int length(sequenlist L);/求顺序表L的长度 void Insert(sequenlist&L,elemtype x,int i);/将元素x插入顺序表L第i个位置 void Dele(sequenlist&L,int i)
9、;/删除顺序表L第i个位置的元素 void setnull(sequenlist&L);/顺序表L置空表 int Locate(sequenlist L,elemtype x);/定位，顺序表L中查找元素x的位置 elemtype Get(sequenlist L,int i);/取顺序表L中第i个位置的元素 elemtype prior(sequenlist L,elemtype x);/顺序表L中求元素x的前驱 elemtype next(sequenlist L,elemtype x);/顺序表L中求元素x的后继 ;9在上述描述中，a为一个数组类型，第一个元素为a0而非a1，因为C+中数
10、组的下标是从0开始而非1开始。存储空间从a0amaxsize-1，而不是从a1amaxsize，不能使用amaxsize。为了与我们的a1对应，建议从a1开始使用元素，将a0存储单元浪费掉，这样给我们的操作带来较大方便（以后使用不再声明），当然，一般情形下，不应该浪费a0存储单元，这可根据具体情形来定。2.2.2 顺序表运算实现顺序表上的基本运算，我们都将以函数的形式描述。下面仅讨论插入、删除、求长度、置空表、定位算法、取元素等，其他算法读者自己可类似分析。1求顺序表的长度length(L)算法的语句如下：int sequenlist:length(sequenlist L)return L.
11、len;该算法的语句频度为1，时间复杂度为O(1)。102插入运算Insert(&L,x,i)要将x插入到顺序表L的第i个位置，可分三种情形考虑：（1）i位置超过表长，发生溢出，不能插入；（2）i值非法，不能插入；（3）i值合法，进行插入。算法描述为：void sequenlist:Insert(sequenlist&L,elemtype x,int i)int j;if(L.len=maxsize-1)coutoverflowendl;else if(iL.len+1)coutposition is not correct!=i;j-)L.aj+1=L.aj;/元素后移L.ai=x;/插入元
12、素L.len+;/表长度增加111分析该算法的执行效率：分析该算法的执行效率：该算法花费的时间，主要在于循环中元素的后移（其他语句花费的时间可以忽略），即从插入位置到最后位置的所有元素都要后移一位，使空出的位置插入元素值x。但是，插入的位置是不固定的，当插入位置i=1时，全部元素都得移动，需n次移动，当i=n+1时，不需移动元素，故在i位置插入时移动次数为n-i+1。假设在每个位置插入的概率相等，为 ，则平均移动元素的次数为 ，故时间复杂度为O(n)。11n112)1(11nininn从上面的分析可知，顺序表上的插入算法平均要移动一半元素，故当n较大时，算法的效率相当低。3删除运算Dele(&
13、L,i)删除算法描述为：void sequenlist:Dele(sequenlist&L,int i)int j;if(iL.len)cout position is not correct!endl;else for(j=i+1;j=L.len;j+)L.aj-1=L.aj;/元素前移 L.len-;/表长度减1 12该算法的运行时间主要花费在元素前移上，和刚才的插入算法类似，平均移动次数为 ，故时间复杂度为(n)。顺序表上的删除运算平均移动元素次数也将近为表长的一半，当n较大时，算法的效率相当低。nininn121)(1从顺序表插入、删除运算可知，当n较大时，算法效率都相当低。若有大量运
14、算为插入、删除运算，则不宜选用顺序表，必须选用另外的存储结构。从顺序表插入、删除运算可知，当n较大时，算法效率都相当低。若有大量运算为插入、删除运算，则不宜选用顺序表，必须选用另外的存储结构。4置空表setnull(&L)算法如下：void sequenlist:setnull(sequenlist&L)L.len=0;该算法的时间复杂度为O(1)。135定位算法Locate(L,x)算法如下：int sequenlist:Locate(sequenlist L,elemtype x)int j=0;while(jL.len)&(L.aj!=x)j+;if(jL.len)return j;el
15、se return-1;该算法的时间复杂度为O(n)。6取元素Get(L,i)算法如下：elemtype sequenlist:Get(sequenlist L,int i)if(i=L.len)return NULL;else return L.ai;该算法的时间复杂度为O(1)。142.2.3 顺序表存储空间的动态分配上面介绍的线性表顺序存储，是预先给定大小为maxsize的存储空间，程序在编译阶段就会知道该类型变量的大小，在程序开始运行前，就会为它分配好存储空间，故是一种存储空间的静态分配。而动态分配是在定义线性表的存储类型时，不是定义好一个数组空间，而是只定义一个指针，待程序运行后再申
16、请一个用于存储线性表的空间，并把该空间的首地址赋给这个指针。访问动态存储分配的线性表中的元素和访问静态存储分配的线性表中的元素的情况完全相同，既可以采用指针方式，也可以采用数组下标方式。若将前面线性表的顺序存储结构类型中的数组形式改为指针形式，则得到动态分配形式如下：class sequenlist public:elemtype *a;int len;15在此时，只有线性表置空表算法需要修改，其他算法都与静态分配相同。这时的置空表算法应改为：void sequenlist:setnull(sequenlist&L)L.a=new elemtypemaxsize;/动态申请存储单元 if(L.
17、a=NULL)exit(1);/申请不成功 L.len=0;162.3 线性表的链式存储结构线性表的链式存储结构，也称为链表。其存储方式是：在内存中利用存储单元（可以不连续）来存放元素值及它在内存中的地址，各个元素的存放顺序及位置都可以以任意顺序进行，原来相邻的元素存放到计算机内存中后不一定相邻，从一个元素找下一个元素必须通过地址（指针）才能实现，故不能像顺序表一样可随机访问，而只能按顺序访问。常用的链表有单链表、循环链表和双向链表、多重链表等。2.3.1 单链表结构在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表。线性链表中的结点结构可描述为 。其中da
18、ta域用来存放结点本身的信息，类型由具体问题而定，本书中，我们也将其设定为elemtype类型，表示某一种具体的已知类型，next域用来存放下一个元素地址。data next17【例2-2】设有一个线性表(a1,a2,a3,a4,a5,a6)，在内存中的存放形式见下图。首先用头指针存放第一个元素的地址，然后每个结点的指针域存放下一个元素地址，最后一个结点的指针域为空，表示没有后继元素，设为NULL或。a2 180a4 170a6 NULLa1 110a5 140a3 130150地址 data 域 next 域110120130140150160170180head头指针我们用上图来描述单链表
19、，是内存中的存放形式，但看起来不太直观，如果我们用下图来描述单链表，则看起来直观得多。a1 a2 a3 a4 a5 a6 18单链表可用+描述为：class link public:elemtype data;/元素类型link *next;/指针类型，存放下一个元素的地址int length();/求链表的长度void Insert(elemtype x,int i);/将元素x插入到第i个位置void Dele(int i);/删除第i个位置的元素void setnull();/置空表int Locate(elemtype x);/定位，查找元素x的位置elemtype Get(int i
20、);/取第i个位置的元素elemtype prior(elemtype x);/求元素x的前驱elemtype succ(elemtype x);/求元素x的后继link*hcreat()/头插法建立单链表link*rcreat()/尾插法建立单链表 192.3.2 单链表运算在此仅介绍单链表建立、查找、插入、删除、输出等运算，其他算法可类似分析。1头插法建立单链表（从左边插入结点）建立不带头结点的链表，算法为：link *link:hcreat(int n)/n表示结点的个数 link*s,*p;int i;p=NULL;for(i=1;is-data;/输入结点的数据值 s-next=p;
21、p=s;return p;20但是，为了便于实现各种运算，通常在单链表的第一个结点之前增设一个附加结点，称为头结点，其他结点称为表结点。头结点结构与表结点结构相同，其数据域为空，也可以存放表长等附加信息。不带头结点的单链表和带头结点的单链表见下图。head a2 an a1 head an a1 a2 不带头结点的单链表带头结点的单链表21建立带头结点的链表，算法为：link*link:hcreat(int n)link*s,*p;int i;p=new link;p-next=NULL;for(i=1;is-data;s-next=p-next;p-next=s;return p;若假设链表
22、中元素个数为n个，则两种算法的时间复杂度都为(n)。222尾插法建立单链表（从右边插入结点）（1）不带头结点的算法 link*link:rcreat(int n)link*s,*r,*p;int i;p=NULL;for(i=1;is-data;if(p=NULL)p=s;else r-next=s;r=s;r-next=NULL;return p;23（2）带头结点的算法 link*link:rcreat(int n)link*s,*r,*p;int i;p=r=new link;p-next=NULL;for(i=1;is-data;r-next=s;r=s;r-next=NULL;ret
23、urn p;24比较上面两种算法可以发现，建立不带头结点的单链表，必须进行空表与非空表两种情形的区分（循环中用if语句），而建立带头结点的单链表，则可省去这种判断。所以，引入头结点可以带来以下好处：第一，由于开始结点的存储地址存放在头结点的指针域中，所以对链表的第一个结点和其他结点的处理一致，无须特殊处理。第二，不管链表是否为空，其头指针都是指向头结点的非空指针。因此，可不必区分空表与非空表，即可使空表与非空表的处理统一起来。第三，头结点的信息域data一般没有存放什么信息，故可以用来存放一些辅助信息，如链表长度等。因此，若无特别声明，以后建立的链表都为带头结点的链表。同样上面两种算法的时间复
24、杂度都为(n)。253单链表上的查找运算单链表上的查找与顺序表不一样，不能实现随机查找，要找某一个元素，只能从头开始查找，故属于顺序查找。（1）按值查找Locate(head,x)在带头结点的单链表head中，查找值为x的结点，若找到，则返回它的地址，否则返回NULL。link *link:Locate(link *head,elemtype x)link*p;p=head-next;while(p!=NULL)&(p-data!=x)p=p-next;return p;26（2）按序号查找get(head,i)在带头结点的单链表head中查找第i个位置上的元素，若找到，则返回它的地址，否则返
25、回NULL。link *link:get(link *head,int i)int j;link*p;j=1;p=head-next;while(jnext;return p;上述两种查找算法的时间复杂度都为(n)。4单链表上的插入运算在顺序表中，插入元素时，将会有大量元素向后移动，而在单链表中，插入一个结点不需要移动元素，只需修改指针指向即可。27算法描述为：void link:insert(link *head,elemtype x,elemtype y)/在头指针head所指带头结点的单链表中，在值为y的结点之后插入值为x的结点 link*p,*s;s=new link;s-data=x
26、;if(head-next=NULL)/链表为空 head-next=s;s-next=NULL;p=Locate(head,y)/调用查找算法 if(p=NULL)coutnext=p-next;p-next=s;该算法花费的时间主要耗费在查找上，故时间复杂为(n)，若调用另一种查找算法，程序需作适当修改，可作类似分析。285单链表上的删除运算算法描述为：void link:dele(link *head,elemtype x)/在head为头指针的带头结点的单链表中，删除值为x的结点 link*p,*q;q=head;p=head-next;while(p!=NULL)&(p-data!=
27、x)q=p;p=p-next;if(p=NULL)coutnext=p-next;delete(p);该算法花费的时间主要耗费在查找上，故时间复杂度为(n)。若要删除链表中第i个结点，将上述删除算法做适当修改即可。296输出单链表若需将单链表按逻辑顺序输出，则必须从头到尾访问单链表中的每一个结点，算法描述如下：void link:print(link *head)link*p;p=head-next;while(p-next!=NULL)coutdata;/输出表中非最后一个元素 p=p-next;coutdata;/输出表中最后一个元素 coutnext;while(q-next!=p)q=
28、q-next;return q;显然该算法的时间复杂度为(n)。a1 a2 an Head p 32既然是循环链表，head指针就可以指向任意结点，若将head指向末尾，有时的操作会比head指向开头的操作更方便，下面将举例说明。【例2-4】将两个链表合并成一个链表（第一个表的尾接第二个表的头），要求用head指向头和head指向尾两种循环链表实现，分别如下图一和图二所示。a1 a2 an Head1 Head2 b1 b2 bm a1 a2 an Head1 b1 b2 bm Head2 图一图二33对第一种合并算法，可以分三步走：第一步，先找到head1中最后一个结点an，语句描述为：p=
29、head1-next;while(p-next!=head1)p=p-next;第二步，找到head2中最后一个结点bm，语句描述为：q=head2-next;while(q-next!=head2)q=q-next;第三步，合并，语句描述为：p-next=head2-next;q-next=head1;具体算法请读者自己完成。对于第二种合并算法，仅用三条语句就能实现，具体为：t=head1-next;head1-next=head2-next-next;head2-next=t;显然，第一种合并算法的时间复杂度为O(n+m)，第二种合并算法时间复杂度为O(1)。因此，用尾指针所示循环表较头指
30、针所示循环表操作更方便。342.3.4 双向链表结构1双向链表的基本概念在单链表中，从某个结点出发可以直接找到它的直接后继，时间复杂度为O(1)，但无法直接找到它的直接前驱；在单循环链表中，从某个结点出发可以直接找到它的直接后继，时间复杂度仍为O(1)，直接找到它的直接前驱，时间复杂度为O(n)。有时，希望能快速找到一个结点的直接前驱，这时，可以在单链表中的结点中增加一个指针域指向它的直接前驱，这样的链表就称为双向链表（一个结点中含有两个指针）。如果每条链构成一个循环链表，则会得到双向循环链表。双向链表可用C+描述如下：class dblink public:elemtype data;/结点
31、的数据域，类型设定为elemtypedblink *next,*prior;/定义指向直接后继和直接前驱的指针 void dbinsert(dulink *head,elemtype x,elemtype y);/插入函数 /其他成员函数定义及实现35在双向链表中，若涉及的运算仅用到一个方向的指针，则双向链表中的运算与单链表中算法一致。例如查找、输出等运算，与单链表中运算一致。若运算涉及两个方向的指针，则与单链表中的算法不同，例如插入、删除运算。下面仅讨论插入、删除运算。由于双向链表是一种对称的结构，因此比起单链表来，求某个结点的直接前驱和直接后继都相当方便，时间复杂度为O(1)，并且还有一个
32、很重要的性质：若P为指向某个结点的指针，则有：p-next-prior=p=p-prior-next双向链表的形式见下图一，双向循环链表形式见下图二。同样，双向链表和双向循环链表与单链表一样，都可以带头结点。a1 a2 an head rear a1 a2 an head rear 图一图二362双向链表插入运算dbinsert(head,x,y)插入算法描述为：void dblink:dbinsert(dulink *head,elemtype x,elemtype y)/在双向链表head中,在值为y的结点之后插入值为x的结点 dblink*p,*s;s=new dblink;/申请待插入
33、的结点 s-data=x;p=head;while(p!=NULL)&(p-data!=y)/用循环查找值为y的结点 p=p-next;if(p!=NULL)/已找到插入位置 s-next=p-next;p-next-prior=s;s-prior=p;p-next=s;else coutdata!=x)/用循环查找值为x的结点 p=p-next;if(p!=NULL)/已找到该结点 p-prior-next=p-next;p-next-prior=p-prior;delete p;/删除后的结点空间回收 else coutnext;q=B-next;当pa和pb都不为空时，反复执行下面的语句
34、（循环）：（1）若p的指数q的指数将q插入新表中，q指针后移；（3）若p的指数=q的指数若相加的系数等于0，删除p、q两个结点，然后p、q后移；若相加的系数不为0，则将结果放入p中，并将p插入新表中，p指针后移，删除q结点，q后移。最后，当循环结束后，若q非空，则pre-next=q;算法结束。40两个链表A(x)=7+3x+9x8+5x17和B(x)=8x+22x7-9x8相加的过程见下图 7 0 3 1 9 8 5 17 A 8 1 22 7-9 8 B 7 0 11 1 5 17 22 7 A （a）相加前的两个链表（b）相加后的两个链表 412算法实现#includeclass pol
35、y public:int coef;/系数int exp ;/指数 poly *next;/指针类型，存放下一个元素的地址 poly*hcreat();/头插法建立多项式链表 poly*add(poly*A,poly*b);/多项式相加;42/头插法建立带头结点的单链表poly*poly:hcreat()poly*s,*p;int i,j;coutij;p=new poly;p-next=NULL;while(i!=0)s=new poly;s-coef=i;s-exp=j;s-next=p-next;p-next=s;cinij;return p;43 poly*poly:add(poly*
36、A,poly*B)/多项式相加 poly*p,*q,*pre,*C,*u;p=A-next;q=B-next;pre=A;C=A;while(p!=NULL&q!=NULL)if(p-expexp)pre=p;p=p-next;else if(p-exp=q-exp)int x=p-coef+q-coef;if(x!=0)p-coef=x;pre=p;else pre-next=p-next;delete p;p=pre-next;u=q;q=q-next;delete u;else u=q-next;q-next=p;pre-next=q;pre=q;q=u;if(q!=NULL)pre-n
37、ext=q;return C;44 void main()poly*A,*B,*C,a;A=a.hcreat();/头插法建立第一个多项式链表 B=a.hcreat();/头插法建立第二个多项式链表 C=a.add(A,B);/多项式相加2.5 顺序表与链表的比较上面已经讨论了线性表的两种存储结构：顺序表和链表。在实际应用中，两种方法各有特色，我们究竟选用哪一种作为存储结构呢?这要根据具体问题的要求和性质来决定，一般可以从以下几个方面考虑。451基于存储空间的考虑顺序表的存储空间是静态分配的，程序执行之前必须预先分配。若线性表的长度n变化较大，存储空间难以事先确定，估计过大，将造成大量存储单元
38、的浪费，估计过小时又不能临时扩充存储单元，将使空间溢出机会增多。链表的存储空间是动态分配的，只要内存空间尚有空闲，就不会发生溢出。对于存储空间的考虑，可以用存储密度的大小来衡量。存储密度为结点应占用的存储量除以结点实际占用的存储量。存储密度越大，存储空间利用率越高，反之利用率越低。例如，顺序表的存储密度为100%，单链表为50%（假设指针所占空间与数据域所占空间相同），双向链表的存储密度为33%。由此可知，当线性表的长度变化不大，存储空间可以事先估计时，采用顺序表作存储结构比较方便；当线性表长度变化较大，存储空间难以事先估计时，采用链表作存储结构比较方便。462基于时间的考虑顺序表是一种随机访
39、问的表，而链表是一种顺序访问的表，因此顺序表的访问较链表方便。若线性表中运算主要为存取、查找运算，采用时间复杂度为O(1)的顺序表比较方便；若线性表中的运算大部分为插入、删除运算，采用时间复杂度为O(1)的链表比较方便；若链表中操作运算都在表尾进行，应采用尾指针所示的单循环链表。3基于语言的考虑有的高级语言无指针数据类型，因此，若用链表作存储结构，则只能用整数代替指针，称这样的链表为静态链表，而一般的链表则称为动态链表（我们所用的链表都为动态链表）。472.6 算法应用举例【例2-5】实现一个单链表的就地逆置（所谓就地逆置就是不另外增加多余的辅助空间）。分析：要将一个单链表逆置，即将(a1,a
40、2,an)变成(an,an-1,a2,a1)。但链表已存在，故不需要另外申请存储空间，只需改变链表的链接关系即可。可以借助单链表的头插法来实现题目要求，改变单链表的链接关系。算法描述如下：void link:swaplink(link *head)link*p,*s;p=head-next;head-next=NULL;while(p!=NULL)s=p-next;p-next=head-next;head-next=p;p=s;该算法的时间复杂度为O(n)。48【例2-6】用顺序表解决约瑟夫（Josephus）问题。约瑟夫问题为：n个人围成一圈，从第S个人开始报数1，2，m，数到m的人出圈，
41、然后从出圈的下一个人开始重复此过程，直到全部人出圈。要求在给出m，n，s后，能输出出圈序列。分析：n个人可以用1，2，n进行编号，然后存入一个一维数组中，若某个人出圈，则将后面的人往前移一个数组位置，最后面的位置被空出，可以存放出圈人的编号，再对前面n-1个人重复此过程，直到剩下一个人为止，则此时数组中存放的值为出圈人的反序。49算法描述如下：const int n=人数;const int m=报数上界;const int s=报数开始位置;void josephus(int an+1,int m,int s)int i,j,k,w,s1;for(i=1;i=2;i-)s1=(s1+m-1)
42、%i;/求得出圈人的位置 if(s1=0)s1=i;w=as1;/w用于存放出圈人的位置 for(j=s1;j=1;k-)coutaksetw(2);/输出出圈的顺序 coutnext;pb=lb-next;lc=la;lc-next=NULL;r=lc;while(pa!=NULL)&(pb!=NULL)if(pa-datadata)r-next=pa;r=pa;pa=pa-next;else r-next=pb;r=pb;pb=pb-next;if(pa=NULL)r-next=pb;else r-next=pa;假设la表长度为n，lb表长度为m，则该算法的时间复杂度为O(nm)。52【
43、例2-8】假设有一个顺序表a，类型为sequenlist，表中有n个元素，表中的元素全部为整型，即elemtype=int，现要求将该表分解为两个顺序表b、c，使b中的元素全部是偶数，c中的元素全部是奇数。算法描述如下：#includeconst int maxsize=100;/线性表的最大长度class sequenlist public:int amaxsize;int len;sequenlist a,b,c;53void div(sequenlist a,int n)b.len=0;c.len=0;for(int i=1;i=n;i+)if(a.ai%2=0)b.len+;b.ab.len=a.ai;else c.len+;c.ac.len=a.ai;void print(sequenlist x)for(int i=1;i=x.len;i+)coutx.ai ;coutendl;54void main()int n;coutn;coutendl;cout请输入表中元素：endl;for(int i=1;ia.ai;a.len=n;print(a);/输出线性表adiv(a,n);/分解线性表a为b和cprint(b);/输出线性表bprint(c);/输出线性表c
