当前位置： 首页 > news >正文

无头单向非循环单链表、带头双向循环链表

news 2025/6/30 13:19:55

文章内容

1. 链表的概念及结构

2. 链表的分类

3.链表实现

4.代码

文章目录

1. 链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表
中的指针链接次序实现的 。

 

 现实中 数据结构中

 链表和顺序表的区别

 

2. 链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

 2.1单向或者双向

 2.2 带头或者不带头

 2.3循环或者非循环

 虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

 1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。


2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都
是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带
来很多优势，实现反而简单了，后面我们代码实现了就知道了。

3.链表实现

3.1无头单向非循环单链表
1.主要功能

 2.接口实现

 

 

 

 

 

 

 

 

 

 

 

 

 以上就是链表每个接口的实现了！！！！

3.2带头双向循环链表
1.主要功能

在理解单链表的基础上，理解带头双向循环链表就简单很多了；

2.接口实现

 

 

 

 

 

 

 

 

 

 

 4.代码

 1.单链表
#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLDataType;
typedef struct SListNode
{SLDataType data;struct SListNode* next;
}SLTNode;//打印链表
void SLTPrint(SLTNode* phead);//创建一个新节点
SLTNode* BuySListNode(SLDataType x);//尾插
void SLTPushBack(SLTNode** pphead, SLDataType x);//头插
void SLTPushFront(SLTNode** pphead, SLDataType x);//尾删
void SLTPopBack(SLTNode** pphead);//头删
void SLTPopFront(SLTNode** pphead);//寻找
SLTNode* SLTFind(SLTNode* phead, SLDataType x);// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x);// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLDataType x);// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);// 删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);//销毁链表
void SLTDestroy(SLTNode** pphead);
#define _CRT_SECURE_NO_WARNINGS 1#include "SList.h"//打印链表
void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}//创建一个新节点
SLTNode* BuySListNode(SLDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("BuySListNode fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}//尾插
void SLTPushBack(SLTNode** pphead, SLDataType x)
{SLTNode* newnode = BuySListNode(x);if (*pphead == NULL){//改变指向结构体的指针，所以要用二级指针*pphead = newnode;}else{SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}//改变结构体，用结构体指针tail->next = newnode;}
}//头插
void SLTPushFront(SLTNode** pphead, SLDataType x)
{SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;}//尾删
void SLTPopBack(SLTNode** pphead)
{//空assert(*pphead);//一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//一个以上节点SLTNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}//头删
void SLTPopFront(SLTNode** pphead)
{//kongassert(*pphead);//非空SLTNode* newnode = (*pphead)->next;free(*pphead);*pphead = newnode;}//寻找
SLTNode* SLTFind(SLTNode* phead, SLDataType x)
{assert(phead);while (phead){if (phead->data == x){return phead;}phead = phead->next;}return NULL;
}// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{assert(pphead);assert(pos);//头插if (*pphead == pos){SLTPushFront(pphead,x);return;}SLTNode* prev = *pphead;SLTNode* newnode = BuySListNode(x);while(prev){if (prev->next == pos){prev->next = newnode;newnode->next = pos;return;}else{prev = prev->next;}}
}// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLDataType x)
{assert(pos);SLTNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;}//SLTNode*  posafter = pos->next;
//pos->next = newnode;
//newnode->next = posafter;// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(*pphead);assert(pos);if (*pphead == pos){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}}// 删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{assert(pos);//检查尾节点assert(pos->next);SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}//销毁链表
void SLTDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* cur = *pphead;while (cur){SLTNode* next = cur;next = cur->next;free(cur);cur = next;}*pphead = NULL;
}

 

2.双向链表
#pragma once#include <stdio.h>
#include <assert.h>
#include <stdlib.h>typedef int LTDataTpye;typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataTpye data;}LTNode;//创建新节点
LTNode* BuyLTnode(LTDataTpye x);//初始化
LTNode* LTInit();//打印链表
void LTPrint(LTNode* phead);//头插
void LTPushFront(LTNode* phead, LTDataTpye x);//头删
void LTPopFront(LTNode* phead);//尾插
void LTPushBack(LTNode* phead, LTDataTpye x);//尾删
void LTPopBack(LTNode* phead);//寻找
LTNode* LTFind(LTNode* phead, LTDataTpye x);//在pos之前插入
void LTInsert(LTNode* pos, LTDataTpye x);//消除pos位置的元素
void LTErase(LTNode* pos);//销毁链表
void LTDestroy(LTNode* phead);
#define _CRT_SECURE_NO_WARNINGS 1
#include "DList.h"//创建新节点
LTNode* BuyLTnode(LTDataTpye x)
{LTNode* node = (LTNode *)malloc(sizeof(LTNode));if (node == NULL){perror("BuyLTNode");exit(-1);}node->data = x;node->prev = NULL;node->next= NULL;return node;
}//初始化
LTNode* LTInit()
{LTNode* phead = BuyLTnode(0);phead->next = phead;phead->prev = phead;return phead;
}//打印链表
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 LTPushFront(LTNode* phead, LTDataTpye x)
{assert(phead);LTNode* newnode = BuyLTnode( x);LTNode* after = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = after;after->prev = newnode;}//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* first = phead->next;LTNode* second = first->next;free(first);phead->next = second;second->prev = phead;}//尾插
void LTPushBack(LTNode* phead, LTDataTpye x)
{assert(phead);LTNode* newnode = BuyLTnode(x);LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* tail = phead->prev;LTNode* first = tail->prev;free(tail);first->next = phead;phead->prev = first;}//寻找
LTNode* LTFind(LTNode* phead, LTDataTpye 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, LTDataTpye x)
{assert(pos);LTNode* first = pos->prev;LTNode* newnode = BuyLTnode(x);first->next = newnode;newnode->prev = first;pos->prev = newnode;newnode->next = pos;}//消除pos位置的元素
void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev = pos->prev;LTNode* posafter = pos->next;free(pos);posprev->next = posafter;posafter->prev = posprev;}//销毁链表
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != (phead)){LTNode* cur1 = cur;cur = cur->next;free(cur1);}free(phead);phead == NULL;}

