C语言详解 顺序表的功能实现_c语言的动态顺序表

目录

• 前言
• ⚪顺序表的定义
• ⚪动态顺序表的优点
• 头文件
• 具体函数功能
• ⚪初始化顺序表
• ⚪打印顺序表
• ⚪销毁/释放顺序表
• ⚪检查/增容顺序表
• ⚪顺序表尾插
• ⚪顺序表尾删
• ⚪顺序表头插
• ⚪顺序表头删
• ⚪查找顺序表某个数字
• ⚪指定下标位置插入(头插尾插的修改)
• ⚪指定下标位置删除(头删尾删的修改)
• ⚪更改指定下标元素
• 完整代码及测试用例

前言

顺序表的定义

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

---

动态顺序表的优点

• 由于静态顺序表更适用于明确知道多少数据需要存储的场景中，很多时候静态顺序表会出现空间浪费(开多了空间)或者空间不够用(开少了空间)的情况。
• 动态顺序表可以根据需要动态分配空间。

---

接口实现

顺序表在实现上与c语言通讯录项目有一些相似之处，我们仍采用三文件进行编写：

• SeqList.h —— 用于函数声明，类型定义和头文件引用
• SeqList.c —— 用于函数实现
• test.c —— 主函数

---

头文件

#pragma once

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

typedef int SLDataType;

//动态顺序表
typedef struct SeqList
{
	SLDataType* a;//数组指针，指向动态开辟内存的数组
	int size;//数组存储数据的个数
	int capacity;//数组实际存的数据最大容量
}SL;//重定义类型名

//接口函数
//打印顺序表
void SeqListPrint(SL* ps);
//初始化
void SeqListInit(SL* ps);
//清空
void SeqListDestory(SL* ps);
//尾插
void SeqListPushBack(SL* ps, SLDataType x);
//尾删
void SeqListPopBack(SL* ps);
//头插
void SeqListPushFront(SL* ps, SLDataType x);
//头删
void SeqListPopFront(SL* ps);
//查找
int SeqListFind(SL* ps, SLDataType x);
//指定下标位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x);
//删除指定下标的指定数据
void SeqListErase(SL* ps, int pos, SLDataType x);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

typedef int SLDataType;的意义是当需要改变顺序表的数据类型时直接改变此int即可。
因为要实际存入数据到顺序表中，所以函数传值传其结构体指针。

---

具体函数功能

初始化顺序表

初始化表的成员变量即可：将顺序表的数组指针置空，size和capacity置零

void SeqListInit(SL* ps)
{
	asssert(ps != NULL);//防止传入的指针为空
	ps->a = NULL;//初始数组置空
	ps->size = ps->capacity = 0;//初始数据个数和容量置空
}
1
2
3
4
5
6

---

打印顺序表

以元素个数size为界，遍历打印每一个元素。

void SeqListPrint(SL* ps)
{
	asssert(ps != NULL);
	for (int i = 0; i < ps->size; i++)//打印当前的数据个数位
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9

---

销毁顺序表

释放数组指针并置空，size，capacity置零。

void SeqListDestory(SL* ps)
{
	free(ps->a);//释放动态开辟的空间
	ps->a = NULL;//数组置空
	ps->size = ps->capacity = 0;//数据个数和容量重新置为零
}
1
2
3
4
5
6

---

检查/增容顺序表容量

• 由于在尾插和头插顺序表时均需要先确定是否需要增容，所以我们把检查增容的代码单独写一个函数
• 增容我们选用每次增加二倍，如果每次增容三倍或往上会造成严重的内存浪费；如果一个一个容量扩容，每次插入都会进行增容，效率低。

void SeqListCheckCapacity(SL* ps)
{
	//如果没有空间或空间不足，扩容
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));//重设大小
		if (tmp == NULL)//判断realloc是否成功
		{
			perror(SeqListPushBack);//不成功报错
			exit(-1);//退出程序
		}
		ps->a = tmp;//将增容后的空间给ps->a
		ps->capacity = newcapacity;//将容量扩大
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这里使用三目运算符ps->capacity == 0 ? 4 : ps->capacity * 2;即如果初始容量为零则设为4否则变成二倍；
realloc在申请空间时，如果数组本身没有空间那么realloc的作用和malloc一样
如果realloc开辟空间失败会返回空，所以判断tmp是否为空

