数据结构--绪论（一些基本概念）

本文是《数据结构（C语言版）》-- 清华大学出版社的读书笔记。

基本概念和术语

数据：（data）是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素：（Data element）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项 组成，数据项是构成数据元素不可分割的最小单位

7dd49858803a4b80aaebb0faf05d1221png

数据对象： （Data Object）是性质相同的数据元素的集合是数据的一个子集

数据结构：（Data Structure）是相互之间存在一种或多种特定关系的数据元素的集合。数据元素之间的关系成为结构。（一组具有相同结构的值）

3219e7b62ab74dd0afba01014a4e39dfpng

数据结构的形式定义为：数据结构是一个二元组

Data_Structure = (D, S)
D：数据元素的有限集
S：D上关系的有限集

结构定义中的关系描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。数据结构在计算机中的表示（又称映像）称为数据的物理结构，它包括数据元素的表示和关系的表示。

数据元素之间的关系

顺序映像： 顺序存储结构；借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
非顺序映像： 非顺序存储结构链式、索引、散列（哈希）；借助指示元素存储地址的指针表示数据元素之间的逻辑关系。

虚拟存储结构： 数据结构在C虚拟处理器中的表示

2c5c553b53a442a8808657ce00ed1ceepng

顺序存储： 把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的相邻关系来体现。

链式存储： 逻辑上相邻的元素在物理位置上可以不相邻，借助元素存储地址的指针来表示元素之间的逻辑关系。

索引存储： 在存储信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是<Key,Addr>

散列存储： 根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储。

数据运算

施加在数据上的运算包括运算的定义和实现，运算的定义是指针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

数据类型

数据类型：（Data Type）一个值的集合和定义在这个值集上的一组操作的总称。

高级程序语言中的数据类型：

原子型：不可分解
结构型：
- 可分解
- 由若干成分按照某种结构组成
- 可以是结构的，也可以是非结构的

抽象数据类型： （Abstract Data Type 简称ADT）一个数学模型以及定义在该模型上的一组操作。抽象数据类型和数据类型实质上是一个概念。

例如：
整型

不同处理器上实现的方法可以不同
数学特性相同
在用户看来都是相同的

抽象的意义在于数据类型的数学抽象特性

原子类型： 变量的值是不可分解的。
固定聚合类型： 值由确定数目的成分按照某种结构组成，如：复数，由两个数依确定的次序关系构成。
可变聚合类型： 值的成分数目不确定

抽象数据类型（D, S, P）

D：数据对象
S：D上关系集
P：D的基本操作

多数据类型： （Polymorphic data type）是指其值的成分是不确定的数据类型

※ 算法和算法分析

算法

算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列。其中每一条指令表示一个或多个操作。算法还具有下列5个重要特性。

有穷性： 一个算法必须总是（合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。
确定性： 每一条指令必须有确切的含义，不能产生二义性。在任何条件下算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
可行性： 算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
输入： 一个算法有0个或多个的输入
输出： 一个算法有一个或多个的输出

算法可以没有参数。

算法设计的要求

正确性： （correctness）算法应当满足具体问题的需求（正确反映需求）
- a. 程序不含语法错误
- b. 程序对于几组输入数据能够得出满足规格说明要求的结果
- c. 程序对于精心选择的类型，苛刻带有刁难的几组输入数据能够得出满足规格说明要求的结果。
- d. 程序对于一切合法的输入数据都能产生满足规格说明要求的结果。
可读性：（readability）算法主要是为了人的阅读与交流，其次才是机器执行。
健壮性： （robustness）当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输入结果。
效率与低存储量需求： 效率指的是算法执行的时间，执行时间短的算法效率高。存储量指的是算法执行过程中所需的最大存储空间。

算法效率的度量。

基本操作

测定运行时间
: 测定运行时间的最可靠方法就是计数对运行时间有贡献的基本操作的执行次数。运行时间与这个计数成正比。

下表中列举了一些基本操作的例子。

程序	基本操作
排序一组整数	比较两个整数
把一个文件复制到另一个文件	复制一个字节
把两个多项式相加	把两个系数相加

重要的是程序所实现的算法
: 在分析程序的运行时间时，重要的是把程序看成算法，即独立于实现它的程序设计语言的一系列步骤。

例子：多项式求值，在多项式求值中通常乘法比加法慢。因此，乘法是主导的基本操作。

输入规模

基本操作与输入规模
: 在分析一个算法的运行时间时，重要的是把基本操作的数量与输入规模关联起来，即基本操作的数量必须表示成输入规模的函数。

算法	输入规模
排序	$n$ :要排序的整数的个数
文件复制	$n$ :输入文件中的字节数量
多项式加法	$n$ :第一个多项式的次数 $m$ ：第二个多项式的次数

函数的渐近增长

假设存在两个如下两个算法 $A$ 和 $B$ 。
$A = 3n-10\\ B = 2n+10$
当n=20时， $A$ 与 $B$ 的比较次数相等。当 $n>20$ 时， $B$ 的比较次数小于 $A$ 的比较次数。即 $B$ 比 $A$ 快（这里的快指运行时间，也可以理解为执行的基本操作次数少）。

显然，在比较次数中，重要的是与 $n$ 相乘的常数，而不是加或减的常数。因此，当作为 $n$ 的函数测定运行时间时，可以忽略这些加法常数。

