数据结构(带头结点的双向循环链表的相关操作)

在前面的文章我也介绍了链表的结构以及类别，在这里就不提，咱们直接开始

一、结构定义以及初始化

//结构定义
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;
}