【数据结构】P1 线性表+顺序表

本笔记基于《王道数据结构》一书理解并笔记记录

在我看来，线性表与顺序表的关系就是一个是思想，一个是实现。
从数据结构的三要素角度来看，线性表代表着逻辑结构，顺序表为物理实现方法。

线性表的定义

线性表是具有相同数据类型的n个数据元素的有限序列。其中n为表长，当然n为0时表示线性表为空表。一般用L=(a₁,a₂,…,a_n) 来表示线性表。

表头元素： 线性表L中，第一个元素a₁，为表头元素。除表头元素外，每个元素有且只有一个直接前驱；
表尾元素： 线性表L中，最后一个元素a_n，为表尾元素。除表尾元素外，每个元素有且只有一个直接后继。

---

线性表的特点

表中元素个数有限；
表中元素具有逻辑上的顺序性，表中元素有先后次序关系；
表中元素都是数据元素，每个元素都是单个元素；
表中元素的数据类型都相同，每个元素占用相同大小的存储空间；
表中元素具有抽象性，即仅讨论元素之间的逻辑关系，不考虑元素究竟表示什么内容。

---

线性表的基本操作

InitList(&L)		// 初始化表，构建一个空的线性表
Length(L)			// 求表长，返回线性表的长度，即L中数据元素的个数
LocateElem(L,e)		// 按值查找操作，在表L中查找值等于e的元素的索引值
GetElem(L,i)		// 按位查找操作，获取表L中第i个位置上的元素的值
ListInsert(&L,i,e)	// 插入操作，在表L中第i个位置插入指定元素e
ListDelete(&L,i,&e)	// 删除操作，删除表L中第i个位置的元素，并用e返回其值
PrintList(L)		// 输出操作，按前后顺序输出线性表L的所有元素值
Empty(L)			// 判空操作，若L为空表，返回true，否则返回false
DestoryList(&L)		// 销毁操作，销毁线性表，并释放线性表L所占用的内存空间
1
2
3
4
5
6
7
8
9

---

顺序表

线性表的顺序存储为顺序表；用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

由于顺序表的特性，使得线性表中的任一数据元素都可以随机存取。所以线性表的顺序存储结构是一种随机存取的存储结构。在高级程序设计语言中，通常用数组来描述线性表的顺序存储结构。

---

静态分配与动态分配

由于顺序表用一组地址连续的存储单元依次存储线性表中的数据元素，所以对空间的初始分配很重要。分为静态分配以及动态分配两种方案。

静态分配

数组的大小和空间事先固定，一旦空间存满，再加入新的数据会导致溢出；进而导致程序崩溃。

#define MaxSize 50
typedef struct{
	ElemType data[MaxSize];
	int length;
}SqList;
1
2
3
4
5

动态分配

存储数组的空间是在程序的执行过程中通过动态存储分配语句分配的。一旦数据空间占满，则另外开辟一块更大的存储空间，用来替换原来的存储空间，从而达到扩充存储数组空间的目的。

#define InitSize 100
typedef struct{
	ElemType *data;
	int MaxSize,length;
}SeqList;
1
2
3
4
5

初始动态分配语句为

//C 语言
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
//C++ 语言
L.data=new ElemType[InitSize];
1
2
3
4

---

顺序表上基本操作

插入

bool ListInsert(SqList &L,int i,ElemType e){
	if(i<1||i>L.length+1)
		return false;
	if(L.length>=MaxSize)
		return false;
	for(int j=L.length;j>=i;j--)
		L.data[j]=L.data[j-1];
	L.data[i-1]=e;
	L.length++;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11

最好情况：在最后一个插入，无需挪动任何其他元素，时间复杂度为O(1)。
最坏情况：在第一个插入，需要移动所有元素，时间复杂度为O(n)。
平均情况：考虑每个位置插入的可能，用需要移动的总和除以n个元素，得到时间复杂度同样为O(n)。
P.S. 要是不明白为甚么O(n/2)也为O(n)，需要理解时间复杂度的相关概念。

---

删除

bool ListDelete(SqList &L,int i,ElemType &e){
	if(i<1||i>L.length)
		return false;
	e=L.data[i-1];
	for(int j=i;j<L.length;j++)
		L.data[j-1]=L.data[j];
	L.length--;
	return true;
}
1
2
3
4
5
6
7
8
9

最好情况：删除最后一个元素，无需移动其他任何数据元素，时间复杂度为O(1)。
最坏情况：删除第一个元素，需要移动除第一个元素外其他所有元素，时间复杂度为O(n)。
平均情况：考虑每个元素都有被删除的可能，平均下来需要移动元素所消耗的时间复杂度为O(n)。

---

按值查找

int LocateElem(SqList L,ElemType e){
	int i;
	for(i=0;i<L.length;i++)
		if(L.data[i]==e)
			return i+1;
	return 0;
}
1
2
3
4
5
6
7

最好情况：第一个元素（索引为0）就是要找到，仅需要比较一次，时间复杂度为O(1)。
最坏情况：查找的元素在表尾，需要比较n次，时间复杂度为O(n)。
平均情况：考虑到每个元素都有可能成为被查找的那个，所以其平均时间复杂度为O(n)。