【数据结构之顺序表】用图和代码让你搞懂顺序结构线性表

22
• 阅读 1164

什么是线性表?

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

【数据结构之顺序表】用图和代码让你搞懂顺序结构线性表

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

表的特点有:

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

【数据结构之顺序表】用图和代码让你搞懂顺序结构线性表

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

【数据结构之顺序表】用图和代码让你搞懂顺序结构线性表

明确几个名词:

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

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

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

线性表的顺序存储方式

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

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

【数据结构之顺序表】用图和代码让你搞懂顺序结构线性表

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

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

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

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

【数据结构之顺序表】用图和代码让你搞懂顺序结构线性表

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

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

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

【数据结构之顺序表】用图和代码让你搞懂顺序结构线性表

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

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

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

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

【数据结构之顺序表】用图和代码让你搞懂顺序结构线性表

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

实现思路

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

【数据结构之顺序表】用图和代码让你搞懂顺序结构线性表

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

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

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

【数据结构之顺序表】用图和代码让你搞懂顺序结构线性表

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

  1. 用来实际存储数据的数组——data[]
  2. 用来表示线性表的最大存储容量的值——MAXSIZE
  3. 用来表示线性表的长度的值——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 || position > list->length + 1) {
        printf("插入位置不合法\n");
        return 0;
    }
    for (int i = list->length - 1; i >= position - 1; i--) {
        list->data[i + 1] = list->data[i]; //向后赋值
    }
    list->data[position - 1] = elem;
    list->length++;
    return 1;
}

