数据结构：带头节点的双向循环链表的操作

分为三个部分：test.c,DList.c,DList.h

• test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "DList.h"
#include <stdio.h>
#include <stdlib.h>
void menu()
{
	printf("**1.尾插             2.尾删            **\n");
	printf("**3.头插             4.头删            **\n");
	printf("**5.任意位置插入     6.任意位置删除    **\n");
	printf("**7.打印             8.销毁            **\n");

}
void test()
{
	int input = 0;
	DLDataType data = 0;
	DLNode *PH = NULL;
	DLDataType val = 0;
	DListInit(&PH);
	do
	{
		menu();
		printf("请选择;>");
		scanf("%d", &input);
		switch (input)
		{
		case 1:
			printf("请输入要插入的数:");
			scanf("%d", &data);
			DListPushBack(PH, data);
			break;
		case 2:
			DListPopBack(PH);
			break;
		case 3:
			printf("请输入要插入的数:");
			scanf("%d", &data);
			DListPushFront(PH, data);
			break;
		case 4:
			DListPopFront(PH);
			break;
		case 5:
			printf("请输入要插入哪个数前面:");
			scanf("%d", &val);
			printf("请输入要插入的值:");
			scanf("%d", &data);
			DListInsertFront(DListFind(PH, val), data);
			break;
		case 6:
			printf("请输入要删除的数:");
			scanf("%d", &data);
			DListErase(DListFind(PH, data));
			break;
		case 7:
			DListPrint(PH);
			break;
		case 8:
			DListDestroy(&PH);
			break;
		}
	} while (input);
}
int main()
{
	test();
	system("pause");
	return 0;
}

• DList.h

#pragma once
typedef int DLDataType;
typedef struct DListNode//带头节点双向循环链表
{
	DLDataType _data;
	struct DListNode* _pPre;
	struct DListNode* _pNext;
}DLNode;
void DListInit(DLNode** pHead);//初始化
void DListPushBack(DLNode *pHead,DLDataType data);//尾插
void DListPopBack(DLNode *pHead);//尾删
void DListPushFront(DLNode *pHead, DLDataType data);//头插
void DListPopFront(DLNode *pHead);//头删
DLNode* DListFind(DLNode *pHead,DLDataType data);//查找
void DListInsertFront(DLNode *pos, DLDataType data);//任意位置插入
void DListErase(DLNode *pos);//任意位置删除
void DListPrint(DLNode *pHead);//显示
void DListDestroy(DLNode **pHead);//销毁

• DList.c

#include "DList.h"
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
DLNode* BuyDlistNode(DLDataType data)
{
	DLNode *pNewNode = NULL;
	pNewNode = (DLNode*)malloc(sizeof(DLNode));
	if (pNewNode == NULL)
	{
		assert(0);
		return NULL;
	}
	pNewNode->_data = data;
	pNewNode->_pPre = NULL;
	pNewNode->_pNext = NULL;
	return pNewNode;
}
void DListInit(DLNode** pHead)//初始化
{
	assert(pHead);
	*pHead = BuyDlistNode(0);
	//前驱和后继都指向自己
	(*pHead)->_pPre = *pHead;
	(*pHead)->_pNext = *pHead;
}
void DListPushBack(DLNode *pHead, DLDataType data)//尾插
{
	DLNode *pNewNode = NULL;
	assert(pHead);
	pNewNode = BuyDlistNode(data);
	//先不要破坏链表结构
	pNewNode->_pPre = pHead->_pPre;
	pNewNode->_pNext = pHead;
	//破坏链表结构
	pHead->_pPre->_pNext = pNewNode;
	pHead->_pPre = pNewNode;
}
void DListPopBack(DLNode *pHead)//尾删
{
	assert(pHead);
	if (pHead == pHead->_pNext)//链表为空
	{
		return;
	}
	else
	{
		DLNode *pDelNode = pHead->_pPre;
		pHead->_pPre = pDelNode->_pPre;
		pDelNode->_pPre->_pNext = pHead;
		free(pDelNode);
	}
}
void DListPushFront(DLNode *pHead, DLDataType data)//头插
{
	DLNode *pNewNode = NULL;
	assert(pHead);
	pNewNode = BuyDlistNode(data);
	pNewNode->_pNext = pHead->_pNext;
	pNewNode->_pPre = pHead;
	pHead->_pNext = pNewNode;
	pNewNode->_pNext->_pPre = pNewNode;
}
void DListPopFront(DLNode *pHead)//头删
{
	DLNode *pDelNode = NULL;
	assert(pHead);
	if (pHead == pHead->_pNext)
	{
		return;
	}
	pDelNode = pHead->_pNext;
	pHead->_pNext = pDelNode->_pNext;
	pDelNode->_pNext->_pPre = pHead;
	free(pDelNode);
}
DLNode* DListFind(DLNode *pHead,DLDataType data)//查找
{
	DLNode *pCur = pHead->_pNext;
	while (pCur != pHead)
	{
		if (pCur->_data == data)
		{
			return pCur;
		}
		pCur = pCur->_pNext;
	}
	return NULL;
}
void DListInsertFront(DLNode *pos, DLDataType data)//任意位置向前插入
{
	DLNode *pNewNode = BuyDlistNode(data);
	if (pos == NULL)
		return;
	pNewNode->_pNext = pos;
	pNewNode->_pPre = pos->_pPre;
	pos->_pPre->_pNext = pNewNode;
	pos->_pPre = pNewNode;
}
void DListErase(DLNode *pos)//任意位置删除
{
	if (pos == NULL)
		return;
	pos->_pPre->_pNext = pos->_pNext;
	pos->_pNext->_pPre = pos->_pPre;
	free(pos);
}
void DListPrint(DLNode *pHead)//显示
{
	DLNode *pCur = NULL;
	assert(pHead);
	pCur = pHead->_pNext;
	while (pCur != pHead)
	{
		printf("%d ", pCur->_data);
		pCur = pCur->_pNext;
	}
	printf("\n");
}
void DListClear(DLNode *pHead)//将有效结点清除
{
	DLNode *pCur = NULL;
	assert(pHead);
	pCur = pHead->_pNext;
	while (pCur != pHead)
	{
		pHead->_pNext = pCur->_pNext;
		free(pCur);
		pCur = pHead->_pNext;
	}
	pHead->_pNext = pHead;
	pHead->_pPre = pHead;
}
void DListDestroy(DLNode **pHead)//销毁,要释放掉二级指针，也会改变指针的方向
{
	assert(pHead);
	DListClear(*pHead);
	free(*pHead);
	*pHead = NULL;
}