栏目分类

你的位置:被窝影院手机版免费-不用充会员可看完整的污软件-免费97免费 > 不用充会员可看完整的污软件 > 顺序存储结构的线性表

顺序存储结构的线性表

发布日期:2021-10-07 00:10    点击次数:71

本文转载自微信公众号「二十二画程序员」,作者行小观。转载本文请联系二十二画程序员公众号。 

什么是线性表?

所谓线性,即一条线,这条线可以是直线,也可以是曲线。

所谓表,肯定都不陌生,生活中有各种各样的表或者表格。我们在表格中填写各种各样的信息,通过表格,能够很好地对信息进行分类储存和分析。

表的特点有:

表由若干单元格组成 单元格之间有顺序 除特殊位置的单元格(首起和结尾)有一个“邻居”外,其他单元格都有两个“邻居”。

那么什么是线性表呢?简单来说,就是使用“直线”或“曲线”连接起来的表。

明确几个名词:

我们在表中称呼的“单元格”,在线性表中可以称之为元素。 对于某个元素,在其前邻的元素称之为直接前驱元素,在其后邻的元素称之为直接后继元素。 线性表中元素的个数称之为线性表的长度。 第一个元素称之为首元素,最后一个元素称之为尾元素。

由上图可以总结出线性表的特点:

线性表由若干元素组成,用来存储信息。 元素之间有顺序。 除了首元素(只有一个直接后继元素)和尾元素(只有一个直接前驱元素)外,其它元素都有且仅有一个直接前驱元素和一个直接后继元素。 线性表的顺序存储方式

不管数据结构的形式再怎么变,数据结构的最根本的目的始终不会变,那就是为了更高效地对数据进行存储、修改、删除和访问,这种高效通常体现在时间上和空间上,也即程序运算速度快慢和所用存储空间的少多。

那么线性表这种数据结构是如何进行存储的呢?前面介绍了一种“用直线连接”的线性表,“直线”只是形象化的语言,实际上的存储中是不会有所谓“直线”这种东西的。

所谓“直线连接”即顺序存储,那么什么是顺序存储呢?

首先得先解释一下什么是内存。内存是计算机的存储器的一种,它扮演着非常重要的角色。世上的一切东西,即使是虚拟的,也需要有物理的实体作为载体。

举个例子,孩子们的玩耍需要有土地来承载,公园、游乐园等都是这种载体。没有土地作为载体,再活泼的孩子也没法活泼起来。对于代码来说,内存就是玩耍时需要的那块土地。

总之,内存就是代码运行时各种信息数据的载体空间。有了内存,我们才能施展拳脚。

既然涉及到空间,那该空间的东西肯定会以某种形式排列起来。通常来说,无外乎“整齐划一”和“杂乱无章”两种形式。

比如,一群孩子肩并肩地站成一排,占据一定的连续土地。

反映在内存中,就是数据紧密相接,占据一定的连续内存。

这种“占据连续的内存空间”即为顺序存储方式。

可以把内存比作一幢大楼,楼中有许多房间,每个房间都有房间号,一个房间刚好住一个人。当 A、B、C、D 四位小朋友来到大楼里,选了连续的 4 个房间分别入住,那么我们就可以认为,这四位小朋友是“顺序入住”的。

内存 = 大楼,房间 = 内存单元,房间号 = 内存地址,入住的人 = 要存储的数据。

反映在内存中,所谓顺序存储,即用一段连续的内存单元分别存储线性表中的数据。

如上图所示,线性表的顺序存储是在内存空间中开辟一块连续的空间,开辟好之后,这块空间就被这个线性表“占用”了。

实现思路

线性表的每个数据元素的类型都相同、数据元素个数有限。根据这个特性我们很容易想出可以用一维数组来实现顺序存储结构。

注意:是先占用再使用,也即线性表的长度不能超过最大存储容量(数组的长度)。

如何用代码表示一个用数组实现的线性表?首先搞清楚一个这样的线性表有哪些必要的东西。

线性表需要一个数组用来存储数据元素; 线性表需要一个最大存储容量(数组长度),即你想要“占”多少个位子,是要事先声明的,不再轻易改变; 线性表需要一个长度用来表示存了多少数据元素,线性表的长度随着数据的增删而变化,没有这个就可能导致你“塞”的数据比“占”的位子多,而“溢”出来。

总结一下,一个顺序存储方式的线性表 (ArrayList) 由以下三部分组成:

用来实际存储数据的数组——data[];

用来表示线性表的最大存储容量的值——MAXSIZE;

用来表示线性表的长度的值——length。

具体实现

那么下面就可以使用 C 语言的结构体来实现这种线性表了。

为了说明问题简单,我们这里的线性表只存储整数。

#define MAXSIZE 10 //线性表的最大存储容量  typedef struct {     int data[MAXSIZE]; //存储数据的数组     int length; //线性表的长度 } ArrayList; 

这样的一个结构体就能完美地表示一个顺序存储结构的线性表了。

初始化

孩子们已经知道公园了在哪了,但还未踏上去。

到此为止,我们已经知道了什么是顺序存储,也知道了如何用代码表示线性表,但仅停留在“知道”这一步,我们还未将其实际地“创造”出来放到内存中。

要想使用一个线性表,那么我们得先声明一个线性表,然后将其初始化为空线性表,也即 length = 0:

/**  * 初始化线性表,将线性表的长度置为0  * list : 要操作的线性表的地址  */ void init(ArrayList *list) {     list->length = 0; } 

注意:我们要改变线性表的长度 length,所以要传给 init 函数的参数是一个 ArrayList 类型的指针。

ArrayList list; //声明线性表list init(&list); //初始化list 
插入和删除操作

现在孩子们已经来到公园了,并且已经肩并肩地排好队开始玩游戏了,现在有一名小伙伴想要加入到队伍中和他们一块玩。所以有一部分孩子为他“腾”出了位置,让他“插队”。

由于 甲 要站在 B 的后面,所以 C、D、E 都要后退一个位置给 甲“腾空位”,然后 甲 才能“插队”到 B 后面。

可以把孩子们站成的队伍看成线性表,把孩子看成元素,下图所示过程就是线性表的插入元素的操作过程。

孩子们从最后一个人开始逐个后退,后退到需要的空位为止,线性表的元素也是如此,不过线性表是使用“向后赋值”来实现“后退”的效果的。

分析到此,代码就可以写出来了。

/**  * 向线性表的指定位置插入指定值  * list : 线性表的地址  * position : 要插入的位置 (1 <= position <= list->length + 1)  * elem : 要插入的值  * return 0 : 插入失败;return 1 : 插入成功  */ int insert(ArrayList *list, int position, int elem) {     if (list->length == MAXSIZE) {         printf("线性表已满\n");         return 0;     }     if (position < 1 


上一篇:因疫情蔓延 日本札幌及大阪将暂停旅游支援项目3周
下一篇:别信!这段所谓歼 20 飞行表演视频是假的