数据结构---顺序表

1.什么是数据结构？

数据结构是由“数据”和“结构”两词组合⽽来。 什么是数据？常⻅的数值1、2、3、4.....、教务系统⾥保存的⽤⼾信息（姓名、性别、年龄、学历等 等）、⽹⻚⾥⾁眼可以看到的信息（⽂字、图⽚、视频等等），这些都是数据 什么是结构？

当我们想要使⽤⼤量使⽤同⼀类型的数据时，通过⼿动定义⼤量的独⽴的变量对于程序来说，可读性 ⾮常差，我们可以借助数组这样的数据结构将⼤量的数据组织在⼀起，结构也可以理解为组织数据的 ⽅式。

想要找到草原上名叫“咩咩”的⽺很难，但是从⽺圈⾥找到1号⽺就很简单，⽺圈这样的结构有效将 ⽺群组织起来。

概念：数据结构是计算机存储、组织数据的⽅式。数据结构是指相互之间存在⼀种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由哪部分构成，以什么⽅式构成，以及数据元素之间呈现的结构。

总结：

1、能够存储数据（如顺序表、链表等结构）

2、存储的数据能够⽅便查找

3、为什么需要数据结构？

如图中所⽰，不借助排队的⽅式来管理客⼾，会导致客⼾就餐感受差、等餐时间⻓、餐厅营业混乱等 情况。

同理，程序中如果不对数据进⾏管理，可能会导致数据丢失、操作数据困难、野指针等情况。

通过数据结构，能够有效将数据组织和管理在⼀起。按照我们的⽅式任意对数据进⾏增删改查等操作。

最基础的数据结构：数组

【思考】有了数组，为什么还要学习其他的数据结构？

假定数组有10个空间，已经使⽤了5个，向数组中插⼊数据步骤：

求数组的⻓度，求数组的有效数据个数，向下标为数据有效个数的位置插⼊数据（注意：这⾥是 否要判断数组是否满了，满了还能继续插⼊吗）.....

假设数据量⾮常庞⼤，频繁的获取数组有效数据个数会影响程序执⾏效率。

结论：最基础的数据结构能够提供的操作已经不能完全满⾜复杂算法实现。

2. 顺序表的概念及结构

那什么是顺序表呢？

在了解顺序表之前我们可以先了解一下线性表。

2.1 线性表

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

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

线性表指的是具有部分相同特性的⼀类数据结构的集合

肯定又要有人疑问了？什么是物理结构，什么是逻辑结构呢？

2.1.1物理结构

假如我们有一个数组arr里面有5个空间这5个空间是连续的那么每一个空间都有自己的地址我们称为物理地址或者叫物理内存，这种存储在内存中存储的方式就是物理的

物理结构在线性表里面不一定连续 

2.1.2 逻辑结构

逻辑结构就是我们肉眼看到的或者说我们想象出来的这种数据结构，对于线性表来说，它的逻辑结构就是我们把它想象成一条直线一样的，比如我们去超市买东西人比较多需要排队随着人越来越多排成一竖排我们把它称之为是线性的，为什么说它是线性的呢？因为我们排队的时候只要站成一条一字型那就是线性的。

那么实际排队的时候一定是线性的吗？那也有可能站的七扭八歪的，所以我们把它称之为抽象的，我们人为想象出来的一个线性。 

所以说线性表在逻辑结构上是连续的。

补充：其实顺序表是线性表的一种，具有相同特性的数据结构的集合

2.2顺序表的特性

既然顺序表是线性表的一种，那么逻辑结构在线性表上都是连续的那肯定在顺序表上也一定是连续的，而物理结构在线性表上是不一定连续，所以物理结构在顺序表上是连续的还是不连续的呢？，我们要明白一点顺序表的底层是数组而数组在物理结构上是连续的所以我们顺序表在物理结构上是连续的。

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

2.2.1顺序表和数组的区别

有人可能要疑问了，既然顺序表的底层就是数组，那它和数组的区别是什么？

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

当对数组进行插入和删除操作时，通常需要知道数组的元素个数以及要操作元素的对应下标，如果数组比较庞大呢。

但是顺序表就不一样了，虽然我底层是数组，但是我提供了很多现成的方法，开箱即用，我就变成了一个新的很厉害的数据结构。

3.顺序表分类

顺序表分为静态顺序表和动态顺序表

静态顺序表;

//静态顺序表
typedef int SLDateType;
#define N 100
struct seqList
{
	SLDateType arr [N];//定长数组
	int size;//有效个数
};

