数据结构——线性表(四).pptVIP

知识回顾 链式存储实现的方式？ 线性表的链式存储结构有什么优点和缺点？ 简述单链表中插入结点的实现思路。 单链表的算法示例 例1:依次输入各结点，动态生成一个单链表 单链表的算法示例 例2：将两个有序链表合并为一个有序链表 循环链表 循环链表 仍为单链表，只是修改最后一个结点的指针域的值由NULL变为指向头结点，形成一个环。 特点： 循环链表中，从任一结点出发都可访问到表中所有结点。 双向链表 双向链表 顾名思义，在双向链表的结点中有两个指针域，一个指向直接后继，另一个指向直接前趋。 将头结点和尾结点链接起来也能构成循环链表，称之为双向循环链表。 C语言描述如下： 双向链表 结点结构 双向循环链表 双向链表 对于带头结点的空双向循环链表 双向循环链表结构的对称性可用下式描述： 即结点*p的存储位置既存放在其前趋结点 *(p—prior)的直接后继指针域中 也存放在它的后继结点 *(p—next)的直接前趋指针域中。 双向链表 对于不需要改变表结构的操作类似于单链表，仅需要对一个方向上的指针作操作，算法描述也相同。 对于插入、删除操作呢？ 双向链表 插入操作 实现步骤 先修改指针p所指结点的前驱结点的指针信息，再修改p所指结点的指针信息； 按照两个方向上的单链表修改。 双向链表 插入算法 双向链表 删除操作 只需修改指针p所指结点的前驱结点和后继结点的指针信息释放指针p所指结点 双向链表 删除算法 * * 第五讲 线性表（四） 数据结构 教学内容 单链表的算法示例 循环链表 双向链表 重点、难点 重点 单链表的合并 难点 单链表的合并 单链表的算法示例 单链表的算法示例 循环链表 双向链表 void CreateList_L(LinkLinst L, int n) { L=(LinkList)malloc(sizeof(LNODE)); L-next=NULL; for(i=n;i0;--i){ p =(LinkList)malloc(sizeof(LNODE)); scanf(p-data); p-next=L-next; L-next=p; } }//createList_L void MergeList_L(LinkList La, LinkList Lb, LinkList Lc) { pa=La-next; pb=Lb-next; Lc=pc=La; while(papb) { if(pa-data=pb-data) { pc-next=pa; pc=pa; pa=pa-next; } else { pc-next=pb; pc=pb; pb=pb-next; } } pc-next=pa ? pa : pb; free(Lb); } //MergeList_L 循环链表 单链表的算法示例 循环链表 双向链表 循环条件：p-next != H 双向链表 单链表的算法示例 循环链表 双向链表 typedef struct DuLNode{ ElemType data; struct DuLNode *prior; struct DuLNode *next; }DuLNode, *DuLinkList; data next prior L-next=L-piror=L (p-prior)-next=p=(p-next)-prior 需要两个方向上的指针修改！ e … s … p b a Status ListInsert_DuL(DuLinkList L,int I,Elemtype e) { if(!(p=GetElemP_Dul(L,i))) return ERROR; if(!(s=(DuLinkList)mall