06数据结构讲义

1、1.3.2 算法的比较现在我们需要写一个求 1 + 2 + 3 + + 100 的结果程序，你应该怎么写呢？大多数人可以马上写出下面 go 语言代码实现（或者其他语言）但是，如果这个问题让来去做，他可能会写如下代码：很显然，不论是从人类还是计算机的角度来看，上述算法效率会高出很多。因此，一个好的算让你的程序更加高效。1.3.3算法的分类1.分治（分布治理）：有明确的目标，明确的执行方式。一般采用 拆分、解决小问题、合并的流程来加以实现。2.最短路径：有明确的目标，需要找寻有效的执行方式。3.贪婪（贪心）：没有明确的目标，没有有效的执行方式。需要现场分析，获取目标，找寻执行方式。1.3.4算法的

2、特性算法具备五个基本特性：输入、输出、有穷性、确定性和可行性1.输入、输出：算法具有零或多个输入，至少有一或多个输出。2.有穷性：算法在执行有限步骤后，自动结束而无限循环。且每一步在可接受时间内完成。3.确定性：算法的每一步骤都有明确的含义，出现二义性。4.可行性：算法的每一步都必须是可行的。即，每一步都能通过执行有限次数完成。2sum := 0n := 100sum = (1+n)*n/2 fmt.Printf(%d,sum)var i int sum := 0n := 100for i = 0; i next = current-next; current-next = node;2.3.

3、2 优点和缺点 优点：n无需定制链表的容量n和删除操作无需移动数据元素 缺点：n数据元素必须保存后继元素的位置信息n获取指定数据的元素操作需要顺序之前的元素3.栈与队列3.1 栈(Stack)3.1.1 栈的基本概念 概念：首先，栈是一个线性表。也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。通常描述栈，说性表的表尾进行和删除操作，这里表尾是指栈顶，而不是栈底。 特性13current-next = ret-next;栈的特殊之处在于限制了线性表和删除，始终在栈顶进行。这使得：栈底是固定的，最先进栈的数据只能在栈底。 操作n 栈的操作，叫做进栈或压栈。类似入（如下

4、图所示）n 栈的删除操作，叫做出栈或弾栈、退栈。如同中的出夹（如下图所示）3.1.2 栈的链式 基本概念栈的链式结构简称链栈。思考如下问题：栈只是栈顶来做和删除操作，栈顶放在链表的头部还是尾部呢？由于单链表有头指针，而栈顶指针也是必须的，那干嘛不让他俩合二为一呢，所以比较好的办法就是把栈顶放在单链表的头部。另外都已经有了栈顶在头部了，单链表中比较常用的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。 设计与实现链栈是一种特殊的线性表，链栈可以通过链式线性表来实现。3.2 队列(Queue)3.2.1 队列基本概念队列（queue）是一种特殊的受限线性表。只在一端进行14，在另一端进行

5、删除操作。采用先进先出的（First In First Out）的原则，简称 FIFO。的一端为队尾，删除的一端为队头。队列不在中间部位进行操作！假设队列是 q=（a1，a2，an），那么 a1 就是队头元素，而 an 是队尾元素。这样我们就可以删除时，总是从 a1 开始，而时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。如下图：3.2.2 队列的链式队列也是一种特殊的线性表；可以用线性表链式来模拟队列的链式。154.二4.1 树的基本概念树的定义：由一个或多个(n0)结点组成的有限集合 T，有且仅有一个结点称为根（root），当 n1 时

6、，其余的结点分为m(m0)个互不相交的有限集合 T1,T2，Tm。每个集合本身又是棵树，被称作这个根的子树。树的结构特点n 非线性结构，有一个直接前驱，但可能有多个直接后继（1:n）n 树的定义具有递归性，还有树。n 树可以为空，即节点个数为 0。若干术语n 根 即根结点(没有前驱)n 叶子 即终端结点(没有后继)n 森林 指m 棵不相交的树的集合(例如删除 A 后的子树个数)n 有序树 结点各子树从有序，不能互换（第一）n 无序树 结点各子树可互换位置。n 双亲 即上层的那个结点(直接前驱) parentn 孩子 即下层结点的子树 (直接后继) child16兄弟 同一双亲下的同层结点（孩子

7、之间互称兄弟）siblingn堂兄弟 即双亲位于同一层的结点（但并非同一双亲）cousinn祖先 即从根到该结点所经分支的所有结点n子孙 即该结点下层子的任一结点n结点 即树的数据元素n结点的度 结点挂接的子树数（有几个直接后继就是几度）n结点的层次 从根到该结点的层数（根结点算第一层）n终端结点 即度为 0 的结点，即叶子n分支结点 除树根以外的结点（也称为内部结点）n树的度 所有结点度中的最大值（Max各结点的度）n树的深度(或高度) 指所有结点中最大的层数（Max各结点的层次）n下图(c)中的结点数 10，树的度 3，树的深度 34.2 树的表示法4.2.1 图形表示法事物之间的逻辑关系

