带头双向循环链表的实现及注释教学

时间：2024-03-30 12:43:11

首先需要借助三个文件        test.c   list.h   list.c

目录

list.h

list.c

test.c

list.h

用于声明函数及创建结构体、包含头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;

LTNode* LTInit();
void LTPrint(LTNode* phead);

bool LTEmpty(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);

LTNode* LTFind(LTNode* phead, LTDataType x);		//查找要返回指针

// 在pos之前插入
void LTInsert(LTNode* pos, LTDataType x);		//插入要传指针
// 删除pos位置的值
void LTErase(LTNode* pos);		//删除要传指针
void LTDestroy(LTNode* phead);	//需要人为置空

list.c

用于函数功能的实现

#include"List.h"

LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));	//开辟
	if (newnode == NULL)	//判断
	{
		perror("malloc fail");
		return NULL;
	}

	newnode->data = x;
	newnode->next = NULL;	//置空
	newnode->prev = NULL;	//置空
	return newnode;		//返回新节点的地址
}

LTNode* LTInit()			//初始化
{
	LTNode* phead = BuyLTNode(-1);	//指针接收新开辟的空间
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

void LTPrint(LTNode* phead)
{
	assert(phead);

	printf("guard<==>");
	LTNode* cur = phead->next;		//遍历节点，cur都是从有效节点开始。
	while (cur != phead)
	{
		printf("%d<==>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

bool LTEmpty(LTNode* phead)
{
	assert(phead);

	return phead->next == phead;		//为空return真
}


//1.链接尾 2.成环	

void LTPushBack(LTNode* phead, LTDataType x)	//目的是尾插，尾节点可以直接找到！
{
	assert(phead);

	LTInsert(phead, x);		//在哨兵位之前插入

	//LTNode* tail = phead->prev;	//找尾指针
	//LTNode* newnode = BuyLTNode(x);	//接收新建的节点

		//链接“尾”和新节点
		
	//tail->next = newnode;		
	//newnode->prev = tail;
	
		//成环

	//newnode->next = phead;	//尾的下一个是头
	//phead->prev = newnode;	//头的上一个是尾
}

//void LTPushFront(LTNode* phead, LTDataType x)
//{
//	assert(phead);
//	LTNode* newnode = BuyLTNode(x);
//
//	newnode->next = phead->next;
//	phead->next->prev = newnode;
//
//	phead->next = newnode;
//	newnode->prev = phead;
//}



//不用管有没有有效节点

void LTPushFront(LTNode* phead, LTDataType x)
{
	/*assert(phead);
	LTNode* newnode = BuyLTNode(x);

	//当只有哨兵位时，phead->next  与 phead->prev 就是 phead
	LTNode* first = phead->next;	//防止找不到下一个，先记录他！（原来的首节点）

	phead->next = newnode;
	newnode->prev = phead;

	newnode->next = first;
	first->prev = newnode;*/

	LTInsert(phead->next, x);			//第一个有效节点之前插入
}
void LTPopBack(LTNode* phead)		//所有删除都需要判断有没有有效节点
{
	assert(phead);
	assert(!LTEmpty(phead));	//判断有没有有效节点。	（！真   就是    假）
	LTErase(phead->prev);

	/*LTNode* tail = phead->prev;	//找尾
	LTNode* tailPrev = tail->prev;	//找prev

	free(tail);		//free

		//链接

	tailPrev->next = phead;		
	phead->prev = tailPrev;*/

}

//void LTPopFront(LTNode* phead)
//{
//	assert(phead);
//	assert(!LTEmpty(phead));
//
//	LTNode* next = phead->next;
//
//	/*phead->next = next->next;
//	phead->next->prev = phead;
//	free(next);*/
//
//	phead->next = next->next;
//	next->next->prev = phead;
//	free(next);
//}

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));	//一定要有一个节点！ 

	LTErase(phead->next);

	//LTNode* first = phead->next;		//借助first 和 second 表示节点
	//LTNode* second = first->next;

		//链接

	//phead->next = second;
	//second->prev = phead;

		//释放

	//free(first);
}

LTNode* LTFind(LTNode* phead, LTDataType x)			//查找绑定修改、插入
{
	assert(phead);

	LTNode* cur = phead->next;	//从有效节点开始查找
	while (cur != phead)	//遍历所有
	{
		if (cur->data == x)
		{
			return cur;		//返回指针
		}

		cur = cur->next;
	}

	return NULL;		//找不到返回空
}

// 在  pos 之前插入， 传pos指针
void LTInsert(LTNode* pos, LTDataType x)		//插入（头插、尾插复用insert）
{
	assert(pos);

	LTNode* prev = pos->prev;
	LTNode* newnode = BuyLTNode(x);		//开空间

	// prev newnode pos
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

// 删除  pos   位置  的值
void LTErase(LTNode* pos)		//要么传phead，检查不能删除phead，要么再检查
{
	assert(pos);

	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;

	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);		//free空间
}

void LTDestroy(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;		//头节点开始
	while (cur != phead)	//！= 哨兵位
	{
		LTNode* next = cur->next;	//建立一个next，指向下一个节点！
		free(cur);
		cur = next;		//通过cur = next改变cur迭代
	}

	
	free(phead);	//释放哨兵位

		//没必要置空phead，形参改变不会影响实参。如果想置空，则要传二级指针！
}

test.c

用于测试函数功能

注意点

此链表的强大之处在于：当只有一个有效节点时，仍能按照一种情况完成所有增删查改！

相关文章