基于数组的数据结构--顺序表

prettyxian

发布于 2025-12-30 19:04:06

830

文章被收录于专栏：QTQT

什么是数据结构？数据结构有什么用？

一个学校里，学生可能有成千上万，非常不方便管理，要找一个学生非常难。把学生基于年级班级分成一个个的班级，这样就可以很轻松的找到某一个学生。在计算机中，有着各种数据需要处理，因此引入了数据结构。

数据：

什么是数据呢？日常生活中的图片，听的音乐，储存的联系人，这些都是数据。

结构：数据结构就是处理数据的方式，例如给知识做思维导图，把知识联系到一起。

在计算机中我们要处理很多不同的数据，单个的数据不方便管理。因此引入了数据结构。数据结构是一种特定的数据组织方式，它定义了数据之间的关系、操作和存储方式。

数据结构可以分为以下几类：

线性数据结构：数据元素之间是一对一的关系，如数组、链表、栈、队列等。
非线性数据结构：数据元素之间是一对多或多对多的关系，如树、图等。
集合数据结构：元素之间没有明确的顺序关系，如集合、哈希表等

我们今天要讲的顺序表基于数组，所以也是一种线性的数据机构。

顺序表

线性表

线性表（linearlist）就是把有着相同特性的数据组织到一起。线性表是⼀种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...。线性表在逻辑上是连续的，可以根据上一个数据找到下一个（非首尾的话）。但是在物理上不一定连续。为什么物理上不连续逻辑上却能够连续呢？可以理解为虽然数据在内存中没有挨到一起，但是它们之间有一根线把他们连接到一起了。

顺序表的分类

顺序表根据储存数据用定长数组函数还是动态申请空间分为静态顺序表和动态顺序表。

静态顺序表

实现静态顺序表需要创建两个变量，第一个定长的数组用来存放数据；size用来记录有效数据的个数。

既然数组是定长的，那么静态顺序表就有一个致命的弱点，能够储存的数据有限，这个数组空间开辟大了会造成空间的浪费如果开辟小了，就可能造成数据丢失。

struct Seqlist
{
	SLDataType arr[10];//定长的数组
	SLDataType size;//数据的个数
};
typedef Seqlist SL;

所以我们更常用动态顺序表。

动态顺序表

动态的顺序表的实现需要创建3个变量，指针a记录开始的位置；size记录有效数据与的个数；capacity用来记录空间的容量。相比于静态顺序表。动态顺序表的内存是动态开辟的，更加灵活。

typedef struct Seqlist
{
	SLDataType *a;//指针
	SLDataType size;//数据的个数
	SLDataType capacity;//空间的容量
}SL;

动态数据表的实现

实现动态顺序表，我们和前面的扫雷一样使用程序的模块化设计。一共分成三个文件。Seqlist.c用来实现顺序表的各种方法，Seqlist.h用来包含实现方法所需的头文件和所需方法的初始化。test.c用来测试写的方法是否有问题。

首先我们用Seqlist.h理出程序的结构

需要包含的头文件：

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

需要实现的方法：

//顺序表初始化
void SLInit(SL* ps);


//顺序表的销毁
void SLDestory(SL* ps);

//头部插入-删除/尾部插入-删除

void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);

void SLPopBack(SL* ps);
void SLPopFront(SL* ps);

//在指定位置插入/删除数据

void SLInert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);

接下来我们在Seqlist.c中实现各种方法

顺序表的初始化：

要用到Seqlist.h中的头文件，所以要包含它。

因为是用过指针访问结构体，所以使用->操作符。

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

写完一个方法就调试，检查有没有故障（在test.c中实现）

顺序表的销毁：

释放掉开辟的内存，为了规避野指针，将a置为空。

//顺序表的销毁
void SLDestory(SL* ps)
{
	if (ps->a)
	{
		free(ps->a);
	}
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

调试：

尾部插入数据：

检查有没有足够的空间来插入数据。

//检查有没有足够的空间
void SLCheckCapacity(SL* ps)
{

	if (ps->capacity == ps->size)
	{
		//申请空间
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));//申请多大的空间
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);//直接退出程序，不在继续执行
		}
		//空间申请成功
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
}

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);//检查有没有足够的空间
	ps->a[ps->size] = x;
	ps->size++;//插入数据之后，有效数据与个数+1
}

测试：

头部插入数据：

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	//让顺序表中已有的数据整体往后挪动一位
	for (int i = ps->size; i > 0; i--)
	{
		ps->a[i] = ps->a[i - 1];//最后一次的时候是ps->a[0] = ps->a[1]
	}
	ps->a[0] = x;
	ps->size++;//插入一个数据，有效数据个数+1
}

调试：

预期结果是0 1 2 3 4，调试看一下

打印：

尾部删除数据：

//尾部删除数据
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	ps->size--;
}

调试执行：

头部删除数据：

//头部删除数据
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	//数据整体挪动前一位
	for (int i = 0; i>ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];//最后一次是ps->a[ps->size-2]= ps->a[ps->size-1]
	}
	ps->size--;
}

调试执行：

指定位置前插入数据：

//在指定位置插入数据

void SLInert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	//判断空间够不够
	SLCheckCapacity(ps);
	//将pos之后的数据向后移动一位
	for (int i = ps->size; i > pos; i--)
	{
		ps->a[i] = ps->a[i - 1];//最后的时候ps->arr[pos + 1]= ps->arr[pos]
	}
	ps->a[pos] = x;
	ps->size++;
}

调试执行：

指定位置删除数据：

//在指定位置删除数据

void SLErase(SL* ps, int pos)
{

	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];//最后一次是arr[size-2] = arr[size - 1];
	}
	ps->size--;
}

调试执行：