随笔——顺序表专题

前言

什么是数据结构？

数据结构是计算机科学中的一种组织和存储数据的方式，以便于对数据进行有效的访问和修改。数据结构不仅仅是数据的存储形
式，还包括对这些数据进行操作的一些算法和方法。不同的数据结构适用于不同类型的应用和问题。

数据结构可以按照多种方式分类，例如线性结构和非线性结构、静态结构和动态结构等。我们之前学的数组便是最为基础的数据结构之一。数组具有操作简单、易于理解、能够快速随机访问的优点，但也存在一些缺点，例如大多数数组的大小是固定的，对某些操作（如插入和删除）来说比较麻烦。为了解决这些缺点，我们在数组的基础上加入了一些算法和方法，从而形成了顺序表。

顺序表是一种动态数组，它可以在需要时动态调整大小，从而更灵活地适应不同的数据量需求。通过顺序表，我们可以在保留数组优点的同时，克服其固定大小的限制，更高效地进行插入和删除操作。

顺序表是线性表的一种。线性表之所以被称为线性，是因为它在逻辑上是环环相扣的，就像高中数学中的排列组合，需要按顺序完成一系列步骤：先做事情A，再做事情B，最后做事情C。这种逻辑上的顺序性就是线性表的线性特征。

线性表不仅有逻辑结构，还有物理结构。物理结构描述数据在内存中的存储形式。例如，数组在内存中是连续存储的，所以数组的物理结构是线性的。然而，线性表的物理结构不一定是线性的。

今天我们讨论的顺序表，由于其底层是数组，所以在物理结构上是线性的。同时，作为线性表的一种，顺序表的逻辑结构也是线性的。

顺序表的分类

如同数组有定长和变长两种，基于数组的顺序表也分为静态顺序表和动态顺序表。

静态顺序表，顾名思义，其内存大小是固定的，长度不可变，这继承了数组的缺点，因此我们不再详细讨论。动态顺序表的内存大小则可以动态调整，以适应不同的数据量需求。这意味着它可以根据需要灵活调整自身，就像现实生活中没有最好的选择，只有最合适的选择一样。动态调整使得顺序表能够更好地适应环境变化，如同生命的进化过程。

下面是实操环节

我们先在VS上创建一个项目，项目名为SeqList 。为什么要这样命名呢？Seq的全写是sequence，意为顺序的，List则是列表的意思，缩写起来就是SeqList 。

多文件项目

在项目 SeqList 中，我们将建立多个文件，以实现代码的模块化。SeqList.h 负责存储项目所需的全局信息，包括头文件、宏定义、函数声明和变量类型定义等，起支持作用。SeqList.c 负责实现项目所需的各类函数，而 test.c 则用于调试 SeqList.c 中的各项函数。我们还可以创建一个 log.c 文件，专门用于日志记录。

#pragma once

先在SeqList.h中加入预处理指令：#pragma once，用于防止头文件重复包含详见《随笔——预处理详解》。

顺序表的定义

顺序表，顺序表，既然是表，那当然是某些数据的集合，我们用结构体去存储这些数据。比如

struct SeqList
{
	int *arr;
	int size;
	int capacity;
};

为了让顺序表的内存空间是动态的，我们需要用到动态内存管理，arr便是用来储存开辟到的地址；size用来储存有效数据的个数，capacity用来描述可以容纳的数据个数。

不过这样的定义是有问题的，数组不是只能存储整型，也可以存储其他类型，如果是其他类型，那么这个顺序表就不适用了，该怎么办呢？我们使用typedef对类型int进行重命名；除此之外，再顺便把结构体struct SeqList进行重命名，以后就不用再写struct了，如下：

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* arr;
	int size;
	int capacity;
}SL;

这里看似对类型int进行了重命名，实际上是对类型int进行了再划分，现在int共有两类，一类是普通的int，就写作int，另一类专门用于描述顺序表中的int,写作SLDataType,以后，所有和顺序表中数据类型有关的int我们都写作SLDataType，而和顺序表中数据类型无关的int，比如循环变量，我们还是用int来写。这样，如果要存储其它类型的数据，只要改这一处类型重命名即可。（据说VS里有一键替换，我觉得还是不要碰比较好）

