【数据结构】超详细之顺序表（利用C语言实现）_(1)设计顺序表并由输入数据建立顺序表、输出顺序表数据、利用原空间和一个额外存

---

前言

数据结构是一个程序员必须会的一种操作功能，学习数据结构能提高我们的逻辑思维能力以及解决实际项目能力，数据结构分为很多种，今天我们要讲的是数据结构中的顺序表.

一、顺序表是什么？

1.顺序表其本质是一种类似于数组的空间,其存储方式与数组一样,具有一段连续的空间.

2.顺序表的功能大致为实现增删改查操作,像QQ群或者微信群中存放的群员列表,都可以用顺序表实现.

3.在实际应用中，顺序表能大大提高工作效率，是一种结构化、具体化的工具

二、使用步骤

1.顺序表的初始化以及开辟空间

代码如下（示例）：
 

//.h文件内
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int TYPE;//将类型重命名作为存放数据的类型,使程序灵活改变
 
//定义一个结构体类型,用于存放数据
typedef struct  SequenceList
{
    TYPE* Data;//数据
    int sz;//计算有效数据
    int sum;//计算空间容量
}SL;
 
//初始化顺序表
void SeqListInit(SL* ps);

//.c文件内
#define _CRT_SECURE_NO_WARNINGS 1
#include"SequenceList.h"
 
//初始化顺序表
void SeqListInit(SL* ps)
{
	assert(ps);
	ps->Data = (TYPE*)malloc(sizeof(TYPE)*4);//开辟四个空间
	if (ps->Data == NULL)
	{
		perror("malloc");
		return;
	}
	ps->sum = 4;
	ps->sz = 0;
}

2.实现顺序表的头插、尾插以及打印

代码如下（示例）：

.h文件
//顺序表头部插入(头插)
void SeqListPushFront(SL* ps, TYPE x);
//顺序表尾部插入(尾插)
void SeqListPushBack(SL* ps, TYPE x);
//打印数据
void SeqListPrint(SL* ps);

.c文件
//扩容
void SLCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->sum == ps->sz)
	{
		TYPE* Add = (TYPE*)realloc(ps->Data, sizeof(TYPE) * 8);//默认一次扩增加4空间
		if (Add == NULL)
		{
			perror("realloc");
			return;
		}
		ps->Data = Add;
		ps->sum += 4;
	}
}
//顺序表头部插入(头插)
void SeqListPushFront(SL* ps, TYPE x)
{
	assert(ps);
	//判断是否还有容量,是否需要扩容
	SLCheckCapacity(ps);
	int n = ps->sz;
	while (n>0)
	{
		ps->Data[n] = ps->Data[n - 1];
		n--;
	}
	ps->Data[0] = x;
	ps->sum--;
	ps->sz++;
}
 
//顺序表尾部插入(尾插)
void SeqListPushBack(SL* ps, TYPE x)
{
	assert(ps);
	//判断是否还有容量,是否需要扩容
	SLCheckCapacity(ps);
	ps->Data[ps->sz] = x;
	ps->sum--;
	ps->sz++;
}
 
//打印数据
void SeqListPrint(SL* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->sz; i++)
	{
		printf("%d->", ps->Data[i]);
	}
}

//.c文件(启动文件)
#define _CRT_SECURE_NO_WARNINGS 1
#include"SequenceList.h"
int main()
{
	SL pr;
	SeqListInit(&pr); //初始化
	SeqListPushBack(&pr, 1);//尾插
	SeqListPushFront(&pr, 2);//头插
	SeqListPushBack(&pr, 3);//尾插
	SeqListPrint(&pr);//打印
	return 0;
}

3.实现顺序表的头删、尾删以及打印

代码如下（示例）：

.h文件
//顺序表头部删除(头删)
void SeqListPopFront(SL* ps);
//顺序表尾部删除(尾删)
void SeqListPopBack(SL* ps);

.c文件
//顺序表头部删除(头删)
void SeqListPopFront(SL* ps)
{
	assert(ps);
	if (ps->sz == 0)
	{
		return;
	}
	int n = 0;
	while (n<(ps->sz)-1)
	{
		ps->Data[n] = ps->Data[n + 1];
		n++;
	}
	ps->sum++;
	ps->sz--;
}
//顺序表尾部删除(尾删)
void SeqListPopBack(SL* ps)
{
	assert(ps);
	if (ps->sz == 0)
	{
		return;
	}
	ps->sz--;
}

---

4.实现顺序表的查找

代码如下（示例）：

.h文件
//顺序表的查找
//找到了返回该数下标
//没找到返回-1;
int SeqListFind(SL* ps, TYPE x);

.c文件
//顺序表的查找
//找到了返回该数下标
//没找到返回-1;
int SeqListFind(SL* ps, TYPE x)
{
	assert(ps);
	assert(ps->sz);
	int i = 0;
	for (i = 0; i < ps->sz; i++)
	{
		if (ps->Data[i] == x)
		{
			return i;
		}
	}
	return -1;
}

---

5.实现顺序表指定位置插入

代码如下（示例）：

.h文件
//顺序表指定插入
void SeqListInsert(SL* ps, int pos, TYPE x);

.c文件
//顺序表指定插入
void SeqListInsert(SL* ps, int pos, TYPE x)
{
	assert(ps);
	//判断是否还有容量,是否需要扩容
	SLCheckCapacity(ps);
	assert(pos >= 0 && pos <= ps->sz);
	int n = ps->sz;
	while (n>pos)
	{
		ps->Data[n] = ps->Data[n - 1];
		n--;
	}
	ps->Data[pos] = x;
	ps->sz++;
	ps->sum--;
}

当有指定位置插入功能时，头插和尾插就可以简化成如下代码：

//顺序表头部插入(头插)
void SeqListPushFront(SL* ps, TYPE x)
{
	assert(ps);
	//判断是否还有容量,是否需要扩容
	SLCheckCapacity(ps);
	SeqListInsert(ps, 0, x);
}
 
 
//顺序表尾部插入(尾插)
void SeqListPushBack(SL* ps, TYPE x)
{
	assert(ps);
	//判断是否还有容量,是否需要扩容
	SLCheckCapacity(ps);
	SeqListInsert(ps, ps->sz, x);
}

---

6.实现顺序表指定位置删除

代码如下（示例）：

.h文件
//顺序表指定删除
void SeqListErase(SL* ps, int pos);

.c文件
//顺序表指定删除（根据下标进行删除）
void SeqListErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos<=ps->sz);
	assert(ps->sz);
	int n = pos + 1;
	while(n<ps->sz)
	{
		ps->Data[n-1] = ps->Data[n];
		n++;
		pos++;
	}
	ps->sz--;
	ps->sum++;
}

---

7.释放内存

代码如下（示例）：

.h文件
//释放空间
void SeqListDestroy(SL* ps);

.c文件
 
//释放空间
void SeqListDestroy(SL* ps)
{
	assert(ps);
	free(ps->Data);
	ps->Data = NULL;
	ps->sum = 0;
	ps->sz = 0;
}

---

总结

以上就是我对数据结构——顺序表的理解，谢谢大家观看！