数据结构-顺序表的基本实现(C语言,简单易懂,含全部代码)

这篇具有很好参考价值的文章主要介绍了数据结构-顺序表的基本实现(C语言,简单易懂,含全部代码)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

                          你们的每个赞和支持都能让我开心好几天!😉

今天起开始编写数据结构中的各种数据结构及算法的实现,说到顺序表,我们首先得了解下线性表。

1.线性表

线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组链式结构的形式存储。
数据结构-顺序表的基本实现(C语言,简单易懂,含全部代码)

2.顺序表

2.1概念及结构

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

1.静态顺序表:使用定长数组存储。
2.动态顺序表:使用动态开辟的数组存储。

//顺序表的静态存储 
#define N 100
struct SeqList
{
	int a[N];//定长存储
	int size;//有效数据的个数
};
//顺序表的动态存储
typedef struct SeqList
{
	SeqDataType* a;//指向动态开辟的数组
	int size;	  //有效数据个数
	int capacity; //容量
}SeqList;

顺序表本质上是数组,在数组上增加了两个要求:

1.插入数据的过程中,可以动态增长
2.并且要求里面存储的数据必须是从左往右,是连续的

顺序表的缺陷

1.动态增容有性能消耗
2.头部插入数据时,需要挪动数据

2.2 提供接口

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用。所以现实中基本都是使用动态顺序表,根据需要动态的分配空间大小,所以下面我们来实现动态顺序表。

首先在头文件<SeqList.h>中提供接口:

typedef int SeqDataType; //需要插入什么类型的数据,就改成对应类型

typedef struct SeqList
{
	SeqDataType* a;//指向动态开辟的数组
	int size;	  //有效数据个数
	int capacity; //容量
}SeqList;

//内存中管理数据结构 提供增删查改的接口
//顺序表初始化
void SeqListInit(SeqList* pq);
//顺序表销毁
void SeqListDestory(SeqList* pq);
//顺序表打印
void SeqListPrint(SeqList* pq);//打印数组
//检查空间,如果满了,进行增容
void SeqCheckCapacity(SeqList* pq)
//顺序表尾插
void SeqListPushBack(SeqList* pq, SeqDataType x);
//顺序表头插
void SeqListPushFront(SeqList* pq, SeqDataType x);
//顺序表尾删
void SeqListPopBack(SeqList* pq);
//顺序表头删
void SeqListPopFront(SeqList* pq);
//顺序表查找x
int SeqListFind(SeqList* pq, SeqDataType x);//查找 查到返回下标,没查到返回-1
//顺序表在指定位置插入数据
void SeqListInsert(SeqList* pq, int pos, SeqDataType x);//在下标pos位置处插入数据
//顺序表在指定位置删除数据
void SeqListErase(SeqList* pq, int pos);//把下标为pos位置处的数据删除
//顺序表在指定位置替换数据
void SeqListModify(SeqList* pq, int pos, SeqDataType x);//把小标为pos位置的值改为x

2.4 接口实现

在源文件SeqList.c中实现接口功能
(1)顺序表初始化

void SeqListInit(SeqList* pq)
{
	assert(pq != NULL);//或者 assert(pq); 断言 防止传入空指针
	pq->a = NULL;
	pq->size = 0;
	pq->capacity = 0;
}

(2)顺序表销毁

void SeqListDestory(SeqList* pq)
{
	assert(pq);
	free(pq->a);
	pq->a = NULL;
	pq->size = 0;
	pq->capacity = 0;
}

(3)顺序表打印

void SeqListPrint(SeqList* pq)
{
	assert(pq);
	for (int i = 0; i < pq->size; ++i)
	{
		printf("%d ", pq->a[i]);
	}
	printf("\n");
}

(4)检查空间,如果满了,进行增容

//检查是否需要扩容
void SeqCheckCapacity(SeqList* pq)
{
	//满了,需要增容
	if (pq->size == pq->capacity)
	{
		int newcapacity = (pq->capacity == 0 ? 4 : pq->capacity * 2);

		//realloc接收的地址如果为空,将像malloc一样,开辟一块新空间
		SeqDataType* newA = realloc(pq->a, sizeof(SeqDataType) * newcapacity);//realloc返回 开辟的新空间的地址
		if (newA == NULL)
		{
			printf("realloc fail\n");
			exit(-1);//失败了就退出
		}
		pq->a = newA;
		pq->capacity = newcapacity;
	}
}

(5)顺序表尾插

void SeqListPushBack(SeqList* pq, SeqDataType x)//尾插
{
	assert(pq);

	SeqCheckCapacity(pq);

	pq->a[pq->size] = x;
	pq->size++;
}

(6)顺序表头插

void SeqListPushFront(SeqList* pq, SeqDataType x)
{
	assert(pq);

	SeqCheckCapacity(pq);

	int end = pq->size - 1;
	while (end >= 0)
	{
		pq->a[end + 1] = pq->a[end];
		end--;
	}
	pq->a[0] = x;
	pq->size++;
}

(7)顺序表尾删

void SeqListPopBack(SeqList* pq)
{
	assert(pq);
	assert(pq->size > 0);
	pq->size--;
}

(8)顺序表头删

void SeqListPopFront(SeqList* pq)
{
	assert(pq);
	assert(pq->size > 0);

	int begin = 0;
	while (begin < pq->size - 1)
	{
		pq->a[begin] = pq->a[begin + 1];
		begin++;
	}
	pq->size--;
}

(9)顺序表查找x

