《数据结构一元多项式与线性表习题.pptx》由会员分享，可在线阅读，更多相关《数据结构一元多项式与线性表习题.pptx（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2.3.3 双向链表 每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接确定一个结点的前驱和后继结点。从而可提高效率。Pp=(p-prior)-next=(p-next)-prior第1页/共42页线性表的双向链表存储结构typedef struct DuNode ElemType data;struct DuNode*prior，*next;DuNode,*DulinkList;第2页/共42页双向链表的操作特点：1、“查询”和单链表相同2、“插入”和“删除”时需要同时修改两个方向上的指针。第3页/共42页aiai-1es-next=p-next;p-next=s;s-next-pr
2、ior=s;s-prior=p;psai-1双向链表的插入（后插）第4页/共42页ai-1aiepsai-1ai双向链表的插入（前插）sprior=pprior;snext=p;ppriornext=s;pprior=s;第5页/共42页ai-1双向链表的删除aiai+1p-next=p-next-next;p-next-prior=p;pai-1第6页/共42页双向循环链表空表非空表a1a2an第7页/共42页用链表实现线性表的操作时，存在的问用链表实现线性表的操作时，存在的问题：题：1 1表长是一个隐含的值；表长是一个隐含的值；2 2插入元素时，可能需遍历整个链表；插入元素时，可能需遍历整
3、个链表；3 3在链表中，元素的在链表中，元素的“位序位序”概念淡化，概念淡化，结点的结点的“位置位置”概念加强。概念加强。第8页/共42页改进链表结构：改进链表结构：Typedef struct LNode Typedef struct LNode /结点类型结点类型 ElemType data;ElemType data;struct LNode *next;struct LNode *next;*Link,*Position;*Link,*Position;Typedef struct LNode Typedef struct LNode /链表类型链表类型 Link head,tail;
4、Link head,tail;int len;int len;LinkList;LinkList;基本操作基本操作第9页/共42页第2章 线性表2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加 第10页/共42页计算机中，可以用一个关于系数的线性表来表示：P=（p0,p1,，pn）2.4 一元多项式的表示及相加但是对于形如S(x)=1+3x100002x20000的多项式，上述表示方法是否合适？第11页/共42页 一般情况下的一元稀疏多项式可写成 Pn(x)=p
5、1xe1+p2xe2+pmxem 其中：pi 是指数为 ei 的项的非零系数，0 e1 e2 em=n可以下列线性表表示：（p1,e1）,(p2,e2),(pm,em)）将单链表的每个结点对应着一元多项式中的一个非零项，它由三个域组成，分别表示非零项的系数、指数和指向下一个结点的指针。第12页/共42页 P99(x)=7x3-2x12-8x99例:可用线性表(7,3),(-2,12),(-8,99)表示：第13页/共42页一元多项式的表示：typedef struct /项的表示 float coef;/系数 int expn;/指数 term,ElemType;typedef Ordered
6、LinkList polynomial;/用带表头结点的有序链表表示多项式数据元素类型定义为:第14页/共42页抽象数据类型一元多项式的定义抽象数据类型一元多项式的定义ADT Polynomial 数据对象：D ai|aiTermSet,i=1,2,.,m,m0 TermSet 中的每个元素包含一个表示 系数的实数和表示指数的整数 数据关系：R1|ai-1,aiD,i=2,.,n 且ai-1中的指数值ai中的指数值 第15页/共42页 基本操作基本操作：CreatPolyn(&P,m)CreatPolyn(&P,m)DestroyPolyn(&P)DestroyPolyn(&P)PrintPo
7、lyn(P)PrintPolyn(P)PolynLength(P)PolynLength(P)AddPolyn(&Pa,&Pb)AddPolyn(&Pa,&Pb)SubtractPolyn(&Pa,&Pb)SubtractPolyn(&Pa,&Pb)MultiplyPolyn(&Pa,&Pb)MultiplyPolyn(&Pa,&Pb)ADT Polynomial ADT Polynomial初始条件：一元多项式 Pa 和 Pb 已存在。操作结果：Pa=PaPb，并销毁一元多项式 Pb。第16页/共42页 在实际的应用程序中取用顺序结构存储一元在实际的应用程序中取用顺序结构存储一元多项式，还是
8、链式存储结构存储多项式，要视多项式，还是链式存储结构存储多项式，要视多项式作何种运算而定，若只对多项式进行多项式作何种运算而定，若只对多项式进行“求值求值”等不改变多项式的系数和指数的运算，等不改变多项式的系数和指数的运算，则采用类似于顺序表的顺序存储结构即可，否则采用类似于顺序表的顺序存储结构即可，否则应采用链式存储表示。则应采用链式存储表示。第17页/共42页例：设两个一元多项式为例：设两个一元多项式为:A(X)=4+6X A(X)=4+6X4 4+5X+5X8 8+4X+4X1212 B(X)=2X B(X)=2X3 3-5X-5X8 8+3X+3X12 12+7X+7X1515 求此两
9、一元多项式之和求此两一元多项式之和:C(x)=A(x)+B(x):C(x)=A(x)+B(x)第18页/共42页AddPolyn(&Pa,&Pb)40 6 58 4 12 headA23-58 312headB 7 15 712 7154064headC2 3121547764)(xxxxC+=32x+4第19页/共42页设p,q分别指向A,B中某一结点，p,q初值是第一结点比较p-exp与q-expp-expexp:p结点是和多项式中的一项p后移,q不动p-expq-exp:q结点是和多项式中的一项将q插在p之前,q后移,p不动p-exp=q-exp:系数相加0：从A表中删去p,释放p,q，
10、p,q后移0：修改p系数域,释放q，p,q后移直到p或q为NULL若q=NULL，结束若p=NULL，将B中剩余部分连到A上运算规则第20页/共42页VoidAddPolyn(polynomial&pa,polynomial&pb)ha=GetHead(pa);hb=GetHead(pb);/ha和hb分别指向Pa和Pb的头结点qa=NextPos(pa,ha);qb=NextPos(pb,hb);/qa和qb分别指向Pa和Pb中当前结点haqaqb40 6 458 4 12 23-58 3127 15 0-1 hb0-1 while(qa&qb)/Pa和Pb均非空a=GetCurElem(q
11、a);b=GetCurElem(qb);/a和b为两表中当前比较元素switch(*cmp(a,b)case-1;/pa当前的指数小于pb当前的指数ha=qa;qa=NextPos(pa,qa);break;case1;/pa当前的指数大于pb当前的指数DelFirst(hb,qb);InsFirst(ha,qb);qb=NextPos(pb,hb);ha=NextPos(pa,ha);break;case0;sum=a.coef+b.coef;if(sum!=0)/修改pa当前结点系数SetCurElem(qa,sum);ha=qa;DelFirst(ha,qa);FreeNode(qa);
12、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+第21页/共42页两个一元多项式相加的算法VoidAddPolyn(polynomial&pa,polynomial&pb)ha=GetHead(pa);hb=GetHead(pb);/ha和hb分别指向Pa和Pb的头结点qa=NextPos(pa,ha);q
13、b=NextPos(pb,hb);/qa和qb分别指向Pa和Pb中当前结点while(qa&qb)/Pa和Pb均非空a=GetCurElem(qa);b=GetCurElem(qb);/a和b为两表中当前比较元素switch(*cmp(a,b)case-1;/pa当前的指数小于pb当前的指数ha=qa;qa=NextPos(pa,qa);break;case1;/pa当前的指数大于pb当前的指数DelFirst(hb,qb);InsFirst(ha,qb);qb=NextPos(pb,hb);ha=NextPos(pa,ha);break;intcmp(terma，termb)；/依a的指数值
14、)b的指数值，分别返回-1,0和1；第22页/共42页两个一元多项式相加的算法case0;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(pa,ha);break;/switch/whileif(!ListEmpty(pb)Append(pa,qb);/链接pb剩余结点FreeNode(hb);/释放pb头结点/Add
15、Polyn第23页/共42页本章小结1.了解线性表的逻辑结构特性是数据元素之间 存在着线性关系，在计算机中表示这种关系 的两类不同的存储结构是顺序存储结构和链 式存储结构。用前者表示的线性表简称为顺 序表，用后者表示的线性表简称为链表。2.熟练掌握这两类存储结构的描述方法，以及 线性表的各种基本操作的实现。3.能够从时间和空间复杂度的角度综合比较线 性表两种存储结构的不同特点及其适用场合第24页/共42页一、基础知识题1.在一个单链表HL中，若要向表头插入一个由 指针P指向的结点，则执行（）。A）HL=p；p-next=HL；B）p-next=HL；HL=p；C）p-next=HL；p=HL；
16、D）p-next=HL-next；HL-next=p；习题与练习第25页/共42页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；D）p-next=q-next；q-next=p；第26页/共42页3.指出以下算法中的错误和低效（费时）之处，并 将其修改正确。Status DeleteK(&L,i,k)/从顺序存储结构的线性表L中删除第i个元素起的K个元素 if(i 1|k L.len)return ERROR;for
17、(count=1;count=i+1;j-)L.elemj-1=L.elemj;L.len-;return OK;/DeleteK1.不合法条件错误。2.第二个for语句中，元素前移的次序错误。2.低效之处是每次删除一个元素的策略。第27页/共42页Status DeleteK(&L,i,k)/从顺序存储结构的线性表L中删除第i个元素起的k个元素 if(i1|kL.len+1|iL.len)return ERROR;for(j=i+k;jdata=P-next-data;28775PRHH28375PR第31页/共42页(2)T=P;while(T!=NULL)T-data=(T-data)*
18、2;T=T-next;H2P1014616H28375P第32页/共42页(3)T=P;while(T-next!=NULL)T-data=(T-data)*2;T=T-next;H28375PH2P101468第33页/共42页(4)P=(LNode*)malloc(sizeof(LNode);P-data=10;R-next=P;P-next=S;HS28375PR第34页/共42页(4)P=(LNode*)malloc(sizeof(LNode);P-data=10;R-next=P;P-next=S;PHS28375PRHS28375R第35页/共42页P10HS28375RHS283
19、75PR(4)P=(LNode*)malloc(sizeof(LNode);P-data=10;R-next=P;P-next=S;第36页/共42页(4)P=(LNode*)malloc(sizeof(LNode);P-data=10;R-next=P;P-next=S;P10HS28375PRHS28375R第37页/共42页(4)P=(LNode*)malloc(sizeof(LNode);P-data=10;R-next=P;P-next=S;P10HS28375PRHS28375R第38页/共42页(5)T=H;T-next=P-next;free(P);H2837PT5H28375
20、P第39页/共42页(6)S-next=H;HS28375如果S-next=H则S所指向的结点为尾结点.HS28375第40页/共42页二、算法设计题二、算法设计题1.1.有一个有有一个有 n n 个结点的单链表，设计一个函数将第个结点的单链表，设计一个函数将第 i-1 i-1 个结点与第个结点与第 i i 个结点互换，但指针不变。个结点互换，但指针不变。2.2.已知一个递增有序的单链表，编写一个函数向该单已知一个递增有序的单链表，编写一个函数向该单链表中插入一个元素为链表中插入一个元素为 x x 的结点，使插入后该链表的结点，使插入后该链表仍然递增有序。仍然递增有序。3.3.有一个单链表有一个单链表 L L（至少有一个结点），其头结点指（至少有一个结点），其头结点指针为针为head head，编写一个函数将，编写一个函数将 L L 逆置，即最后一个逆置，即最后一个结点变成第结点变成第 1 1 个结点，原来倒数第个结点，原来倒数第 2 2 个结点变成个结点变成第第 2 2个结点个结点如此等等。如此等等。4.4.试编写一个在循环双向链表中进行删除操作的算法，试编写一个在循环双向链表中进行删除操作的算法，要求删除的结点是指定结点要求删除的结点是指定结点 p p 的前趋结点。的前趋结点。第41页/共42页谢谢您的观看！第42页/共42页