数据结构总结---------线性表

ゝ一纸荒年。 2022-03-15 05:28 217阅读 0赞

### 数据结构总结---------线性表 ###

*  1.顺序表（数组）
 *   *  1.1 增加
     *  1.2 删除
     *  1.3 更改
     *  1.4 查询
 *  2.链式存储结构（链表）
 *   *  2.1 增加
     *  2.2 删除
     *  2.3 更改
     *  2.4 查找
     *  2.5 空间
     *  2.6 链表结构的讨论

# 1.顺序表（数组） #

由于讨论的是线性表所以会与链表进行增删改的对比

## 1.1 增加 ##

1.  当每次的加入都是在末尾时：速度很快
2.  当插入的位置不在末尾时（不管是否知道下标的情况下）：速度相对链表来说是慢的  
    为什么？因为插入到对应的位置后，后续的元素都需要往后移动

## 1.2 删除 ##

1.  当每次删除都是末尾元素时：速度很快
2.  当删除的元素不在末尾时（不管是否知道下标的情况下）：速度相对链表来说是慢的  
    为什么？因为删除后，后面的元素都需要往前移动

## 1.3 更改 ##

1.  当每次更改元素时（不管是否知道下标的情况下）：速度相对链表来说是快的  
    为什么？链表的空间不是连续的而数组是，且如果通过下标的方式修改数组会更快

## 1.4 查询 ##

1.  知道下标的情况下：会比链表快很多  
    为什么？因为链表想找到那个元素只能从头开始遍历
2.  不知道下标的情况下：也会比链表快  
    为什么？因为链表空间不是连续的

# 2.链式存储结构（链表） #

## 2.1 增加 ##

相对数组来说，是快的，因为链表存储结构并不是连续的，而是一个类指定，**所以他不管增加到哪个位置都不需要像数组那样向后移元素，只需要改变指定的对象即可**

## 2.2 删除 ##

相对数组来说，是快的，因为删除一个元素时不会发生元素后移的现象

## 2.3 更改 ##

相对数组来说会慢，因为是非连续的空间，找到修改的值需要从头开始遍历才能找到想修改的那个空间

## 2.4 查找 ##

相对数组来说是慢的，因为非连续的空间和需要从头遍历查找

## 2.5 空间 ##

由于创建时需要多指定一个空间，所以从这个方面来讲是浪费空间的，但是数组的创建是固定不变的所以会存在空间的浪费现象，而链表则没有浪费现象，从这方面来讲就是节省空间的

## 2.6 链表结构的讨论 ##

1.图解链表结构  
![在这里插入图片描述][20190228233743946.png]  
2.头指针概念

*  在线性表的链式存储结构中，头指针是指链表指向第一个结点的指针，若链表有头结点，则头指针就是指向链表头结点的指针。
 *  头指针具有标识作用，故常用头指针冠以链表的名字。
 *  无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

3.头结点

*  ==结点的存在使得空链表与非空链表处理一致=，也方便对链表的开始结点的插入或删除操作。
 *  首元结点也就是第一个元素的结点，它是头结点后边的第一个结点。
 *  头结点不是链表所必需的。

**总结 ：在业务场景需要大量查询和修改操作时我们可以优先考虑数组，但是当需要大量增加和删除操作时我们可以考虑链表的数据结构。而链表中的头指针主要用于标识整个数组，而头结点则是主要用于避免空链表与非空链表处理不一致的问题**

版权声明：本博客为记录本人自学感悟，内容大多从网上学习与整理所得，若侵权请告知！

[https://me.csdn.net/qq\_39657909][https_me.csdn.net_qq_39657909]

[20190228233743946.png]: /images/20220315/ded926ba272d4347873855a5bd91edb7.png
[https_me.csdn.net_qq_39657909]: https://me.csdn.net/qq_39657909

发表评论取消回复

表情：

评论列表（有 0 条评论，217人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构——线性表——知识点总结

自己看的书，对书上的内容进行总结。此篇为相关知识点总结线性表的定义：线性表是具有相同数据类型的n个数据元素的有限序列。n为表长，当n = 0时，为空表。

柔情只为你懂/ 2023年10月17日 13:01/ 0 赞/ 154 阅读

相关数据结构——线性表

顺序表代码单链表代码循序表算法 include<stdio.h> include<string.h> include"malloc.h

ゝ一纸荒年。/ 2022年12月26日 13:27/ 0 赞/ 194 阅读

相关【数据结构】线性表

文章git地址：https://gitee.com/HappyTeemo/c\_data\_structure 线性表定义定义：由零个（空表）或多个数据元素组成的有限

缺乏、安全感/ 2022年12月12日 04:49/ 0 赞/ 202 阅读

相关数据结构线性表

\ifndef SEQLIST\_H \define SEQLIST\_H \include<iostream> using namespace std;

痛定思痛。/ 2022年08月13日 12:36/ 0 赞/ 201 阅读

相关数据结构--线性表

数据结构是相互之间一种或多种关系的数据元素的集合，它是针对具体的问题提出的，我们在分析问题的过程中一般要经历：根据问题建立数学模型（逻辑结构），在计算机中建立相

偏执的太偏执、/ 2022年07月14日 01:44/ 0 赞/ 232 阅读

相关数据结构-->线性表

package 线性表; import java.util.Scanner; class DATA \{ /\ 定义节点 \/ String key;// 关键字

阳光穿透心脏的1/2处/ 2022年06月13日 10:16/ 0 赞/ 237 阅读

相关数据结构（线性表）

线性结构-线性表实验简介数据结构中的逻辑结构分为线性结构和非线性结构，这一章和下一章我们会介绍线性结构，简单地说，线性结构是n个数据元素的有序（次序）集

素颜马尾好姑娘i/ 2022年06月05日 11:42/ 0 赞/ 271 阅读

相关数据结构（线性表）

线性表的逻辑结构线性结构的特点是数据元素之间存在一对一的线性关系。即：（1）除第一个元素之外所有元素位置前面都只有一个元素，称为直接前驱（2）出最后一个元素之外所有元素

港控/mmm°/ 2022年06月05日 02:44/ 0 赞/ 260 阅读

相关数据结构总结---------线性表

数据结构总结---------线性表 1.顺序表（数组） 1.1 增加 1.2 删除 1.3 更改 1.4 查

ゝ一纸荒年。/ 2022年03月15日 05:28/ 0 赞/ 218 阅读

相关数据结构：线性表

先来一张总体的结构图： ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4

淡淡的烟草味﹌/ 2021年12月09日 04:25/ 0 赞/ 436 阅读