C语言课件-数据结构与算法

第1章数据结构与算法1.1算法1.2数据结构的根本概念1.3线性表及其顺序存储结构1.4栈和队列1.5线性链表1.6树和二叉树1.7查找技术1.8排序技术算法的根本概念算法的复杂度分析1.1算法算法的根本概念通俗的定义：算法是指解题方案的准确而完整的描述。算法的根本特征1.可行性2.确定性3.有穷性4.拥有足够的情报算法的严格定义： 算法是一组严谨地定义运算顺序的规那么，并且每一个规那么都是有效的，且是明确的，此顺序将在有限的次数下终止。算法的根本要素(1)算法中对数据的运算和操作①算术运算②逻辑运算③关系运算④数据传输(2)算法的控制结构传统流程图、N-S结构化流程图、算法描述语言等。算法设计根本方法1.列举法 根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。 因此，列举法常用于解决“是否存在”或“有多少种可能”等类型的问题，例如求解不定方程的问题。例：设每只母鸡值3元，每只公鸡值2元，两只小鸡值1元。现要用100元钱买100只鸡，设计买鸡方案。假设买母鸡I只，公鸡J只，小鸡K只。2.归纳法通过列举少量的特殊情况，经过分析，最后找出一般的关系。3.递推从的初始条件出发，逐次推出所要求的各中间结果和最后结果。4.递归将一个复杂的问题归结为假设干个较简单的问题，然后将这些较简单的每一个问题再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为止。5.减半递推技术所谓“减半”，是指将问题的规模减半，而问题的性质不变。所谓“递推”，是指重复“减半”的过程。例：二分法求方程实根6.回溯法通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，假设试探成功，就得到问题的解，假设试探失败，就逐步回退，换别的路线再进行试探。例：迷宫问题算法的复杂度分析算法的时间复杂度算法的空间复杂度执行算法所需要的内存空间。1.2数据结构的根本概念什么是数据结构数据结构的图形表示线性数据结构与非线性数据结构目的：提高数据处理的效率提高数据处理的速度尽量节省计算机存储空间数据结构三个方面的问题：(1)数据的逻辑结构(2)数据的存储结构(3)对各种数据结构进行的运算什么是数据结构数据结构是指相互有关联的数据元素集合。现实世界中客观存在的一切个体都可以是数据元素。描述一年四季的季节名春，夏，秋，冬可以作为季节的数据元素；表示数值的各个数18，11，35，23，16，…可以作为数值的数据元素；前后件关系前后件关系(也称为直接前驱和直接后继)是数据元素之间的自然存在的一个根本关系，但前后件关系所表示的实际意义是随具体对象的不同而不同。一般来说，数据元素之间的任何关系都可以用前后件关系来描述。数据的逻辑结构一个数据结构应包含两方面的信息〔1〕表示数据元素的信息；〔2〕表示各数据元素之间的前后件关系〔即逻辑关系〕数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构有两个要素：数据元素的集合D；反映D中各数据元素之间的前后件关系R。数据的逻辑结构数据结构可以表示成B＝〔D，R〕其中B表示数据结构。为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。设a与b是D中的两个数据，那么二元组〔a，b〕表示a是b的前件，b是a的后件。数据的逻辑结构例如B＝〔D，R〕D＝{春，夏，秋，冬}R＝{(春，夏)，(夏，秋)，(秋，冬)}家庭成员数据结构B＝〔D，R〕D＝{父亲，儿子，女儿}R＝{(父亲，儿子〕，(父亲，女儿〕}数据的存储结构〔数据的物理结构〕数据的逻辑结构在计算机存储空间中的存放形式。各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的，而且一般也不可能相同。常用的存储结构有：顺序、链接、索引等存储结构。采用不同的存储结构，其数据处理的效率是不同的。数据结构的图形表示数据集合D中的每一个数据元素用中间标有元素值的方框表示〔数据结点，结点〕用一条有向线段从前件结点指向后件结点。如:一年四季数据结构的图形表示

家庭成员间辈份关系数据结的图形表示用图形表示数据结构B＝〔D，R〕D＝{di|1≤i≤7}＝{d1，d2，d3，d4，d5，d6，d7}R＝{(d1，d3)，(d1，d7)，(d2，d4)，(d3，d6)，(d4，d5)}对数据结构的运算根本运算：插入和删除其他运算：查找、分类、合并、分解、复制和修改等。数据结构的处理过程中，不仅结点的个数在动态地变化，而且各数据元素之间的关系也有可能在动态地变化。线性数据结构与非线性数据结构线性结构：〔1〕有且只有一个根结点；〔2〕每一个结点最多有一个前件，也最多有一个后件。线性结构又称线性表。如果一个数据结构不是线性结构，那么称之为非线性结构不是线性结构的数据结构特例

提示:在一个线性结构中插入或删除任何一个结点后还应是线性结构空数据结构

1.3线性表及其顺序存储结构什么是线性表线性表的顺序存储结构线性表在顺序存储下的插入运算线性表在顺序存储下的删除运算什么是线性表n维向量(x1，x2，…，xn)是一个长度为n的线性表英文小写字母表(a，b，c，…，z)是一个长度为26的线性表一年中的四个季节(春，夏，秋，冬)是一个长度为4的线性表矩阵是一个比较复杂的线性表学生情况登记表是一个复杂的线性表什么是线性表(定义〕线性表是由n(n≥0)个数据元素a1，a2，…，an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为(a1，a2，…，ai，…，an)其中ai(i＝1，2，…，n)是属于数据对象的元素，通常也称其为线性表中的一个结点。非空线性表结构特征(1)有且只有一个根结点a1，它无前件；(2)有且只有一个终端结点an，它无后件；(3)除根结点与终端结点外，其它所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n＝0时，称为空表。线性表的顺序存储结构线性表的顺序存储结构根本特点：(1)线性表中所有元素所占的存储空间是连续的；(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。线性表中第i个元素ai在计算机存储空间中的存储地址为ADR(ai)＝ADR(a1)＋(i－1)k长度为n的线性表(a1，a2，…，ai，…，an)

顺序存储结构整型一维数组存放长度为8的线性表

(29,18,56,63,35,24,31,47)顺序存储结构下线性表的运算：插入删除查找排序分解合并复制逆转原那么：运算后仍保持线性表的特性线性表在顺序存储下的插入运算线性表在顺序存储下的删除运算1.4栈和队列栈及其根本运算队列及其根本运算栈及其根本运算什么是栈栈的顺序存储及其运算栈(stack)是限定在一端进行插入与删除的线性表。允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈是按照“先进后出”(FILO—FirstInLastOut)或“后进先出”(LIFO—LastInFirstOut)的原那么组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。栈具有记忆作用。用指针top来指示栈顶的位置，用指针bottom指向栈底。往栈中插入一个元素称为入栈运算，从栈中删除一个元素(即删除栈顶元素)称为退栈运算。如：主程序与子程序之间的调用关系什么是栈栈的顺序存储及其运算top＝0表示栈空；top＝m表示栈满(1)入栈运算〔上溢〕(2)退栈运算〔下溢〕(3)读栈顶元素〔不删除栈顶元素〕栈的顺序存储及其运算队列及其根本运算什么是队列循环队列队列(equeue)是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾，用尾指针(rear)指向队尾元素。允许删除的一端称为排头(也称队头)，用排头指针(front)指向排头元素的前一个位置。队列又称为“先进先出”(FIFO—FirstInFirstOut)或“后进后出”(LILO—LastInLastOut)的线性表，表达了“先来先效劳”的原那么。往队列的队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。什么是队列队列根本运算循环队列及其运算循环队列及其运算循环队列的初始状态为空，即rear=front=m入队运算：队尾指针进1，当队尾指针rear=m+1时，那么置rear=1。退队运算：排头指针进1，当排头指针front=m+1时，那么置front=1队列空的条件为s＝0〔下溢〕队列满的条件为(s＝1)且front＝rear〔上溢〕1.5线性链表什么是线性表线性链表的根本运算循环链表顺序存储线性表的缺点：插入上溢共享1.线性链表线性表的链式存储结构称为线性链表。线性链表的根本概念头结点：指向线性表中第一个结点的指针HEAD称为头指针，当HEAD=NULL(或0〕时称为空表。线性单链表只能顺指针向链尾方向进行扫描。双向链表带链的栈带链的队列线性链表的插入在链式存储结构下的线性表中插入一个新元素。线性链表的根本运算(1)从可利用栈取得一个结点，设该结点号为p。并置结点p的数据域为插入的元素值b，即V(p)＝b。(2)在线性链表中寻找包含元素x的前一个结点q。(3)将结点p插入到结点q之后：①使结点p指向包含元素x的结点，即NEXT(p)＝NEXT(q)②使结点q的指针域内容改为指向结点p，即NEXT(q)＝p线性链表的删除链式存储结构下的线性表中删除包含指定元素的结点。(1)寻找包含元素x的前一个结点q。那么包含元素x的结点序号p＝NEXT(q)。(2)将结点q后的结点p删除，即NEXT(q)＝NEXT(p)。(3)将包含元素x的结点p送回可利用栈。(1)在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点。(2)空表与非空表的运算统一。循环链表循环链表的优势：通过任何一个结点都可以访问到其他任意结点增加了表头结点，使得空表与非空表的运算统一。树与二叉树树的根本概念二叉树及其根本性质二叉树的存储结构二叉树的遍历树是由n(n0)个结点组成的有限集合。如果n=0，称为空树；如果n>0，那么:有一个特定的称之为根的结点，它只有后继，但没有前驱；除根以外的其它结点划分为m(m0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合本身又是一棵树，并且称之为根的子树。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个后继。什么是树？1〕度〔次数、级〕〔1〕结点的度：一个结点所拥有的子树的个数〔2〕树的度：树内各结点的度的最大值2〕描述上下及左右的关系孩子结点：一个结点的子树的根双亲结点：结点的直接前驱〔前件〕兄弟结点：同一个双亲的孩子之间互称兄弟祖先：结点的祖先是从根到该结点所经分支上的所有结点子孙：结点的后代3〕层次〔1〕结点的层次〔2〕树的深度〔高度〕树的根本术语结点(node)结点的度(degree)分支(branch)结点叶(leaf)结点孩子(child)结点双亲(parent)结点兄弟(sibling)结点祖先(ancestor)结点子孙(descendant)结点结点所处层次(level)树的深度(depth)树的度(degree)(1)表达式中的每一个运算符在树中对应一个结点，称为运算符结点。(2)运算符的每一个运算对象在树中为该运算符结点的子树〔在树中的顺序为从左到右〕。(3)运算对象中的单变量均为叶子结点。表达式树a*(b＋c/d)＋e*h－g*f(s，t，x＋y)a*(b＋c/d)＋e*h－g*f(s，t，x＋y)注：树在计算机中通常用多重链表表示。

(1)非空二叉树只有一个根结点；(2)每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。什么是二叉树性质1在二叉树的第k层上，最多有2k－1(k≥1)个结点。性质2深度为m的二叉树最多有2m－1个结点。性质3在任意一棵二叉树中，度为0的结点〔即叶子结点〕总是比度为2的结点多一个。性质4具有n个结点的二叉树，其深度至少为[log2n]＋1其中[log2n]表示取log2n的整数局部。二叉树的根本性质满二叉树完全二叉树假设设二叉树的深度为h，那么共有h层。除第h层外，其它各层(0h-1)的结点数都到达最大个数，第h层从右向左连续缺假设干结点，这就是完全二叉树。性质5具有n个结点的完全二叉树的深度为[log2n]＋1。性质6设完全二叉树共有n个结点。如果从根结点开始，按层序〔每一层从左到右〕用自然数1，2，…，n给结点进行编号，那么对于编号为k(k＝1，2，…，n)的结点有以下结论：(1)假设k＝1，那么该结点为根结点，它没有父结点；假设k＞1，那么该结点的父结点编号为INT(k/2)。(2)假设2k≤n，那么编号为k的结点的左子结点编号为2k；否那么该结点无左子结点〔显然也没有右子结点〕。(3)假设2k＋1≤n，那么编号为k的结点的右子结点编号为2k＋1；否那么该结点无右子结点。二叉链表

二叉树的存储结构〔链表存储和顺序存储〕1.前序遍历(DLR)假设二叉树为空，那么结束返回。否那么：(1)访问根结点；(2)前序遍历左子树；(3)前序遍历右子树。2.中序遍历(LDR)假设二叉树为空，那么结束返回。否那么：(1)中序遍历左子树；(2)访问根结点；(3)中序遍历左子树。3.后序遍历(LRD)假设二叉树为空，那么结束返回。否那么：(1)后序遍历左子树；(2)后序遍历左子树；(3)访问根结点。二叉树的遍历二叉树的遍历例题〔1〕二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是A〕acbedB〕decabC〕deabcD〕cedba

〔2〕一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，那么该二叉树的后序遍历为A〕GEDHFBCAB〕DGEBHFCAC〕ABCDEFGHD〕ACBFEDHG1.7查找技术顺序查找二分法查找(1)如果线性表为无序表〔即表中元素的排列是无序的〕，那么不管是顺序存储结构还是链式存储结构，都只能用顺序查找。(2)即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。(3)最坏情况时间复杂度为n。顺序查找设有序线性表的长度为n，被查元素为x。将x与线性表的中间项进行比较：假设中间项的值等于x，那么说明查到，查找结束；假设x小于中间项的值，那么在线性表的前半局部〔即中间项以前的局部〕以相同的方法进行查找；假设x大于中间项的值，那么在线性表的后半局部〔即中间项以后的局部〕以相同的方法进行查找。这个过程一直进行到查找成功或子表长度为0(说明线性表中没有这个元素)为止。在最坏情况下，对分查找只需比较log2n次，而顺序查找需比较n次。二分法查找1.8排序技术交换类排序插入类排序选择类排序首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。假设相邻两个元素中，前面的元素大于后面的元素，那么将它们互换，称之为消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后。然后从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。假设相邻两个元素中，后面的元素小于前面的元素，那么将它们互换，这样就又消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的小者往前移动，最后就将剩下线性表中的最小者换到了表的最前。对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有序。最坏情况下的时间复杂度为n(n-1)/2.冒泡排序快速排序首先，在表的第一个、中间一个与最后一个元素中选取中项，设为P(k)，并将P(k)赋给T，再将表中的第一个元素移到P(k)的位置上。然后设置两个指针i和j分别指向表的起始与最后的位置。反复作以下两步：(1)将j逐渐减小，并逐次比较P(j)与T，直到发现一个P(j)＜T为止，将P(j)移到P(i)的位置上。(2)将i逐渐增大，并逐次比较P(i)与T，直到发现一个P(i)＞T为止，将P(i)移到P(j)的位置上。上述两个操作交替进行，直到指针i与j指向同一个位置〔即i＝j〕为止，此时将T移到P(i)的位置上。简单插入排序51731694286

↑j＝215731694286

↑j＝315731694286

↑j＝413571694286

↑j＝511357694286

↑j＝6

11356794286

↑j＝711356794286

↑j＝81