函数的渐近增长
: 给定两个函数 $f(x) \text{和} g(n)$ ，如果存在一个整数 $N$ ，使得对于所有的 $n>N$ ， $f(n)$ 总是比 $g(n)$ 大，那么，我们就说 $f(n)$ 的增长渐近快于 $g(n)$ 。

考虑两个执行相同任务的算法 $P$ 和 $Q$
$\begin{array}{ll} f_p(n)=4n+20\\ f_q(n)=2n^2-10 \end{array}$

$n$	$f_p$	$f_q$
5	40	40
10	60	190
20	100	790
50	220	4990

显然与 $f_p$ 相比较 $f_q$ 是在跳跃式的增长。这是因为的 $f_q$ 主导项是二次的，而 $f_p$ 的主导项只是线性的（次数为1），即使前者的乘积常数比后者的小， $f_q$ 还是比 $f_p$ 增长的快，在这种情况下，与主导项相乘的常数不重要。

$P$ 的线性运行时间与 $Q$ 的二次运行时间属于不同的级别，或不同的复杂度的阶。我们说 $Q$ 的运行时间是 $n^2$ 阶的，而 $P$ 的运行时间是 $n$ 阶的。

阶与大 $O$

在比较算法的运行时间时，重要的是确定运行时间去除了乘法常数和加法常数后的阶。有相同运行时间阶的算法被认为是处于相同的速度水平。记号 $O$ 成为大 $O$ ，是阶的一种简捷记法。因此，用 $O(n)$ 表示“阶为 $n$ ”，用 $O(n^2)$ 表示“阶为 $n^2$ ”。

大 $O$

给定两个函数 $f(n)$ 和 $g(n)$ ， $f(n)=O(g(n))$ 当且仅当存在一个常数 $c$ 使得 $c*g(n)$ 的增长渐近快于 $f(n)$ 。

假设 $f(n)=4n+20$ 且 $g(n)=n$ 。那么，对于 $c=5,c*g(n)$ 的增长渐近快于 $f(n)$ ，所以， $f(n)=4n+20=O(n)$ 。换句话说， $4n+20$ 是阶 $n$ 的（或它的阶是 $n$ ）。

推导大 $O$

用常数1取代运行时间中所有的加法常数（减法可以理解为加一个负数）。
在修改后的运行时间中，只保留最高阶项
如果最高阶项不是1，去除与这个项相乘的常数。剩下的就是大 $O$ 阶

求多项式的阶

多项式求值 $P=a_{n}x^{n}+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+...+a_{3}x^{3}+a_{2}x^{2}+a_{1}x$ ，

在多项式的计算中通常乘法比加法慢。因此，乘法是主导的基本操作。假设有一个次数为 $n$ 的多项式，并且各项系数均不为0。

常规解法
使用常规解法就必须求下列各幂的值。
$x^n,\;x^{n-1},\;x^{n+2},\;x^{n-3},\;...\;,\;x^3,\;x^2,\;x^1$
第一项执行 $n-1$ 次乘法，第二项是 $n-2$ 以此类推，执行乘法的总数是
$(n-1)+ (n-2) + (n-3) + ... + 3 + 2 + 1 = \frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2}$
除常数外，每项需要与系数的一次乘法，总共是 $n$ 次，因此总的乘法次数是
$\frac{n^2}{2} - \frac{n}{2} + n = \frac{n^2}{2} + \frac{n}{2}$

根据上面的步骤推导出大 $O$ 的阶为 $n^2$

使用霍纳法则
使用霍纳法则求值多项式，只需要进行 $n$ 此乘法即可，所以说运行时间是 $O(n)$ 。

典型运行时间的阶

典型的运行时间的阶有：常数阶、线性阶、二次阶、对数阶、三次阶、指数阶。

运行时间	阶	非正式术语
10	$O(1)$	常数
$3n+25$	$O(n)$	线性
$1.5n^2+25n-55$	$O(n^2)$	二次
$250n+10n\log{n} + 25$	$O(n\log{n})$	$en\quad log \quad en$
$3\log{n}+30$	$O(\log{n})$	对数
$10n^3+2n$	$O(n^3)$	三次
$12 * 2^n$	$O(k^n)$	指数

阶的相对顺序
$1 < \log{n} < \sqrt{n} < n < n\log{n}< n\sqrt{n}<n^2<n^3<k^n$

阶的算术运算

阶函数中的变量
: 对于出现在算法输入规模中的每一个变量，算法的运行时间的阶函数中至多有一项包含该变量。

如 $O(n + n\log{n})$ ，因为项 $n\log{n}$ 是主导项，所以应该写成 $O(n\log{n})$ ，类似的如 $O(n + n^2)$ 应写为 $O(n^2)$ 。

最坏情况与平均情况

负责度的最坏情况
: 通常，计算机科学家使用“时间复杂度”指运算时间需求，并使用“空间复杂度”指空间需求。当不用限定词地使用“复杂度”时，他们通常指时间复杂度。另外，如果他们没有特指平均情况或最坏情况，一般指的是最坏情况。

一个算法的空间需求总是小于或等于它的时间需求。

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,324评论 5赞 476
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,303评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,192评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,555评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,569评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,566评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,927评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,583评论 0赞 257
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,827评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,590评论 2赞 320
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,669评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,365评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,941评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,928评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,159评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,880评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,399评论 2赞 342