《数据结构第04讲一元多项式与线性表习题C》由会员分享，可在线阅读，更多相关《数据结构第04讲一元多项式与线性表习题C（42页珍藏版）》请在金锄头文库上搜索。
1、第2章 线性表2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现2.3.1 线性链表2.3.2 循环链表2.3.3 双向链表 2.4 一元多项式的表示及相加 2.3.3 双向链表每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接确定一个结点的前驱和后继结点。从而可提高效率。P p=(p-prior)-next=(p-next)-prior 线性表的双向链表存储结构typedef struct DuNodeElemType data;struct DuNode *prior，*next;DuNode, * DulinkList;双向链表的操作特点：1
2、、“查询” 和单链表相同2、“插入” 和“删除”时需要同时修改两个方向上的指针。aiai-1es-next = p-next; p-next = s;s-next-prior = s; s-prior = p;psai-1双向链表的插入（后插）ai-1aiepsai-1ai双向链表的插入（前插）sprior=pprior; snext=p; ppriornext=s; pprior=s;ai-1双向链表的删除aiai+1p-next = p-next-next;p-next-prior = p;pai-1双向循环链表空表非空表a1a2an用链表实现线性表的操作时，存在的问题：1表长是一个隐含的
3、值；2插入元素时，可能需遍历整个链表；3在链表中，元素的“位序”概念淡化，结点的“位置”概念加强。改进链表结构：Typedef struct LNode /结点类型ElemType data; struct LNode *next; *Link, *Position; Typedef struct LNode /链表类型Link head, tail; int len; LinkList ;基本操作第2章 线性表2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现2.3.1 线性链表2.3.2 循环链表2.3.3 双向链表 2.4 一元多项式的表示及相加 计
4、算机中，可以用一个关于系数的线性表来表示：P = （p0, p1, ，pn）2.4 一元多项式的表示及相加但是对于形如S(x) = 1 + 3x10000 2x20000的多项式，上述表示方法是否合适？一般情况下的一元稀疏多项式可写成Pn(x) = p1xe1 + p2xe2 + + pmxem其中：pi 是指数为 ei 的项的非零系数，0 e1 |ai-1 ,aiD, i=2,.,n且ai-1中的指数值ai中的指数值 基本操作：CreatPolyn ( hb=GetHead(pb) ; / ha和hb分别指向Pa和Pb的头结点 qa=NextPos(pa, ha); qb=NextPos(p
5、b, hb) ;/qa和qb分别指向Pa和Pb中当前结点 haqaqb4 0 6 4 5 8 4 12 2 3 -5 8 3 12 7 15 0 -1 hb0 -1 while (qa b=GetCurElem(qb); /a和b为两表中当前比较元素 switch(*cmp(a, b) ) case -1; /pa当前的指数小于pb当前的指数ha=qa; qa=NextPos(pa, qa); break;case 1; /pa当前的指数大于pb当前的指数DelFirst(hb,qb);InsFirst(ha,qb); qb=NextPos(pb, hb);ha=NextPos(pa, ha)
6、;break;case 0;sum=a.coef+b.coef;if (sum!=0) /修改pa当前结点系数SetCurElem(qa,sum); ha=qa; DelFirst(ha,qa);FreeNode(qa); DelFirst(hb,qb);FreeNode(qb); qb=NextPos(pb,hb); qa=NextPos(pa,ha); break;else /删除pa当前结点7if (!ListEmpty(pb) Append(pa, qb) ; /链接pb剩余结点FreeNode(hb); /释放pb头结点pa121547764)(xxxxC+=32x+两个一元多项式相
7、加的算法 Void AddPolyn( polynomial hb=GetHead(pb) ; / ha和hb分别指向Pa和Pb的头结点 qa=NextPos(pa, ha); qb=NextPos(pb, hb) ;/qa和qb分别指向Pa和Pb中当前结点 while (qa b=GetCurElem(qb); /a和b为两表中当前比较元素 switch(*cmp(a, b) ) case -1; /pa当前的指数小于pb当前的指数ha=qa; qa=NextPos(pa, qa); break;case 1; /pa当前的指数大于pb当前的指数DelFirst(hb,qb); InsFir
8、st(ha,qb);qb=NextPos(pb, hb); ha=NextPos(pa, ha); break;int cmp (term a，term b)； /依a的指数值)b的指数 值，分别返回-1,0和1； 两个一元多项式相加的算法case 0;sum=a.coef+b.coef;if (sum!=0) /修改pa当前结点系数SetCurElem(qa,sum); ha=qa; else /删除pa当前结点DelFirst(ha,qa); FreeNode(qa); DelFirst(hb,qb); FreeNode(qb); qb=NextPos(pb,hb); qa=NextPos
9、(pa,ha); break; / switch /whileif (!ListEmpty(pb) Append(pa, qb) ; /链接pb剩余结点FreeNode(hb); /释放pb头结点 / AddPolyn本章小结1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合一、基础知识题1. 在一个单链表
10、HL中，若要向表头插入一个由指针P指向的结点，则执行（ ）。A） HL = p ；p - next = HL；B） p - next = HL； HL = p ；C） p - next = HL； p = HL ；D） p - next = HL - next； HL - next = p ；习题与练习2. 在一个单链表HL中，若要在指针q指向的结点的后面插入一个由指针P指向的结点，则执行（ ）。A） q - next = p - next ； p = q；B） p - next = q - next ； q = p；C） q - next = p - next ； p - next = q
11、；D） p - next = q - next ； q - next = p ；3. 指出以下算法中的错误和低效（费时）之处，并将其修改正确。Status DeleteK ( for (count = 1; count = i+1; j- - )L.elemj-1 = L.elemj;L.len - -; return OK; / DeleteK1.不合法条件错误。2.第二个for语句中，元素前移 的次序错误。2.低效之处是每次删除一个元素 的策略。Status DeleteK ( for (j = i+k ; jdata=P-next-data;28775PRHH28375 PR(2) T=
12、P;while(T!=NULL) T-data=(T-data)*2;T=T-next; H2 P1014616H28375 P(3) T=P;while(T-next!=NULL) T-data=(T-data)*2;T=T-next;H28375 PH2 P101468(4) P=(LNode*)malloc(sizeof(LNode);P-data=10;R-next=P;P-next=S;H S28375 PR(4) P=(LNode*)malloc(sizeof(LNode);P-data=10;R-next=P;P-next=S;PH S28375 PRH S28375 RP10H
13、 S28375 RH S28375 PR(4) P=(LNode*)malloc(sizeof(LNode);P-data=10;R-next=P;P-next=S;(4) P=(LNode*)malloc(sizeof(LNode);P-data=10;R-next=P;P-next=S;P10H S28375 PRH S28375 R(4) P=(LNode*)malloc(sizeof(LNode);P-data=10;R-next=P;P-next=S;P10H S28375 PRH S28375 R(5) T=H; T-next=P-next; free(P);H2837PT5H28
14、375 P(6) S-next=H;HS28375如果 S-next= =H 则S所指向的结点为尾结点.H S28375二、算法设计题1.有一个有 n 个结点的单链表，设计一个函数将第 i-1 个结点与第 i 个结点互换，但指针不变。2.已知一个递增有序的单链表，编写一个函数向该单链表 中插入一个元素为 x 的结点，使插入后该链表仍然递 增有序。3.有一个单链表 L（至少有一个结点），其头结点指针为 head ，编写一个函数将 L 逆置，即最后一个结点变成 第 1 个结点，原来倒数第 2 个结点变成第 2个结点 如此等等。4.试编写一个在循环双向链表中进行删除操作的算法，要 求删除的结点是指定结点 p 的前趋结点。
