数据结构线性表
转载于崽🐏的小屋
线性表
数据结构线性表的定义和特点
线性表，从名字上你就能感觉到，是具有像线一样的性质，例如一个班级的小朋友，一个跟着一个排着队，有一个打头，有一个收尾，当中的小朋友每一个都知道他前面一个是谁，他后面一个是谁，这样如同有一根线把他们串联起来了。就可以称之为线性表。
线性表的定义
由$n(n \geq O)$个数据特性相同的元素构成的有限序列称为线性表。
线性表的特点
线性表中元素的个数$n(n \geq O)$定义为线性表的长度，$n=O$时称为空表。
将非空的线性表$(n>O)$记作$(a_1，a_2，a_3，\cdots ，a_n)$
这里的数据元素$a_i(1 \leq i \leq n)$只是个抽象的符号，其具体含义在不同情况下可以不同。
在非空的线性表，有且仅有一个开始结点$a_1$，它没有直接前趋，而仅有一个直接后继$a_2$；
有且仅有一个终端结点$a_n$，它没有直接后继，而仅有一个直接前趋$a_{n-1}$；
其余的内部结点$a_i$，$(2<i<n-1)$都有且仅有一个直接前趋$a_i-1$和一个直接后继$a_i+1$。
线性表的例子
26个英文字母的字母表：(A, B, C, …，Z)；学生信息表；12星座。
同一线性表中的元素必定具有相同的特性，数据元素之间关系是线性的。
案例引入
$P_n(x)=p_0+p_1x+p_2x^2+\cdots+p_nx^n$
逻辑结构抽象为线性表存储结构呢？
线性表 $P=(p_0，p_1，p_2，\cdots，p_n)$，这时，每一项的指数$i$隐含在其系数$p_i$的序号中。
例：$P(x)=10+5x-4x^2+3x^3+2x^4$
| 指数（下标$i$） | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 系数$p[i]$ | 10 | 5 | -4 | 3 | 2 |
一元多项式的运算
$R_n(x)=P_n(x)+Q_m(x)$
线性表$R=(p_0+q_0，p_1+q_1，p_2+q_2，\cdots，p_m+q_m，p_{m+1}，\cdots，p_n)$
例：稀疏多项式的运算：在处理如$S(x)=1+3x^{10000}+2x^{20000}$的多项式时，就要用一个长度为20001的线性表来表示，而表中仅有3个非零元素，此时将会造成存储空间的很大浪费，由此可改变元素设定，对多项式的每一项，可用（系数，指数）唯一确定。
$P_n(x)=p_1x^{e_1}+p_2x^{e_2}+\cdots+p_mx^{e_m}$
若用一个长度为$m$且每个元素有两个数据项（系数项和指数项）的线性表$((p_1，e_1)，(p_2，e_2)，\cdots，(p_m，e_m))$
每一个系数与指数也构成了一个线性表只不过是线性表的每个数据元素有2个数据项
用结构体数组存储，(结构体实现每一项)。
$A(x)=7+3x+9x^8+5x^{17}$
$B(x)=8x+22x^7-9x^8$
$A=((7,0),(3,1),(9,8),(5,17))[4项]$
$B=((8,1),(22,7),(-9,8),)[3项]$
创建一个新的多项式$c$用来存放$a$与$b$和
分别从头遍历比较$a$和$b$的每一项
- 指数相同，对应系数相加，若其和不为零，则在$c$中增加一个新项
- 指数不相同，则将指数较小的项复制到$c$中
- 一个多项式已遍历完毕时，将另一个剩余项依次复制到$c$中即可
和有多少项呢？
最少：指数一样，系数正好互为相反数项数为0，最多指数都不一样项数为元素个数之和。项数不容易确定太大了浪费空间，太小了放不下。
顺序存储结构存在问题：
- 存储空间分配不灵活
- 运算的空间复杂度高
尝试链式存储结构(不需要额外的空间只利用已有的空间)
图书信息管理系统
出版社有一些图书数据保存在一个文本文件book.txt中，为简单起见，在此假设每种图书只包括三部分信息：ISBN（书号）、书名和价格。现要求实现一个图书管理系统，包括以下6个具体功能。
- 查找：根据指定的ISBN（书号）或书名查找相应图书的有关信息，并返回该图书在表中的位置序号。
- 插入：插入一种新的图书信息。
- 删除：删除一种图书信息。
- 修改：根据指定的ISBN（书号），修改该图书的价格。
- 排序：将图书按照价格由低到高进行排序。
- 计数：统计图书表中图书的数量。
逻辑结构：根据图书表的特点将其抽象成一个线性表，每本图书作为线性表中的一个元素
存储结构：
顺序
链式
比较这两种存储结构的优缺点根据实际情况，选择适当的存储结构，实现此存储结构上的基本操作，利用基本操作完成功能。
线性表的类型定义
抽象数据类型线性表的定义
ADT List {
数据对象：D = {$a_i$|$a_i$属于Elemset，($i=1，2，\cdots，n，n\geq0$)}
数据关系：R = {<$a_{i-1}，a_i$>|$a_{i-1}，a_i属于D，(i=2，3，\cdots，n)$}
基本结构：InitList(&L); DestroyList(&L); ListInsert(&L,i,e); ListDelete(&L,i,&e) ;……
} ADT List
InitList(&L) (Initialization List)
- 造作结果：构造一个空的线性表L。
DestroyList(&L)
- 初始条件：线性表L已经存在。
- 操作结果：销毁线性表L。
ClearList(&L)
- 初始条件：线性表L已经存在。
- 操作结果：将线性表L重置为空表。
ListEmpty(L)
- 初始条件：线性表L已经存在。
- 操作结果：若线性表为空表，则返回true；否则返回false。
ListLength(L)
- 初始条件：线性表L已经存在。
- 操作结果：返回线性表L中的数据元素个数。
GetElem(L,i,&e)
- 初始条件：线性表L已经存在，$1 \leq i \leq$ ListLength(L)。
- 操作结果：用$e$返回线性表L中第$i$个数据元素的值。
LocateElem(L,e,compare())
- 初始条件：线性表L已经存在，compare()是数据元素判定函数。
- 操作结果：返回L中第1个与$e$满足compare()的数据元素的位序。这样的数据元素不存在则返回值为0。
PriorElem(L,cur_e,&pre_e)
- 初始条件：线性表L已经存在。
- 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无意义。
NextElem(L,cur_e,&next_e)
- 初始条件：线性表L已经存在。
- 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无意义。
ListInsert(&L,i,e)
初始条件：线性表L已经存在，$1 \leq i \leq$ListLength(L)+1。
操作结果：在L的第$i$个位置之前插入新的数据元素$e$，L的长度加一。
插入元素$e$之前（长度为$n$）：($a_1，a_2，\cdots，a_{i-1}，a_i，\cdots，a_n $)
插入元素$e$之后（长度为$n+1$）:($a_1，a_2，\cdots，a_{i-1}，e，a_i，\cdots，a_n $)
ListDelete(&L,i,&e)
初始条件：线性表L已经存在，$1 \leq i \leq$ListLength(L)+1。
操作结果：删除L的第$i$个数据元素，并用$e$返回其值，L的长度减一。
删除前（长度为$n$）：($a_1，a_2，\cdots，a_{i-1}，a_i，a_{i+1}，\cdots，a_n $)
删除后（长度为$n-1$）：($a_1，a_2，\cdots，a_{i-1}，a_{i+1}，\cdots，a_n $)
ListTraverse(&L,visited())
- 初始条件：线性表L已经存在。
- 操作结果：依次对线性表中每个元素调用visited()。
