【数据结构】手写顺序表【纯C语言版】

【数据结构】手写顺序表【纯C语言版】

摘要：本章主要讲述线性表，以及用C语言代码实现动态的顺序表

---

目录

• • • 1. 什么是线性表
    • • 1.1 概念
      • 1.2 线性表的特点
    • 3. 什么是顺序表
    • • 3.1 概念
      • 3.2 顺序表的分类
    • 4. 动态顺序表的代码实现
    • • 4.1 定义顺序表及其数据元素类型
      • 4.2 顺序表的初始化
      • 4.3 顺序表的增容
      • 4.4 顺序表尾插法
      • 4.5 顺序表尾删法
      • 4.6 打印顺序表
      • 4.7 顺序表头插法
      • 4.8 顺序表头删法
      • 4.9 顺序表的插入
      • 4.10 顺序表的删除
      • 4.11 顺序表的销毁
      • 4.12 思考
    • 5. 源码链接
    • 后记

正文开始

---

1. 什么是线性表 1.1 概念

线性表(Linear list)是n个具有相同特性的数据元素的有限序列。线性表是一 种在实际中广 泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

1.2 线性表的特点

我们知道，由n（n≥0）个数据特性相同的元素构成的有限序列称为线性表，所以线性表中元素的个数n（n≥0）就是线性表的长度，n=0 是称为空表

对于非空线性表或线性结构，有以下几个特点：

1. 存在唯一的一个被称作“第一个”的数据元素；
2. 存在唯一的一个被称作“最后一个”的数据元素；
3. 除第一个数据元素外，结构中的每个数据元素均只有一个前驱；
4. 除最后一个元素之外，结构中的每个数据元素均只有一个后继。

3. 什么是顺序表 3.1 概念

顺序表（Sequentila List）是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。

顺序表的特点：逻辑上相邻的数据元素，在物理上也是相邻的；顺序表是一种随机存取的存储结构

随机存取：可以通过下标直接 *** 作数据元素，与存储位置无关
顺序存取：与随机存取相反，不能通过下标 *** 作数据元素，与存储位置有关
顺序存取就是如果我们要 *** 作第N个元素时，必须把该元素之前的所有元素访问一遍；而随机存取就是直接 *** 作就行了。

3.2 顺序表的分类

1.静态顺序表：使用定长数组存储。
2.动态顺序表：使用动态开辟的数组存储，容量不受限制,支持数据插入,删除,修改等一系列 *** 作。（接下来着重介绍）

4. 动态顺序表的代码实现 4.1 定义顺序表及其数据元素类型

// 定义顺序表中的数据元素的类型
typedef int SLDataType;

// 定义顺序表
typedef struct SeqList
{
	SLDataType* datas; // 数据序列
	size_t size; // 顺序表的有效数据个数
	size_t capacity; // 属性表的最大存储空间,即最多可以保存多少个数据
} SeqList;

使用 typedef 定义顺序表及其数据元素的类型是为了代码的可扩展性，大家想一想，如果有一天我们的数据元素不用 int 了，而是使用double或结构体，那么此时我们只需要修改这里就可以了，这样是不是就避免很多麻烦了呢？

思考：为什么数据序列要使用指针类型？

大家注意，我们这里实现的是动态顺序表，要使用顺序表为动态，我们就需要动态开辟内存，使用指针是为了让其容量不受限；如果我们将数据序列修改为 SLDataType data[50]，那么这样就是一个静态的顺序表了，因为它的长度已经被限定了

4.2 顺序表的初始化

【算法步骤】：

1. 为顺序表 SeqList 动态分配一个预定义大小的数组空间，是数据序列datas 指向这段空间的基地址
2. 将表的当前长度设为0，存储空间设为预定义大小

【算法描述】