为什么不用#define类型重命名呢？你可以看这篇文章，我在某处题外话里讲过这个。另外注意，#define最好不要有分号,typedef是必须要有分号的。

SL初始化

在这篇文章中，我阐述了一个观点：函数里的形参实际上是对实参的拷贝。这意味着，如果要修改上一级函数中的某些变量，就不能直接将这些变量作为实参传入，而是要传入这些变量的地址。在 SL 初始化函数中，为了能够修改上一级函数中的 SL 类型变量，参数类型必须使用 SL*。

void SLInit(SL* ps_Init)
{
	__BUG_NULL__(ps_Init);
	ps_Init->arr = NULL;
	ps_Init->capacity = ps_Init->size = 0;
}

我们知道，为了避免野指针的出现，对于不使用的指针，要统统置为空，所以arr要初始化成NULL，并且此时顺序表中还未储存数据，所以capacity和size也都置为0；对于将使用的指针，比如这里的ps_Init，在使用之前也要判断是否为空。宏__BUG_NULL__正是为此而设计的。

题外话：
这里的NULL是要包含头文件stdio.h的，头文件属于全局信息，所以包含于SeqList.h中，同理，宏__BUG_NULL__也定义于头文件，这样，我们在SeqList.c下只包含SeqList.h这一个头文件就行了。

宏__BUG_NULL__定义如下：

#define __M_FILE__ (strrchr(__FILE__,'\\') ? strrchr(__FILE__,'\\') + 1 : __FILE__)

