详解顺序表的接口函数

新建一个头文件（SL.h）和两个源文件(SL.c和test.c)

SL.h用来包含头文件，结构体的定义还有接口函数的声明
SL.c用来放顺序表的接口函数的实现
test.c用来测试代码

将对头文件的包含和结构体的定义都放在SL.h中

为什么要将int 重命名为SLDataType呢？
这是为了以后如果改变了SL结构体中数据存储的类型时，不用到处改函数参数等地方的数据类型，只要改typedef后的int 为对应要改成的数据类型就可以。

SL结构体中的
a是用来接收malloc的空间的指针，用来存放顺序表要存放的数据
size用于表示当前顺序表中有多少个有效数据
capacity则表示顺序表的最大容量

初始化函数

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

将a指向空，size=0，capacity的初始值为0（或者其他）

尾插

void SeqListPushBack(SL* ps, SLDataType x)
{
	//增容
	if ((ps->size)==(ps->capacity))
	{
		ADD_capacity(ps);
	}
	ps->a[ps->size] = x;
	ps->size++;
}

如果ps->size==ps->capacity
则表示顺序表已满，需要增加容量
如果没满，就在顺序表的当前最后一个有效数据的下一个位置插入数据，并让size++表示有效数据加一。

增容函数

void ADD_capacity(SL* ps)
{
	SLDataType capacity = ps->capacity ? (ps->capacity) * 2 : 4;//看容量是否为0，
	//如果是就申请可存4个数据个数的字节数，
	//如果不是0，就在原来容量的基础上乘以2
	SLDataType* tmp = (SLDataType*)realloc(ps->a, capacity * sizeof(SLDataType));
	if(tmp==NULL)
	{
		printf("增容失败！");
		exit(-1);//结束程序
	}
	ps->a = tmp;//**设置变量tmp防止a接收到NULL，导致增容前的数据也消失**
	ps->capacity = capacity;
}

尾删

void SeqListPopBack(SL* ps)
{
	assert(ps->size!=0);
	ps->size--;
}

为了防止顺序表已经为空时还尾删的错误操作，用assert来防止
assert函数的作用：如果assert（）中的表达式为假，它就会弹窗报错，并告知报错assert的位置

因为size表示的是顺序表的有效数据（所以如果取出size-1之后的下标的数据就是违规操作了），所以尾删时只要size–就可以了。

头插

void SeqListPushFront(SL* ps, SLDataType x)
{
	//增容
	if ((ps->size) == (ps->capacity))
	{
		ADD_capacity(ps);
	}
	int i = ps->size;//防止数据被覆盖，所以从最后一个数据开始向后挪
	while (i>=1)
	{
		ps->a[i]= ps->a[i - 1];
		i--;
	}
	ps->a[0] = x;
	ps->size++;
}

头插数据时也要看顺序表是否满了，如果满了就要增容。
头插时为了保证原来的第一个数据不被覆盖，需要将顺序表中头插前的所有数据向后移动一位。
挪动数据的方法是：从最后一个数据开始向后挪（因为从开头的一个数据开始挪，会将第二个数据覆盖）

头删

void SeqListPopFront(SL* ps)
{
	int i =0;
	assert(ps->size != 0);//防止顺序表为空还删
	//挪动覆盖
	while (i<ps->size-1)
	{
		ps->a[i] = ps->a[i + 1];
		i++;
	}
	ps->size--;
}

头删删除数据之前也要考虑顺序表是否为空。
删除方法是挪动覆盖，即用第二个数据将第一个数据覆盖，用第三个数据将第二个数据覆盖…以此类推
覆盖完成后size再–。

查找数据

int SeqListFind(SL* ps, SLDataType x)
{
	int i = 0;
	while (i < ps->size)
	{
		if (ps->a[i] == x)
		{
			return i;//找到了就返回下标
		}
		i++;
	}
	return -1;//找不到就返回-1
}

遍历一遍顺序表，找到等于参数x的就返回对应下标，找不到就返回-1。

随机插入

//随机插入//pos为下标
void SeqListInsert(SL* ps,int pos, SLDataType x)
//增容
if ((ps->size) == (ps->capacity))
{
	ADD_capacity(ps);
}
int i = ps->size;
//将pos后的数据一起向后挪动一位，给pos的插入腾出位置
while (i >pos)
{
	ps->a[i] = ps->a[i - 1];
	i--;
}
ps->a[pos] = x;
ps->size++;

