数据结构——线性表

1、第二章第二章 线性表线性表学习要点：学习要点：o线性（表）结构的基本概念和特征。线性（表）结构的基本概念和特征。o线性表的顺序存储结构和在此结构下各种基本操作实现。线性表的顺序存储结构和在此结构下各种基本操作实现。o线性表的链式存储结构和在此结构下各种基本操作实现。线性表的链式存储结构和在此结构下各种基本操作实现。o分析比较线性表的两种存储结构的特点，优点和不足。分析比较线性表的两种存储结构的特点，优点和不足。o单链表的头结点与开始结点，循环链表的循环条件，具有对称结单链表的头结点与开始结点，循环链表的循环条件，具有对称结构的双向链表。构的双向链表。2.1 线性表概念线性表概念一对一的线性结构

2、一对一的线性结构2.1.1 线性表逻辑结构线性表逻辑结构p学生信息记录表，除了表头和表尾，每个记录有且仅有一个直接学生信息记录表，除了表头和表尾，每个记录有且仅有一个直接前趋和一个直接后继。前趋和一个直接后继。形式形式 （a0 ,a1 ,a2 , , an-1） 符合线性表的四个特征符合线性表的四个特征相关概念：直接前趋，直接后继，长度，空表相关概念：直接前趋，直接后继，长度，空表2.1.2 线性表的线性表的ADT描述描述ADT List is基本操作：基本操作：（1）List CreatList() 创建并返回一个空线性表；创建并返回一个空线性表；（2）ClearList(List L) 清

3、空线性表清空线性表L中的元素；中的元素；（3）int LengthList(List L) 返回线性表返回线性表L中的元素个数；中的元素个数；（4）int InsertPre(List L,int i, DataType x) 在线性表在线性表L中的第中的第i个位置之前插入值为个位置之前插入值为x的元素，并返回插入成功与否的标志；的元素，并返回插入成功与否的标志；（5）int InsertPost(List L,int i, DataType x) 在线性表在线性表L中的第中的第i个位置之后插入值为个位置之后插入值为x的元素，并返回插入成功与否的标志；的元素，并返回插入成功与否的标志；（6）i

4、nt DeletePos(List L,int i) 在线性表在线性表L中的删除第中的删除第i个位置上的元素，并返回删除成功与否的标志；个位置上的元素，并返回删除成功与否的标志；（7）int search(List L, DataType x) 在线性表在线性表L中的查找值为中的查找值为x的元素，并返回查找成功与否的标志；的元素，并返回查找成功与否的标志；（8）Display(List L) 输出线性表输出线性表L中的元素。中的元素。 ADT List 接下来学习线索：接下来学习线索： 存储方式：顺序，链式存储方式：顺序，链式 行为特征行为特征2.2 线性表的顺序存储结构线性表的顺序存储结构2

5、.2.1顺序存储结构顺序存储结构o用一组用一组连续连续的地址空间的地址空间依次依次存放线性表里的元素存放线性表里的元素a0 a1a2 an-1Loc（a0） 起始地址（基地址）起始地址（基地址）Loc(a1) = Loc(a0) + lengthLoc(a2) = Loc(a1) + length = Loc(a0) + 2* lengthLoc(a3) = Loc(a2) + length = Loc(a0) + 3* length所以，我们可以得出线性表第所以，我们可以得出线性表第i个元素地址的求址公式为：个元素地址的求址公式为：Loc(ai) = Loc(a0) + i* length

6、定义顺序表数据类型定义顺序表数据类型 00 struct SeqList01 02 int MAXNUM； /* 顺序表中可以存放元素的个数顺序表中可以存放元素的个数 */03 int n; /* 实际存放线性表中元素的个数，实际存放线性表中元素的个数，nMAXNUM-1 */ 04 DataType *element; 05 ；06 typedef struct SeqList *PSeqList; 2.2.1 顺序存储结构顺序存储结构2o逻辑相邻逻辑相邻=物理相邻物理相邻 只要知道基地址，就可以通过计算得到任一元素地址，故线性表只要知道基地址，就可以通过计算得到任一元素地址，故线性表可实现