#define __BUG_NULL__(p) \
		if(p == NULL)\
		{\
		printf("\nBug!\n");\
		printf("The address " #p " is null." "\n");\
		printf("%s\n",__M_FILE__);\
		printf("%d\n",__LINE__);\
		exit(EOF);\
		}

宏的相关知识我们曾在预处理详解中讲过，这里主要讲函数strrchr，strrchr的头文件是string.h，原型如下：

char * strrchr ( const char *, int character);

该函数会在字符串str中寻找字符character，找不到，则返回空指针，也就是假，如果能找到，就会返回字符character最后一次出现位置的指针。在这里，为了解决__FILE__将包括路径在内的完整文件名都替换出来的问题，设计了宏__M_FILE__，如果找不到用于分隔目录的反斜杠’\‘，那就替换成__FILE__本身，如果找得到，那就加1跳过’\‘,只要后面的字符串。这里为了防止编译器把’\‘当成转义字符，所以有两个反斜杠。同时为了避免括号打乱三目操作符的顺序，只在最外层打了括号。另外，函数exit头文件为stdlib.h，需要包含。

函数写好了，就要在 test.c 中测试一下，等确认Bug(准确来说是自己能找到的Bug)都找完了，再去写下一个函数。我就不带着测了，要是你用我的代码测出了问题，就请在评论区说一下。

SL销毁

如果一个类型为SL的变量不再使用，就要进行销毁。销毁函数就很简单，如下：

//SL销毁函数
void SLDestroy(SL* s_Destroy)
{
	__BUG_NULL__(s_Destroy);
	free(s_Destroy->arr);
	s_Destroy->arr = NULL;
	s_Destroy->capacity = s_Destroy->size = 0;
}

使用指针时先判断是否为空，动态开辟的内存要用free释放，不用的指针要置为空，内存释放后，就没有数据了，capacity和size都要置为空。

同理，写完的函数也要测试一下。

SL尾插函数

如果要在顺序表末尾插入一个数据的话，则需要尾插函数，如下：

//SL尾插函数
void SLPushBack(SL* ps_PushBack, SLDataType x)
{
	__BUG_NULL__(ps_PushBack);
	ps_PushBack->arr[ps_PushBack->size] = x;
	ps_PushBack->size++；
}

push不就是汇编里的压栈指令吗，back是尾部，所以命名为SLPushBack；ps_PushBack是要插入的SL变量指针，x则是要插入的数据，其类型取决于SL中存储的数据，所以使用 SLDataType 类型；指针使用前要判断是否为空，所以要用宏__BUG_NULL__检测，插入过后，有效数据的个数增多了，所以要让size++。

但这样写很明显是有问题的，要先判断是否有剩余空间，再进行插入，所以有了SL扩展函数

SL扩展函数

//SL扩展函数
static void SLExpand(SL** pps_Expand)
{
	__BUG_NULL__(*pps_Expand);
	int newcapacity = (*pps_Expand)->capacity == 0 ? 4 : (*pps_Expand)->capacity * 2;
	SLDataType* p = Realloc(SLDataType, (*pps_Expand)->arr, newcapacity);
	__BUG_NULL__(p);
	(*pps_Expand)->arr = p;
	(*pps_Expand)->capacity = newcapacity;
}

关键字static限定了该函数的作用范围，使得其只能在定义所在文件起作用；newcapacity，顾名思义，就是新的可容纳数据个数，为了避免频繁扩展，这里把newcapacity的值定为原capacity的两倍，具体为什么是两倍，这涉及到某些数学上的概率统计问题，在此不予深究；同时为了防止原capacity就是0，使用了三目操作符，如果原capacity就是0，则把newcapacity定为4；这里使用宏Realloc进行内存开辟，其定义如下：

#define Realloc(type, p, n) (type*)realloc(p, n * sizeof(type))

这里不用在意p是否会出现空的可能，我们在动态内存管理说过，如果传入的p是空指针，则说明没有原空间，realloc会直接开辟一个符合大小的新空间，此种情况下，realloc就相当于malloc。

为了防止内存开辟失败，我们使用第三方指针接收地址，再判断是否为空，不为空之后再传给arr，同时既然可容纳数据个数发生了改变，capacity自然也要进行调整。最后，SL尾插函数是这样的：

//SL扩展函数
static void SLExpand(SL** pps_Expand)
{
	__BUG_NULL__(*pps_Expand);
	int newcapacity = (*pps_Expand)->capacity == 0 ? 4 : (*pps_Expand)->capacity * 2;
	SLDataType* p = Realloc(SLDataType, (*pps_Expand)->arr, newcapacity);
	__BUG_NULL__(p);
	(*pps_Expand)->arr = p;
	(*pps_Expand)->capacity = newcapacity;
}

//SL尾插函数
void SLPushBack(SL* ps_PushBack, SLDataType x)
{
	__BUG_NULL__(ps_PushBack);
	if (ps_PushBack->capacity == ps_PushBack->size)
	{
		SLExpand(&ps_PushBack);
	}
	ps_PushBack->arr[ps_PushBack->size++] = x;
}

别忘了函数写好之后测试一下

SL尾删函数

void SLPopBack(SL* ps_PopBack)
{
	__BUG_NULL__(ps_PopBack);
	ps_PopBack->size--;
}

我们之前说过,size描述的是有效的数据个数，这意味着，下标介于0到size-1的数据才是有效数据，所以直接让size–就等同于删除了这个数。不过这个函数仍有问题，删除数据的前提是SL中仍有数据可以删除，所以可以稍微优化一下：

void SLPopBack(SL* ps_PopBack)
{
	__BUG_NULL__(ps_PopBack);
	if (ps_PopBack->size)
	{
		ps_PopBack->size--;
	}
	else
	{
		printf("This memory block no longer contains valid data.\n");
		printf("%s\n", __M_FILE__);
		printf("%d\n\n", __LINE__);
		exit(EOF);
	}
}

即使这样，这个函数仍然不够好，都说了这是动态顺序表，既然都有了扩展函数，为什么不能有缩小函数呢？于是，就有了SL缩小函数

//SL缩小函数
static void SLContract(SL** pps_Contract)
{
	__BUG_NULL__(*pps_Contract);
	int newcapacity = (*pps_Contract)->size == 0 ? 4 : (*pps_Contract)->size;
	SLDataType* p = Realloc(SLDataType, (*pps_Contract)->arr, newcapacity);
	__BUG_NULL__(p);
	(*pps_Contract)->arr = p;
	(*pps_Contract)->capacity = newcapacity;
}

与SL扩展函数有着相同的逻辑，在此不作解释。

于是，SL尾删函数就是这样的：

//SL缩小函数
static void SLContract(SL** pps_Contract)
{
	__BUG_NULL__(*pps_Contract);
	int newcapacity = (*pps_Contract)->size == 0 ? 4 : (*pps_Contract)->size;
	SLDataType* p = Realloc(SLDataType, (*pps_Contract)->arr, newcapacity);
	__BUG_NULL__(p);
	(*pps_Contract)->arr = p;
	(*pps_Contract)->capacity = newcapacity;
}

void SLPopBack(SL* ps_PopBack)
{
	__BUG_NULL__(ps_PopBack);
	if (ps_PopBack->size)
	{
		ps_PopBack->size--;
	}
	else
	{
		printf("This memory block no longer contains valid data.\n");
		printf("%s\n", __M_FILE__);
		printf("%d\n\n", __LINE__);
		exit(EOF);
	}
	if (ps_PopBack->size * 2 < ps_PopBack->capacity)
	{
		SLContract(&ps_PopBack);
	}
}

SL头插函数

void SLPushFront(SL* ps_PushFront, SLDataType x)
{
	__BUG_NULL__(ps_PushFront);
	if (ps_PushFront->capacity == ps_PushFront->size)
	{
		SLExpand(&ps_PushFront);
	}
	int i = 0;
	for (i = ps_PushFront->size; i > 0; i--)
	{
		ps_PushFront->arr[i] = ps_PushFront->arr[i - 1];
	}
	ps_PushFront->arr[0] = x;
	ps_PushFront->size++;
}

SL头删函数

//SL头删函数
void SLPopFront(SL* ps_PopFront)
{
	__BUG_NULL__(ps_PopFront);
	if (ps_PopFront->size)
	{
		int i = 0;
		for (i = 0; i < ps_PopFront->size - 1; i++)
		{
			ps_PopFront->arr[i] = ps_PopFront->arr[i + 1];
		}
		ps_PopFront->size--;
	}
	else
	{
		printf("This memory block no longer contains valid data.\n");
		printf("%s\n", __M_FILE__);
		printf("%d\n\n", __LINE__);
		exit(EOF);
	}
	if (ps_PopFront->size * 2 < ps_PopFront->capacity)
	{
		SLContract(&ps_PopFront);
	}
}

道理相通，不作解释。

SL指定位置插入

相当于不完全头插：

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(0 <= pos && pos <= ps->size);
	if (ps->capacity == ps->size)
	{
		SLExpand(&ps);
	}
	int i = 0;
	for (i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

因为这里用的是断言，所以就不在ps后加后缀了。

SL指定位置删除

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(0 <= pos && pos < ps->size);
	if (ps->size)
	{
		int i = 0;
		for (i = pos; i < ps->size - 1; i++)
		{
			ps->arr[i] = ps->arr[i + 1];
		}
		ps->size--;
	}
	else
	{
		printf("This memory block no longer contains valid data.\n");
		printf("%s\n", __M_FILE__);
		printf("%d\n\n", __LINE__);
		exit(EOF);
	}
	if (ps->size * 2 < ps->capacity)
	{
		SLContract(&ps);
	}
}

SL查找

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

找不到就返回一个非法下标。

原代码

SeqList.c

#include"SeqList.h"

 //SL初始化
#ifndef __SLINT__

#ifdef __SLINT_DEBUG__

void SLInit(SL* ps_Init)
{
	ps_Init->arr = NULL;
	ps_Init->capacity = ps_Init->size = 0;
}

#else

void SLInit(SL* ps_Init)
{
	__BUG_NULL__(ps_Init);
	ps_Init->arr = NULL;
	ps_Init->capacity = ps_Init->size = 0;
}

#endif

#else

void SLInit(SL s_Init)
{
	s_Init.arr = NULL;
	s_Init.capacity = s_Init.size = 0;
}
#endif

//SL销毁函数
void SLDestroy(SL* s_Destroy)
{
	__BUG_NULL__(s_Destroy);
	free(s_Destroy->arr);
	s_Destroy->arr = NULL;
	s_Destroy->capacity = s_Destroy->size = 0;
}

//SL扩展函数
static void SLExpand(SL** pps_Expand)
{
	__BUG_NULL__(*pps_Expand);
	int newcapacity = (*pps_Expand)->capacity == 0 ? 4 : (*pps_Expand)->capacity * 2;
	SLDataType* p = Realloc(SLDataType, (*pps_Expand)->arr, newcapacity);
	__BUG_NULL__(p);
	(*pps_Expand)->arr = p;
	(*pps_Expand)->capacity = newcapacity;
}

//SL缩小函数
static void SLContract(SL** pps_Contract)
{
	__BUG_NULL__(*pps_Contract);
	int newcapacity = (*pps_Contract)->size == 0 ? 4 : (*pps_Contract)->size;
	SLDataType* p = Realloc(SLDataType, (*pps_Contract)->arr, newcapacity);
	__BUG_NULL__(p);
	(*pps_Contract)->arr = p;
	(*pps_Contract)->capacity = newcapacity;
}

//SL尾插函数
void SLPushBack(SL* ps_PushBack, SLDataType x)
{
	__BUG_NULL__(ps_PushBack);
	if (ps_PushBack->capacity == ps_PushBack->size)
	{
		SLExpand(&ps_PushBack);
	}
	ps_PushBack->arr[ps_PushBack->size++] = x;
}

//SL尾删函数
#ifndef __SLPOPBACK__
void SLPopBack(SL* ps_PopBack)
{
	__BUG_NULL__(ps_PopBack);
	if (ps_PopBack->size)
	{
		ps_PopBack->size--;
	}
	else
	{
		printf("This memory block no longer contains valid data.\n");
		printf("%s\n", __M_FILE__);
		printf("%d\n\n", __LINE__);
		exit(EOF);
	}
	if (ps_PopBack->size * 2 < ps_PopBack->capacity)
	{
		SLContract(&ps_PopBack);
	}
}

#else

void SLPopBack(SL* ps_PopBack)
{
	__BUG_NULL__(ps_PopBack);
	ps_PopBack->size--;
	if (ps_PopBack->size * 2 < ps_PopBack->capacity)
	{
		SLContract(&ps_PopBack);
	}
}

#endif

//SL头插函数
void SLPushFront(SL* ps_PushFront, SLDataType x)
{
	__BUG_NULL__(ps_PushFront);
	if (ps_PushFront->capacity == ps_PushFront->size)
	{
		SLExpand(&ps_PushFront);
	}
	int i = 0;
	for (i = ps_PushFront->size; i > 0; i--)
	{
		ps_PushFront->arr[i] = ps_PushFront->arr[i - 1];
	}
	ps_PushFront->arr[0] = x;
	ps_PushFront->size++;
}

//SL头删函数
void SLPopFront(SL* ps_PopFront)
{
	__BUG_NULL__(ps_PopFront);
	if (ps_PopFront->size)
	{
		int i = 0;
		for (i = 0; i < ps_PopFront->size - 1; i++)
		{
			ps_PopFront->arr[i] = ps_PopFront->arr[i + 1];
		}
		ps_PopFront->size--;
	}
	else
	{
		printf("This memory block no longer contains valid data.\n");
		printf("%s\n", __M_FILE__);
		printf("%d\n\n", __LINE__);
		exit(EOF);
	}
	if (ps_PopFront->size * 2 < ps_PopFront->capacity)
	{
		SLContract(&ps_PopFront);
	}
}

//SL指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(0 <= pos && pos <= ps->size);
	if (ps->capacity == ps->size)
	{
		SLExpand(&ps);
	}
	int i = 0;
	for (i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

//SL指定位置删除
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(0 <= pos && pos < ps->size);
	if (ps->size)
	{
		int i = 0;
		for (i = pos; i < ps->size - 1; i++)
		{
			ps->arr[i] = ps->arr[i + 1];
		}
		ps->size--;
	}
	else
	{
		printf("This memory block no longer contains valid data.\n");
		printf("%s\n", __M_FILE__);
		printf("%d\n\n", __LINE__);
		exit(EOF);
	}
	if (ps->size * 2 < ps->capacity)
	{
		SLContract(&ps);
	}
}

//SL查找
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	return EOF;
}

