马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
×
弁言
用动态的方式实现双向链表的注意接口，以代码解释为主。
一、什么是双向链表
单向链表是可以向后依次遍历每个元素，双向链表是既可以依次向后遍历每个元素，也可以依次向前，遍历每个元素。
有了单链表的实现，双向链表的实现是很类似的。
注意：这里是实现的是带“哨兵位”的双向链表，即带头双向循环链表。也有不带头的双向循环链表，可以自己实验实验。
二、动态双向链表模仿实现
分3个文件：- List.c //双链表的主要代码（核心）
- List.h //双链表的函数的声明
- test.c //测试代码
界说在List.h文件中- #pragma once
- #include<stdio.h>
- #include<assert.h>
- #include<stdlib.h>
- #include<stdbool.h>
- //双链表的结构：
- typedef int LTDataType;
- typedef struct ListNode
- {
- LTDataType data; //存储的数据
- struct ListNode* next;//指向前一个地址的指针
- struct ListNode* prev;//指向下一个地址的指针
- }LTNode;
- LTNode* LTBuyNode(LTDataType x) //申请新结点
- {
- LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
- if (newnode == NULL)
- {
- perror("malloc fail!");
- exit(1);
- }
- newnode->data = x;
- newnode->next = newnode->prev = newnode; //结点自己指向自己
- return newnode;
- }
- LTNode* LTInit() //初始化哨兵位
- {
- LTNode* phead = LTBuyNode(-1); //将哨兵位的值设置成无效的值
- return phead;
- }
小提示：先修改新结点的指针，再修改原链表的指针
以明白为主，不消影象代码- //尾插
- void LTPushBack(LTNode* phead, LTDataType x)
- {
- assert(phead);
- LTNode* newnode = LTBuyNode(x);
- newnode->prev = phead->prev; //新结点的前驱指向最后一个结点
- newnode->next = phead; //新结点的后驱指向哨兵位
- phead->prev->next = newnode; //先找到原链表的最后一个结点，将其后驱改成新结点的地址
- phead->prev = newnode; //最后将哨兵位的前驱指向新结点（即最后一行结点）
- }
- //头插
- void LTPushFront(LTNode* phead, LTDataType x)
- {
- assert(phead);
- LTNode* newnode = LTBuyNode(x);
- newnode->next = phead->next;
- newnode->prev = phead;
- phead->next->prev = newnode;
- phead->next = newnode;
- }
- void LTPrint(LTNode* phead)
- {
- assert(phead);
- LTNode* pcur = phead->next; //指向第一个结点
- while (pcur != phead) //回到哨兵位时，结束打印
- {
- printf("%d->", pcur->data);
- pcur = pcur->next; //依次向后找结点，打印结点内容
- }
- printf("\n");
- }
- //判断有无元素
- bool LTEmpty(LTNode* phead)
- {
- assert(phead);
- return phead->next == phead; //当哨兵位自己指向自己说明没有元素，链表为空，否则，链表里面就是有元素的
- }
- //尾删
- void LTPopBack(LTNode* phead)
- {
- assert(!LTEmpty(phead));
- LTNode* del = phead->prev; //拿到尾结点
- del->prev->next = phead; //修改尾结点前一个结点的后驱
- phead->prev = del->prev; //修改头结点的前驱
- free(del);
- del = NULL;
- }
- //头删
- void LTPopFront(LTNode* phead)
- {
- assert(!LTEmpty(phead));
- LTNode* del = phead->next;
- del->next->prev = phead; //修改头结点的下一个结点的前驱
- phead->next = del->next; //修改头结点的后驱
- free(del);
- del = NULL;
- }
- //查找
- LTNode* LTFind(LTNode* phead, LTDataType x)
- {
- assert(phead);
- LTNode* pcur = phead->next;
- while (pcur != phead) //依次向后遍历链表
- {
- if (pcur->data == x)
- {
- return pcur; //找到返回结点的地址
- }
- pcur = pcur->next;
- }
- return NULL; //没有就返回NULL
- }
- //在pos位置之后插入数据
- void LTInsert(LTNode* pos, LTDataType x)
- {
- assert(pos);
- LTNode* newnode = LTBuyNode(x);
- newnode->prev = pos;
- newnode->next = pos->next;
- pos->next->prev = newnode;
- pos->next = newnode;
- }
- //在pos位置前插入数据
- void LTInsertAfter(LTNode* pos, LTDataType x)
- {
- assert(pos);
- LTNode* newnode = LTBuyNode(x);
- newnode->next = pos;
- newnode->prev = pos->prev;
- pos->prev->next = newnode;
- pos->prev = newnode;
- }
- //删除pos位置的结点
- void LTErase(LTNode* pos)
- {
- assert(pos);
- pos->next->prev = pos->prev;
- pos->prev->next = pos->next;
- free(pos);
- pos = NULL;
- }
- 销毁双向链表(法一：因为要对头节点做修改，传二级指针)
- void LTDesTroy(LTNode** pphead)
- {
- assert(pphead);
- LTNode* pcur = (*pphead)->next;
- while (pcur != *(pphead))
- {
- LTNode* next = pcur->next;
- free(pcur);
- pcur = next;
- }
- free(*pphead);
- *pphead = NULL;
- }
- //销毁双向链表(法二：为了保持代码的统一性，这里也传一级指针，但是调用完函数后需要手动将头结点置为NULL;)
- void LTDesTroy(LTNode* phead)
- {
- assert(phead);
- LTNode* pcur = phead;
- while (pcur != phead)
- {
- LTNode* next = pcur->next;
- free(pcur);
- pcur = next;
- }
- }
说白了:双向链表的实现和修改就是对结点地点的修改，只要想明白了，是很简朴的
1、List.h中的代码：
- #pragma once
- #include<stdio.h>
- #include<assert.h>
- #include<stdlib.h>
- #include<stdbool.h>
- //双链表的结构：
- typedef int LTDataType;
- typedef struct ListNode
- {
- LTDataType data; //存储的数据
- struct ListNode* next;//指向前一个地址的指针
- struct ListNode* prev;//指向下一个地址的指针
- }LTNode;void LTPrint(LTNode* phead);LTNode* LTInit();//尾插void LTPushBack(LTNode* phead, LTDataType x);//头插void LTPushFront(LTNode* phead, LTDataType x);//判断有无元素bool LTEmpty(LTNode* phead);//尾删void LTPopBack(LTNode* phead);//头删void LTPopFront(LTNode* phead);//查找LTNode* LTFind(LTNode* phead, LTDataType x);//在pos位置之后插入数据void LTInsert(LTNode* pos, LTDataType x);//在pos位置前插入数据void LTInsertAfter(LTNode* pos, LTDataType x);//删除pos位置的结点void LTErase(LTNode* pos);//烧毁双向链表(法一：由于要对头节点做修改，传二级指针)//void LTDesTroy(LTNode** pphead);//烧毁双向链表(法二：为了保持代码的同一性，这里也传一级指针，但是调用完函数后必要手动将头结点置为NULL;)void LTDesTroy(LTNode* phead);
3、测试时的代码（test.c中）：
- #include"List.h"
- int main()
- {
- LTNode* plist = LTInit();
- LTPushBack(plist, 1);
- LTPushBack(plist, 2);
- LTPushBack(plist, 3);
- LTPushBack(plist, 4);
-
- /*LTPushFront(plist, 3);
- if (LTFind(plist, 2))
- {
- printf("找到了\n");
- }
- else
- {
- printf("无\n");
- }*/
- //LTInsert(LTFind(plist, 3), 4);
- //LTInsertAfter(LTFind(plist, 3), 4);
- //LTErase(LTFind(plist, 2));
- LTPrint(plist);
- LTDesTroy(plist);
- plist = NULL;
- return 0;
- }
|
发表于 2025-10-1 10:17:34