数据结构精品课件-循环单链表与双向链表.pptVIP

第 2 章 线性表 单链表 单链表上的基本运算 循环链表 双向链表 静态链表 第 2 章 线性表 循环链表(Circular Linked List)： 是一个首尾相接的链表。 特点：将单链表最后一个结点的指针域由NULL改为指向 头结点或线性表中的第一个结点，就得到了单链形式的循 环链表，并称为循环单链表。在循环单链表中，表中所有 结点被链在一个环上。 第 2 章 线性表 循环链表(Circular Linked List) 例2-3 有两个带头结点的循环单链表LA、LB，编写一个算法， 将两个循环单链表合并为一个循环单链表，其头指针为LA。 先找到两个链表的尾，并分别由指针p、q指向它们，然后将 第一个链表的尾与第二个表的第一个结点链接起来，并修改 第二个表的尾q，使它的链域指向第一个表的头结点。 p-next=LB-next; q-next=LA; free(LB); 第 2 章 线性表 循环链表(Circular Linked List) 算法实现1 LinkList merge_1(LinkList LA,LinkList LB) { Node *p, *q; p=LA; q=LB; while (p-next!=LA) p=p-next; while (q-next!=LB) q=q-next; p-next=LB-next; free(LB); q-next=LA; return(LA); } 时间复杂度为 O(n) 第 2 章 线性表 循环链表(Circular Linked List) 例2-3 有两个采用带尾指针的循环链表LA、LB，编写一个算 法，将两个循环单链表合并为一个循环单链表，返回其尾指针。 执行时间可降低为O(1)。 RA-next=RB-next-next; RB-next=p; free(RB-next); 第 2 章 线性表 循环链表(Circular Linked List) 算法实现2 LinkList merge_2(LinkList RA,LinkList RB) { Node *p; p=RA-next; RA-next=RB-next-next; free(RB-next); RB-next=p; return(RB); } 返回 第 2 章 线性表 双向链表(Double Linked List) 在单链表的每个结点里再增加一个指向其前趋的指针域prior。这样形成的链表中就有两条方向不同的链，我们称之为双 ( 向) 链表。 结构定义： typedef struct Dnode { ElemType data； struct DNode *prior，*next； }DNode, *DoubleList； 定义： 第 2 章 线性表 双向链表(Double Linked List) 示意图： 第 2 章 线性表 双向链表(Double Linked List) 前插操作： s p × ① ① p-prior-next=s; ② ② s-prior=p-prior; 顺序可以 颠倒吗？ × ③ ③ p-prior=s; ④ ④ s-next=p; 顺序可以 颠倒吗？ 顺序可以 颠倒吗？ 第 2 章 线性表 2.3线性表的链式存储 双向链表(Double Linked List)前插操作 算法实现： int DlinkIns(DoubleList L,int i,ElemType e) { DNode *s,*p; p=search ( L , i); if(p==NULL) return ERROR; s=(DNode*)malloc(sizeof(DNode)); if (!s) return ERROR; s-data=e; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; return OK; } 第 2 章 线性表 双向链表(Double Linked List) 删除操作： p × ① p-prior-next=p-next; ① × ② ② p-next-prior=p-prior; free(p); 第 2 章