顺序表

基本概念

用一组地址连续的存储单元依次存储线性表的数据元素，这种存储结构的线性表称为顺序表。

数据结构的三要素

• 逻辑结构
  • 线性结构：顺序表是线性表的实现之一
• 存储结构
  • 顺序存储：逻辑上相邻的数据元素，物理次序也是相邻的
• 数据的运算

费曼理解

1. 在内存内划分一块连续的地址空间来存储数据，这块地址原来有无数据，并不清楚
2. 就好像划了一块田给你种地，这块土地原来有没有作物我们并不知道，所以需要将每块田的原本作物拔掉（假设每块土地存在原作物），也就是进行初始化。因为只有这块田是属于我们的，所以如果种的作物种到田外了，那就不属于我们了。所以需要边界判定。

内部实现：

静态表

define maxsize 10
typedef struct{
	int data[maxsize];
	int length
}Sqlist

• maxsize:我们为静态表所申请的空间长度
• length:表的当前长度
• data[maxsize]:以数组的形式存储数据
• Sqlist:静态表的类型定义
  • 例如我们可以使用Sqlist l的语句来声明一个名叫L的静态表

动态表

define maxsize 10
typedef struct{
	int *data
	int maxsize
	int length
}Seqlist

• maxsize:我们为初始动态表申请空间的最大容量，可增加
• $*data$：指针，指向内存的数组
• length:动态表当前长度
• Seqlist:动态表的类型定义

复杂度分析：

初始化

静态表的初始化

void Initlist(Sqlist &L)
{
	for(int i=0;i<maxsize;i++){
		L.data[i]=0;
	}
	L.length=0;
}

复杂度分析

• 时间复杂度：$O(maxsize)$
• 空间复杂度：$O(1)$

动态表的初始化

void Initlist(Seqlist &L)
{
	L.data=(int*)malloc(InitSize*sizeof(int));//申请数组空间
	L.length=0;
	L.MaxSize=InitSize;
}

复杂度分析

• 时间复杂度：$O(1)$
• 空间复杂度：$O(InitSize)$

动态表的容量增加

void IncreaseSize(Seqlist &L,int len)
{
	int *p=L.data //*p指向原来表所指向的数组
	L.data=(int*)malloc((L.MaxSize+len)*sizeof(int));
	for(int i=0;i<L.MaxSize;i++){
		L.data[i]=p[i];       //复制元素到新的数组空间
	}
	L.MaxSize=L.MaxSize+len   //更新表的最大容量
	free(p)       //释放p
}

复杂度分析

• 时间复杂度：$O(MaxSize)$
• 空间复杂度：$O(MaxSize+len)$

顺序表的插入

bool ListInsert(Sqlist &L,int i,int e)
{
	// 边界探索
	//判断当前表的容量是否允许数据插入
	if(L.length>=MaxSize){
		return False;
	}
	//判断插入元素的位置的位置是否在表内
	if（i<1||i>L.length+1){
		return False;
	}
	// 进行插入操作
// 先将第i-1个元素之后的元素往后移1位，为插入元素腾出空间，因为我们是顺序存储，所以不能直接插入
	for(int j=L.length;j>=i;j--){
		L.data[j]=L.data[j-1];
	}
	L.data[i-1]=e;//在第i个位置插入元素e
	L.length++;  //更新表长
	return True;
}

复杂度分析

• 时间复杂度：
  • 最好情况-在表尾插入元素：$O(1)$
  • 最差情况-在表头插入元素：$O(N)$
  • 平均情况-移动n/2个元素：$O(N)$
• 空间复杂度：$O(1)$

顺序表的删除

bool ListDelete(Sqlist &L,int i,int &e)// e用引用型参数
{
	// 边界探索
	//判断i是否合法
	if（i<1||i>L.length){
		return False;
	}
	// 进行删除操作
// 使用引用型参数e挖走第i个位置上的元素，此时L.data[i-1]==null
	e=L.data[i-1];
	//将第i个位置后的元素前移1位
	for(int j=L.length;j>=i;j--){
		L.data[j-1]=L.data[j];
	}
	L.length--;  //更新表长
	return True;
}

复杂度分析

• 时间复杂度：
  • 最好情况-在表尾删除元素：$O(1)$
  • 最差情况-在表头删除元素：$O(N)$
  • 平均情况-移动n/2个元素：$O(N)$
• 空间复杂度：$O(1)$

顺序表的按位查找（返回值）

ElemType GetElem(Sqlist L,int i)
{
	return L.data[i-1];
}

复杂度分析

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

顺序表的按值查找（返回位序）

Int LocalElem(SeqlistL,ElemType e)
{
	for(int i=0;i<L.length;i++)
	{
		if(e==L.data[i]){
			return i+1
		}
	}
	return 0;
}

复杂度分析

• 时间复杂度：
  • 最好情况-元素在表头：$O(1)$
  • 最差情况-元素在表尾或元素不存在：$O(N)$
  • 平均情况-移动n/2个元素：$O(N)$
• 空间复杂度：$O(1)$

应用场景：

顺序表的特点

• 随机访问：可以在$O(1)$时间返回找到元素
• 插入、删除操作不方便，需要移动大量元素
• 拓展容量不方便（需要重新申请空间并且移动元素）
• 存储密度高，每个节点只存储数据元素（使用数组存取元素）

应用场景

概念图谱

// 顺序表在内存中的布局
rectangle: 栈区
  - L: [指针] → 指向堆区数组
  
rectangle: 堆区  
  - data[0]: 元素1
  - data[1]: 元素2
  - ...
  - data[n]: 元素n