线性表1
一、线性表的定义和特点
线性表是具有相同特性的数据元素的一个有限序列 （a1,a2,a3,…,an)
(https://gitee.com/little-xh/beginner/raw/master/typora/image-20211012200604729.png)]
定义：
线性表：由n(n>=0)个数据元素(结点)a1, a2, … , an组成的有限序列。
- 数据元素的个数n定义为表的长度
- 当n=0时称为空表
- 非空的线性表(n>0)记作：(a1, a2, … an)
线性表的例子
例1：分析26个英文字母组成的英文表 （A, B, C, D, … ,Z）
? 数据元素都是字母； 元素间关系是线性关系
例2：分析学生登记表
? 数据元素都是一条条的学生记录； 元素间关系是线性关系
例3：某单位历年拥有计算机的数量（6, 17, 28, 50, 92, 188）
? 数据元素都是整数； 元素间关系是线性的
线性表的逻辑特征：
同一线性表中的元素必定具有相同特性，数据元素间的关系是线性关系
第一个元素只有直接后继，最后一个元素只有一个直接前趋，其余元素有且仅有一个直接前趋和一个直接后继
二、案例引入
案例1：一元多项式的运算
一元多项式的运算：实现两个多项式加、减、乘运算
Pn(x) = p0 + p1x + p2x2 + … + pnxn
线性表 P = (p0, p1, p2, p3, … , pn) （x的指数和pi 的序号相同）
可用数组来表示
稀疏多项式 S(x) = 1 + 3x10000 + 2x20000
只存三项数据
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wL1SViZf-1638540067057)(https://gitee.com/little-xh/beginner/raw/master/typora/image-20211012204907915.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Ic0LdKR1-1638540067059)(https://gitee.com/little-xh/beginner/raw/master/typora/image-20211012210225230.png)]
顺序存储结构存在的问题：
? 存储空间分配不灵活，分配的空间是固定大小，有时会不够，有时会浪费
? 运算的空间复杂度高，还用了新数组C
链式存储结构
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iIeJP7sW-1638540067060)(https://gitee.com/little-xh/beginner/raw/master/typora/image-20211012212406493.png)]
三、线性表的类型定义
抽象数据类型定义格式：
ADT 抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<数据关系的定义>
}ADT 抽象数据类型名
线性表的抽象数据类型定义：
基本操作：
①InitList(&L) 线性表初始化
操作结果：构造一个空的线性表L
②DestroyList(&L) 销毁线性表
初始条件：线性表L已存在
操作结果：销毁线性表L
③ClearList(&L) 清空线性表
初始条件：线性表L已存在
操作结果：将L重置为空表，填0
④ListEmpty(L) 判断线性表L是否为空表
初始条件：线性表L已存在
操作结果：若L为空表（元素个数n=0），则返回true，否则返回false
⑤ListLength(L) 求线性表的长度n
初始条件：线性表L已存在
操作结果：返回线性表L中的数据元素个数
⑥GetElem(L, i, &e) 获取元素
初始条件：线性表L已存在， 且1<=i<=ListLength(L)
操作结果：用e返回线性表L中第i个数据元素的值
注意：线性表是从a1开始，不是a0
⑦LocateElem(L, e, compare()) 查找定位元素
初始条件：线性表L已存在，compare()是数据元素判定函数（相等、小于、大于…）
操作结果：返回L中第1个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回0
⑧PriorElem(L, cur_e, &pre_e) 获得当前元素cur_e的前趋
初始条件：线性表L已经存在
操作结果：若cur_e是L的数据元素，且不是第一个，则pre_e返回其其前趋，否则操作失败，pre_e无意义
⑨NextElem(L, cur_e, &next_e) 获得当前元素cur_e的后继
初始条件：线性表L已经存在
操作结果：若当前元素cur_e是L的数据元素，且不是最后一个，则用next_e返回其后继，否则操作失败，next_e无意义
⑩ListInsert(&L,i,e) 插入元素e
初始条件：线性表L已存在，且1<=i<=ListLength(L)+1（插在最后一个元素的后面）
操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
?ListDelete(&L, i) 删除元素
初始条件：线性表L已存在且非空，且1<=i<=ListLength(L)
操作结果：删除L的第i个数据元素，L的长度减1
?ListTraverse(&L, visited()) (traverse：遍历)
初始条件：线性表L已存在
操作结果：依次对线性表L中的每个元素调用visited()
四、线性表的顺序表示和实现1
在计算机内，线性表有两种基本的存储结构：顺序存储结构和链式存储结构
线性表的顺序表又称为顺序存储结构或顺序映像
1、顺序存储定义：
顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构
逻辑上相邻，物理上也相邻
基地址(起始位置)：线性表的第一个数据元素a1的存储位置
2、顺序存储结构：
例如：线性表(1，2，3，4，5，6)的存储结构：
依次存储，地址连续，中间没有空出存储单元，（占用一片连续的存储空间）是一个典型的线性表顺序存储结构
3、顺序表中元素存储位置的计算：
知道首地址和每个元素占的内存单元数 即可计算每个元素的存储位置
任一元素均可随机存取(优点) 存和取
4、顺序表的顺序存储表示：
----- 用一维数组表示顺序表
线性表长度可变 但是数组的长度不可动态定义(不可变) ----- 单独用一变量表示顺序表的长度
5、线性表的定义：
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
typedef struct{
ElemType elem[LIST_SIZE]; //数组
int length; //当前长度
}SqList;
init(initialization初始化) SqList(顺序表) ElemType(元素类型)
多项式的顺序存储结构类型定义：
#define MAXSIZE 1000 //多项式可能达到的最大长度
typedef struct { //多项式非零项的定义
float p; //系数
int e; //指数
}Polynomial;//一个该元素类型8个字节（4+4）
typedef struct { //线性表定义
Polynomial *elem; //存储空间的基地址 元素类型是Polynomial 好比int *elem
int length; //多项式中当前项的个数
}SqList;
Polynomial: 多项式
图书表的顺序存储结构类型定义：
#define MAXSIZE 10000 //图书表可能达到的最大长度
typedef struct { //图书信息定义
char no[20]; //图书ISBN
char name[50]; //图书名字
float price; //图书价格
}Book;
typedef struct {
Book *elem; //存储空间的基地址 Book型
int length; //图书表中当前图书的个数
}SqList; //图书表的顺序存储结构类型为SqList
6.类C语言有关操作
1.顺序表类型定义
typedef struct {
ElemType date[]; //定义数组
int length; //定义长度
}SqList;
ElemType元素类型：可写char、float、Book结构类型、Polynomial结构类型
可事先做 typedef char ElemType; typedef int ElemType; 将ElemType定义为char/int类型来使用
2.数组定义
数组静态分配：
typedef struct {
ElemType date[MaxSize]; //数组名也是首地址
int length;
}SqList; //顺序表类型
数组动态分配：
typedef struct {
ElemType *date; //数组的首地址
int length;
}SqList; //顺序表类型
3.C语言的内存动态分配
需要加载头文件：include < stdlib.h >
malloc(m)函数：开辟m字节长度的地址空间，并返回这段空间的首地址 m为整数
free§函数：释放指针p所指变量的存储空间，即彻底删除一个变量
动态分配内存：
SqList L; //用顺序表类型定义1个变量L
L.date=(ElemType*)malloc(sizeof(ElemType)*MaxSize); //基地址
(申请的空间如何划分)malloc(需要的字节数)
(L.date是数组的首地址)
(char*)malloc(800) —> 800个空间
(int*)malloc(800) —> 200个空间
(Polynomial*)malloc(800) —> 100个空间
***** ：( )是强制类型转换运算—>(int)强转为整数 (int*)强转为指向整型的指针
malloc() 与 free() 配套使用
new 与 delete 配套使用
4.C++的动态存储分配
new 类型名T (初值列表)
功能：申请存放T类型对象的内存空间，并依初值列表赋以初值
结果值：成功：T类型的指针，指向新分配的内存 失败：0（NULL）
int *p1 = new int; 没有赋初值
int *p1 = new int(10); 赋初值10
delete 指针P
功能：释放指针P所指向的内存。P必须是new操作的返回值
delete p1;
5.C++中的参数传递
参数传递的两种方式
1、传值方式：参数为整型、实型、字符型等
2、传地址：参数是指针变量
? 参数是引用类型(C++) &
? 参数是数组名
引用类型作参数
引用：给对象提供一个替代的名字
int i=5; int &j=i; (j引用i) j是i的一个替代名，操作i和j是一样的，i值改变时，j值也跟着改变
★：i、j地址一样，共用同一个空间
void swap (float &m, float &n){}; swap(a,b)m引用a，n引用b &m=a, &m=b。m和a用同一块空间，n和b用同一块空间
相比一般变量作参数，节省了实参变量副本的空间
四、线性表的顺序表示与实现2
线性表通过数组存储：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zULfIJmC-1638540067062)(线性表1.assets/image-20211020192230620.png)]
线性表L：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LAAjIRQ9-1638540067063)(线性表1.assets/image-20211020194641578.png)]
SqList L;引用成员：L.elem L.length 指针形式SqList *L;L->elem L->length
补充：操作算法中用到的预定义常量和类型
//函数状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASILB -1#define OVERFLOW -2//Status 是函数的类型，其值是函数结果状态代码typedef int Status;typedef char ElemType;
infeasible：adj. 不可实行的
顺序表基本操作的实现
1、线性表L的初始化
Status InitList_Sq(SqList &L){ //构造一个空的顺序表L L.elem = new ElemType[MAXSIZE]; //为顺序表分配空间 L.elem是数组首地址 if(!L.elem) exit(OVERFLOW); //存储分配失败 ！有内容-->假 ！无内容-->真，分配失败退出 L.length=0; //空表长度为0 return OK;}
2、销毁线性表
void DestroyList(SqList &L){ if(L.elem) delete L.elem; }
L.elem有内容 --> 销毁L.elem
L.elem无内容 --> 无操作
3、清空线性表
void ClearList(SqList &L){ L.length=0; ?为什么不把数组里的元素置为0}
4、求线性表的长度
int GetLength(SqList L){ return (L.length);}
5、判断线性表L是否为空
int IsEmpty(SqList L){ if (L.length==0) return 1; else return 0;}
6、取值
取线性表中第i个元素的值 —> 线性表随机存取的特性
int GetElem(SqList L, int i, ElemType &e){ if (i<1 || i>L.length) return ERROR; //判断 e=L.elem[i-1]; //数组第i-1号 存储着第i个数据 return OK;}
算法固定执行1次/10000次 复杂度O(1)
算法执行的次数固定不变 常量阶，复杂度O(1)
7、查找
LocateElem(L, e)：在线性表L中查找与指定值e相同的数据元素的位置，若成功，返回该元素在表中是第几个元素，否则返回0（按值查找）
分析：从表的一端开始，逐个查找
int LocatedElem(SqList L, ElemType e){ for(i=0; i<L.length; i++) //i是数组序号 if(L.elem[i]==e) return i+1; //i+1是第几个 return 0; }
return：返回结果 并结束当前的函数
时间复杂度：if(L.elem[i]==e)为基本语句 n=L.length
平均查找长度(ASL Average Search Length) =(1+2+3+···+n-1+n)/n = (n+1)/2 （查找次数的期望值）
平均时间复杂度：O(n)
8、插入
插入元素后的线性表必须保证连续的特性，例如，插最后一个元素时必须紧跟原线性表的末尾元素
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rFMOT0sj-1638540067065)(线性表1.assets/image-20211026145701319.png)]
插入位置思想： 将元素f、a依次后移，再将g放入 length加1
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ubY9HmRr-1638540067065)(线性表1.assets/image-20211026144724953.png)]
算法思想：
①判断插入位置i是否合法
②判断顺序表的存储空间是否已满，若已满返回ERROR
③将第n至第i位的元素依次向后移动一个位置，空出第i个位置
④将元素e放入第i个位置
⑤表长加1，插入成功返回OK
Status ListInsert_Sq(SqList &L, int i, ElemType e){ if(i<1 || i>L.length+1) return ERROR; //判断插入位置i是否合法 if(L.length == MAXSIZE) return ERROR; //判断顺序表的存储空间是否已满 for(j=L.length-1; j>=i-1; j--){ L.elem[j+1] = L.elem[j]; //插入元素及之后的元素依次后移 } L.elem[i-1] = e; //将元素e放入第i个位置 L.length++; //表长增1 return OK;}
算法分析：
可插入的位置有（n+1）个 n:线性表中元素个数
插入第（n+1）个位置：移动0次
插入第n个位置：移动1次
插入第（n-1）个位置：移动2次
? ·
? ·
插入第2个位置：移动（n-1）次
插入第1个位置：移动n次
插入位置 + 移动次数 = n + 1
平均移动次数：n/2（每一种出现的可能性是1/n+1）
平均时间复杂度：O(n)
9、删除
算法思想：
①判断删除位置i 是否合法（合发值为1≤i≤n）
②将第i+1至第n位的元素依次向前移动一个位置
③表长减1，删除成功返回OK
Status ListDelete Sq(SqList &L, int i){ if(i<1 || i>L.length) return ERROR; //判断删除位置i是否合法 for(j=i; j<=L.length-1; j++){ //被删除元素之后的元素前移 L.elem[j-1]=L.elem[j]; } L.Length--; //表长减1 return OK;}
算法分析：
| 删除位置i | 第1个 | 第2个 | ··· | 第(n-2)个 | 第(n-1)个 | 第n个 |
|---|---|---|---|---|---|---|
| 移动次数 n-i | n-1 | n-2 | ··· | 2 | 1 | 0 |
平均移动次数：(n-1)/2（每一种出现的可能性是1/n）
平均时间复杂度：O(n)
线性表小结
算法分析：
- 时间复杂度：查找、插入、删除算法的平均时间复杂度为O(n)
- 空间复杂度：顺序表操作算法的空间复杂度S(n)=O(1)（没有占用辅助空间）
优缺点：
优点：
- 存储密度大
- 可以随机存取表中任一元素
缺点：
- 在插入、删除某一元素时，需要移动大量元素
- 浪费存储空间
- 属于静态存储结构，数据元素的个数不能自由扩充