資料結構(帶頭結點的雙向循環連結清單的相關操作)

在前面的文章我也介紹了連結清單的結構以及類别，在這裡就不提，咱們直接開始

一、結構定義以及初始化

//結構定義
typedef int ItemType;
typedef struct TCListNode{
	ItemType Data;
	struct TCListNode *Next;
	struct TCListNode *Prev;
}TCListNode,*TCList;
//初始化
void  TCListInit(TCList *phead){
	assert(phead != NULL);
	(*phead) = (TCListNode *)malloc(sizeof(TCListNode));  //申請一個頭結點
	(*phead)->Next = (*phead)->Prev = (*phead);
}
           

二、插入

//尾插法
void TCListPushBack(TCList *phead, ItemType x){
	assert(phead != NULL);
	TCListNode *s = (TCListNode *)malloc(sizeof(TCListNode));
	s->Data = x;
	s->Next = (*phead)->Prev->Next;
	s->Prev = (*phead)->Prev;
	s->Next->Prev = s;
	s->Prev->Next = s;
}
//頭插法
void TCListPushFront(TCList *phead, ItemType x){
	assert(phead != NULL);
	TCListNode *p = (*phead);
	TCListNode *s = (TCListNode *)malloc(sizeof(TCListNode));
	s->Data = x;
	s->Next = (*phead)->Next;
	s->Prev = (*phead);
	s->Prev->Next = s;
	s->Next->Prev = s;
}
           

三、删除

//頭删法
void TCListPopFront(TCList phead){
	assert(phead != NULL);
	TCListNode *p = phead->Next;
	if (IsEmpty(phead)){
		printf("沒有元素，無法删除!\n");
		return;
	}
	phead->Next = p->Next;
	p->Next->Prev = p->Prev;
	free(p);
}
//尾删法
void TCListPopBack(TCList phead){
	assert(phead != NULL);
	TCListNode *p = phead->Prev;
	if (IsEmpty(phead)){
		printf("沒有元素，無法删除!\n");
		return;
	}
	phead->Prev = p->Prev;
	p->Prev->Next = p->Next;
	free(p);
}
//按值删除元素(删除所有值)
void TCListEraseByVal(TCList * phead, ItemType val){
	assert(phead != NULL);
	TCListNode *p = (*phead)->Prev;
	TCListNode *q = NULL;
	while (p != *phead){
		if (val == p->Data){
			q = p;
			p = p->Prev;
			q->Prev->Next = q->Next;
			q->Next->Prev = q->Prev;
			free(q);
		}
		else{
			p = p->Prev;
		}
	}
}
//清除連結清單元素
void TCListClear(TCList * phead){
	assert(phead != NULL);
	TCListNode *p = (*phead)->Next;
	TCListNode *temp = NULL;
	while ((*phead)->Next != *phead){
		temp = p;
		p = p->Next;
		(*phead)->Next = p;
		p->Prev = (*phead)->Next->Prev;
		free(temp);
	}
}
           

四、判空

//判空
bool IsEmpty(TCListNode *phead){
	assert(phead != NULL);
	return phead->Next == phead;
}
           

五、周遊

//周遊
void TCListShow(TCListNode * phead){
	assert(phead != NULL);
	TCListNode *p = phead->Next;
	while (p != phead){
		printf("%d->", p->Data);
		p = p->Next;
	}
	printf("over.\n");
}
           

六、排序

//排序
void TCListSort(TCList phead){
	assert(phead != NULL);
	TCListNode *p = phead->Next;
	TCListNode *temp = phead->Next;
	if (IsEmpty(phead) || p->Next == phead){
		return;
	}
	TCListNode *q = p->Next;
	p->Next = phead->Prev->Next;
	phead->Prev = q->Prev; //截斷
	while (q != phead){
		p = q;
		q = q->Next;
		while (temp->Data < p->Data&&temp->Next != phead){   //截斷的連結清單與被截斷的結點比較
			temp = temp->Next;
		}
		if (temp->Data < p->Data){       //連結清單走完，未找到比p->data大的數，尾插
			p->Next = temp->Next;
			p->Prev = temp->Next->Prev;
			p->Next->Prev = p;
			p->Prev->Next = p;
		}
		else{                     //中間插入，插在temp前面
			p->Next = temp->Prev->Next;
			p->Prev = temp->Prev;
			p->Next->Prev = p;
			p->Prev->Next = p;
		}
		temp = phead->Next;
	}
}
           

七、逆置

//逆置
void TCListInver(TCList phead){
	assert(phead != NULL);
	TCListNode *p = phead->Next;
	if (IsEmpty(phead) || p->Next == phead){
		return;
	}
	TCListNode *q = p->Next;
	p->Next = phead->Prev->Next;
	phead->Prev = p->Next->Prev; //截斷
	while (q != phead){
		p = q;
		q = q->Next;
		p->Next = phead->Next;
		p->Prev = phead->Next->Prev;
		p->Next->Prev = p;
		p->Prev->Next = p;
	}
}
           

八、求連結清單長度(不包括頭結點)

//長度
size_t TCListLength(TCList phead){
	assert(phead != NULL);
	size_t i = 0;
	TCListNode *p = phead->Next;
	while (p != phead){
		i++;
		p = p->Next;
	}
	return i;
}
           

九、求表頭表尾元素

//求連結清單頭元素
ItemType TCListFront(TCListNode * phead){
	assert(phead != NULL);
	assert(phead->Next != phead);//連結清單不能是空連結清單
	return phead->Next->Data;
}
//求連結清單尾元素
ItemType TCListBack(TCListNode * phead){
	assert(phead != NULL);
	assert(phead->Next!= phead);//連結清單不能是空連結清單
	return phead->Prev->Data;
}
           

十、查找

//查找(按值查找，傳回結點位址)
TCListNode *TCListFind(TCListNode * phead, ItemType key){
	assert(phead != NULL);
	TCListNode *p = phead->Next;
	while (p != phead){
		if (p->Data == key){
			return p;
		}
		p = p->Next;
	}
	return NULL;
}
           

十一、摧毀連結清單

//摧毀
void TCListDestroy(TCList *phead){
	assert(phead);
	TCListNode *p = (*phead)->Next;
	TCListNode *q = NULL;
	while ((*phead)->Next != *phead){
		q = p;
		p = p->Next;
		(*phead)->Next =p;
		p->Prev = *phead;
		free(q);
	}
	free(*phead);
	*phead = NULL;
}