【数据结构】单链表的基本操作及实现

article/2025/10/7 7:30:36

        线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素a_{i}与其直接后继数据元素a_{i+1}之间的逻辑关系，对数据元素a_{i}来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素a_{i}的存储映像，称为节点，它包括两个域，其中存储数据单元信息的域被称为数据域，存储直接后继存储位置的域被称为指针域，指针域中的存储信息乘坐指针或链。n个节点(a_{i}(1<=i<=n)的存储映像)链接成一个链表，即为线性表。

        单链表特点：随机存储，顺序存取。

        下图即为单链表的图示表示，其中蓝色框表示节点的地址，第一个为头指针，它只存储第一个节点的地址。Data为数据域，Next为指针。

        图一       

        我创建的单链表结构体如下所示。注意最后一行注释，这里使用一个LNode表示该结构体，*LinkList表示该结构体的地址

typedef struct LNode {ElemType data;LNode* next;
}LNode, *LinkList;//注意

        本次初始化代码如下所示，当调用初始化方法，在方法体内声明一个LinkList变量，即表示LNode结构体类型的地址（图一中的Head）。我这里没有进行分配失败判断，自己写的时候要注意。分配成功后，将该节点的next属性赋成NULL，即没有直接后继。最后将这个节点返回， 即头结点。

LinkList InitLNode() {LinkList L;L = (LinkList)malloc(sizeof(LNode));L->next = NULL;return L;
}

 代码实现

        下面代码是自己根据自己思路完成，有很多可以优化的地方。特别是单链表的逆置操作。

