[数据结构 - C语言] 顺序表

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

目录

1、线性表

2、顺序表

2.1 顺序表的概念

2.2 接口

3、接口实现

3.1 初始化

3.2 销毁

3.3 容量检测

3.4 打印数据

3.5 顺序表的头插

3.6 顺序表的尾插

3.7 顺序表的头删、尾删

3.8 顺序表查找

3.9 指定位置插入数据


1、线性表

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

[数据结构 - C语言] 顺序表

2、顺序表

2.1 顺序表的概念

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

        1.静态顺序表:使用定长数组存储元素。

#define N 10

struct SeqList
{
	int a[N];
	int size;
};

静态顺序表缺点:开的大了浪费空间,小了不够用。

优点:可以通过下标访问任意一个数组元素。

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

动态的顺序表比起静态的顺序表就很灵活了,空间不够用可以随时增容。

2.2 接口

typedef int SLDateType;

typedef struct SeqList
{
	SLDateType* a;
	int size;
	int capacity;
}SeqList;

// 对数据的管理:增删查改 
void SeqListInit(SeqList* ps);
void SeqListDestroy(SeqList* ps);

void SeqListPrint(SeqList* ps);
void SeqListPushBack(SeqList* ps, SLDateType x);
void SeqListPushFront(SeqList* ps, SLDateType x);
void SeqListPopFront(SeqList* ps);
void SeqListPopBack(SeqList* ps);

// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList * ps, int pos);

3、接口实现

3.1 初始化

