当前位置 : 主页 > 编程语言 > c语言 >

【数据结构】双向链表的实现

来源:互联网 收集:自由互联 发布时间:2023-09-03
一、什么是双向链表 双向链表也叫双链表,是链表的一种,它的每个 数据 节点中都有两个 指针 ,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很


一、什么是双向链表

        双向链表也叫双链表,是链表的一种,它的每个数据节点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表

【数据结构】双向链表的实现_List


二、双向链表的实现

        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 LTDestory(LTNode* phead);
void LTPrint(LTNode* phead);
bool LTEmpty(LTNode * phead);
void LTPushBack(LTNode* phead,LTDataType x);
void LTPopBack(LTNode * phead);

void LTPushFront(LTNode *phead,LTDataType x);
void LTPopFront(LTNode* phead);

void LTInsert(LTNode* pos,LTDataType x);
void LTErase(LTNode* pos);
LTNode* LTFind(LTNode* phead, LTDataType x);

【数据结构】双向链表的实现_#include_02

        List.c

        

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
LTNode* BuyListNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("fail:malloc");
		exit(-1);
	}
	node->next = NULL;
	node->prev = NULL;
	node->data = x;
	return node;
}

LTNode* LTInit()
{
	LTNode* phead = BuyListNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}

void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}
void LTPrint(LTNode* phead)
{
	assert(phead);
	printf("<=phead=>");
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<=>",cur->data);
		cur = cur->next;
	}
	printf("\n");
}


void LTPushBack(LTNode* phead,LTDataType x)
{	
	assert(phead);
	LTInsert(phead,x);
}

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTErase(phead->prev);
}

void LTPushFront(LTNode* phead,LTDataType x)
{
	assert(phead);
	LTInsert(phead->next,x);
}

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTErase(phead->next);
}

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前一个位置添加节点
void LTInsert(LTNode* pos,LTDataType x)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyListNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* p = pos->prev;
	LTNode* n = pos->next;
	p->next = n;
	n->prev = p;
	free(pos);
	pos = NULL;
}

【数据结构】双向链表的实现_链表_03

   思路:

        BuyListNode函数

        BuyListNode的实现,我们在实现头插尾插时,为了更加遍历的实现功能,我们创建了BuyListNode函数,malloc一块新的空间,并且对其进行初始化,返回其类型

LTNode* BuyListNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("fail:malloc");
		exit(-1);
	}
	node->next = NULL;
	node->prev = NULL;
	node->data = x;
	return node;
}

【数据结构】双向链表的实现_List_04

       LTInit函数

        在实现该链表前,我们对其进行初始化,对其哨兵位的头节点,进行循环指向

        哨兵位头节点的出现,使得链表添加与删除效率大大提高

LTNode* LTInit()
{
	LTNode* phead = BuyListNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

【数据结构】双向链表的实现_链表_05

        LTInsert和LTErase函数

                LTInsert函数的实现:

                                                我们找到pos的前一个节点位置,进行操作,首先我们找到pos的前一个位置,保存该节点,创建新的节点,将pos前一个位置的节点next指向新节点,新节点的prev指向pos前一个位置,新节点的next指向pos,pos的前一个位置指向新节点

               LTErase函数的实现:

                                                删除pos位置的节点,先暴力检查是否为空,其中只有哨兵位的头节点,如果只有头节点则直接报错,保存pos位置节点的前一个节点和后一个节点,让pos的prev和next分别指向前一个位置和后一个位置的节点

void LTInsert(LTNode* pos,LTDataType x)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyListNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* p = pos->prev;
	LTNode* n = pos->next;
	p->next = n;
	n->prev = p;
	free(pos);
	pos = NULL;
}

【数据结构】双向链表的实现_链表_06

        LTPushBack与LTPopBack函数

                尾插与尾删功能,我们先对其进行暴力检查,通过LTInsert和LTErase函数进行实现该功能

void LTPushBack(LTNode* phead,LTDataType x)
{	
	assert(phead);
	LTInsert(phead,x);
}

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTErase(phead->prev);
}

【数据结构】双向链表的实现_链表_07

        LTPushFront和LTPopFront函数

         头插与头删功能,我们先对其进行暴力检查,通过LTInsert和LTErase函数进行实现该功能

void LTPushFront(LTNode* phead,LTDataType x)
{
	assert(phead);
	LTInsert(phead->next,x);
}

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTErase(phead->next);
}

【数据结构】双向链表的实现_List_08

          LTDestory和LTPrint函数的实现

               LTPrint: 当我们功能实现时,LTPrint函数可在控制台进行打印和输出,优先找到哨兵位头节点的下一位,我们对其进行循环,当循环节点等于哨兵位时,停止循环

                LTDestory:当我们退出链表时,对其进行销毁

void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}
void LTPrint(LTNode* phead)
{
	assert(phead);
	printf("<=phead=>");
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<=>",cur->data);
		cur = cur->next;
	}
	printf("\n");
}

【数据结构】双向链表的实现_#include_09

                  ListTest.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
void ListTest()
{
	LTNode* phead = LTInit();
	LTPushBack(phead, 1);
	LTPushBack(phead, 2);
	LTPushBack(phead, 3);
	LTPrint(phead);
	LTPopBack(phead);
	LTPrint(phead);
	LTPushFront(phead,10);
	LTPrint(phead);
	LTPopFront(phead);
	LTPrint(phead);
}

int main()
{
	ListTest();
	return 0;
}

【数据结构】双向链表的实现_List_10



上一篇:驱动开发:内核实现进程汇编与反汇编
下一篇:没有了
网友评论