//线性表的单链表
# include<stdio.h>
# include<stdlib.h>#define ERROR -2
typedef char ElemType;typedef struct LNode {ElemType data;LNode* next;
}LNode, *LinkList;LinkList InitLNode() {LinkList L;L = (LinkList)malloc(sizeof(LNode));L->next = NULL;return L;
}void createLinkList(LinkList L, int num) {int elem = 0;LinkList head = L;printf("请输入元素内容");for (int i = 0; i < num; i++) {L->next = (LNode*)malloc(sizeof(LNode));scanf_s("%d", &elem);L->next->data = elem;L = L->next;}L->next = NULL;L = head;
}
//获取链表长度
int listLength(LinkList L) {LinkList first = L;int length = 0;while (L->next != NULL) {length++;L = L->next;}L = first;return length;
}
//定位某个元素
void LocationElem(LinkList L, ElemType elem) {int i = 0;bool flag = false;LinkList first = L;while (L->next != NULL){i++;if (L->next->data == elem) {flag = true;printf("%d位于第%d位",elem,i);}L = L->next;}L = first;if (!flag) {printf("抱歉，没有该元素");}
}
//通过位置获取元素
void GetElem(LinkList L, int Location) {LNode* first = L;int i = 0;int length = 0;while (L->next != NULL) {length++;L = L->next;}L = first;if (length < Location|| Location<1) {printf("下标不合法\n");L = first;return;}else {while (i < Location) {L = L->next;i++;}printf("第%d位置的元素是%d\n",Location, L->data);L = first;}
}
//插入元素
void InsertList(LinkList L, ElemType elem, int location) {LNode* wait = NULL;//待插入LNodeLNode* wait_next = NULL;LNode* first = L;int i = 0;int length = 0;while (L->next != NULL) {length++;L = L->next;}//获取链表长度L = first;if (location > length + 1 || location < 1) {printf("下标不合法\n");L = first;return;}while (i <= (location - 2)) {L = L->next;i++;}//将L转到插入位置的前面wait_next = L->next;wait = (LNode*)malloc(sizeof(LNode));//分配空间给待插入的LNodewait->data = elem;L->next = wait;//将待插LNode的前一个LNode的next指向待插LNode地址wait->next = wait_next;printf("插入成功\n");L = first;
}void deleteElem(LinkList L, int location) {LNode* first = L;int i = 0;int length = 0;while (L->next != NULL) {length++;L = L->next;}//获取链表长度L = first;if (location > length || location < 1) {printf("下标不合法\n");L = first;return;}while (i < location -1 ) {L = L->next;i++;}L->next = L->next->next;printf("删除成功");L = first;
}
//打印单链表
void print(LinkList L) {LNode* first = L;while (first->next != NULL) {printf("%d ", first->next->data);first = first->next;}
}
//由于传进地址，排序完成后无法恢复原样
void sort(LinkList L) {ElemType temp;LNode* first = L;LNode* flag = L;int i = 0;int length = 0;while (L->next != NULL) {length++;L = L->next;}//获取链表长度L = first;for (int i = 0; i < length-1; i++) {//flag = L;for (int j = 0; j < length - i - 1; j++) {if (L->next->data > L->next->next->data) {temp = L->next->data;L->next->data = L->next->next->data;L->next->next->data = temp;}L = L->next;}//L = flag->next;L=first;}L = first;print(L);
}
//逆置
void Invert(LinkList L) {LNode* first = L;LNode* last = L;ElemType temp;int i = 0;int length = 0;int length_temp;//用来获取后一半的节点while (L->next != NULL) {length++;L = L->next;}//获取链表长度length_temp = length;last = L;//将最后倒数的节点节点赋给last变量L = first;for (i = 0; i < length / 2; i++) {temp = L->next->data;L->next->data = last->data;last->data = temp;//交换完毕L = L->next;last = first;//重新找下一个last节点length_temp--;for (int j = 0;j < length_temp; j++) {last = last->next;}//找到后面的节点}L = first;printf("逆置成功\n");print(L);
}int main() {LinkList L = NULL;int elem;int operate = -1;//操作数int length = 0;//求表长用到int num = 0;//表元素个数int location = 0;//元素下标printf("请输入要进行的操作\n");printf("1---创建单链表\n");printf("2---单链表长度\n");printf("3---求指定元素的位置\n");printf("4---给定下标获取元素\n");printf("5---插入元素\n");printf("6---删除元素\n");printf("7---排序\n");printf("8---逆置单链表\n");printf("11---打印单链表\n");while (operate != 0) {scanf_s("%d", &operate);switch (operate){case 1:printf("请输入元素个数\n");scanf_s("%d", &num);L = InitLNode();createLinkList(L, num);printf("请输入编号进行下一步操作\n");break;case 2:length = listLength(L);printf("单链表的长度是%d\n", length);printf("请输入编号进行下一步操作\n");break;case 3:printf("请输入你想定位的元素\n");scanf_s("%d", &elem);LocationElem(L, elem);printf("请输入编号进行下一步操作\n");break;case 4:printf("请输入元素下标:\n");scanf_s("%d", &location);GetElem(L, location);printf("请输入编号进行下一步操作\n");break;case 5:printf("请输入插入的元素和插入位置:\n");scanf_s("%d %d",&elem, &location);InsertList(L, elem, location);printf("请输入编号进行下一步操作\n");break;case 6:printf("请输入你想删除的元素的位置\n");scanf_s("%d", &location);deleteElem(L, location);printf("请输入编号进行下一步操作\n");break;case 7:sort(L);printf("请输入编号进行下一步操作\n");break;case 8:Invert(L);printf("请输入编号进行下一步操作\n");break;case 11:print(L);printf("请输入编号进行下一步操作\n");break;}}}

  参考：严蔚敏 吴伟民《数据结构（C语言版）》----清华大学出版社


http://chatgpt.dhexx.cn/article/BUeyxw0E.shtml

相关文章

单链表的基本操作C++

单链表的基本操作C++

定义一个结构体结构体里存有数据域以及指针域&#xff0c;Lnode跟Node意思一样只是为了方便而重新起名&#xff0c;Linklist 也就是Node 的意思也是为了方便 typedef struct Node {int data; //数据域Node* next;//指针域 指针域是用来存放下一个节点的}Lnode, * Linklist;…
阅读更多...
数据结构与算法 | 单链表的基本操作

数据结构与算法 | 单链表的基本操作

1024G 嵌入式资源大放送&#xff01;包括但不限于C/C、单片机、Linux等。关注微信公众号【嵌入式大杂烩】&#xff0c;回复1024&#xff0c;即可免费获取&#xff01; 线性表的存储结构有顺序存储结构&#xff08;顺序表&#xff09;和链式存储结构&#xff08;链表&#xff09…
阅读更多...
单链表的基本操作（完整代码）

单链表的基本操作（完整代码）

函数说明&#x1f603;&#xff1a; LinkList List_HeadInsert(LinkList& L)&#xff1a;用头插法建立单链表 LinkList List_TailInsert(LinkList& L)&#xff1a;用尾插法建立单链表 LNode * GetElem(LinkList L, int i):按照序号查找结点值 LNode * LocateElem(Link…
阅读更多...
【链表】单链表的基本操作详解(C语言)

【链表】单链表的基本操作详解(C语言)

本文是单链表的C语言实现方法&#xff0c;包括单链表的创建、插入、删除、修改、查找等基本操作。 链表的底层是通过指针将一个个零散的内存块连接起来&#xff0c;链表的每个内存块称为结点。 单链表结点结构体 单链表的结点上存储数据data和下个结点的地址——后继指针nex…
阅读更多...
单链表的基本操作（详细）

单链表的基本操作（详细）

目录 0.本帖的内容&#xff1a; 1.单链表的定义 2.初始化 3.这个帖子中的功能&#xff08;函数块&#xff09; 4.利用为尾插法创建单链表 5.打印单链表 6.在带有头结点的单链表L中第i个位置之前的插入元素e 7.当第i个元素存在时&#xff0c;把第i个元素赋值给e并返回ok…
阅读更多...
单链表基本操作

单链表基本操作

目录 结构体&#xff0c;这里讨论的都是带头节点的 一、单链表建立 1、头插法&#xff1a;利用头指针控制链表节点的增加 代码&#xff1a; 2、尾插法&#xff1a; 二、遍历 三、插入&#xff1a;&#xff08;pos代表要插入的位置&#xff09; 四、删除 五、销毁 六、…
阅读更多...
单链表的基本操作

单链表的基本操作

文章目录 单链表(含头结点)一、单链表二、单链表的创建(有头结点)三、单链表的结点查找(按位置查找)四、单链表的插入操作五、链表的删除操作六、链表的逆置七、链表的置空八、链表的销毁 单链表(含头结点) 一、单链表 1.1 关于单链表 单链表是一种采用链式存储的线性结构&am…
阅读更多...
单链表的操作（超详细），保证你看完不后悔

单链表的操作（超详细），保证你看完不后悔

&#x1f30d;新人小白的博客 ⌛️希望大家多多关注 &#x1f331;一起加油&#xff0c;共同成长 &#x1f383;以后会经常更新哒~&#x1f648; ⭐️个人主页&#xff1a; 收藏加关注&#xff0c;永远不迷路~⭐️ 数据结构系列&#x1f440; 一&#xff1a;顺序表的操作&…
阅读更多...
C语言单链表实现初始化、创建、增、删、查等基本操作（详细）

C语言单链表实现初始化、创建、增、删、查等基本操作（详细）

C语言单链表实现初始化、创建、增、删、查等基本操作 #include <stdio.h> #include <stdlib.h> #include <malloc.h> typedef int ElemType; //定义单链表结构 typedef struct Node {ElemType data;//数据域struct Node *next;//指针域&#xff0c;指向下一…
阅读更多...
java线程池的工作原理_JAVA线程池原理详解一

java线程池的工作原理_JAVA线程池原理详解一

线程池的优点 1、线程是稀缺资源，使用线程池可以减少创建和销毁线程的次数，每个工作线程都可以重复使用。 2、可以根据系统的承受能力，调整线程池中工作线程的数量，防止因为消耗过多内存导致服务器崩溃。 线程池的创建 1 public ThreadPoolExecutor(int corePoolSize, 2 in…
阅读更多...
线程池原理解析

线程池原理解析

1、为什么要用线程池&#xff0c;线程池的作用&#xff08;意义&#xff09;&#xff0c;如果使用线程池会有什么好处&#xff0c;说说你对线程池的了解&#xff1f; 创建和销毁线程的代价是很大的&#xff0c;线程不像创建普通object对象那样&#xff0c;在堆中分配点内存就好…
阅读更多...
Java 线程池原理及四种常用的线程池使用

Java 线程池原理及四种常用的线程池使用

推荐阅读&#xff1a;Java线程池实现原理及其在美团业务中的实践 文章目录 什么是线程池使用线程池的好处线程池的实现原理流程图分析源码分析 线程池的使用向线程池中提交任务newCachedThreadPoolnewFixedThreadPoolnewScheduledThreadPoolnewSingleThreadExecutor自定义线程池…
阅读更多...
Tomcat线程池监控及线程池原理分析

Tomcat线程池监控及线程池原理分析

目录 一、背景 二、tomcat线程池监控 三、tomcat线程池原理 四、总结 一、背景 我们都知道稳定性、高可用对于一个系统来讲是非常重要的&#xff0c;而为了保证系统的稳定性&#xff0c;我们一般都会进行各方面的监控&#xff0c;以便系统有任何异常情况时&#xff0c;开发人员…
阅读更多...
Python学习：线程池原理及实现

Python学习：线程池原理及实现

传统多线程方案会使用“即时创建&#xff0c; 即时销毁”的策略。尽管与创建进程相比&#xff0c;创建线程的时间已经大大的缩短&#xff0c;但是如果提交给线程的任务是执行时间较短&#xff0c;而且执行次数极其频繁&#xff0c;那么服务器将处于不停的创建线程&#xff0c;销…
阅读更多...
超详细的线程池原理解析

超详细的线程池原理解析

说明 线程池作为常用的并发工具重要性不言而喻&#xff0c;本文针对线程池进行了抽丝剥茧般的深入解析&#xff0c;希望大家看后会有帮助。 1 ThreadPoolExecutor结构关系图 2 参数结构 public ThreadPoolExecutor( int corePoolSize,//核心线程数量int maximumPoolSize,…
阅读更多...
从简单代码入手，分析线程池原理

从简单代码入手，分析线程池原理

一、线程池简介 1、池化思想 在项目工程中&#xff0c;基于池化思想的技术应用很多&#xff0c;例如基于线程池的任务并发执行&#xff0c;中间件服务的连接池配置&#xff0c;通过对共享资源的管理&#xff0c;降低资源的占用消耗&#xff0c;提升效率和服务性能。 池化思想…
阅读更多...
线程池原理与实现

线程池原理与实现

目录 1. 线程池是什么 2. 线程池的优点&#xff1a; 3. 线程池的应用场景 4. 线程池的实现 4.1 线程池实现原理 4.2 线程池基本框架 4.3 结构体&#xff1a; 4.4 提供的接口 4.5 线程池测试代码 5 线程池提高demo thrd_pool.h thrd_pool.c main.c 运行结果 6 re…
阅读更多...
线程池原理——高频面试题

线程池原理——高频面试题

1.高频面试题&#xff1a; 1.为什么使用线程池&#xff0c;优势是什么&#xff1b; 2.线程池如何使用&#xff1b; 3.线程池的几个重要的参数介绍&#xff1b; 4.线程池底层工作原理&#xff1b; 5.线程池用过吗&#xff1f;生产上你如何设置合理参数&#xff1b; 2.线程…
阅读更多...
Android线程池原理详解

Android线程池原理详解

简介 但凡有点开发经验的同学都知道&#xff0c;频繁的创建和销毁线程是会给系统带来比较大的性能开销的。所以线程池就营运而生了。那么使用线程池有什么好处呢&#xff1f; 降低资源消耗 可以重复利用已创建的线程降低线程创建和销毁造成的消耗。提高响应速度 当任务到达时…
阅读更多...
Java面试题之：线程池原理

Java面试题之：线程池原理

Java面试题之&#xff1a;线程池原理 一、简介二、线程复用三、线程池的组成四、拒绝策略五、Java 线程池工作过程 一、简介 线程池做的工作主要是控制运行的线程的数量&#xff0c;处理过程中将任务放入队列&#xff0c;然后在线程创建后启动这些任务&#xff0c;如果线程数量…
阅读更多...
推荐文章

Copyright @ 2022~2023