【线性表】(List)
程序员文章站
2022-07-10 21:09:43
...
本文围绕以下三个部分展开:
一、线性表(List)
二、顺序存储结构
三、链式存储结构
一、线性表(List)
1. 概念
线性表:0个或多个数据元素的有限序列。(像线一样性质的表)
线性表的每个数据元素的类型都是相同的。
A. 是一个序列。(元素之间是有顺序的,若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他每个元素都有且只有一个前驱和后继。)
B. 元素个数是有限的。
类比:幼儿园小朋友按次序排队。
2. 线性表的抽象数据类型
(1)基本操作:
抽象数据类型定义如下:
(2)复杂的个性化操作
例题:union操作(实现两个线性表集合A和B的并集操作)
思想:把存在在集合B中但不存在在A中的数据元素插入到A中即可。即:循环集合B中的每个元素,判断当前元素是否存在A中。若不存在,则插入到A中即可。
二、顺序存储结构
1. 顺序存储
指用一段地址连续的存储单元依次存储线性表的数据元素。
2. 顺序存储方式
在内存中找了块地儿,通过占位符的形式,把一定内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空地中。
使用一维数组来实现顺序存储结构。即:把第一个数据元素存到数组下标为0的位置中,接着把线性表相邻的元素存储在数组中相邻的位置。
3. 顺序存储结构代码和三个属性
4. 地址计算方法
存储器中每个存储单元都有自己的编号,称为地址。
(1)数据元素的序号和存放它的数组下标之间的对应关系:
(2)假设一个数据元素占c个存储单元,则第i+1个数据元素的存储位置和第i个数据元素的存储位置的关系:
第i个数据元素的存储位置和第1个数据元素的存储位置的关系:
(3)随机存取结构:可以随时算出线性表中任意位置的地址,存取时间复杂度均为O(1),具有这样特点的存取结构称为随机存取结构。
5. 获得元素的操作(GetElem):将线性表L中第i个位置元素值返回。
6. 插入某个数据元素
7. 删除某个数据元素
8. 优缺点
三、链式存储结构
1. 特点:
用一组任意的存储单元存储线性表的数据元素。这组存储单元可以连续,也可以不连续。意味着,这些数据元素可以存放在内存中未被占用的任意位置。
2. 数据域、指针域、指针/链、结点
3. 头结点、头指针
(1)头指针:链表中第一个结点的存储位置。
链表最后一个结点的指针为空(NULL/"^")
(2)头结点:为了更方便地对链表进行操作,在单链表的第一个结点前附设的一个结点。
数据域可以不存储任何信息,也可以存储如线性表长度等附加信息。
指针域存储指向第一个结点的指针。
(3)二者的异同
4. 分类
链式存储结构又有不同形式,分为:单链表、静态链表、循环链表和双向链表。
整理时重点参考:《大话数据结构》程杰著
一、线性表(List)
二、顺序存储结构
三、链式存储结构
一、线性表(List)
1. 概念
线性表:0个或多个数据元素的有限序列。(像线一样性质的表)
线性表的每个数据元素的类型都是相同的。
A. 是一个序列。(元素之间是有顺序的,若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他每个元素都有且只有一个前驱和后继。)
B. 元素个数是有限的。
类比:幼儿园小朋友按次序排队。
2. 线性表的抽象数据类型
(1)基本操作:
抽象数据类型定义如下:
(2)复杂的个性化操作
例题:union操作(实现两个线性表集合A和B的并集操作)
思想:把存在在集合B中但不存在在A中的数据元素插入到A中即可。即:循环集合B中的每个元素,判断当前元素是否存在A中。若不存在,则插入到A中即可。
二、顺序存储结构
1. 顺序存储
指用一段地址连续的存储单元依次存储线性表的数据元素。
2. 顺序存储方式
在内存中找了块地儿,通过占位符的形式,把一定内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空地中。
使用一维数组来实现顺序存储结构。即:把第一个数据元素存到数组下标为0的位置中,接着把线性表相邻的元素存储在数组中相邻的位置。
3. 顺序存储结构代码和三个属性
4. 地址计算方法
存储器中每个存储单元都有自己的编号,称为地址。
(1)数据元素的序号和存放它的数组下标之间的对应关系:
(2)假设一个数据元素占c个存储单元,则第i+1个数据元素的存储位置和第i个数据元素的存储位置的关系:
第i个数据元素的存储位置和第1个数据元素的存储位置的关系:
(3)随机存取结构:可以随时算出线性表中任意位置的地址,存取时间复杂度均为O(1),具有这样特点的存取结构称为随机存取结构。
5. 获得元素的操作(GetElem):将线性表L中第i个位置元素值返回。
6. 插入某个数据元素
7. 删除某个数据元素
8. 优缺点
三、链式存储结构
1. 特点:
用一组任意的存储单元存储线性表的数据元素。这组存储单元可以连续,也可以不连续。意味着,这些数据元素可以存放在内存中未被占用的任意位置。
2. 数据域、指针域、指针/链、结点
3. 头结点、头指针
(1)头指针:链表中第一个结点的存储位置。
链表最后一个结点的指针为空(NULL/"^")
(2)头结点:为了更方便地对链表进行操作,在单链表的第一个结点前附设的一个结点。
数据域可以不存储任何信息,也可以存储如线性表长度等附加信息。
指针域存储指向第一个结点的指针。
(3)二者的异同
4. 分类
链式存储结构又有不同形式,分为:单链表、静态链表、循环链表和双向链表。
整理时重点参考:《大话数据结构》程杰著
上一篇: php数据类型-浮点型(float)
推荐阅读