CH2数据结构课件.ppt

1、线性结构线性结构特点特点：在数据元素的非空有限集中：在数据元素的非空有限集中存在存在唯一唯一的一个被称作的一个被称作“第一个第一个”的数据元素的数据元素存在存在唯一唯一的一个被称作的一个被称作“最后一个最后一个”的数据元素的数据元素除第一个外，集合中的每个数据元素均除第一个外，集合中的每个数据元素均只有一个只有一个前驱前驱除最后一个外，集合中的每个数据元素均除最后一个外，集合中的每个数据元素均只有一只有一个后继个后继 2.1 2.1 线性表的逻辑结构线性表的逻辑结构定义：一个线性表是定义：一个线性表是n n个数据元素的有限序列个数据元素的有限序列niaaaa,21如例例 英文字母表英文字母表（

2、A,B,C,.Z)是一个线性表是一个线性表例例学号姓名年龄001张三18002李四19数据元素数据元素例例 一副扑克的点数一副扑克的点数 （2 2，3 3，4 4，J J，Q Q，K K，A A）从以上例子可看出线性表的逻辑特征是：从以上例子可看出线性表的逻辑特征是： 在非空的线性表，有且仅有一个开始结点在非空的线性表，有且仅有一个开始结点a a1 1，它没，它没有直接前趋，而仅有一个直接后继有直接前趋，而仅有一个直接后继a a2 2； 有且仅有一个终端结点有且仅有一个终端结点a an n，它没有直接后继，而仅，它没有直接后继，而仅有一个直接前趋有一个直接前趋a an-1n-1； 其余的内部结

3、点其余的内部结点a ai i(2in-1)(2in-1)都有且仅有一个直接都有且仅有一个直接前趋前趋a ai-1i-1和一个直接后继和一个直接后继a ai+1i+1。 线性表是一种典型的线性结构。数据的运算是定义线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。上进行的。特征：特征： 元素个数元素个数n n表长度，表长度，n=0n=0空表空表 11ini=0 数据关系：数据关系：Rl = ai-1， ai | ai-1， ai D，i=1,2,n 基本操作：基本操作： InitList(&L) De