SeqList.h

#pragma once

#define __DEBUG__ //总Debug开关


 //#define __SLINT__//SLInit条件编译总开关，打开进入错误示范
//#define __SLINT_DEBUG__//打开为SLInit初始版本，没有判断形参是否为空；关闭为SLInit修正版本，判断了形参是否为空

//#define __SLPOPBACK__//打开版本健壮性不足，关闭为修正版

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
#include"vld.h"


#define __M_FILE__ (strrchr(__FILE__,'\\') ? strrchr(__FILE__,'\\') + 1 : __FILE__)

#define __BUG_NULL__(p) \
		if(p == NULL)\
		{\
		printf("\nBug!\n");\
		printf("The address " #p " is null." "\n");\
		printf("%s\n",__M_FILE__);\
		printf("%d\n",__LINE__);\
		exit(EOF);\
		}

#define Realloc(type, p, n) (type*)realloc(p, n * sizeof(type))


typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* arr;
	int size;
	int capacity;
}SL;


//SL初始化
//Init全写：initialization意为初始化
#ifndef __SLINT__

#ifdef __SLINT_DEBUG__

void SLInit(SL* ps_Init);

#else

void SLInit(SL* ps_Init);

#endif

#else

void SLInit(SL s_Init);

#endif

//SL销毁函数
//Destory就是全写，意为销毁，破坏
void SLDestroy(SL* s_Destroy);

