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

零 正文开始之前

  1. 优秀老师的功能:以自身过硬知识授业解惑,通过传达个人积极价值观向学生传递真、善、美的意愿,最终实现上课听课都是享受的目的。

  2. 不同标准的C语言开发环境,注释要求和变量声明有可能不一样,低端编译环境可能死板一些。

  3. 学习数据结构可以加强对C语言中指针的理解。

  4. 如果你有梦想的话,就要去捍卫它。当别人做不到的时候,他们就一定会告诉你你也不行。你不是为别人而活,所以将梦想坚持捍卫下去。

  5. 疯子是有思想的标志。

  6. 数据具有逻辑结构和存储结构。

  7. 前人的智慧。媳妇熬成婆。

  8. 书包不是人,当然排队无效,用书包或书本占位或者排队纯属想不劳而获。

  9. 舒适的环境是很难培养出坚强品格,被安排好的人生,也很难做出伟大事业。

  10. 璇玑图(回文诗的千古力作)

  11. You got a dream,you gotta protect it.People can’t do something themselves,they wanna tell you you can’t do it.If you want something ,go get it .Period.

  12. if you give someone a program, you will frustrate them for a day; if you teach them how to program, you will frustrate them for a lifetime.

一 数据结构绪论

1.学习数据结构可以加强对C语言中指针的理解。

2.数据具有逻辑结构和物理结构(存储结构)。

3.数据的定义(符号): 描述客观事物的符号,是计算机中可操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。

4.数据元素:是组成数据的、有一定意义的基本单位,在计算机中通常作为整体处理。也被称为记录。

5.数据的类型: 数值类型:整型、实型等(可进行数值计算); 非数值类型:字符(非数值处理);声音、图像、视频(编码手段变成字符数据处理)等。

6.数据元素可以有若干个数据项。数据对象是指具有相同性质的数据元素的集合。实际问题中数据元素是数据结构中建立数据模型的着眼点。

7.数据结构的定义: 是相互之间存在一种或多种特定关系的数据元素的集合。(数据元素间的特定关系就是结构——数据的组织形式的定义)

8.逻辑结构(数据对象中数据元素的关系,面向问题):

集合:各数据元素之间平等;
线性:各数据元素之间一对一;
树形:各数据元素之间一对多的层次关系;
图形:各数据元素之间多对多。

9.物理结构(数据的逻辑结构在计算机中的存储形式,面向计算机): PS:内部存储器指内存,内存是数据机构中数据元素存放的地方。而硬盘、光盘等外部存储器的数据组织通常是以文件结构来描述。 顺序存储结构:数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的。 链式存储结构:数据元素存放在任意的存储单元里,这组存储单元可连续可不连续。数据元素的存储关系并不能反映其逻辑关系,因此需要用一个指针存放数据元素的地址,这样通过地址就可以找到相关联数据元素的位置了。

10.数据类型:是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。(为满足不同需要催生的)

11.C语言按照取值不同数据类型分2类: 1_原子类型:不可再分解的基本类型,包括整形、实型、字符型等; 2_结构类型:由若干个类型组合而成,可再分解。如整形数组是由若干整形数据组成的。

12.抽象是指抽取事物具有的普遍性的本质(忽略非本质的,提取达成目的所必需的信息)。

13.抽象数据类型(Abstract Data Type):指一个数学模型及定义在该模型上的一组操作。

二 算法

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

15.溢出:定义或声明的数据类型长度不够满足实际数据的长度导致的后果。

16.算法的五个基本特性:输入、输出、有穷性、确定性和可行性。 1_输入输出:算法具有0个或多个输入、至少有一个或多个输出; 2_有穷性:指算法在执行有限的步骤之后,自动结束而不会出现无限循环,并且每一个步骤在可接受的时间内完成; 3_确定性:算法的每一个步骤都具有确定的含义,不会出现二义性。 4_可行性:算法的每一步都必须是可行的,也就是说每一步都能通过执行有限次数完成。