#define DEFAULT_SIZE 4
// 初始化顺序表
void SeqListInit(SeqList* ps)
{
	assert(ps);
	// 默认开辟4个SLDataType大小的空间
	ps->data = (SLDataType*)malloc(sizeof(SLDataType) * DEFAULT_SIZE);
	if (ps->datas == NULL)
	{
		perror("申请内存失败");
		exit(-1);
	}
	ps->size = 0;
	ps->capacity = DEFAULT_SIZE;
}

这里我们为顺序表的容量设置了一个常量DEFAULT_SIZE，其常量值为4

【使用】

int main()
{
	SeqList plist;
	SeqListInit(&plist);
}

思考：为什么要传递指针？

因为我们这里需要改变线性表plist中的内容，所以需要传址；如果传值的话ps只是plist的一份临时拷贝，在SeqListInit函数内对ps的修改并不会对plist有任何影响。当然也可以将SeqListInit改造为下面这个：

#define DEFAULT_SIZE 4
SeqList SeqListInit()
{
	// 默认开辟4个SLDataType大小的空间
	SLDataType* ps = (SLDataType*)malloc(sizeof(SLDataType) * DEFAULT_SIZE);
	if (ps == NULL)
	{
		perror("申请内存失败");
		exit(-1);
	}
	SeqList list = { 0 };
	list.datas = ps;
	list.size = 0;
	list.capacity = DEFAULT_SIZE;
	return list;
}

【使用】

int main()
{
	SeqList plist = SeqListInit();
	
}

这是方式是使用返回值完成顺序表的初始化，当然是利用指针还是返回值都是可以的。

4.3 顺序表的增容

【算法步骤】

1. 当顺序表满了的时候进行增容，每次增加原有容量的2倍
2. 判断顺序表是否满了：如果有效数据长度等于最大容量则表面表满

【算法描述】

// 检查增容
void SeqListCheckCapacity(SeqList* ps)
{
	assert(ps);
	if ((ps->size) >= (ps->capacity))
	{
		// 两倍增容
		ps->capacity *= 2;
		ps->datas = (SLDataType*)realloc(ps->datas, ps->capacity * sizeof(SLDataType));
		if (ps->datas == NULL)
		{
			perror("增容失败");
			exit(-1);
		}
	}
}

4.4 顺序表尾插法

【算法步骤】

1. 检查是否需要增容
2. 在下标为size位置处插入数据
3. 有效数据个数加1

【算法描述】

// 顺序表的尾插
void SeqListPushBack(SeqList* ps, SLDataType* data)
{
	assert(ps);

	// 1.检查扩容
	SeqListCheckCapacity(ps);
	// 2.插入数据
	ps->datas[ps->size] = *data;
	// 3.有效数据个数加1
	(ps->size) ++;
}

4.5 顺序表尾删法

【算法步骤】

1. 判断是否是空表，空表则中断
2. 有效数据个数减1即可

【算法描述】

// 顺序表的尾删
void SeqListPopBack(SeqList* ps) 
{
	assert(ps);
	// 空表时中断
	assert(ps->size > 0);
	// 有效数据减1
	(ps->size)--;
}

4.6 打印顺序表

void SeqListPrint(SeqList* ps)
{
	assert(ps);

	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->datas[i]);
	}
	putchar('n');
}

【使用】

int main()
{
	SeqList sl = SeqListInit();
	SLDataType a[] = { 0,1,2,3,4,5,6,7,8,9 };
	// 尾插
	SeqListPushBack(&sl, &a[1]);
	SeqListPushBack(&sl, &a[2]);
	// 打印
	SeqListPrint(&sl);				// 1 2 
}

4.7 顺序表头插法

【算法步骤】

1. 检查是否需要增容
2. 所有元素整体后移
3. 在头插入数据
4. 有效数据个数加1

【算法描述】