静态顺序表使⽤定⻓数组存储元素，上面的arr数组给定了100个空间而它的的空间是固定死了的，有个时候我们要放的数据比较少可能会多出很多空间，这样可能会造成空间浪费，而有个时候我们存放的数据比较多导致空间又不够用。

size表示当前顺序表里面的有效个数。

静态顺序表缺陷：空间给少了不够⽤，给多了造成空间浪费 

动态顺序表：

//动态顺序表
typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* arr;
	int size;//有效数据个数
	int capacity;//空间大小
}SL;

而动态顺序表就不一样了，动态顺序表可以动态增容（成倍数的增加，一般以2倍的形式增加），当空间不够用的时候我们可以增容。

第一个成员arr指向的内存空间是一个数组，用来存储顺序表中的元素。这个数组的大小可以动态调整，所以这里将其定义为指针类型，方便后续动态内存分配和释放。

size表示当前有效数组的元素个数

capacity表示顺序表当前分配的空间个数

以上你们会选择哪一种顺序表呢？

我会选择第二种，动态顺序表，使用起来更加方便，因为它可以动态的增容。

4.动态顺序表的代码实现

我们应该如何使用C语言实现一个动态顺序表呢，首先我们要知道一个项目里面有头文件和源文件，我们使用头文件来定义顺序表的方法和声明，用源文件来实现顺序表的方法，我们还需要创建一个源文件用来检测我们的方法是否正确运行我们称它为测试文件。

我们一共有三个文件，一个头文件(SeqList.h)，两个源文件：顺序表的方法文件（SeqList.c），测试文件(test.c)

现在我们来开始写代码

SeqList.h

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;
	int size;//有效数据个数
	int capacity;//空间大小
	
}SL;

首先我们在头文件里面定义了我们的数据结构，可以用typedef定义一个名字，然后我们想一下这个数组里面我们一定要用int类型吗？不一定，万一我们以后要用char类型呢，所以我们可以使用typedef 语句定义一个类型别名 SLDateType，它被指定为 int 类型，以后需要使用别的类型我们就可以直接把int改为我们想要的类型了。

然后我们需要在头文件里面声明一些函数，根据我们顺序表的功能来看，我们起码要完成增删查改吧，内存不够的时候我们要进行增容，还要对结构体的成员进行初始化，我们开辟了空间那肯定是需要释放的。

所以我们来总结一下需要实现哪些功能:

顺序表的初始化

尾部插入

头部插入

尾部删除

头部删除

在指定位置之前插入数据

删除指定位置数据

查找

打印

顺序表的销毁

所以我们的SeqList.h文件里面有这些代码：

#define _CRT_SECURE_NO_WARNINGS 1
#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 SLPushBack(SL* ps, SLDataType x);//尾插
 
void SLPrint(SL s);//打印
 
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);//查找
 
void SLDestroy(SL* ps);//顺序表的销毁

4.1顺序表的初始化

SeqList.c

//给结构体初始化
#include "SeqList.h"
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

把arr置为空指针，size和capacity初始化为0

测试文件test.c

注意：记得包含头文件，一定要传地址而不是传值，因为传值操作变量都有独立的空间，形参的修改不影响实参。

---

4.2.增容

初始化时我们把空间设置为0，我们要向顺序表里面插入数据那就需要增容，下面我们来写增容的代码。

SeqList.c

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;
	}
}

增容用的函数是realloc函数，但刚开始是0，所以我们用三目操作符来判断如果为0我们就给4个空间，如果不等于0直接用2*capacity也就是我们的空间大小（增容以2倍的形式增加），我们申请空间的时候可能会申请失败，所以我们可以创建一个临时指针变量用来进行判断。（如果大家不知道realloc函数怎么用的可以看我主页里面的动态内存管理）

---

4.3.尾插和头插

增容完我们就来插入数据，插入数据分为头部插入尾部插入。

写代码之前我们先分析一下：  

尾插

SeqList.c文件下：

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);//ps不能为空指针
	SLCheckCapacity(ps);
	ps->arr[ps->size++] = x;
}

ps是我们结构体的地址，x是我们要插入的元素。

在插入之前我们需要看看内存够不够，不够就要增容

我们在测试文件（test.c）里面测试一下我们的尾插，为了方便我们查看尾插是否插入数据我们写把它打印出来。 

SeqList.c文件下
//打印
void SLPrint(SL s)
{
	for (int i = 0; i < s.size; i++)
	{
		printf("%d ", s.arr[i]);
	}
	printf("\n");
}

