清华962数据结构 --- Ch2 线性表
一、线性表
1、线性表的定义
具有相同数据类型的 n(n≥0)个数据元素的有限序列,其中 n 为表长,当 n = 0 时线性表是一个空表
- 元素之间有序
- 除第一个数据元素外,每个元素只有一个直接前驱;除最后一个数据元素外,每个元素只有一个直接后继
- 线性表强调有限,因此像“所有的整数按递增次序排列”这样的论述不是线性表
需要注意:
- 同一线性表中的元素必定具有相同特性(属于同一数据对象),相邻数据元素之间存在序偶关系
- ai是线性表中第 i 个数据元素,称 i 为为数据元素 ai 在线性表中的位序
- 位序从 1 可开始,而数组下标从 0 开始
2、线性表的基本操作
- InitList (&L):初始化表。构造一个空的线性表 L,分配内存空间
- DestroyList (&L):销毁操作。销毁线性表,并释放线性表 L 所占用的内存空间
- ListInsert (&L, i, e):插入操作。在表 L 中的第 i 个位置上插入指定元素 e
- ListDelete (&L, i,&e):删除操作。删除表 L 中第 i 个位置的元素,并用 e 返回删除元素的值
- LocateElem (L, e):按值查找操作。在表 L 中查找具有给定关键字值的元素
- GetElem (L, i):按位查找操作。获取表 L 中第 i 个位置的元素的值
- Length (L):求表长。返回线性表 L 的长度,即 L 中数据元素的个数
- PrintList (L):输出操作。按前后顺序输出线性表 L 的所有元素值
- Empty (L):判空操作。若 L 为空表,则返回 true,否则返回 false
- 引用符号“&”:表示对参数的修改结果需要“带回来”
二、顺序表
定义:线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素
1、顺序表的实现
(1)静态分配
静态分配是指开始时就确定好这个线性表的大小,可以理解为数组
Ps: malloc、free 函数: 动态申请和释放内存空间 L.data = (ElemType ) malloc (sizeof (ElemType) InitSize); Elemype: 强制转型为定义的数据元素类型指针
(2)动态分配
借助 C/C++ 的内存管理,在堆上开辟一块空间,然后用指针指向它,使用指针进行管理
2、顺序表的特点
- 支持随机访问,可以在 O ( 1 ) 时间内找到第 i 个元素
- 存储密度高,每个结点只存储数据元素
- 扩展容量不方便,即便采用动态分配,扩展动态数组长度需将整片数据复制到新区域,时间开销大
- 插入、删除不方便,需要移动大量元素
3、顺序表的操作
(1)顺序表的的插入
插入位置后面的元素要依次让出位置 增加对 i 和合法性的检查
时间复杂度: 最好情况:新元素插入到表尾,不需要移动元素,为 O ( 1 ) 最坏情况:新元素插入到表头,需要 n 那个元素,为 O ( n ) 平均情况:新元素插入到任何一个位置的概率都相同,为 n/2,即 O ( n )
(2)顺序表的删除
删除元素时被删除元素后面的元素向前移动覆盖即可
时间复杂度: 最好情况:删除表尾,不需要移动元素,为 O ( 1 ) 最坏情况:删除表头元素,需要移动 n 元素,为 O ( n ) 平均情况:删除任何一个位置元素的概率都相同,为(n − 1) / 2,即 O ( n )
(3)顺序表的查找
- 按位查找
时间复杂度: 因为顺序表支持随即访问,所以在按位查找的情况下,时间复杂度是 O ( 1 )
- 按值查找
时间复杂度: 最好情况:目标元素在表头,为 O ( 1 ) 最坏情况:目标元素在表尾,需要移动 n 元素为 O ( n ) 平均情况:目标元素出现在任何一个位置的概率,概率都相同,为(n + 1) / 2,即 O ( n )
三、线性表的链式表示
1、定义
每个数据元素除了存储其本身的信息之外,还需要存储一个指示其后继的信息。我们把存储数据元素的域称之为数据域,把存储直接后继位置的域称之为指针域,这两部分共同组成了一个结点,n 个结点链接成一个链表,即为线性表 (a{1}, a{2},..., a_{n}) 的链式存储结构,由于此链表的每个结点只包含一个指针域,因此称之为单链表。
头指针: 链表中第一个结点位置的指针叫做头指针(如果头指针丢失,则链表丢失) 头结点: 在单链表第一个结点之前增加的一个结点成为头结点,他的数据域不设任何信息
二者的区别: 头结点是在链表的第一个结点之前附加一个结点(该结点可以不存储任何信息,也可以存储链表长度等信息),从而使得链表的第一个结点和其他结点在处理问题上的操作保持一致。 头指针是为了标识一个链表而产生的,当链表存在头结点时,则头指针指向头结点,当链表不存在头结点时,头指针指向链表的第一个元素(也可能为空)。
2、链表的特点
- 不要求逻辑上相邻的元素在物理位置上也相邻
- 数据元素之间的逻辑关系是由结点中的指针指示的
优点:空间分配更加方便,改变容量方便 缺点:不可随机读取,存储密度低
3、单链表
(1)初始化
不带头结点
带头结点
(2)单链表的插入
按位插入(带头结点)
按位插入(不带头结点)
指点结点后插
指定结点前插 获取头结点然后再一步步找到指定结点的前驱
将新结点先连上指定结点 p 的后继,接着指定结点 p 连上新结点 s,将 p 中元素复制到 s 中,将 p 中元素覆盖为要插入的元素 e
(3)单链表的删除
按位删除
指定结点删除 传入头指针,循环寻找 p 的前驱结点
(4)单链表的查找
按位查找
按值查找
(5)单链表的建立
头插法 每次插入元素都插入到单链表的表头
尾插法 每次插入元素都插入到单链表的表尾
每次从头开始遍历:
增加一个尾指针 r,每次插入都让 r 指向新的表尾结点:
4、双链表
为什么需要双链表
- 单链表:无法逆序检索
- 双链表:可以双向的检索
定义:
typedef struct DNode
{
DataType data;
struct DNode* prior;//指向前驱结点
struct DNode* next;//指向后继结点
}DNode
(1)双链表的初始化
(2)双链表的插入
s->prior=p
s->next=p->next
p->next->priot=s
p->next=s
(3)双链表的删除
p->prior->next=p->next
p->next->prior=p->prior
5、循环链表
- 表尾结点的 next 指针指向头结点
- 从一个结点出发可以找到其他任何一个结点
(1)循环单链表
尾节点的 next
指针指向头结点
- 从头结点找到尾部,时间复杂度为 O (n)
- 如果需要频繁的访问表头、表尾,可以让 L 指向表尾元素(插入、删除时可能需要修改 L)
- 从尾部找到头部,时间复杂度为 O (1)
(2)循环双链表
尾节点的 next
指针指向头结点,头结点的 prior
指针指向尾节点
判空条件:头结点的 prior 和 next 月域都指向它本身
(3)循环链表的插入
(4)循环链表的删除
6、静态链表
什么是静态链表:
- 分配一整片连续的内存空间,各个结点集中安置
- 每个结点由两部分组成:data(数据元素)和 next(游标)
- 0 号结点充当“头结点”,不具体存放数据
游标为 -1 表示已经到达表尾游标充当“指针”,表示下个结点的存放位置
静态链表中指针指示的是链表中下一元素在数组中的地址
定义静态链表:
7、顺序表与链表的比较
逻辑结构 顺序表和链表都是线性表,都是线性结构
存储结构 顺序表 采用顺序存储的方式实现了线性结构,各数据元素大小相同,各结点只需存储数据元素本身,不需要存储其他额外信息 优点:支持随机存取、存储密度高 缺点:大片连续空间分配、改变容量时不方便
链表 采用链式存储的方式实现了线性结构,各数据元素离散的存储在空间当中 优点:离散的小空间分配、改变容量时方便 缺点:不可随机存取,存储密度低
- 基本操作 (1)初始化 顺序表:需要预分配大片连续空间。如果分配空间过小,则之后不方便拓展容量;如果分配空间过大,则浪费内存资源 链表:只需要分配一个头结点,之后也方便拓展
(2)销毁 顺序表:对于静态分配,由于开辟在栈区,所以由系统自动回收;对于动态分配,由于开辟在堆区,所以需要手动 free 链表:依次 free 结点即可
(3)插入和删除 顺序表:插入和删除需要大量元素的移动,而移动操作代价往往比较大 链表:插入和删除元素只需要修改指针即可。
综上:
表长难以预估、经常要增加/删除元素——链表
表长可预估、查询(搜索)操作较多——顺序表