8、可以通过数的形式很直观的表示出来，如下图：174.2.2 广义表表示法用广义表表示法表示上图：中国（河北（保定，石家庄），（广州，东莞），山东（青岛，济南）根作为由子树森林组成的表的名字写在表的左边。184.2.3右兄弟表示法右兄弟表示法可以将一颗多转化为一颗二：节点的结构：节点有两个指针域，其中一个指针点，另一个指针指向其兄弟节点。4.3 二概念4.3.1 二基本概念 定义：二（binary tree）是 n（n0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二组成 。 基本特征:19n 每个结点最多只有两棵子树（不存在度大于 2 的结点）；n 左子右子树次序不

9、能颠倒（有序树）。 基本形态:l 二性质性质 1:若根节点的层次为 1，则二第 i 层上至多有 2i-1 个结点（i0）n性质 2:在高度为 k 的二中，最多有 2k-1 个结点（k0）。n 满二一棵深度为 k 且有 2k -1 个结点的二。特点：每层都“充满”了结点 完全二除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。20理解：k-1 层与满二完全相同，第 k 层结点尽力靠左对完全二，若从上至下、从编号，则编号为 i 的结点，其编号必为 2i，其右孩子编号必为 2i1；其双亲的编号必为 i/2（i1, 除外）使用此性质，可以将完全二实现树的顺序。如果不是完全二

10、怎么办呢? 可将其转换成完全二后，再做。21但缺点也较明显：浪费空间、删除不便。4.3.2 二的表示二主要采用链式结构，顺序结构仅适用于完全二和满二，还有静态链表。 二的顺序结构 二的链式结构二的链式结构主要有二叉链表和三叉链表两种。二叉链表n二叉链表的节点结构如下：22n 结点数据类型定义：4.3.3 二的遍历遍历定义指按某条搜索路线遍访每个结点且不重复（又称周游）。遍历用途它是树结构、删除、修改、查找和排序运算的前提，是二一切运算的基础和。遍历方法牢记一种约定，对每个结点的查看都是“先左后右” 。限定先左后右，树的遍历有三种实现方案：DLRLDRLRD先 (根)序遍历中 (根)序遍历后(根

11、)序遍历n DLR先序遍历，即先根再n LDR中序遍历，即先左再根再右n LRD后序遍历，即先再根23type BinaryNode struct Ch byteLChild *BinaryNode RChild *BinaryNode注：“先、中、后”的意思是指的结点 D 是先于子树出现还是后于子树出现。从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的路径是相同的，只是结点的时机不同。从虚线的出发点到终点的路径上，每个结点经过 3 次。n 第 1 次经过时先序遍历n 第 2 次经过时中序遍历n 第 3 次经过时后序遍历5.排序算法5.1 排序基本概念现实生活中排序很重要，例如：

12、淘宝按条件搜索的结果展示等。l 概念排序是计算机内经常进行的一种操作，其目的是将一组“无序”的数据元素调整为“有序”的数据元素。l 排序数学定义：假设含 n 个数据元素的序列为 R1, R2, , Rn，其相应的关键字序列为 K1, K2, , Kn这些关键字相互之间24可以进行比较，即在它们之间存在着这样一个关系 ：Kp1Kp2Kpn按此固有关系将上式序列重新排列为 Rp1, Rp2, ，Rpn的操作称作排序排序的稳定性l如果在序列中有两个数据元素 ri和 r j，它们的关键字 ki = k j，且在排序之前，对象 ri排在 r j前面。如果在排序之后，对象 ri仍在 r j前面，则称这个排

13、序方法是稳定的，否则称这个排序方法是不稳定的。排序中的关键操作ln 比较：任意两个数据元素通过比较操作确定先后次序。n 交换：数据元间需要交换才能得到预期结果。内排序和外排序ln 内排序：在排序过，待排序的所有全部都放置在内存中，排序分为：内排序和外排序。n 外排序：由于排序的个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。排序的审判ln 时间性能：关键性能差异体现在比较和交换的数量n 辅助空间：为完成排序操作需要的额外的空间，必要时可以“空间换时间”n 算法的实现复杂性：过于复杂的排序影响代码的可读性和可维护性，也可能影响排序的性能总结l25n 排序是数据元素

14、从无序到有序的过程n 排序具有稳定性，是选择排序算法的因一n 比较和交换是排序的基本操作n 多关键字排序与单关键字排序无本质区别n 排序的时间性能是区分排序算法好坏的主要因素5.2 大 O 表示法在编，同一个编程问题，十个程序员可能会写出十种不同的程序，算法各不相同，却能解决同样的问题。程序员对算法的效率十分在乎，尽管无论算法效率高度都能解决问题，但效率高的算法除了能够解决问题，还可以在问题规模变大变复杂的时候高效的解决问题。那么众多解决同样问题的算法，我们如何去评价这些算法，从什么角度去评价这些算法呢？评价算法时，应该结合数据量来评价，当数据量增大时，算法所消耗的时间变化趋势。在计算机世界，