---

顺序表尾插

• 尾插是每次从后插入，所以每次插入把ps->size++即可

void SeqListPushBack(SL* ps, SLDataType x)
{
	SeqListCheckCapacity(ps);//先检查是否需要增容
	//存储
	ps->a[ps->size] = x;//将需要插入的数据x放入
	ps->size++;//size++，
}
1
2
3
4
5
6
7

---

顺序表尾删

• 尾插从尾部进行，直接ps->size--即可

void SeqListPopBack(SL* ps)
{
	//ps->a[ps->size - 1] = 0;		<-没必要，该位置本来就可能为零，size--后该位置直接被删去
	
	//if (ps->size > 0)//防止越界
	//{
	//	ps->size--;
	//}
	assert(ps->size > 0);
	ps->size--;
}
1
2
3
4
5
6
7
8
9
10
11

这里if(ps->size>0)也可以，这样当我们删的次数超过顺序表元素后，ps->size将不再减小，即最多减到零；而assert(ps->size > 0)会在我们删除过多后直接assert报错。

---

顺序表头插

• 把数据最后一位作为end，每次将该位赋到下一位后再向前移动
• 即先将数据5放到end+1位，end再向前移

void SeqListPushFront(SL* ps, SLDataType x)
{
	//先检查是否需要扩容
	SeqListCheckCapacity(ps);
	int end = ps->size - 1;//end为顺序表最后一个元素的下标位置
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];//数据后移
		end--;
	}
	ps->a[0] = x;//把首位赋值为数据x
	ps->size++;//数据个数增加
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

顺序表头删

• 头插将首位元素后的元素前移即可
• 具体操作 每次将begin位的元素赋值给前一位，随后begin给到下一位，循环往复

void SeqListPopFront(SL* ps)
{
	assert(ps->size > 0);//断言数据个数大于0
	int begin = 1;//从第二位设置begin
	//数据前移
	while (begin < ps->size)//begin小于数据个数
	{
		ps->a[begin - 1] = ps->a[begin];//数据前移
		++begin;
	}
	ps->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12

---

查找顺序表某个数字

• 遍历顺序表的所有位即可，找到返回下标，找不到返回-1

int SeqListFind(SL* ps, SLDataType x)
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11

---

指定下标位置插入

• 这里同样像尾删那样可以选择if判断或assert断言，我们都选用断言
• 将pos位的所有元素后移一位，随后在pos位插入元素。

void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	/*if (pos > ps->size || pos < 0)
	{
		printf("pos Invalid\n");
		return;
	}*/
	assert(pos >= 0 && pos <= ps->size);//插入0-size的任意位置
	SeqListCheckCapacity(ps);//判断是否扩容
	int end = ps->size - 1;
	//后移
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

当此代码写完后，我们可以修改尾插和头插的内容

//尾插
void SeqListPushBack(SL* ps, SLDataType x)
{
	SeqListInsert(ps, ps->size, x);//从size下标插入
}
//头插
void SeqListPushFront(SL* ps, SLDataType x)
{
	SeqListInsert(ps, 0, x);//从零下标插入
}
1
2
3
4
5
6
7
8
9
10

---

指定下标位置删除

• 把pos（待删除元素位置）后面的元素全部前移一位即可。

void SeqListErase(SL* ps, int pos)
{
	//这里同样可以用if语句，我们直接使用assert
	assert(pos >= 0 && pos < ps->size);
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12

和上一个相同，我们也可以由此改变尾删和头删。’

//尾删
void SeqListPopBack(SL* ps)
{
	SeqListErase(ps, ps->size - 1);//删除size-1下标元素
}
//头删
void SeqListPopFront(SL* ps)
{
	SeqListErase(ps, 0);//删除0下标元素
}
1
2
3
4
5
6
7
8
9
10

---

更改指定下标元素

• pos只能更改0~size下标的数据，且本身顺序表要有元素
• 保证不越界后直接修改

void SeqListModify(SL* ps, int pos, SLDataType x)
{
	assert(ps->size > 0 && pos >= 0 && pos < ps->size);//确保pos的范围合法，顺序表有元素0
	ps->a[pos] = x;//更改
}
1
2
3
4
5

---

完整代码及测试用例

卜及中-动态顺序表完整代码