7、随机存取，即访问任一元素时间相等。可实现随机存取，即访问任一元素时间相等。1、插入、插入:在第在第i个位置前插入元素个位置前插入元素2.2.2 基于顺序存储基本操作基于顺序存储基本操作算法算法2.3 在第在第i个位置前插入元素个位置前插入元素00 int InsertPre(List L,int i, DataType x)00 int InsertPre(List L,int i, DataType x)01 01 02 int j;02 int j;03 if (iL.n) 03 if (iL.n) / /* * 判断输入的位置判断输入的位置i i是否合法是否合法 * */ /04 04

8、05 printf(“05 printf(“插入位置插入位置i i不合法！不合法！”);”);06 return(0); 06 return(0); / /* * 返回插入失败的标志返回插入失败的标志 * */ /07 07 08 if (L.n=MAXSIZE)08 if (L.n=MAXSIZE)09 09 10 printf(“10 printf(“表已满，无法插入！表已满，无法插入！”)”)11 return(0);11 return(0);12 12 13 for (j=n-1;j=i;j-); 13 for (j=n-1;j=i;j-); / /* * i i位置以及之后所有元素后

9、移一位位置以及之后所有元素后移一位 * */ /14 L.elemj+1=L.elemj;14 L.elemj+1=L.elemj;15 L.elemi=x; 15 L.elemi=x; / /* * 将将x x放入第放入第i i个位置个位置 * */ /16 L.n=L.n+1; 16 L.n=L.n+1; / /* * 顺序表元素个数加顺序表元素个数加1 1 * */ /17 return(1); 17 return(1); / /* * 返回插入成功的标志返回插入成功的标志 * */ /18 18 2.2.2 基于顺序存储基本操作基于顺序存储基本操作22、删除第、删除第i个位置元素个位置

10、元素算法算法2-4 删除第删除第i个元素个元素00 00 intint DeletePos(ListDeletePos(List L,intL,int i) i)01 01 02 02 intint j; j;03 if (iL.n-1) 03 if (iL.n-1) / /* * 判断要删除元素的位置判断要删除元素的位置i i是否合法是否合法 * */ /04 04 05 05 printfprintf(“(“删除位置删除位置i i不合法！不合法！”););06 return(0); 06 return(0); / /* * 返回删除失败的标志返回删除失败的标志 * */ /07 07 08

11、 for (j=i+1;j=n-1;j+);08 for (j=i+1;j=n-1;j+);/ /* * i+1 i+1位置以及之后所有元素前移一位位置以及之后所有元素前移一位 * */ /09 L.elemj-1=09 L.elemj-1=L.elemjL.elemj;10 10 L.nL.n=L.n-1; =L.n-1; / /* * 顺序表元素个数减顺序表元素个数减1 1 * */ /11 return(1); 11 return(1); / /* * 返回删除成功的标志返回删除成功的标志 * */ /12 12 00 00 intint search(List L, search(Li

12、st L, DataTypeDataType x) x)01 01 02 02 intint i i; ;03 03 i i=0;=0;04 while (04 while (i i L.nL.n)&()&(L.elemL.elem i i!=x) !=x) / /* * 当位置当位置i i的元素不等于的元素不等于x x时，继续向下比对时，继续向下比对 * */ /05 05 i i=i+1;=i+1;06 if (06 if (i i=L.nL.n) ) / /* * 判断比对位置是否超出地址范围判断比对位置是否超出地址范围 * */ /07 return(-1); 07 r

13、eturn(-1); / /* * 返回查找不成功的标志返回查找不成功的标志 * */ /08 else 08 else 09 return(09 return(i i); ); / /* * 返回查找到的给定值所在下标返回查找到的给定值所在下标 * */ /10 10 2.2.2 基于顺序存储基本操作基于顺序存储基本操作33、查找给定值、查找给定值例例2-1：有两个顺序表：有两个顺序表LA和和LB，其元素均为非递减有序序列，将它们合并，其元素均为非递减有序序列，将它们合并成一个顺序表成一个顺序表LC，要求，要求LC也是非递减有序序列。如也是非递减有序序列。如LA=（2，4，4，6），），LB

14、=（1，3，3，5），则），则LC=（1，2，3，3，4，4，5）。）。算法分析算法分析 ：T(n)= O(LA.n + LB.n)根据根据LA和和LB已经是非递减有序序列的特征，已经是非递减有序序列的特征，LA和和LB都从头开始都从头开始比较，值小的放入比较，值小的放入LC中。中。当当LA和和LB中还有元素时，比较中还有元素时，比较LA.elemi和和LB.elemj的大的大小，小的放入小，小的放入LC中，同时相应的指示变量后移一位，继续比较，移动，中，同时相应的指示变量后移一位，继续比较，移动，直到直到LA或或LB扫描完毕。然后判断扫描完毕。然后判断LA或或LB中是否有剩余元素，将顺序中是

