数据结构之顺序表_数据结构顺序表

目录

前言

一、顺序表的结构

二、顺序表各接口函数及实现

1、顺序表的初始化

2、顺序表的打印

3、顺序表的插入函数

①、顺序表头部插入函数

②、顺序表尾部插入函数

③、任意位置插入函数

 4、顺序表的删除函数

①、头部删除函数

②、尾部删除函数

③、任意位置删除

5、顺序表的增容

6、顺序表的查找与修改

①、查找函数

②、修改数据函数

7、顺序表的销毁

结语

---

前言

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。

数据结构可简单分为线性结构和非线性结构；顺序表就是线性结构的一种，其在物理结构和逻辑结构上都是连续的，本文针对顺序表这一结构进行分析，通过C语言实现简单的接口函数对顺序表进行操作。

一、顺序表的结构

动态顺序表结构里包含的元素有SLDataType* a指针、整型变量size、整型变量capacity。（SLDataType指顺序表存储的数据类型）

指针用于指向动态开辟的内存空间地址，size变量用于保存已存数据的个数，capacity变量负责保存目前顺序表的容量大小。

二、顺序表各接口函数及实现

1、顺序表的初始化

函数功能：负责动态开辟内存，将开辟成功的地址传给指针a，将size置为0，capacity赋值为开辟的初始容量。

函数实现（C语言）：

//初始化
void SeqListInit(SL *ps)
{
	ps->a = (SLDataType)malloc(sizeof(SLDataType)* 4);//SLDataType:存储的数据类型
	if (ps->a == NULL)//开辟失败
	{
		printf("申请内存失败\n");
		exit(-1);
	}
	ps->capacity = 4;//开辟空间容量
	ps->size = 0;//目前有效存储数据个数
}

 

2、顺序表的打印

函数功能：负责对顺序表的数据进行打印输出。

函数实现：

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

 

3、顺序表的插入函数

顺序表的插入函数可分为三种，第一种为头部插入，第二种为尾部插入，第三种为从任意位置插入，下面对每种情况进行分析实现。

①、顺序表头部插入函数

函数功能：从顺序表的第一个位置插入特定数据

函数实现思路：

 函数实现代码：

//头插
void SeqListPushFront(SL *ps, SLDataType x)
{
	SLCheckCapacity(&ps);//检查容量，不足则增容
	int end = ps->size;//控制挪动数据
	while (end > 0)
	{
		ps->a[end] = ps->a[end - 1];
		--end;
	}
	ps->a[0] = x;
	ps->size++;
}

 

②、顺序表尾部插入函数

函数功能：从顺序表的尾部插入数据。

函数实现思路：相比头部插入，尾部插入会方便很多，只需要将数据插入，size++即可。

函数实现代码：

//尾插
void SeqListPushBack(SL *ps, SLDataType x)
{
	SLCheckCapacity(ps);//检查容量，不足则增容
	ps->a[ps->size] = x;
	ps->size++;
}

 

③、任意位置插入函数

函数功能：从特定位置插入数据，可通过输入控制插入的位置。

函数实现思路：

 函数实现代码：

//从pos位置插入
void SeqListInsert(SL *ps, int pos, SLDataType x)
{
	assert(pos >= 0 && pos <= ps->size);//判断pos的合法性
	SLCheckCapacity(ps);//检查容量，不足则增容
	
	//挪动数据
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
 
	ps->a[pos] = x;
	ps->size++;
}

 

 4、顺序表的删除函数

与插入函数一样，删除函数一样分为头部删除、尾部删除、从任意位置删除三种，实现如下。

①、头部删除函数

函数功能：从顺序表的头部删除数据。

函数实现思路：

 函数实现代码：

//头删
void SeqListPopFront(SL *ps)
{
	assert(ps->size > 0);//保证有数据可删
	int begin = 1;
	while (begin < ps->size)//begin小于size时挪动数据
	{
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}
	ps->size--;
}

②、尾部删除函数

函数功能：从尾部删除一个数据。

函数实现思路：尾部删除不需要挪动数据，只需要将size的值进行减1操作即可。

函数实现代码：

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

③、任意位置删除

函数功能：从特定的位置删除数据。

函数思路：

 函数实现代码：

//从pos位置删除
void SeqListErase(SL *ps, int pos)//pos代表需要删除的位置
{
	assert(pos >= 0 && pos < ps->size);//保证pos的合法性
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}
	ps->size--;
}

5、顺序表的增容