void SeqListInit(SeqList* ps)
{
	ps->a = (SLDateType*)malloc(sizeof(SLDateType) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}

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

使用malloc在堆区开辟动态内存,开4个整形的空间。容量也就初始化为4。

3.2 销毁

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

在销毁的时候我们使用 free ,来将开辟的整个顺序表的内存释放掉,并将头指针置为空。

3.3 容量检测

void SeqCheckCapacity(SeqList* ps)
{
	if (ps->capacity == ps->size)
	{
		SLDateType* tmp = (SLDateType*)realloc(sizeof(SLDateType), 2 * ps->capacity);
		ps->a = tmp;
		if (ps->a == NULL)
		{
			perror("realloc fail:");
			return;
		}
		ps->capacity *= 2;
	}
}

如果 4 个整型空间被使用完了就得继续开辟空间,因此我们使用 realloc 再开辟空间,合理的是再开辟的空间大小为原来的二倍。

3.4 打印数据

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

对数组遍历,打印每个元素。

3.5 顺序表的头插

void SeqListPushFront(SeqList* ps, SLDateType x)
{
	assert(ps);
	SeqCheckCapacity(ps);
	int begin = 0;
	for (begin = ps->size; begin > 0; begin--)
	{
		ps->a[begin] = ps->a[begin - 1];
	}
	ps->a[0] = x;
	ps->size++;
}

插入前我们调用容量检测函数对容量进行检测,函数内部已经写好了增容的程序。

分析:

在头插的时候我们要将数组从后往前移动。

[数据结构 - C语言] 顺序表

3.6 顺序表的尾插

void SeqListPushBack(SeqList* ps, SLDateType x)
{
	assert(ps);
	SeqCheckCapacity(ps);

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

顺序表的尾插还是先要检测容量是否足够。

分析:

[数据结构 - C语言] 顺序表

3.7 顺序表的头删、尾删

//头删
void SeqListPopFront(SeqList* ps)
{
	assert(ps);

	int begin = 0;
	for (begin = 0; begin < ps->size - 1; begin++)
	{
		ps->a[begin] = ps->a[begin + 1];
	}
	ps->size--;
}
//尾删
void SeqListPopBack(SeqList* ps)
{
	assert(ps);

	ps->a[ps->size - 1] = 0;
	ps->size--;
}

分析:

头删

[数据结构 - C语言] 顺序表

尾删

将 size-1 位置上的数字置 0,让 size-- 就完成尾删操作。

3.8 顺序表查找

约定:找到返回下标,没找到返回 -1。

int SeqListFind(SeqList* ps, SLDateType x)
{
	int begin = 0;
	for (begin = 0; begin < ps->size - 1; begin++)
	{
		if (ps->a[begin] == x)
			return begin;
	}
	return -1;
}

遍历数组就可以完成操作。

3.9 指定位置插入数据

void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{
    assert(pos>=0 && pos <= ps->size);
    
	int end = 0;
	for (end = ps->size - 1; end >= pos; end--)
	{
		ps->a[end + 1] = ps->a[end];
	}
	ps->a[pos] = x;
	ps->size++;
}

注意:

1.pos 位置要合法,0<= pos <= size;

2.依旧是从后往前覆盖;

3.如果pos = size 就是尾插,pos = 0 就是头插。

[数据结构 - C语言] 顺序表

3.10 指定位置删除

void SeqListErase(SeqList* ps, int pos)
{
	assert(pos >= 0 && pos < ps->size);

	int begin = 0;
	for (begin = pos; begin < ps->size-1; begin++)
	{
		ps->a[begin] = ps->a[begin + 1];
	}

	ps->size--;
}

注意:

1.pos 位置要合法,0<= pos <= size-1;

2.从 pos 位置开始,到 size-1 位置结束,将 begin+1 的元素移到 begin 位置;

3.如果pos = size-1 就是尾删,pos = 0 就是头删。

[数据结构 - C语言] 顺序表

完整代码在代码仓库,入口--->C语言: C语言的初级阶段时期 - Gitee.com

********************************************本片结束**********************************************

大牛的你看到有什么问题请一定要指出来。如果看了有收获,点赞收藏+关注三连一波。文章来源地址https://www.toymoban.com/news/detail-419947.html

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

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

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

相关文章

  • 【数据结构初阶】七、非线性表里的二叉树(堆的实现 -- C语言顺序结构)

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

    2024年02月08日
    浏览(45)
  • 【数据结构】(顺序表)C语言实现线性表顺序存储的创建、插入、删除、查找、输出等基本操作(附完整代码)

    要求:利用书本上的线性表的顺序存储结构定义 #define MAXSIZE 100 //顺序表可能达到的最大长度 typedef struct{ ElemType *elem; // 存储空间基址 int length; // 当前长度 int listsize; // 当前分配的存储容量(以sizeof(ElemType)为单位) } SqList; 1)编写完成下列功能的函数: (1)初始化一个线性表

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

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

    2024年02月01日
    浏览(65)
  • 数据结构:线性表顺序存储结构———顺序表

    目录 顺序表的定义 初始化线性表 销毁线性表 求线性表的长度 判断是否为空表 插入数据元素 逻辑序号与物理序号的区别 删除数据元素 输出线性表  按序号求线性表中的元素 按元素值查找 整体上创建顺序表 顺序表实验 线性表的顺序存储是把线性表中的所有元素按照其逻辑

    2024年02月03日
    浏览(46)
  • 【数据结构】线性结构 之 顺序表

    🌱博客主页:大寄一场. 🌱系列专栏:数据结构与算法 😘博客制作不易欢迎各位👍点赞+⭐收藏+➕关注 目录 前言 顺序表概念及结构 静态代码实现: 动态代码实现: SeqList.h文件 SeqList.c文件 test.c文件 本章节博主将会带领大家了解数据结构的 线性结构的顺序表 。 提到线性

    2024年02月06日
    浏览(44)
  • 【玩转408数据结构】线性表——线性表的顺序表示(顺序表)

            通过前文,我们了解到线性表是具有相同数据类型的有限个数据元素序列;并且,线性表只是一种逻辑结构,其不同存储形式所展现出的也略有不同,那么今天我们来了解一下线性表的顺序存储——顺序表。         顺序表指的是将 逻辑上相邻的元素 存储在 物理位

    2024年02月19日
    浏览(52)
  • 数据结构 · 线性表 | 顺序表

    啊我摔倒了..有没有人扶我起来学习.... 👱 个人主页: 《 C G o d 的 个 人 主 页 》 color{Darkorange}{《CGod的个人主页》} 《 C G o d 的 个 人 主 页 》 交个朋友叭~ 💒 个人社区: 《 编 程 成 神 技 术 交 流 社 区 》 color{Darkorange}{《编程成神技术交流社区》} 《 编 程 成 神 技 术

    2024年02月02日
    浏览(50)
  • 数据结构-线性表-顺序表

    线性表的定义:由n(n=0)个数据特性相同的元素构成的有限序列,称为线性表。当n=0时称之为空表。 因为构件线性表时元素数组已经使用静态分配,所以在此只需要对线性表的长度执行初始化即可。 获取数据需要参数: sqList:需要给定一个线性表从而获取数据,因为只是拿值

    2024年02月08日
    浏览(48)
  • 数据结构——线性表①(顺序表)

    线性表是一种数据结构,它是由n个具有 相同数据类型 的数据元素a1,a2,…,an组成的 有限序列 。 其中,除第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后一个元素an外,每一个元素有且只有一个直接后继元素。 线性表可以用 顺序存储结构 或 链式存储结构

    2024年02月06日
    浏览(54)
  • 数据结构---顺序表示的线性表

             数据结构(data structure)是带有结构特性的数据元素的集合,它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系,并对这种结构定义相适应的运算,设计出相应的算法,并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简言之,数据

    2024年02月16日
    浏览(54)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包