数据结构线性表.ppt

合并了值为-7，-2的结点后示意图如图2-5所示。图2-5合并了值为-7，-2的结点后的状态-249……15?LbpcpbLc-7312……23?Lapa算法说明算法中pa，pb分别是待考察的两个链表的当前结点，pc是合并过程中合并的链表的最后一个结点。第49页,共74页，星期六，2024年，5月算法描述LNode*Merge_LinkList(LNode*La，LNode*Lb)/*合并以La,Lb为头结点的两个有序单链表*/{LNode*Lc,*pa,*pb,*pc,*ptr;Lc=La;pc=La;pa=La-next;pb=Lb-next;while(pa!=NULL pb!=NULL){if(pa-datapb-data){pc-next=pa;pc=pa;pa=pa-next;}/*将pa所指的结点合并，pa指向下一个结点*/if(pa-datapb-data){pc-next=pb;pc=pb;pb=pb-next;}/*将pa所指的结点合并，pa指向下一个结点*/第50页,共74页，星期六，2024年，5月if(pa-data==pb-data){pc-next=pa;pc=pa;pa=pa-next;ptr=pb;pb=pb-next;free(ptr);}/*将pa所指的结点合并，pb所指结点删除*/}if(pa!=NULL)pc-next=pa;elsepc-next=pb;/*将剩余的结点链上*/free(Lb);return(Lc);}算法分析若La，Lb两个链表的长度分别是m，n，则链表合并的时间复杂度为O(m+n)。第51页,共74页，星期六，2024年，5月6静态链表也可用一维数组来描述线性表，类型说明如下:#defineMAXSIZE1000//链表最大长度Typedefstruct{ElemTypedata;//数据项intcur;//游标项}component,SLinkList[MAXSIZE];数组的一个分量表示一个结点，同时用指示器cur代替指针表示结点在链表中的位置。数组的零分量可看成是头结点。与顺序表相比，仍需预先分配空间，但是可以只修改指示器cur，而无需移动数据元素。第52页,共74页，星期六，2024年，5月2.3.2循环链表循环链表(CircularLinkedList)：是一种头尾相接的链表。其特点是最后一个结点的指针域指向链表的头结点，整个链表的指针域链接成一个环。从循环链表的任意一个结点出发都可以找到链表中的其它结点，使得表处理更加方便灵活。图2-6是带头结点的单循环链表的示意图。空表图2-6单循环链表示意图非空表a1a2……anheadhead第53页,共74页，星期六，2024年，5月循环链表的操作对于单循环链表，除链表的合并外，其它的操作和单线性链表基本上一致，仅仅需要在单线性链表操作算法基础上作以下简单修改：⑴判断是否是空链表：head-next==head;⑵判断是否是表尾结点：p-next==head;第54页,共74页，星期六，2024年，5月2.3.3双向链表双向链表(DoubleLinkedList):指的是构成链表的每个结点中设立两个指针域：一个指向其直接前趋的指针域prior，一个指向其直接后继的指针域next。这样形成的链表中有两个方向不同的链，故称为双向链表。和单链表类似，双向链表一般增加头指针也能使双链表上的某些运算变得方便。将头结点和尾结点链接起来也能构成循环链表，并称之为双向循环链表。双向链表是为了克服单链表的单向性的缺陷而引入的。第55页,共74页