文档介绍：该【数据结构 第2章 线性表 】是由【相惜】上传分享，文档一共【40】页，该文档可以免费在线阅读，需要了解更多关于【数据结构 第2章 线性表 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构与算法
第三讲:线性表(二)
内容提要
线性表的顺序存储结构回顾
单链表
循环链表
双向链表
静态链表
2023/2/7
2
线性表的顺序存储结构回顾(1)
a1
0
a2
1
……
ai-1
i-2
ai
i-1
……
an
i-1
空闲空间
下标:
数组的长度MAXSIZE
线性表的当前长度length(=n)
data
即
LOC(a1)
//线性表顺序存储的结构代码
#defineMAXSIZE20
typedefintElemType;
typedefstruct
{
ElemTypedata[MAXSIZE];
intlength;
}SqList;
三个属性:
存储空间的起始地址:data
线性表的最大存储容量:MAXSIZE
线性表的当前长度:length
c
(i-1)*c
LOC(ai)
存储位置地址计算公式:
LOC(ai)=LOC(a1)+(i-1)*c
其中c为每个数据元素占用的字节长度
2023/2/7
3
线性表的顺序存储结构回顾(2)
//插入算法的思路(参数:线性表L,插入位置i,插入元素e)
如果插入位置i不合理,提示异常;
如果线性表长度大于等于数组长度MAXSIZE,提示异常或动态增加容量;
从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移动一个位置;
将要插入元素e填入位置i处;
表长加1。
A
B
C
D
E
F
G
H
空闲空间
A
B
C
D
E
F
G
H
空闲空间
插入前:
插入后:
2023/2/7
4
线性表的顺序存储结构回顾(3)
//删除算法的思路(参数:线性表L,删除位置i,用来存放被删除元素的变量e)
如果删除位置i不合理,提示异常;
取出删除元素,存放在e中;
从删除位置i开始遍历到最后一个元素位置,分别将他们都向前移动一个位置;
表长减1。
删除前:
删除后:
A
B
C
D
E
F
G
H
空闲空间
A
B
C
D
E
F
G
H
空闲空间
2023/2/7
5
实验1:顺序存储结构线性表
FTP地址:
用户:zheng_stu
密码:123456
目录:/student/数据结构/实验1
文件:
任务:在程序中标有/*ADDYOURCODEHERE*/的地方加入自己的代码使程序功能完整,且能够正确运行。
2023/2/7
6
线性表顺序存储结构的优缺点
2023/2/7
7
顺序存储结构不足的解决办法
思路(链式存储):
元素可以散落在任何位置,不必相邻
让每个元素知道它的下一个元素在哪里
我们只需要知道第一个元素的位置
插入删除不再需要移动元素而是需要修改元素间的关系
1
2
3
4
5
6
2
3
4
5
6
1
2023/2/7
8
线性表链式结构的存储示意
假设我们有一个线性表(a1,a2,…,an)
ai
0500
ai+1
……
……
……
0800
地址0500
数据信息
结点
指针
数据域
指针域
a1
0700
an
……
……
……
NULL
第一个结点
地址0900
……
0900
头指针
指针指向空
最后一个结点
图a:链表中的相邻元素
图b:一个完整的链表
【注意】有没有不大协调的地方?
2023/2/7
9
头结点与头指针
a1
0700
an
……
……
……
NULL
第一个结点
地址0900
……
0900
头指针
指针指向空
最后一个结点
……
0500
可存线性表长度等公共数据,地址0500
头结点
图c:一个带头结点的完整链表
【注意】接下去的讨论都基于带头结点的链表
2023/2/7
10