探索顺序表：数据结构中的秩序之美（c语言实现常见功能接口）

是Nero哦

发布于 2024-01-18 18:38:08

1370

发布于 2024-01-18 18:38:08

文章被收录于专栏：c/c++学习与分享

在我们的数据结构探索中，我们已经探讨时间复杂度、空间复杂度。大家可以移步到我的上篇文章：

打开数据结构大门：深入理解时间与空间复杂度

今天，我们将深入研究另一个重要的主题——顺序表

全部的源代码大家可以去我github主页进行浏览：Nerosts/just-a-try: 学习c语言的过程、真 (github.com)

在介绍顺序表前，先来了解一下线性表的概念，后面一段时间讲到的数据结构也都属于线性表。

一.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、字符串…

线性表在==逻辑上（我们想象它是）==是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

二.顺序表

2.1概念和结构

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

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

#define N 7
typedef int SLDataTypt;
struct SeqList
{
	int a[N];//数组长度固定
	int size;//有效数据的个数
			//因为数组长度固定，也不需要capacity来表示容积
};

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

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* a;
	int size;//the number of valid data
	int capacity;//the size of volumetric space
}SL;

2.2项目文件方面规划

头文件SquList.h:用来基础准备，顺序表的基本框架，函数的声明
源文件SeqList.h:用来各种接口函数的具体实现
源文件test.h:用来测试功能是否有问题

2.3基本功能实现

各接口总体一览

void SLInit(SL* ps); //初始化
void SLDestroy(SL* ps);//销毁
void SLPrint(SL* ps);//打印

void SLPushBack(SL* ps, SLDataType x);//尾插
void SLPushFront(SL* ps, SLDataType x);//头插
void SLPopFront(SL* ps);//头删
void SLPopBack(SL* ps);//尾删

// 顺序表查找
int SLFind(SL* ps, SLDataType x);//返回下标索引
// 顺序表在pos位置插入x
void SeqListInsert(SL* ps, int pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SL* ps, int pos);

初始化、销毁、打印

void SLInit(SL* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

void SLDestroy(SL* ps)
{
	assert(ps);
	free(ps->a);//pa->a 是realloc动态开辟的
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

void SLPrint(SL* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)//size means the number of valid data
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

尾插

void CheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* new = realloc(ps->a,sizeof(SLDataType) * newcapacity);
		if (new == NULL)
		{
			perror("realloc");
			return -1;
		}
		ps->a = new;
		ps->capacity = newcapacity;
	}
}

void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	CheckCapacity(ps);//检查此时容积是否存满
	ps->a[ps->size] = x;
	ps->size++;
}

SLPushBack函数用于向单链表尾部添加元素。

首先使用assert宏判断ps是否为空指针
然后调用CheckCapacity函数检查容量是否已满，若已满则进行扩容操作
接着将元素x添加到单链表数组的末尾，然后更新单链表的大小

CheckCapacity函数用于检查单链表的容量是否已满，如果已满则进行扩容操作

首先使用assert宏判断ps是否为空指针
然后判断如果单链表的大小等于容量，说明已满，需要进行扩容操作。新的容量设置为原容量的两倍，如果原容量为0，则新容量设置为4
然后使用realloc函数重新分配内存，将原数组指针ps->a指向的内存空间扩展到新的容量大小，如果内存分配失败则输出错误信息并返回-1
最后更新ps->a指向新的内存空间，同时更新容量为新的容量值

这两个函数结合起来可以实现向单链表尾部添加元素并在需要时自动扩容的功能

头插

void SLPushFront(SL* ps, SLDataType x) //将所有元素向后迁移一个，把第一个位置空出来
{
	assert(ps);
	CheckCapacity(ps);
	memmove(ps->a + 1, ps->a, sizeof(SLDataType) * ps->size);
	ps->a[0] = x;
	ps->size++;
}

函数的作用是将所有元素向后移动一个位置，从而空出第一个位置，然后在第一个位置插入新的元素x

首先使用assert宏判断ps是否为空指针，然后调用CheckCapacity函数检查容量是否已满，若已满则进行扩容操作
接着使用memmove函数将数组中的元素整体向后移动一个位置，从ps->a的位置开始，移动sizeof(SLDataType) * ps->size个字节的数据，移动到ps->a + 1的位置，即每个元素向后移动一个位置。
然后将新元素x插入到第一个位置ps->a0，并更新单链表的大小

头删

void SLPopFront(SL* ps)//整体向前偏移
{
	assert(ps);
    assert(ps->size > 0);//保证有元素来删
	memmove(ps->a, ps->a+1, sizeof(SLDataType) * ps->size);
	ps->size--;
}

尾删

void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	ps->size--;
}

查找

int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (x == ps->a[i])
		{
			return i;
		}
	}
	return -1;
}

插入

void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	CheckCapacity(ps);
	memmove(ps->a + pos + 1, ps->a + pos, sizeof(SLDataType) * (ps->size - pos));
	ps->a[pos] = x;
	ps->size++;
}

删除

void SeqListErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	int start = pos;
	while (start < ps->size)
	{
		ps->a[start] = ps->a[start + 1];
		start++;
	}
	ps->size--;
}

2.4测试

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"

void test1()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	printf("尾插三个：");
	SLPrint(&s);

	SLPushFront(&s, 0);
	SLPushFront(&s, 0);
	printf("头插2个：");
	SLPrint(&s);

	SLPopFront(&s);
	SLPopFront(&s);
	printf("头删2个：");
	SLPrint(&s);

	SLPopBack(&s);
	SLPopBack(&s);
	printf("尾删2个：");
	SLPrint(&s);

	SLDestroy(&s);
}

int main()
{
	test1();
	return 0;
}

结果如下：