| 数据结构第二章 |
线性表
2.1线性表的定义与特点
定义：由n（n>=0）个数据特性相同的元素构成的有限序列称为线表。
线性表中元素的个数n(n>=0）定义为线性表的长度，n=0时为空表。
非空线性表或线性结构的特点
存在唯一的一个被称为“第一个”的数据元素；
存在唯一的一个被称为“最后一个”的数据元素；
除第一个之外，结构中的每一个元素均只有一个前驱；
除最后一个之外，结构中的每个数据元素均只有一个后继；
2.8案例分析与实现
一元多项式的运算
稀疏多项式的运算
多项式的创建
多项式的相加
图书信息管理系统
2.2案例引入
案例
1.一元多项式的运算
2.稀疏多项式的运算
3.图书信息管理系统
包含有n个数据特性相同的元素，即可以表示为线性表。不同的问题所涉及元素的数据类型不尽相同，可以为简单的数据类型，也可以为复杂的数据类型
2.7线性表的应用
求一般集合的并集问题
线性表的合并
求有序集合的并集问题
有序表的合并
若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，则称该线性表为有序表
顺序有序表的合并
链式有序表的合并
2.6顺序表和链表的比较
空间性能
存储空间的分配
存储密度的大小
时间性能
存取元素的效率
插入和删除操作的效率
2.3线性表的类型定义
基本操作
IntList(&L)
DestoryList(&L)
ClearList(&L)
ListEmpty(L)
ListLength(L)
GetElem(L,i,&e)
LocateElem(L,e)
PriorElem(L,e)
NextElem(L,cur_e,&pre_e)
ListInsert(&L,i,e)
ListDelete(&L,i)
TraverseList(L)
2.5线性表的链式表示和实现
线性链式表存储结构的特点：用一组任意的存储单元存储线表的数据元素（这组存储单元可以是连接的，也可以是不连接的）
数据元素本身的信息和指示其直接后继的信息组成存储映像，称为结点
结点包含两个域
存储数据元素信息的域称为数据域
存储直接后继存储位置的域称为指针域，指针域中存储的信息称为指针或链
n个结点（ai（1<=i<=n））链接成一个链表，即为线性表（a1，a2，...，an）的链式存储节后，又由于此链表中的每个结点中只包含一个指针域，故又称为线性链表或单链表
一般情况下，为了处理方便，在单链表的第一个结点之前附设一个结点，称为头结点。
作用
1.便于首元节点的处理
2.便于空表和非空表的统一处理
单链表是非随机存取的存储结构，也称为顺序存取的存取结构
单链表的基本操作
初始化
取值
空间复杂度O（n） 平均时间复杂度O（n）
查找
平均时间复杂度O（n）
插入
时间复杂度O（n）
删除
时间复杂度O（n）
创建单链表
前插法
时间复杂度O（n）
后插法
时间复杂度O（n）
循环链表是另一种形式的链式存储结构，其特点是表中最后一个结点的指针域只想头结点，整个链表形成一个环。由此，表中任意一节点出发均可找到表中其他节点
在双向链表的结点中有两个指针域，一个指向直接后继，另一个指向直接前驱
双向链表的插入和删除的时间复杂度均为O（n）
2.4线性表的顺序表示或实现
线性表的顺序表示指的是用一组地址连续的存储单元一次存储线性表的数据元素，这种表示也称作线性表的顺序存储结构或顺序映像。通常，称这种存储结构的线性表为顺序表。
顺序表的特点：逻辑上相邻的数据元素，其物理次序也是相邻的
线性表的顺序存储结构是一种随机存取的存储结构
顺序表中的基本操作
顺序表的初始化
顺序表的取值
时间复杂度：O（1）
顺序表的查找
平均时间复杂度：O（n）
顺序表的插入
平均时间复杂度：O（n）
顺序表的删除
平均时间复杂度：O（n）