你真的会数据结构吗:顺序表

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

❀❀❀ 文章由@不准备秃的大伟原创 ❀❀❀

♪♪♪ 若有转载,请联系博主哦~ ♪♪♪

❤❤❤ 致力学好编程的宝藏博主,代码兴国!❤❤❤

         又和大家见面啦!在大家看到这个标题的时候其实就已经发现了:我们的C语言的基础知识大部分已经学完了呢~真厉害,给自己鼓个掌吧,啪叽啪叽~ 现在开始我们要进击数据结构了!是不是很激动呢?诶,先憋激动,在开始前我们先了解一下数据结构是什么吧!

          我们在生活中无论什么事几乎都少不了逻辑吧,比如是先吃饭还是先睡觉,是先给大伟的文章点赞还是先收藏一下(^▽^ ),再更具体一点,我们的手机软件,比如电话啊,QQ啊,微信啊,里面不是都有联系人吗,我们可以在手机上对联系人进行一系列操作:修改信息,增加联系人,删除联系人,查找联系人等等等等.......这些啊其实都是我们的数据结构。

        而概念性来说:

数据结构(Data Structure)是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的 数据元素的集合。

        我爱说实话,数据结构是非常非常重要的!无论是我们刷题目,以后面试,甚至是以后工作了之后,数据结构都是会一直会陪伴我们的,而大伟我也会一直陪着大家的(✿◡‿◡)

        那我们要如何学好数据结构呢?简单,像这样就行:你真的会数据结构吗:顺序表,你真的学懂了数据结构?,c语言,数据结构,算法

        哈哈,开个玩笑,别当真啦!其实呢,重要的是需要画图思考,虽然这两点在哪里都很重要就是了~

        好的,废话不多说,那我们就开始今天的内容:顺序表吧!

                顺序表

        在动手写码顺序表前,我们需要先来分清楚两个概念:线性表和顺序表:

        那有铁汁好奇了,线性表是啥呢?

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

        简单来说,线性表就是在逻辑上是一条线,而实际的物理结构不一定是一条线。而我们今天要写的顺序表就是一个线性表,且他的底层就是数组,是对数组进行了封装。

         谈到顺序表,我们就有两个选择:静态顺序表和动态顺序表。那么这两个有什么区别呢?我们通过代码来看一看:

静态:

typedef int SQLDataType;//重命名int
#define N 10
typedef struct SeqList {
	SQLDataType arr[N];
	int size;//顺序表的实际大小
}SeqList;//重命名结构体

        动态: 

typedef int SQLDataType;
typedef struct SeqList {
	SQLDataType *arr;
	int size;
	int capacity;
}SeqList;

        不知道大家还记不记得typedef了,没错,typedef将int 和 struct SeqList进行重命名,而我为什么要这么做呢?大家可以思考一下,其实也就是typedef的好处是什么:


        鸡屁踢老弟给出了以下几种答案:

  1. 代码可读性:为复杂的数据类型创建简洁的别名,提高代码的可读性
  2. 平台无关性:在一些情况下,数据类型的大小可能因编译器和操作系统的不同而有所变化,可以为不同平台定义相同的别名,提高代码的可移植性
  3. 简化复杂声明:声明一个函数指针类型可能会变得更加清晰
  4. 抽象底层实现:使你的代码更容易维护。通过定义数据类型的别名,你可以在不影响代码其他部分的情况下更改底层实现
  5. 提高代码的一致性:确保在整个代码库中一致地使用相同的数据类型,减少错误和混淆的可能性

        umm,说的很好,不亏是鸡踢屁牢弟,简单来说,就是便于书写和阅读,可以以便后面根据需求修改类型,如可以直接把一大片的int改为char,且便于维护。

        那我们再回到上面的两段代码,我们会发现,静态顺序表是通过N来确定整个顺序表的最大容积;而动态顺序表是定义了个指针,后期可以通过动态内存开辟来实现最大容积的变化,还有size来确定有效数据,capacity来确定最大数据。

        这样一对比铁汁们就会发现哪个方法会更好呢?  当然是动态更好了,对吧?

        好的,我们确定了我们的顺序表是由动态开辟的,那我们可以玩(对动态表做什么)什么呢?

        来,让我们联想到微信联系人,我们可以加小姐姐的wx(增),可以删掉不喜欢的基佬(删),查找自己的好舍友(查),修改新加的朋友的备注(改)。诶~对了,我们实现的就是增删查改。

        代码实现:

    和之前的扫雷一样,我们还是开了三个文件,分别为:Sql.c  Sql.h test.c(当然了,名字是自己取的,我这么取的原因是顺序表英文为Sequence List,这样子更容易理解)

        这里插一嘴啊~ 其实关于C语言的命名有一定的规则,如:大驼峰命名法等,有兴趣的铁汁们下来自己查啊~(ง •_•)ง

        首先我们先定义个结构体(Sql.h),当然了别忘了重命名:

