网站建设温州,wordpress美食主题,wordpress添加登录,科技资讯网站有哪些Yan-英杰的主页
悟已往之不谏 知来者之可追 C程序员#xff0c;2024届电子信息研究生 目录
一、什么是双向链表
二、双向链表的实现 一、什么是双向链表 双向链表也叫双链表#xff0c;是链表的一种#xff0c;它的每个数据节点中都有两个指针#xff0c;分别指向直接后… Yan-英杰的主页
悟已往之不谏 知来者之可追 C程序员2024届电子信息研究生 目录
一、什么是双向链表
二、双向链表的实现 一、什么是双向链表 双向链表也叫双链表是链表的一种它的每个数据节点中都有两个指针分别指向直接后继和直接前驱。所以从双向链表中的任意一个结点开始都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。 二、双向链表的实现 List.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.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); 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;
} 思路: 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;
} LTInit函数 在实现该链表前我们对其进行初始化对其哨兵位的头节点进行循环指向 哨兵位头节点的出现使得链表添加与删除效率大大提高 LTNode* LTInit()
{LTNode* phead BuyListNode(-1);phead-next phead;phead-prev phead;return phead;
} LTInsert和LTErase函数 LTInsert函数的实现: 我们找到pos的前一个节点位置进行操作首先我们找到pos的前一个位置保存该节点创建新的节点将pos前一个位置的节点next指向新节点新节点的prev指向pos前一个位置新节点的next指向pospos的前一个位置指向新节点 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;
} 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);
} 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);
}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);
} 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;
}
