前言

线性结构的基本特点是除了第一个元素无直接前驱,最后一个元素无直接后续之外,其他每个数据元素都有一个前驱和后继. 线性表是最基本且最常用的一种线性结构,同时它也是其他的数据结构的基础. 尤其是单链表是贯穿于整个数据结构课程的基本技术点.

一. 线性表的定义和特点

在我们生活中有那些线性表的例子了?
例如,26个字母表; 例如学生基本信息表.每个学生为一个数据元素,包含学号,姓名,专业等数据项目.
满足数据元素不同,但是在同一个线性表中的元素必定具有相同的特点,即属于同一数据对象, 相邻数据元素之间存在这个序偶关系. 诸如此类由(n>=0)个数据特性相同的元素构成的有限序列称为"线性表".
线性表中的元素的个数n定义为线性表的长度,如果n = 0则称为空表.

对于非空的线性表和线性结构,其特点如下:

存在唯一的一个被称作"第一个"的数据元素
存在唯一的一个呗称作"最后一个"的数据元素
除了第一个之外,结构中的每个数据元素均有一个前驱
除了最后一个之外,结构中的每个数据元素都有一个后继.

1.2 线性表的类型定义

线性表是一个相当灵活的数据结构,其长度可根据需要增长或缩短,即对线性表的数据元素不仅可以进行访问,而且可以对其进行插入和删除等操作.

---

线性表结构体设计

image.png

1.线性表的顺序存储

2.线性表->单链表节点

结构

数据域+指针域

---

3.线性表->单向循环链表

image.png

与单向链表区别之处在于单向链表的最后的结点的指针域 next 是设置为null. 但是单向循环链表最后一个结点是重新指向它的第一个首元结点的位置;

3.1单向链表的创建 (采用尾插法)

在实现单向链表的创建时,需要考虑.你进行创建新增结点时的2种情况

第一种情况: 第一次创建; 第二种情况: 链表已经创建成功,并且已经存储了相应的结点. 需要在链表的末尾继续新增数据;

3.2单向循环链表插入数据

在往一个单向循环链表中插入数据,需要提前分析2种情况.

第一种情况,则是插入的位置在首元结点上;

情况1

判断输入的位置是否是place = 1;
创建新的结点temp,并且做出合理的健壮性判断;以及赋值
将新创建的结点temp 的next 指向原始的首元结点A的位置
通过循环找到链表最后一个尾结点,将尾结点的next 指针域指向 新创建的结点temp.
由于链表的首元结点,通过插入发生了改变,所以此时将*L指向新的首元结点temp

第二种情况,插入其他位置(包括链表中间/末尾);

情况2
判断输入的位置是否是place = 1;
创建新的结点temp,并且做出合理的健壮性判断;以及赋值;
通过循环找到待插入的位置前一个结点p ;
将新创建的结点 temp指向p->next;
将待插入结点的前一个结点 P 与新结点 temp之间连接起来;

3.3单向循环链表的删除

在实现单向链表的创建时,需要考虑.你进行创建新增结点时的3种情况

第一种情况: 删除的位置在首元结点上;
第二种情况: 删除时,当链表只剩下最后一个结点时;
第三种情况: 删除其他位置上的结点;

4.线性表->双向链表
5.线性表->双向链表