初阶数据结构:顺序表

这篇具有很好参考价值的文章主要介绍了初阶数据结构:顺序表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 引子:线性表

了解到学习数据结构与算法的重要性后,又学习了评判程序效率高低算法好坏的标准,时间空间复杂度。接下来,进行一些简单数据结构的初步学习。所有数据结构中存在着可以划分为一大类的简单结构,线性表,即在逻辑上都呈现线性关系的数据结构(物理结构上不一定是线性),诸如,顺序表,链表,栈,队列等。今天,进行其中顺序表的学习。

2. 简单数据结构:顺序表

2.1 顺序表简介与功能模块分析

简介:

顺序表为在物理地址上连续的一种简单线性结构,其存储的数据元素一个连着一个。一般使用数组来进行其的实现,根据其存储空间是否可以动态增长又进一步分为,静态(定长数组)与动态(使用动态内存管理函数实现malloc)的顺序表。

功能模块分析:

数据存储方式:

  1. 定长数组/malloc动态开辟空间
  2. 存储数据信息的记录变量,帮助数据的管理
    以上两部分构成的结构体。

数组管理方式:

  1. 增(头插,尾插,随机插入):push_front,push_back,insert
  2. 删(头删,尾删,随机删除):pop_front,pop_back,erase
  3. 改(指定数据的修改):modify
  4. 查(指定数据的查询):find

2.2 顺序表的实现

2.2.1 顺序表:存储数据结构的构建

静态顺序表:

//替换更改表中元素类型
typedef int STDatatype;
//定义能够存储的数据个数
#define N 100

//静态
typedef struct SeqList
{
	STDatatype data[N];
	int capacity;
	int size;
}SeqList;

动态顺序表:

typedef struct SeqList
{
	STDatatype* data;
	int capacity;
	int size;
}SeqList;

2.2.2 顺序表:初始化与空间清理(动态)

初始化:

