C语言:数据结构(双向链表)
Fastrack527 2024-06-12 17:05:05 阅读 53
目录
1、双向链表的结构2、顺序表和双向链表的优缺点分析3、双向链表的实现
1、双向链表的结构
注意:这⾥的“带头“跟前面我们说的“头节点”是两个概念,实际前面的在单链表阶段称呼不严谨,但是为了更好的理解就直接称为单链表的头节点。
带头链表里的头节点,实际为“放哨的”,哨兵位节点不存储任何有效元素,只是站在这里“放哨的”。
“哨兵位”存在的意义:遍历循环链表避免死循环。
2、顺序表和双向链表的优缺点分析
不同点 | 顺序表 | 链表 |
存储空间上 | 物理上一定连续 | 逻辑上连续,但物理上不一定连续 |
随机访问 | 支持O(1) | 不支持O(N) |
任意位置插⼊或者删除元素 | 可能需要搬移元素,效率低 | 只需修改指针指向 |
插入 | 动态顺序表,空间不够时需要扩容 | 没有容量的概念 |
应用场景 | 元素高效存储和频繁访问 | 任意位置频繁插入和删除 |
3、双向链表的实现
ListNode.h
#pragma once#include <stdio.h>#include <stdlib.h>#include <assert.h>//定义双向链表节点的结构typedef int Ltdatatype;typedef struct ListNode{Ltdatatype data;struct ListNode* prev;//指向前一个节点的指针struct ListNode* next;//指向后一个节点的指针}ListNode;//双向链表的初始化ListNode* LtInit();//尾插//不改变哨兵位的地址,所以传一级即可void LtPushBack(ListNode* phead, Ltdatatype x);//插入数据之前,链表必须初始化到只有一个头结点的情况//打印链表void LtPrint(ListNode* phead);//头插void LtPushFront(ListNode* phead, Ltdatatype x);//尾删LtPopBack(ListNode* phead);//头删LtPopFront(ListNode* phead);//查找ListNode* LtFind(ListNode* phead, Ltdatatype x);//指定位置前插入void LtInsert(ListNode* pos, Ltdatatype x);//删除pos位置void LtErase(ListNode* pos);//销毁链表void LtDestroy(ListNode* phead);
ListNode.c
#define _CRT_SECURE_NO_WARNINGS#include "ListNode.h"//申请节点ListNode* LtBuyNode(Ltdatatype x){ListNode* node = (ListNode*)malloc(sizeof(ListNode));if (node == NULL){perror("malloc fail");exit(1);}//申请成功node->data = x;node->next = node->prev = node;return node;}//双向链表的初始化ListNode* LtInit(){ListNode*phead = LtBuyNode(-1);return phead;}//尾插void LtPushBack(ListNode* phead, Ltdatatype x){assert(phead);ListNode* newnode = LtBuyNode(x);//改变新节点的指向newnode->prev = phead->prev;newnode->next = phead;//改变尾节点和哨兵位的指向phead->prev->next = newnode;phead->prev = newnode;}//打印链表void LtPrint(ListNode* phead){ListNode* pcur = phead->next;//遍历链表while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");}//头插void LtPushFront(ListNode* phead,Ltdatatype x){assert(phead);ListNode* newnode = LtBuyNode(x);newnode->prev = phead;newnode->next = phead->next;//修改哨兵位和第一个有效节点的指向phead->next->prev = newnode;phead->next = newnode;}//尾删LtPopBack(ListNode* phead){//链表必须有效且链表不能为空(只有一个哨兵位)assert(phead && phead->next != phead);ListNode* Del = phead->prev;//尾节点ListNode* DelPrev = Del->prev;//尾节点的前一个节点phead->prev = DelPrev;DelPrev->next = phead;free(Del);//删除Del节点Del = NULL;}//头删LtPopFront(ListNode* phead){//判断链表是否有效和链表是否为空assert(phead && phead->next != phead);ListNode* Del = phead->next;//第一个有效节点ListNode* DelNext = Del->next;//有效节点的下一个节点phead->next = DelNext;DelNext->prev = phead;free(Del);//删除Del节点Del = NULL;}//查找ListNode* LtFind(ListNode* phead, Ltdatatype x){ListNode* pcur = phead->next;//遍历链表while (pcur != phead){if (pcur->data == x)return pcur;pcur = pcur->next;//继续让pcur往下遍历}return NULL;//没有找到}//在pos位置之前插入数据void LtInsert(ListNode* pos,Ltdatatype x){ListNode* newnode = LtBuyNode(x);newnode->prev = pos->prev;newnode->next = pos;pos->prev->next = newnode;pos->prev = newnode;}//删除pos位置void LtErase(ListNode* pos){assert(pos);ListNode* PosPrev = pos->prev;//pos的前一个节点ListNode* PosNext = pos->next;//pos的后一个节点PosPrev->next = PosNext;PosNext->prev = PosPrev;free(pos);//pos = NULL;这里就算置空了,也不会影响实参}//销毁链表void LtDestroy(ListNode* phead){ListNode* pcur = phead->next;//边遍历边释放节点while (pcur != phead){ListNode* Next = pcur->next;//保存要释放掉节点的下一个地址free(pcur);pcur = Next;}//此时pcur指向phead,而phead还没有被销毁free(phead);pcur = NULL;}
text.c
#define _CRT_SECURE_NO_WARNINGS#include "ListNode.h"void LtnodeTest(){//测试初始化ListNode* plist = LtInit();//测试尾插LtPushBack(plist,1);LtPushBack(plist,2);LtPushBack(plist,3);//测试打印LtPrint(plist);//测试头插//LtPushFront(plist,4);//LtPushFront(plist,5);//LtPushFront(plist,6);//LtPrint(plist);//测试尾删LtPopBack(plist);LtPrint(plist);//测试头删//LtPopFront(plist);//LtPrint(plist);//测试查找//ListNode*find = LtFind(plist,2);//if (find)//printf("找到了!\n");//else//printf("没找到!\n");//测试在pos位置之前插入数据//LtInsert(find,88);//LtPrint(plist);//测试删除pos位置//LtErase(find);//find = NULL;//形参的改变不会影响实参,所以要在函数调用结束之后置为空//LtPrint(plist);//测试销毁链表//LtDestroy(plist);//plist = NULL;}int main(){LtnodeTest();return 0;}
如果对你有所帮助的话,别忘了一键三连哟,谢谢宝子们😘!
声明
本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。