注意:

  1. 需检查线性表是否已满(length 是否等于 MAXSIZE
  2. 需检查插入位置是否合法(不能插入到表外)
  3. 插入成功后,线性表的长度要加一

现在,刚刚插队的小孩被妈妈喊回家吃饭了,所以他需要离开队伍,这时队伍中“空出”了一个位置,所以他后面的小孩都自觉的向前一步走,使队伍更紧凑。

【数据结构之顺序表】用图和代码让你搞懂顺序结构线性表

孩子离队后,“空位”之后的每个孩子都逐个“向前一步走”。线性表删除元素时,使用“向前赋值”来实现孩子“向前一步走”的效果。删除操作和插入操作刚好相反,下图是其过程:

【数据结构之顺序表】用图和代码让你搞懂顺序结构线性表

下面是代码实现:

/**
 * 删除指定位置的元素,并保存其值
 * list : 线性表的地址
 * position : 要删除的元素位置
 * elem : 保存变量的地址
 * return 0 : 删除失败;return 1 : 删除成功
 */
int delete(ArrayList *list, int position, int *elem)
{
    if (list->length == 0) {
        printf("线性表为空\n");
        return 0;
    }
    if (position < 1 || position > list->length) {
        printf("删除位置不合法\n");
        return 0;
    }
    *elem = list->data[position - 1];
    for (int i = position - 1; i < list->length - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    list->length--;
    return 1;
}

同样注意:

  1. 需检查线性表是否为空
  2. 需检查删除位置是否合法
  3. 删除成功后,线性表长度要减一

其他操作

至此,已经介绍了基本的“增、删、改、查”的“增和删”。

至于“改和查”,由于顺序存储结构的线性表是用数组来实现的,而数组的查询和修改是及其方便的,如:

int a = array[1]; //查询
array[2] = 5; //修改

所以,顺序存储的线性表的查询和修改也极为方便。

下面是查询的代码:

/**
 * 查询指定位置的元素
 * list : 要操作的线性表
 * position : 要查询的元素位置
 * elem : 保存变量的地址
 * return 0 : 查询失败;return 1 : 查询成功
 */
int get(ArrayList list, int position, int *elem)
{
    if (list.length == 0) {
        printf("线性表为空\n");
        return 0;
    }
    if (position < 1 || position > list.length) {
        printf("位置不合法\n");
        return 0;
    }
    *elem = list.data[position - 1];
    return 1;
}

下面是更新的代码:

/**
 * 更新指定位置的元素
 * list : 要操作的线性表的地址
 * position : 要更新的元素位置
 * elem : 要更新的值
 * return 0 : 更新失败;return 1 : 更新成功
 */
int update(ArrayList *list, int position, int elem)
{
    if (list->length == 0) {
        printf("线性表为空\n");
        return 0;
    }
    if (position < 1 || position > list->length) {
        printf("位置不合法\n");
        return 0;
    }
    list->data[position - 1] = elem;
    return 1;
}

以上即为针对顺序存储结构的最基础的增删改查操作,会了这四种,其他的操作也基本上可以触类旁通了。

顺序存储线性表的优缺点

上面的那个小孩加入队伍的时候,为了给他腾位置,很多人都而向后退一步。但是才玩了一会,他就被叫回去吃饭了,之前向后退步的人又不得不再向前走一步。因为一个人,而导致很多人不得不为之变动,小孩们很不乐意。

写过上面四个函数,我们也会有小孩们的体会。

增加和删除一个元素太麻烦了,当元素很少还不明显,但当有成百上千个元素时,就需要移动大量的元素了,很麻烦,我们很不乐意。

查询和修改一个元素却很简单,这是数组的功劳。

另外,线性表的容量是固定的,大多数情况下,我们并不会提前知道线性表的容量,所以容量的分配是一个很大的问题,少了不够用,多了太浪费。像极了在快速长身体的青春期时买衣服的你。

总结一下:

优点:

  • 查询和修改元素方便快捷

缺点:

  • 增加和删除某个元素需要移动大量的其他元素
  • 难以确定容量大小(所以通常会尽可能分多一点来“兜底”,但这极易造成浪费从而影响性能)

如有错误,还请指正。 如果觉得不错,可以关注一下我。

【数据结构之顺序表】用图和代码让你搞懂顺序结构线性表

点赞
收藏
评论区
推荐文章
22 22
2年前
【数据结构之链表】看完这篇文章我终于搞懂链表了
一览:本文从零介绍链式存储结构的线性表——单链表。包括以下内容:什么是链式存储存储结构?单链表的结构辨析头结点、头指针等易混淆概念基本的增删改查操作(不带头结点和带头结点)单链表与顺序表的对比线性表的链式存储结构在一文中我们介绍了一种“用曲线连接”的线性表,“曲线”是一种形象化的语言,实际上并不会存在所谓“曲线”的这种东西。所谓“曲线连
22 22
2年前
一文看懂二叉树的概念和原理
系列文章推荐阅读0.前言到目前为止,我们已经讲述了、、、四种数据结构,它们有一个共同的特点,就是它们都是线性表,换句话来说,它们都是线性结构,像一根绳子一样。在文章已经介绍过线性表的定义了,即由若干元素按照线性结构(一对一的关系)组成的有限序列。关键词是一对一的关系。显然,在复杂的现实社会中,这种一对一的关系是不能较好的满足我们的需求的。比如
22 22
2年前
【数据结构之栈】用详细图文把「栈」搞明白(原理篇)
【系列文章合集】顺序存储结构的线性表(https://mp.weixin.qq.com/s/OGbxsh0aNh1woHA85weZw)如何掌握C语言的一大利器——指针?(https://mp.weixin.qq.co
查找算法
顺序查找顺序查找又称为线性查找,对线性表和链表都适用。线性表可以通过数组下标递增来顺序扫描每个元素,链表可以通过next指针依次扫描每一个元素。:::tip指针实现顺序表时,顺序表中是指针时,在定义顺序表的结构体后,需要对顺序表初始化,初始化时为指针申请堆
线性表
线性表的顺序存储实现(数组形式)称为顺序表。线性表顺序表示原理解析这里描述的线性表是逻辑结构的,独立于存储结构。线性表的顺序表示简称顺序表。顺序表实现线性表的方式是使用数组。线性表第一个元素的数组下标是0。另外一种实现顺序表的方法:使用数组方式比动态分配更
Wesley13 Wesley13
2年前
Java实现顺序栈
一、分析  栈是限定仅在表的一端进行插入或删除操作的线性表,对于栈来说,操作端称为栈顶,另一端则称为栈底,栈的修改是按照后进先出的原则进行的,因此又称为后进先出的线性表。  顺序栈是指利用顺序存储结构实现的栈,即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置。  一个标准的顺序栈
Stella981 Stella981
2年前
Excel工作表保护的密码破解与清除...假装自己破解密码系列?
有一次我女朋友让我帮忙解一个excel表格的保护密码,然后~用了宏网上下载来的Excel经常会有工作表保护,也就是无法修改,妄图做任何修改的时候你就会看见这句话:您试图更改的单元格或图表位于受保护的工作表中。若要进行更改,请取消工作表保护。您可能需要输入密码。那么这篇文章可以简单的帮你解决这个问题...因为Excel中内置了VisualBasi
Wesley13 Wesley13
2年前
D1
1\.数据结构  1.1线性结构  (1)最常用的数据结构,特点是数据元素之间存在一对一的线性关系  (2)有两种不同的存储结构,即顺序存储结构和链式存储结构    顺序存储的线性表称为顺序表,顺序表中的存储元素是连续的    链式存储的线性表称为链表,链表中的存储元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息
Wesley13 Wesley13
2年前
C#二分查找算法设计实现
C二分查找算法设计实现1.介绍二分查找也称折半查找(BinarySearch),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。(记住了前提要求是顺序存储结构,而且要有序排序,所以说对于一个无序的是没法用二分查找的)2.查找算法过程
Wesley13 Wesley13
2年前
PHP优先级队列
优先级队列首先,我们要了解一下什么叫队列:队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。从定义来看,队列是无法更改顺序的线性集合。线性集合一般有几种规则:先进先出(队