数据结构----顺序表

在学习顺序表之前，我们先来了解一下数据结构。

数据是什么呢？

我们在生活中常见的名字，数字，性别等都属于数据。

结构又是什么呢？

在计算机中，结构就是用来保存数据的方式。

总的来说，数据结构就是计算机存储和组织数据的方式。

1.顺序表

顺序表是数据结构中的一种，也就是说顺序表是一种用来存储和组织数据的一种结构，并且顺序表的底层本质就是数组，只不过顺序表是在数组的的基础上，增加了增删查改的方法，也就是说顺序表里面已经提供了对数据进行增删查改的现成的方法。只不过顺序表里面的增删查改的方法需要我们通过代码来实现，实现顺序表里面的增删查改的代码之后，以后我们实现对通讯录里面数据的增删查改的操作直接用就行了。

同时顺序表是线性表的一种。

1.1线性表

线性表就是具有相同特性的的数据结构的集合。

数据结构是否具有相同特性是从物理结构和逻辑结构来判断。

物理结构：数据在内存中存储的样子。由于我们无法得知计算机是如何给数据分配内存的，所以数据结构有连续和不连续的两种。

逻辑结构：逻辑结构一定是连续的。逻辑结构是我们抽象想象的。

比如排队的时候，我们排对的时候可能排的不是一条直线，但是我们还是得一个一个按序付钱，虽然看起来是不连续的，但在逻辑上我们将其抽象想象成线性的。

前面我们提到，顺序表的底层结构就是数组，而数据又是一块连续的空间，所以顺序表在物理结构和逻辑结构上都是连续的。

 

2.顺序表的分类

我们将顺序表分为了两种，分别为静态顺序表和动态顺序表。

2.1 静态顺序表

静态顺序表简单来说就是一个定长的数组。

如下图

此时Seqlist就是一个静态顺序表，该顺序表能储存的数据个数大小已经确定，其只能存储100个数据。

2.1动态顺序表

动态顺序表就是一个未定长的数组，也就是动态顺序表里面的数组能存储数据的个数是未定的，但是动态顺序表能存储的数据个数是可以根据实际情况实现动态改变的。

那上面两种顺序表哪种更好用呢？

肯定是动态顺序表。因为它能够根据实际情况来动态实现增容或删除数据。

3.动态顺序表的的实现

由于顺序表的属性有点多，所以我们要用结构体来实现顺序表。

当我们实现动态顺序表的时候我们要分多个文件来实现。如下图

3.1 动态顺序表的创建和声明

typedef int SLDataType;  //方便以后修改要存储的数据类型
struct SeqList
{
	SLDataType* arr;
	int size;  //有效的数据个数顺序表里面
	int capacity;  //顺序表的总大小
};
typedef struct SeqList SL; 

在一个头文件里面实现动态顺序表的声明。这里我们要将顺序表里面要存储的数据类型重命名为SLDataType,是为了以后方便修改要存储的数据类型，并且也将顺序表重命名为SL，方便后面的操作。

3.2动态顺序表的初始化

在.c源文件实现初始化

void SLInit(SL* sl)
{
	sl->arr = NULL;
	sl->size = 0;
	sl->capacity = 0;
}

需要注意的是，我们进行传参的时候要将sl的地址传过去。我们知道形参是实参的拷贝，我们对形参的改变是不会影响实参的，不会影响实参，初始化就会失败。所以我们要将sl的地址传过去，通过指针来实现初始化 。

通过调试，我们发现顺序表初始化成功了。

3.2 销毁动态顺序表

因为后面涉及到扩容等问题，要用到realloc函数，申请空间，完成程序之后我们要将申请的空间还给计算机，我们这里先把顺序表的销毁讲了，方便以后操作。

void SLBreak(SL* sl)
{
	if (sl->arr)
	{
		free(sl->arr);
	}
	sl->size = 0;
	sl->capacity = 0;
}

3.3 数据插入

将数据插入顺序表中有两种方法，分别是尾插和头插。

3.3.1 尾插

什么是尾插呢？

尾插就是从顺序表的尾部插入数据。如下图

此时的size==4，我们可能就会想到所以只要将ps->arr[size]改为想要插入的之就行了 。写出以下代码

void SLPushBack(SL* sl, SLDataType x)
{
	sl->arr[sl->size] = x;
}

但事情并没有那么简单。

我们要知道插入数据时，首先要清楚顺序表内有没有足够的空间来存储插入的数据呢？一开始我们已经将顺序表的内存大小设置为0，这时侯肯定是没有空间插入数据的，所以这时候我们要向内存申请空间，并且以后我们要根据实际情况来实现扩容，所以这时候最好的选择是通过realloc函数来申请空间。