头插 

SeqList.c：

//头插
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++;
}

通过for循环遍历将元素整体往后挪动一步，遍历完后第一个元素的位置已经空出来了直接把x赋值给它，然后size++就行了。

测试（test.c）一下头插：

---

4.4.尾删和头删

完成了头插和尾插后，我们再来写一下尾删和头删。代码和分析如下：

尾删

SeqList.c

//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	//顺序表不为空
	--ps->size;
}

如果size为空我们还可以删除数据吗？不可以，所以我们要加个断言。

test.c文件下测试一下尾删：

头删

SeqList.c

//头删
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--;
}

test.c文件下测试一下头删

---

4.5.指定位置删除和插入

我们知道了头插和尾插，头删和尾删，我们还有指定位置进行删除和指定位置之前进行插入。代码和分析如下：

指定位置之前插入数据

SeqList.c

//在指定位置之前插入数据
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++;
}

pos是指定位置的下标，pos只能在我们size的有效个数之间进行指定位置的插入，上面pos<=ps->size是因为我们size这个位置要放数据最后size会++的 ，所以我们加了个断言限制一下。

test.c：

删除指定位置的数据

SeqList.c:

//删除指定位置的数据
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--;
}

这里pos < ps->size为什么是小于而不是小于等于呢？因为我们是要删除数据，size这个地方有数据吗？这个地方没有数据，所以我们pos不能指定这个位置。

test.c：

---

4.6.查找

我们再来实现一个查找数据的功能。代码如下：

SeqList.c:

//查找
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;
}

查找失败我们就返回一个无用的下标。 

test.c：

int find = SLFind(&sl, 4);
//int find = SLFind(&sl,30);
if (find == -1)
{
	printf("没有找到\n");
}
else
{
	printf("找到了下标是%d\n", find);
}

---

4.7销毁

最后我们要把申请的空间进行销毁，如果不销毁的话会导致内存泄漏等等问题。

代码实现如下：

 SeqList.c:

//顺序表的销毁
void SLDestroy(SL* ps)
{
	if (ps->arr) // 等价于  if(ps-> != NULL)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

test.c:

SLDestroy(&sl);

---

5.顺序表所有代码展示

SeqList.h

#define _CRT_SECURE_NO_WARNINGS 1
#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 SLPushBack(SL* ps, SLDataType x);//尾插
 
void SLPrint(SL s);//打印
 
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);//查找
 
void SLDestroy(SL* ps);//顺序表的销毁

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
 
//给结构体初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}
//顺序表的销毁
void SLDestroy(SL* ps)
{
	if (ps->arr) // 等价于  if(ps-> != 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)
{
	assert(ps);
	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];
	}
	ps->arr[0] = x;
	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--;
}
//在指定位置之前插入数据
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);
	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;
}
//打印
void SLPrint(SL s)
{
	for (int i = 0; i < s.size; i++)
	{
		printf("%d ", s.arr[i]);
	}
	printf("\n");
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
 
void SLTest01()
{
	SL sl;
	SLInit(&sl);//初始化
	SLPushBack(&sl, 1);//尾插
	SLPushBack(&sl, 2);//尾插
	SLPushBack(&sl, 3);//尾插
	SLPushBack(&sl, 4);//尾插
	SLPushBack(&sl, 5);//尾插
	SLPrint(sl);//打印
 
	SLPushFront(&sl, 0);//头插
	SLPushFront(&sl, 7);//头插
	SLPrint(sl);//打印
 
	SLPopBack(&sl);//尾删
	SLPrint(sl);//打印
 
	SLPopFront(&sl);//头删
	SLPrint(sl);//打印
 
	SLInsert(&sl, 0, 10);//指定位置插入
	SLPrint(sl);//打印
 
	SLErase(&sl, 0);//指定位置删除数据
	SLPrint(sl);//打印
	SLErase(&sl, 3);//指定位置删除数据
	SLPrint(sl);//打印
 
	int find = SLFind(&sl, 4);
	if (find == -1)
	{
		printf("没有找到\n");
	}
	else
	{
		printf("找到了下标是%d\n", find);
	}
	int find1 = SLFind(&sl, 30);
	if (find1 == -1)
	{
		printf("没有找到\n");
	}
	else
	{
		printf("找到了下标是%d\n", find1);
	}
	SLDestroy(&sl);
}
int main()
{
	SLTest01();
	return 0;
}

---

由于个人能力和知识有限，可能存在表述不准确或理解不深刻的地方，还请各位看客不吝指正。