【数据结构】顺序表的实现及基本操作完整代码（C语言实现）-Toy模板网

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

顺序表的基本操作

顺序表：逻辑上相邻的数据元素，其物理次序也是相邻的

宏定义及头文件

#include<stdio.h>
#include<stdlib.h>
typedef int SqlElemType;
typedef int Status;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define max_length 20

这里之所以要把int分别创建新名字为SqlElemType和Status，是因为实际应用时数据的类型不一定是int型，这样设置方便修改元素类型，提高代码适用性。

顺序表的存储结构

typedef struct {
	SqlElemType *arr;//存储空间的基地址 
	int length;//当前长度
}SqList;
//图书表的顺序存储结构
typedef struct {//图书信息定义
	char name[50];//图书名字 
	char num[50];//图书编号 
	float price;//图书价格 
}Book;
typedef struct {
	Book* brr;
	int length;//图书表中当前图书个数 
}BookSqList;

初始化顺序表

Status InitSqList(SqList *L, int length)//构造一个空的顺序表 
{
	L->arr = (SqlElemType*)malloc(sizeof(SqlElemType) * max_length);//为顺序表分配空间 
	if (!L->arr)//存储分配失败 
		return OVERFLOW;
	L->length = 0;//空表长度为0 
	return OK;
}

获取顺序表的元素

Status GetElem(SqList L, int i, SqlElemType* e)
{
	if (i < 1 || i > L.length)//判断i值是否合理，若不合理 ，返回ERROR 
		return ERROR;
	*e = L.arr[i - 1];//第i-1的单元存储着第i个数据 
	return OK;
}

顺序表的查找

int LocateElem(SqList L, SqlElemType e)
{
//在线性表中查找值为e的数据元素，返回其序号 
	for (i = 0; i < L.length; i++)
	{
		if (e == L.arr[i])//查找成功，返回序号 
			return i + 1;
	}
	return 0;//查找失败，返回0 
}

LocateElem的时间复杂度为O（n)

顺序表的插入

Status InsertSq(SqList* L, int j, SqlElemType e)
{
	if (j<1 || j>L->length+1)//i值不合法 
	{
		return ERROR;
	}
	if (L->length == max_length)//当前存储空间已满 
	{
		return OVERFLOW;
	}
	for (i = L->length - 1; i >= j-1; i--)
	{
		L->arr[i ] = L->arr[i-1];//插入位置及之后的元素后移 
	}
	L->arr[j-1] = e;//将新元素放入第i个位置 
	L->length++;//表长加一 
	return OK;
}

InsertSq的时间复杂度为O（n)

顺序表的删除

Status DeleteSq(SqList* L, int i, SqlElemType* e)
{
	if (i<1 || i>L->length)//i值不合法
	{
		return ERROR;
	}
	*e = L->arr[i - 1];
	for (j = i; j < L->length; j++)
	{
		L->arr[j - 1] = L->arr[j];//被删除之后的元素前移
	}
	L->length--;//表长减一 
	return OK;
}

DeleteSq的时间复杂度为O（n)

判断顺序表是否为空

Status IsEmptySq(SqList* L)
{
	if (L->length == 0)
		return TRUE;
	else
		return FALSE;
}

清空顺序表

void ClearSq(SqList* L)
{
	L->length = 0;//将线性表的长度置为0 
}

顺序表的销毁

Status DestroySq(SqList* L)
{
	if (!L->arr)
	{
		return ERROR;
	}
	else
		free(L->arr);//释放存储空间 
	return OK;
}

输出顺序表

int PrintList(SqList* L)
{
	if (!L->arr)//判断是不是空表
		return FALSE;
	printf("顺序表里的元素有：");
	for (i = 0; i < L->length; i++)
		printf("%d ", L->arr[i]);
	printf("\n");
}

完整代码

