数据结构c线性表.pptx

《数据结构c线性表.pptx》由会员分享，可在线阅读，更多相关《数据结构c线性表.pptx（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1时间性能比较 时间性能是指实现基于某种存储结构的基本操作（即算法）的时间复杂度。按位查找：顺序表的时间为(1)，是随机存取；单链表的时间为(n)，是顺序存取。插入和删除：顺序表需移动表长一半的元素，时间为(n)；单链表不需要移动元素，在给出某个合适位置的指针后，插入和删除操作所需的时间仅为(1)。第1页/共71页2时间性能比较 结论：若线性表的操作主要是进行查找，很少做插入和删除，或其操作和元素在表中的位置密切相关时，宜采用顺序表做存储结构。对于频繁进行插入和删除的线性表，宜采用链表做存储结构。第2页/共71页3空间性能比较 空间性能是指某种存储结构所占用的存储空间的大小。定义结点的存储密度

2、：数据域占用的存储量整个结点占用的存储总量存储密度第3页/共71页4空间性能比较 结点的存储密度：顺序表中每个结点的存储密度为1（只存储数据元素），没有浪费空间；单链表的每个结点的存储密度1（包括数据域和指针域。例如单链表的结点的数据均为整数，指针所占空间和整型量相同，则单链表的存储密度为50%。因此若不考虑顺序表中的备用结点空间，则顺序表的存储空间利用率为100%，而单链表的存储空间利用率为50%。第4页/共71页5空间性能比较 整体结构：顺序表需要预分配存储空间，如果预分配得过大，造成浪费，若估计得过小，又将发生上溢；单链表不需要预分配空间，只要有内存空间可以分配，单链表中的元素个数就没有

3、限制。第5页/共71页6空间性能比较 结论：当线性表中元素个数变化较大或者未知时，最好使用单链表实现如果用户事先知道线性表的大致长度，使用顺序表的空间效率会更高第6页/共71页7总之，线性表的顺序实现和链表实现各有其优缺点，不能笼统地说哪种实现更好，只能根据实际问题的具体需要，并对各方面的优缺点加以综合平衡，才能最终选定比较适宜的实现方法。第7页/共71页82.5 线性表的其他存储方法循环链表firsta1ai-1anaip从单链表中某结点p出发如何找到其前驱？将单链表的首尾相接，将终端结点的指针域由空指针改为指向头结点，构成单循环链表，简称循环链表。第8页/共71页9循环链表空表和非空表的处

4、理一致附设头结点first空循环链表firsta1ai-1anai非空循环链表第9页/共71页10firsta1ai-1anai循环链表插入xspxspxsp算法描述：s=new Node;s-data=x;s-next=p-next;p-next=s;第10页/共71页11循环链表的实现插入算法描述伪代码 1.工作指针p初始化；累加器j初始化；2.查找第i-1个结点并使工作指针p指向该结点；3.若查找不成功，说明插入位置不合理，抛出插入位置异常；否则，3.1 生成一个元素值为x的新结点s；3.2 将新结点s插入到结点p之后；第11页/共71页12循环链表插入 template void Li