随机插入，即在对应下标插入数据，只要是插入数据就要考虑顺序表是否满了，为了防止插入前的pos下标对应数据被覆盖，让pos下标数据及其后数据向后挪动一位，也是最后一个数据开始挪。

随机删除

void SeqListErase(SL* ps, int pos)
{
	int i = pos;
	assert(ps->size != 0);
	//挪动覆盖
	while (i < ps->size - 1)
	{
		ps->a[i] = ps->a[i + 1];
		i++;
	}
	ps->size--;
}

只要是删除数据就要防止删除时顺序表为空。
删除pos下标对应数据的方法是，用其后的数据将其覆盖。

打印顺序表

void SeqListPrint(SL* ps)
{
	int i = 0;
	while (i < ps->size)
	{
		printf("%d  ", ps->a[i]);
		i++;
	}
}

销毁顺序表

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

所有代码

SL.h

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLDataType;

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

//增容
void ADD_capacity(SL* ps);
//初始化
void SeqListInit(SL* ps);
//插入数据--尾插
void SeqListPushBack(SL* ps, SLDataType x);
//尾删
void SeqListPopBack(SL* ps);
//头插
void SeqListPushFront(SL* ps, SLDataType x);
//尾删
void SeqListPopBack(SL* ps);
//头删
void SeqListPopFront(SL* ps);
//打印顺序表
void SeqListPrint(SL* ps);
//销毁顺序表
void SeqListDestroy(SL* ps);
//查找x的位置//找到了返回x的下标，找不到返回-1
int SeqListFind(SL* ps, SLDataType x);
//随机插入//pos为下标
void SeqListInsert(SL* ps,int pos, SLDataType x);
//删除pos下标的数据
void SeqListErase(SL* ps, int pos);

SL.c

#define _CRT_SECURE_NO_WARNINGS
#include"test.h"
void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
void ADD_capacity(SL* ps)
{
	SLDataType capacity = ps->capacity ? (ps->capacity) * 2 : 4;
	SLDataType* tmp = (SLDataType*)realloc(ps->a, capacity * sizeof(SLDataType));
	if(tmp==NULL)
	{
		printf("增容失败！");
		exit(-1);
	}
	ps->a = tmp;
	ps->capacity = capacity;
}


void SeqListPushBack(SL* ps, SLDataType x)
{
	//增容
	if ((ps->size)==(ps->capacity))
	{
		ADD_capacity(ps);
	}
	ps->a[ps->size] = x;
	ps->size++;
}

void SeqListPrint(SL* ps)
{
	int i = 0;
	while (i < ps->size)
	{
		printf("%d  ", ps->a[i]);
		i++;
	}
}

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

void SeqListPopBack(SL* ps)
{
	assert(ps->size!=0);
	ps->size--;
}

void SeqListPushFront(SL* ps, SLDataType x)
{
	//增容
	if ((ps->size) == (ps->capacity))
	{
		ADD_capacity(ps);
	}
	int i = ps->size;
	while (i>=1)
	{
		ps->a[i]= ps->a[i - 1];
		i--;
	}
	ps->a[0] = x;
	ps->size++;
}

void SeqListPopFront(SL* ps)
{
	int i =0;
	assert(ps->size != 0);
	//挪动覆盖
	while (i<ps->size-1)
	{
		ps->a[i] = ps->a[i + 1];
		i++;
	}
	ps->size--;
}

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

void SeqListInsert(SL* ps,int pos,SLDataType x)
{
	//增容
	if ((ps->size) == (ps->capacity))
	{
		ADD_capacity(ps);
	}
	int i = ps->size;
	//将pos后的数据一起向后挪动一位，给pos的插入腾出位置
	while (i >pos)
	{
		ps->a[i] = ps->a[i - 1];
		i--;
	}
	ps->a[pos] = x;
	ps->size++;
}

void SeqListErase(SL* ps, int pos)
{
	int i = pos;
	assert(ps->size != 0);
	//挪动覆盖
	while (i < ps->size - 1)
	{
		ps->a[i] = ps->a[i + 1];
		i++;
	}
	ps->size--;
}

以上就是所有内容了，如果对你有帮助，可以点个赞支持一下！