[数据结构] 1.顺序表

「前言」

????个人主页： 代码探秘者
????C语言专栏：C语言
????C++专栏： C++
????喜欢的诗句:天行健,君子以自强不息.

线性表

线性表（List）：零个或多个数据元素的有限序列。

线性表的数据集合为{a1,a2,…,an}，假设每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

在较复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称为文件

1、顺序表的基本概念

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

特点：逻辑上相邻的数据元素，物理次序也是相邻的。

只要确定好了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的储存结构，因为高级语言中的数组类型也是有随机存取的特性，所以通常我们都使用数组来描述数据结构中的顺序储存结构，用动态分配的一维数组表示线性表。

顺序表和数组的区别

◦ 顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口

1.1 静态顺序表

概念：使用定长数组存储元素
静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费

 静态顺序表(这里拿里面存储的整形举例)
 typedef int SLDataType;
 #define N 100
 typedef struct SeqList
 {
     SLDatatype arr[N];
     int size;//size是有效数据的个数
 }SL;
  
 解释一下为什么要把存储的类型变为SLDataType
 这么做是为了方便以后修改 使用 不同 的类型 
 还有把数组存储的数据容量N 便于修改

1.2 动态顺序表

动态顺序表的结构更加灵活, 可以对结构进行 增删查改，所以我们下面的接口都是通过动态顺序表实现的

2、顺序表存储结构

//头文件
#include<stdio.h>
#include<stdlib.h>

typedef int ElemType;//假设当前元素类型int
//顺序表使用动态数组实现
typedef struct
{
	ElemType* elem;	//动态数组

	int length;		//长度：顺序表当前元素个数

	int ListSize;	//容量：最多存储的个数
}SqList;

3、构造一个空的顺序表L

• 开辟动态数组，以及初始化长度容量
• 返回顺序表

//初始化
SqList SqList_Init(int Size)
{
	SqList t;

	t.elem = (ElemType*)malloc(Size * sizeof(ElemType));
	t.length = 0;		//当前长度0
	t.ListSize = Size;  //容量
    
	return t;			//返回顺序表
}
int main()
{
	SqList sl;				//创建顺序表
    
	sl = SqList_Init(10);	//开容量为10的顺序表	
	return 0;
}

4、检查容量，扩容

• 可以使用malloc或者realloc

• 用三目运算符（如果开始是0，可以赋值给它，当然我们这里避免了这种情况）

• 扩容两倍

  //扩容
  void SqList_Capacity(SqList* t)
  {
  	//插入数据之前先看空间够不够
  	if (t->length == t->ListSize)
  	{
  		//申请空间
  		//malloc calloc realloc  int arr[100] --->增容realloc
  		//三目表达式
  		int newCapacity = t->ListSize == 0 ? 4 : 2 * t->ListSize;
  		ElemType* tmp = (ElemType*)realloc(t->elem, newCapacity * sizeof(ElemType));//要申请多大的空间
  		if (tmp == NULL)
  		{
  			perror("realloc fail!");
  			exit(1);//直接退出程序，不再继续执行
  		}
  		//空间申请成功(赋值回来就行)
  		t->elem = tmp;
  		t->ListSize = newCapacity;
  	}
  }
  

5、指定位置前插入元素

• 顺序表：不为空

• 检查容量：顺序表是否满了，满了就扩容

• 位置：判断位置是否合法

• 移动：根据插入位置需要移动元素个数/次数，将指定位置开始所以元素向后移动位置（从后往前移动）

• 插入和长度：插入元素，元素个数（length）+1

• 插入注意：

  • 1.插入位置超过顺序表长度，直接插入指定位置
  • 2.移动再插入

  //指定位置前插入	这里得用指针，因为得修改
  void SqList_Push(SqList* t,int index,ElemType elem)
  {
  	//检查容量：顺序表是否满了，满了就扩容
  	SqList_Capacity(t);
  	//位置：判断位置是否合法
  	if (index >= t->ListSize || index < 0)
  	{
  		printf("位置不合法");
  		return;
  	}
  
  	//移动和插入
  	
  	//如果插入位置超过顺序表长度，直接插入指定位置
  	if (index >= t->length)
  	{
  		t->elem[t->length] = elem;		//这里插入在最后一个元素下一个，不给它乱插
  		t->length++;
  		return;
  	}
  	//移动再插入
  	for (int i = t->length; i >index; i--)
  	{
  		//最开始  length=length-1  最后一个元素移动
  		//结束    index+1=index	   刚好index位置空出来
  		t->elem[i] = t->elem[i - 1];
  	}
  	t->elem[index] = elem;
  	t->length++;
  	return;
  }

6、删除

6.1 删除指定位置元素

• 顺序表：不为空

• 下标是否合法

• 下标i+1至length-1（最后一个元素的下标）移动（从前往后移动）

• 顺序表长度-1