5、nkList:Insert(int i,T x)p=first;j=0;while(p!=first&jnext;j+;if(p=first)throw 位置;else s=new Node;s-data=x;s-next=p-next;p-next=s;与单链表的插入操作相比，差别是什么？分析边界情况i=1，此算法有问题吗？第12页/共71页13循环链表插入 template void LinkList:Insert(int i,T x)p=first;j=0;if(i=1)插入 else p=p-next;j=1;while(p!=first&jnext;j+;if(p=first)thr

6、ow 位置;else s=new Node;s-data=x;s-next=p;q-next=s;第13页/共71页14循环链表循环条件：p!=NULLp!=firstp-next!=NULLp-next!=first循环链表中没有明显的尾端 如何避免死循环第14页/共71页15循环链表如何查找开始结点和终端结点？firsta1ai-1anai开始结点：first-next，时间为O(1)终端结点：将单链表扫描一遍，时间为O(n)第15页/共71页16循环链表reara1ai-1anai开始结点：rear-next-next O(1)终端结点：rear O(1)带尾指针的循环链表一个存储结构设

7、计得是否合理，取决于基于该存储结构的运算是否方便，时间性能是否提高。第16页/共71页17双链表如何求结点p的直接前驱，时间性能？firsta1ai-1anaip为什么可以快速求得结点p的后继？如何快速求得结点p的前驱？第17页/共71页18双链表双链表：在单链表的每个结点中再设置一个指向其前驱结点的指针域。结点结构：priordatanextdata：数据域，存储数据元素；prior：指针域，存储该结点的前驱结点地址；next：指针域，存储该结点的后继结点地址。第18页/共71页19双链表template struct DulNode T data;DulNode*prior,*next;启

8、示？时空权衡空间换取时间priordatanext定义结点结构：第19页/共71页20a1a2a3first非空的双向链表first-next=NULLfirst-proir=NULLrear=firstrearfirst,rear空的双向链表双链表第20页/共71页21双链表 由于在双向链表中既有前向链又有后向链，寻找任一个结点的直接前驱结点与直接后继结点变得非常方便。设指针p指向双链表中某一结点，则有下式成立：p-prior-next=p=p-next-prior a1a2a3first非空的双向链表rear第21页/共71页22s-prior=p;s-next=p-next;p-next

9、-prior=s;p-next=s;ai-1ai操作接口：void Insert(DulNode*p,T x);pxs注意指针修改的相对顺序双链表的操作插入第22页/共71页23双链表的操作删除(p-prior)-next=p-next;(p-next)-prior=p-prior;操作接口：T Delete(DulNode*p);ai-1aipai结点p的指针是否需要修改？delete p;第23页/共71页24实际应用中，常采用带头结点的双循环链表双链表first 空的双循环链表 非空的双循环链表firstab第24页/共71页25完成在双循环链表结点p之后插入s的操作是A p-next=

10、s;s-priou=p;p-next-priou=s;s-next=p-next;B p-next-priou=s;p-next=s;s-priou=p;s-next=p-next;C s-priou=p;s-next=p-next;p-next=s;p-next-priou=s;D s-priou=p;s-next=p-next;p-next-priou=s;p-next=s;D第25页/共71页26总结 空间性能：与单链表的结点相比，双链表的存储密度更低操作复杂性：与单链表的插入和删除结点相比，操作变得更加复杂，因为要维护prior指针时间性能：由于双链表具有对称性，在某些情况下（例如对结

11、点p的前后结点进行操作）会提高算法的时间性能结论：时空权衡 第26页/共71页27静态链表静态链表：用数组来表示单链表，用数组元素的下标来模拟单链表的指针。data：存储数据元素；next：也称游标，存储该元素的后继在数组的下标。数组元素（结点）的构成：data next数据域指针域第27页/共71页28静态链表例：线性表(张，王，李，赵，吴)的静态链表存储张 2王 3李 4赵 5吴-1012345678 7 8-1 1data nextfirstavailfirst：静态链表头指针，为了方便插入和删除操作，通常静态链表带头结点；avail：空闲链表头指针，空闲链表由于只在表头操作，所以不带头

12、结点；第28页/共71页29静态链表在线性表(张，王，李，赵，吴)中“王”之后插入“孙”张 2王 3李 4赵 5吴-1012345678 7 8-1 1data next张 2王 6李 4赵 5吴-1012345678孙 3 8-1 1data next王之后插入孙第29页/共71页30静态链表在线性表(张，王，李，赵，吴)中删除“赵”张 2王 3李 4赵 5吴-1012345678 7 8-1 1data next张 2王 3李 5赵 5吴-1012345678 7 8-1 1data next删除赵摘链第30页/共71页31静态链表在线性表(张，王，李，赵，吴)中删除“赵”张 2王 3李

13、4赵 5吴-1012345678 7 8-1 1data next张 2王 3李 5 6吴-1012345678 7 8-1 1data next删除赵归还空间第31页/共71页32第32页/共71页33静态链表相对于顺序表而言，静态链表有什么优点？优点：在执行插入和删除操作时，只需修改游标，不需要移动表中的元素，从而改进了在顺序表中插入和删除操作需要移动大量元素的缺点。缺点：没有解决连续存储分配带来的表长难以确定的问题；静态链表还需要维护一个空闲链；静态链表不能随机存取。第33页/共71页34间接寻址间接寻址：是将数组和指针结合起来的一种方法，它将数组中存储数据元素的单元改为存储指向该元素的

14、指针。0 1 2 i-1 n-1 Max-1 空闲 长度 a1 ai an a2插入操作移动的不是元素而是指向元素的指针。当元素占用的空间较多时，比顺序表的插入操作快得多。第34页/共71页35间接寻址相对于顺序表而言，间接寻址的优缺点：优点插入和删除操作移动的不是元素而是指向元素的指针，虽然时间复杂度仍为O(n)，但当每个元素占用的空间较大时，比顺序表的插入和删除操作快得多。缺点指针的开销降低了空间性能没有解决连续存储分配带来的表长难以确定的问题第35页/共71页362.6 应用举例一元多项式的表示和相加它实际上可以由n+1个系数唯一确定。因此，在计算机内，可以用一个线性表P来表示：在数学上

15、，一个一元多项式Pn(x)可按升幂的形式写成：第36页/共71页37一元多项式的表示和相加假设Qm(x)是一个一元多项式，则它也可以用一个线性表Q来表示，即 若 假 设 mn，则 两 个 多 项 式 相 加 的 结 果Rn(x)=Pn(x)+Qm(x)，也可以用线性表R来表示：第37页/共71页38一元多项式的表示和相加 例：S(x)=1+3 x 1000+2 x 2000 非零系数指数线性表:(1,0),(3,1000),(2,2000)系数线性表(1,0,0,3,0,0,2)第38页/共71页39一元多项式的表示和相加例：求两多项式的和多项式 A(x)=7+3 x+9 x 8+5 x 17

16、 B(x)=8 x+22 x 7 9 x 8 C(x)=A(x)+B(x)=7+11x+22 x 7+5 x 17A=(7,0),(3,1),(9,8),(5,17)B=(8,1),(22,7),(-9,8)C=(7,0),(11,1),（22，7），(5,17)选择什么样的存储结构？第39页/共71页40一元多项式的表示和相加若采用单链表存储，则每一个非零项对应单链表中的一个结点，且单链表应按指数递增有序排列。coef:系数域，存放非零项的系数exp:指数域，存放非零项的指数next:指针域，存放指向下一结点的指针 coef exp next一元多项式链表的结点结构：第40页/共71页41一

17、元多项式的表示和相加template struct Node T data;Node*next;struct elem int coef;int exp;struct Node int coef;int exp;Node*next;第41页/共71页42一元多项式的表示和相加1.两个多项式中所有指数相同的项的对应系数相加，若和不为零，则构成“和多项式”中的一项；2.所有指数不相同的项均复抄到“和多项式”中。多项式相加的过程：第42页/共71页43AH=1-3x6+7x12BH=-x4+3x6-9x10+8x14AH.firstBH.firstCH.first1 01 0-1 4-1 4-3 6

18、3 6-9 10-9 107 127 128 148 14一元多项式的表示和相加第43页/共71页44AH.firstBH.firstCH.first1 01 0-1 4-3 63 6-9 107 128 14pappcpb第44页/共71页45AH.first1 0-1 4-3 63 6-9 107 128 14papbpcCH.first1 0第45页/共71页46AH.first1 0-1 4-3 63 6-9 107 128 14papbpcCH.first1 0-1 4第46页/共71页47AH.firstCH.first1 01 0-1 4-1 4-3 63 6-9 107 128

19、 14pappcpb0第47页/共71页48AH.firstCH.first1 01 0-1 4-1 40 6-9 107 128 14pappcpb第48页/共71页49AH.firstCH.first1 01 0-1 4-1 4-9 107 128 14papcpb-9 10第49页/共71页50AH.firstCH.first1 01 0-1 4-1 4-9 107 128 14papc-9 10pb7 12第50页/共71页51AH.firstCH.first1 01 0-1 4-1 4-9 107 127 128 148 14pa=pc-9 10pb第51页/共71页52AH.fir

20、stCH.first1 01 0-1 4-1 4-9 107 127 128 148 14pa=pc-9 10pb第52页/共71页531.设置四个工作指针，pa,pb,pc,p,并对其进行初始化2.当 pa!=NULL 并且pb!=NULL时，重复做以下工作1.if（pa.exppb.exp）,将pb加入到CH中，之后移动pb、pc;3.if(pa.exp=pb.exp),pa、pb的系数相加，删除pb,pb后移1.如果和为0，删除pa,pa后移2.否则，将和写入到pa中，将pa加入到CH中，之后，pa、pc后移；3.如pa!=NULL,将pa链入CH中，否则将pb链入CH中；算法分析第53

21、页/共71页54一元多项式的表示和相加 void Add(LinkList&AH,LinkList BH)pc=AH.first;pa=pc-next;p=BH.first;pb=p-next;delete p;/删除BH链的头结点 算法描述C+描述第54页/共71页55 while(pa!=NULL&pb!=NULL)if(pa-expexp)pc-next=pa;pc=pa;pa=pa-next;else if(pa-exppb-exp)pc-next=pb;pc=pb;pb=pb-next;else a=pa-coef+pb-coef;/系数相加 p=pb;pb=pb-next;dele

22、te p;/删去原pb所指结点算法描述C+描述第55页/共71页56 if(a=0)p=pa;pa=pa-next;delete p;/相加为零,该项不要 else /相加不为零,加入ch链 pa-coef=a;pc-next=pa;pc=pa;pa=pa-next;if(pa)pc-next=pa;ese pc-next=pb;第56页/共71页57 教材中代码：将AH看作是结果表达式的一部分，将BH中的节点依次插入到AH中，完成结果表达式的构造存在的问题未对指向结点前驱的指针进行及时的修改第57页/共71页58AH.firstBH.first1 0-1 4-3 63 6-9 107 128

23、 14pqpre第一种情况：第58页/共71页59AH.firstBH.first1 0-1 4-3 63 6-9 107 128 14pqpre第二种情况第59页/共71页60AH.firstBH.first1 0-1 4-3 63 6-9 107 128 14ppreqqpre此时，一定要修改pre指针，这是教材算法中的错误，没有修改这个指针第60页/共71页61AH.firstBH.first1 0-1 43 6-9 107 128 14pqpreqp0 6第三种情况第61页/共71页62AH.firstBH.first1 0-1 4-9 107 128 14preqpqpre第62页/

24、共71页63AH.firstBH.first1 0-1 4-9 107 128 14pqpre第63页/共71页64一元多项式相加算法1.工作指针pre,qre,p、q初始化(分别指向A、B的头结点和首元节点)；2.while（p存在且q存在）执行下列三种情形之一 2.1 如果p-expexp，则指针p后移，q不移动;2.2 如果p-expq-exp，则 2.2.1 将结点q插入到结点p之前；2.2.2 指针q指向原指结点的下一个结点，P不移动；第64页/共71页65一元多项式相加算法2.3 如果p-exp=q-exp，则 2.3.1 p-coef=p-coef+q-coef；2.3.2 如果

25、p-coef=0，则执行下列操作，否则，指针p后移;2.3.2.1 删除结点p；2.3.2.2 使指针p指向它原指结点的下一个结点；2.3.3 删除结点q；2.3.4 使指针q指向它原指结点的下一个结点；3.如果q不为空，将结点q链接在第一个单链表的后面；第65页/共71页66void Add(LinkList&A,LinkList B)pre=A.first;p=pre-next;/pre是P的前驱qre=B.first;q=qre-next;/qre 是q的前驱while（p&q）if(p-expexp)/第1种情况 pre=p;p=p-next;第66页/共71页67else if(p-

26、expq-exp)/第2种情况，将结点q插入到结点p之前 v=q-next;pre-next=q;q-next=p;q=v;错误如何修改？有不同的方法pre=q;添加在语句块的开始处还可以怎么改：在最后：pre=pre-next第67页/共71页68else /第3种情况 p-coef=p-coef+q-coef;/系数相加 if(p-coef=0)/系数为0，删除结点p和结点q pre-next=p-next;/删除结点p delete p;p=pre-next;else /系数不为0，只删除结点q pre=p;p=p-next;qre-next=q-next /删除结点q delete q

27、;q=qre-next;if(q)pre-next=q;/将结点q链接在第一个单链表的后面delete B.first;/释放第二个单链表的头结点所占的内存第68页/共71页l掌握线性表的定义及其逻辑特征；l理解线性表的抽象数据类型定义；l掌握顺序表的存储结构；l掌握顺序表的插入、删除、查找算法及其时间性能；l掌握单链表的存储结构；l掌握单链表的插入、删除、查找操作及其时间性能；l掌握顺序表和单链表的比较方法和结论；l掌握循环链表和双链表的存储方法；l理解静态链表和间接寻址的存储方法；l理解顺序表类、单链表类与线性表抽象数据类型之间的关系本章教学目标第69页/共71页作业11、将不带头结点的单链表L就地逆置，即要求利用原结点空间将其逆置。2、有两个单链表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个链表LC，要求LC也是非递减有序排列第70页/共71页感谢您的观看。第71页/共71页