您现在的位置是:门户> 算法与数据结构

最简单易懂的10堂算法入门课——初阶数据结构
x0ffer 2018-12-19 455人围观 0条评论
简介数据结构对算法设计至关重要 数据结构有两层含义—— 1 代表了储存数据的集合 一系列的数据能够储存在这个数据结构中。 2 代表了储存的数据之间有特定的关系

    先来做个小复习

    上一课咱们了解了“程序结构”共有三种——

    顺序/循环/分支


    三种结构互相组合/嵌套,就能形成千变万化的各种各校的程序。

    也进阶地讲解了递归函数表结构这两个概念——

    递归是循环的一种,递归可以把规模为n的问题,简化到规模为n-1的问题上,并且可以循环这个过程,最终变成容易解决的问题。

    分支结构过长是不好的,可以采用函数表结构的形式,把状态用数字表示出来,以解决这个问题,程序会变得非常简洁美妙。

    本课我们开始学习——“数据结构”。

    数据与数据之间,往往存在逻辑关系

    数据结构对算法设计至关重要

    数据结构有两层含义——

    1 代表了储存数据的集合

    一系列的数据能够储存在这个数据结构中。

    2 代表了储存的数据之间有特定的关系

    这正是“结构”一词的意义,学过线性代数的同学一定很清楚,结构的力量很强大,能让信息量成倍地扩大。

    数据——重要的信息价值所在

    数据结构的选择会极大地影响算法设计

    合适的数据结构能让算法设计时更高效更简洁,而不合适的数据结构有时候会把算法设计带入深渊,甚至无法实现算法

    有些初学编程的朋友在处理一些算法问题时,难免会遇到一些“感觉很繁琐,但又想不出什么简单的方法”的情况,这时不妨回来看看数据结构,换一个更适合的数据结构,常常会有柳暗花明之感呢。

    数据结构是编程的基础中的基础

    初阶数据结构

    数据结构共8种,有4种最常用也最简单,它们是:

    数组(Array)

    链表(Linked list)

    堆栈(Stack)

    队列(Queue)

    由于它们的结构都是线性的,它们还有一个共同的名字——

    “线性表”

    四种初阶数据结构

    数组(Array)

    数组是最基本最常用的数据结构,它就是将数据存储在一片连续的区域内。

    学过线性代数的同学马上知道,线性代数中的向量/矩阵都是对应着数组的数据结构。

    举个例子:

    一个数组a,在a中存了3个数,依次是2 4 8。那么访问时,只需要使用“下角标”就可以。

    比如,a[0]就是2,a[1]就是4,a[2]就是8。

    对于编程初学者,还需要提示一点,编程中的整数是从0开始的,所以数组中第一个位置为:a[0]。


    数组的优势——访问元素

    从上面例子我们能够看到,数组中的数据很容易访问,使用下角标就可以;而且数组可以是2维/3维甚至n维,比如:

    二维数组 a 的第2行,第3列元素为——

    a[1,2]

    简单吧。数组的下角标有许多巧妙的应用,在使用时就会发现。

    数组也有劣势,就是插入/删除元素时,需要移动后面所有的元素,会耗费资源,所以如果在需要频繁插入/删除元素的场合下,就不太适合使用数组,那么用什么呢?

    链表(Linked list)

    有的应用场合,需要建立一个线性表,但是长度又不确定,比如要经常增加或删除元素,那么就要用到链表

    链表包含两个部分——

    数据部分 和 指针部分

    指针就是指它所链接的地址,所以链表的插入和删除数据只需要修改指针即可。


    还是上个具体的例子吧——

    链表a的数据部分:2 4 8 6

    链表a的指针部分:1 3 2 _

    (链表a的数据部分对应的地址是 0 1 2 3)

    首先第1个元素是数据2,然后数据2对应的是指针1,那么就是指向数据4,而数据4对应的指针为3,即对应数据6,以此类推。

    所以链表a代表的实际顺序其实是 2 4 6 8

    这时,如果我想在4 和 6 中间加一个数据5,就很简单——

    首先在数据最后加一个5,然后再修改指针即可:

    链表a的数据部分:2 4 8 6 5

    链表a的指针部分:1 4 2 _ 3

    (链表a的数据部分对应的地址是 0 1 2 4)

    指针中加粗的两位是更改的部分,能看出怎么做的么?

    单向链表/双向链表/环形链表

    上面的链表是单向的,从0到1到最后,而如果将上面的空位_变成0,就变成了环形链表,这时就无所谓头还是尾了,而是形成了一个环。


    当指针部分不仅仅指向下一位置,而是也指向上一位置的话,那么就可以自由地向上或向下搜索了,这就是双向链表


分享:

文章评论