基础算法 | 数据结构之线性表&顺序表&链表(上)

各位,起床了起床了

小编又来送干货了

今天讲的是数据结构

全文字数:1185

阅读时间:10分钟

数据结构?啥玩意?

内容提要:

*预备知识

*顺序表(Sequential List)

*单链表(Singly Linked List )

*静态链表(Static list )

*循环链表(circular linked list)

*双向链表(doubly linked list)

01 预备知识

1.0 什么是线性表?

线性表(List)是零个或者多个数据元素的有限序列.

Pay attention:

1) 首先它是一个序列.里面的元素是有顺序的,如果有多个元素,除开头和结尾以外的元素都有一个前驱和一个后继.而开头元素只有后继,结尾元素只有前驱.

2) 其次线性表是有限的,也就是里面的元素个数是有限的。

1.1 线性表的基本操作(描述)

ADT 线性表(List) Data 线性表的数据对象集合为{a1, a2, a3, ......, an},每个元素类型为DataType。

Operation

InitList(L); //初始化线性表 IsEmptyList(L); //判断线性表是否为空 ClearList(L); //清空线性表 GetElemList(L, i, *e); //获取第i个位置的数据 SearchList(L, e); //查找与数据e相等的元素 InsertNodeList(L, i, e);//在第i个位置插入元素 DeleteNodeList(L, i, *e);//删除第i个位置数据 GetLengthList(L); //获取线性表的长度

endADT

关于线性表的基本操作就上面几种,还有几个例如线性表的排序,合并,逆序等等操作。为了文章篇幅,就下次再介绍了。

1.2 什么是顺序存储结构?

线性表的顺序存储结构,就是指 用一段地址连续的存储单元一次存储线性表的数据元素。学过高级语言的朋友,相信对数组这玩意儿都不会陌生吧。数组就是一种顺序存储结构。

1.3 什么是链式存储结构?

链式存储结构就是可以用一组任意的内存单元存储线性表中的元素。与顺序存储不同的是,这组内存单元可以是连续的,也可以是不连续的。这就意味着,元素可以存储在内存的任意位置。(嗯对的,强调三连)正因为如此,在链式结构中,每个元素不仅要存它的信息,还需要存储它后继元素的存储地址。我们把存储元素信息的域称为数据域,而把存储后继元素地址的域称为指针域。由这两部分共同组成的数据元素ai,则可以称之为节点(Node)。

如下面这个图所示:

1.5 什么是链表?

链表就是链式存储的线性表。结点之间通过逻辑连接,形成链式存储结构。存储结点的内存单元,可以是连续的也可以是不连续的。逻辑连接与物理存储次序没有关系。

02 顺序表(Sequential List)

2.0 什么是顺序表?

采用顺序存储结构的线性表,就是顺序表。

2.1 顺序表的存储结构代码

这里我们统一采用C语言来描述。

#define MAXSIZE 20 //存储空间的初始大小

typedef int DataType //类型可根据实际情况而定typedef struct

{ DataType data[MAXSIZE]; //数组来存储数据 int length; //实际长度

}SqlList;

可见,顺序表的几个重要特性:

1) 存储空间的位置:数组data

2) 顺序表的最大容量:数组长度MAXSIZE

3) 顺序表当前长度:length

2.2 顺序表的插入操作

相信大家在排队的时候都有过被插队的体验吧。当一个插队到你前面时,这个时候你内心os mmp外加素质三连的同时,也不得不往后挪一个位置。于是乎这个就不得了了,你后面的也要往后挪,你后面的后面也是……然后队伍里瞬间就炸锅了…… 那么,这个顺序表的插入其实也差不多的。由于地址是连续存储的,那么在某个地方插入以后,其后的元素不得不往后挪一个位置。

插入算法描述:

1) 异常处理(插入位置不合理、顺序表已经满等等),返回异常。

2) 从最后一个元素往前遍历到第i个位置,依次将他们都往后挪一个位置。

3) 将要插入的元素放入位置i处。

