初识线性表

由n(n≥0)个数据特性相同的元素构成的有限序列称为线性表。

线性表的特点

线性表中元素的个数n(n≥O)定义为线性表的长度，n=0时称为空表。

将非空的线性表(n>O)记作(a₁，a₂，a₃，…，a_n)

这里的数据元素a_i(1≤i≤n)只是个抽象的符号，其具体含义在不同情况下可以不同。

在非空的线性表，有且仅有一个开始结点a₁,它没有直接前趋，而仅有一个直接后继a₂;

有且仅有一个终端结点a_n,它没有直接后继，而仅有一个直接前趋a_n-1;

其余的内部结点a_i,(2<i<n-1)都有且仅有一个直接前趋a_i-1和一个直接后继a_i+1

线性表的例子、

26个英文字母的字母表：(A, B, C, …，Z)；学生信息表；12星座。

同一线性表中的元素必定具有相同的特性，数据元素之间关系是线性的。

案例引入

逻辑结构抽象为线性表存储结构呢？

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vGJqGNRc-1677728036862)(https://typora01u.oss-cn-beijing.aliyuncs.com/img/8823c906008c1dc04447be453964f97f10d9058b.png@437w_69h_progressive.webp)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TpVMVYVC-1677728036862)(https://typora01u.oss-cn-beijing.aliyuncs.com/img/7e847d9bbf0f3126aa0151016c58e4ceb1f7997b.png@272w_77h_progressive.webp)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TnYQEqDH-1677728036862)(https://typora01u.oss-cn-beijing.aliyuncs.com/img/e40f15560243aaf01e64866cbcea9afa52ef53c9.png@848w_155h_progressive.webp)]

的多项式时，就要用一个长度为20001的线性表来表示，而表中仅有3个非零元素，此时将会造成存储空间的很大浪费，由此可改变元素设定，对多项式的每一项，可用（系数，指数）唯一确定。

每一个系数与指数也构成了一个线性表只不过是线性表的每个数据元素有2个数据项

用 结构体数组存储，(结构体实现每一项。)

多项式加法

• 加法

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最多指数都不一样项数为元素个数之和。项数不容易确定太大了浪费空间，太小了放不下。

顺序存储结构存在问题存储空间分配不灵活；运算的空间复杂度高

尝试链式存储结构(不需要额外的空间只利用已有的空间)

逻辑结构：根据图书表的特点将其抽象成一个线性表，每本图书作为线性表中的一个元素

存储结构：
a.顺序

b.链式

比较这两种存储结构的优缺点根据实际情况，选择适当的存储结构，实现此存储结构上的基本操作，利用基本操作完成功能。当然学生信息管理也是类似的

线性表的类型定义

---

线性表的存储结构

在计算机中线性表有两种存储结构：1. 顺序存储结构 2. 链式存储结构

抽象数据类型线性表的定义如下

ADT List {
数据对象：D = { a_i丨a_i属于Elemset，(i = 1,2,3…)}
数据关系：R = {<a_i-1 , a_i丨a_i-1 , a_i 属于D,(i = 1,2,3…) >}
基本操作：

​ InitList(&L); DestroyList(&L);

​ ListInsert(&L,i,e); ListDelete(&L,i,&e);

​ } ADT List

基本操作（一）init，destory，clear

InitList(&L)

操作结果：构造一个空的线性表L

DestoryList(&L)

初始条件：线性表L已经存在

操作结果：销毁线性表L

ClearList(&L)

初始条件：线性表L已经存在

操作结果：将线性表L重置为空表

基本操作（二） 判空 ，求长

ListEmpty(L)

初始条件：线性表L已经存在

操作结果：若线性表L为空表(n=0)，则返回TURE ，否则返回FALSE

Listlength(L)

初始条件：线性表L已经存在

操作结果：返回线性表L中元素的个数

基本操作（三）取值，取位置

GetElem(L,i,&e)

初始条件：线性表L已经存在，1≤ i ≤ ListLength(L)

操作结果：用e返回线性表L中第i个数据元素的值

LocateElem(L,e,compare())

初始条件：线性表L已经存在，compare()是数据元素判定函数。

操作结果：返回L中第一个与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≤ i ≤ ListLength(L)+1

操作结果：在L的第i个位置==之前==插入新的数据元素e，L的长度+1

基本操作（六） 删除

ListDelete(&L,i,&e)

初识条件：线性表L已经存在，1≤ i ≤ ListLength(L)

操作结果：删除L的第i个元素，并用e返回其值，L的长度-1

ListTraverse(&L,visited())

初识条件：线性表L已经存在

操作结果：依次对线性表中每个元素调用visited()

线性表的顺序存储结构实现

**线性表的顺序表示(又称顺序存储结构或顺序映象) **

顺序存储定义:把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

线性表的第1个数据元素a1的存储位置称为线性表的起始位置或基地址

线性表的顺序存储结构是指用一段地址连续的存储单元依次存储线性表的数据元素。

例如:线性表(1,2,3,4,5,6)

顺序存储结构的寻址公式

数组长度与线性表长度

数组长度，线性表最多可容纳数据元素的个数

线性表长度(length)：当前数据元素个数

一个教室最多容纳50人(数组长度/线性表的最大存储容量)，但现在教室里坐着34(线性表中当前元素个数)个数。

由于顺序表中的元素要求地址连续、依次存放、随机存取、类型相同，高级程序设计语言当中可以用一维数组来实现

一维数组的定义方式：

类型说明符 数组名[常量表达式]

说明：常量表达式中可以包含常量和符号常量(宏命名)，不能包含变量。即C语言中不允许对数组的大小作动态定义。

线性表经常进行插入和删除的操作长度可变而C中数组的长度是不可变的。

用一个额外的变量表示线性表的长度

ElemType是根据实际问题，你需要什么类型的数组就定义成什么，一般是根据问题定义一个结构体或者是 typedef char ElemType

**数组的定义 **

数组名其实就是首元素的地址所以也可以直接定义一个指针。数组的大小用相应的函数来动态分配内存

用结构体变量名.成员变量名对成员访问；指针：SqList *p=&L;p->data=…;

1.malloc()函数是在程序运行时分配内存的重要工具接受一个参数:所需的内存字节数但并不会为其赋名.然而,但他确实返回了动态分配内存块的首地址.因此可以把该地址赋给一个指针变量,并使用指针访问这块内存注意要强制类型转换

(类型说明符*)malloc(size);

如向内存要100个int(类型说明符*)malloc(100*sizeof(int));

2.sizeof(x)计算变量/数据类型x所占据的字节数

3.free§释放指针p所指变量的存储空间，即彻底删除一个变量

需要加载头文件<stdlib.h>

C++内容

定义一个线性表 类型说明 变量名SqList L;

SqList L; 定义变量L ，L是SqList这种类型的，L是个顺序表

基本操作实现

操作中常用的预定义常量与类型

初始化(分配空间；赋初值)

销毁线性表

线性表置空/清空线性表

求表长

判断线性表是否为空

线性表的按值查找算法(在查找的一章还要详细介绍，这里我们先说最简单的顺序查找)

查找算法的算法分析

查找算法的基本操作:将记录的关键字同给定值进行比较(L.elem==e)

比较的次数与输入的定值e有关(假设7个数字出现的概率均为1/7)
当e=a，1次；当e=b，2次；当e=c，3次；…e=g,7次
平均比较次数(1+2+3+…+7)/7=4

在查找时，为确定元素在顺序表中的位置，需和给定值进行比较的数据元素个数的期望值称为查找算法在查找成功时的平均查找长度(AverageSearch Length, ASL)。

插入算法

(在线性表a3位置之前插入一个新元素e(e=6))

插入位置在最后在线性表的最后添加一个元素不需要移动直接添加

插入位置在最前在原线性表的第1个元素之前插入一个新的元素，线性表的所有元素都要移动 移动次数最多

插入位置在中间如上例

删除操作

①判断删除位置i是否合法（合法值为1≤i≤n)

②将欲删除的元素保留在e当中

③将第i+l个至第n个的元素依次向前移动一个位置(i= n时无需移动）

④表长减1

删除算法分析

线性表的小结

查找、插入、删除的平均算法复杂度为O(n)

空间复杂度显然顺序表操作没有占用辅助空间算法的空间复杂度O(1)

线性表的优缺点

优点

存储密度大(结点本身所占用的空间/结点结构所占存储量=1)无需为表示表中元素之间的逻辑关系，而增加额外的存储空间

可以随机存取表中任意位置的元素

缺点

插入、删除某一元素需移动大量元素

当线性表长度变化较大时，难以确定存储空间的容量，数据元素的个数不能自由扩充(存储空间不灵活)