17.算法的设计要求:正确性、可读性、健壮性、时间效率高和存储量低。 1_正确性:指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案 (算法的正确性在大部分情况下都不可能用程序来证明,而是用数学方法证明的。) 1_1算法正确性在用法上的四个层次: 1_1_1算法程序没有语法错误; (要求最低 – “满足温饱不算幸福生活”) 1_1_2算法程序对于合法的输入数据能够产生满足要求的输出结果; 1_1_3算法程序对于非法的输入数据能够得出满足规格说明的结果; (此为算法是否正确的标准) 1_1_4算法程序对于精心选择的,甚至刁难的测试数据都有满足要求的输出结果。 (几乎不可能逐一:验证所有的输入都得到正确的结果) 2_健壮性:当输入数据不合法时,算法也能做出相关处理,而不是产生异常或莫名奇妙的结果。 3_时间效率高和存储量低: 时间效率指算法的执行时间(越短越高),存储量需求指算法在执行过程中需要的最大存储空间(要求少)

18.算法效率的度量方法: 1_事后统计:主要是通过设计好的测试程序和数据,利用计算机即时器对不同算法编制的程序的运行时间进行比较,从而确定算法效率的高低。 缺陷:事先编好未知好坏的程序浪费时间精力、计算机软硬件的环境因素有时会掩盖算法本身的优劣、算法的测试数据设计困难(测试数据的规模有影响) 2_事前分析估算:在计算机程序编制前,依据统计方法对算法进行估算。

19.高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素: 1_算法采用的策略、方法; (算法好坏的根本) 2_编译产生的代码质量; (由软件支撑) 3_问题的输入规模; (问题的输入规模是指输入量的多少) 4_机器执行指令的速度。 (需要看硬件性能)

20.算法独立于程序设计语言之外。

20.事前估算方法的理论依据:某个算法,随着N()的增大,他会越来越优于另一算法或越来越差于另一算法。

21.算法的时间复杂度(推导需要熟悉数学的数列相关知识) – 估算算法时间效率。

22.利用算法分析工具改进自己的代码。(此章节未仔细看)

三 线性表

23.线性表:零个或多个数据元素的有限序列。(要是相同类型的数据所构成的有限序列)

24.计算机处理的对象都是有限的,那种无限的数列,只存在与数学的概念中。

25.在较复杂的线性表中,一个数据元素可以由若干个数据项组成。

26.顺序存储结构的三个属性: 1_存储空间的起始位置:数组data,它的存储位置就是存储空间的存储位置。 2_线性表的最大存储容量:数组长度MaxSize。 3_线性表的当前长度:length。

27.数组长度和线性表长度的区别: 数组长度是存放线性表的存储空间的长度,存储分配后这个量一般是不变的。(高级语言可以编程实现动态分配数组,不过会带来性能上的损耗) 线性表的长度是线性表中数据元素的个数,随着线性表插入和删除操作的进行,这个量是变化的。 任何时刻,线性表的长度应该小于等于数组的长度。

28.线性表的第i个元素是要存储在数组下标为i-1的位置。(数组从0计数,线性表从1开始)。

29.存储器的每个存储单元都有自己的编号,这个编号称为地址。

30.线性表的链式存储结构:用一组任意的未被占用的存储单元存储线性表的数据元素(可连续可不连续)。

31.链式结构与顺序结构的区别:顺序结构中每个数据元素只存储数据元素,而链式结构中,除存储数据元素的信息外,还要存储它的后继元素的 存储地址。

32.结点(Node,数据元素ai的存储映像)由两部分组成: 1_数据域:把存储数据元素信息的域称为数据域。 2_指针域:把存储直接后继位置的域称为指针域,指针域中存储的信息称作指针(地址)或链

33.n个结点链结成一个链表,即为线性表(a1,a2,…,an)的链式存储结构。因为此链表的每个结点中只包含一个指针域,所以叫单链表。 单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起的。

34.头指针:链表中第一个结点的存储位置叫做头指针。整个链表的存取都必须从头指针开始进行。 空指针(NULL/^):线性链表的最后一个结点指针。 头结点:单链表的第一个结点前附设一个结点。(为了更方便的对链表进行操作)头结点的数据域可以不存储任何信息,也可以存储如 线性表的长度等附加信息,头结点的指针域存储指向第一个结点的指针。

35.很多算法常用技术:工作指针后移。(因为单链表中没有定义表长所以不知道要循环多少次)

36.与指针相关的C语言的标准函数 malloc:生成新结点;free:回收结点释放内存。

37.单链表的插入和删除算法都由两部分组成:1_遍历查找第i个元素; 2_插入和删除元素。

38.对于插入和删除数据越频繁的操作,单链表的效率优势就越明显。(经过算法分析后与顺序存储结构对比可得此结论)