void SLInit(SeqList* s)
{
	//不为NULL
	assert(s);
	//初始空间开辟4个数据大小
	s->data = (STDatatype*)malloc(4 * sizeof(STDatatype));
	if (s->data == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	s->capacity = 4;
	s->size = 0;
}

空间清理:

void SLDestroy(SeqList* s)
{
	assert(s);

	free(s->data);
	s->capacity = 0;
	s->size = 0;
}

2.2.3 顺序表:插入与删除数据

扩容函数:

void CheckCapacity(SeqList* s)
{
	assert(s);

	if (s->capacity == s->size)
	{
		//使用临时变量去接收新地址(可能会扩容失败返回NULL),增加程序的健壮性
		STDatatype* tmp = (STDatatype*)realloc(s->data, s->capacity * 2 * sizeof(STDatatype));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		s->data = tmp;
		s->capacity *= 2;
	}
}

尾插,尾删

尾插过程演示:

初阶数据结构:顺序表,数据结构

尾删过程演示:

初阶数据结构:顺序表,数据结构

//尾插
void SLPush_Back(SeqList* s, STDatatype val)
{
	assert(s);

	CheckCapacity(s);

	s->data[s->size] = val;
	s->size++;
}

//尾删
void SLPop_Back(SeqList* s)
{
	assert(s);
	assert(s->size > 0);

	s->size--;
}

头插,头删

头插过程演示:

初阶数据结构:顺序表,数据结构

头删过程演示:

初阶数据结构:顺序表,数据结构

//头插
void SLPush_Front(SeqList* s, STDatatype val)
{
	assert(s);

	CheckCapacity(s);

	int i = s->size;
	while (i > 0)
	{
		s->data[i] = s->data[i - 1];
		i--;
	}

	s->data[i] = val;
	s->size++;
}

//头删
void SLPop_Front(SeqList* s)
{
	assert(s);
	//暴力检查
	assert(s->size > 0);
	//警告
	/*if (s->size == 0)
	{
		printf("表内已无元素,删除失败\n");
		return;
	}*/

	int i = 0;
	while (i < s->size - 1)
	{
		s->data[i] = s->data[i + 1];
		i++;
	}

	s->size--;
}

随机插入与随机删除

随机插入:

随机插入演示过程:

初阶数据结构:顺序表,数据结构

注:当随机插入的下标pos为0 或者 size - 1就相当于头插与尾插,可以直接复用到头插,尾插部分。头删,尾删相同

//在pos位置插入元素
//pos为下标
void SLInsert(SeqList* s, int pos, STDatatype val)
{
	assert(s);
	assert(pos >= 0);
	assert(pos < s->size);

	CheckCapacity(s);

	int i = s->size;
	while (i > pos)
	{
		s->data[i] = s->data[i - 1];
		i--;
	}

	s->data[pos] = val;
	s->size++;
}

随机删除:

随机删除演示过程:

初阶数据结构:顺序表,数据结构

void SLErase(SeqList* s, int pos)
{
	assert(s);
	assert(s->size > 0);
	assert(pos >= 0);
	assert(pos < s->size);

	int i = pos;
	while (i < s->size - 1)
	{
		s->data[i] = s->data[i + 1];
		i++;
	}

	s->size--;
}

2.2.4 查找数据与修改

<1> 查找数据(查找顺序表中是否有指定数据,并返回下标):

//找到返回下标,未找到返回-1
int SLFind(SeqList* s, STDatatype val)
{
	assert(s);

	int i = 0;
	for (i = 0; i < s->size; i++)
	{
		if (s->data[i] == val)
		{
			return i;
		}
	}

	return -1;
}

<2> 修改指定下标的数据(不要直接访问数据,函数可以帮助检查数据合法)文章来源地址https://www.toymoban.com/news/detail-807669.html

//高内聚,低耦合f
void SLModify(SeqList* s, int pos, STDatatype val)
{
	assert(s);
	assert(pos > 0);
	assert(pos < s->size);

	s->data[pos] = val;
}

到了这里,关于初阶数据结构:顺序表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据结构(初阶):顺序表实战通讯录

    数据结构(初阶)第一节:数据结构概论-CSDN博客 数据结构(初阶)第二节:顺序表-CSDN博客         本文将以C语言和顺序表实现通讯录基础管理,实现功能包括增、删、改、查等,在实现相关功能时需要用到在第二节中顺序表的相关内容,需要友友们掌握顺序表的相关

    2024年04月16日
    浏览(36)
  • 初阶数据结构:顺序表相关题目练习

    在对顺序表这一数据结构进行了学习与自实现后,我明白了顺序表的是使用了 物理地址上连续的数组模型 实现的,而 插入删除 的操作都会涉及到其中 数据的挪动与边界问题 。接下来,就结合算法时空间复杂的要求来对这一相关问题通过几道题目进行巩固练习。 题目要求:

    2024年01月20日
    浏览(50)
  • 【数据结构初阶】顺序表和链表(1)

    线性表(linear list) 是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上

    2024年02月08日
    浏览(241)
  • 【数据结构初阶】二、 线性表里的顺序表

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】一. 复杂度讲解_高高的胖子的博客-CSDN博客  =======================================

    2024年02月09日
    浏览(36)
  • 【数据结构初阶】二、 线性表里的顺序表(C语言实现顺序表)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】一. 复杂度讲解_高高的胖子的博客-CSDN博客  =======================================

    2024年02月08日
    浏览(43)
  • 数据结构初阶之顺序表(C语言实现)

    顺序表是数据结构里面很基础的一类,它是线性表的一种,其它线性表还有链表、栈和队列等,今天来和博主一起学习关于顺序表的知识吧。 顺序表,它分为两类: 动态顺序表 和 静态顺序表 ,这两个表的区别就是 前者的空间不固定 ,是 支持扩容 的,后者的 空间是固定

    2024年02月03日
    浏览(45)
  • 初阶数据结构之---顺序表和链表(C语言)

    线性表: 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构。线性表在逻辑上是线性结构,也就是说是连续的一条直线。但在物理上并不一定是连续的。线性表在物理上存储时,通常以 数组 和 链式结构 的形式存储。

    2024年02月22日
    浏览(66)
  • 『初阶数据结构 • C语言』⑧ - 动态顺序表详解(附完整源码)

    本章内容 写在前面 1.静态与动态是指什么? 2.动态顺序表结构的定义 3.动态顺序表的函数接口实现 4.动态顺序表的问题及思考 5.关于顺序表的OJ题 6.OJ答案及解析 1.移除元素 2.删除有序数组中的重复项 ​3.合并两个有序数组 7.动态顺序表完整源码 1.SeqList.h 2.SeqList.c     上一章

    2024年02月16日
    浏览(44)
  • 『初阶数据结构 • C语言』⑦ - 静态顺序表详解(附完整源码)

    本章内容 1.什么是线性表 2.什么是顺序表  3.静态顺序表结构的定义 4.静态顺序表的函数接口实现 5.静态顺序表的问题及思考     线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、

    2024年02月15日
    浏览(44)
  • 【数据结构初阶】七、非线性表里的二叉树(堆的实现 -- C语言顺序结构)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】六、线性表中的队列(链式结构实现队列)-CSDN博客  ===========================

    2024年02月08日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包