🪴 Quartz 4.0

数据结构1——顺序表

5 min read

定义：用顺序存储的方式实现线性表

顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

存放地址的计算：设第一个元素存放的位置是LOC(L)，则第i个元素的存放地址则为：

如何知道一个数据元素的大小：利用sizeof（ElemType）

sizeof(int)

顺序表的实现

  1. 静态分配
#define Maxsize 10
typedef struct{
    ElemType data[MaxSize];
    int length;
}SqList

具体代码：

#include <stdio.h>
#define MaxSize 10  //定义最大长度
typedef struct{
	int data[MaxSize]; //用静态的“数组”存放数据元素
	int length;  //顺序表的当前长度
}SqList  //顺序表的类型定义
 
//基本操作：初始化一个顺序表
void InitList(SqList &L){
	for(int i=0; i<Maxsize; i++) //将所有数据元素设置为默认初始值
		L.data[i]=0;
	L.length=0 //顺序表初始长度为0
}
int main(){
	SqList L; // 声明一个顺序表
	InitList(L); //初始化顺序表
	//……未完待续，后续操作
}

NOTE:内存中会有遗留的脏数据 Q：如果”数组“存满了怎么办？ A：放弃治疗，顺序表的表长刚开始确定后无法更改（存储空间是静态的）

  1. 动态分配
#define Maxsize 10
typedef struct{
    ElemType *data; //指示动态分配数组的指针
    int MaxSize;  //顺序表的最大容量
    int length;  //顺序表的当前长度
}SeqList

具体实现展示：

#include<stdlib.h> //malloc,free的头文件
#define InitSize 10 
typedef struct{
    int *data; //指示动态分配数组的指针
    int MaxSize;  //顺序表的最大容量
    int length;  //顺序表的当前长度
}SeqList
 
void InitList(SeqList &L){
	//用malloc函数申请一片连续的存储空间
	L.data=(int *)malloc(InitSize*sizeof(int));
	L.length=0;
	L.MaxSize=InitSize
}
//增加动态数组的长度
void IncreaseSize(SeqList &L, int len){
	int *p=L.data;
	L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
	for(int i=0;i<L.length;i++){
		L.data[i]=p[i];
	}
	L.MaxSize=L.MaxSize+len;
	free(p); //释放原来的内存空间
}
int main(){
	SeqList L;
	InitList(L);
	//……往顺序表中随便插入几个元素……
	IncreaseSize(L,5);
	return 0;
}

顺序表的插入和删除

  1. 插入 ListInsert(&L,i,e) —在表L的第i个位置上插入元素e
void ListInsert(SqList &L,int i,int e){
	for(int j=L.length;j>=i;j--)
		L.data[j]=L.data[j-1];
	L.data[i-1]=e;
	L.length++;
}
 
//优化版
bool ListInsert(SqList &L,int i,int 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. 删除操作
//优化版
bool ListInsert(SqList &L,int i,int &e){
   if(i<1||i>L.length+1)
   	return false;
   e=L.data[i-1]; //将被删除的数据元素复制给e
   for(int j=i;j<L,length;j++)//将第i个位置后的元素前移
   	L.data[j-1]=L.data[j];
   L.length--;   //线性表长度减1
   return true;
}

删除操作的时间复杂度：

最好情况：删除表尾元素，不需要移动元素

最坏情况：删除表头元素

平均情况：

顺序表的查找

  1. 按位查找 静态分配：
ElemType GetElem(SqList L,int i){
	return L.data[i-1];
}

动态分配

ElemType GetElem（SeqList L，int i）{
	return L.data[i-1];
}

时间复杂度

  1. 按值查找
int LocateElem(SeqList L,ElemType e){
	for(int i=0;i<L.length;i++)
		if(L.data[i]==e)
			return i+1;
	return 0;
}
// 基本数据类型：int，char，double，float等可以直接运用“==”比较

时间复杂度

最好时间复杂度：

最坏：

平均：

结构类型的比较

//需要依次对比各个分量来判断两个结构体是否相等
if(a.num == b.num&&a.people==b.people){
	printf("相等");
}else{
	printf("不相等")；
}

Graph View