1. Toy模板网首页
  2. > Toy博客

【数据结构】顺序表基本操作的实现（C语言）

9月前 作者：不 良 分类：Toy博客 阅读(55) 违法举报

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

🚀 作者简介：一名在后端领域学习，并渴望能够学有所成的追梦人。
🐌 个人主页：蜗牛牛啊
🔥 系列专栏：🛹数据结构、🛴C++
📕 学习格言：博观而约取，厚积而薄发
🌹 欢迎进来的小伙伴，如果小伙伴们在学习的过程中，发现有需要纠正的地方，烦请指正，希望能够与诸君一同成长！ 🌹

一、认识顺序表

1.线性表

线性表是n个具有相同特性的数据元素的有限序列，线性表是一种在实际中广泛使用的数据结构，常见的线性表有顺序表、链表、栈、队列、字符串……线性表在逻辑上是线性结构，也就是说是一条连续的直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式来存储。

【数据结构】顺序表基本操作的实现（C语言）,数据结构,数据结构,c语言,顺序表
【数据结构】顺序表基本操作的实现（C语言）,数据结构,数据结构,c语言,顺序表

2.顺序表的概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删改查。顺序表一般可分为：静态顺序表和动态顺序表（使用动态开辟的数组存储）。

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

#define MAX 10
typedef int SLDataType;//当存储数据类型改变时，方便修改
typedef struct SeqList
{
	SLDataType arr[MAX];//用来存储数据
	int size;//用来记录数组中存储有效数据元素的个数
}SL;

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

//动态顺序表
typedef int SLDataType;//当存储数据类型改变时，方便修改
typedef struct SeqList
{
	SLDataType* arr;//指向动态开辟的数组
	int size;//用来记录数组中存储有效数据元素的个数
	int capacity;//用来记录容量大小
}SL;

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

二、顺序表的基本操作（接口实现）

1.初始化顺序表

void SLInit(SL* ps)
{
	assert(ps);//不为空指针
	ps->arr = NULL;//刚开始指向空指针
	ps->size = ps->capacity = 0;//有效数据个数和容量都为0
}

初始化时设置其有效数据个数和容量都为0，指针指向NULL，断言assert(ps)，避免在定义结构体变量时写为SL* sl=NULL。

函数形参应该是结构体的指针，不能够直接传递结构体本身，因为传值传参，形参的改变不会影响实参。传递结构体指针可以通过对结构体地址解引用来修改结构体本身。

2.打印顺序表

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

3.尾插

void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		int NewCapacity =ps->capacity == 0 ? 4 : 2 * ps->capacity;//判断刚开始是否有空间
		SLDataType* tmp = (SLDataType*)realloc(ps->arr,sizeof(SLDataType) * NewCapacity);//开空间
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		ps->arr = tmp;
		ps->capacity = NewCapacity;
	}
	ps->arr[ps->size] = x;
	ps->size++;
}

尾插就是在尾部插入数据，因为刚开始的时候没有给数组分配空间，所以要考虑当没有空间时要去申请空间，realloc函数是扩容函数，在指针为空的情况下作用和malloc相同，int NewCapacity =ps->capacity == 0 ? 4 : 2 * ps->capacity判断当前容量大小并确定要开辟的空间大小。
SLDataType* tmp = (SLDataType*)realloc(ps->arr,sizeof(SLDataType) * NewCapacity)，用来在堆内存中开辟空间，realloc之后注意将其强制转化成SLDataType*类型。当成功开辟空间之后赋给ps->arr，同时注意将NewCapacity赋给ps->capacity。

4.尾删

void SLPopBack(SL* ps)
{
	assert(ps);
	//暴力的检查
	assert(ps->size > 0);//判断ps->size是否大于0，当等于0时再删的话ps->size就会变为-1，越界
	//温柔的检查
	//if (ps->size == 0)
	//{
	//	return;
	//}
	ps->size--;
}

当ps->size等于0时直接返回，如果不返回，造成ps->size为负数，造成数组越界，当我们再次插入数据的时候可能会出现报错，同时当越界时可能不会报错，但是可能会在free时候报错。所以要用assert(ps->size > 0)检查ps->size大小，等于0时直接退出，并提示。
扩展：free时候报错可能的错误原因有两种，一是free时候指针不正确，可能是野指针，同时释放的时候必须从起始位置释放。二是越界时候free会报错。当越界读数组的时候基本不会被检查出来报错，但是改变它的值的时候就可能会报错，是一种抽查行为，是在运行时检查。

