数据结构第二章(上篇)
2线性表(上篇)
“以下四章为线性结构相关的知识，同时本章是整个课程的重点与核心内容，也是其他后续章节的重要基础。”
2.1 线性表的定义和特点
线性表是具有相同特性的数据元素的一个有限序列
$\large (a1,a2,a3,……a_i,a_{i+1},……,a_n)$ 也就是说数组就是线性表咯
其中数据元素的个数n定义为表的长度。
-
当n=0时称为空表。
-
将非空的线性表记作(a1,a2……，an)
可以看出线性表的逻辑特征是：
- 有且仅有一个开始结点$a1$，他没有直接前驱，而仅有一个直接后继$a2$。
- 有且仅有一个终端结点$a_n$，他没有直接前驱，而仅有一个直接前驱$a{n-1}$。
- 其余内部结点都有且仅有一个直接前驱和一个直接后继。
2.2 案例引入
2.2.1 一元多项式的运算
$\large P_n(x)=p_0+p_1x+p_2x^{2}+……+p_nx^n$ $\large Q_n(x)=q_0+q_1x+q_2x^{2}+……+q_nx^n$
- 其中$\large p_x和\large q_x$是系数
- 那么两个多项式相加的结果$R_n(x)=P_n(x)+Q_m(x)$可用线性表R表示：
- $\large R=(p_0+q_0,p1+q1,p2+q2+……+p_n+q_n)$
- 那么两个多项式相加的结果$R_n(x)=P_n(x)+Q_m(x)$可用线性表R表示：
2.2.2 稀疏多项式的运算
$\large S(x)=1+3x^{10000}+2x^{20000}$
- 仅记录系数不为零的系数即可，这样可以大大节省空间。
线性表A：(7,0)、(3,1)、(9,8)、(5,7)
线性表B：(8,1)、(22,7)、(-9,8)
- 创建一个新数组C
- 分别从头比较A、B的每一项 PS：就是相当于走一遍一元多项式运算的步骤
- 指数相同：对应系数相加，若其和不为零，则在C中增加一个新项
- 指数不相同：则将指数较小的项复制到C中
- 一个线性表添加完后，将另一个线性表剩余项依次复制到C中即可
| 0 | 1 | 7 | 8 | 7 |
|---|---|---|---|---|
| 7 | 11 | 22 | 0 | 5 |
- 顺序结构存在的问题
- 存储空间分配不灵活
- 运算的空间复杂度高
- 由此引出了链式存储结构
-
- 不需要额外的操作空间
2.2.3 图书信息管理系统
- 将图书表抽象为线性表
- 表中每本图书抽象线性表中数据元素
- 具体实现，学完这一章就会了，暂时按下不表
总结：
- 线性表中数据元素的类型可以为简单类型，也可以为复杂类型。
- 许多实际应用问题所涉及的基本操作有很大相似性，不应为每个具体应用单独编写一个程序。
- 从具体应用中抽象出共性的逻辑结构和基本操作（抽象数据类型），然后实现其存储结构和基本操作。
2.3 线性表的类型定义
- 抽象数据类型线性表定义如下：
PS: List是线性表的英文名
- 基本操作：
- InitList(&L) (Initialization List)
操作结果：构造一个空的线性表L。 - DestroyList(&L)
初始条件:线性表L已存在。
操作结果：将L重置为空表。 - ListEmpty(L)
初始条件：线性表L已存在。
操作结果：若L为空表， 则返回true, 否则返回false。 - ListLength(L)
初始条件：线性表L已存在。
操作结果：返回L中数据元素个数。 - GetElem(L,i,&e)
初始条件：线性表L巳存在，且1:,s;i:os;ListLength(L)。
操作结果：用e返回L中第1个数据元素的值。 - LocateElem(L,e)
初始条件：线性表L已存在
操作结果：返回L中第1个 值与e相同的元素在 L中的位置 。若这样的数据元素不存在 ， 则返回值为0。 - PriorElem(r,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:,s;i:os;ListLength (L) +l。
操作结果：在 L中第1个位置之前插入新的数据元素 e, L的长度加1。 - ListDelete(&L,i)
初始条件：线性表L已存在且非空 ，且l:os;i:os;ListLength(L)。
操作结果：删除L的第1个数据元素，L的长度减1。 - TraverseList(L)
初始条件：线性表L已存在
操作结果：对线性表L进行遍历，在遍历过程中对 L的每个结点访问一次。
- InitList(&L) (Initialization List)
2.4 线性表的顺序表示和实现
2.4.1 线性表的顺序存储表示
- 线性表的顺序表示又称为顺序存储结构或顺序映像
- 顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构
线性表的第一个数据元素$a_1$的存储位置，称作线性表的起始位置或基地址
-
顺序表的特点：以物理位置相邻表示逻辑关系，任一元素均可随机存取。（优点）
- PS：必须是占用一片连续的存储空间，中间不存在空的存储单元
-
线性表类型定义的模版：
1 |
|
- 例一：多项式的顺序存储结构类型定义
1 |
|
- 例二：图书表的顺序存储结构类型定义
1 |
|
-
补充：数组定义
-
数组静态分配
1
2
3
4typedef struct{
ElemType data[MaxSize];
int length;
}SqList; //顺序表类型 -
数组动态分配
1
2
3
4typedef struct{
ElemType *data;
int length;
}SqList; //顺序表类型 -
C语言的内存动态分配
SqList L；
L.data=(ElemType*^f)malloc(sizeof(ElemType)*MaxSize);
需要加载头文件：<stdlid.h>
-
-
传地址方式——指针变量做参数(c++)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void swap(float*m,float*n){
float t:
t=*m;
*m=*n;
*n=t;
}
void main(){
float a,b,*p1,*p2;
cin>>a>>b; //cin>>输入的意思
p1=&a; p2=&b;
swap(p1,p2);
cout<<a<<endl<<b<<endl; //endl换行的意思
} -
传地址方式——数组名作参数
1
2
3
4
5
6
7
8
9
void sub(char b[]){
b[]="world";
}
void main (void){
char a[10]="hello";
sub(a):
cout<<a<<endl; //结果为world
} -
传地址方式——引用类型作参数
1
2
3
4
5
6
7
void main(){
int i=5;
int &j=i; //i是本名；j是小名
i=7; //i值改变j值也会跟着改变
cout<<"i="<<i<<"j="<<j; //输出i=7 j=7
}- 形参变化实参也发生变化
- 占有同一片区域
-
顺序表示意图
1
2
3
4
5
typedef struct{
ElemType *elem;
int length;
}SqList; //定义顺序表类型- $\large SqList$ $\large L$； //定义变量L，L是SqList这种类型的，L是个顺序表
2.4.2 顺序表的基本操作的实现
-
初始化线性表L
算法2.1 顺序表的初始化
- elem指向这段空间的基地址
- 将表的当前长度设为0
1
2
3
4
5
6Status lnitLIS_Sq(SqList &L){ //构造一个空的顺序表
L.elem=new ElemType[MAXSIZE]; //为顺序表分配空间
if(!L.elem)exit(OVERFLOW); //存储分配失败
L.length=0; //空表长度为0
retunrn OK;
} -
销毁线性表L
1
2
3void DestroyList(SqList &L){
if(L.elem)delete L.elem: //释放存储空间
} -
清空线性表L
1
2
3void ClearList(SqList &L){
L.length=0; //将线性表长度置为0
} -
求线性表L的长度
1
2
3int GetLength(SqList L){
return(L.length);
} -
判断线性表L是否为空
1
2
3
4int IsEmpty(SqList L){
if(L.length==0)return 1;
else return 0;
} -
取值
算法2.2 顺序表的取值
- 根据指定的位置序号$\large i$，获取顺序表中第$\large i$个数据元素的值。
- 若是$\large i$值合理，则将将第 $\large i $个数据元素 $\large L.elem[i-1]$赋给参数$\large e$, 通过$\large e$返回第 1 个数据元素的传值。
1
2
3
4
5int GetElem(SqList L,int i,ElemType &e){
if(i<1||i>L.length)return ERROR: //i是序号，所以不能小于1
e=L.elem[i-1];
return OK
} -
查找
算法2.3 顺序表的查找
- 从第一个元素开始，往后找，查找成功返回该元素的序号i+1
- 若找到最后还是没找到，则查找失败，返回0
1
2
3
4
5int LocateELem(SqList L,ElemType e){
for(i=0;i<L.length;i++)
jif(L.elem[i]==e)return i+1; //查找成功返回i+1
return 0； //查找失败返回0
}平均查找长度ASL ：在查找时，为确定元素在顺序表中的位置， 需和给定值进行比较的数据元素个数的期望值称为查找算法在查找成功时的平均查找长度
$\large ASL=\sum\limits_{i=1}^nP_iC_i$ $P_i$是第i个记录被查找的概率 $C_i$是第i个记录需要比较的次数
$\large ASL=p_1+2p_2+3p_3+np_n=\dfrac{1}{n}(1+2+3+……+n)$ 每一个记录被查找的概率都相等是$\large p_i=\dfrac{1}{n}$
$ASL=\dfrac{1}{n}\dfrac{n(n+1)}{2}=\dfrac{n+1}{2}$
tips：这里和C语言的查找有着异曲同工之妙，还是要打好C语言的基础学这个就会轻松很多了
-
插入
算法2.4 顺序表的插入
- 看插入位置是否合法（1<=i<=n+1）,不合法则返回error
- 看顺序表存储空间是否已满，已满返回error
- 将第n干活到第i个位置元素一次后移一个位置
- 将e放入第i个位置
- 表长+1
1
2
3
4
5
6
7
8
9status ListInsert(SqList &L,int i,ElemType e){
if(i<=1||i>L.length+1)return ERROR;
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; //赋值
L.length++; //表长加一
return OK;
}顺序表插入算法分析：$\large E_{ins}=\dfrac{1}{n+1}\sum\limits_{i=1}^{n+1}(n-i+1)=\dfrac{n}{2}$
i是第几个位置，x是移动次数，第1个移动n次，第2个移动n-1次最后一个移动0次，可发现$\large i+x=n+1$
所以顺序表插入算法的平均复杂度为$\large O(n)$ (前面最高次项的系数二分一是常数，删除了)
-
删除
算法2.5 顺序表的删除
- 判断位置i是否合法
- 将位置i后的元素一次前移
- 表长-1，删除成功返回OK、
1
2
3
4
5
6
7status ListInsert(SqList &L,int i,ElemType e){
if(i<=1||i>L.length+1)return ERROR;
for(j=i.j<length-1;j++
L,elem[j-1]=L.elem[j]; //元素前移
L，length--;
ruturn OK;
}顺序表删除算法分析：$\large E_{del}=\dfrac{1}{n}\sum\limits_{i=1}^{n}(n-i)=\dfrac{n-1}{2}$
i是第一个移动n-1次，i是2移动n-2次,i是第n个移动0次，可发现$\large x=n-i$
