数据结构：手撕代码——顺序表

目录

 

1.线性表

2.顺序表

2.1顺序表的概念

2.2动态顺序表实现

 2.2-1 动态顺序表实现思路

2.2-2 动态顺序表的初始化

 2.2-3动态顺序表的插入

检查空间

 尾插

头插 

中间插入 

2.2-4 动态顺序表的删除 

尾删

头删 

中间删除 

2.2. 5 动态顺序表查找与打印、销毁

查找

打印 

销毁 

 2.2 6 测试动态顺序表

---

1.线性表

    线性表（linear list）是n个具有相同特性的数据元素的有限序列。例如我们有一个数组，这个数组中的元素都占相同大小的内存，都具有相同的类型，而它们也按顺序排列的。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

     线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。什么意思呢？逻辑结构可以看作我们把它想象成一个排列有序的数组：

  

物理结构就是这个表实际在内存的结构，它有可能是一个排列有序的数组，但是更大的可能是用指针连起来的无序的一块块空间：

2.顺序表

2.1顺序表的概念

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

顺序表一般可以分为：
1. 静态顺序表：使用定长数组存储元素。

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

     那么二者哪个更具有优势呢？答案是动态顺序表，如果我们使用静态顺序表去存储某个app的用户数据，那么我们该用多少空间呢，如果空间太少，我们就会丢失一部分用户的数据，如果空间太大，又会浪费内存，而使用动态顺序表则不用考虑这两个问题，如果我们空间太小就增加内存，而一开始我们不会开辟太大的内存，所以不用担心空间浪费的问题，所以我们本期就要用代码实现动态顺序表。

2.2动态顺序表实现

  我们要实现顺序表，需要实现它的增删查改等功能：

typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
SLDataType* array; // 指向动态开辟的数组
size_t size ;
// 有效数据个数
size_t capicity ;
// 容量空间的大小
}SeqList;
// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* psl);
// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl);
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* psl);
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* psl);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 顺序表打印
void SeqListPrint(SeqList* psl)

接下来我们来一个一个实现吧。

 2.2-1 动态顺序表实现思路

    我们需要实现顺序表的增删查改等功能，包含十几个方法，为了避免代码混乱等问题，我们将顺序表分成三个文件来实现（1）test.c，这个文件负责我们实现接口之后的测试，（2）SeqList.h，这个文件负责包含所有头文件和放置所有的函数声明，如果另外两个文件要使用这些头文件只需要包含这个文件就可以了，（3）SeqList.h，这个文件负责实现所有方法（函数）的功能，我们顺序表的大部分代码也是在这个文件。

2.2-2 动态顺序表的初始化

     有了思路之后我们就来实现我们的代码。首先我们创建三个文件：

在SeqList文件中包含我们要用到的头文件，输入输出需要用到stdio.h,开辟内存的函数需用到stdlib.h，我们还会用到断言（assert.h),为了避免多次包含头文件以免不必要的内存浪费，我们还会用到#pragma once 这段代码：

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

接下来我们创建一个顺序表，我们用一个结构体来表示这个顺序表并用typedef将它更名为SL：

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

那么存储数据的类型为什么也要改名呢？因为我们将来如果使用顺序表存储数据时，我们并不知道我们存何种类型的数据，如果我们存储的数据是int，而要将它们全部换成字符类型，此时恰好我们已经写了100000行代码，我们要修改的化会变得相当困难，所以我们将数据类型改名是为了方便以后我们要存储不同类型数据时可以很方便的更换类型。

我们来实现第一个方法——初始化，在开始时我们将它们都初始化为0：

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

 2.2-3动态顺序表的插入

    我们使用顺序表最主要的功能就是存储数据，而在一开始顺序表是没有数据的，所以我们先实现插入功能，插入分为：尾插，头插，从中间插入。尾插就是在最后一个有效数据后插入我们要插入的数据：

