1. Toy模板网首页
  2. > Toy博客

【数据结构与算法】：带你手搓顺序表（C/C++篇）

7月前 作者：爱喝兽奶的荒天帝 分类：Toy博客 阅读(33) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构与算法】：带你手搓顺序表（C/C++篇）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、顺序表

1.1 线性表

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

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
【数据结构与算法】：带你手搓顺序表（C/C++篇）,数据结构与算法,c语言,c++,数据结构,算法

二、顺序表

【数据结构与算法】：带你手搓顺序表（C/C++篇）,数据结构与算法,c语言,c++,数据结构,算法

2.1 概念及结构

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

  1. 静态顺序表：使用定长数组存储。
typedef int SLDataType;//便于类型的改动
#define N 100
// 静态顺序表
typedef struct SeqList
{
	SLDataType arr[N];  // 定长数组
	int size; //  有效数据个数
}SL;

静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费

  1. 动态顺序表：使用动态开辟的数组存储。
typedef int SLDataType;//便于类型的改动
// 动态顺序表
typedef struct SeqList
{
	SLDataType* arr;
	int size;  // 有效数据的个数
	int capacity;  // 空间大小
}SL;
2.2 实现方法

首先要创建三个文件，创建一个SeqList.h的头文件用于函数的声明， SeqList.c用于函数的实现，test.c用于代码测试

SeqList.h文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
// 定义顺序表的结构
typedef int SLDataType;  //便于类型的改动
//#define N 100
 静态顺序表
//typedef struct SeqList
//{
//	SLDataType arr[N];  // 定长数组
//	int size; //  有效数据个数
//}SL;
// 动态顺序表
typedef struct SeqList
{
	SLDataType* arr;
	int size;  // 有效数据的个数
	int capacity;  // 空间大小
}SL;
// 顺序表的初始化
void SLInit(SL* ps);
// 顺序表的销毁
void SeqListDestory(SL* ps);
// 顺序表的打印
void SLPrint(SL s);
// 扩容
void SLCheckCapacity(SL* ps);
// 顺序表的增删查改等接口函数
// 尾插法
void SeqListPopBack(SL* ps, SLDataType x);
// 头插法
void SLPushFront(SL* ps, SLDataType x);
// 尾部删除
void SLPopBack(SL* ps);
// 头部删除
void SLPopFront(SL* ps);
// 指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x);
// 指定位置删除
void SLErase(SL* ps, int pos);
// 顺序表的查找
int SLFind(SL* ps, SLDataType x);
// 顺序表元素的索引
int SLIndex(SL* ps, int index);
// 顺序表元素的修改
void SLMod(SL* ps, int index, SLDataType x);

SeqList.c文件

1. 顺序表的初始化
// 顺序表的初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;  // 开始空间为0
 }

初始化的时候，可以选择申请原始空间大小，也可以选择不申请空间。

2. 顺序表的销毁
// 顺序表的销毁
void SeqListDestory(SL* ps)
{
	if (ps->arr) // arr不为空，释放空间
	{
		free(ps->arr);
	}
	ps->arr = NULL;  // 置为空指针
	ps->size = ps->capacity = 0;
}

代码测试：
test.c文件

#include"SeqList.h"
void SLTest01()
 {
	SL sl;
	// 初始化
	SLInit(&sl);
	// 销毁
	SeqListDestory(&sl);
}
int main()
{
	SLTest01();
	return 0;
}

【数据结构与算法】：带你手搓顺序表（C/C++篇）,数据结构与算法,c语言,c++,数据结构,算法

3. 扩容

注意：每次扩容新空间不能太大，也不能太小，太大容易造成空间浪费，太小则会导致频繁扩容而影响程序效率。

这里采用的是成倍扩容：

