欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

带头循环双向链表的增删查找操作

程序员文章站 2022-03-24 18:01:51
...
#pragma once

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>

//双向带头循环  链表(如果要改变链表的头指针指向,就要传入二级指针)
typedef int DataType;

typedef struct DListNode
{
	DataType data;
	struct DListNode *prev;
	struct DListNode *next;

}DListNode;

//初始化   销毁   清空链表   插入节点   删除节点

void DListInit(DListNode **ppHead, DataType data)
{
	assert(ppHead);
	DListNode *pHead = (DListNode *)malloc(sizeof(DListNode));
	pHead->data = data;
	assert(pHead != NULL);
	//初始化时,创建一个头结点,有时候会让头结点的data存一些有效信息(长度)
	pHead->next = pHead;//指向自己
	pHead->prev = pHead;//指向自己

	*ppHead = pHead;
}

// 销毁链表   但是要保留头结点
void DListClear(DListNode *pHead)
{
	DListNode *cur = pHead->next;
	DListNode *next = NULL;
	while (cur != pHead)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	pHead->next = pHead;
	pHead->prev = pHead;
}

// 销毁链表   不保留头结点
void DListDestroy(DListNode **ppHead)
{
	assert(ppHead);
	DListClear(*ppHead);
	free(*ppHead);
	*ppHead = NULL;
}

DListNode*  DListFind(DListNode *pHead, DataType data)
{
	assert(pHead);
	DListNode *pcur = pHead->next;
	while (pcur != pHead)
	{
		if (pcur->data == data)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	printf("have no data!!!\n");
	return NULL;
}

//插入(pos前面插入)
void DListInsert(DListNode *pHead, DListNode *pos, DataType data)
{
	assert(pHead);
	assert(pos);
	DListNode *newNode = (DListNode *)malloc(sizeof(DListNode));
	newNode->data = data;

	newNode->prev = pos->prev;
	newNode->next = pos;
	pos->prev->next = newNode;
	pos->prev = newNode;
}


//删除(删除pos节点)(pos不能是头节点)
void DListErase(DListNode *pHead, DListNode *pos)
{
	assert(pos != pHead);
	assert(pos != NULL);

	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
}


void DListPrint(DListNode *pHead)
{
	assert(pHead);
	DListNode *cur = pHead;
	while (cur->next != pHead)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("%d->", cur->data);
	printf("%d\n", cur->next->data);
}


void Test()
{
	DListNode *pHead = NULL;//头节点指针
	DListInit(&pHead, 0);//头节点

	DListInsert(pHead, pHead, 1);
	DListInsert(pHead, pHead, 2);
	DListInsert(pHead, pHead, 3);
	DListInsert(pHead, pHead, 4);
	DListInsert(pHead, pHead, 5);


	DListErase(pHead, DListFind(pHead, 1));//头删
	DListErase(pHead, DListFind(pHead, 2));
	DListErase(pHead, DListFind(pHead, 3));//任意位置删除
	DListErase(pHead, DListFind(pHead, 4));
	DListErase(pHead, DListFind(pHead, 5));//尾删

	DListPrint(pHead);

	DListDestroy(&pHead);
}