http://www.lryc.cn/news/107214.html

相关文章：

  • UE4/5C++多线程插件制作（二十、源码）
  • 构建稳健的PostgreSQL数据库：备份、恢复与灾难恢复策略
  • 查看本地mysql账号密码
  • 数据结构：顺序表详解
  • 采集数据筛选-过滤不要数据或只保留指定数据
  • RISC-V基础指令之shift移动指令slli、srli、srai、sll、srl、sra
  • 【沁恒蓝牙mesh】CH58x flash分区与数据存储管理
  • Ctfshow web入门 JWT篇 web345-web350 详细题解 全
  • 2023年国家留学基金委（CSC）青年骨干教师项目即将开始申报
  • GC垃圾回收器【入门笔记】
  • 在 React 中渲染大型数据集的 3 种方法
  • uniapp iOS 消息推送扩展：后台/杀死app进程状态能语音播报
  • 批量创建可配置物料参数文件
  • 性能压力测试的重要性与实施方法
  • HCIP入门静态实验
  • Vue与js的融合，如何编写现代化的前端应用
  • Boost开发指南-3.10singleton_pool
  • 腾讯云从业者认证考试考点——云网络产品
  • Miniled透明屏：超薄、轻便，还有哪些特点？
  • MySQL 极速安装使用与卸载
  • 举个栗子！Tableau 技巧（256）：灵活折叠文本表的多级数据行
  • Android View 初始化完成后，如果再调用measure再设置点击事件则点击事件会失效的解决方案
  • 客户端电脑使用 FTP的Cadence_CIS库方法说明 （下）
  • 【ES】笔记-let 声明及其特性
  • wps 预加载项插件本地开发启动项目打开wps 客户端，未看到加载项菜单，
  • uni-app开发微信小程序经常遇到的一些问题及解决方案
  • 一个 git 仓库下拥有多个项目的 git hooks 配置方案
  • 钉钉对接打通金蝶云星空获取流程实例列表详情（宜搭）接口与其他应收单接口
  • 用python做一个小项目,python做简单小项目
  • 输入筛选框搜索