【数据结构】--顺序表的实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】--顺序表的实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、顺序表的概念

什么是顺序表？顺序表（SeqList）是线性表中的一类。而线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、字符串、栈、队列... 注意：线性表在逻辑上是线性结构，也就是说是一条连续的直线。但在物理结构上不一定是连续的。（这里很好理解，例如有10个人在买蜜雪冰城，在逻辑上应该是10个人按照先后顺序排成一队一个一个买，突然这10个人中的一个人的朋友也要买蜜雪冰城，但是他不想排队，他就站在他朋友的旁边一起买。这就是在物理上不一定连续。）

而顺序表是用一组地址连续的存储单元依次存储线性表中的数据元素。顺序表在逻辑结构是线性的结构，在物理结构上是连续的。它的底层是基于数组来实现的，所以顺序表的实现其实是在数组上完成数据的增删查改。

二、顺序表的分类

1、静态顺序表

定义：使用定长数组存储数据

//静态顺序表
typedef int SLDataType;
#define N 6
typedef struct SeqList
{
    SLDataTyppe arr[N];//定长数组
    int size;//有效数据个数
}SL;

2、动态顺序表（推荐使用）

定义：按需申请容量大小

//动态顺序表

//顺序表不仅可以插入整形数据，还可以插入浮点型，char型等等
//所以我们给int重新定义一个名字SLDataType,后面如果想要换数据类型，直接更改typedef后面的int就好了
typedef int SLDataType;

typedef struct SeqList
{
    SLDataType* arr;//一级指针指向的动态开辟的数组
    int size;//有效数据个数
    int capacity;//数组的容量大小
}SL;

在这里我推荐使用动态顺序表。静态顺序表如果空间给少了不够用，给多了会造成空间浪费。动态顺序表可以根据需要的多少来调整顺序表的大小。

三、动态顺序表的实现

1、定义一个动态顺序表

//动态顺序表
typedef int SLDataType;

typedef struct SeqList
{
    SLDataType* arr;//一级指针指向的动态开辟的数组
    int size;//有效数据个数
    int capacity;//数组的容量大小
}SL;

2、对动态顺序表进行初始化

//初始化顺序表
void SeqListInit(SL* ps)
{
	assert(ps);//断言ps指针不能是空指针
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

3、对顺序表进行扩容

扩容思路：

（1）判断顺序表的空间容量是否足够？当顺序表的数据个数==空间容量时表示顺序表的空间容量已经满了，需要进行扩容。

（2）用三目表达式来判断，如果顺序表的空间容量为0，则先给空间容量为4（这个数值是随便设置）；如果空间容量不为0，则让空间容量以2倍的数量进行增加。（这样可以在扩容的同时减少空间的浪费）

（3）用realloc进行动态空间的扩容。

（4）检查realloc是否扩容成功并用一个临时指针temp来接收，若temp不为空，则将temp赋值给ps->arr,并将新的空间容量newcapacity赋值给capacity。

//扩容
void SLCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->capacity == ps->size)
	{
		//扩容
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* temp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
		if (temp == NULL)
		{
			perror("realloc fail!");
			exit(1);//直接退出程序不在执行
		}
		ps->arr = temp;
		ps->capacity = newcapacity;
	}
}

4、打印顺序表

顺序表的底层是数组，所以打印顺序表就相当于打印数组，这里非常简单所以直接上代码

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

5、顺序表尾插数据

顺序表尾插就是在数组里size这个位置插入数据，所以需要注意的当插入完数据之后不要忘了size++。

【数据结构】--顺序表的实现,数据结构,数据结构

例如这里尾插一个4，在ps->arr[ps->size]这个位置插入完数据之后，ps->size要往后移动一位。

//尾插
void SeqListPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	//判断是否需要扩容
	SLCheckCapacity(ps);
	ps->arr[ps->size] = x;
	ps->size++;
}

6、顺序表头插数据

顺序表头插其实就是在数组的下标为0的位置插入数据，所以我们需要先把顺序表里面的数据从后往前依次向后移动一位，把下标为0的位置空出来在插入数据。

【数据结构】--顺序表的实现,数据结构,数据结构

例如我想头插一个5，所以我需要先把1,2,3,4四个数据从后往前依次往后移动一位，然后插入5。