39.顺序存储结构的创建,其实就是一个数组的初始化,即声明一个类型和大小的数组并赋值的过程。而单链表不像顺序存储结构那么集中,它属于 一种动态结构。对于每个链表来说,它所占用的空间大小和位置是不需要预先分配划定的,可以根据系统的情况和实际的需求即时生成。所以, 创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态起,依次建立个元素结点,并逐个插入链表。

40.如何选择顺序结构和链式结构: 1_若线性表需要频繁查找,很少插入和删除时,最好采用顺序存储结构。若需要频繁插入和删除时,最好采用单链表结构。 2_当线性表中的元素个数变化比较大或者根本不知道有多大时,最好采用单链表结构(不需要考虑存储空间的大小问题)。如果事先知道线性表的大致长度,最好选择顺序结构。

41.C语言因为具有指针能力,所有它可以非常容易地操作内存中的地址和数据。

42.静态链表(用数组描述的链表,也叫游标实现法):让数组的元素都是由2个数组域组成(data和cur)。数组域data存放数据元素,游标cur相 当于单链表中的指针,存放该元素的后继在数组中的下标。

43.静态链表中,数组的第一个和最后一个元素不存数据。并把未被使用的数组元素称为备用链表。注意将数组建立大一些以防止溢出。

44.静态链表如何辨明数组中那些分量未被使用: 将所有未被使用过的及已被删除的分量用游标链成一个备用的链表,每当进行插入时,便可以从备用链表上取得第一个结点作为带插入的新结点。

45.静态链表中插入的特点:不移动元素却插入了数据。(详见page99)

46.静态链表其实是为了给没有指针的高级语言设计的一种实现单链表能力的方法,应理解其巧妙的思考方式,以备不时之需。

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

48.循环链表和单链表的主要差异在于循环的判断条件上,原来是判断p -> next是否为空,现在是p - next 不等于头结点则循环未结束。

49.双向链表(double linked list):在单链表的每个结点中,再设置一个指向其前驱结点的指针域。即双向链表由两个指针域,一个指向直接后继另一个指向直接前驱。它具有对称性,使对某个结点的前后结点的操作带来了方便,可以有效提高算法的时间性能(也就是用空间换时间)

四 栈与队列

50.栈(stack):限定仅在表尾(栈顶)进行插入(push)和删除(pop)操作的线性表。(last in ,first out。导致了栈底始终是固定的,最先进栈的只能在栈底) 栈顶–把允许插入和删除的一端称为栈顶 栈底–不含任何数据元素的栈称为空栈 进栈(压栈、入栈)–栈的插入操作 出栈(弹栈)–栈的删除操作 队列(queue):只允许在一端进行插入操作、而在另一端进行删除操作的线性表。(first in ,first out)

51.最先进栈的元素不一定最后出栈。栈对线性表的插入和删除的位置进行了限制,并没有对元素的进出时间进行限制。即在不是所有元素都进栈 的情况下,事先进去的元素也可以出栈,只要保证是栈顶元素出栈就可以。

52.栈的顺序存储结构中,因为首元素都存在栈底,变化量最小,所以下标为0的一端作为栈底比较好。若用top表示栈顶元素在数组中的位置,top=0则栈存在一个元素,若top=-1则此为空栈。

53.在两栈空间共享中,有一个前提是:这两个要是具有相同数据类型的栈。有一个特点是:能这样共享一般都是这两个栈的空间需求是相反关系时,也就是一个站增长时另一个栈在缩短的情况。

54.栈的链式存储结构(链栈):通常,链栈不需要头结点,基本上不存在栈满的情况,除非内存已经没有可以使用的空间(那时的计算操作系统已经面临司机崩溃的情况了)。 空栈其实就是top=NULL的时候。

55.如何选择栈的顺式结构和链式结构:如果栈的使用过程元素不可预料,最好使用链栈;如果它的变化在可控的范围内最好使用顺序栈会更好。

56.栈的作用:简化程序设计的问题。划分了不同关注层次使得思考范围缩小,更加聚焦于我们要解决的问题问题核心。

57.栈的应用:递归(像中像–经典问题—斐波那契数列实现(兔子繁殖问题))。 递归:在高级语言中,调用自己和其他函数没有本质的区别。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数称为,递归函数。

58.每个递归定义必须至少有一个条件,满足时递归停止,即不再引用自身而是返回值退出。