void SqList_Pop1(SqList* t, int index)
{
	//顺序表：不为空
	if (t == NULL)
	{
		printf("顺序表为空");
		return;
	}
	if (index >= t->ListSize || index < 0)
	{
		printf("位置不合法");
		return;
	}
	//
	//
	for (int i=index; i<t->length-1; i++)
	{
		//最开始  index=index+1			覆盖index位置元素
		//结束    length-2=length-1	    刚好
		t->elem[i] = t->elem[i+1];
	}
	t->length--;	//元素个数减1
}

6.2 删除所有指定元素

• 顺序表：不为空
• 遍历顺序表，找到要删的，依次覆盖

//删除所有指定元素
void SqList_Pop2(SqList* t, ElemType elem)
{
	//顺序表：不为空
	if (t == NULL)
	{
		printf("顺序表为空");
		return;
	}
	//开始遍历
	int j = 0;
	while (j != t->length)
	{
		//不是要找的元素，下一个
		if (t->elem[j] != elem)
		{
			j++;
			continue;
		}
		//是，从前往后移动覆盖
		// j  =j+1
		// length-2=length-1
		for (int i = j; i < t->length-1; i++)
		{
			t->elem[i] = t->elem[i + 1];
		}
		t->length--;		//个数减1

		j++;
	}
}

7、查找

7.1 查找指定位置的元素

• 顺序表：不为空
• 位置合法
• 返回下标对应元素

//获取顺序表某一位置上的元素
ElemType  Find_Elem1(SqList t, int index)
{
	//顺序表：不为空
	if (t.length==0)
	{
		printf("顺序表为空");
		return -1;
	}
	//位置合法
	if (index >= t.length || index < 0)
	{
		printf("位置不合法");
		return -1;
	}
	return t.elem[index];
}

7.2 查找指定元素的下标

• 用index记录，遍历顺序表，如果找到，返回下标。
• 如果有多个，默认返回第一个。

//查找元素
int  Find_Elem2(SqList t, ElemType elem)
{
	//默认没找到
	int index = -1;
	for (int i = 0; i < t.length; i++)
	{
		if (t.elem[i] == elem)
		{
			//记录元素下标
			index = i;
			break;
		}
	}
	//没有找到
	if (index == -1)
	{
		printf("元素不存在，没有找到");
		return -1;
	}
	return index;
}

8、打印

• 根据顺序表长度遍历整个顺序表
• 遍历每个元素输出
• 用length还是ListSize呢？当然是前者啦，看看前面数据结构定义！

//打印
void SqList_Print(SqList t)
{
	//                         这个是一个宏定义，可以观察行号
	printf("[%s %d]打印顺序表：",__FUNCTION__,__LINE__);
	for (int i = 0; i < t.length; i++)
	{
		printf("%d ", t.elem[i]);
	}
	printf("\n");

9、销毁

//销毁
void SqList_Destory(SqList* t)
{
	if (t == NULL)
	{
		printf("顺序表为空，不能销毁");
		return;
	}
	//动态数组不为空
	if (t->elem)
	{
		free(t->elem);
		t->elem = NULL;
		t->ListSize = t->length = 0;
	}
}

10、测试

int main()
{
	SqList sl;
	sl = SqList_Init(5);			//开容量为5的顺序表	
	for (int i = 0; i < 10; i++)	//插入
	{
		SqList_Push(&sl, i, i);	
	}
	SqList_Print(sl);				//打印
	//查找指定下标4的元素
	int ret1 = Find_Elem1(sl, 4);	
	printf("查找指定下标4的元素:%d\n", ret1);

	//查找元素的下标
	int ret2 = Find_Elem2(sl, 3);	
	printf("查找元素3的下标:%d\n", ret2);

	//删除指定下标元素3
	printf("删除指定下标元素3\n");
	printf("删除前:");
	SqList_Print(sl);
	SqList_Pop1(&sl, 3);	
	printf("删除后:");
	SqList_Print(sl);
	
	//删除指定元素8
	printf("删除指定元素8");
	SqList_Push(&sl, 5, 8);			//再插入一个8
	printf("删除前:");
	SqList_Print(sl);
	SqList_Pop2(&sl, 8);			//删除指定元素8
	printf("删除后：");
	SqList_Print(sl);


	SqList_Destory(&sl);			//销毁
	return 0;
}

测试结果：

11、 小结

11.1 顺序表时间复杂度

从以上代码可以很明显的看出，线性表的顺序存储结果在读、存数据是的时间复杂度是O(1)，插入、删除操作的时间复杂度是O(n)。

11.2 顺序表的优缺点

优点：

• 无须为表中元素之间的逻辑关系而增加额外的存储空间；
• 可以快速的存取表中任一位置的元素。

缺点：

• 插入和删除操作需要移动大量元素；
• 当线性表长度较大时，难以确定存储空间的容量；造成存储空间的“碎片”。