5.扩容

void SLCheckCapacity(SL* ps)
{
	assert(ps);
	//检查是否需要扩容
	if (ps->size == ps->capacity)
	{
		int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * NewCapacity);
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		ps->capacity = NewCapacity;
		ps->arr = tmp;
	}
}

扩容函数，用于检查数组空间大小是否适合继续插入，当数组空间不足时进行扩容，定义此函数之后可以对上面尾插函数进行简化，如下：

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

6.头插

void SLPushFront(SL* ps, SLDataType x)
{
	SLCheckCapacity(ps);
	int end = ps->size;
	//挪动数据
	while (end > 0)
	{
		ps->arr[end] = ps->arr[end-1];
		end--;
	}
	ps->arr[0] = x;
	ps->size++;
}

利用扩容函数对其检查，注意控制循环结束条件。

7.头删

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	int begin = 0;
	while (begin < ps->size-1)
	{
		ps->arr[begin] = ps->arr[begin + 1];
		begin++;
	}
	ps->size--;
}

注意判断当ps->size等于0时不能再进行ps->size--，要加上一条判断语句assert(ps->size > 0)。

8.任意位置插入

void SLInsert(SL* ps, int pos, SLDataType x)//任意位置插入
{
	assert(ps);
	assert(pos >= 0);
	assert(pos <= ps->size);
	SLCheckCapacity(ps);
	int end = ps->size;
	while (end > pos)
	{
		ps->arr[end] = ps->arr[end - 1];
		end--;
	}
	ps->arr[pos] = x;
	ps->size++;
}

pos是数组下标，同时注意判断pos的范围。

9.任意位置删除

void SLErase(SL* ps, int pos)//任意位置删除
{
	assert(ps);
	assert(pos >= 0);
	assert(pos < ps->size);
	while (pos < ps->size-1)
	{
		ps->arr[pos] = ps->arr[pos + 1];
		pos++;
	}
	ps->size--;
}

pos表示的是数组下标，有assert(pos >= 0)和assert(pos <= ps->size)两个判断条件之后不用再加assert(ps->size>0)，因为当ps->size等于0时，assert(pos <= ps->size)会报错。

10.查找某个数的位置

int SLFind(SL* ps, SLDataType x)//返回类型为int,是数组下标
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
			return i;
	}
	return -1;
}

返回值是数组下标。

思考：当我们想删除某个值时应该怎么做？当被删除的值有多个时又要怎么做呢？
我们可以通过下面的代码实现：

int SLNFind(SL* ps, SLDataType x, int begin)//begin是开始查找的位置
{
	assert(ps);
	int i = 0;
	for (i = begin; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
			return i;
	}
	return -1;
}

三、顺序表演示及代码（含源码）

1.演示效果

【数据结构】顺序表基本操作的实现（C语言）,数据结构,数据结构,c语言,顺序表文章来源地址https://www.toymoban.com/news/detail-603833.html

2.完整源代码

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
//动态顺序表
typedef int SLDataType;//当存储数据类型改变时，方便修改
typedef struct SeqList
{
	SLDataType* arr;//指向动态开辟的数组
	int size;//用来记录数组中存储有效数据元素的个数
	int capacity;//用来记录容量大小
}SL;
void SLInit(SL* ps)//初始化顺序表
{
	assert(ps);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}