#include<stdio.h>
#include<assert.h>
#include<malloc.h>
typedef int SQLDataType;
typedef struct SeqList {
	SQLDataType *arr;//数组保存数据
	int size;//有效数据体积
	int capacity;//最大体积
}SeqList;

        然后是我们的声明增删查改(Sql.h),但是在此之外我们还多了一些操作:

//顺序表初始化
void SeqListInit(SeqList* ps);
//检查空间,如果满了,进行增容
void CheckCapacity(SeqList* ps);
// 顺序表尾插
void SeqListPushBack(SeqList* ps, SQLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* ps);
// 顺序表头插
void SeqListPushFront(SeqList* ps, SQLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* ps);
// 顺序表查找
int SeqListFind(SeqList* ps, SQLDataType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, size_t pos, SQLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, size_t pos);
// 顺序表销毁
void SeqListDestory(SeqList* ps);
// 顺序表打印
void SeqListPrint(SeqList* ps);

         因为一开始只是一张白纸,所以初始化一下没问题吧,既然都初始化了,没有空间怎么可以呢,再来个检查空间也没问题吧,增的话,在头部增加,在尾部增加,在特定位置增加没话说吧,删的话,删头,删为,删特定位置也没话说吧,查找,修改,再打印个链表以便观察,最后再销毁,有始有终,完美!

        好,开码!

        Sql.c

初始化:

void SeqListInit(SeqList* ps)
{
	ps->arr = NULL;//一开始啥都没有
	ps->capacity = ps->size = 0;//一开始啥都没有
}

  检查空间:

void CheckCapacity(SeqList* ps)
{
	if (ps->capacity == ps->size)//若有效容积等于最大容积了
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//若顺序表为空,先给四个空间,若不为空,两倍空间
		SQLDataType* tmp = (SQLDataType*)realloc(ps->arr, newCapacity * sizeof(SQLDataType));//扩容(开辟空间)
		if (tmp == NULL)//若开辟失败
		{
			perror("malloc failed!");
			return;
		}
		ps->arr = tmp;//修改空间
		ps->capacity = newCapacity;//修改最大体积
	}
}

  头插:

void SeqListPushFront(SeqList* ps, SQLDataType x)
{
	assert(ps);//断言,若ps不为空
	CheckCapacity(ps);//检查体积够不够了
	for (int i = ps->capacity; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//从最后一个元素的后一个元素往前覆盖,直到第一个元素
	}
	ps->arr[0] = x;//修改首元素的值
	ps->size++;//修改size的值
}

尾插:

void SeqListPushBack(SeqList* ps, SQLDataType x)
{
	assert(ps);
	CheckCapacity(ps);
	ps->arr[ps->size] = x;//直接在最后一个有效元素有一个位置插入
	ps->size++;//修改size大小
}

特定位置插入:

void SeqListInsert(SeqList* ps, size_t pos, SQLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);//确保pos(下标)位置有效
	CheckCapacity(ps);
	for (int i = ps->size; i > pos ; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//从最后一个元素后面一个元素开始往前覆盖,直到下标为pos位置
	}
	ps->arr[pos] = x;//修改pos位置的值
	ps->size++;//修改size
}

头删:

void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	int i;
	for ( i = 0; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//从前往后一次覆盖
	}
	ps->arr[i] = -1;//将最后一个元素修改为-1(这句代码其实可以不需要,放上去也有问题,大家思考一下为什么)
	ps->size--;//修改size
}

尾删:

void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	ps->arr[ps->size - 1] = -1;//(同样的,这句代码可以有问题并可以不要)
	ps->size--;//修改size
}

特定位置删除:

void SeqListErase(SeqList* ps, size_t pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	int i;
	for ( i = pos; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//从pos位置往后,依次覆盖
	}
	ps->arr[i] = -1;//(多余,错误)
	ps->size--;//修改size
}

查找:

int SeqListFind(SeqList* ps, SQLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
			return i;//遍历,如果找到了,返回下标
	}
	return -1;//如果找不到,返回个无效的下标
}

打印:

void SeqListPrint(SeqList* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d  ", ps->arr[i]);//遍历一下,没啥好说的
	}
	printf("\n");
}
void SeqListDestory(SeqList* ps)
{
	assert(ps);
	free(ps->arr);//释放空间
	ps->arr = 0;
	ps->capacity = ps->size = 0;
}

        OK,OK,上面就是我们的的动态单链表的代码实现,现在考验大家的大家的记性和认真程度了:还记得博主括号内的问题吗?不记得?呵,赶紧回去看!o( ̄ε ̄*)  。昂,看到了吧?简单来说问题就是 ps->arr[i] = -1 为什么有问题,为什么可以不需要?

        emm,怎么说捏,我们在插入数据的时候范围是不限的吧,所以我们也可以插入一个-1进去吧?那如果我们现在把这个位置设置为-1,那可不可以算是插入了个-1呢?’(°ー°〃),所以,我们完全可以直接不给他赋值,任由他自由,反正我们后面也不要关心他的值对吧~?

        所以啊,我们的代码实现可以多种多样,逻辑上和实用性上都要考虑。那我们顺序表的代码写完了,不得来玩一玩?┗|*`0′*|┛

test.c

#include"Sql.h"
int main()
{
	SeqList ps;
	SeqListInit(&ps);

 	 SeqListPushBack(&ps, 1);
	 SeqListPushBack(&ps, 2);
	 SeqListPushBack(&ps, 3);
	 SeqListPushBack(&ps, 4);
	 SeqListPrint(&ps);//1 2 3 4

	 SeqListPushFront(&ps, 7);
	 SeqListPushFront(&ps, 6);
	 SeqListPushFront(&ps, 5);
	 SeqListPrint(&ps);//5 6 7 1 2 3 4 

	  SeqListPopBack(&ps);
	  SeqListPopBack(&ps);
	  SeqListPrint(&ps);//5 6 7 1 2

	  SeqListPopFront(& ps);
	  SeqListPopFront(&ps);
	  SeqListPrint(&ps);// 7 1 2

	  if (SeqListFind(&ps, 1))
		  printf("1的下标为%d\n", SeqListFind(&ps, 1));
	  else
			  printf("找不到!");//1的下标为1

	 SeqListInsert(&ps, 1, 5);
	 SeqListPrint(&ps);// 7 5 1 2

	 SeqListErase(&ps, 2);
	 SeqListPrint(&ps);// 7 5 2

	 SeqListDestory(&ps);
	 SeqListPrint(&ps);//NULL

	return 0;
}

        让我们看看运行框内打印的是不是和我们想要的一样呢?你真的会数据结构吗:顺序表,你真的学懂了数据结构?,c语言,数据结构,算法

        通过对比,我们发现实际输出的结果和我们想要的效果完全一样啊,而且代码返回为0,这也就说明了我们代码写的没有问题。

        害,累鼠博主了,看到这里还不给大伟来个一键三连?o(^▽^)o。今天的顺序表也就到此为止了啊,下次带大家来看看顺序表的实际应用~期待着吧!

        I have no secret of success but hard work. 除辛勤工作之外,我别无成功的秘诀。

        本篇博客也就到此为止了,送大家一碗鸡汤,勉励自己以及这世界上所有追逐梦想的赤子趁年华尚好努力提升自己,莫欺少年穷!          你真的会数据结构吗:顺序表,你真的学懂了数据结构?,c语言,数据结构,算法

 文章来源地址https://www.toymoban.com/news/detail-828207.html

 

 

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

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

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

相关文章

  • 你真的会数据结构吗:二叉树

    ❀❀❀ 文章由@不准备秃的大伟原创 ❀❀❀ ♪♪♪ 若有转载,请联系博主哦~ ♪♪♪ ❤❤❤ 致力学好编程的宝藏博主,代码兴国!❤❤❤         halo铁汁们,没错又是你们人见人爱,花见花开的大伟啊,今天也是周六,大伟心情也是非常的美妙啊~ 所以就迫不及待的给大

    2024年04月23日
    浏览(28)
  • 数据结构:线性表顺序存储结构———顺序表

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

    2024年02月03日
    浏览(46)
  • 数据结构->顺序表实战指南,(手把手教会你拿捏数据结构顺序表)

    文章目录 ✅作者简介:大家好,我是橘橙黄又青,一个想要与大家共同进步的男人😉😉 🍎个人主页:橘橙黄又青-CSDN博客 今天开始我们正式进入数据结构的学习了,这篇简单了解一下: 线性表的存储结构:顺序存储结构、链式存储结构; 顺序表的定义:用一段物理地址连

    2024年01月25日
    浏览(65)
  • 【数据结构】二叉树——顺序结构

    由于每个节点都 只有一个父节点 ,所以我们可通过双亲来表示一棵树。具体方式通过 数组的形式 实现。 根节点的下标为0 按照层序从上到下排序 每层从左向右递增 表示形式: 二维数组 数据的列标为0 ,只需确定行标,即可锁定位置 根节点的父节点下标为 -1 列标为1存父节

    2024年02月02日
    浏览(56)
  • 数据结构(顺序结构、链式结构、索引结构、散列结构)

    数据结构,就是一种程序设计优化的方法论,研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算, 目的是加快程序的执行速度、减少内存占用的空间 。 数据的逻辑结构指反映数据元素之间的逻辑关系,而与数据的存储无关,是独立于计算

    2024年02月03日
    浏览(82)
  • 数据结构与算法——顺序表(顺序存储结构)及初始化详解

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

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

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

    2024年02月06日
    浏览(44)
  • 【数据结构——顺序表三种数据结构差异】

    数据结构 :就是数据之间的关系。 数据结构的关系 :一对多,多对多,集合,网络 第一种顺序表数据结构 第二种顺序表数据结构 第三种顺序表数据结构 从 初始化InitList、摧毁DestroyList、尾插法Push_back 来比较三者差异。 数据结构 InitList 第一种 只需要定义cursize 第二种 需要

    2024年02月21日
    浏览(39)
  • 数据结构-二叉树·堆(顺序结构的实现)

    🎉个人名片: 🐼作者简介:一名乐于分享在学习道路上收获的大二在校生 🐻‍❄个人主页🎉:GOTXX 🐼个人WeChat : ILXOXVJE 🐼本文由GOTXX原创,首发CSDN🎉🎉🎉 🕊系列专栏:零基础学习C语言----- 数据结构的学习之路 🐓每日一句:如果没有特别幸运,那就请特别努力!🎉

    2024年02月05日
    浏览(47)
  • 【数据结构】二叉树的顺序结构-堆

    普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而 完全二叉树 更适合使用顺序结构存储。 现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一个

    2024年02月09日
    浏览(53)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包