例如这个顺序表有三个有效数据，那么我们的尾插就是将它放在最后一个有效数据（3）的后面，如果我们将数字4用尾插的方式插入顺序表，那么就是这样：

头插则与尾插刚好相反，它是将要插入的数据放在有效数据的最前面，而使其他数据整体往后移一位，假设我们要用头插插入数字0：

使用中间插入我们可以指定插入的位置，如果我们要将数字6插入到3的位置，我们只需要将这个位置后的所有有效数据都往后挪一位：

接下来我们用代码实现。

检查空间

       使用插入前，我们需要为顺序表开辟一块空间，我们在空间上会遇到两个问题：如果我们是第一次进来，所有数据都为0，那么我们要第一次开辟内存；如果我们要存入数据时，内存不足，则需要新开辟内存。这两种情况都有一个共同点——有效数据与空间大小相等，所以只要有序数据和空间大小相等时我们就增加1倍空间，在进入函数时，我们先判断这个指针是不是为空，如果我们向空指针存入数据，则一点会出错，代码实现：

void SeqCheckcapa(SL* ps)//检查内存够不够，不够则增加
{
	assert(ps);
	if (ps->capacity == ps->size)
	{
		int Newcapecity = ps->capacity == 0 ? 4 : 2 * ps->capacity * sizeof(SLDataType);
		SLDataType* tem = (SLDataType*)realloc(ps->arr, Newcapecity * 2 *sizeof(SLDataType));
		if (tem != NULL)
		{
			ps->arr = tem;
		}
	}
}

 尾插

  我们使用尾插前先判断我们的空间够不够，传入的指针是否为空。那么我们如何插入呢？我们顺序表中的有效数据是size个，而最后一个有效数据的下标是size-1，我们只需要在下标为size的位置插入数据，然后size加1，就完成了尾插的操作：

void SeqPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SeqCheckcapa(ps);
	
	ps->arr[ps->size++] = x;
 
}//尾插

画图演示：

头插 

  头插前面做的事和尾插一样，先判断指针是不是为空，再判断空间够不够。然后将所有数据往后移一位，最后在下标为0的位置插入数据，size加1：

void SeqPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SeqCheckcapa(ps);
	int i = 0;
	for (i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	} 
	ps->arr[0] = x;
	++ps->size;
}//头插

中间插入 

先判断指针是否为空和判断空间够不够。因为中间插入是指定位置进行插入，所以我们只能在已经有的数据中间插入，我们指定的数字不能小于0，也不能大于size。当我们指定了一个有效数字pos下标，我们将这个位置及它后面的所有数据往后挪一位，此时这个位置就空出来了，我们也就可以插入我们想插入的数字，插入之后，我们让size加1：

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SeqCheckcapa(ps);
 
	int i = 0;
	for (i = ps->size ; i>pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	++ps->size;
 
}//指定下标前插入数据

2.2-4 动态顺序表的删除 

删除同样分为尾删，头删，中间删除，这部分内容比插入相对简单一点。

尾删

 我们先判断指针是否为空，再判断有效数据的情况，如果有效数据为0，我们就不能删除数据。而删除数据，只需要让size往前挪动一位，我们打印时不会打印这个数据，而插入数据时会将这个数据覆盖：

void SeqPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size >= 0);
 
	ps->size--;
}//尾删

头删 

与尾删一样，先判断指针是否为空，再判断数据情况。头删操作只需将第二位及后面的所以数据往前移动一位，将第一位数据覆盖，最后让size减1就可以了：

代码实现：

void SeqPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size >= 0);
	int i = 0;
	for (i = 0; i <ps->size-1 ; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
 
}//头删

中间删除 

  先判断指针是否为空，再判断有效数据的情况。因为中间删除是指定位置删除，那么这个制定的数字肯定不能小于0，也不能大于等于size，而删除操作与头删相似，我们指定好数字后，只需要将它后面的所有有效数据往前挪动一位将它覆盖然后让size减1就可以了：

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	int i = 0;
	for (i = pos; i<ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
 
	}
	ps->size--;
}//指定下标删除