59.递归和迭代的区别:迭代使用的是循环结构,递归使用的是选择结构。递归能使程序的结构更清晰、简洁、更容易让人理解,从而减少读懂代码的时间。但是大量的递归会调用会建立函数的副本,会耗费大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。

60.递归和栈的关系:在前行阶段,对于每一层递归,函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段,位于栈顶的局部变量、参数值和返回地址被弹出,用于返回调用层次中执行代码的其余部分,也就是恢复了调用的状态。

61.中缀表达式转化为后缀表达式的规则: 从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级,是右括号 或优先级低于栈顶符号(乘除优先加减)则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最终输出后缀表达式为止。

62.假溢出:因为数组末尾元素已经占用,再向后加就会产生数组越界的错误。

63.循环队列:把队列的这种首尾相连的顺序存储结构称为循环队列。

64.链队列:队列的链式存储结构,即线性表的单链表只不过它只能尾进头出而已。同时,将队头指针指向链队列的头结点,而队尾指针指向终端结点。

五 串(String)

65.串:由零个或多个字符组成的有限序列,又名字符串。

66.ASCII与Unicode:ASCII是计算机中的常用字符,经历了7(128个符)、8(256个字符)位二进制数表示字符。Unicode编码足够表示世界上所有语言的所有字符常用的unicode是由16(约65W多个字符)位的二进制数表示一个字符。为了和ASCII兼容,unicode的前256个字符与ASCII码完全相同。

67.串和线性表的异同:两者的逻辑结构相似,不过串针对的是字符集,线性表的是单个元素。不同之处在于两者的操作。线性表更关注单个元素的操作, 比如查找、插入、删除等。串更多的是查找字串位置、得到指定位置子串、替换子串等。

68.用不同的高级语言操作字符串的时候,需要先查看它的参考手册关于字符串的基本操作有哪些。(不同语言除方法名称外操作实质都是类似的)。

69.串的顺序存储结构:用一组地址连续的存储单元来存储串中的字符序列。一般是用定长数组来定义串。

70.串值的存储空间可在程序执行过程中动态分配而得。(堆–计算机中存在的一个自由存储区,C语言中可以由malloc()和free()来管理)。

71.串的链式存储结构:与线性表类似。最后个结点若是未被占满时,可以用“#”或其他非串值字符补全。除了在连接串和串操作时有一定的方便外,总的所来不如顺序存储灵活,性能也不如顺序存储结构好。

72.串的模式匹配:子串的定位操作。算是串中最重要的操作之一。

73.KMP及其改进算法【过段时间仔细看】

六 树

74.Tree:树是n(n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中: (1)有且仅有一个特定的称为根(root)的结点; (2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1、T2、……、Tm,其中每一个集合本身又是一棵树,并称为根的子树(SubTree)。

75.结点的度(Degree):结点拥有的子树数。度为0的结点称为叶结点(Leaf)或终端结点;不为0的结点称为非终端结点或分支结点(内部结点–根节点除外)。树的度是树内各节点的度中的最大值。

76.结点件关系:孩子(child)、双亲(parent)–父母同体、兄弟(sibling)。

77.存储结构的设计是一个非常灵活的过程。一个存储结构设计得是否合理,取决于基于该存储结构的运算是否适合、是否方便,时间复杂度好不好。

78.多重链表表示法:每个结点有多个指针域,其中每个指针指向一个子树的根结点的方法。

79.孩子表示法:把每个结点的孩子结点排列起来,以单链表作存储结构,则n个结点有n个孩子链表,如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表,采用顺序结构,存放进一个一位数组中。

80.孩子兄弟表示法:任意一棵树,它的结点的第一个孩子如果存在就是唯一的,他的右兄弟如果存在也是唯一的。因此,我们设置两个指针,分别指向该结点的第一个孩子和此结点的兄弟。

81.二叉树(Binary Tree):n(n>=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

七 图

82.邻接表:数组和链表相结合的存储方式。

八 查找

  1. 数据结构的最终目的是提高数据的处理速度。

本文最后修改时间: 2015-08-01 19:22:32 +0000 (完) CC BY-NC-ND 3.0

若您发现文章中的错误,并愿告知于我,或想与我交流,我的联系方式在: Contacts


上一篇 CentOS7 搭建 LANMP

All The Best

下一篇 关于 "全栈"