資料結構-7.循環連結清單

一.循環單連結清單：

1. 定義循環單連結清單

和普通單連結清單一樣：

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;
           

1. 初始化循環單連結清單：

bool InitList(LinkList &L){
	L=(LNode*)malloc(sizeof(LNode));   //配置設定一個單連結清單
	if(L==NULL);					   
		return false;
	L->next=L;						   //頭結點指向自己
	return true;
}
           

1. 判斷循環單連結清單是否為空：

bool Empty(LinkList L){
	return (L->next==L);
}
           

1. 判斷指定結點是否為尾結點：

bool IsTail(LinkList L,LNode *p){
	return (p->next==L);
}
           

二.循環雙連結清單：

1. 循環雙連結清單的定義：

typedef struct DNode{
	Elemtype data;
	struct DNode *next,*prior;
}DNode,*DLinkList;
           

1. 循環雙連結清單的初始化：

bool InitDLinkList(DLinkList &L){
	L=(DNode*)malloc(sizeof(DNode));
	if(L==NULL)
		return false;
	L->next=L;
	L->prior=L;
	return true;
}
           

1. 判斷循環雙連結清單是否為空：（與單連結清單相同）

bool Empty(DLinkList L){
	return (L->next==L);  //&&L->prior==L可以省略
}
		
           

1. 指定結點是否為尾結點：（與單連結清單相同 ）

bool IsTail(DNode *p,DLinkList L){
	return (p->next==L);
}
           

1. 循環雙連結清單的插入：

之前雙連結清單的插入雖然也是如此，但是在最後一個結點插入時會出現問題。因為p->next->prior會傳回空指針錯誤。

//p結點後插入s結點
bool InsertNextDNode(DNode *p,DNode *s){
	s->prior=p;
	s->next=p->next;
	p->next->prior=s;
	p->next=s;
	return true;
}
           

1. 循環雙連結清單的删除：

//在p結點後删除s
bool DeletDNode(DNode *p,DNode *s){
	p->next=s->next;
	s->next->prior=p;
	free(s);
	return true;
}
           

以上許多操作少寫了異常判斷，應該加入判斷傳入指針是否為空指針的語句。（作業太多了，偷懶ing。。。）

總結一下，循環連結清單主要是可以友善操作頭結點尾結點（尤其尾結點）

，尾結點的下一個結點是頭結點。