2.2. 5 动态顺序表查找与打印、销毁

查找

查找数据我们先判断指针是否为空。使用循环判断顺序表中是否有我们要查找的数据，如果找到了，则返回它的下标，如果找不到，则返回-1：

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

我们使用一个整型来接收，如果大于0，说明找到了，并打印它的下标，如果小于0，则表示顺序表中没有这个数据：

int find = SLFind(&sl, 4);
if (find < 0)
{
	printf("没有找到！\n");
}
else
{
	printf("找到了，下标是%d\n", find);
}

打印 

打印顺序表中的数据要先判断指针是否为空。接着使用循环将它的内容打印出来：

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

销毁 

 当使用完这块动态开辟出来的空间，不要忘了释放，以免造成内存泄漏和出现野指针的情况：

void SeqDestroy(SL* ps)
{
	assert(ps);
	free(ps->arr);
 
	if (ps->arr != NULL);
	{
		ps->arr = NULL;
	}
	ps->capacity = ps->size = 0;
}
//销毁

至此所有方法就实现完成了。 

 2.2 6 测试动态顺序表

  我们来测试一下其中一些方法：

void test2()
{
	SL sl;
	SeqInit(&sl);
	//插入1 2 3 4
	SeqPushBack(&sl, 1);
	SeqPushBack(&sl, 2);
	SeqPushBack(&sl, 3);
	SeqPushBack(&sl, 4);
	SeqPrint(&sl);
 
	//插入99 99
	SLInsert(&sl, 0, 99);
	SLInsert(&sl, 3, 88);
	SLInsert(&sl, sl.size, 10000);
 
	SeqPrint(&sl);
 
	//删除
	SLErase(&sl,2);
	SeqPrint(&sl);
	SLErase(&sl, 5);
	SeqPrint(&sl);
 
	//查找
	int find = SLFind(&sl, 4);
	if (find < 0)
	{
		printf("没有找到！\n");
	}
	else
	{
		printf("找到了，下标是%d\n", find);
	}
	//释放空间
	SeqDestroy(&sl);
}

来看运行结果：

可以看到我们实现的方法都没有问题，我将原码放在下面，感兴趣的小伙伴可以试试哦。

SeqList.h ：

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
 
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;
	int size;//有效数据
	int capacity;//空间大小
	
}SL;
 
void SeqInit(SL* ps);//初始化
 
void SeqDestroy(SL* ps);//销毁
 
void SeqPushBack(SL* ps, SLDataType x);//尾插
 
void SeqPushFront(SL* ps, SLDataType x);//头插
 
void SeqPopBack(SL* ps);//尾删
 
void SeqPopBack(SL* ps);//头删
 
void SeqPrint(SL* ps);//打印
 
void SLErase(SL* ps, int pos);//指定删除
 
int SLFind(SL* ps, SLDataType x);//查找数据
 
//指定下标前插入数据
void SLInsert(SL* ps,int pop, SLDataType x);
 
 
 
 
 
 

SeqList.c :

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
 
 
 
void SeqInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}//初始化
 
void SeqCheckcapa(SL* ps)//检查内存够不够，不够则增加
{
	assert(ps);
	if (ps->capacity == ps->size)
	{
		int Newcapecity = ps->capacity == 0 ? 4 : 2 * ps->capacity * sizeof(SLDataType);
		SLDataType* tem = (SLDataType*)realloc(ps->arr, Newcapecity * 2 *sizeof(SLDataType));
		if (tem != NULL)
		{
			ps->arr = tem;
		}
	}
}
 
 
void SeqPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SeqCheckcapa(ps);
	
	ps->arr[ps->size++] = x;
 
}//尾插
 
void SeqPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SeqCheckcapa(ps);
	int i = 0;
	for (i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	} 
	ps->arr[0] = x;
	++ps->size;
}//头插
 
void SeqPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size >= 0);
 
	ps->size--;
}//尾删
 
void SeqPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size >= 0);
	int i = 0;
	for (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);
	SeqCheckcapa(ps);
 
	int i = 0;
	for (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);
	int i = 0;
	for (i = pos; i<ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
 
	}
	ps->size--;
}//指定下标删除
 
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}//查找数据
void SeqPrint(SL* ps)
{
	assert(ps);
	int i = 0;
 
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}//打印
 
 
 
void SeqDestroy(SL* ps)
{
	assert(ps);
	free(ps->arr);
 
	if (ps->arr != NULL);
	{
		ps->arr = NULL;
	}
	ps->capacity = ps->size = 0;
}
//销毁

test.c :

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
//void SLPushBack(SL* ps, SLDatatype x)
//{
//	assert(ps);
//
//	if (ps->size == ps->capacity)
//	{
//		int Newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
//
//		SLDatatype* tem=(SLDatatype*)realloc(ps->arr,2* Newcapacity*sizeof(SLDatatype))
//			if (tem == NULL)
//			{
//				perror("realloc");
//				exit(1);
//			}
//
//		ps->arr = tem;
//		ps->capacity = Newcapacity;
//	}
//	ps->arr[size++] = x;
//
//}
//
//
//
//
//void SLPushBack(SL* ps, SLDataType x)
//{
//	//1.判断指针是否为空，为空则出错
//	assert(ps);
//
//	//2.判断空间够不够，不够则申请空间
//	if (ps->capecity == ps->size)
//	{
//		//如果capecity为0，我们就要第一次开辟出4个SLDataType类型的空间
//		SLDataType NewCapecity = ps->capecity == 0 ? 4 : 2 * ps->capecity;
//		//开辟空间，如果下次空间不够，则下次开辟此次2倍的空间
//		SLDataType* tem = (SLDataType*)realloc(ps->arr, NewCapecity * 2 * sizeof(SLDataType));
//		if (tem == NULL)
//		{
//			perror("realloc");
//			exit(1);
//		}
//		//走到这里说明tem不为空，将新开辟好的内存给arr
//		ps->arr = tem;
//		ps->capecity = NewCapecity;
//	}
//	ps->arr[ps->size++] = x;
//	//3.进行尾插操作
//}
void test1()
{
	SL sl;
	SeqInit(&sl);
	
	SeqPushBack(&sl, 1);
	SeqPushBack(&sl, 2);
	SeqPushBack(&sl, 3);
	SeqPushBack(&sl, 4);
	SeqPrint(&sl);
 
	SeqPushFront(&sl, 6);
	SeqPrint(&sl);
 
	SeqPopBack(&sl);
	SeqPrint(&sl);
 
	SeqPopFront(&sl);
	SeqPopFront(&sl); 
	SeqPopFront(&sl); 
	
	SeqPrint(&sl);
 
 
	SeqDestroy(&sl);
}
void test2()
{
	SL sl;
	SeqInit(&sl);
	//插入1 2 3 4
	SeqPushBack(&sl, 1);
	SeqPushBack(&sl, 2);
	SeqPushBack(&sl, 3);
	SeqPushBack(&sl, 4);
	SeqPrint(&sl);
 
	//插入99 99
	SLInsert(&sl, 0, 99);
	SLInsert(&sl, 3, 88);
	SLInsert(&sl, sl.size, 10000);
 
	SeqPrint(&sl);
 
	//删除
	SLErase(&sl,2);
	SeqPrint(&sl);
	SLErase(&sl, 5);
	SeqPrint(&sl);
 
	//查找
	int find = SLFind(&sl, 4);
	if (find < 0)
	{
		printf("没有找到！\n");
	}
	else
	{
		printf("找到了，下标是%d\n", find);
	}
	//释放空间
	SeqDestroy(&sl);
}
int main()
{
	test2();
	//test1();
	return 0;
}