4) 别忘记了表长度length++。

由于数组下标是从0开始的,我们习惯要删除的位置第i处又是从1开始算起的。本文就全部统一成,都从0开始吧。比如要在第5个位置插入一个元素,那就是a[5]。不然新手朋友真的会纠结死在这个点上.当然,如果你喜欢,也可以将数组设置为从1开始.....

具体代码如下:

2.2 顺序表的删除操作

算法描述:

1) 异常处理(删除位置不合理、顺序表为空等等)

2) 尾删,直接获取然后length--。

3) 中间删,从i开始往后遍历,依次将各元素往前挪。e获取要删元素,length--即可。

就暂时讲这两个比较复杂的操作就好了。其他的看完整源代码应该很容易理解的。

2.3 顺序表的完整代码

关于单链表,循环链表,双链表等内容,请听下回分解吧。把太多东西塞一篇文章估计各位老铁也容易爆炸……喜欢就撒花撒花哈哈哈哈,希望大家多多支持哈。

1

END

-The End-

文案 / 邓发珩(大一)

排版 / 邓发珩(大一)

指导老师 / 秦时明岳

如对文中内容有疑问,欢迎交流。

邓发珩(华中科技大学管理学院本科一年级、2638512393@qq.com、个人公众号:程序猿声)

原文发布于微信公众号 - 数据魔术师(gh_39567a079597)

原文发表时间:2018-01-31

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开发技术

排序之堆排序

  本篇博客是在伍迷兄的博客基础上进行的,其博客地址点击就可以进去,里面好博客很多,我的排序算法都来自于此;一些数据结构方面的概念我就不多阐述了,伍迷兄的博客中...

952
来自专栏小狼的世界

Leetcode刷题记录:构建最大数二叉树

给定一个不含重复数字的数组,最大二叉树构建规则如下: 1、根是数组中最大的数字 2、左边的子树是最大数字左边的内容 3、右边的子树是最大数字右边的内容

1052
来自专栏微信公众号:Java团长

高效遍历Java容器

通过本文,你可以更深入的学习 Java 语言中 forEach 语法的知识,以及它和 C 语言形式的 for 循环、 Steam API 的对比。

2194
来自专栏小勇DW3

HashMap 与 ConcrrentHashMap 使用以及源码原理分析

数组:采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为O(1);通过给定值进行查找,需要遍历数组,逐一比对给定关键字和数组元素,时间复杂度为...

5703
来自专栏微信公众号:Java团长

Java开发中如何正确踩坑

之前在这个手册刚发布的时候看过一遍,当时感觉真是每个开发者都应该必读的一本手册,期间还写过一篇关于日志规约的文章:《下一个项目为什么要用 SLF4J》,最近由于...

1054
来自专栏趣谈编程

可以管理时间的二叉堆

面试官:写一个堆排吧 我心想:堆排是什么鬼 理解堆排,首先要理解二叉堆。理解了二叉堆的“下沉”操作,基本上就可以理解堆排了。今天我们来看一看什么是堆,以及堆...

2106
来自专栏小鄧子的技术博客专栏

算法与数据结构(2),Map

睡了不到六个小时,被一个很奇葩又很奇怪的梦吓醒,以最快的速度穿好衣服,跑下楼去买了杯咖啡上来,文字没写多少,咖啡倒是一饮而尽。

891
来自专栏数据结构与算法

2952 细胞分裂 2

2952 细胞分裂 2 时间限制: 2 s 空间限制: 16000 KB 题目等级 : 钻石 Diamond 题目描述 Description 著...

3536
来自专栏IT笔记

乐视2017暑假实习生笔试题二分查找之JAVA实现

试题 对一个含有20个元素的有序数组做二分查找,数组起始下标为1,则查找A[2]的比较序列的下标为() A. 9,5,4,2 B. 10, 5, 3, 2 C....

3937
来自专栏浪淘沙

Java学习day16---人际关系

1285

扫码关注云+社区

领取腾讯云代金券