MYBLOG

0XFF编程网

先来做个小复习

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

顺序/循环/分支


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

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

递归是循环的一种,递归可以把规模为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,就变成了环形链表,这时就无所谓头还是尾了,而是形成了一个环。


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


阅读 221
全部留言