【数据结构初阶】顺序表

各位读者老爷好，又见面了哈！鼠鼠我呀现在基于C语言浅浅介绍一下数据结构初阶中的顺序表，希望对你有所帮助！

目录

1.线性表 

2.顺序表

2.1.概念即结构

2.2.动态顺序表接口的实现

2.2.1.定义顺序表

2.2.2.初始化

2.2.3.销毁 

2.2.4.打印

2.2.5.尾插

2.2.6.头插 

2.2.7.头删

2.2.8.尾删 

2.2.9.顺序表查找

 2.2.10.顺序表在下标pos位置插入数据x

2.2.11.顺序表删除下标pos位置的值

3.顺序表使用 

3.1.test.c

3.2.SeqList.h

3.3.SeqList.c

4.小知识累积（与顺序表无关）

4.1.数组越界一定会报错吗？

4.2.数组的下标为什么不从1开始而要从0开始呢？ 

5.ending

额额额，好哈！顺序表是线性表的一种哈！那我们看看下面是线性表！

1.线性表 

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

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

咱们下面介绍的顺序表是一种在逻辑上和物理结构上是连续的。为什么说顺序表在物理结构上是连续的呢？因为顺序表在内存中是一块连续的空间，我们可以在下面体会。

2.顺序表

2.1.概念即结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存
储。在数组上完成数据的增删查改。

与数组不同的是，数组可以在不越界的情况下任意位置存储数据，而顺序表要求数据只能从头开始连续存储。

 顺序表一般可以分为：

1.静态顺序表：使用定长数组存储数据

//顺序表的静态存储
#define N 7
#typedef int SLDataType
typedef struct SeqList
{
SLDataType array[N];//定长数组
size_t size;//有效数据的个数
}SeqList;

2.动态顺序表：使用动态开辟的数组存储

//顺序表的动态存储
#typedef int SLDataType
typedef struct SeqList
{
SLDataType*array;//指向动态开辟的数组
size_t size;//有效数据的个数
size_t capicity;//容量空间的大小
}SeqList;

2.2.动态顺序表接口的实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空
间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间
大小，所以下面我们实现动态顺序表。

2.2.1.定义顺序表

typedef int SLDateType;

typedef struct SeqList
{
	SLDateType* a;
	int size;                                           //有效数据个数
	int capaticy;                                       //空间容量大小
}SeqList;

typedef一下有效数据的数据类型（现在是int）防止以后有效数据类型变更，如果变更我们只需要更改typedef的内容即可，方便后续代码维护。

根据上面结构体定义的顺序表，咱们在main函数里面创建一个顺序表s1，并实现该顺序表一系列接口实现。

SeqList s1;//顺序表

2.2.2.初始化

void SeqListInit(SeqList* ps)                               //初始化
{
	assert(ps);
	ps->a = NULL;
	ps->capaticy = 0;
	ps->size = 0;
}

咱们使用顺序表之前需要将有效数据size和空间容量capaticy置零，同时不妨将指向动态开辟数组的指针a置为NULL。

ps:这个函数的参数接收的是上面创建的顺序表s1的地址。

question：实现这个初始化函数参数为啥是s1的地址而不是s1呢？

answer：因为形参是实参的一份临时拷贝，形参的改变不会影响实参。就以这个初始化函数为例，如果这个函数参数是"SeqList s2"的话 ，虽然这个函数中将s2的成员a置为NULL、将s2的成员size和capaticy都置为零，但根本影响不了顺序表s1的成员a、size和capaticy。

就是因为这个原因，下面接口的实现都是采用传递s1的地址。

2.2.3.销毁 

void SeqListDestroy(SeqList*ps)                              //销毁
{
	assert(ps);
	if (ps->a != NULL)
	{
		ps->a = NULL;
		ps->capaticy = 0;
		ps->size = 0;
	}
}

咱们如果不再使用顺序表的话，因为顺序表的成员a指向动态开辟的数组，所以最好将这块空间free掉，size和capaticy也最好置零。

 ps:这个函数的参数接收的是上面创建的顺序表s1的地址。

2.2.4.打印

void SeqListPrint(SeqList* ps)                               //打印
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