// 扩容
void SLCheckCapacity(SL* ps)
{
	if (ps->capacity == ps->size)
	{
		// 申请空间
		// 三目运算来判断原始空间是否为0
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;   // 如果为0，默认申请4个空间大小
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)  // 申请失败
		{
			perror("realloc");
			return 1;
		}
		// 申请成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

【数据结构与算法】：带你手搓顺序表（C/C++篇）,数据结构与算法,c语言,c++,数据结构,算法

4. 尾部插入/尾部删除
// 尾插法
void SeqListPopBack(SL* ps, SLDataType x)
{
	assert(ps);  // 判断传入的是否是空指针 
	// 插入数据前先查看空间够不够
	SLCheckCapacity(ps);
	// ps->arr[ps->size] = x;
	// ++ps->size;  // 插入数据之后size要加1
	ps->arr[ps->size++] = x;
}

// 尾部删除
void SLPopBack(SL* ps)
{
	assert(ps);  // 判断传入的是否是空指针
	assert(ps->size); // 确保数据域不为空
	--ps->size;  // 删除最后一个元素
}

【数据结构与算法】：带你手搓顺序表（C/C++篇）,数据结构与算法,c语言,c++,数据结构,算法

5. 头部插入/头部删除
// 头插法
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);  // 判断传入的是否是空指针
	// 先判断空间是否足够
	SLCheckCapacity(ps);
	// 先让顺序表中的元素整体往后挪动一位
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1]; // arr[1] = arr[0];
	}
	ps->arr[0] = x; // 将元素插在下标为0的位置
	ps->size++; // 插入数据后数据要加一
}

// 头部删除
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);  // 确保数据域不为空
	// 顺序表中所有的元素往前挪一位
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	--ps->size;  // 删除后大小减一
}

【数据结构与算法】：带你手搓顺序表（C/C++篇）,数据结构与算法,c语言,c++,数据结构,算法

6. 指定位置插入/删除

1. 元素指定位置插入
顺序表的元素插入，就是指给定一个索引和一个元素，将这个元素插入到对应的索引位置上，这个位置以后的所有元素都要往后移动一个位置。
【数据结构与算法】：带你手搓顺序表（C/C++篇）,数据结构与算法,c语言,c++,数据结构,算法
2. 元素指定位置删除
顺序表的元素删除，就是指给定一个索引，将这个索引上的元素删除，并且把这个索引位置以后的所有元素都往前移动一个位置。
【数据结构与算法】：带你手搓顺序表（C/C++篇）,数据结构与算法,c语言,c++,数据结构,算法

// 指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);  // 判断传入的是否是空指针
	assert(pos >= 0 && pos <= ps->size);
	// 先判断空间是否足够，不够就扩容
	SLCheckCapacity(ps);
	// 让pos及其之后的元素往后挪
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	// 插入数据
	ps->arr[pos] = x;
	// 插入元素后，数据域大小要加一
	ps->size++;
}

// 指定位置删除
void SLErase(SL* ps, int pos)
{
	assert(ps);  // 判断传入的是否是空指针
	assert(pos >= 0 && pos < ps->size);
	// pos之后的元素往前挪
	for (int i = pos;i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	// 删除元素后，数据域大小要减一
	ps->size--;
}
7. 顺序表的查找

顺序表的元素查找，是指在顺序表中查找指定元素是否存在，如果存在则返回该元素的索引，否则返回-1。由于需要遍历整个顺序表进行元素对比，所以查找的时间复杂度为 O(n) 。
【数据结构与算法】：带你手搓顺序表（C/C++篇）,数据结构与算法,c语言,c++,数据结构,算法
元素查找的顺序：
第1步、遍历整个顺序表，对顺序表中的每个元素，和指定元素进行比较，如果相等则返回当前的索引；
第2步、如果遍历完所有的顺序表元素，都没有找到相等的元素，则返回 -1；

// 顺序表的查找
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);  // 判断传入的是否是空指针
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)  // 找到了
			return i;
	}
	// 未找到
	return -1;
}
8. 顺序表元素的索引

顺序表的元素索引，是指给定一个索引值，通过下标访问，直接在顺序表中获取元素的值，时间复杂度 O(1)。
【数据结构与算法】：带你手搓顺序表（C/C++篇）,数据结构与算法,c语言,c++,数据结构,算法

// 顺序表元素的索引
int SLIndex(SL* ps, int index)
{
	assert(index >= 0 && index < ps->size);
	return ps->arr[index];
}
9. 顺序表元素的修改

顺序表的元素修改是指将顺序表中指定位置的元素更新为新的值。
【数据结构与算法】：带你手搓顺序表（C/C++篇）,数据结构与算法,c语言,c++,数据结构,算法文章来源地址https://www.toymoban.com/news/detail-861105.html

