数据结构·顺序表

????????数据结构是计算机存储，组织数据的方式。数据结构和算法是不分家的，属于是算法的基础。数据结构会用到结构体，指针，结构体指针，动态内存管理的相关知识，这些知识一定要掌握扎实。接下来的一段时间让我们一起来学习数据结构方面的知识吧！

1. 顺序表的概念和结构

1.1 线性表

????????线性表是n个具有相同特性的数据元素的1有限序列。线性表是一种在实际应用中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串······

????????线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理上不一定是连续的结构，线性标表在物理上存储时，通常以数组和链式结构的形式存储

2. 顺序表分类

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

????????顺序表的分类：

????????静态顺序表：

????????使用指定长度数组存储元素，缺点是空间给少了不够用，给多了造成空间浪费

????????????????

????????定义数据结构的时候我并没有用int而是将int改了个名字，这是为了后期可能数组要换一个类型用了的时候好更改

????????动态顺序表：

????????用动态内存分配所需空间，需要多少空间开辟多少空间，同时还有扩容的能力

????????????????

? ? ? ? arr用动态内存开辟，形成数组，用来存放数据

? ? ? ? capacity用来记录这个顺序表的总大小，总共能存几个元素

? ? ? ? size用来记录有效数据的个数

3. 动态顺序表的实现

? ? ? ? 下面我们尝试实现一个顺序表，一个合格的顺序表要包括增加数据、删除数据、查找数据/更改数据，四种功能，简称“增删查改”。

? ? ? ? 在开始敲代码之前我们要先做一个准备工作

????????????????

? ? ? ? 创建一个头文件SeqList.h用来归纳顺序表中需要的功能的函数的声明，和生成顺序表的结构体

? ? ? ? 创建源文件SeqList.c用来实现函数

? ? ? ? test.c用来检测函数是否成功，有没有什么bug，好的习惯是写完一段函数就在这里检查一下，我在接下来的讲解中就不演示检查了，如果我的代码出了什么问题欢迎各位评论区指正。

? ? ? ? 为了使用方便我们把结构体类型改个名字

????????

? ? ? ? 现在我们可以靠结构体中的这三个参数的控制生成一个顺序表了

3.1 初始化和销毁

? ? ? ? 这个阶段我先写3个功能，如下，声明放在头文件中

????????????????????????

? ? ? ? 初始化函数没什么好讲的，就是把结构体中的三个成员置空或者归零。

????????说一下为什么用结构体指针传参，而不是用结构体变量传。是因为如果传结构体变量的话传过去相当于参数的一份临时拷贝，我并不能修改参数的内容，相当于没办法真正更改结构体中的内容。而传指针的话我可以顺着指针找到它指向的那块区域，再进行更改，这样就能真正改到结构体内容了。

????????????????

? ? ? ? 销毁函数我们要判断这个结构体指针是否存在，要不然传一个空指针过来我做的改动意义就没有了，这里用到了assert断言，记得要在SeqList.h中引用<assert.h>。

????????因为后面我们知道arr是动态开辟的所以free(arr)是销毁函数的重头戏，这其中判不判断arr为空都行，因为free空指针什么都不会做。

????????销毁最后相当于在初始化一下这个结构体或者说顺序表，就完成销毁。

? ? ? ? 这里我随手写了一个打印函数，就是用来在test.c中检查我写的功能能不能用的，这里用到了printf()记得在头文件中引用一下库，这个函数就是用for循环打印一下所有有效数据就完事了

????????

3.2 "增" "删"

? ? ? ? "增"和"删"是顺序表中的主要功能

????????

? ? ? ? 这里是接下来要实现的功能

3.2.1 扩容

? ? ? ? 首先我们要想清楚一个事情，就是当arr是动态开辟的，那么当长度不够用的时候，如何检测，如何扩容？当然这个扩容的功能因为只涉及到“增”这一个方面，所以就直接写在SeqList.c中了

? ? ? ? 这个函数就是用来解决上面那个问题的，当存的有效数据个数size和总大小capacity一样的时候就说明空间沾满了，如果再要用就要扩容。

? ? ? ? 注意这里用到了realloc()先去声明一下<stdlib.h>

? ? ? ? newCapacity是用来说明要扩容到多大的，当我们第一次开辟空间的时候也就是刚初始化完的那一次开辟capacity是0，所以要检查一下，先开4个元素位置，如果不是第一次开辟空间了，就让新空间等于老空间的2倍，这种操作是将代码运行效率和空间浪费程度综合考虑后的方案。如果每次都开辟固定的小空间，那后期数据量庞大的时候就需要不停开辟空间，这样会大大影响代码运行效率，如果一次就开辟巨大无比的空间就会造成很多的空间浪费。

? ? ? ? 为了防止扩容失败，我用tmp做了一个保护，最后记得在结构体中把总大小更新

3.2.2 ''增'插入

? ? ? ? 从尾部插入

? ? ? ? 这个逻辑很简单没啥好说的，就注意增加了一个数据，所以最后要让size++记录增加了一个有效数据

? ? ? ? 从头部插入

????????指定位置前面增加数据

