数据结构（顺序表）

一.顺序表的概念及结构

线性表

顺序表是线性表的一种。

线性表（linear  list）是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

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

案例：蔬菜分为绿叶类、瓜类、菌菇类。线性表指的是具有部分相同特性的⼀类数据结构的集合 如何理解逻辑结构和物理结构？

线性表的物理结构指的是线性表在计算机内存中的存储方式，包括顺序存储和链式存储两种形式（顺序表就是顺序存储，所以它的物理结构就是一定连续的）。

线性表的逻辑结构指的是线性表中元素之间的关系，包括线性表的元素之间的顺序和相邻元素之间的关系。线性表的逻辑结构是指数学上的约定，用于描述线性表的特性和操作规则。例如，线性表可以是有序的，元素按照一定的顺序排列；线性表可以是无序的，元素的顺序可以任意改变。线性表的逻辑结构可以由具体的实现方式来决定，不同的物理结构可以实现相同的逻辑结构。

线性表的物理结构不一定连续，逻辑结构一定是连续的。

顺序表的物理结构一定连续，逻辑结构一定是连续。

二.顺序表的分类

顺序表和数组的区别：

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

听起来顺序表好像很陌生，实际上就是数组的豪华版套装，变得更加灵活了。

1.静态顺序表

创建一个结构体，结构体的成员有两个，一个是定长的数组，一个是有效数据的个数。

这种静态顺序表使用起来不太好：空间给少了不够用，给多了造成空间浪费

2.动态顺序表

有静态就会有动态，这个结构体就有三个成员：一个指针类型的变量，一个是有效数据个数，一个是空间容量（因为这个是动态的，我们在使用的时候可能会改变顺序表的大小，所以我们最好是有一个变量可以记录一下这个表的大小。）

其实关于这两种顺序表，我们是更加推荐动态顺序表的，因为我们可以随时的改变我们需要的大小。

三.动态顺序表的实现

这里就实现一下动态顺序表，我们需要创建三个文件，一个SeqList.h的头文件，一个SeqList.c实现功能的文件，还有一个用来测试我们代码错误的测试文件test.c。

先来SeqList.h文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;
//动态顺序表
typedef struct SeqList
{
	SLDataType* arr;
	int size; //有效数据个数
	int capacity; //空间大小
}SL;
//顺序表初始化
void SLInit(SL* ps);

//顺序表的销毁
void SLDestroy(SL* ps);
void SLPrint(SL s);

//头部插入删除 / 尾部插入删除
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);
int SLFind(SL* ps, SLDataType x);

然后再SeqList.c里实现它们的功能：

#include"SeqList.h"
void SLInit(SL* ps)//初始化
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}
//顺序表的销毁
void SLDestroy(SL* ps)
{
	if (ps->arr) //等价于  if(ps->arr != NULL)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}
void SLCheckCapacity(SL* ps)
{
	//插入数据之前先看空间够不够
	if (ps->capacity == ps->size)
	{
		//申请空间
		//malloc calloc realloc  int arr[100] --->增容realloc
		//三目表达式
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//要申请多大的空间
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);//直接退出程序，不再继续执行
		}
		//空间申请成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	温柔的解决方式
	//if (ps == NULL)
	//{
	//	return;
	//}
	assert(ps); //等价与assert(ps != NULL)

	//ps->arr[ps->size] = x;
	//++ps->size;
	SLCheckCapacity(ps);
	ps->arr[ps->size++] = x;
}
//头插
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];//arr[1] = arr[0]
	}
	ps->arr[0] = x;
	ps->size++;
}
//打印
void SLPrint(SL s)
{
	for (int i = 0; i < s.size; i++)
	{
		printf("%d ", s.arr[i]);
	}
	printf("\n");
}
//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	//顺序表不为空
	//ps->arr[ps->size - 1] = -1;
	--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]; //arr[size-2] = arr[size-1]
	}
	ps->size--;
}

//在指定位置之前插入数据
// 1 2   size = 2
//pos 0 -1 100000
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];//arr[pos+1] = arr[pos]
	}
	ps->arr[pos] = x;
	ps->size++;
}
//指定位置删除
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}
//查找
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;
}

最后是测试的text.c文件：

#include"SeqList.h"

void SLTest01()
{
	SL sl;
	SLInit(&sl);
	
	//尾插
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPrint(sl);//1 2 3 4
	//头插
	//SLPushFront(&sl, 5);
	//SLPushFront(&sl, 6);

	//尾删
	SLPopBack(&sl);
	SLPrint(sl);//1 2 3 
	SLPopBack(&sl);
	SLPrint(sl);//1 2
	SLPopBack(&sl);
	SLPrint(sl);//1
	SLPopBack(&sl);
	SLPrint(sl);//报错
	SLPopFront(&sl);
	SLPrint(sl);
	//...........
	SLDestroy(&sl);
}
void SLTest02()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPrint(sl);//1 2 3 4
	//测试指定位置之前插入数据
	SLInsert(&sl, 1, 99);
	SLPrint(sl);
	SLInsert(&sl, sl.size, 88);

	//测试删除指定位置的数据
	SLErase(&sl, 1);
	SLPrint(sl);//1 3  4

	//测试顺序表的查找
	int find = SLFind(&sl, 40);
	if (find < 0)
	{
		printf("没有找到！\n");
	}
	else {
		printf("找到了！下标为%d\n",find);
	}
	SLDestroy(&sl);
}
int main()
{
	SLTest02();
	return 0;
}

这些代码是需要我们手动敲的，先看一遍尝试理解，理解之后尽量自己敲一下。

感谢观看，如有错误，不足的地方，还请大家多多指正