4、stroyList(&L) ClearList(&L) ListEmpty(L) ListLength(L) GetElem(L,I,&e) LocateElem(L,e,compare() PriorElem(L,cur_e,&pre_e) NextElem(L,cur_e,&next_e) ListInsert(&L,i,e) ListDelete(&L,i,&e) ListTraverse(L,visit() ADT List利用两个线性表利用两个线性表LALA和和LBLB分别表示两个集合分别表示两个集合A A和和B B，现要求一个新的集合现要求一个新的集合A=ABA=AB。 void

5、union(List &La，List Lb) La-len=listlength(La); Lb-len=listlength(Lb); for(I=1;I=lb-len;I+) getelem(lb，I，e); if(!locateelem(la，e，equal) listinsert(la，+la-en，e) 算法的时间复杂度：算法的时间复杂度：O（ListLength(LA) ListLength(LB)） 巳知线性表巳知线性表LALA和线性表和线性表LBLB中的数据元中的数据元素按值非递减有序排列，现要求将素按值非递减有序排列，现要求将LALA和和LBLB归并归并为一个新的线性表为一

6、个新的线性表LCLC，且，且LCLC中的元素仍按值非中的元素仍按值非递减有序排列。递减有序排列。void mergelist(list la，list lb，list &lc) initlist(lc); I=j=1;k=0; la-len=listlength(la); lb-len=listlength(lb); while(I=la-len)&(j=lb-len) getelem(la，I，ai);getelem(lb，j，bj); if(ai=bj)listinsert(lc，+k，ai);+I; elselistinsert(lc，+k，bj);+j; while(I=la-len)

7、 getelem(la，I+，ai);listinsert(lc，+k，ai); while(j=lb-len) getelem(lb，j+，bj);listinsert(lc，+k，bj); 算法的时间复杂度：算法的时间复杂度：O（ListLength(LA) +ListLength(LB)） 2.2 2.2 线性表的顺序存储结构线性表的顺序存储结构顺序表：顺序表： 定义：用一组地址连续的存储单元存放一个线性表叫定义：用一组地址连续的存储单元存放一个线性表叫 元素地址计算方法：元素地址计算方法：LOC(aiLOC(ai) = LOC(a1) + (i-1) = LOC(a1) + (i-1)

8、* *L LLOC(ai+1) = LOC(aiLOC(ai+1) = LOC(ai) + L) + L其中：其中：L L 一个元素占用的存储单元个数一个元素占用的存储单元个数LOC(aiLOC(ai) ) 线性表第线性表第i i个元素的地址个元素的地址 特点：特点：实现实现逻辑上相邻逻辑上相邻物理地址相邻物理地址相邻实现实现随机存取随机存取 实现：实现：可用可用C C语言的一维数组实现语言的一维数组实现a1a2an01n-112n内存内存V数组下标数组下标元素序号元素序号M-1typedef int DATATYPE; #define M 1000DATATYPE dataM;例例 type

9、def struct card int num; char name20; char author10; char publisher30; float price;DATATYPE;DATATYPE libraryM; 备用空间备用空间数据元素不是简单类型时数据元素不是简单类型时,可定义可定义结构体数组结构体数组或动态申请和释放内存或动态申请和释放内存DATATYPE *pData = (DATATYPE *)malloc(M*sizeof(DATATYPE);free(pData); 由于由于C语言中的一维数组也是采用顺序存储表示，故可语言中的一维数组也是采用顺序存储表示，故可以用数组类型

10、来描述顺序表。又因为除了用数组来存以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺示线性表的长度属性，所以我们用结构类型来定义顺序表类型。序表类型。 # define ListSize 100 typedef int DataType; typedef struct DataType dataListSize; int length; Sqlist;插入插入 定义：线性表的插入是指在第定义：线性表的插入是指在第i i（1 1 i i n+1 n+1）个元素）个

11、元素之前插入一个新的数据元素之前插入一个新的数据元素x x，使长度为，使长度为n n的线性表的线性表变变为为n+1n+1niiaaaaa,1,21 变成变成长度为长度为n+1n+1的线性表的线性表niiaaxaaa,1,21 需将第需将第i i至第至第n n共共（n-i+1)n-i+1)个元素后移个元素后移 算法算法Void InsertList(Sqlist*L，DataType x，int I) int j; if (Il.length+1) printf(“Position error”); return ERROR; if (l.length=ListSize) printf(“ove

12、rflow”); exit(overflow); for (j=l.length-1;j=I-1;j-) l.dataj+1=l.dataj; l.dataI-1=x; l.length+; 内存内存a a1 1a a2 2a ai ia ai+1i+1a an n0 01 1i-1i-1V V数组下标数组下标n-1n-1i in n1 12 2i i元素序号元素序号i+1i+1n nn+1n+1内存内存a a1 1a a2 2a ai ia ai+1i+1a an n0 01 1i-1i-1V V数组下标数组下标n-1n-1i in n1 12 2i i元素序号元素序号i+1i+1n nn+

13、1n+1a an-1n-1x x 这里的问题规模是表的长度，设它的值为。该算法的这里的问题规模是表的长度，设它的值为。该算法的时间主要化费在循环的结点后移语句上，该语句的执行次时间主要化费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是。由此可看出，所需移动结点数（即移动结点的次数）是。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。的次数不仅依赖于表的长度，而且还与插入位置有关。 当当i=n+1时，由于循环变量的终值大于初值，结点后移时，由于循环变量的终值大于初值，结点后移语句将不进行；这是语句将不进行；这是最好最好情况，其时间复杂度情况，其时间复杂度O

14、（1）；）； 当当i=1时，结点后移语句将循环执行时，结点后移语句将循环执行n次，需移动表中次，需移动表中所有结点，这是所有结点，这是最坏最坏情况，其时间复杂度为情况，其时间复杂度为O（n）。）。 算法时间复杂度算法时间复杂度T(n)T(n)设设PiPi是在第是在第i i个元素之前插入一个元素的概率，个元素之前插入一个元素的概率，则在长度为则在长度为n n的线性表中插入一个元素时，所需的线性表中插入一个元素时，所需移动的元素次数的平均次数为：移动的元素次数的平均次数为：11)1(niiinPEis nOnTninnEisnPnii112)1(1111则若认为 也就是说，在顺序表上做插入运算，平

15、均要移动表上一半也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长结点。当表长 n较大时，算法的效率相当低。虽然较大时，算法的效率相当低。虽然Eis(n)中中n的的系数较小，但就数量级而言，它仍然是线性阶的。因的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为此算法的平均时间复杂度为O(n)。动态删除删除 定义：线性表的删除是指将第定义：线性表的删除是指将第i i（1 1 i i n n）个元素删）个元素删除，使长度为除，使长度为n n的线性表的线性表niiaaaaa,1,21 变成变成长度为长度为n-1n-1的线性表的线性表niiaaaaa,11,21 需

16、将第需将第i+1i+1至第至第n n共共（n-i)n-i)个元素前移个元素前移算法 Void deleteList (Sqlist*L，int i) int j; if (il.length) printf(“Position error”); return ERROR for (j=i;jdatap-data表示表示p p指向结点的数据域指向结点的数据域( (* *p).linkp).linkp-linkp-link表示表示p p指向结点的指针域指向结点的指针域线性链表线性链表 定义：结点中只含一个指针域的链表叫定义：结点中只含一个指针域的链表叫 ，也叫单链表，也叫单链表 typedef l

17、istnode *linklist; listnode *p; linklist head;注意区分注意区分指针变量指针变量和和结点变量结点变量这两个不同的概念。这两个不同的概念。 P为动态变量，它是通过标准函数生成的，即为动态变量，它是通过标准函数生成的，即 p=(listnode*)malloc(sizeof(listnode);函数函数malloc分配了一个类型为分配了一个类型为listnode的结点变量的空间，的结点变量的空间，并将其首地址放入指针变量并将其首地址放入指针变量p中。一旦中。一旦p所指的结点变量不所指的结点变量不再需要了，又可通过标准函数再需要了，又可通过标准函数 fre

18、e ( p )释放所指的结点变量空间。释放所指的结点变量空间。指针变量指针变量P（其值为结点地址）和结点变量（其值为结点地址）和结点变量*P之间的关系。之间的关系。一、建立单链表一、建立单链表 假设线性表中结点的数据类型是字符，我们逐个假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符输入这些字符型的结点，并以换行符n为输入结束为输入结束标记。动态地建立单链表的常用方法有如下两种：标记。动态地建立单链表的常用方法有如下两种： 1、头插法建表、头插法建表 该方法从一个空表开始，重复读入数据，生成该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域

19、中，然后新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标将新结点插入到当前链表的表头上，直到读入结束标志为止。志为止。a2.h头结点头结点an-10an linklist createlistf (void) char ch; linklist head; listnode *p; head=null; ch=getchar( ); while (ch!= n) p=(listnode*)malloc(sizeof(listnode); pdata=ch; pnext=head; head=p; ch=getchar( ); return (head

20、); 2、尾插法建表、尾插法建表 头插法建立链表虽然算法简单，但生成的链表中头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针的表尾上，为此必须增加一个尾指针r，使其始终指向，使其始终指向当前链表的尾结点。当前链表的尾结点。linklist creater( ) char ch; linklist head; listnode *p，*r; /(， *head;) head=NUL

21、L; r=NULL; while(ch=getchar( )!= n) p=(listnode *)malloc(sizeof(listnode); pdata=ch; if(head= =NULL) head=p; else rnext=p; r=p; if (r!=NULL) rnext=NULL; return(head); 第一个生成的结点是开始结点，将开始结点插入到空第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因操作和链表中其它位

22、置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中，而其余是开始结点的位置是存放在头指针（指针变量）中，而其余结点的位置是在其前趋结点的指针域中。结点的位置是在其前趋结点的指针域中。 算法中的算法中的第一个第一个ifif语句语句就是用来对第一个位置上的插入就是用来对第一个位置上的插入操作做特殊处理。算法中的操作做特殊处理。算法中的第二个第二个ifif语句语句的作用是为了分别的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表是结束标志符，则链表headhead是空表，尾指针是空表

23、，尾指针r r亦为空，结点亦为空，结点* *r r不存在；否则链表不存在；否则链表headhead非空，最后一个尾结点非空，最后一个尾结点* *r r是终端结是终端结点，应将其指针域置空。点，应将其指针域置空。如果我们在链表的开始结点之前附加一个结点，并称它如果我们在链表的开始结点之前附加一个结点，并称它为为头结点头结点，那么会带来以下两个优点：，那么会带来以下两个优点： 由于开始结点的位置被存放在头结点的指针域由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊处理；位置上的操作

24、一致，无需进行特殊处理； 无论链表是否为空，其头指针是指向头结点在无论链表是否为空，其头指针是指向头结点在的非空指针（空表中头结点的指针域为空），因此空表的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。和非空表的处理也就统一了。ha1a2头结点头结点an .h空表空表头结点：头结点：在单链表第一个结点前附设一个结点叫在单链表第一个结点前附设一个结点叫头结点指针域为空表示线性表为空头结点指针域为空表示线性表为空linklist createlistr1( ) char ch; linklist head=(linklist)malloc(sizeof(listnode)

25、; listnode *p，*r； r=head; while(ch=getchar( )!= n p=(listnode*)malloc(sizeof(listnode); pdata=ch; rnext=p; r=p; rnext=NULL; return(head); 上述算法里动态申请新结点空间时未加错误处理，可上述算法里动态申请新结点空间时未加错误处理，可作下列处理：作下列处理： p=(listnode*)malloc(sizeof(listnode) if(p=NULL) error(No space for node can be obtained); return ERROR;

26、以上算法的时间复杂度均为以上算法的时间复杂度均为O(n)O(n)二、查找运算二、查找运算 1、按序号查找、按序号查找 在链表中，即使知道被访问结点的序号在链表中，即使知道被访问结点的序号i，也不能象，也不能象顺序表中那样直接按序号顺序表中那样直接按序号i访问结点，而只能从链表的头访问结点，而只能从链表的头指针出发，顺链域指针出发，顺链域next逐个结点往下搜索，直到搜索到逐个结点往下搜索，直到搜索到第第i个结点为止。因此，链表不是随机存取结构。个结点为止。因此，链表不是随机存取结构。 设单链表的长度为设单链表的长度为n，要查找表中第，要查找表中第i个结点，仅当个结点，仅当1in时，时，i的值是

27、合法的。但有时需要找头结点的位的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第置，故我们将头结点看做是第0 个结点，其算法如下：个结点，其算法如下：Listnode * getnode(linklist head ， int i) int j; listnode * p; p=head;j=0; while(pnext & jnext; j+; if (i=j) return p; else return NULL; 2 2、按值查找、按值查找 按值查找是在链表中，查找是否有结点值等于给定值按值查找是在链表中，查找是否有结点值等于给定值keykey的结点，若有的话，则返回首次找到

28、的其值为的结点，若有的话，则返回首次找到的其值为keykey的结点的结点的存储位置；否则返回的存储位置；否则返回NULLNULL。查找过程从开始结点出发，顺。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值着链表逐个将结点的值和给定值keykey作比较。其算法如下：作比较。其算法如下： Listnode Listnode * * locatenode(linklist head locatenode(linklist head，intint key) key) listnode listnode * * p=headnext; p=headnext; while( p & pdata!=

29、key) while( p & pdata!=key) p=pnext; p=pnext; return p; return p; 该算法的执行时间亦与输入实例中的的取值该算法的执行时间亦与输入实例中的的取值keykey有关，有关，其平均时间复杂度的分析类似于按序号查找，也为其平均时间复杂度的分析类似于按序号查找，也为O(n)O(n)。pabxs三、插入运算三、插入运算 插入运算是将值为插入运算是将值为x x的新结点插入到表的第的新结点插入到表的第i i个结个结点的位置上，即插入到点的位置上，即插入到a ai-1i-1与与a ai i之间。因此，我们必须之间。因此，我们必须首先找到首先找到a

30、ai-1i-1的存储位置的存储位置p p，然后生成一个数据域为，然后生成一个数据域为x x的的新结点新结点* *p p，并令结点，并令结点* *p p的指针域指向新结点，新结点的指针域指向新结点，新结点的指针域指向结点的指针域指向结点a ai i。从而实现三个结点。从而实现三个结点a ai-1i-1，x x和和a ai i之之间的逻辑关系的变化，插入过程如：间的逻辑关系的变化，插入过程如：s-next=p-next;p-next=s;具体算法如下：具体算法如下： void insertnode(linklist head，datetype x，int i) listnode * p，*q; p

31、=getnode(head，i-1); if(p=NULL) error(position error); q=(listnode *) malloc(sizeof(listnode); qdata=x; qnext=pnext; pnext=q; 设链表的长度为设链表的长度为n，合法，合法的插入位置是的插入位置是1in+1。注意当。注意当i=1时，时，getnode找到的是头结点，当找到的是头结点，当i=n+1时，时，getnode找到的找到的是结点是结点an。因此，用。因此，用i-1做做实参调用实参调用getnode时可完时可完成插入位置的合法性检查成插入位置的合法性检查。算法的时间主要耗

32、费在。算法的时间主要耗费在查找操作查找操作getnode上，上，故故时间复杂度亦为时间复杂度亦为O(n)。pabc四、删除运算四、删除运算 删除运算是将表的第删除运算是将表的第i i个结点删去。因为在单链个结点删去。因为在单链表中结点表中结点a ai i的存储地址是在其直接前趋结点的存储地址是在其直接前趋结点a a i-1 i-1的指的指针域针域nextnext中，所以我们必须首先找到中，所以我们必须首先找到a a i-1 i-1的存储位置的存储位置p p。然后令然后令pnextpnext指向指向a ai i的直接后继结点，即把的直接后继结点，即把a ai i从链从链上摘下。最后释放结点上摘下

33、。最后释放结点a ai i的空间，将其归还给的空间，将其归还给“存储存储池池”。此过程为：。此过程为：p-link=p-link-link;具体算法如下：具体算法如下： void deletelist(linklist head， int i) listnode * p， *r; p=getnode(head，i-1); if(p= =NULL | pnext= =NULL) return ERROR; r=pnext; pnext=rnext; free( r ) ; 设单链表的长度为设单链表的长度为n，则删去，则删去第第i个结点仅当个结点仅当1in时是合时是合法的。注意，当法的。注意，当i

34、=n+1时，虽时，虽然被删结点不存在，但其前趋然被删结点不存在，但其前趋结点却存在，它是终端结点。结点却存在，它是终端结点。因此被删结点的直接前趋因此被删结点的直接前趋*p存存在并不意味着被删结点就一定在并不意味着被删结点就一定存在，仅当存在，仅当*p存在（即存在（即p!=NULL）且）且*p不是终端结不是终端结点点 （即（即pnext!=NULL）时）时，才能确定被删结点存在。，才能确定被删结点存在。显然此算法的时间复杂度也是显然此算法的时间复杂度也是O(n)。单链表特点单链表特点它是一种它是一种动态结构动态结构，整个存储空间为多个链表，整个存储空间为多个链表共用共用不需预先分配不需预先分配

35、空间空间指针占用指针占用额外额外存储空间存储空间不能随机存取不能随机存取，查找速度慢，查找速度慢静态单链表 循环链表循环链表(circular linked list)(circular linked list) 循环链表是表中最后一个结点的指针指向头结点，循环链表是表中最后一个结点的指针指向头结点，使链表构成环状使链表构成环状 特点：从表中任一结点出发均可找到表中其他结点，特点：从表中任一结点出发均可找到表中其他结点，提高查找效率提高查找效率 操作与单链表基本一致操作与单链表基本一致, ,循环条件不同循环条件不同单链表单链表p p或或p-link=NULLp-link=NULL循环链表循环链

36、表p p或或p-link=Hp-link=Hhh空空表表双向链表（双向链表（double linked listdouble linked list）在循环链表中，访问结点的特点：在循环链表中，访问结点的特点： 访问后继结点，只需访问后继结点，只需要向后走一步，而访问前驱结点，就需要转一圈。要向后走一步，而访问前驱结点，就需要转一圈。 结论：结论：循环链表并不适用于经常访问前驱结点的情况。循环链表并不适用于经常访问前驱结点的情况。 解决方法：解决方法：在需要频繁地同时访问前驱和后继结点的时在需要频繁地同时访问前驱和后继结点的时候，使用双向链表。候，使用双向链表。 就是每个结点有两个指针域。一个

37、指向后继就是每个结点有两个指针域。一个指向后继结点，另一个指向前驱结点。结点，另一个指向前驱结点。结点定义结点定义typedef struct node datatype element; struct node *prior,*next;JD;priorelement nextL空双向循环链表：空双向循环链表：非空双向循环链表：非空双向循环链表：LABbcapp-prior-next= p= p-next-proir;bcaPvoid del_dulist(JD *p) p-prior-next=p-next; p-next-prior=p-prior; free(p);删除删除算法描述算法

38、描述算法评价：算法评价：T(n)=O(1)p-prior-next=p-next;p-next-prior=p-prior;void ins_dulist(JD* p,int x) JD *s; s=(JD*)malloc(sizeof(JD); s-element=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s;算法描述算法描述算法评价：算法评价：T(n)=O(1)xSbaP插入插入 2.4 2.4 线性表的应用举例线性表的应用举例 一元多项式的表示及相加一元多项式的表示及相加一元多项式的表示：一元多项式的表示：nnnxPxPx

39、PPxP2210)(),(210nPPPPP可用线性表可用线性表P P表示表示200001000231)(xxxS但对但对S(x)S(x)这样的多项式浪费空间这样的多项式浪费空间一般一般emmnxPxPxPxPee2121)(其中其中为非零系数）（iPemee210用数据域含两个数据项的线性表表示用数据域含两个数据项的线性表表示 emPePePm，2121其存储结构可以用顺序存储结构，也可以用单链表其存储结构可以用顺序存储结构，也可以用单链表单链表的结点定义单链表的结点定义coefexpnext17787178522117)()()(9228)(5937)(xxxxBxAxCxxxxBxxxx

40、A-1A7 0 3 1 9 8 5 17 -1B8 1 22 7 -9 8 -1C7 0 11 1 22 7 5 17 一元多项式相加一元多项式相加typedef struct node int coef,exp; struct node *next;JD;设设p,qp,q分别指向分别指向A,BA,B中某一结点，中某一结点，p,qp,q初值是第一结点初值是第一结点比较比较p-exp与与q-expp-exp exp : p结点是结果多项式中的一结点是结果多项式中的一 项，项， p后移后移,q不动不动p-exp q-exp : q结点是结果多项式中的一项，结点是结果多项式中的一项， 将将q插在插在

41、p之前之前,q后移后移,p不动不动p-exp = q-exp : 系数相加系数相加0 ：从：从A表中删去表中删去p, 释放释放p,q，p,q后移后移 0 ：修改：修改p系数域系数域, 释放释放q，p,q后移后移直到直到p或或q为为NULL 若若q=NULL，结束，结束 若若p=NULL，将，将B中剩余部分连到中剩余部分连到A上即可上即可运算规则运算规则q-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre-1pa7 0 11 1 22 7 5 17 算法描述算法描述voi

42、d add_poly(JD *pa,JD *pb) JD *p,*q,*u,*pre; int x; p = pa-next; q = pb-next; pre = pa; while( p ! = NULL ) & ( q ! = NULL ) if ( p-exp exp ) pre = p; p = p-next; else if ( p-exp = q-exp ) x = p-coef + q-coef; if ( x ! = 0 ) p-coef = x; pre = p; else pre-next = p-next; free(p); p = pre-next; u=q; q=q

43、-next; free(u); else u=q-next; q-next=p; pre-next=q; pre=q; q=u; if ( q ! = NULL) pre-next=q; free(pb); 编号为编号为1 1，2 2，n n的的n n个人按顺时针方向围坐在一张个人按顺时针方向围坐在一张圆桌旁，每个人手中持有一个密码（正整数）。首先输入圆桌旁，每个人手中持有一个密码（正整数）。首先输入一个正整数作为报数上限值一个正整数作为报数上限值m m，然后，从第一个人开始按顺，然后，从第一个人开始按顺时针方向自时针方向自1 1开始顺序报数，报到开始顺序报数，报到m m的人离开桌旁，并将他的

44、人离开桌旁，并将他手中的密码作为新的手中的密码作为新的m m值，从顺时针方向的下一个就坐在桌值，从顺时针方向的下一个就坐在桌旁的人人开始重新从旁的人人开始重新从1 1报数，如此下去，直至所有人全部离报数，如此下去，直至所有人全部离开桌旁为止。开桌旁为止。 假设有假设有7 7个人，编号从个人，编号从1 1到到7 7，他们手中的密码分别，他们手中的密码分别是是3 3，1 1，7 7，2 2，4 4，8 8，4 4，最初的，最初的m=2m=2，通过报数，这，通过报数，这7 7个人离开桌旁的顺序应该是：个人离开桌旁的顺序应该是：2 2，3 3，5 5，4 4，7 7，6 6，1 1。数据结构的分析：数

45、据结构的分析： 这个问题的主角是这个问题的主角是n n个人，每个人需要描述的信息个人，每个人需要描述的信息有：编号、密码和是否在桌旁的状态。假设有有：编号、密码和是否在桌旁的状态。假设有7 7个人，个人，他们的信息可以表示成下面的形式。他们的信息可以表示成下面的形式。编号密码是否在桌旁的状态131211371421541681741算法描述：算法描述：让让n个人围坐在一张圆桌旁；个人围坐在一张圆桌旁；for (i=1;i=n;i+) 从从1开始报数，报到开始报数，报到m停止；停止； 报到报到m的人离开桌子；的人离开桌子；# define LIST_MAX_LENGTH 7# define n

46、LIST_MAX_LENGTHtypedef int EntryType; / 将将EntryType定义为定义为int类型类型void Joseph(int code ,int n)最终的算法实现最终的算法实现/通过一维数组通过一维数组code带入带入n个人手中的密码，个人手中的密码，n是开始就坐在桌是开始就坐在桌旁的人数旁的人数 SQ_LIST people; int temp,m; /m是报数的上限值是报数的上限值 scanf(“%d”,&m); /输入最初的输入最初的m if (InitList(&people)=ERROR) exit ERROR; for (i=1;i=n;i+)

47、if (ListInsert(&people,i,codei-1)=ERROR) exit ERROR; position=0; /记录当前报数人的编号记录当前报数人的编号 count=0; /记录当前所报的数目记录当前所报的数目 for (i=1;i0) count+; while (count!=m); printf(“%d”,position); /输出当前离开桌旁人的编号输出当前离开桌旁人的编号 GetElem(people,position,&m); people. tempposition-1 = -people.tempposition-1; /将密码变为负值将密码变为负值 链式

48、存储结构：链式存储结构： 使用一个不带头结点的循环单链表结构。结点结构为：使用一个不带头结点的循环单链表结构。结点结构为：图图 2-10 No code next用用C语言定义语言定义typedef struct /循环链表中每个结点的数据域部分的类型循环链表中每个结点的数据域部分的类型 int No; /编号编号 int code; /密码密码INFO;typedef INFO EntryType;算法算法void Joseph(int code,int n) LINK_LIST people; NODE *position,*pre; /position指向当前报数的结点指向当前报数的结点

49、 if (InitList(&people)=ERROR) exit ERROR; /初始化链表初始化链表people for (i=1;inext!=people.head) position= NextElem(people,position); scanf(“%d”,&m); /输入最初的输入最初的m for (i=1;iitem.No); /离开桌子处理离开桌子处理 m=position-item.code; pre=PriorElem(people,position); pre-next=position-next; free(position); position= pre; printf(“%d”,position-item.No); /处理最后一个人处理最后一个人 free(position);重点：重点：线性表的顺序存储；线性表的顺序存储； 线性表的链式存储；线性表的链式存储； 顺序表的插入、删除顺序表的插入、删除 单链表的插入、删除单链表的插入、删除难点：难点：双向链表的系列操作双向链表的系列操作 线性表的应用。线性表的应用。