学习
实践
活动
专区
工具
TVP
写文章

C/C+编程笔记:数据结构难点之单链表!一篇文章带你突破难点

数据结构之单链表

单链表是一种链式存取的数据结构,用一组地址任意的存储单元 存放线性表中的数据元素 。链表中的数据是以结点来表示的,每个结点的构成:元素( 数据元素 的映象) + 指针 (指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。

介绍:单链表就是结构体变量和结构体变量 通过指针成员连接在一起,故:单链表就是多个结构体变量。

链表分类

根据链表有无头结点,指针是是否双向,链表是否环状,我们把链表分为以下几种:

带头结点单链表。

无头结点单链表。

双向链表。

双向循环链表。

单链表操作

带头结点的链式结构主要有以下常规操作:

创建链表:创建头结点。

创建结点:为插入做准备。

表头插入。

表尾插入。

指定位置插入。

表头删除。

表尾删除。

指定位置删除。

链表的打印。

插曲:指针如何当做变量使用?

通过赋值变量的地址。

通过动态内存申请。

代码如下:

结构体定义

数据结构中的结构体设计, 一般都是单一个体的抽象,即把整个结构拆开的零件。

创建表头

单链表就是结构体变量和结构体变量 通过指针成员连接在一起,故如果定义一个函数去创建链表,其实就是创建表头,表头也是一个结构体变量,故就是创建结构体变量的过程,然后数据结构一般习惯用指针去表示,指针变成变量,故通过动态内存是申请即可变成变量,最后只需要给变量初始化即可。

单链表的创建表头源码:

创建节点

创建结点单独用一个函数封装,为插入节点做准备,结点也是结构体变量,相对于表头只是多了一个数据域,而数据可以形参传进去,这样就可以实现数据加工,加工为一个结点数据。

单链表的结点创建代码:

表头法插入

因为是一个有表头的链表,故表头位置不可改变,插入结点只能放在表头后面。表头就像讲台,学生座位怎么排,都只能放在讲台后面,不能排到讲台前面去。

单链表的表头插入代码:

表尾插入

表尾插入,首先找到表尾,然后把插入的结点放到表尾结点后面即可。

单链表的表尾插入代码:

指定位置插入

只要找到指定位置与指定位置前面哪个结点,我想每一个同学都应该会插入结点。指定位置插入问题转换为找到指定位置以及指定位置的前面哪个结点。

单链表的指定位置插入代码实现:

链表遍历

因为做的是一个有表头的链表 ,故打印数据的时候是从第二个节点开始打印,如果存在数据,打印数据,打印完后往下一个结点移动即可。就像公交车一样,过一站下一批乘客。

单链表的遍历实现:

测试检验

首先表头插入数据1,在表头插入数据3 ,链表中数据为 3 1。

在指定1前面插入2,链表中数据为3 2 1。

最后表尾插入0,链表中数据为3 2 1 0。

故打印结果是3 2 1 0

希望对你有帮助~

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20200927A0FYPW00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

关注

腾讯云开发者公众号
10元无门槛代金券
洞察腾讯核心技术
剖析业界实践案例
腾讯云开发者公众号二维码

扫码关注腾讯云开发者

领取腾讯云代金券