必要时可以将存储在顺序表的数据打印出来看看，因为有size个数据，所以循环打印size次即可将数据全部打印出来。

 ps:这个函数的参数接收的是上面创建的顺序表s1的地址。

2.2.5.尾插

void SLCheckcapacity(SeqList* ps)                        //扩容
{
	assert(ps);
	if (ps->size == ps->capaticy)
	{
		int newcapaticy = (ps->capaticy == 0) ? 4 : 2 * (ps->capaticy);
		SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * newcapaticy);
		if (tmp == NULL)
		{
			perror("calloc fail");
			return;
		}
		ps->a = tmp;
		ps->capaticy = newcapaticy;
	}
}
void SeqListPushBack(SeqList* ps, SLDateType x)               //尾插
{
	assert(ps);
	SLCheckcapacity(ps);
	ps->a[ps->size] = x;
	ps->size += 1;
}

在顺序表的末尾（下标为size处）处插入数据时直接插入，size加一即可。但要考虑顺序表容量空间是否足够，所以要调用扩容函数SLCheckcapacity，扩容函数的实现（供参考）大致时当顺序表的size和capaticy一样时，调用realloc函数二倍扩容。 

ps:尾插函数的参数接收的是上面创建的顺序表s1的地址。

2.2.6.头插 

void SLCheckcapacity(SeqList* ps)                        //扩容
{
	assert(ps);
	if (ps->size == ps->capaticy)
	{
		int newcapaticy = (ps->capaticy == 0) ? 4 : 2 * (ps->capaticy);
		SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * newcapaticy);
		if (tmp == NULL)
		{
			perror("calloc fail");
			return;
		}
		ps->a = tmp;
		ps->capaticy = newcapaticy;
	}
}
void SeqListPushFront(SeqList* ps, SLDateType x)              //头插
{
	assert(ps);
	SLCheckcapacity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

顺序表头部插入数据就是将第二个及以后的数据均后移，在将所需头插数据x插入到顺序表头部，size加一即可，同样要考虑容量问题。

 ps:头插函数的第一个参数接收的是上面创建的顺序表s1的地址，第二个参数是所需头插数据。

2.2.7.头删

void SeqListPopFront(SeqList* ps)                             //头删
{
	assert(ps);
	assert(ps->size > 0);
	int begin = 0;
	while (begin<ps->size-1)
	{
		ps->a[begin] = ps->a[begin+1];
		begin++;
	}
	ps->size--;
}

顺序表删除头部数据也很简单，将第二个及以后的数据均向前覆盖，在将size减一即可。但是需要注意的是，如果size为零的话说明没有数据就不要再删了，用assert断言一下就行。

  ps:这个函数的参数接收的是上面创建的顺序表s1的地址。

2.2.8.尾删 

void SeqListPopBack(SeqList* ps)                              //尾删
{
	assert(ps);
	assert(ps->size >0);
	ps->size--;
}

顺序表尾部删除数据最简单，直接将size减一就行，但和头删一样，用assert断言一下防止删空了。

  ps:这个函数的参数接收的是上面创建的顺序表s1的地址。

2.2.9.顺序表查找

int SeqListFind(SeqList* ps, SLDateType x)                     //顺序表查找
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (x == ps->a[i])
		{
			return i;//找得到返回下标
		}
	}
	return -1;//找不到返回-1
}

我们也许需要在顺序表中查找某个数据，所以遍历这个顺序表的数据即可，找到返回该数据下标，找不到返回-1。

 ps:该函数的第一个参数接收的是上面创建的顺序表s1的地址，第二个参数是所需查找的数据。

 2.2.10.顺序表在下标pos位置插入数据x

void SLCheckcapacity(SeqList* ps)                        //扩容
{
	assert(ps);
	if (ps->size == ps->capaticy)
	{
		int newcapaticy = (ps->capaticy == 0) ? 4 : 2 * (ps->capaticy);
		SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * newcapaticy);
		if (tmp == NULL)
		{
			perror("calloc fail");
			return;
		}
		ps->a = tmp;
		ps->capaticy = newcapaticy;
	}
}
void SeqListInsert(SeqList* ps, int pos, SLDateType x)           //顺序表在下标pos位置插入x
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckcapacity(ps);
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