函数功能：当进行插入数据时，需要对顺序表的容量进行检查，容量不足时，通过realloc函数进行内存空间的重新申请，一般增容的大小为原先的二倍。

函数实现代码：

//检查容量，容量不足则增容
void SLCheckCapacity(SL *ps)
{
	if (ps->size >= ps->capacity)
	{
		//增容
		ps->capacity *= 2;
		ps->a = (SLDataType)realloc(ps->a, sizeof(SLDataType)*ps->capacity);
		if (ps->a == NULL)
		{
			printf("增容失败\n");
			exit(-1);
		}
	}
}

6、顺序表的查找与修改

①、查找函数

函数功能：对顺序表内的数据进行查找，查找成功返回下标，查找失败返回-1。

函数实现代码：

//查找元素
int SeqListFind(SL *ps, SLDataType x)
{
	for (int i = 0; i < ps->size; i++)//遍历顺序表
	{
		if (ps->a[i] == x)//找到数据返回下标
		{
			return i;
		}
	}
	return -1;//找不到返回-1
}

②、修改数据函数

函数功能：根据输入的下标找到对应数据，将其修改为对应的数据。

函数实现代码：

//修改指定位置数据
void SeqListAlter(SL *ps, int pos, SLDataType x)
{
	assert(pos >= 0 && pos < ps->size);
	ps->a[pos] = x;
}

7、顺序表的销毁

因为顺序表是动态开辟的空间，所以需要一个函数用来对顺序表进行释放。

函数实现代码：

//不用时释放顺序表
void SeqListDestory(SL *ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

三、总代码分享

头文件SeqList.h

#pragma once
#include<stdio.h>
#include<assert.h>
typedef int SLDataType;//方便修改顺序表存取的数据类型
 
enum func//菜单时使用，提高代码的可读性
{
	头部插入 = 1,
	头部删除,
	尾部插入,
	尾部删除,
	任意位置插入,
	任意位置删除,
	查找数据,
	修改数据,
	打印,
	销毁
};
 
//动态顺序表的结构
typedef struct SeqList
{
	SLDataType* a;//存取的数据
	int size;//已存的数据个数
	int capacity;//容量
}SL;
 
//打印顺序表
void SeqListPrint(SL *ps);
 
//初始化顺序表
void SeqListInit(SL *ps);
 
//头插头删
void SeqListPushFront(SL *ps, SLDataType x);
void SeqListPopFront(SL *ps);
 
//尾插尾删
void SeqListPushBack(SL *ps, SLDataType x);
void SeqListPopBack(SL *ps);
 
//任意位置插入删除
void SeqListInsert(SL *ps, int pos, SLDataType x);
void SeqListErase(SL *ps, int pos);
 
//增容
void SLCheckCapacity(SL *ps);
 
//查找元素，找到返回下标，没找到返回-1
int SeqListFind(SL *ps, SLDataType x);
 
//修改指定位置的数据
void SeqListAlter(SL *ps, int pos, SLDataType x);
 
//释放内存
void SeqListDestory(SL *ps);

SeqList.c

#include"SeqList.h"
 
//初始化
void SeqListInit(SL *ps)
{
	ps->a = (SLDataType)malloc(sizeof(SLDataType)* 4);//SLDataType:存储的数据类型
	if (ps->a == NULL)//开辟失败
	{
		printf("申请内存失败\n");
		exit(-1);
	}
	ps->capacity = 4;//开辟空间容量
	ps->size = 0;//目前有效存储数据个数
}
 
//不用时释放顺序表
void SeqListDestory(SL *ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}
 
//检查容量，容量不足则增容
void SLCheckCapacity(SL *ps)
{
	if (ps->size >= ps->capacity)
	{
		//增容
		ps->capacity *= 2;
		ps->a = (SLDataType)realloc(ps->a, sizeof(SLDataType)*ps->capacity);
		if (ps->a == NULL)
		{
			printf("增容失败\n");
			exit(-1);
		}
	}
}
 
//打印顺序表
void SeqListPrint(SL *ps)
{
	for (int i = 0; i < ps->size; i++)//size控制打印次数
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}
 
 
//头插
void SeqListPushFront(SL *ps, SLDataType x)
{
	SLCheckCapacity(&ps);//检查容量，不足则增容
	int end = ps->size;//控制挪动数据
	while (end > 0)
	{
		ps->a[end] = ps->a[end - 1];
		--end;
	}
	ps->a[0] = x;
	ps->size++;
}
 
//头删
void SeqListPopFront(SL *ps)
{
	assert(ps->size > 0);//保证有数据可删
	int begin = 1;
	while (begin < ps->size)//begin小于size时挪动数据
	{
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}
	ps->size--;
}
 
//尾插
void SeqListPushBack(SL *ps, SLDataType x)
{
	SLCheckCapacity(ps);//检查容量，不足则增容
	ps->a[ps->size] = x;
	ps->size++;
}
 
//尾删
void SeqListPopBack(SL *ps)
{
	assert(ps->size > 0);
	ps->size--;
}
 
//从pos位置插入
void SeqListInsert(SL *ps, int pos, SLDataType x)
{
	assert(pos >= 0 && pos <= ps->size);//判断pos的合法性
	SLCheckCapacity(ps);//检查容量，不足则增容
	
	//挪动数据
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
 
	ps->a[pos] = x;
	ps->size++;
}
 
//查找元素
int SeqListFind(SL *ps, SLDataType x)
{
	for (int i = 0; i < ps->size; i++)//遍历顺序表
	{
		if (ps->a[i] == x)//找到数据返回下标
		{
			return i;
		}
	}
	return -1;//找不到返回-1
}
 
//从pos位置删除
void SeqListErase(SL *ps, int pos)//pos代表需要删除的位置
{
	assert(pos >= 0 && pos < ps->size);//保证pos的合法性
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}
	ps->size--;
}
 
