带头双向循环链表

目录

一、结构定义

二、结点创建

三、头结点初始化

四、链表打印 

五、尾插

六、头插

七、尾删

八、头删

九、查找（返回结点）

十、任意位置插入

十一、任意位置删除

十二、利用LTInsert写尾插函数

十三、利用LTInsert写头插函数

十四、利用LTErase写尾删函数

十五、利用LTErase写头删函数

十六、销毁链表 

十七、测试代码

---

一、结构定义

//带头双向循环链表的结构定义
typedef int LTDataType;
 
typedef struct ListNode {
	LTDataType val;
	struct LTNode* next;
	struct LTNode* prev;
}LTNode;

二、结点创建

//带头双向循环链表结点创建
LTNode* CreateLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malLoc fail:");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	newnode->prev = NULL;
 
	return newnode;
}

三、头结点初始化

//带头双向循环链表的初始化
LTNode* LTInit(LTNode* phead)
{
	phead = CreateLTNode(-1);
	phead->next = phead;
	phead->prev = phead;
 
	return phead;
}

四、链表打印 

//带头双向循环链表的打印
void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<=>", cur->val);
		cur = cur->next;
	}
	printf("\n");
}

五、尾插

//带头双向循环链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = CreateLTNode(x);
 
	LTNode* tail = phead->prev;//尾指针
	//尾插
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
 
}

六、头插

//带头双向循环链表的头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = CreateLTNode(x);
	LTNode* first = phead->next;
	
	newnode->next = first;
	first->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;
}

七、尾删

//带头双向循环链表的尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//空链表不能删
	LTNode* tail1 = phead->prev;//尾1结点
	LTNode* tail2 = tail1->prev;//尾2结点
 
	tail2->next = phead;
	phead->prev = tail2;
	free(tail1);
	tail1 = NULL;
}

八、头删

//带头双向循环链表的头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//空链表不能删
 
	LTNode* first = phead->next;
	LTNode* second = first->next;
	free(first);
	first = NULL;
	phead->next = second;
	second->prev = phead;
 
}

九、查找（返回结点）

//带头双向循环链表的查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->val == x)
			return cur;
		else
			cur = cur->next;
	}
	return NULL;
}

十、任意位置插入

如果插入位置是哨兵位，那么相当于尾插

如果插入位置是哨兵位的后一结点，那么相当于头插

//带头双向循环链表的任意位置插入
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);//插入位置必须有效
	
	LTNode* newnode = CreateLTNode(x);
	LTNode* posPrev = pos->prev;
 
	newnode->next = pos;
	pos->prev = newnode;
	posPrev->next = newnode;
	newnode->prev = posPrev;
}

十一、任意位置删除

如果删除位置是哨兵位的后一结点，那么相当于头删

如果删除位置是哨兵位的前一结点，那么相当于尾删

//带头双向循环链表的任意位置删除
void LTErase(LTNode* pos)
{
	assert(pos);
 
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
 
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}

十二、利用LTInsert写尾插函数

//利用LTInsert写尾插函数
void LTPushBackInsert(LTNode* phead, LTDataType x)
{
	assert(phead);
 
	LTInsert(phead, x);
}

十三、利用LTInsert写头插函数

//利用LTInsert写头插函数
void LTPushFrontInsert(LTNode* phead, LTDataType x)
{
	assert(phead);
 
	LTInsert(phead->next, x);
}

十四、利用LTErase写尾删函数

//利用LTErase写尾删函数
void LTPopBackErase(LTNode* phead)
{
	assert(phead->next != phead);//链表为空不能删除
 
	LTErase(phead->prev);
}

十五、利用LTErase写头删函数

//利用LTErase写头删函数
void LTPopFrontErase(LTNode* phead)
{
	assert(phead->next != phead);
 
	LTErase(phead->next);
}

十六、销毁链表 

//销毁带头双向循环链表
void LTDestroy(LTNode* phead)
{
	assert(phead);
 
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* tmp = cur;
		cur = cur->next;
		free(tmp);
	}
	free(phead);
}

十七、测试代码

void test01()
{
    //初始化哨兵位
    LTNode* plist = NULL;
    plist = LTInit(plist);
    //LTNode* plist = LTInit(plist);
 
    //尾插
    LTPushBack(plist, 1);
    LTPushBack(plist, 2);
    LTPushBack(plist, 3);
    LTPushBack(plist, 4);
    LTPushBack(plist, 5);
    LTPushBack(plist, 6);
    //头插
    LTPushFront(plist, 1);
    LTPushFront(plist, 2);
    LTPushFront(plist, 3);
    LTPushFront(plist, 4);
    LTPushFront(plist, 5);
    LTPushFront(plist, 6);
    //打印
    LTPrint(plist);
    //尾删
    LTPopBack(plist);
    LTPopBack(plist);
    LTPopBack(plist);
    //打印
    LTPrint(plist);
    //头删
    LTPopFront(plist);
    LTPopFront(plist);
    LTPopFront(plist);
    //打印
    LTPrint(plist);
    //查找值为2的结点并在该位置插入值为10的结点
    LTNode* pos1 = LTFind(plist, 2);
    LTInsert(pos1, 10);
    //打印
    LTPrint(plist);
    //查找值为3的结点并删除该结点
    LTNode* pos2 = LTFind(plist, 3);
    LTErase(pos2);
    //打印
    LTPrint(plist);
    //尾插
    LTPushBackInsert(plist, 1);
    LTPushBackInsert(plist, 2);
    LTPushBackInsert(plist, 3);
    LTPushBackInsert(plist, 4);
    //打印
    LTPrint(plist);
    //头插
    LTPushFrontInsert(plist, 1);
    LTPushFrontInsert(plist, 2);
    LTPushFrontInsert(plist, 3);
    LTPushFrontInsert(plist, 4);
    //打印
    LTPrint(plist);
    //尾删
    LTPopBackErase(plist);
    LTPopBackErase(plist);
    LTPopBackErase(plist);
    //打印
    LTPrint(plist);
    //头删
    LTPopFrontErase(plist);
    LTPopFrontErase(plist);
    LTPopFrontErase(plist);
    //打印
    LTPrint(plist);
    //销毁链表
    //LTDestroy(plist);
    //plist=NULL;
 
}
 
int main()
{
    test01();
 
    return 0;
}