这个接口的实现大致是将下标pos以后的数据都往后挪，在将所需插入的数据x插入到下标pos的位置，在将size加一即可。但有几处细节要注意：1.pos只能在0和size之间（包括0和size）， 否则就越界访问了，所以利用assert断言一下；2.防止顺序表容量不足，调用扩容函数。

ps:该函数的第一个参数接收的是上面创建的顺序表s1的地址，第二个参数是插入位置的下标，第三个参数是需插入的数据。

2.2.11.顺序表删除下标pos位置的值

void SeqListErase(SeqList* ps, int pos)    // 顺序表删除下标pos位置的值
{
	assert(ps);
	assert(pos >= 0 && pos< ps->size);
	int begin = pos + 1;
	while (begin <= ps->size - 1)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}

这个接口实现大致就是将下标pos以后的数据均向前覆盖，size减一即可，若需删除最后一个（下标为size-1）数据 ，无需覆盖，直接size减一即可。细节：下标pos只能在0到size之间（包括0），否则会越界访问，利用assert断言。

ps：该函数第一个参数接收的是上面创建的顺序表s1的地址，第二个参数是需删除数据的下标。

3.顺序表使用 

咱们顺序表接口就实现完了。可以写一个工程来对接上面的所以接口，以验证顺序表的增删查改及初始化、销毁、打印等功能。鼠鼠我写了一个，可以参考参考哈：

3.1.test.c

#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"
void menu()
{
	printf("**********************\n");
	printf("********0.退出********\n");
	printf("****1.头插  2.头删****\n");
	printf("****3.尾插  4.尾删****\n");
	printf("****5.查找  6.打印****\n");
	printf("*7.在下标pos位置插入值\n");
	printf("*8.删除下标pos位置的值\n");
	printf("**********************\n");
}
int main()
{
	SeqList s1;
	SeqListInit(&s1);
	int input;
	do 
	{
		menu();
		printf("请输入你想操作的数字：->");
		scanf("%d", &input);
		if (input == 0)
		{
			SeqListDestroy(&s1);
			printf("\n");
			break;
		}
		else if (input == 1)
		{
			int number = 0;
			printf("请输入你要头插数据的个数：->");
			scanf("%d", &number);
			printf("请输入你要头插的数据：->");
			while (number--)
			{
				SLDateType x = 0;
				scanf("%d", &x);
				SeqListPushFront(&s1, x);
			}
			printf("\n");
		}
		else if (input == 2)
		{
			SeqListPopFront(&s1);
			printf("\n");
		}
		else if (input == 3)
		{
			int  number = 0;
			printf("请输入你要尾插数据的个数：->");
			scanf("%d", &number);
			printf("请输入你要尾插的数据：->");
			int i = 0;
			for (i = 0; i < number; i++)
			{
				SLDateType x = 0;
				scanf("%d", &x);
				SeqListPushBack(&s1, x);
			}
			printf("\n");
		}
		else if (input == 4)
		{
			SeqListPopBack(&s1);
			printf("\n");
		}
		else if (input == 5)
		{
			SLDateType x = 0;
			printf("请输入你要查找的值：->");
			scanf("%d", &x);
			int flag=SeqListFind(&s1, x);
			if (flag!=-1)
			{
				printf("你要查找的值下标是%d\n", flag);
			}
			else
			{
				printf("找不到！\n");
			}
			printf("\n");
		}
		else if (input == 6)
		{
			SeqListPrint(&s1);
			printf("\n");
		}
		else if (input == 7)
		{
			SLDateType x = 0; int pos = 0;
			printf("请分别输入你要插入的值及插入的下标：->");
			scanf("%d %d", &x, &pos);
			SeqListInsert(&s1,pos,x);
			printf("\n");
		}
		else if (input == 8)
		{
			int pos = 0;
			printf("请输入你要删除值的下标：->");
			scanf("%d", &pos);
			SeqListErase(&s1,pos);
			printf("\n");
		}
		else
		{
			printf("输入错误，请重新输入：->");
		}
	} while (input);
	return 0;
}

3.2.SeqList.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLDateType;

typedef struct SeqList
{
	SLDateType* a;
	int size;                                           //有效数据
	int capaticy;                                       //空间容量
}SeqList;

