《大话数据结构》读书笔记

阅读时，摘抄是非常好的习惯。“最淡的墨水也胜于最强的记忆！"有不少读者会认为摘抄了将来也不会再去看，有什么必要，但其实在写字的过程就是大脑学习的过程，写字在减缓你阅读的速度，从而让你更好地消化阅读的内容。相信大家都能理解，“囫囵吞枣"和“慢慢品味”的差异，学习同样如此。

image

大话数据结构

★★★★☆7.9

程杰 / 2011 / 清华大学出版社

程序 = 数据结构 + 算法

第一章 数据结构绪论

1.4.1 数据

数据：是描述客观事物的符号，是计算机中可操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。

1.4.2 数据元素

数据元素：是组成数据的，有一定意义的基本单位，在计算机中通常作为整理处理，也被成为记录。

1.4.3 数据项

数据项：一个数据可以由若干个数据项组成；

数据项是数据不可分割的最小单位

1.4.4 数据对象

数据对象：是性质相同的数据元素的集合，是数据的子集。

1.4.5 数据结构

数据结构：是相互之间存在一种或多种特定关系的数据元素集合

在计算机中，数据元素并不是孤立、杂乱无序的，而是具有内在联系的数据集合。数据元素之间存在的一种或多种特定关系，也就是数据的组织形式。

1.5 逻辑结构与物理结构

1.5.1 逻辑结构

1. 集合结构

集合结构：集合结构中的数据元素除了同属于一个集合外，没有其他关系。

[](javascript:;)[](javascript:;)[](javascript:;)

[删除](javascript:;) image

[集合结构](javascript:;)

2. 线性结构

线性结构：线性结构中的数据元素是一对一的关系

[](javascript:;)[](javascript:;)[](javascript:;)

[删除](javascript:;) image

[线性结构](javascript:;)

3. 树形结构

树形结构：树形结构中的数据元素之间存在一种一对多的层次关系

[](javascript:;)[](javascript:;)[](javascript:;)

[删除](javascript:;) image

[树形结构](javascript:;)

4. 图形结构

图形结构: 图形结构的数据元素是多对多的关系

[](javascript:;)[](javascript:;)[](javascript:;)

[删除](javascript:;) image

[图形结构](javascript:;)

1.5.2 物理结构

物理结构：是指数据的逻辑结构在计算机中的存储形式。

1. 顺序存储结构

开辟一段连续的空间，依次按顺序存放数据元素。

[](javascript:;)[](javascript:;)[](javascript:;)

[删除](javascript:;) image

[顺序存储结构](javascript:;)

2. 链式存储结构

现在如银行、医院等地方，设置了排队系统，也就是每个人去了，先领一个号，等着叫号，叫到时去办理业务或看病。在等待的时候，你爱在哪在哪，可以坐着、站着或者走动，甚至出去逛一圈，只要及时回来就行。你关注的是前一个号有没有被叫到，叫到了，下一个就轮到了。

[](javascript:;)[](javascript:;)[](javascript:;)

[删除](javascript:;) image

[链式存储结构](javascript:;)

1.6 抽象数据类型

1.6.1

事实上，抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。抽象数据类型把实际生活中的问题分解为多个规模小且容易处理的问题，然后建立一个计算机能处理的数据模型，并把每个功能模块的实现细节作为一个独立的单元，从而使具体实现过程隐藏起来。

第一章总结

[](javascript:;)[](javascript:;)[](javascript:;)

[删除](javascript:;) image

[数据](javascript:;)

第二章 算法

算法：算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

为了解决某个或某类问题，需要把指令表示成一定的操作序列，操作序列包括一组操作，每一个操作都完成特定的功能，这就是算法了。

算法具有五个基本特性：输人、输出、有穷性、确定性和可行性。

算法时间复杂度定义

在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况并确定T（n）的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T（n）=O(f(n))0它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f（n）是问题规模n的某个函数。

常见的时间复杂度

[](javascript:;)[](javascript:;)[](javascript:;)

[删除](javascript:;) image

[(选填) 图片描述](javascript:;)

记住logN > 1； 2^n < n! < n^n 就好理解了;

第二章总结

算法的定义：算法是解决特定问题求解步骤的描述，在计算机中为指令的有限序列，并且每条指令表示一个或多个操作。

算法的特性：有穷性、确定性、可行性、输人、输出。

算法的设计的要求：正确性、可读性、健壮性、高效率和低存储量需求。

算法特性与算法设计容易混，需要对比记忆。

算法的度量方法：事后统计方法（不科学、不准确）、事前分析估算方法。在讲解如何用事前分析估算方法之前，我们先给出了函数渐近增长的定义。函数的渐近增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n>N，f〔n〕总是比g〔n)大，那么，我们说f〔n)的增长渐近快于g〔n)。于是我们可以得出一个结论，判断一个算法好不好，我们只通过少量的数据是不能做出准确判断的，如果我们可以对比算法的关键执行次数函数的渐近增长性，基本就可以分析出：

某个算法，随着n的变大，它会越来越优于另一算法，或者越来越差于另一算法。

第三章 线性表

线性表： 零个或多个数据元素的有限序列

[](javascript:;)[](javascript:;)[](javascript:;)

[删除](javascript:;) image

[(选填) 图片描述](javascript:;)

