动态顺序表的增删查改（C语言实现）

有礼貌的灰绅士

发布于 2023-03-28 15:24:23

5860

发布于 2023-03-28 15:24:23

文章被收录于专栏：C++与Linux的学习之路

动态顺序表

准备工作

我们还是分一个头文件和两个源文件

sequence.h sequence.c test.c

sequence.h

#include <stdio.h>
typedef struct Sequence_List
{
	int* p;//顺序表的初始地址
	int count;//元素数量
	int capacity;//容量
}SL;//顺序表的动态储存

sequence.c

void Initialize(SL* s)//初始化顺序表
{
	assert(s);//判断s是否为空指针
	s->p = NULL;
	s->count = 0;
	s->capacity = 0;
}

void Destroy(SL* s)//释放顺序表内存
{
	assert(s);
	free(s->p);
	s->p = NULL;
	s->count = 0;
	s->capacity = 0;
}

检查，扩容

sequence.c

void SeqListInit(SL* s)//检查，扩容
{
	assert(s);
	if (s->capacity == s->count)//判断是否满足扩容条件
	{
		int i = (s->capacity == 0 ? 4 : s->capacity*2);//第一次扩容4，后续的扩容都是之前的两倍
		SLData* p1 = (SLData*)realloc(s->p, sizeof(SLData) * i);
		if (p1 == NULL)//判断，防止空指针让原本的位置丢失
		{
			perror("realloc fail");//开辟失败报错
			return;
		}
		s->p = p1;
		s->capacity = i;//容量增加
	}
}

头插头删，尾插尾删

sequence.c 尾插：

void SeqListPushBack(SL* s, SLData x)//尾插，x是你要插入的元素
{
	assert(s);
	SeqListInit(s);//检查空间是否需要扩容
	s->p[s->count] = x;//插入
	s->count++;//元素数量增加
}

头插：

void SeqListPopBack(SL* s, SLData x)//头插
{
	assert(s);
	SeqListInit(s);
	int i = 0;
	int j = s->count;
	for (i = j; i > 0; i--)
	{
		s->p[j] = s->p[j - 1];//移动已有元素
	}
	s->p[0] = x;//在第一个元素的位置插入你想要的数值
	s->count++;
}

尾删：

void SeqListPopBack(SL* s)//尾删
{
	assert(s);
	assert(s->count > 0);//判断数量，少于0就不能删除了
	s->count--;
}

头删：

void SeqListPopFront(SL* s)//头删
{
	assert(s);
	assert(s->count > 0);
	int j = 0;
	while (j < s->count)
	{
		s->p[j] = s->p[j + 1];//原理是覆盖
		j++;
	}
	s->count--;
}

顺序表查找

sequence.c

int SeqListFind(SL* s, int x)//搜索，x是你要搜索的数值
{
	assert(s);
	int i = 0;
	for (i = 0; i < s->count; i++)
	{
		if (s->p[i] == x)
		{
			return i;//找到返回下标
		}
	}
	return -1;//找不到返回-1，下标不可能是-1，如果返回-1就说明没找到
}

顺序表打印

sequence.c

void SeqListPrint(SL* s)//打印
{
	assert(s);
	int i = 0;
	for (i = 0; i < s->count; i++)
	{
		printf("%d ", s->p[i]);
	}
	printf("\n");
}

在指定位置插入和删除x

sequence.c pos是指下标。插入：

void SeqListInsert(SL* s, size_t pos, int x)//在pos的位置放入元素x
{
	assert(s);
	assert(pos <= s->count);//判断插入位置是否合法，这里相等也就等于尾插
	SeqListInit(s);
	size_t i = s->count;
	for (i = s->count; i > pos; i--)
	{
		s->p[i] = s->p[i - 1];//往后挪动下标为pos元素后面所有元素的位置
	}
	s->p[pos] = x;//在下标为pos的位置放入x
	s->count++;
}

删除：

void SeqListErase(SL* s, size_t pos)//删除pos位置的元素
{
	assert(s);
	assert(pos < s->count);
	size_t j = pos;
	for (; j < s->count; j++)
	{
		s->p[j] = s->p[j + 1];
	}
	s->count--;
}

完整版顺序表