void SLCheckCapacity(SL* ps)//检查是否需要扩容
{
	assert(ps);
	//检查是否需要扩容
	if (ps->size == ps->capacity)
	{
		int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * NewCapacity);
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		ps->capacity = NewCapacity;
		ps->arr = tmp;
	}
}
void SLPushBack(SL* ps, SLDataType x)//尾插
{
	SLCheckCapacity(ps);//检查是否需要扩容
	//assert(ps);
	//if (ps->size == ps->capacity)
	//{
	//	int NewCapacity =ps->capacity == 0 ? 4 : 2 * ps->capacity;//判断刚开始是否有空间
	//	SLDataType* tmp = (SLDataType*)realloc(ps->arr,sizeof(SLDataType) * NewCapacity);
	//	if (tmp == NULL)
	//	{
	//		perror("realloc");
	//		exit(-1);
	//	}
	//	ps->arr = tmp;
	//	ps->capacity = NewCapacity;
	//}
	ps->arr[ps->size] = x;
	ps->size++;
}
void SLPrint(SL* ps)//打印
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}
void SLDestroy(SL* ps)//销毁
{
	assert(ps);
	if (ps->arr != NULL)
	{
		free(ps->arr);
		ps->arr = NULL;
	}
	ps->size = ps->capacity = 0;
}
void SLPopBack(SL* ps)//尾删
{
	assert(ps);
	//暴力的检查
	assert(ps->size > 0);//判断ps->size是否大于0，当等于0时再删的话ps->size就会变为-1，越界
	//温柔的检查
	if (ps->size == 0)
	{
		return;
	}
	ps->size--;
}
void SLPushFront(SL* ps, SLDataType x)//头插
{
	SLCheckCapacity(ps);
	int end = ps->size;
	//挪动数据
	while (end > 0)
	{
		ps->arr[end] = ps->arr[end - 1];
		end--;
	}
	ps->arr[0] = x;
	ps->size++;
}
void SLPopFront(SL* ps)//头删
{
	assert(ps);
	assert(ps->size > 0);
	int begin = 0;
	while (begin < ps->size - 1)
	{
		ps->arr[begin] = ps->arr[begin + 1];
		begin++;
	}
	ps->size--;
}
void SLInsert(SL* ps, int pos, SLDataType x)//任意位置插入
{
	assert(ps);
	assert(pos >= 0);
	assert(pos <= ps->size);
	SLCheckCapacity(ps);
	int end = ps->size;
	while (end > pos)
	{
		ps->arr[end] = ps->arr[end - 1];
		end--;
	}
	ps->arr[pos] = x;
	ps->size++;
}
void SLErase(SL* ps, int pos)//任意位置删除
{
	assert(ps);
	assert(pos >= 0);
	assert(pos < ps->size);
	while (pos < ps->size - 1)
	{
		ps->arr[pos] = ps->arr[pos + 1];
		pos++;
	}
	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;
}
int SLNFind(SL* ps, SLDataType x, int begin)//从begin开始查找某个数
{
	assert(ps);
	int i = 0;
	for (i = begin; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
			return i;
	}
	return -1;
}
void menu()//菜单函数
{
	printf("********************************\n");
	printf("**   1.尾插      2.尾删       **\n");
	printf("**   3.头插      4.头删       **\n");
	printf("**   5.任意位置插入           **\n");
	printf("**   6.任意位置删除           **\n");
	printf("**   7.查找某个数并返回其下标 **\n");
	printf("**   8.删除某个数             **\n");
	printf("**   9.打印                   **\n");
	printf("**   0.退出程序               **\n");
}
int main()
{
	int input = 0;
	int ret = 0;
	int pos = 0;
	SL sl;
	SLInit(&sl);
	do {
		menu();
		printf("请选择：");
		scanf("%d", &input);
		switch (input)
		{
		case 1:
			printf("请输入你要尾插的值，以-1结束：");
			scanf("%d", &ret);
			while (ret != -1)
			{
				SLPushBack(&sl, ret);
				scanf("%d", &ret);
			}
			printf("尾插成功！\n");

			break;
		case 2:
			SLPopBack(&sl);
			printf("尾删成功！\n");
			break;
		case 3:
			printf("请输入你要头插的值，以-1结束：");
			scanf("%d", &ret);
			while (ret != -1)
			{
				SLPushFront(&sl, ret);
				scanf("%d", &ret);
			}
			printf("头插成功！\n");
			break;
		case 4:
			SLPopFront(&sl);
			printf("头删成功！\n");
			break;
		case 5:
			printf("请输入你想插入的位置和数值：");
			scanf("%d%d", &pos, &ret);
			SLInsert(&sl, pos - 1, ret);
			printf("插入成功！\n");
			break;
		case 6:
			printf("请输入你想删除的位置：");
			scanf("%d", &pos);
			SLErase(&sl, pos - 1);
			printf("删除成功！\n");
			break;
		case 7:
			printf("请输入你想要查找的数：");
			scanf("%d", &ret);
			int s = SLFind(&sl, ret);
			printf("查找的数的数组下标为:%d！\n", s);
			break;
		case 8:
			printf("请输入你要删除的数值：");
			scanf("%d", &ret);
			int tmp = SLNFind(&sl, ret, 0);
			while (tmp != -1)
			{
				SLErase(&sl, tmp);
				tmp = SLNFind(&sl, ret, tmp);
			}
			printf("删除成功！\n");
			break;
		case 9:
			SLPrint(&sl);
			break;
		default:
			printf("请重新选择！\n");
			break;
		}
	} while (input);
	SLDestroy(&sl);
	return 0;
}

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包