数据结构第04讲一元多项式与线性表习题.ppt
第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 DuNode ElemType data;struct DuNode*prior，*next;DuNode,*DulinkList;,双向链表的操作特点：1、“查询”和单链表相同2、“插入”和“删除”时需要同时修改两个方向上的指针。,s-next=p-next;p-next=s;s-next-prior=s;s-prior=p;,p,s,双向链表的插入（后插）,p,s,双向链表的插入（前插）,sprior=pprior;snext=p;ppriornext=s;pprior=s;,双向链表的删除,p-next=p-next-next;p-next-prior=p;,p,双向循环链表,空表,非空表,a1,a2,an,用链表实现线性表的操作时，存在的问题：,1表长是一个隐含的值；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 一元多项式的表示及相加,计算机中，可以用一个关于系数的线性表来表示：P=（p0,p1,，pn）,2.4 一元多项式的表示及相加,但是对于形如,S(x)=1+3x10000 2x20000,的多项式，上述表示方法是否合适？,一般情况下的一元稀疏多项式可写成 Pn(x)=p1xe1+p2xe2+pmxem 其中：pi 是指数为 ei 的项的非零系数，0 e1 e2 em=n,可以下列线性表表示：（p1,e1）,(p2,e2),(pm,em)）,将单链表的每个结点对应着一元多项式中的一个非零项，它由三个域组成，分别表示非零项的系数、指数和指向下一个结点的指针。,P99(x)=7x3-2x12-8x99,例:,可用线性表(7,3),(-2,12),(-8,99)表示：,一元多项式的表示：,typedef struct/项的表示 float coef;/系数 int expn;/指数 term,ElemType;,typedef OrderedLinkList polynomial;/用带表头结点的有序链表表示多项式,数据元素类型定义为:,抽象数据类型一元多项式的定义,ADT Polynomial 数据对象：D ai|aiTermSet,i=1,2,.,m,m0 TermSet 中的每个元素包含一个表示 系数的实数和表示指数的整数 数据关系：R1|ai-1,aiD,i=2,.,n 且ai-1中的指数值ai中的指数值,基本操作：CreatPolyn(&P,m)DestroyPolyn(&P)PrintPolyn(P)PolynLength(P)AddPolyn(&Pa,&Pb)SubtractPolyn(&Pa,&Pb)MultiplyPolyn(&Pa,&Pb)ADT Polynomial,初始条件：一元多项式 Pa 和 Pb 已存在。操作结果：Pa=PaPb，并销毁一元多项式 Pb。,在实际的应用程序中取用顺序结构存储一元多项式，还是链式存储结构存储多项式，要视多项式作何种运算而定，若只对多项式进行“求值”等不改变多项式的系数和指数的运算，则采用类似于顺序表的顺序存储结构即可，否则应采用链式存储表示。,例：设两个一元多项式为:A(X)=4+6X4+5X8+4X12 B(X)=2X3-5X8+3X12+7X15 求此两一元多项式之和:C(x)=A(x)+B(x),AddPolyn(&Pa,&Pb),4 0,6,5 8,4,12,head,A,2 3,-,5 8,3 12,head,B,7,15,7 12,7 15,4 0,6 4,head,C,2,3,4,设p,q分别指向A,B中某一结点，p,q初值是第一结点,运算规则,Void AddPolyn(polynomial/qa和qb分别指向Pa和Pb中当前结点,4,12,while(qa/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);,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当前结点,7,if(!ListEmpty(pb)Append(pa,qb);/链接pb剩余结点,FreeNode(hb);/释放pb头结点,pa,两个一元多项式相加的算法Void AddPolyn(polynomial,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(pa,ha);break;/switch/while if(!ListEmpty(pb)Append(pa,qb);/链接pb剩余结点 FreeNode(hb);/释放pb头结点/AddPolyn,本章小结1.了解线性表的逻辑结构特性是数据元素之间 存在着线性关系，在计算机中表示这种关系 的两类不同的存储结构是顺序存储结构和链 式存储结构。用前者表示的线性表简称为顺 序表，用后者表示的线性表简称为链表。2.熟练掌握这两类存储结构的描述方法，以及 线性表的各种基本操作的实现。3.能够从时间和空间复杂度的角度综合比较线 性表两种存储结构的不同特点及其适用场合,一、基础知识题,1.在一个单链表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；D）p-next=q-next；q-next=p；,3.指出以下算法中的错误和低效（费时）之处，并 将其修改正确。Status DeleteK(/DeleteK,1.不合法条件错误。2.第二个for语句中，元素前移的次序错误。2.低效之处是每次删除一个元素的策略。,Status DeleteK(/DeleteK,4.比较顺序表与链表的优缺点。在什么情况下用顺序表比链表好？5.为什么在单循环链表中设置尾指针比设置头指针更好？6.已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试写出完成下列功能的语句：(1)在P结点后插入S结点的语句序列是。(2)在P结点前插入S结点的语句序列是。(3)在表首插入S结点的语句序列是。(4)在表尾插入S结点的语句序列是。,7.已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试写出完成下列功能的语句：(1)删除P结点的直接后继结点的语句序列是。(2)删除P结点的直接前驱结点的语句序列是。(3)删除P结的语句序列是。(4)删除首元结点的语句序列是。(5)删除尾元结点的语句序列是。,8.对以下单链表分别执行下列各程序段，画出结果示意图。,(1)R-data=P-next-data;,(2)T=P;while(T!=NULL)T-data=(T-data)*2;T=T-next;,(3)T=P;while(T-next!=NULL)T-data=(T-data)*2;T=T-next;,(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;,P,10,(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;,P,10,(4)P=(LNode*)malloc(sizeof(LNode);P-data=10;R-next=P;P-next=S;,P,10,(5)T=H;T-next=P-next;free(P);,(6)S-next=H;,如果 S-next=H 则S所指向的结点为尾结点.,二、算法设计题1.有一个有 n 个结点的单链表，设计一个函数将第 i-1 个结点与第 i 个结点互换，但指针不变。2.已知一个递增有序的单链表，编写一个函数向该单链表中插入一个元素为 x 的结点，使插入后该链表仍然递增有序。3.有一个单链表 L（至少有一个结点），其头结点指针为head，编写一个函数将 L 逆置，即最后一个结点变成第 1 个结点，原来倒数第 2 个结点变成第 2个结点如此等等。4.试编写一个在循环双向链表中进行删除操作的算法，要求删除的结点是指定结点 p 的前趋结点。,