sequence.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLData;
typedef struct Sequence_List
{
	SLData* p;//顺序表的初始地址
	int count;//元素数量
	int capacity;//容量
}SL;
//函数声明区
void Initialize(SL* s);//初始化
void Destroy(SL* s);//释放内存
void SeqListInit(SL* s);//检查，扩容

void SeqListPushBack(SL* s, SLData x);//尾插
void SeqListPushFront(SL* s, SLData x);//头插
void SeqListPopBack(SL* s);//尾删
void SeqListPopFront(SL* s);//头删

int SeqListFind(SL* s, int x);//搜索

void SeqListPrint(SL* s);//打印顺序表

void SeqListInsert(SL* s, size_t pos, int x);//在pos的位置放入元素x
void SeqListErase(SL* s, size_t pos);//删除pos位置的元素

sequence.c

#include "sequence.h";
void Initialize(SL* s)//初始化顺序表
{
	assert(s);
	s->p = NULL;
	s->count = 0;
	s->capacity = 0;
}
void Destroy(SL* s)//释放顺序表的动态内存
{
	assert(s);
	free(s->p);
	s->p = NULL;
	s->count = 0;
	s->capacity = 0;
}
void SeqListInit(SL* s)//检查，扩容
{
	assert(s);
	if (s->capacity == s->count)
	{
		int i = (s->capacity == 0 ? 4 : s->capacity*2);
		SLData* p1 = (SLData*)realloc(s->p, sizeof(SLData) * i);
		if (p1 == NULL)
		{
			perror("realloc fail");
			return;
		}
		s->p = p1;
		s->capacity = i;
	}
}
void SeqListPushBack(SL* s, SLData x)//尾插
{
	assert(s);
	SeqListInit(s);
	s->p[s->count] = x;
	s->count++;
}
void SeqListPushFront(SL* s, SLData x)//头插
{
	assert(s);
	SeqListInit(s);
	int i = s->count;
	while (i > 0)
	{
		s->p[i] = s->p[i - 1];
		i--;
	}
	s->p[0] = x;
	s->count++;
}
void SeqListPopBack(SL* s)//尾删
{
	assert(s);
	assert(s->count > 0);
	s->count--;
}
void SeqListPopFront(SL* s)//头删
{
	assert(s);
	assert(s->count > 0);
	int j = 0;
	while (j < s->count)
	{
		s->p[j] = s->p[j + 1];
		j++;
	}
	s->count--;
}
int SeqListFind(SL* s, int x)//搜索
{
	assert(s);
	int i = 0;
	for (i = 0; i < s->count; i++)
	{
		if (s->p[i] == x)
		{
			return i;
		}
	}
	return -1;
}
void SeqListPrint(SL* s)//打印
{
	assert(s);
	int i = 0;
	for (i = 0; i < s->count; i++)
	{
		printf("%d ", s->p[i]);
	}
	printf("\n");
}
void SeqListInsert(SL* s, size_t pos, int x)//在pos的位置放入元素x
{
	assert(s);
	assert(pos <= s->count);
	SeqListInit(s);
	size_t i = s->count;
	for (i = s->count; i > pos; i--)
	{
		s->p[i] = s->p[i - 1];
	}
	s->p[pos] = x;
	s->count++;
}
void SeqListErase(SL* s, size_t pos)//删除pos位置的元素
{
	assert(s);
	assert(pos < s->count);
	size_t j = pos;
	for (; j < s->count; j++)
	{
		s->p[j] = s->p[j + 1];
	}
	s->count--;
}

test.c

#include "sequence.h";
void test1()//实验程序的总接口
{
	SL s1;
	Initialize(&s1);
	SeqListPushBack(&s1, 1);//尾插
	SeqListPushBack(&s1, 2);
	SeqListPushBack(&s1, 5);
	SeqListPushBack(&s1, 0);
	SeqListPushFront(&s1, 3);//头插
	SeqListPopBack(&s1);//尾删
	SeqListPopFront(&s1);//头删
	SeqListInsert(&s1, 2, 9);//在pos的位置放入元素x
	SeqListErase(&s1, 3);//删除pos位置的元素
	int num = SeqListFind(&s1, 2);//搜索
	SeqListPrint(&s1);//打印
	printf("%d\n", num);//打印搜索的下标
	Destroy(&s1);
}
int main()
{
	test1();
	return 0;
}

运行结果：