void SeqListInit(SeqList* ps);                          //初始化

void SeqListDestroy(SeqList* ps);                       //销毁

void SeqListPrint(SeqList* ps);                         //打印

void SeqListPushBack(SeqList* ps, SLDateType x);        //尾插

void SeqListPushFront(SeqList* ps, SLDateType x);       //头插

void SeqListPopFront(SeqList* ps);                      //头删

void SeqListPopBack(SeqList* ps);                       //尾删

int SeqListFind(SeqList* ps, SLDateType x);             //顺序表查找

void SeqListInsert(SeqList* ps, int pos, SLDateType x); // 顺序表在下标pos位置插入x

void SeqListErase(SeqList* ps, int pos);                // 顺序表删除下标pos位置的值

3.3.SeqList.c

#define _CRT_SECURE_NO_WARNINGS 
#include"SeqList.h"


void SLCheckcapacity(SeqList* ps)                        //扩容
{
	assert(ps);
	if (ps->size == ps->capaticy)
	{
		int newcapaticy = (ps->capaticy == 0) ? 4 : 2 * (ps->capaticy);
		SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * newcapaticy);
		if (tmp == NULL)
		{
			perror("calloc fail");
			return;
		}
		ps->a = tmp;
		ps->capaticy = newcapaticy;
	}
}


void SeqListInit(SeqList* ps)                               //初始化
{
	assert(ps);
	ps->a = NULL;
	ps->capaticy = 0;
	ps->size = 0;
}


void SeqListDestroy(SeqList*ps)                              //销毁
{
	assert(ps);
	if (ps->a != NULL)
	{
		ps->a = NULL;
		ps->capaticy = 0;
		ps->size = 0;
	}
}


void SeqListPrint(SeqList* ps)                               //打印
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}


void SeqListPushBack(SeqList* ps, SLDateType x)               //尾插
{
	assert(ps);
	SLCheckcapacity(ps);
	ps->a[ps->size] = x;
	ps->size += 1;
}


void SeqListPushFront(SeqList* ps, SLDateType x)              //头插
{
	assert(ps);
	SLCheckcapacity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}


void SeqListPopFront(SeqList* ps)                             //头删
{
	assert(ps);
	assert(ps->size > 0);
	int begin = 0;
	while (begin<ps->size-1)
	{
		ps->a[begin] = ps->a[begin+1];
		begin++;
	}
	ps->size--;
}


void SeqListPopBack(SeqList* ps)                              //尾删
{
	assert(ps);
	assert(ps->size >0);
	ps->size--;
}


int SeqListFind(SeqList* ps, SLDateType x)                     //顺序表查找
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (x == ps->a[i])
		{
			return i;//找得到返回下标
		}
	}
	return -1;//找不到返回-1
}


void SeqListInsert(SeqList* ps, int pos, SLDateType x)           //顺序表在下标pos位置插入x
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckcapacity(ps);
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}


void SeqListErase(SeqList* ps, int pos)                          // 顺序表删除下标pos位置的值
{
	assert(ps);
	assert(pos >= 0 && pos< ps->size);
	int begin = pos + 1;
	while (begin <= ps->size - 1)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}

 各位读者老爷可以将这三个文件放到一个工程下玩玩哦！

4.小知识累积（与顺序表无关）

4.1.数组越界一定会报错吗？

answer：越界读基本不会报错。越界写可能会报错。越界的检查是一种抽查行为，就像查酒驾一样，比如数组通常会在数组后面设置一些标记位，一旦标记位的 值被更改就会报错，所以一般在数组末尾附近越界写会报错，但越界太远写就基本不报错了（跳过了标记位）。当然不同的编译器对越界的检查不同。这里只是对越界报错的一种认知。

4.2.数组的下标为什么不从1开始而要从0开始呢？ 

因为通过下标访问数组本质是指针访问，数组下标从0开始是要和指针的设计自恰！

a[i]等价于*(a+i)，只有当下标从0开始时，当i=0时，a[0]=*(a+0)才解释得通。

5.ending

鼠鼠我才疏学浅，且时间紧迫，如有不足，恳请斧正，谢谢哈哈哈！

懂我意思吧？