数据结构与算法(3)-线性表
目录
一.线性表的定义
二.线性表的顺序存储结构
1.顺序存储的定义:
2.顺序存储方式:
3.数组长度与线性表长度的区别
4.地址计算方法
三.顺序存储结构的插入与删除
1.获得元素操作
2.插入操作
3.数组长度与线性表长度的区别
4.线性表顺序存储的优缺点
四.线性表的链式存储结构
1.线性表链式存储结构定义:
2.头指针与头节点的异同
五.单链表的读取
六.单链表的插入与删除
1.单链表的插入:
2.单链表的删除:
七.单链表的整表创建
1.创建单链表的过程就是一个动态生成链表的过程
2.单链表整表创建的算法思路:
八.单链表的整表删除
1.单链表整表删除的算法思路如下:
九.单链表结构与顺序存储结构优缺点
十.静态链表
2.静态链表的优缺点
十一.循环链表
十二.双向链表
一.线性表的定义
1.线性表是零个或多个具有相同类型的数据元素的有限序列
2.线性表的关键:
(1)首先线性表是一个序列,元素之间是有顺序的
(2)然后,线性表强调是有限的
二.线性表的顺序存储结构
1.顺序存储的定义:
线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素
2.顺序存储方式:
(1)描述顺序存储结构需要三个属性:
- 存储空间的起始位置:数组data,它的存储位置就是存储空间的存储位置
- 线性表的最大存储容量:数组长度MaxSize
- 线性表的当前长度:length
3.数组长度与线性表长度的区别
(1)数组的长度是存放线性表的存储空间的长度,存储分配后这个量一般是不变的
(2)线性表的长度是线性表中数据元素的个数,随着线性表插入和删除操作的进行,这个量是变化的
(3)线性表的长度应该小于等于数组的长度
4.地址计算方法
三.顺序存储结构的插入与删除
1.获得元素操作
2.插入操作
(1)插入算法的思路:
- 如果插入位置不合理,抛出异常;
- 如果线性表长度大于等于数组长度,则抛出异常或动态增加容量;
- 从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移动一个位置;
- 将要插入元素填入位置i处,表长加1
3.删除操作
(1)删除算法的思路:
- 如果删除位置不合理,抛出异常;
- 取出删除元素;
- 从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置;
- 表长减1
4.线性表顺序存储的优缺点
(1)线性表的顺序存储结构,在存、读数据时,不管是哪个位置,时间复杂度都是O(1);而插入或删除时,时间复杂度都是O(n)
四.线性表的链式存储结构
1.线性表链式存储结构定义:
(1)线性表的链式存储结构的特点:
是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。这就意味着,这些数据元素可以存在内存未被占用的任意位置
(2)链表的每个结点中只包含一个指针域,所以叫做单链表
(3)链表中第一个结点的存储位置叫做头指针
(4)线性链表的最后一个结点指针为“空”
2.头指针与头节点的异同
五.单链表的读取
(1).获得链表第i个数据的算法思路:
- 声明一个指针p指向链表第一个结点,初始化j从1开始;
- 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1;
- 若到链表末尾p为空,则说明第i个结点不存在;
- 否则查找成功,返回结点p的数据
六.单链表的插入与删除
1.单链表的插入:
(1)单链表第i个数据插入结点的算法思路:
- 声明一指针p指向链表头结点,初始化j从1开始;
- 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1;
- 若到链表末尾p为空,则说明第i个结点不存在;
- 否则查找成功,在系统中生成一个空结点s;
- 将数据元素e赋值给s->data;
- 单链表的插入标准语句s->next=p->next;p->next=s;
- 返回成功
2.单链表的删除:
(1)单链表第i个数据删除结点的算法思路:
- 声明一指针p指向链表头结点,初始化j从1开始;
- 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一个结点,j累加1;
- 若到链表末尾p为空,则说明第i个结点不存在;
- 否则查找成功,将欲删除的结点p->next赋值给q;
- 单链表的删除标准语句p->next=q->next;
- 将q结点中的数据赋值给e,作为返回;
- 释放q结点;
- 返回成功
七.单链表的整表创建
1.创建单链表的过程就是一个动态生成链表的过程
2.单链表整表创建的算法思路:
(1).声明一指针p和计数器变量i;
(2).初始化一空链表L;
(3).让L的头结点的指针指向NULL,即建立一个带头结点的单链表;
(4).循环:
- 生成一新结点赋值给p;
- 随机生成一数字赋值给p的数据域p->data;
- 将p插入到头结点与前一新结点之间
八.单链表的整表删除
1.单链表整表删除的算法思路如下:
(1).声明一指针p和q;
(2).将第一个结点赋值给p;
(3).循环:
- 将下一结点赋值给q;
- 释放p;
- 将q赋值给p