// 顺序表元素的修改
void SLMod(SL* ps, int index, SLDataType x)
{
	assert(ps); // 判断传入的是否是空指针
	assert(index >= 0 && index < ps->size);
	ps->arr[index] = x;  // 指定下标元素修改
}
10. SeqList.c完整代码
#include"SeqList.h"

// 顺序表的初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;  // 开始空间为0
 }

// 顺序表的销毁
void SeqListDestory(SL* ps)
{
	if (ps->arr) 
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

// 打印
void SLPrint(SL s)
{
	for (int i = 0; i < s.size; i++)
	{
		printf("%d ", s.arr[i]);
	}
	printf("\n");
}

// 扩容
void SLCheckCapacity(SL* ps)
{
	if (ps->capacity == ps->size)
	{
		// 申请空间
		// 三目运算来判断原始空间是否为0
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;   // 如果为0，默认申请4个空间大小
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)  // 申请失败
		{
			perror("realloc");
			return 1;
		}
		// 申请成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}
// 尾插法
void SeqListPopBack(SL* ps, SLDataType x)
{
	assert(ps);  // 判断传入的是否是空指针 
	// 插入数据前先查看空间够不够
	SLCheckCapacity(ps);
	// ps->arr[ps->size] = x;
	// ++ps->size;  // 插入数据之后size要加1
	ps->arr[ps->size++] = x;
}

// 头插法
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);  // 判断传入的是否是空指针
	// 先判断空间是否足够
	SLCheckCapacity(ps);
	// 先让顺序表中的元素整体往后挪动一位
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1]; // arr[1] = arr[0];
	}
	ps->arr[0] = x; // 将元素插在下标为0的位置
	ps->size++; // 插入数据后数据要加一
}


// 尾部删除
void SLPopBack(SL* ps)
{
	assert(ps);  // 判断传入的是否是空指针
	assert(ps->size); // 确保数据域不为空
	--ps->size;  // 删除最后一个元素
}

// 头部删除
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);  // 确保数据域不为空
	// 顺序表中所有的元素往前挪一位
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	--ps->size;  // 删除后大小减一
}

// 指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);  // 判断传入的是否是空指针
	assert(pos >= 0 && pos <= ps->size);
	// 先判断空间是否足够，不够就扩容
	SLCheckCapacity(ps);
	// 让pos及其之后的元素往后挪
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	// 插入数据
	ps->arr[pos] = x;
	// 插入元素后，数据域大小要加一
	ps->size++;
}

// 指定位置删除
void SLErase(SL* ps, int pos)
{
	assert(ps);  // 判断传入的是否是空指针
	assert(pos >= 0 && pos < ps->size);
	// pos之后的元素往前挪
	for (int i = pos;i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	// 删除元素后，数据域大小要减一
	ps->size--;
}

// 顺序表的查找
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);  // 判断传入的是否是空指针
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)  // 找到了
			return i;
	}
	// 未找到
	return -1;
}

// 顺序表元素的索引
int SLIndex(SL* ps, int index)
{
	assert(index >= 0 && index < ps->size);
	return ps->arr[index];
}

// 顺序表元素的修改
void SLMod(SL* ps, int index, SLDataType x)
{
	assert(ps); // 判断传入的是否是空指针
	assert(index >= 0 && index < ps->size);
	ps->arr[index] = x;  // 指定下标元素修改
}