接着再来分析，我们要申请多大的空间呢？

一搬来说，是原来capacity的两倍或者三倍是最好的的选择。

但原来的capacity为0，所以这时候要用上三目操作符。

尾插代码如下

void SLPushBack(SL* sl, SLDataType x)
{
	assert(sl);
	if (sl->size == sl->capacity)
	{
		//实现扩容
		int SLNewCapacity = sl->capacity == 0 ? 4 : 2 * sl->capacity;
		SLDataType* tmp =(SLDataType*) realloc(sl->arr, SLNewCapacity * sizeof(SLDataType));
         //判断空间是否申请成功
		if (tmp==NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		//代码运行到这里，空间就申请成功了
		sl->arr = tmp;
		sl->capacity = SLNewCapacity;
	}
	sl->arr[sl->size] = x;
	sl->size++;
}

易错点：扩容那里后面是两个==。

 我们需要注意的是我们申请空间成功时返回的地址不能直接传给原来顺序表的数组，因为申请空间会存在失败的情况，空间申请失败就会退出程序，并销毁该空间了。假设我们之前的顺序表已经存有数据，但因为空间申请失败也把原来的空间释放掉，那么原来的数据也没了，这就功亏一篑了，所以我们要设计一个中间变量存储申请空间返回的地址，有这个中间变量来判断空间是否申请成功。

由于我们插入了数据，不要忘了让size的个数进行增加。

3.3.2 头插

什么是头插呢？

头插就是从顺序表的头部插入一个数据。

下面来分析一下如何实现头插。

假设上图是我们要进行头插的一个数组？

我们要将一个数据插入1的位置，那么我们就要将原有的数据向后移一位。如下图

既然插入数据，我们就涉及到空间申请了，这里的空间申请于尾插的一莫一样，既然一样，那我们干脆把空间申请的那部分代码单独写为一个函数，需要的时候调用这个函数就行了。

空间申请的代码如下

void SLSpace(SL* sl)
{
	assert(sl);
	if (sl->size == sl->capacity)
	{
		//实现扩容
		int SLNewCapacity = sl->capacity == 0 ? 4 : 2 * sl->capacity;
		SLDataType* tmp = (SLDataType*)realloc(sl->arr, SLNewCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		//代码运行到这里，空间就申请成功了
		sl->arr = tmp;
		sl->capacity = SLNewCapacity;
	}
}

尾插代码

void SLPushHead(SL* sl, SLDataType x)
{
	assert(sl);
	//调用空间申请函数
	SLSpace(sl);
	//实现顺序表原数据向后移1位
	for (int i = sl->size; i > 0; i--)
	{
		sl->arr[i] = sl->arr[i - 1];//arr[1]=arr[0]
	}
	sl->arr[0] = x;
	sl->size++;
}

运行效果如下图，头插的数据为5。

3.4.数据删除

既然有数据的插入，那么就有数据的删除。删除我们也分为尾删和头删的两种。

3.4.1 尾删

什么是尾删？

尾删就是将顺序表里面的的最后一个元素删除掉。

如上图，尾删将4给除掉了。

代码实现

void SLPopBack(SL* sl)
{
	assert(sl);
	assert(sl->size);  //检测顺序表不为空
	sl->size--;
}

尾删我们直接让size（ 顺序表中的有效个数）减减就行了。我们没必要将要尾删的数据改为其他，我们只要求尾删的操作不影响后面的增删查改的操作就行了。

运行效果

3.4.2 头删

什么是头删呢？

头删就是将顺序表的第一个元素删除掉 。

头删如上图所示，也就是将第一个元素除外其他元素向前移动一位。

代码实现 

void SLPopHead(SL* sl)
{
	assert(sl);
	assert(sl->size);
	//实现数据向前移动一位
	for (int i = 0; i<sl->size-1; i++)
	{
		sl->arr[i] = sl->arr[i + 1];  //arr[2]=arr[3]
	}
	sl->size--;
}

运行效果

3.5 在指定位置插入数据

分析如何实现？

思路：将指定位置的数据及以从后向前的顺序向后移动一位。

如下图

代码实现

 

void SLPopPos(SL* sl, int pos, SLDataType x)
{
	assert(sl);
	assert(sl->size && pos <= sl->size);
	//插入数据之前要申请空间
	SLSpace(sl);
	for (int i = sl->size; i > pos; i--)
	{
		sl->arr[i] = sl->arr[i - 1];
	}
	sl->arr[pos] = x;
	sl->size++;
}

运行效果

3.6 在指定位置删除数据

 思路

将指定位置之后的数据向前移动一位。

如下图

代码实现

void SLPopPos(SL* sl, int pos)
{
	assert(sl&&sl->size);
	assert(pos && pos < sl->size);
	for (int i = pos; i<sl->size-1; i++)
	{
		sl->arr[pos] = sl->arr[pos + 1];
	}
	sl->size--;
}

运行效果

3.7 查找数据

代码实现

int SLFind(SL* sl, SLDataType x)
{
	assert(sl);
	for (int i = 0; i < sl->size; i++)
	{
		if (sl->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
 
}

运行效果

 这里就结束了对顺序表的介绍

下面给大家列处全部代码

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
int main()
{
	SL sl;  //创建一个结构体变量
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPrint(sl);
	SLPushHead(&sl, 5);
	SLPrint(sl);
	SLPopBack(&sl);
	SLPrint(sl);
	SLPopHead(&sl);
	SLPrint(sl);
	SLPushPos(&sl, 1, 3);
	SLPrint(sl);
	SLPopPos(&sl, 2);
	SLPrint(sl);
	int find = SLFind(&sl, 3);
	if (find < 0)
	{
		printf("不存在");
	}
	else
	{
		printf("数据位于下标为%d",find);
	}
	//要在顺序表销毁之前完成增删查改的操作
	SLBreak(&sl);
	
	return 0;
}

SeqList.h

#include <assert.h>
typedef int SLDataType;  //方便以后修改要存储的数据类型
struct SeqList
{
	SLDataType* arr;
	int size;
	int capacity;
};
typedef struct SeqList SL; 
void SLInit(SL* sl);
void SLPrint(SL sl);
void SLBreak(SL* sl);
void SLPushHead(SL* sl, SLDataType x);
void SLPushBack(SL* sl, SLDataType x);
void SLPopBack(SL* sl);
void SLPopHead(SL* sl);
void SLPushPos(SL* sl, int pos, SLDataType x);
void SLPopPos(SL* sl, int pos);
int SLFind(SL* sl, SLDataType x);

Seqlist.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
void SLInit(SL* sl)
{
	sl->arr = NULL;
	sl->size = 0;
	sl->capacity = 0;
}
void SLSpace(SL* sl)
{
	assert(sl);
	if (sl->size == sl->capacity)
	{
		//实现扩容
		int SLNewCapacity = sl->capacity == 0 ? 4 : 2 * sl->capacity;
		SLDataType* tmp = (SLDataType*)realloc(sl->arr, SLNewCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		//代码运行到这里，空间就申请成功了
		sl->arr = tmp;
		sl->capacity = SLNewCapacity;
	}
}
void SLPrint(SL sl)
{
	for (int i = 0; i < sl.size; i++)
	{
		printf("%d ", sl.arr[i]);
	}
	printf("\n");
}
void SLBreak(SL* sl)
{
	if (sl->arr)
	{
		free(sl->arr);
	}
	sl->arr = NULL;
	sl->size = 0;
	sl->capacity = 0;
}
void SLPushBack(SL* sl, SLDataType x)
{
	SLSpace(sl);
	sl->arr[sl->size] = x;
	sl->size++;
}
void SLPushHead(SL* sl, SLDataType x)
{
	assert(sl);
	//调用空间申请函数
	SLSpace(sl);
	//实现顺序表原数据向后移1位
	for (int i = sl->size; i > 0; i--)
	{
		sl->arr[i] = sl->arr[i - 1];//arr[1]=arr[0]
	}
	sl->arr[0] = x;
	sl->size++;
}
void SLPopBack(SL* sl)
{
	assert(sl);
	assert(sl->size);  //检测顺序表不为空
	sl->size--;
}
void SLPopHead(SL* sl)
{
	assert(sl);
	assert(sl->size);
	//实现数据向前移动一位
	for (int i = 0; i<sl->size-1; i++)
	{
		sl->arr[i] = sl->arr[i + 1];  //arr[2]=arr[3]
	}
	sl->size--;
}
void SLPushPos(SL* sl, int pos, SLDataType x)
{
	assert(sl);
	assert(sl->size && pos <= sl->size);
	//插入数据之前要申请空间
	SLSpace(sl);
	for (int i = sl->size; i > pos; i--)
	{
		sl->arr[i] = sl->arr[i - 1];
	}
	sl->arr[pos] = x;
	sl->size++;
}
void SLPopPos(SL* sl, int pos)
{
	assert(sl&&sl->size);
	assert(pos && pos < sl->size);
	for (int i = pos; i<sl->size-1; i++)
	{
		sl->arr[pos] = sl->arr[pos + 1];
	}
	sl->size--;
}
int SLFind(SL* sl, SLDataType x)
{
	assert(sl);
	for (int i = 0; i < sl->size; i++)
	{
		if (sl->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
 
}

 感谢观看。