Data

线性表的数据对象集合为{ai，a2，...，a。}，每个元素的类型均为DataTypeo其中，除第一个元素外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

Operation

InitList（(L)：初始化操作，建立一个空的线性表L

ListEmpty（L）：若线性表为空，返回true，否则返回false.

ClearList（*L）· 将线性表清空。

GetEIem(L,i,*e）· 将线性表中的第i个位置元素值返回给e。

LocateElem（L, e）：在线性表L中查找与給定值e相等的元素，如果查找成功，该元素在表中序号表 示成功；否则，返回0表示失败。

ListInsert(*L, i，e）：在线性表L中的第个位置插入新元素

ListDeIete（*L，i，*e)：删除线性表中第土个位置元素，并用e返回其值返回

ListLength（L）：返回线性表L的元素个数。

• 数组的长度是存放线性表的存储空间的长度，存储分配后这个量是一般是不变的。

• 线性表的长度是线性表中数据元素的个数，随着线性表插人和删除操作的进行，这个量是变化的。

• 在任意时刻，线性表的长度应该小于等于数组的长度。

• 所以对于第i个数据元素ai的存储位置可以有a1推算得出：

LOC(ai) = LOC（a1） + (i - 1) *c

[](javascript:;)[](javascript:;)[](javascript:;)

[删除](javascript:;) image

[(选填) 图片描述](javascript:;)

单链表

[](javascript:;)[](javascript:;)[](javascript:;)

[删除](javascript:;) image

[(选填) 图片描述](javascript:;)

单链表结构和顺序存储结构

存储分配方式

● 顺序存储结构用一段连续的存储单元一次存储依次存储线性表的数据元素

● 单链表采用链式存储结构，用一组任意的存储单元存性表的元素

时间性能

● 查找

● 顺序存储结构 O(1)

● 单链表O(n)

● 插入和删除

● 顺序存储结构需要平均移动表长一般的元素，时间为O(n)

● 单链表在线出某位置的指针后，插入和删除时间仅为O(1)

● 空间性能

● 顺序存储结构需要预分配存储空间，不好控制。

● 单链表不需要预分配存储空间，只要有空间就可以分配，元素个数不受限制

若线性表需要频繁查找，很少进行插人和删除操作时，宜采用顺序存储结构。若需要频繁插人和删除时，宜采用单链表结构.当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度，比如一年12个月，一周就是垡期一至星期日共七天，这种用顺序存储结构效率会高很多。

静态链表

首先我们让数组的元素都是由两个数据域组成，山和也就是说，数组的每个下标都对应一个山忪和一个curo数据域山，用来存放数据元素，也就是通常我们要处理的数据；而游标cur相当于单链表中的next指针，存放该元素的后继在数组中的下标。我们把这种用数组描述的链表叫做静态链表，这种描述方法还有起名叫做游标实现法。

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表（circular linked list)。

[](javascript:;)[](javascript:;)[](javascript:;)

[删除](javascript:;) image

[(选填) 图片描述](javascript:;)

双向链表

[](javascript:;)[](javascript:;)[](javascript:;)

[删除](javascript:;) image

[(选填) 图片描述](javascript:;)

第三章 总结

这章主要讲线性表，线性表是另个或多个具有相同类型数据元素的有限序列。

然后是线性表的一些基本操作。后面是线性表的两大结构：顺序存储结构和链式存储结构

[](javascript:;)[](javascript:;)[](javascript:;)

[删除](javascript:;) image

[(选填) 图片描述](javascript:;)

第四章 栈与队列

4.2 栈的定义

栈(stack)是限定仅在表尾进行插入和删除的线性表

[](javascript:;)[](javascript:;)[](javascript:;)

[删除](javascript:;) image

[(选填) 图片描述](javascript:;)

两个栈共享空间

[](javascript:;)[](javascript:;)[](javascript:;)

[删除](javascript:;) image

[(选填) 图片描述](javascript:;)

想想极端的情况，若栈2是空栈，栈1的topl等于n一1时，就是栈1满了。反之，当栈1为空栈时，top2等于0时，为栈2满。但更多的情况，两个栈见面之时，也就是两个指针之间相差1时，即topl+1==top2为栈满。

4.6 栈的链式存储结构及实现

[](javascript:;)[](javascript:;)[](javascript:;)

[删除](javascript:;) image

[(选填) 图片描述](javascript:;)

栈的引人简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦于我们要解决的问题核心。反之，像数组等，因为要分散精力去考虑数组的下标增减等细节问题，反而掩盖了问题的本质。

4.8 栈的递归

[](javascript:;)[](javascript:;)[](javascript:;)

[删除](javascript:;) image

[(选填) 图片描述](javascript:;)

递归函数： 在高级语言中，调用自己和其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。

当然，写递归程序最怕的就是陷人永不结束的无穷递归中，所以，每个递归定义必须至少有一个条件满足时递归不再进行，即不在引用自身，而是以返回值退出。

4.10 队列

队列（queue）是只允许在一段进行插入，在另一端进行删除的线性表。

先进先出（First In First Out）与醒了

[](javascript:;)[](javascript:;)[](javascript:;)

[删除](javascript:;) image

[(选填) 图片描述](javascript:;)

4.12.2 循环队列定义

所以解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。