数据结构笔记4-线性表-循环双向链表

参考网课数据结构-青岛大学-王卓-第四周

参考书籍《数据结构C语言版第二版》 中国工信出版集团 人民邮电出版社出版 严蔚敏 编著

---

循环链表

循环链表的基本特征

特点：表中最后一个节点的指针指向头节点。

优点：从表中任意节点出发都能找到表中其他节点。

遍历循环链表的终止条件：判断p是否等于头指针。

Note

使用头指针寻找单链表中的第$1$个元素：$O(1)$；第$n$个元素：$O(n)$。

使用尾指针寻找循环链表的第$1$个元素：$O(1)$；第$n$个元素：$O(1)$。

尾指针在循环链表中更为常用。

循环链表的合并

Hint

下面使用的指针是尾指针

LinkList Connect(LinkList Ta,LinkList Tb){  
	p=Ta->next;  //p存储的是Ta表尾的地址，临时存储 
	Ta->next=Tb->next->next;  //Ta的末节点连到Tb的初始节点（不是头结点）
	delete Tb->next;  //删掉Tb的原本尾指针
	Tb->next=p;  // 给新的表尾指针域赋值为Ta表尾的地址
	return Tb;
}

Note

给指针的赋值：等号右边写地址

双向链表

提高前驱结点的查找速度。

typedef struct DuLNode{
	Elemtype data;
	struct DuLNode *prior,*next;
}DuLNode, *DuLinkList;

双向循环链表

双向循环链表的对称性

p->prior->next=p->next->prior

双向链表的插入

void ListInsert_DuL(DuLinkList &L, int i, ElemType e){
	if(!(p=GetElemP_Dul(L,i))) return ERROR; //调用了之前定义过的
	s=new DuLNode;
	s->prior=p->prior; p->prior->next=s; //这里就要修改四个指针了
	s->next=p; p->prior=s;
	return OK;
}

时间复杂度$O(n)$，花在get步骤上

也可以这样写：

双向链表的删除

void ListDelete_DuL(Dulink &L, int i, ElemType &e){
	if(!(p=GetElemP_Dul(L,i))) return ERROR;
	e=p->data;
	p->prior->next=p->next;
	p->next->prior=p->prior;
	free(p);
	return OK;
}

时间复杂度$O(n)$，花在get步骤上

单链表，循环链表，双向链表的时间效率比较

	查找首元节点	查找尾节点	查找节点*p的前驱节点
带有头结点的单链表L	$O(1)$	$O(n)$	无法通过p->next找到前驱
带有头结点的仅设头指针的循环单链表L	$O(1)$	$O(n)$	通过p->next可找，$O(n)$
带有头结点的仅设尾指针的循环单链表R	$O(1)$	$O(1)$	通过p->next可找，$O(n)$
带有头结点的双向循环链表L	$O(1)$	$O(1)$	$O(1)$

顺序表与链表总体特点的比较

---