//头插
void SeqListPushFront(SL* ps,SLDataType x)
{
	assert(ps);
	//判断是否需要扩容
	SLCheckCapacity(ps);
	int i = 0;
	for (i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}

7、顺序表尾删数据

顺序表尾删数据就非常简单了，只需要让ps->size--,size向前移动一位就好了。但需要注意的一点是必须要判断一下ps->size是否大于0，因为顺序表里必须要有数据才能够做删除操作。这里直接上代码。

//尾删
void SeqListPopBack(SL* ps)
{
	assert(ps);
	//这里有两种方法来判断ps->size是否>0
	//第一种方法比较温柔
	//if (ps->size == 0)
	//{
		//return;
	//}
	//第二种方法比较简单粗暴
	assert(ps->size > 0);
	ps->size--;
}

8、顺序表头删数据

头删操作也非常的easy，头删只需要把顺序表里从下标为1的数据开始依次往前移动一位，同时也要判断ps->size是否大于0，以及删除一个数据要让ps->size--。

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

9、顺序表查找数据

顺序表查找就是通过遍历数组来比较数组里的数据与已知要查找的数据是否相等。若相等，则返回数组下标，若不相等，则返回-1表示所查找的数据不存在。

//查找顺序表
int SeqListFind(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;
}

10、在指定位置（pos）插入数据

在指定位置插入数据，首先我们需要通过SeqListFind函数接口来得到需要插入数据的位置下标，接着我们要把从pos到ps->size-1位置上的数据从后往前向后移动一位，把pos 位置空出来，最后在pos位置插入数据。

【数据结构】--顺序表的实现,数据结构,数据结构

例如，我想要在2这个位置插入100，首先把2,3,4三个数据从后往前依次向后移动一位，然后在pos位置插入100。

//指定位置插入数据
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	//pos必须是有效的数据下标
	assert(pos >= 0 && pos < ps->size);
	//判断是否需要扩容
	SLCheckCapacity(ps);
	int i = 0;
	for (i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

11、在指定位置（pos）删除数据

这里就很简单了，只需要让pos位置之后的数据整体向前移动一位就好了。

//指定位置删除数据
void SeqListErase(SL* ps, int pos)
{
	assert(ps);
	//pos必须是有效的数据下标
	assert(pos >= 0 && pos < ps->size);
	int i = 0;
	for (i = pos; i < ps->size; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

12、销毁顺序表

//销毁顺序表
void SeqListDestroy(SL* ps)
{
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

四、完整代码

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 SeqListInit(SL* ps);
//销毁顺序表
void SeqListDestroy(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//打印顺序表
void SeqListPrint(SL* ps);
//尾插
void SeqListPushBack(SL* ps, SLDataType x);
//头插
void SeqListPushFront(SL* ps);
//尾删
void SeqListPopBack(SL* ps);
//头删
void SeqListPopFront(SL* ps);
//查找顺序表
int SeqListFind(SL* ps, SLDataType x);
//指定位置之前插入数据
void SeqListInsert(SL* ps, int pos, SLDataType x);
//指定位置删除数据
void SeqListErase(SL* ps, int pos);

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"

//初始化顺序表
void SeqListInit(SL* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

//销毁顺序表
void SeqListDestroy(SL* ps)
{
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

//扩容
void SLCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->capacity == ps->size)
	{
		//扩容
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* temp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
		if (temp == NULL)
		{
			perror("realloc fail!");
			exit(1);//直接退出程序不在执行
		}
		ps->arr = temp;
		ps->capacity = newcapacity;
	}
}

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

//尾插
void SeqListPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	//判断是否需要扩容
	SLCheckCapacity(ps);
	ps->arr[ps->size] = x;
	ps->size++;
}

//头插
void SeqListPushFront(SL* ps,SLDataType x)
{
	assert(ps);
	//判断是否需要扩容
	SLCheckCapacity(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 SeqListPopBack(SL* ps)
{
	assert(ps);
	//这里有两种方法来判断ps->size是否>0
	//第一种方法比较温柔
	//if (ps->size == 0)
	//{
		//return;
	//}
	//第二种方法比较简单粗暴
	assert(ps->size > 0);
	ps->size--;
}

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

//查找顺序表
int SeqListFind(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 SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	//pos必须是有效的数据下标
	assert(pos >= 0 && pos < ps->size);
	//判断是否需要扩容
	SLCheckCapacity(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 SeqListErase(SL* ps, int pos)
{
	assert(ps);
	//pos必须是有效的数据下标
	assert(pos >= 0 && pos < ps->size);
	int i = 0;
	for (i = pos; i < ps->size; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

test.c

测试文件可以自己写，这里仅供参考。

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"

void test()
{
	SL s;
	SeqListInit(&s);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPrint(&s);
	//SeqListPushFront(&s, 5);
	//SeqListPrint(&s);
	//SeqListPopBack(&s);
	//SeqListPrint(&s);
	//SeqListPopFront(&s);
	//SeqListPopFront(&s);
	//SeqListPopFront(&s);
	//SeqListPopFront(&s);
	//SeqListPopFront(&s);
	//SeqListPrint(&s);
	int find = SeqListFind(&s, 2);
	if (find < 0)
	{
		printf("所查找的数据不存在！\n");
	}
	else
	{
		printf("所查找的数据存在，该数据所在位置下标为%d\n", find);
	}
	SeqListInsert(&s, find, 100);
	SeqListPrint(&s);
	SeqListErase(&s, find);
	SeqListPrint(&s);
}

int main()
{
	test();
	return 0;
}

这是关于数据结构的第一篇博客，后期我会持续更新数据结构以及C语言的相关内容。欢迎大家在评论区相互讨论以及指出我的不足，我会在后面的文章中参考大家的建议来写出更好的博客。

感谢大家点赞+关注，来跟着我一起学习吧！

文章来源地址https://www.toymoban.com/news/detail-854972.html

到了这里，关于【数据结构】--顺序表的实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！