int SeqListFind(SeqList* pq, SeqDataType x)
{
	assert(pq);
	for (int i = 0; i < pq->size; ++i)
	{
		if (pq->a[i] == x)
		{
			return x;
		}
	}
	return -1;//没找到
}

(10)顺序表在指定位置插入数据

void SeqListInsert(SeqList* pq, int pos, SeqDataType x)
{
	assert(pq);
	assert(pos >= 0 && pos < pq->size);

	SeqCheckCapacity(pq);//检查是否需要扩容

	int end = pq->size - 1;
	while (end >= pos)
	{
		pq->a[end + 1] = pq->a[end];
		end--;
	}
	pq->a[pos] = x;
	pq->size++;
}

(11)顺序表在指定位置删除数据

void SeqListErase(SeqList* pq, int pos)
{
	assert(pq);
	assert(pos >= 0 && pos < pq->size);
	int begin = pos;
	while (begin <= pq->size - 1)
	{
		pq->a[begin] = pq->a[begin + 1];
		begin++;
	}
	pq->size--;
}

(12)顺序表在指定位置替换数据

void SeqListModify(SeqList* pq, int pos, SeqDataType x)
{
	assert(pq);
	assert(pos >= 0 && pos < pq->size);

	pq->a[pos] = x;
}

主函数的设计大家可以自由发挥,做个简单的测试功能调用函数或是创建菜单栏实现交互都可以。我水平有限,请朋友们谅解!写的不好的地方还请大佬们指出。最后,如果这篇文章对你有帮助,就点个赞或者收藏评论一下吧,谢谢大家支持😁。

下期预告——单链表文章来源地址https://www.toymoban.com/news/detail-402452.html

到了这里,关于数据结构-顺序表的基本实现(C语言,简单易懂,含全部代码)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】线性表的顺序存储结构及实现——C语言版

    线性表的顺序存储结构称为 顺序表 ,其基本思想是 用一段地址连续的存储单元一次存储线性表的数据元素。 设顺序表的每个元素占用 c 个存储单元,则第 i 个元素的存储地址为: 所以, 只要确定了存储顺序表的起始地址(即基地址),计算任意一个元素的存储地址的时间

    2024年03月15日
    浏览(53)
  • 数据结构-线性表的顺序表基本操作代码实现(超级详细清晰 C++实现)

    顺序表是用一段 物理地址连续的存储单元 依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。 顺序表: 可动态增长的数组,要求数据是连续存储的 特点: 随机访问 顺序既可以 静态分配 ,也可以 动态分配 。在静态分配时,由于数组

    2024年02月07日
    浏览(56)
  • C语言数据结构-----顺序表(多功能动态顺序表的代码实现)

    本篇讲述了顺序表的相关知识,以及动态顺序表的代码实现。 顺序表和链表一般情况下都会叫他们线性表。 线性表(linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使 用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性

    2024年02月07日
    浏览(48)
  • [C语言][数据结构][动态内存空间的开辟]顺序表的实现!

    目录 零.必备知识 a.顺序表的底层是数组. b.数组在内存中是连续存放的. c.动态内存空间的开辟(malloc,calloc,realloc). 一.顺序表的定义与实现          1.1 顺序表的定义          1.2 顺序表的初始化          1.3 顺序表的销毁          1.4 顺序表容量的检查与调整

    2024年04月09日
    浏览(88)
  • 【数据结构】C语言实现双链表的基本操作

    大家好,很高兴又和大家见面啦!!! 经过前面几个篇章的内容分享,相信大家对顺序表和单链表的基本操作都已经熟练掌握了。今天咱们将继续分享线性表的链式存储的第二种形式——双链表。在今天的内容中,咱们将介绍双链表的创建以及一些基本操作,接下来跟我一起

    2024年02月04日
    浏览(62)
  • c语言数据结构——链表的实现及其基本操作

    顺序表的问题及思考 问题: 中间/头部的插入删除,时间复杂度为O(N) 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到 200,我们再继续插入了5个数据,后面没有数据插

    2023年04月09日
    浏览(85)
  • 【数据结构】C语言实现单链表的基本操作

    大家好,很高兴又和大家见面啦!!! 在上一篇中,我们详细介绍了单链表的两种创建方式——头插法与尾插法,相信大家现在对这两种方式都已经掌握了。今天咱们将继续介绍单链表的基本操作——查找、插入与删除。在开始今天的内容之前,我们先通过尾插法创建一个单

    2024年02月03日
    浏览(65)
  • 【数据结构】顺序表基本操作的实现(C语言)

    🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🐌 个人主页:蜗牛牛啊 🔥 系列专栏:🛹数据结构、🛴C++ 📕 学习格言:博观而约取,厚积而薄发 🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与

    2024年02月16日
    浏览(55)
  • 数据结构中: 一元多项式的运算(相加,相减,相乘)------用C语言 / C++来实现。 数据结构线性表的操作和应用(顺序存储)

    线性表的操作和应用(顺序存储)。用顺序存储实现一元多项式,并进行加、减、乘运算。 (1)一元多项式结构体创建  (2)初始化 (3)一元多项式赋值             (4)打印一元多项式 (5)加法运算                        (6)减法运算 (7)乘法运算    全部代

    2024年02月01日
    浏览(63)
  • 数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

    实验的写法多种多样,但本文并未采用 #define 定义容量的写法,这样写已经是很老旧过时的写法。所有实验主体采用均为动态开辟,后续如果利用 C++ 来写或许会应用更多语法… 本篇展示数据结构的两个实验 其中,重点分析约瑟夫问题 实验中代码的命名风格等均与下方博客

    2024年02月16日
    浏览(62)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包