《CH2 线性表.ppt》由会员分享，可在线阅读，更多相关《CH2 线性表.ppt（65页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章第二章 线性表线性表线性结构线性结构特点特点：在数据元素的非空有限集中：在数据元素的非空有限集中l存在存在唯一唯一的一个被称作的一个被称作“第一个第一个”的数据元素的数据元素l存在存在唯一唯一的一个被称作的一个被称作“最后一个最后一个”的数据元素的数据元素l除第一个外，集合中每个数据元素均除第一个外，集合中每个数据元素均只有一个前驱只有一个前驱l除最后一个外，集合中每个数据元素均除最后一个外，集合中每个数据元素均只有一个后继只有一个后继2.1 2.1 线性表的逻辑结构线性表的逻辑结构l定义：一个线性表是定义：一个线性表是n n个数据元素的有限序列个数据元素的有限序列例例 英文字母表英文字
2、母表（A,B,C,.Z)是一个线性表是一个线性表例例数据元素数据元素例例 一副扑克的点数一副扑克的点数 （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；其余的内部结点其余的内部结点a ai i(2in-1
3、)(2in-1)都有且仅有一个直接都有且仅有一个直接前趋前趋a ai-1i-1和一个直接后继和一个直接后继a ai+1i+1。线性表是一种典型的线性结构。数据的运算是定义在线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上逻辑结构上的，而运算的具体实现则是在存储结构上进行的。进行的。l特征：特征：元素个数元素个数nn表长度，表长度，n=0n=0空表空表11ini=0 数据关系：数据关系：Rl=ai-1，ai|ai-1，ai D，i=1,2,n 基本操作：基本操作：InitList(&L)DestroyList(&L)ClearList(&L)ListE
4、mpty(L)ListLength(L)GetElemList(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 算法算法算法算法2.12.12.12.1例例2-1 2-1 利用两个线性表利用两个线性表LALA和和LBLB分别表示两个集合分别表示两个集合A A和和B B，现现要求一个新的集合要求一个新的集合A=ABA=AB。void union(Li
5、st&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)）算法算法算法算法2.22.22.22.2例例2-2 2-2 巳知线性表巳知线性表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
7、);+j;while(I=la-len)getelem(la，I+，ai);listinsert(lc，+k，ai);while(j=lb-len)getelem(lb，j+，bj);listinsert(lc，+k，bi);算法的时间复杂度：算法的时间复杂度：O（ListLength(LA)+ListLength(LB)）2.2 2.2 线性表的顺序存储结构线性表的顺序存储结构l顺序表：顺序表：定义：用一组地址连续的存储单元存放一个线性表叫定义：用一组地址连续的存储单元存放一个线性表叫 元素地址计算方法：元素地址计算方法：lLOC(aiLOC(ai)=LOC(a1)+(i-1)*L)=LOC
8、(a1)+(i-1)*LlLOC(ai+1)=LOC(ai+1)=LOC(aiLOC(ai)+L)+Ll其中：其中：L L 一个元素占用的存储单元个数一个元素占用的存储单元个数LOC(aiLOC(ai)线性表第线性表第i i个元素的地址个元素的地址特点：特点：l实现实现逻辑上相邻逻辑上相邻物理地址相邻物理地址相邻l实现实现随机存取随机存取实现：实现：可用可用C C语言的一维数组实现语言的一维数组实现a1a2an01n-112n内存内存V数组下标数组下标元素序号元素序号M-1typedef int DATATYPE;#define M 1000DATATYPE dataM;例例 typedef
9、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;l插入插入定义：线性表的插入是指在第定义：线性表的插入是指在第i i（1 1 i i n+1 n+1）个元素之前个元素之前插入一个新的数据元素插入一个
11、新的数据元素x x，使长度为使长度为n n的线性表的线性表变为变为n+1n+1 变成变成长度为长度为n+1n+1的线性表的线性表 需将第需将第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(“overflow”);exit(overflow);for(j=l.length-1;j=i-1;j-)l.dataj+
12、1=l.dataj;l.datai-1=x;l.length+;内存内存a1a2aiai+1an01i-1V数组下标数组下标n-1in12i元素序号元素序号i+1nn+1内存内存a1a2aiai+1an01i-1V数组下标数组下标n-1in12i元素序号元素序号i+1nn+1an-1x分析算法的复杂度分析算法的复杂度分析算法的复杂度分析算法的复杂度 这里的问题规模是表的长度，设它的值为。该算法的时这里的问题规模是表的长度，设它的值为。该算法的时间主要化费在循环的结点后移语句上，该语句的执行次数间主要化费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是。由此可看出，所需移动结点的（
13、即移动结点的次数）是。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。次数不仅依赖于表的长度，而且还与插入位置有关。当当i=n+1时，由于循环变量的终值大于初值，结点后移时，由于循环变量的终值大于初值，结点后移语句将不进行；这是语句将不进行；这是最好最好情况，其时间复杂度情况，其时间复杂度O（1）；）；当当i=1时，结点后移语句将循环执行时，结点后移语句将循环执行n次，需移动表中次，需移动表中所有结点，这是所有结点，这是最坏最坏情况，其时间复杂度为情况，其时间复杂度为O（n）。）。算法时间复杂度算法时间复杂度T(n)T(n)l设设PiPi是在第是在第i i个元素之前插入
14、一个元素的概率，则在长个元素之前插入一个元素的概率，则在长度为度为n n的线性表中插入一个元素时，所需移动的元素次的线性表中插入一个元素时，所需移动的元素次数的平均次数为：数的平均次数为：也就是说，在顺序表上做插入运算，平均要移动表上一半结也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长点。当表长 n较大时，算法的效率相当低。虽然较大时，算法的效率相当低。虽然Eis(n)中中n的的的系数较小，但就数量级而言，它仍然是线性阶的。因此算的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为法的平均时间复杂度为O(n)。动态l删除删除定义：线性表的删除是指将第定义：线
15、性表的删除是指将第i i（1 1 i i n n）个元素删除，个元素删除，使长度为使长度为n n的线性表的线性表 变成变成长度为长度为n-1n-1的线性表的线性表 需将第需将第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).link(*p).linkp-linkp-link表示表示p p指向结点的指针域
16、指向结点的指针域l线性链表线性链表定义：结点中只含一个指针域的链表叫定义：结点中只含一个指针域的链表叫，也叫单链表，也叫单链表 typedef listnode *linklist;listnode *p;linklist head;注意：注意：注意：注意：区分区分指针变量指针变量和和结点变量结点变量这两个不同的概念。这两个不同的概念。P为动态变量，它是通过标准函数生成的，即为动态变量，它是通过标准函数生成的，即 p=(listnode*)malloc(sizeof(listnode);函数函数malloc分配了一个类型为分配了一个类型为listnode的结点变量的空间，的结点变量的空间，并将
17、其首地址放入指针变量并将其首地址放入指针变量p中。一旦中。一旦p所指的结点变量不所指的结点变量不再需要了，又可通过标准函数再需要了，又可通过标准函数 free(p)释放所指的结点释放所指的结点变量空间。变量空间。指针变量指针变量P（其值为结点地址）和结点变量（其值为结点地址）和结点变量*P之间的关系。之间的关系。ha1a2头结点头结点头结点头结点an .h空表空表头结点：头结点：在单链表第一个结点前附设一个结点叫在单链表第一个结点前附设一个结点叫头结点指针域为空表示线性表为空头结点指针域为空表示线性表为空一、建立单链表一、建立单链表 假设线性表中结点的数据类型是字符，我们逐个输假设线性表中结点
18、的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符入这些字符型的结点，并以换行符n为输入结束为输入结束标记。动态地建立单链表的常用方法有如下两种：标记。动态地建立单链表的常用方法有如下两种：1、头插法建表、头插法建表 该方法从一个空表开始，重复读入数据，生成新该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志新结点插入到当前链表的表头上，直到读入结束标志为止。为止。h头结点头结点an 0h头结点头结点an-10an a2.h头结点头结点an-10an ha1
19、a2头结点头结点an .0h头结点头结点0 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);listlink createlist(int n)int data;linklist head;listnode*p head=null;for(i=n;i0;-i)p=(listno
20、de*)malloc(sizeof(listnode);scanf(%d，&pdata);pnext=head;head=p;return(head);2、尾插法建表、尾插法建表 头插法建立链表虽然算法简单，但生成的链表中头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针的表尾上，为此必须增加一个尾指针r，使其始终指向，使其始终指向当前链表的尾结点。当前链表的尾结点。linklis
21、t creater()char ch;linklist head;listnode *p，*r;/(，*head;)head=NULL;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语句语句的作用是为了分别的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就处理空表和
23、非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表是结束标志符，则链表headhead是空表，尾指针是空表，尾指针r r亦为空，结点亦为空，结点*r r不存在；否则链表不存在；否则链表headhead非空，最后一个尾结点非空，最后一个尾结点*r r是终端结是终端结点，应将其指针域置空。点，应将其指针域置空。如果我们在链表的开始结点之前附加一个结点，并称如果我们在链表的开始结点之前附加一个结点，并称它为它为头结点头结点，那么会带来以下两个优点：，那么会带来以下两个优点：a a、由于开始结点的位置被存放在头结点的指针由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的
24、操作就和在表的域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊处理；其它位置上的操作一致，无需进行特殊处理；b b、无论链表是否为空，其头指针是指向头结点无论链表是否为空，其头指针是指向头结点在的非空指针（空表中头结点的指针域为空），因此在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。空表和非空表的处理也就统一了。linklist createlistr1()char ch;linklist head=(linklist)malloc(sizeof(listnode);listnode *p，*r；r=head;while(ch=ge
25、tchar()!=n p=(listnode*)malloc(sizeof(listnode);pdata=ch;pnext=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;以上算法的时间复杂度均为以上算法的时间复杂度均为O(nO(n)二、查找运算二、查找运算 1、按序号
26、查找、按序号查找 在链表中，即使知道被访问结点的序号在链表中，即使知道被访问结点的序号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的结点，若有的话，则返回首次找到的其值为的结点，若有的话，则返回首次找到的其值为keykey的结点的存的结点的存储位置；否则返回储位置；否则返回NULLNULL。查找过程从
28、开始结点出发，顺着链查找过程从开始结点出发，顺着链表逐个将结点的值和给定值表逐个将结点的值和给定值keykey作比较。其算法如下：作比较。其算法如下：ListnodeListnode*locatenode(linklistlocatenode(linklist head head，intint key)key)listnodelistnode*p=headnext;*p=headnext;while(p&pdata!=key)while(p&pdata!=key)p=pnext;p=pnext;return p;return p;该算法的执行时间亦与输入实例中的的取值该算法的执行时间亦与输入实
29、例中的的取值keykey有关，其有关，其平均时间复杂度的分析类似于按序号查找，也为平均时间复杂度的分析类似于按序号查找，也为O(n)O(n)。pabxs三、插入运算三、插入运算 插入运算是将值为插入运算是将值为x x的新结点插入到表的第的新结点插入到表的第i i个结点的位个结点的位置上，即插入到置上，即插入到ai-1ai-1与与aiai之间。因此，我们必须首先找到之间。因此，我们必须首先找到ai-1ai-1的存储位置的存储位置p p，然后生成一个数据域为，然后生成一个数据域为x x的新结点的新结点*p p，并令结点并令结点*p p的指针域指向新结点，新结点的指针域指向结的指针域指向新结点，新结
30、点的指针域指向结点点aiai。从而实现三个结点。从而实现三个结点ai-1ai-1，x x和和aiai之间的逻辑关系的变之间的逻辑关系的变化，插入过程如：化，插入过程如：q-next=p-next;p-next=q;具体算法如下：具体算法如下：void insertnode(linklist head，datetype x，int i)listnode *p，*q;p=getnode(head，i-1);if(p=NULL)error(position error);q=(listnode*)malloc(sizeof(listnode);qdata=x;qnext=pnext;pnext=q;
31、设链表的长度为设链表的长度为n，合法的插入，合法的插入位置是位置是1in+1。注意当。注意当i=1时，时，getnode找到的是头结点，当找到的是头结点，当i=n+1时，时，getnode找到的是结点找到的是结点an。因此，用。因此，用i-1做实参调用做实参调用getnode时可完成插入位置的合时可完成插入位置的合法性检查。算法的时间主要耗法性检查。算法的时间主要耗费在查找操作费在查找操作getnode上，上，故时故时间复杂度亦为间复杂度亦为O(n)。pabc四、删除运算四、删除运算 删除运算是将表的第删除运算是将表的第i i个结点删去。因为在单链表中个结点删去。因为在单链表中结点结点aiai
32、的存储地址是在其直接前趋结点的存储地址是在其直接前趋结点a i-1a i-1的指针域的指针域nextnext中，所以我们必须首先找到中，所以我们必须首先找到a i-1a i-1的存储位置的存储位置p p。然后。然后令令pnextpnext指向指向aiai的直接后继结点，即把的直接后继结点，即把aiai从链上摘下。从链上摘下。最后释放结点最后释放结点aiai的空间，将其归还给的空间，将其归还给“存储池存储池”。此过程。此过程为：为：p-link=p-link-link;具体算法如下：具体算法如下：void deletelist(linklist head，int i)listnode*p，*r;
33、p=getnode(head，i-1);if(p=NULL|pnext=NULL)return ERROR;r=pnext;pnext=rnext;free(r);设单链表的长度为设单链表的长度为n，则删去第，则删去第i个结点仅个结点仅当当1in时是合法的。注意，当时是合法的。注意，当i=n+1时，时，虽然被删结点不存在，但其前趋结点却存虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接在，它是终端结点。因此被删结点的直接前趋前趋*p存在并不意味着被删结点就一定存存在并不意味着被删结点就一定存在，仅当在，仅当*p存在（即存在（即p!=NULL）且）且*p不是不是终端结点终
34、端结点（即（即pnext!=NULL）时，才能）时，才能确定被删结点存在。确定被删结点存在。显然此算法的时间复杂度也是显然此算法的时间复杂度也是O(n)。从上面的讨论可以看出，链表上实现插入和删除运从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针。算，无须移动结点，仅需修改指针。单链表特点单链表特点l它是一种它是一种动态结构动态结构，整个存储空间为多个链表共用，整个存储空间为多个链表共用l不需预先分配不需预先分配空间空间l指针占用指针占用额外额外存储空间存储空间l不能随机存取不能随机存取，查找速度慢，查找速度慢补：补：补：补：（1）线性表中的数据元素在存储单元中的存放
35、顺序与）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；逻辑顺序不一定一致；（2）在对线性表操作时，只能通过头指针进入链表，）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。有这种特点的存取方式被称为顺序存取方式。静态单链表 l循环链表循环链表(circular linked list)(circular linked list)循环链表是表
36、中最后一个结点的指针指向头结点，使链循环链表是表中最后一个结点的指针指向头结点，使链表构成环状表构成环状特点：从表中任一结点出发均可找到表中其他结点，提特点：从表中任一结点出发均可找到表中其他结点，提高查找效率高查找效率操作与单链表基本一致操作与单链表基本一致,循环条件不同循环条件不同l单链表单链表p p或或p-link=NULLp-link=NULLl循环链表循环链表p p或或p-link=Hp-link=Hhh空空表表l双向链表（双向链表（double linked listdouble linked list）在循环链表中，访问结点的特点：在循环链表中，访问结点的特点：访问后继结点，只需
37、访问后继结点，只需要向后走一步，而访问前驱结点，就需要转一圈。要向后走一步，而访问前驱结点，就需要转一圈。结论：结论：循环链表并不适用于经常访问前驱结点的情况。循环链表并不适用于经常访问前驱结点的情况。解决方法：解决方法：在需要频繁地同时访问前驱和后继结点的时候，在需要频繁地同时访问前驱和后继结点的时候，使用双向链表。使用双向链表。双向链表：双向链表：双向链表：双向链表：就是每个结点有两个指针域。一个指向后继结就是每个结点有两个指针域。一个指向后继结点，另一个指向前驱结点。点，另一个指向前驱结点。结点定义结点定义typedef struct node datatype element;stru
38、ct node*prior,*next;JD;priorelement nextL空双向循环链表：空双向循环链表：非空双向循环链表：非空双向循环链表：LABbcapp-prior-next=p=p-next-proir;bcaaPPvoid del_dulist(JD*p)p-prior-next=p-next;p-next-prior=p-prior;free(p);删除删除l算法描述算法描述l算法评价：算法评价：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*)m
39、alloc(sizeof(JD);s-element=x;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;l算法描述算法描述xSbaP 插入插入算法评价：算法评价：T(n)=O(1)2.4 2.4 线性表的应用举例线性表的应用举例 一元多项式的表示及相加一元多项式的表示及相加l一元多项式的表示：一元多项式的表示：可用线性表可用线性表P P表示表示但对但对S(x)S(x)这样的多项式浪费空间这样的多项式浪费空间一般一般其中其中用数据域含两个数据项的线性表表示用数据域含两个数据项的线性表表示其存储结构可以用顺序存储结构，也可以用单链表其存储结构可
40、以用顺序存储结构，也可以用单链表l单链表的结点定义单链表的结点定义coefexpnext-1A7 0 3 1 9 8 5 17 -1B8 1 22 7 -9 8 -1C7 0 11 1 22 7 5 17 l一元多项式相加一元多项式相加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-e
41、xp:q结点是结果多项式中的一项，结点是结果多项式中的一项，将将q插在插在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上即可上即可l运算规则运算规则q-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7
42、0 11 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 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre-1pa7 0 11 1 22 7 5 17 l算法描述算法描述void add_poly(JD*pa,JD*pb)JD*p,*q,*u,*pre;int x;p=pa-next;q=pb-next;pre=pa;while(p!=N
43、ULL)&(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-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);线性表的应用举例 约瑟夫（Joseph）问题 编号为编号为1 1，2 2，n n的的n n个人按顺时针方向围坐在个人按顺时针方
44、向围坐在一张圆桌旁，每个人手中持有一个密码（正整数）。首先一张圆桌旁，每个人手中持有一个密码（正整数）。首先输入一个正整数作为报数上限值输入一个正整数作为报数上限值m m，然后，从第一个人开始然后，从第一个人开始按顺时针方向自按顺时针方向自1 1开始顺序报数，报到开始顺序报数，报到m m的人离开桌旁，并的人离开桌旁，并将他手中的密码作为新的将他手中的密码作为新的m m值，从顺时针方向的下一个就坐值，从顺时针方向的下一个就坐在桌旁的人人开始重新从在桌旁的人人开始重新从1 1报数，如此下去，直至所有人全报数，如此下去，直至所有人全部离开桌旁为止。部离开桌旁为止。假设有假设有7 7个人，编号从个人，
45、编号从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。数据结构的分析：数据结构的分析：这个问题的主角是这个问题的主角是n n个人，每个人需要描述的信息有：个人，每个人需要描述的信息有：编号、密码和是否在桌旁的状态。假设有编号、密码和是否在桌旁的状态。假设有7 7个人，他们个人，他们的信息可以表示成下面的形式。的信息可以表示成下面的形式。算法描述：算法描述：让让n
46、n个人围坐在一张圆桌旁；个人围坐在一张圆桌旁；for(i=1;i=n;i+)for(i=1;i=n;i+)从从1 1开始报数，报到开始报数，报到m m停止；停止；报到报到m m的人离开桌子；的人离开桌子；#define LIST_MAX_LENGTH 7#define n LIST_MAX_LENGTHtypedef int EntryType;/将将EntryType定义为定义为int类型类型void Joseph(int code,int n)顺序存储结构：顺序存储结构：顺序存储结构：顺序存储结构：最终的算法实现最终的算法实现/通过一维数组通过一维数组code带入带入n个人手中的密码，个人
47、手中的密码，n是开始就坐在桌旁是开始就坐在桌旁的人数的人数 SQ_LIST people;int temp,m;/m是报数的上限值是报数的上限值 scanf(“%d”,&m);/输入最初的输入最初的m if(InitList(&people)=ERROR)exit ERROR;for(i=1;i=n;i+)if(ListInsert(&people,i,codei-1)=ERROR)exit ERROR;position=0;/记录当前报数人的编号记录当前报数人的编号 count=0;/记录当前所报的数目记录当前所报的数目 for(i=1;i0)count+;while(count!=m);p
48、rintf(“%d”,position);/输出当前离开桌旁人的编号输出当前离开桌旁人的编号 GetElem(people,position,&m);people.itemposition-1=-people.itemposition-1;/将密码变为负值将密码变为负值 链式存储结构：链式存储结构：使用一个不带头结点的循环单链表结构。结点结构为：使用一个不带头结点的循环单链表结构。结点结构为：图图 2-10 No code next用用C语言定义语言定义typedef struct /循环链表中每个结点的数据域部分的类型循环链表中每个结点的数据域部分的类型 int No;/编号编号 int c
49、ode;/密码密码INFO;typedef INFO EntryType;算法算法void Joseph(int code,int n)LINK_LIST people;NODE*position,*pre;/position指向当前报数的结点指向当前报数的结点 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);重点：重点：线性表的顺序存储；线性表的顺序存储；线性表的链式存储；线性表的链式存储；顺序表的插入、删除顺序表的插入、删除 单链表的插入、删除单链表的插入、删除难点：难点：双向链表的系列操作双向链表的系列操作 线性表的应用。线性表的应用。