15、否有剩余元素，将顺序表剩余的元素也放入表剩余的元素也放入LC中。中。算法算法2-6 顺序表的合并顺序表的合并00 List merge(List LA, List LB, List LC)01 02 int i,j,k ;03 i=0 ;j=0 ;k=0 ;04 while(iLA.n)&( jLB.n) /* 当当i和和j都在合理范围内时都在合理范围内时 */05 if(LA.elemi= LB.elemj)06 07 LC.elemk= LA.elemi;08 i+;k+; 09 10 else11 12 LC.elemk= LB.elemj;14 j+;k+; 15 算法算法2-

16、6 顺序表的合并顺序表的合并16 if (iLA.n) /* 如果如果i还在合理范围内，即还有剩余元素还在合理范围内，即还有剩余元素 */17 while(iLA.n) /* 将将LA中的所有剩余元素放入中的所有剩余元素放入LC中中 */18 19 LC.elemk= LA.elemi;20 i+;k+; 21 22 else23 while(jdata=x;05 p-next=NULL;06 return(p);07 1.初始化链表初始化链表（2）链表的初始化）链表的初始化2.3.2单链表基本操作单链表基本操作00 NODE *InitList()01 02 NODE *head;03 he

17、ad=(NODE *) malloc (sizeof(NODE);04 head-next=NULL;05 return(head);06 2.3.2单链表基本操作单链表基本操作22.插入结点插入结点（1）插入结点到表头：）插入结点到表头：o已知一个结点已知一个结点p以及链表以及链表head，执行插入，执行插入p结点到表头的操作结点到表头的操作 。p-next=head-next;head-next=p;插入的结点插入的结点p作为作为head之后的第一个元素，成为了新的表头结点。之后的第一个元素，成为了新的表头结点。2.3.2单链表基本操作单链表基本操作22.插入结点插入结点（2）插入结点到指

18、定结点之后）插入结点到指定结点之后o已知一个结点已知一个结点p以及链表中的某结点以及链表中的某结点q，执行插入，执行插入p结点到结点到q结点之结点之后的操作后的操作 。1 p-next=q-next;2 q-next=p;在这两个语句中，必须先执行第在这两个语句中，必须先执行第1句，否则先将句，否则先将p赋予了赋予了q的指针域，会造成的指针域，会造成q与与q原来的后继断开，找不到其后继结点地址的后果。原来的后继断开，找不到其后继结点地址的后果。2.3.2单链表基本操作单链表基本操作22.插入结点插入结点（3）插入结点到表尾）插入结点到表尾o已知一个结点已知一个结点p以及链表以及链表head，执

19、行插入，执行插入p结点到表尾的操作。结点到表尾的操作。 00 NODE *Searchrear(NODE *head)01 02 NODE *q;03 q=head;04 while (q-next!=NULL)05 q=q-next; 06 2.3.2单链表基本操作单链表基本操作33.建立建立 链表链表（1）头插法建立链表）头插法建立链表00 NODE *CreateFromHead()01 02 NODE *head,*p,*q;03 int i,n,x；04 printf(nInput the length of the line:);05 scanf(%d,&n); /* 键盘

20、读取链表的长度键盘读取链表的长度n */06 head=Initlist(); /* 初始化链表初始化链表head */07 printf(nInput %d datas:,n);08 for (i=0;inext=head-next;13 head-next=p;14 15 2.3.2单链表基本操作单链表基本操作33.建立建立 链表链表（2）尾插法建立链表）尾插法建立链表00 NODE *CreateFromTail()01 02 NODE *head,*p,*q;03 int i,n,x;04 printf(nInput the length of the line:);05 scanf(

21、%d,&n); /* 链表的长度链表的长度n */06 head=q=Initlist(); /* 初始化链表初始化链表head，q代表表尾结点代表表尾结点 */07 printf(nInput %d datas:,n);08 for (i=0;inext=p; /* p连接到表尾连接到表尾q之后之后 */13 q=p; /* p结点作为新的表尾，更新表尾结点作为新的表尾，更新表尾q */14 15 2.3.2单链表基本操作单链表基本操作44.删除结点删除结点（1）删除给定结点的后继结点）删除给定结点的后继结点o已知链表中的某结点已知链表中的某结点p，执行删除，执行删除p的后继的操作的

22、后继的操作 q=p-next； /* 用用q记录要删除的结点记录要删除的结点 */p-next=q-next; /* p的指针域直接跳过的指针域直接跳过q结点结点 */free(q); /* 释放已被删除的结点释放已被删除的结点 */2.3.2单链表基本操作单链表基本操作44.删除结点删除结点（2）删除给定结点）删除给定结点p已知一个结点已知一个结点p以及链表以及链表head，执行删除，执行删除p结点的操作结点的操作00 NODE *delete(NODE *head, NODE *p)01 02 NODE *q;03 q=head;04 while (q-next!=p) /* 找找p的后继

23、的后继q */05 q=q-next; 06 q-next=p-next; /* 删除删除p结点结点 */07 free(p);08 return(head);09 2.3.2单链表基本操作单链表基本操作55.输出单链表输出单链表00 void Display(NODE *head)01 02 NODE *p;03 printf(nThe line are:);04 p=head-next; /* p指向链表的第一个元素指向链表的第一个元素 */05 while(p!=NULL) /* 判断判断p是否已到链表的末尾是否已到链表的末尾 */06 07 printf(%d ,p-data); /*

24、 输出输出p的值的值 */08 p=p-next; /* p指向下一个结点指向下一个结点 */09 10 2.3.2单链表基本操作单链表基本操作66.查找给定值结点查找给定值结点00 NODE *Search(NODE *head,int x)01 02 NODE *p;03 p=head-next;04 while(p!=NULL)&(p-data!=x)05 p=p-next;06 return(p);07 练习：练习：o查找链表中值为查找链表中值为x的元素，返回其地址或空。的元素，返回其地址或空。上机：上机：o键盘输入键盘输入n，然后建立一个长度为，然后建立一个长度为n的单链表，

25、最后输出此单链表；的单链表，最后输出此单链表；o输入数字输入数字k，在单链表中查找，在单链表中查找k并输出查找结果。并输出查找结果。2.3.3 循环链表循环链表o 首尾相连首尾相连2.3.3 循环链表循环链表2p 例例2-2：现有循环单链表：现有循环单链表head，输出链表中的所有元素。，输出链表中的所有元素。算法算法2-13 输出循环单链表输出循环单链表1 void Display(NODE *head)2 NODE *p;3 printf(nThe line are:);4 p=head-next;5 while(p!=head) /* 判断判断p是否已到链表头结点是否已到链表头结点 */

26、6 printf(%d ,p-data);7 p=p-next;8 9 2.3.3 循环链表循环链表3o 例：合并例：合并图图2-152-15（a a） headAheadA和和headBheadB合并前合并前图图2-15（b） headA和和headB合并后合并后 2.3.3 循环链表循环链表4p算法算法2-16带头结点的循环单链表的合并带头结点的循环单链表的合并00 NODE *merge1(NODE *headA, NODE *headB)01 02 NODE *p,*q;03 p=headA-next;04 while(p-next!=headA) p=p-next; /* 找到表找到

27、表headA的表尾的表尾p */05 q=headB-next;06 while(q-next!=headB) q=q-next; /* 找到表找到表headB的表尾的表尾q */07 q-next=headA; /* 修改修改q的指针域指向的指针域指向headA的头结点的头结点 */08 p-next=headB-next; /* 修改修改p的指针域指向的指针域指向headB的表头结点的表头结点 */09 q-next=headA; /* q的指针域指向的指针域指向headA头结点头结点 */10 free(headB); /* 释放释放headB的头结点的头结点 */11 return(h

28、eadA);12 2.3.3 循环链表循环链表5p 算法算法2-17带尾指针的循环单链表的合并带尾指针的循环单链表的合并00 NODE *merge2(NODE *rearA, NODE *rearB)01 02 NODE *p;03 p=rearA-next; /* 找到表找到表rearA的头结点的头结点p */04 rearB-next=p; /* 修改修改rearB的指针域指向的指针域指向rearA的头结点的头结点 */05 rearA-next=rearB-next-next; /* 修改修改rearA的指针域指向的指针域指向rearB的表头结点的表头结点 */06 free(rear

29、B-next); /* 释放释放rearB的头结点的头结点 */07 return(rearB); /* 返回返回rearB的尾指针的尾指针 */08 2.3.4 双向链表双向链表o 引入：单链表中求前趋困难引入：单链表中求前趋困难datanextprior2.3.4 双向链表双向链表21.插入结点到指定结点之前插入结点到指定结点之前o已知双向链表中的某结点已知双向链表中的某结点p以及一个孤立结点以及一个孤立结点s，执行插入，执行插入s结点结点到到p结点之前的操作。结点之前的操作。01 s-next=p; /* s的后继指向的后继指向p */02 s-prior=p-prior; /* s的前

30、驱指向的前驱指向p的前驱的前驱 */03 p-prior-next=s; /* p的前驱的后继指向的前驱的后继指向s */04 p-prior=s; /* p的前驱指向的前驱指向s */ 2.3.4 双向链表双向链表32.删除结点删除结点o 已知双向链表中的某结点已知双向链表中的某结点p，执行删除，执行删除p的操作。的操作。01 p-prior-next=p-next； /* p的前驱的后继指向的前驱的后继指向p的后继的后继 */02 p-next-prior=p-prior; /* p的后继的前驱指向的后继的前驱指向p的前驱的前驱 */03 free(p); /* 释放已被删除的释放已被删除

31、的p结点结点 */2.3.5 静态链表静态链表一个静态链表的例子：一个静态链表的例子： datadata cursorcursor 0 0 3 3 1 1 C C 6 6 2 2 E E - -1 1 3 3 A A 5 5 4 4 5 5 B B 1 1 6 6 D D 2 2 7 7 8 8 9 9 sheadshead 设设StaList为静态链表数组，为静态链表数组，shead为头结点指针。则为头结点指针。则StaListshead.cursor指示指示了链表的第一个结点在数组中的了链表的第一个结点在数组中的位置。位置。2.3.5 静态链表静态链表o静态链表的数据类型可用静态链表的数据

32、类型可用C语言定义如下：语言定义如下：00 struct node01 DataType data; /* Data表示数据可能的类型表示数据可能的类型 */02 int cursor;03 ;04 typedef struct node Stanode; /* 定义静态链表结点类型定义静态链表结点类型 */05 Stanode StaListMaxsize; /* Maxsize表示链表可能达到的最大长度表示链表可能达到的最大长度 */2.3.5 静态链表静态链表1.初始化初始化算法算法2-18 静态链表初始化静态链表初始化00 void initial(Stanode StaListMax

33、size,int spare)01 02 int k;03 StaList 0.cursor=-1; /* 设置已用静态链表的游标域为设置已用静态链表的游标域为-1，即已用静态链表为空，即已用静态链表为空 */04 spare=1; /* 设置备用链表头指针初值设置备用链表头指针初值 */05 for(k=av;kMaxsize-1;k+)06 StaList k.cursor=k+1; /* 将空闲结点链接起来将空闲结点链接起来 */07 spaceMaxsize-1. cursor=-1; /* 标记链尾标记链尾 */08 2.3.5 静态链表静态链表22.插入插入 datadata cu

34、rsorcursor 0 0 3 3 1 1 C C 6 6 2 2 E E - -1 1 3 3 A A 5 5 4 4 7 7 5 5 B B 1 1 6 6 D D 2 2 7 7 8 8 8 8 9 9 9 9 - -1 1 sheadshead s sparepare datadata cursorcursor 0 0 3 3 1 1 C C 4 4 2 2 E E - -1 1 3 3 A A 5 5 4 4 X X 6 6 5 5 B B 1 1 6 6 D D 2 2 7 7 8 8 8 8 9 9 9 9 - -1 1 sheadshead s sparepare 在线性表（

35、在线性表（A，B，C，D，E)的第的第3个个结点结点C之后插入一之后插入一值为值为X的元素的元素2.3.5 静态链表静态链表2算法算法2-19 在静态链表的第在静态链表的第i个元素之后插入元素个元素之后插入元素X00 void InsAfter(Stanode StaListMaxsize,int spare,int i,DataType X)01 02 int j,k,m;03 j=spare ; /* j为从备用链表中取到的可用结点的下标，为从备用链表中取到的可用结点的下标，j即为新结点下标即为新结点下标 */04 spare =StaListspare.cursor; /* 修改备用链表

36、的头指针修改备用链表的头指针 */05 StaListj.data=X; /* 为新结点赋值为新结点赋值 */ 06 k= StaList0.cursor ; /* k为已用静态链表的第一个元素的下标为已用静态链表的第一个元素的下标 */07 for(m=0;mi-1;m+) /* 寻找第寻找第i个元素的位置个元素的位置k */08 k= StaListk.cursor ;09 StaListj.cursor=StaListk.cursor; /* 修改新结点游标域，指向第修改新结点游标域，指向第i个结点的后继个结点的后继 */10 StaListk.cursor=j; /* 修改第修改第i个

37、结点游标域，指向新结点个结点游标域，指向新结点 */11 2.3.5 静态链表静态链表33.删除删除 datadata cursorcursor 0 0 3 3 1 1 C C 6 6 2 2 E E - -1 1 3 3 A A 5 5 4 4 7 7 5 5 B B 1 1 6 6 D D 2 2 7 7 8 8 8 8 9 9 9 9 - -1 1 sheadshead s sparepare 在线性表（在线性表（A，B，C，D，E)中删除中删除第第3个结点个结点C之后之后 datadata cursorcursor 0 0 3 3 1 1 4 4 2 2 E E - -1 1 3 3

38、A A 5 5 4 4 7 7 5 5 B B 6 6 6 6 D D 2 2 7 7 8 8 8 8 9 9 9 9 - -1 1 sheadshead s sparepare 2.3.5 静态链表静态链表3算法算法2-20 删除静态链表的第删除静态链表的第i个元素个元素00 void Delete(Stanode StaListMaxsize,int spare,int i)01 02 int j,k,m;03 k= StaList0.cursor ; /* k为已用静态链表的第一个元素的下标为已用静态链表的第一个元素的下标 */04 for(m=1;mnext;04 head-next=

39、NULL;05 while(p!=NULL) /* 将链表中的结点依次取出，直到将链表中的结点依次取出，直到p指向表尾指向表尾 */06 07 q=p; /* q指向当前要倒置的结点指向当前要倒置的结点 */08 p=p-next; /* p指向下一个要倒置的结点指向下一个要倒置的结点 */09 q-next=head-next;10 head-next=q; /* 把当前结点把当前结点q用头插法插入到链表表头用头插法插入到链表表头 */11 12 return head;13 2.3.6 单链表应用单链表应用22.两个有序链表的合并两个有序链表的合并例例2-6：已知两个单链表已知两个单链表h

40、eadA和和headB，元素均递增有序，编写算，元素均递增有序，编写算法，将法，将headA和和headB合并成一个按元素递增的单链表合并成一个按元素递增的单链表headC，要求用，要求用headA和和headB中的原结点组成，不能重新申请结点。中的原结点组成，不能重新申请结点。算法分析：算法分析：利用利用headA和和headB原本已经递增有序的特点，设定两个原本已经递增有序的特点，设定两个指针指针p和和q分别指向分别指向headA和和headB的表头，进行比较，将当前值较小者的表头，进行比较，将当前值较小者插入到插入到C表表尾，并后移一个结点。如此循环反复，直到表表尾，并后移一个结点。如此

41、循环反复，直到p或或q为空。最后为空。最后判断判断headA或或headB中哪个链表有剩余的结点，插入到中哪个链表有剩余的结点，插入到headC中。中。2.3.6 单链表应用单链表应用2算法算法2-23 两个有序链表的合并两个有序链表的合并00 NODE *mergeSorted(NODE *headA, NODE *headB) 01 02 NODE *headC,*p,*q,*s,* mergedNODE;03 p=headA-next;04 q=headB-next;05 headC=headA;06 s=headC;07 while(p!=NULL)&( q!=NULL)08

42、09 if (p-datadata) /* 将数值小的结点存入将数值小的结点存入mergedNODE中中 */10 11 mergedNODE=p; 12 p=p-next; 13 2.3.6 单链表应用单链表应用2算法算法2-23 两个有序链表的合并两个有序链表的合并14 else 15 16 mergedNODE=q; 17 q=q-next; 18 19 s-next=mergedNODE; /* mergedNODE插入到插入到headC表尾表尾 */20 s=mergedNODE;21 22 if (p != NULL) /* 判断判断headA或或headB中哪个链表有剩余中哪个链

43、表有剩余 */23 s-next=p; 24 else25 s-next=q; 26 return headC; 27 2.3.6 单链表应用单链表应用33.一元多项式的计算一元多项式的计算 例例2-7：编写程序，通过键盘输入两个一元多项式编写程序，通过键盘输入两个一元多项式headA和和headB，能够按照指数升序排列建立并输出多项式，然后，能够按照指数升序排列建立并输出多项式，然后对它们进行相加运算，结果存储到对它们进行相加运算，结果存储到headA中并将结果输出。中并将结果输出。如输入的一元多项式分别是如输入的一元多项式分别是x1=10-8x+6x2+3x5和和x2=17+8x+3x2+

44、5x5+4x6，则它们相加的结果为，则它们相加的结果为x1=x1+x2=27+9x2+8x5+4x6。2.3.6 单链表应用单链表应用33.一元多项式的计算一元多项式的计算 算法分析：算法分析： 一元多项式的项数不确定，并且指数虽然是升序排列，一元多项式的项数不确定，并且指数虽然是升序排列，但不一定相连；而且两个多项式经过相加后，但不一定相连；而且两个多项式经过相加后，headA每一项都可能会每一项都可能会变化，常需要进行插入、删除操作，从效率上考虑，宜采用链表存储变化，常需要进行插入、删除操作，从效率上考虑，宜采用链表存储结构。结构。 一元多项式每一项的格式统一，都由系数、底数、指数构成，并

45、一元多项式每一项的格式统一，都由系数、底数、指数构成，并且底数都为且底数都为x。多项式的结构定义可用结构体，结构体包含。多项式的结构定义可用结构体，结构体包含2项内容，项内容，即系数和指数，底数默认即系数和指数，底数默认x。结点的定义如下：。结点的定义如下：struct node int coef; /* 系数域系数域 */ int expn; /* 指数域指数域 */ struct node *next; /* 指向下一个多项式结点指向下一个多项式结点 */;2.3.6 单链表应用单链表应用3算法算法2-24 一元多项式相加一元多项式相加00 #include01 #include02 st

46、ruct node03 04 int coef; /* 系数域系数域 */05 int expn; /* 指数域指数域 */06 struct node *next; /* 指向下一个多项式结点指向下一个多项式结点 */07 ;08 typedef struct node Polyn; /* Polyn为结点类型为结点类型 */2.3.6 单链表应用单链表应用3算法算法2-24 一元多项式相加一元多项式相加09 Polyn *CreatePolyn() /* 建立一元多项式建立一元多项式 */10 11 int i=1,c,e;12 Polyn *head,*p,*q;13 head=q=(P

47、olyn *)malloc(sizeof(Polyn); 14 q-expn= -1;15 q-next=NULL;16 printf(ninput 1s coep & expn:);17 scanf(%d,%d,&c,&e);18 while(c!=0)|(e!=0) /* 输入输入“系数系数指数指数”对对 */19 20 if (c=0) /* 判断输入的系数不能为判断输入的系数不能为0，否则输入出错，否则输入出错 */21 printf(Input error!n);2.3.6 单链表应用单链表应用3算法算法2-24 一元多项式相加一元多项式相加22 else23

48、 if (eexpn) /* 判断当前输入的指数要比上一个指数大判断当前输入的指数要比上一个指数大 */24 printf(Input error!n);25 else26 p=(Polyn *)malloc(sizeof(Polyn); /*建立新结点以接收数据建立新结点以接收数据*/27 p-coef=c; 28 p-expn=e; 29 p-next=NULL;30 q-next=p; /* p插入到链表表尾插入到链表表尾 */31 q=p; /* q指向新的表尾指向新的表尾 */32 i=i+1;33 34 printf(ninput %ds coep & expn:,i);3

49、5 scanf(%d,%d,&c,&e);36 37 return head; 2.3.6 单链表应用单链表应用3算法算法2-24 一元多项式相加一元多项式相加39 Polyn *AddPolyn(Polyn *ha,Polyn *hb) /* 一元多项式相加一元多项式相加 */40 41 int i,c,e;42 Polyn *p0,*p,*q,*s;43 p0=ha;p=ha-next; /* p指向指向ha的表头，的表头，p0为为p的前驱的前驱 */44 q=hb-next; /* q指向指向hb的表头的表头 */45 while(p!=NULL)&(q!=NULL)46 47 if(p-expnexpn) /* 如如p的指数小于的指数小于q的指数，的指数，p与与p0均后移均后移 */48 49 p0=p; 50 p=p-next;51 52 else2.3.6 单链表应用单链表应用3算法算法2-24 一元多项式相加一元多项式相加5