到了这里，关于【数据结构与算法】：带你手搓顺序表（C/C++篇）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法——顺序表（顺序存储结构）及初始化详解

    数据结构与算法——顺序表（顺序存储结构）及初始化详解

    顺序表 ，全名 顺序存储结构 ，是线性表的一种。通过《什么是线性表》一节的学习我们知道，线性表用于存储逻辑关系为“一对一”的数据，顺序表自然也不例外。 不仅如此，顺序表对数据的物理存储结构也有要求。 顺序表存储数据时，会提前申请一整块足够大小的物理

    2024年02月16日
    浏览(41)
  • 数据结构与算法—顺序表

    数据结构与算法—顺序表

    目录 一、线性表 二、顺序表概念  三、实现顺序表 1、声明结构体 2、初始化 3、打印数据  4、销毁  5、尾插头插 尾插 判断是否扩容   头插 6、尾删头删 尾删 头删 7、 指定位置插入元素 8、 删除指定位置元素 9、 查找指定元素位置 10、修改指定位置元素 完整版附上： S

    2024年02月08日
    浏览(37)

  • 数据结构：两个顺序表合并算法

            将a，b两个有序顺序表进行合并，放在c顺序表当中，并且要保证顺序表c仍然有序。         因为a，b两个顺序表是有序的，所有可以从前往后一起查找a，b当中最小的一个数值，放入到c中。         如果遍历到最后，a遍历完了，b没有遍历完，就把b剩下的放入

    2024年02月08日
    浏览(38)
  • 【数据结构与算法】3.顺序表

    【数据结构与算法】3.顺序表

    📚博客主页：爱敲代码的小杨. ✨专栏：《Java SE语法》 ❤️感谢大家点赞👍🏻收藏⭐评论✍🏻，您的三连就是我持续更新的动力❤️ 🙏小杨水平有限，欢迎各位大佬指点，相互学习进步！ 定义：线性表是 n 个具有相同特性的数据元素的有序序列。线性表是一种在实际中

    2024年01月23日
    浏览(44)
  • 顺序表（更新版）——“数据结构与算法”

    顺序表（更新版）——“数据结构与算法”

    各位CSDN的uu们你们好呀，今天小雅兰又来更新新专栏啦，其实之前我就已经写过了顺序表的内容，只是之前的内容不是最新版的顺序表，现在，我来更新一下最新版的顺序表，下面，就让我们进入更新版的顺序表的世界吧 顺序表和小雅兰之前写的三子棋、扫雷、通讯录一样，

    2023年04月23日
    浏览(32)

  • 数据结构算法--1 顺序查找二分查找

    顺序查找时间复杂度为O(n) 我们可以借助Python中的函数enumerate,通过enumerate遍历列表返回其索引和值 也可以通过列表长度依次遍历: 但是二分查找时间复杂度为O(logn):

    2024年02月12日
    浏览(54)
  • 【数据结构与算法】一文带你学透——算法

    【数据结构与算法】一文带你学透——算法

       本期我们所要学习的内容是数据结构与算法中的算法的相关内容，通过上期我们学的数据结构想必大家都会了吧，在学习完毕之后算法，我想你已经可以编写出比较优秀的代码了， 著名计算机科学家沃思曾提出一个公式 程序=数据结构+算法。双剑合璧，天下无敌！   前言

    2024年02月07日
    浏览(40)
  • 【数据结构与算法】之顺序表及其实现！

    【数据结构与算法】之顺序表及其实现！

    目录 ​编辑 1. 顺序表的概念及结构 2. 接口的实现 2.1 顺序表的初始化 2.2 检查顺序表容量是否已满 2.3 顺序表的尾插 ​编辑 2.4 顺序表的尾删 2.5 顺序表的头插 2.6  顺序表的头删 2.7 顺序表在pos位置插入 2.8  顺序表在pos位置删除 2.9 顺序表的查找 2.10 顺序表的销毁 2.1

    2024年04月28日
    浏览(35)

  • 数据结构与算法 --顺序表的创建

    1. 顺序表（Sequence List）是一种线性表的实现方式，通过连续的内存空间存储元素，按照顺序排列。 顺序表的特点包括： 元素在内存中的存储是连续的，通过数组实现。 元素之间的逻辑顺序与物理顺序一致。 可以根据元素的索引直接访问和修改元素。 需要预先分配足够的内

    2024年03月26日
    浏览(50)
  • 【数据结构】：实现顺序表各种基本运算的算法

    【数据结构】：实现顺序表各种基本运算的算法

    领会顺序表存储结构和掌握顺序表中各种基本运算算法设计。 编写一个程序sqlist.cpp，实现顺序表的各种基本运算和整体建表算法（假设顺序表的元素类型ElemType为char），并在此基础上设计一个主程序，完成如下功能： 初始化顺序表L 依次插入a,b,c,d,e元素 输出顺序表L 输出顺

    2024年02月07日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包