旅游平台网站合作建设方案,上海市建筑业官网,福建建筑人才网官方网站,全椒网站建设专栏#xff1a;数据结构 个人主页#xff1a;HaiFan. 专栏简介#xff1a;从零开始#xff0c;数据结构#xff01;#xff01; 双链表前言双链表各接口的实现为要插入的值开辟一块空间BuyLN初始化LNInit和销毁LNDestory打印链表中的值LNPrint尾插LNPushBack和尾删LNPop… 专栏数据结构 个人主页HaiFan. 专栏简介从零开始数据结构 双链表前言双链表各接口的实现为要插入的值开辟一块空间BuyLN初始化LNInit和销毁LNDestory打印链表中的值LNPrint尾插LNPushBack和尾删LNPopBack头插LNPushFron和头删LNPopFront判断链表是否为空LNEmpty查找LNFind任意位置插入 LNInsert任意位置删除LNErase测试结果源代码前言 双向链表是在结构体内存两个指针一个指针存下一个结点的地址另一个指针是存上一个结点的地址这样就可以通过一个结点找到前后两个结点。听起来很复杂但实现起来要比单链表简单许多。 双链表
typedef int LDataType;typedef struct ListNode
{LDataType val;struct ListNode* head;struct ListNode* tail;
}LN;双链表各接口的实现
LN* BuyLN(LDataType x);//为要插入的值开辟一块空间void LNInit(LN** pphead);//初始化
void LNDestory(LN* phead);//销毁void LNPrint(LN* phead);//打印链表中的值void LNPushBack(LN* phead, LDataType x);//尾插
void LNPopBack(LN* phead);//尾删void LNPushFront(LN* phead, LDataType x);//头插
void LNPopFront(LN* phead);//头删bool LNEmpty(LN* phead);//双链表是否为空LN* LNFind(LN* phead, LDataType x);//查找void LNInsert(LN* pos, LDataType x);//任意位置插入
void LNErase(LN* pos);//任意位置删除为要插入的值开辟一块空间BuyLN
这个BuyLN是为链表开辟一块空间为什么要额外写一个这函数因为在插入值的过程中需要为这个值开辟一块空间每次都需要写相同的代码所以把这个代码写成一个函数用到式直接调用函数即可
LN* BuyLN(LDataType x)
{LN* sn (LN*)malloc(sizeof(LN));if (sn NULL){perror(malloc fail);exit(-1);}sn-val x;sn-head NULL;sn-tail NULL;return sn;
}初始化LNInit和销毁LNDestory
双链表的初始化只需要把链表中的head和tail指针都指向自己形成一个环即可。
void LNInit(LN** pphead)
{(*pphead) BuyLN(-1);(*pphead)-head *pphead;(*pphead)-tail *pphead;
}空间有开辟就有销毁销毁之后把空间还给系统
void LNDestory(LN* phead)//ٿռ
{assert(phead);LN* cur phead-head;while (cur ! phead){LN* sn cur;free(sn);sn NULL;cur cur-head;}
}打印链表中的值LNPrint
头结点是不需要打印的所以可以先定义一个sn代表头结点指向的下一个元素的位置然后依次打印直到sn的地址和头节点的地址相同时打印结束
void LNPrint(LN* phead)
{assert(phead);LN* sn phead-head;while (sn ! phead){cout sn-val ;sn sn-head;}cout endl;
}尾插LNPushBack和尾删LNPopBack
单链表的尾插需要先遍历找到尾然后进行插入操作双链表不同于单链表双链表有两个指针一个存下一个结点一个存上一个结点我们只需要在头节点的左面也就是让头节点中存上一个结点存要插入的值即可这样就能完成尾插。 这样就不需要在遍历链表找尾了。
void LNPushBack(LN* phead, LDataType x)
{LN* newnode BuyLN(x);LN* prev phead-tail;prev-head newnode;newnode-tail prev;newnode-head phead;phead-tail newnode;
}尾删依旧是把头节点左边的那一个元素给删除即可当然表中如果只有头节点就不要在删除了。。。
void LNPopBack(LN* phead)
{assert(phead-head ! phead-tail);LN* prev phead-tail;prev-tail-head phead;phead-tail prev-tail;free(prev);prev NULL;
}头插LNPushFron和头删LNPopFront 头插的话要先找到首元素然后把要插入的元素和头节点首元素都双向链接起来即可。
void LNPushFront(LN* phead, LDataType x)
{LN* newnode BuyLN(x);LN* ne phead-head;ne-tail newnode;newnode-head ne;phead-head newnode;newnode-tail phead;
}头删的话呢跟上面一样要先找到首元素然后让头节点和首元素指向的下一个元素链接起来即可。
void LNPopFront(LN* phead)
{assert(phead-head ! phead-tail);LN* ne phead-head;phead-head ne-head;ne-head-tail phead;free(ne);ne NULL;}判断链表是否为空LNEmpty
如果链表为空返回true反之返回false当双链表的头指针和尾指针都指向自己的时候就说明双链表为空。
bool LNEmpty(LN* phead)
{assert(phead);return phead-head phead-tail;
}查找LNFind
查找一个元素返回这个元素的地址只需要遍历双链表即可。
LN* LNFind(LN* phead, LDataType x)
{assert(phead);assert(phead-head ! phead-tail);LN* cur phead-head;while (cur ! phead){if (x cur-val){return cur;}cur cur-head;}return NULL;
}任意位置插入 LNInsert
再插入之前要先找到要插入的位置寻找这个位置的任务就交给了上面写的查找函数我们只需要传递参数对该位置进行插入即可
void LNInsert(LN* pos, LDataType x)
{assert(pos);LN* newnode BuyLN(x);LN* prev pos-head;pos-head newnode;newnode-tail pos;newnode-head prev;prev-tail newnode;
}任意位置删除LNErase
和上面一样要删除哪个元素就要先找到那个元素然后进行删除操作找到那个元素的任务依旧交给LNFind函数
void LNErase(LN* pos)
{assert(pos);LN* ne pos-head;pos-head ne-head;ne-tail pos;
}测试结果
测试代码
#include List.hvoid TestLN()
{LN* plist NULL;LNInit(plist);LNPrint(plist);LNPushBack(plist, 1);LNPushBack(plist, 2);LNPushBack(plist, 3);LNPushBack(plist, 4);LNPushBack(plist, 5);LNPrint(plist);LNPopBack(plist);LNPrint(plist);LNPushFront(plist, -1);LNPushFront(plist, -2);LNPushFront(plist, -3);LNPushFront(plist, -4);LNPushFront(plist, -5);LNPrint(plist);LNPopFront(plist);LNPrint(plist);LN* ret LNFind(plist, 3);if (ret ! NULL){cout ret-val ret endl;LNInsert(ret, 10000);LNErase(ret);}LNPrint(plist);LNDestory(plist);
}int main()
{TestLN();return 0;
}源代码
.h文件
#pragma once#include iostream
#include assert.h
#include stdlib.husing namespace std;typedef int LDataType;typedef struct ListNode
{LDataType val;struct ListNode* head;struct ListNode* tail;
}LN;LN* BuyLN(LDataType x);//为要插入的值开辟一块空间void LNInit(LN** pphead);//初始化
void LNDestory(LN* phead);//销毁void LNPrint(LN* phead);//打印链表中的值void LNPushBack(LN* phead, LDataType x);//尾插
void LNPopBack(LN* phead);//尾删void LNPushFront(LN* phead, LDataType x);//头插
void LNPopFront(LN* phead);//头删bool LNEmpty(LN* phead);//双链表是否为空LN* LNFind(LN* phead, LDataType x);//查找void LNInsert(LN* pos, LDataType x);//任意位置插入
void LNErase(LN* pos);//任意位置删除
.cpp文件
#include List.hLN* BuyLN(LDataType x)
{LN* sn (LN*)malloc(sizeof(LN));if (sn NULL){perror(malloc fail);exit(-1);}sn-val x;sn-head NULL;sn-tail NULL;return sn;
}void LNPrint(LN* phead)
{assert(phead);LN* sn phead-head;while (sn ! phead){cout sn-val ;sn sn-head;}cout endl;
}void LNInit(LN** pphead)//ʼ
{(*pphead) BuyLN(-1);(*pphead)-head *pphead;(*pphead)-tail *pphead;
}void LNDestory(LN* phead)//ٿռ
{assert(phead);LN* cur phead-head;while (cur ! phead){LN* sn cur;free(sn);sn NULL;cur cur-head;}
}void LNPushBack(LN* phead, LDataType x)
{LN* newnode BuyLN(x);LN* prev phead-tail;prev-head newnode;newnode-tail prev;newnode-head phead;phead-tail newnode;
}void LNPopBack(LN* phead)
{assert(phead-head ! phead-tail);LN* prev phead-tail;prev-tail-head phead;phead-tail prev-tail;free(prev);prev NULL;
}void LNPushFront(LN* phead, LDataType x)
{LN* newnode BuyLN(x);LN* ne phead-head;ne-tail newnode;newnode-head ne;phead-head newnode;newnode-tail phead;
}void LNPopFront(LN* phead)
{assert(phead-head ! phead-tail);LN* ne phead-head;phead-head ne-head;ne-head-tail phead;free(ne);ne NULL;}bool LNEmpty(LN* phead)
{assert(phead);return phead-head phead-tail;
}LN* LNFind(LN* phead, LDataType x)
{assert(phead);assert(phead-head ! phead-tail);LN* cur phead-head;while (cur ! phead){if (x cur-val){return cur;}cur cur-head;}return NULL;
}void LNInsert(LN* pos, LDataType x)
{assert(pos);LN* newnode BuyLN(x);LN* prev pos-head;pos-head newnode;newnode-tail pos;newnode-head prev;prev-tail newnode;
}void LNErase(LN* pos)
{assert(pos);LN* ne pos-head;pos-head ne-head;ne-tail pos;
}
test.cpp文件
#define _CRT_SECURE_NO_WARNINGS 1#include List.hvoid TestLN()
{LN* plist NULL;LNInit(plist);LNPrint(plist);LNPushBack(plist, 1);LNPushBack(plist, 2);LNPushBack(plist, 3);LNPushBack(plist, 4);LNPushBack(plist, 5);LNPrint(plist);LNPopBack(plist);LNPrint(plist);LNPushFront(plist, -1);LNPushFront(plist, -2);LNPushFront(plist, -3);LNPushFront(plist, -4);LNPushFront(plist, -5);LNPrint(plist);LNPopFront(plist);LNPrint(plist);LN* ret LNFind(plist, 3);if (ret ! NULL){cout ret-val ret endl;LNInsert(ret, 10000);LNErase(ret);}LNPrint(plist);LNDestory(plist);
}int main()
{TestLN();return 0;
}