//修改指定位置数据
void SeqListAlter(SL *ps, int pos, SLDataType x)
{
	assert(pos >= 0 && pos < ps->size);
	ps->a[pos] = x;
}

main.c（菜单只是为了使用美观，与顺序表的实现无实质影响）

#include"SeqList.h"
 
void menu()
{
	SL s3;
	SeqListInit(&s3);
 
	int input = 0;
	int i = 0, j = 0;
	do
	{
		printf("*****************************************************\n");
		printf("************1.头部插入        2.头部删除*************\n");
		printf("************3.尾部插入        4.尾部删除*************\n");
		printf("************5.任意位置插入    6.任意位置删除*********\n");
		printf("************7.查找数据        8.修改数据*************\n");
		printf("************9.打印            10.销毁   *************\n");
		printf("************           0.退出           *************\n");
		printf("*****************************************************\n");
		printf("请选择:>");
		scanf("%d", &input);
		switch (input)
		{
		case 头部插入:
			/*int i = 0;*/
			printf("请输入需要插入头部的数据:>");
			scanf("%d", &i);
			SeqListPushFront(&s3, i);
			printf("插入成功\n");
			break;
		case 头部删除:
			SeqListPopFront(&s3);
			printf("删除成功\n");
			break;
		case 尾部插入:
			/*int i = 0;*/
			printf("请输入需要插入尾部的数据:>");
			scanf("%d", &i);
			SeqListPushBack(&s3, i);
			printf("插入成功\n");
			break;
		case 尾部删除:
			SeqListPopBack(&s3);
			printf("删除成功\n");
			break;
		case 任意位置插入:
			/*int i = 0, j = 0;*/
			printf("请输入需要插入的位置与数据，以空格隔开:>");
			scanf("%d %d", &i, &j);
			SeqListInsert(&s3, i, j);
			printf("插入成功\n");
			break;
		case 任意位置删除:
			/*int i = 0;*/
			printf("请输入需要删除的位置:>");
			scanf("%d", &i);
			SeqListErase(&s3, i);
			printf("删除成功\n");
			break;
		case 查找数据:
			/*int i = 0, j = 0;*/
			printf("请输入需要查找的数据:>");
			scanf("%d", &i);
			j = SeqListFind(&s3, i);
			if (j != -1)
			{
				printf("找到了，下标是:%d\n", j);
			}
			else
				printf("暂无此数据\n");
			break;
		case 修改数据:
			/*int i = 0, j = 0;*/
			printf("请输入需要修改的数据下标及修改后的数据，以空格隔开:>");
			scanf("%d %d", &i,&j);
			SeqListAlter(&s3, i, j);
			printf("修改成功\n");
			break;
		case 打印:
			SeqListPrint(&s3);
			break;
		case 销毁:
			SeqListDestory(&s3);
			printf("销毁成功\n");
			break;
		case 0:
			printf("退出\n");
			break;
		default:
			printf("输入非法\n");
			break;
		}
	} while (input);
	
}
int main()
{
	menu();
	return 0;
}

 

结语

顺序表的基本接口函数到此就介绍完毕啦~希望此文对初学者能有所帮助，也欢迎大家指正错误！