【百度百科】顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序储存是指用一组地址连续的储存单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序储存结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

顺序表一般可以分为：

1) . 静态顺序表


#define N 200//定长数组储存个数
 
typedef int SLDatatype;//类型重命名
 
//静态顺序表
typedef struct SeqList {
	SLDatatype a[N];//定长数组
	size_t size;    //有效数据个数
}SL;

特点：使用定长数组来储存数据元素。

缺点：静态顺序表只适用于确定要储存多少数据元素的场景。若N定大了，则倒置空间开多了浪费；若N定小了，则导致空间不够用。

2) . 动态顺序表

特点：使用动态开辟的数组储存数据元素。

优点：动态顺序表可根据我们的需要自动分配空间。


typedef int SLDatatype;//类型重命名
 
//动态顺序表
typedef struct SeqList {
	SLDatatype* a;//指向动态开辟的数组
	size_t size;//有限数据个数
	size_t capacity;//容量大小
}SL;

二、接口函数的实现

由于静态顺序表定长数组的局限性，在其实际工作中通常使用动态顺序表解决实际问题。所以本文将以动态顺序表的角度来实现。

基本增删查改接口


void SLInit(SL* ps);							 //初始化
void SLPushBack(SL* ps, SLDatatype x);			 //尾插
void SLPopBack(SL* ps);							 //尾删
void SLPushFront(SL* ps, SLDatatype x);			 //头插
void SLPopFront(SL* ps);						 //头删
void SLPrit(SL* ps);							 //打印
void SLDestory(SL* ps);							 //释放
void SLCheckCapacity(SL* ps);					 //检查容量-扩容
void SLInsert(SL* ps, int pos, SLDatatype x);	 //任意位置插入
void SLErase(SL* ps, int pos);					 //任意位置删除
int SLFind(SL* ps, SLDatatype x);				 //查找
void SLModify(SL* ps, int pos, SLDatatype x);    //修改

关于函数以及常量的命名

函数以及常量的命名是随意的，可为了保证代码的可读性以及正规性，建议命名更为正规一些。本文的函数命名方式源于https://cplusplus.com/

1.基本类型的创建


#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
typedef int SLDatatype;//类型重命名
 
//动态顺序表
typedef struct SeqList {
	SLDatatype* a;//指向动态开辟的数组
	size_t size;//有限数据个数
	size_t capacity;//容量大小
}SL;

由于有效数据个数（size）与空间容量（capacity）不可能小于0，所以将其类型定义为size_t（unsigned int）的无符号整型。

2.初始化

将ps指向a并设置为空（NULL），因为是初始化，所以也将有效数据个数（size）与空间容量（capacity）设为0。


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

3.检查容量-扩容

如果空间不够，则使用recalloc扩容。

tmp为指向新开扩的空间的指针。若原先空间为，0将先开辟4个元素的空间；若空间已满，则在原空间容量大小的基础上再增加一倍。（开扩倍数并不固定，为了减少开扩空间的次数并减少所浪费的空间折中采取扩容一倍）


//检查容量-扩容
void SLCheckCapacity(SL* ps) {	
	if (ps->size == ps->capacity) {		//检查空间容量是否为满或空间容量为0
		 ps->capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDatatype* tmp = (SLDatatype*)realloc(ps->a, ps->capacity * sizeof(SLDatatype));
 
		if (tmp == NULL) {
			perror("realloc :");
			exit(-1);
		}
		ps->a = tmp;
	}
}

4.头插

头插：在数组的开头插入一个数据元素。

思路：创建一个 end 变量用来指向要移动的数据，因为指向的是数据的下标，所以是 size 要减 1 。然后进入for循环，将数组中的元素逐一向后传递，直到end为0为止。最后将所要插入的元素插到数组的开头。


void SLPushFront(SL* ps, SLDatatype x) {		//检查容量-扩容
	SLCheckCapacity(ps);
	for (int end = ps->size - 1; end >= 0; --end) {
		ps->a[end + 1] = ps->a[end];
	}
	ps->a[0] = x;
	ps->size++;
}

5.头删

头删：将数组的第一个数据元素删除。

思路：由于有效数据个数（size）可能存在为0的情况，所以需要对有效数据（size）的个数进行断言（assert）。然后进入for循环，将数组中的元素逐一向前传递，直到size-1为止。


//头删
void SLPopFront(SL* ps) {						
	assert(ps->size);
	for (int begin = 0; begin < ps->size-1; ++begin) {
		ps->a[begin] = ps->a[begin+1];
	}
	ps->size--;
}

6.尾插

尾插：在最后插入一个数据元素。

由于存在空间尚未开辟或空间满了的缘故需要进行容量的检查/扩容。


//尾插
void SLPushBack(SL* ps, SLDatatype x) {			
	SLCheckCapacity(ps);            //检查容量-扩容
	ps->a[ps->size] = x;
	ps->size++;
}

7.尾删

尾删：将最后一个数据元素删除。

由于有效数据个数（size）可能存在为0的情况，所以需要对有效数据（size）的个数进行断言（assert）。

注：本函数不需将最后的数据元素进行处理后再ps->size--;因为size代表着有效数据的个数，在size之后的任何数据都无法访问即无效的数据。


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

8.任意位置插入

任意位置插入：对指定的位置进行数据元素的差额u。

通过对pos限制条件的增加，从而保证pos的合法性。创建一个变量 end 记录最后一个的下标 ps->size-1，并通过它来指向要移动的数据，以end >= pos 作为条件对数组中的元素进行向后移动。移动后将数据元素x进行储存。


//任意位置插入
void SLInsert(SL* ps, int pos, SLDatatype x) {
	SLCheckCapacity(ps);                            //检查容量-扩容
	assert(pos >= 0 && pos < ps->size);
	for (int end = ps->size - 1; end >= pos; --end) {
		ps->a[end + 1] = ps->a[end];
	}
	ps->a[pos] = x;
	ps->size++;
}

9.任意位置删除

任意位置删除：最指定位置的数据元素进行删除。

删除指定位置的数据，我们仍然要限制 pos 的位置而进行断言（assert）。

因为 ps->a[size] 这个位置没有效数据，所以删除的位置不能为 ps->a[size]。


//任意位置删除
void SLErase(SL* ps, int pos) {
	assert(pos >= 0 && pos < ps->size-1);
	for (int begin = pos; begin < ps->size; ++begin) {
		ps->a[begin] = ps->a[begin + 1];
	}
	ps->size--;
}

10.打印

打印：将顺序表中所含的数据元素逐一输出


//打印
void SLPrit(SL* ps) {							
	for (int i = 0; i < ps->size; ++i) {
		printf("%d", ps->a[i]);
	}
	printf("\n");
}

11.释放

释放：将开辟的空间进行销毁。

由于空间是动态开辟的，所以空间不用时我们就需要释放。否者将存在内存泄漏的风险。


//释放
void SLDestory(SL* ps) {						
	if (ps->a!=NULL) {
		free(ps->a);
		ps->a = NULL;
		ps->capacity = ps->size = 0;
	}
}

12.查找

查找：在数据元素中查询所需要的数据位置。

由于顺序表（ps）可能存在为空的情况，所以需要对顺序表（ps）进行断言（assert）。


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

13.修改

修改：对数据元素中想要修改的位置进行数据更换

由于顺序表（ps）可能存在为空的情况，所以需要对顺序表（ps）进行断言（assert）。


//修改
void SLModify(SL* ps, int pos, SLDatatype x) {
	assert(ps);
	assert(pos >= 0 && pos < ps->size - 1);
 
	ps->a[pos] = x;
}

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】