15、这种粗略的评价方式称为“大 O 表示法”。算法的执行时间一般是最主要的评价标准。然而存在一个问题，不同的编程语言，不同的编译器，或不同的CPU 等因素将导致执行一次操作的时间各不相同，这样的结果会使算法的比较产生歧义，于是我们假定所有计算机执行一次相同的基本操作所需要的时间是相同的，而把算法中最基本操作的最大次数作为量度。也就是说我们把算法的执行时间简单的用基本操作的执行次数来代替了。基本操作是什么？它可以是基本的运算，赋值，比较，交换。当要处理的数据，基本操作要重复执行的次数必定会增长，那么我们关心的是这个执行次数是以什么样的数量级增长。这个所谓的数量级被称为算法的渐进时间复杂度。如何分析这

16、个数量级呢？由于基本操作的执行次数是问题规模 n 的一个函数 T(n),所以问题就是要确定这个函数 T(n)是什么？然后分析它的数量级，O 是数量级的标记。怎么一个算法的效率？（规则如下）26一个算法的效率时，往往只需要关注操作数量的最高次项，其他次要常数项可以忽略。ll 在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度l 只有常数项记做 1l 操作数量的估算，可以作为时间复杂度的估算总结：u 只关注最高次项u 时间复杂度是指最坏时间复杂度u 只有常数项记做 1常见的时间复杂度n 常见的时间复杂度之间的关系27执行次数函数阶非正式术语12O(1)常数阶2n+3O(n)线性阶3

17、n2+2n+1O(n2)平方阶5log2n+20O(logn)对数阶2n+3nlog2n+19O(nlogn)nlogn 阶6n3+2n2+3n+4O(n3)立方阶2nO(2n)指数阶常用的时间复杂度所耗费的时间从小到大依次是：5.2.1 简单练习28/ 时间复杂度:/ 空间复杂度:func sum1(n int) int var i intsum := 0for i = 0; i = n; i+ sum = sum + ifmt.Printf(%d, sum) return sum/ 时间复杂度:/ 空间复杂度:func sum2(n int) int sum := 0n = 100sum

18、= (1+n)*n/2 fmt.Printf(%d,sum) return sumO(1) O(logn) O(n) O(nlogn) O(n2) O(n3) O(2n) O(n!) O(nn)5.3 常见排序算法5.3.1 冒泡排序冒泡排序（bubble sort）的基本思想：比较相邻两个元素的关键字值，如果反序，则交换。 冒泡总结：29/ 时间复杂度:/ 空间复杂度:func test1(n int) var count int = 1 for count n count = count * 2/ 时间复杂度:/ 空间复杂度:func test2(n int) var i, j intfo

19、r i = 0; i n; i+ for j = i; j n; j+ fmt.Println(i + j)n 冒泡排序是一种效率低下的排序方法，在数据规模很小时，可以采用。数据规模比较大时，最好用其它排序方法。n 冒泡排序算法的平均时间复杂度一般为 O(n2 )，算法的空 间复杂度为 O(1)。 冒泡排序算法是稳定的。5.3.2 选择排序直接选择排序（straight select sort）的基本思想：第一趟从 n 个元素的数据序列中选出关键字最小（或最大）的元素并放到最前（或最后）位置，下一趟再从 n-1 个元素中选出最小（大）的元素并放到次前（后）位置，以此类推，经过 n-1 趟完成排

20、序。1.直接选择排序算法描述2.直接选择排序算法分析直接选择排序的比较次数为n(n -1)n-1n2C = (n - i) =22i=1直接选择排序算法的时间复杂度为 O(n2 )，算法的空间复杂度为 O(1)。 直接选择排序算法是不稳定的。5.3.3排序排序算法是一种简单的排序算法，也称为直接排序算法。它是一种稳定的排序算法，对局部有序的数据具有较高的效率。30排序算法是一个队少量元素进行排序的有效算法。比如，是我们使用排序方法最多的日常生活例子。我们在摸牌时，一般会重复一下步骤。期初，我们手里没有牌，摸出第一张，随意放在左手上，以后每一次摸排，都会按照花色从小到大排列，直到所有的牌摸完。排

21、序算法采用的类似思路，每一次从无序序列中拿出一个数据，将它放到已排序的序序列的正确位置，如此重复，直到所有的无序序列中的数据都找到了正确位置。315.3.4排序排序（shell sort）又称缩小增量排序，它的基本思想：分组的直接排序。1、排序算法描述：322、排序算法分析排序算法实际所需的时间取决于具体的增量序列， 所以它的时间复杂度分析比较复杂， 一般为O(n(log2n)2 ) ，算法的空间复杂度为 O(1)。排序算法不稳定。5.3.5 快速排序快速排序（quick sort）是一种分区交换排序算法，它的基本思想：在数据序列中选择一个值作为比较的基准值， 每趟从数据序列的两端开始交替进行，将小于基准值的元素交换到序列前端，将大于基准值的元素交换到序列后端， 介于两者之间的位置则成为基准值的最终位置。1.快速排序算法描述：33上述数据序列的快速排序（升序）过程如下图所示。2.快速排序算法分析快速排序算法的平均时间复杂度为 O(nlog2n)，算法的平均空间复杂度为 O(log2n)。快速排序算法不稳定。345.3.6 堆排序堆排序