// 顺序表的头插
void SeqListPushFront(SeqList* ps, SLDataType* data)
{
	// 顺序表的头插
void SeqListPushFront(SeqList* ps, SLDataType* data)
{
	assert(ps);
	// 1.检查增容
	SeqListCheckCapacity(ps);
	// 2.整体元素后移一个位置
	for (int i = ps->size - 1; i >= 0; i--)
	{
		// 后移
		ps->datas[i + 1] = ps->datas[i];
	}
	// 3.插入数据
	ps->datas[0] = *data;
	// 4.有效数据个数加1
	(ps->size) ++;
}}

4.8 顺序表头删法

【算法步骤】

1. 判断是否为空表，如果是函数执行结束
2. 整体元素前移一个单位
3. 有效数据个数加1

【算法描述】

// 顺序表的头删
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	if (ps->size == 0)
	{
		printf("顺序表元素为空,删除失败!");
		return;
	}
	// 1.整体元素前移一个位置 要移动的元素-->[1,size]
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->datas[i] = ps->datas[i + 1];
	}
	// 有效数据个数减1
	(ps->size)--;
}

4.9 顺序表的插入

【算法步骤】

1. 判断插入位置pos是否合法（pos值的合法范围时0≤pos＜size），若不合法则程序中断。
2. 判断顺序表是否需要增容。
3. 将第pos个至第size-1个元素依次向后移动一个位置，空出第pos个位置。
4. 将要插入的新元素data放入第pos处。
5. 顺序表有效数据个数加1。

【算法描述】

// 任意位置插入
void SeqListInsert(SeqList* ps, int pos, SLDataType* data)
{
	assert(ps);
	size_t size = ps->size;
	// pos需要在[0,size]范围中
	assert( (pos <= size) && (pos >= 0) );

	// 检查增容
	SeqListCheckCapacity(ps);

	// [pos,size-1]处的元素后移一个位置
	for (int i = size - 1; i >= pos; i--)
	{
		ps->datas[i + 1] = ps->datas[i];
	}
	// 插入元素
	ps->datas[pos] = *data;
	// 有效数据个数加1
	(ps->size) ++;
}

4.10 顺序表的删除

【算法步骤】

1. 判断插入位置pos是否合法（pos值的合法范围时0≤pos≤size），若不合法则程序中断。
2. 将第pos个至第size-1个元素依次向前移动一个位置。
3. 顺序表有效数据个数减1

【算法描述】

// 任意位置删除
void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	size_t size = ps->size;
	assert((pos <= size) && (pos >= 0));

	// 检查增容
	SeqListCheckCapacity(ps);
	// [pos+1,size-1] 的元素整体前移一个位置
	for (int i = pos; i < size -1; i++)
	{
		ps->datas[i] = ps->datas[i + 1];
	}
	(ps->size) --;
}

4.11 顺序表的销毁

【算法步骤】

1. 将数据序列释放掉
2. 将数据序列置为NULL
3. 将数据有效个数和最大容量置为0

【算法描述】

void SeqListDestory(SeqList* ps)
{
	assert(ps);
	// 释放资源
	free(ps->datas);
	ps->datas = NULL;
	ps->size = ps->capacity = 0;
}

4.12 思考

大家思考一下，为什么我在对顺序进行增容、插入等这些 *** 作时，传递的数据采用传址的方式，而不是传值的方式呢？欢迎各位在评论区留言。

5. 源码链接

点击跳转

【文件说明】

文件名说明SeqList.h类型定义和函数声明SeqList.c具体函数的实现test.c测试代码 后记

我水平有限，错误难免，还望各位加以指正。

---

关于顺序表的内容到此结束，感谢您的阅读！！！如果内容对你有帮助的话，记得给我三连丫（点赞、收藏、关注）

---

【参考资料】

  [1] 严蔚敏，李冬梅，吴伟民. 数据结构（C语言版）北京：人民邮电出版社，2015.2
  [2] 数据结构】 顺序表的简单理解和基本 *** 作

---

本人博客所有文章，均为原创。部分文章中或引用相关资料，但均已著明来源出处。可随意转载、分享，但需加本文链接，以及版权说明。