//SL尾插函数
void SLPushBack(SL* ps_PushBack, SLDataType x);

//SL尾删函数
void SLPopBack(SL* ps_PopBack);

//SL头插函数
void SLPushFront(SL* ps_PushFront, SLDataType x);

//SL头删函数
void SLPopFront(SL* ps_PopFront);

//SL指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x);

//SL指定位置删除
void SLErase(SL* ps, int pos);

//SL查找
int SLFind(SL* ps, SLDataType x);

test.c

#include"SeqList.h"

void SLInit_test(void)
{
	SL s;
#ifndef __SLINT__

#ifdef __SLINT_DEBUG__

	SLInit(&s);

#else

	SLInit(NULL);

#endif

#else

	SLInit(s);

#endif
}

static SLprintf(SL* p)
{
	int i = 0;
	printf("\n");
	for (i = 0; i < p->size; i++)
	{
		printf("%d ", p->arr[i]);
	}
	printf("\n\n");
}

void SLPushBack_test(void)
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushBack(&s, 5);
	SLPushBack(&s, 6);
	SLPushBack(&s, 7);
	SLPushFront(&s, 8);
	SLPushFront(&s, 9);
	SLPushFront(&s, 10);
	SLPushFront(&s, 11);
	SLPushFront(&s, 12);

	SLprintf(&s);
	SLPopFront(&s);
	SLPopFront(&s);
	SLPopFront(&s);
	SLPopFront(&s);
	SLPopFront(&s);
	SLPopFront(&s);
	SLPopFront(&s);

	SLPopFront(&s);
	SLPopFront(&s);
	SLprintf(&s);
	SLInsert(&s, 1, 4);
	SLErase(&s, 1);
	int a = SLFind(&s, 7);
	if (a < 0)
	{
		printf("找不到\n");
	}
	else
	{
		printf("找到了，下标为%d\n", a);
	}
	SLDestroy(&s);
}


int main()
{
	//SLInit_test();
	SLPushBack_test();
	return 0;
}

完