? ? ??

? ? ? ? 这个功能可以在顺序表中的任意位置插入数据，pos就是这个位置的下标，要记得断言一下pos是不是一个有效的位置。

????????这个功能其实可以包含前两个功能的pos==0就是在头部插入，pos==size就是在尾部插入

3.2.3 "删"删除

? ? ? ? 从尾部删除

? ? ? ? 这里删最后一位就是直接size--很灵性，直接让最后一位不在有效数据范围内就属于是删除了

? ? ? ? 从头部删除

????????少一个有效数据，删完记得size自减

? ? ? ? 删除指定位置数据

? ? ??

? ? ? ? 这里就要注意pos不能和size相等了，因为size不属于有效数据的下标，删一个不有效的位置是错误的。其他没什么需要注意的了for循环写对就行，逻辑是不难的。

3.3 "查"

? ? ? ? 查找数据功能很好实现，先在头文件中声明一下该功能

??????????????????????????????????????

? ? ? ? 然后在SeqList.c中实现它

????????

? ? ? ? 我这个功能模块写的相当简单，就是遍历数组，感兴趣的可以改一下，qsort排个序，用个二分法什么的。

3.4 "改"

? ? ? ? "改"最简单了，老规矩，还是现在头文件中声明一下

????????

????????然后在SeqList.c中实现它

????????

? ? ? ? 这个也简单，检查一下pos是不是有效的然后改一下arr就行了

3.5 完整代码

? ? ? ? 头文件SeqList.h完整代码?

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDatatype;
typedef struct SeqList
{
	SLDatatype* arr;	//存储数据的底层结构
	int capacity;		//记录顺序表的空间大小
	int size;			//有效数据个数
}SL;

//初始化和销毁
void SLInit(SL* ps);
void SLDestory(SL* ps);
void SLPrint(SL* ps);

//顺序表插入数据
//从尾部插入
void SLPushBack(SL* ps, SLDatatype x);
//从头部插入
void SLPushFront(SL* ps, SLDatatype x);

//顺序表删除数据
//从尾部删除
void SLPopBack(SL* ps);
//从头部删除
void SLPopFront(SL* ps);

//顺序表任意位置增删数据
//指定位置前面增加数据
void SLInsert(SL* ps, int pos, SLDatatype x);
//删除指定位置数据
void SLErase(SL* ps, int pos);


//在顺序表中查找x
int SLFind(SL* ps, SLDatatype x);

//在顺序表中把pos位置的数据改成x
int SLChange(SL* ps, int pos, SLDatatype x);

? ? ? ? 函数实现SeqList.c完整代码

#include"SeqList.h"

//初始化和销毁	
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

void SLDestory(SL* ps)
{
	assert(ps);
	if (ps->arr)//arr不是空的再释放，也可以不判断
	{
		free(ps->arr);//free空指针函数什么都不会做
	}	
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

void SLPrint(SL* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]); 
	}
	printf("\n");
}


//顺序表插入数据
//判断空间是否足够，不够就扩容
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)//空间不够时
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		//为了防止扩容失败导致数据丢失，扩容后的空间地址先不给ps->arr
		SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype));
		if (tmp == NULL)//扩容失败
		{
			printf("realloc fail!\n");
			exit(1);//错误退出码1
		}
		//扩容成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

//从尾部插入
//逻辑：空间足够就直接尾插，空间不够就扩容，扩容一般是扩容当前空间的2倍
void SLPushBack(SL* ps, SLDatatype x)
{
	assert(ps);

	//判断空间够不够，不够就扩容
	SLCheckCapacity(ps);

	//走到这里时空间肯定够了，直接在后面插入数据
	ps->arr[ps->size++] = x;
	//ps->size++;
}

//从头部插入
//逻辑：将所有数据向后挪一位，再在第一位插入数据
void SLPushFront(SL* ps, SLDatatype x)
{
	assert(ps);

	//判断空间够不够，不够就扩容
	SLCheckCapacity(ps);

	//此时空间够了，将所有数据往后挪一位，再放数据
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}
//在添加完元素之后一定要记得 ps->size 增加一个

//顺序表删除数据
//从尾部删除
//逻辑：顺序表为空，不能执行删除，顺序表不为空直接删最后一个数据
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);//数据为空报警

	//顺序表不为空
	ps->size--;
	//看不见最后一位等于删了最后一位
}
//从头部删除
//逻辑：顺序表为空不删，顺序表不为空将数据们往前挪一位
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);

	//顺序表不为空
	for (int i = 0; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}
//在删除完数据之后也要记得减size


//顺序表任意位置增删数据
//指定位置前面增加数据
void SLInsert(SL* ps, int pos, SLDatatype x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);

	//pos及之后的数据往后挪一位
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

//删除指定位置数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	//pos以后的数据向前挪一位
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}



//在顺序表中查找x
int SLFind(SL* ps, SLDatatype x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;//找到了返回下标
		}
	}
	return -1;//没找到返回-1
}


//在顺序表中把pos位置的数据改成x
int SLChange(SL* ps, int pos, SLDatatype x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	ps->arr[pos] = x;
}