//顺序表的存储结构
#include<stdio.h>
#include<stdlib.h>
typedef int SqlElemType;
typedef int Status;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define max_length 20
int i,j;
typedef struct {
	SqlElemType *arr;//存储空间的基地址 
	int length;//当前长度
}SqList;
//图书表的顺序存储结构
typedef struct {//图书信息定义
	char name[50];//图书名字 
	char num[50];//图书编号 
	float price;//图书价格 
}Book;
typedef struct {
	Book* brr;
	int length;//图书表中当前图书个数 
}BookSqList;
//初始化顺序表
Status InitSqList(SqList *L, int length)//构造一个空的顺序表 
{
	L->arr = (SqlElemType*)malloc(sizeof(SqlElemType) * max_length);//为顺序表分配空间 
	if (!L->arr)//存储分配失败 
		return OVERFLOW;
	L->length = 0;//空表长度为0 
	return OK;
}
void WriteList(SqList* L)//把元素放入顺序表
{
	printf("请输入你要创建的顺序表的长度：");
	scanf("%d", &L->length);
	printf("请输入%d个你要放入顺序表里的元素：", L->length);
	for ( i = 0; i < L->length; i++)
		scanf("%d", &L->arr[i]);
}
//获取元素
Status GetElem(SqList L, int i, SqlElemType* e)
{
	if (i < 1 || i > L.length)//判断i值是否合理，若不合理 ，返回ERROR 
		return ERROR;
	*e = L.arr[i - 1];//第i-1的单元存储着第i个数据 
	return OK;
}
//查找元素
int LocateElem(SqList L, SqlElemType e)
{
//在线性表中查找值为e的数据元素，返回其序号 
	for (i = 0; i < L.length; i++)
	{
		if (e == L.arr[i])//查找成功，返回序号 
			return i + 1;
	}
	return 0;//查找失败，返回0 
}
//顺序表的插入
Status InsertSq(SqList* L, int j, SqlElemType e)
{
	if (j<1 || j>L->length+1)//i值不合法 
	{
		return ERROR;
	}
	if (L->length == max_length)//当前存储空间已满 
	{
		return OVERFLOW;
	}
	for (i = L->length - 1; i >= j-1; i--)
	{
		L->arr[i ] = L->arr[i-1];//插入位置及之后的元素后移 
	}
	L->arr[j-1] = e;//将新元素放入第i个位置 
	L->length++;//表长加一 
	return OK;
}
//顺序表的删除
Status DeleteSq(SqList* L, int i, SqlElemType* e)
{
	if (i<1 || i>L->length)//i值不合法
	{
		return ERROR;
	}
	*e = L->arr[i - 1];
	for (j = i; j < L->length; j++)
	{
		L->arr[j - 1] = L->arr[j];//被删除之后的元素前移
	}
	L->length--;//表长减一 
	return OK;
}
//销毁顺序表
Status DestroySq(SqList* L)
{
	if (!L->arr)
	{
		return ERROR;
	}
	else
		free(L->arr);//释放存储空间 
	return OK;
}
//清空顺序表
void ClearSq(SqList* L)
{
	L->length = 0;//将线性表的长度置为0 
}
//判断顺序表是否为空
Status IsEmptySq(SqList* L)
{
	if (L->length == 0)
		return TRUE;
	else
		return FALSE;
}
//输出顺序表
int PrintList(SqList* L)
{
	if (!L->arr)//判断是不是空表
		return FALSE;
	printf("顺序表里的元素有：");
	for (i = 0; i < L->length; i++)
		printf("%d ", L->arr[i]);
	printf("\n");
}
int main()
{
	SqList A;
	SqList* p = &A;
	InitSqList(&A, 10);
	WriteList(&A);
	PrintList(&A);
	int b;
	GetElem(A, 2, &b);
	printf("获取第二个位置的元素：\n");
	printf("获取到的元素为%d\n", b);
	int e = 3;
	int location=LocateElem(A, e);
	printf("查找值为3的元素e的位置：\n");
	printf("查找到元素e的位置为%d\n", location);
	DeleteSq(p, 2, &b);//删除顺序表的第二个位置的元素
	printf("删除顺序表的第二个位置的元素:%d\n", b);
	printf("删除后：");
	PrintList(&A);
	InsertSq(&A, 5, e);//在第五个位置插入元素e
	printf("在第五个位置插入3,此时");
	PrintList(&A);
	ClearSq(p);//清空顺序表
	printf("清空顺序表后，");
	PrintList(&A);
	int em=IsEmptySq(&A);//判断顺序表是否为空
	printf("判断顺序表是否为空,为空输出1，不为空输出0: %d\n", em);
	DestroySq(p);//销毁顺序表
	return 0;
}