搜索
基本数据结构与算法算法的基本概念算法是解题方案的准确而完整的描述，它是指令的有限序列。其中每一条指令表示一个或多个操作。它是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。算法不同于程序，程序是算法的一种表示形式，它受到计算机系统等很多细节问题限制，一般地，程序的编制不可能优于算法。算法具有有穷性、确定性、可行性、输入和输出（拥有足够的情报）等５个重要特性。算法的基本要素1、对数据对象的运算和操作•算术运算•逻辑运算•关系运算•数据传输2、算法的控制结构一个算法一般可以用顺序、选择、循环三种基本结构组合而成。3、算法设计基本方法列举法、归纳法、递推、递归、减半递推技术、回溯法算法复杂度•时间复杂度–指执行算法所需要的基本计算工作量，为了客观的反映算法的效率，可以用算法执行过程中所需基本运算的重复次数来度量算法的工作量。时间复杂度=f(n)——n是问题的规模平均时间复杂度A(n)=∑p(x)t(x)最坏情况复杂度W(n)=max{t(x)}•算法的空间复杂度–一般是指执行这个算法所需要的内存空间数据结构的基本概念•数据结构：相互之间存在特定关系的数据集合•数据的逻辑结构：数据元素的信息、各数据元素之间的前后件关系•数据的存储（物理）结构：数据的逻辑结构在计算机存储空间中的存放形式线性树图数据结构的图形表示•图形表示数据元素由结点表示，用从前件指向后件的有向线段表示。没有前件的结点称为根结点，没有后件的结点称为叶子结点。女儿儿子父亲春夏秋冬线性结构与非线性结构一般将数据结构分为两种类型：（1）线性结构如果一个非空的数据结构满足下列二个条件：1）有且只有一个根结点2）每个结点最多有一个前件和一个后件包括线性表、队列、堆栈（2）非线性结构如果一个数据结构不是线性的，则称非线性的包括树和图线性表及其特点•线性表是一种线性结构，元素在线性表中的位置仅取决于自己的序号。线性表中结点的个数n称为表的长度。当n=0时，称作空表。•线性表的特点：1.线性表中所有元素的性质相同。2.除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前驱和一个后继。3.有且只有一个根结点和一个终端结点，第一个数据结点无前驱，最后一个数据结点无后继。线性表的顺序存储结构1、线性表中数据元素类型一致，只有数据域，存储空间利用率高。2、所有元素所占的存储空间是连续的3、各数据元素在存储空间中是按逻辑顺序依次存放的元素an……..元素ai……..元素a2元素a1bb+mb+(i-1)*mb+(maxlen-1)*m存储地址内存状态m为每个元素占用的存储单元数起始地址插入与删除运算122018259642723555122018259642723555插入运算删除运算1220259642723555原始数据插入结果删除结果栈和队列•栈和队列是两种特殊的线性表栈：限定只能在表的一端进行插入和删除的特殊的线性表,此种结构称为后进先出栈顶（top)：允许插入和删除的一端；约定top始终指向新数据元素将存放的位置。栈底（bottom):不允许插入和删除的一端。a1a2….an进栈出栈栈顶栈底栈的基本运算基本运算：压(进)栈：PUSH——插入top=top+1出栈：POP——删除top=top-1设置一个简单变量top指示栈顶位置，称为栈顶指针，它始终指向待插入元素的位置。ACBtopPUSHXACBXtopACBtopPOPX队列队列：限定只能在表的一端进行插入，在表的另一端进行删除的线性表。此种结构称为先进先出（FIFO）队尾rear只允许插入，队头front只允许删除a1,a2,a3,a4,…………an-1,an队列示意图队头front队尾rear队列基本运算ABCrearfront入队运算rear=rear+1ABCrearfrontDBCrearfrontD出队运算front=front+1循环队列rearfrontABC……线性链表•将线性表的元素放到一个具有头指针的链表中，链表中每个结点包含数据域和指针域•数据域存放数据，指针域存放后继结点的地址，最后一个结点的指针域为空。逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻双向链表与循环链表线性双链表：每个结点设置两个指针，左指针指向其前件，右指针指向其后件循环链表：最后一个结点的指针域不为空，而是指向表头结点datanextbefore00…………HEAD…..表头a1a2a4HEAD单链表的插入运算•生成新结点•新结点的指针S指向后一个结点S.next=P.next•前一个结点的指针P指向新结点P.next=SbabaxPPS单链表的删除运算要删除P的后继结点，则让P的指针指向P的后继的后继P.next=P.next.next然后释放被删除结点单链表的查找从表头开始顺次向后查找，直到找到需要的元素ai-1aiai+1P树的基本概念•树是一种简单的非线性结构。在这种结构中，所有数据元素之间的关系具有明显的层次特性。+-*de/fg*a+bc*a+bc-e*d/fg+父结点根结点子结点叶子结点结点的度树的度树的深度子树计算机中，用树结构表示表达式a*(b+c)+d*e-f/g二叉树及其基本性质二叉树是具有以下两个特点的树：（1）非空二叉树只有一个根结点（2）每一个结点最多有两棵子树，且分别称为该结点的左子树和右子树在二叉树中每一个结点的度的最大为2二叉树的基本性质性质1在二叉树的第k层上，最多有2(k-1)个结点性质2深度为m的二叉树最多有2m-1个结点423167891011121314155性质3在任意一棵二叉树中，度为0的结点（叶子结点）总比度为2的结点多一个。n0+n1+n2=1+n1+2*n2例：一棵二叉树有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数是多少？（13）性质4具有n个结点的二叉树，其深度至少为[log2n]+1423165满二叉树与完全二叉树满二叉树：除叶子结点外，所有结点都有两个子结点。在二叉树的第k层上，有2^(k-1)个结点深度为m的二叉树有2^m-1个结点例在深度为5的满二叉树中，叶子结点的个数是多少？结点数是多少？（16，31）完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若于结点特点：如果从根结点出发，对二叉树的结点自上而下、自左而右进行编号，则其编号是与满二叉树的编号相一致的•满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。123455123467123456满二叉树完全二叉树非完全二叉树性质5具有n个结点的完全二叉树，其深度为[log2n]+1性质6为结点数n的完全二叉树编号，则对于编号为k的结点有以下结论：（1）若k=1，则该结点为根结点（2）若k1，则该结点的父结点编号为INT(k/2)（3）编号为k的结点的左子结点编号为2k（若2k=n），其右子结点编号为2k+1（若2k+1=n）423167891011121314155例一个完全二叉树共有739个结点，则该树有多少个叶子结点？（370）提示：叶子结点出现在层次最大的两层，可推导出公式：叶子结点数=INT（(结点总数+1)/2）•顺序存储完全二叉树，则很容易确定每一个结点的父结点、左子结点、右子结点的存储位置。二叉树的存储结构•二叉树通常采用链式存储结构，称为二叉链表。对于满二叉树和完全二叉树可以采用顺序存储。10E0239B0453A86780C190D010BTABCDE二叉链表的存储状态二叉链表的逻辑状态LchildValueRchild二叉树结点结构二叉树的遍历二叉树的遍历是指不重复地访问二叉树中的所有结点。原则：先遍历左子树，后遍历右子树三种不同的方法：根据访问根结点的次序，二叉树的遍历可以分为前序遍历、中序遍历、后序遍历。前序遍历：访问根结点——前序遍历左子树——前序遍历右子树中序遍历：中序遍历左子树——访问根结点——中序遍历右子树后序遍历：后序遍历左子树——后序遍历右子树——访问根结点树的遍历是一个递归过程例如下的二叉树，它的前序遍历是什么？中序遍历是什么？后序遍历是什么？前序遍历FCADBEGHP中序遍历ACBDFEHGP后序遍历ABDCHPGEFFCEADBHPG练习：一棵二叉树的中序遍历为DBEAFC，前序遍历是ABDECF，则后序遍历是什么？查找技术•所谓查找是指在一个给定的数据结构中查找某个指定的元素•顺序查找就是从线性表的第一个元素开始，依次将线性表中的元素与所查元素进行比较顺序查找的最好情况：线性中的第一个元素就是被查找元素——只需1次比较顺序查找的最坏情况：线性中的最后一个元素就是被查找元素——需比较N次顺序查找的平均情况：N/2次在下面两种情况下只能采取顺序查找：a.线性表为无序表（元素排列是无序的）；b.即使是有序线性表，但采用的是链式存储结构。折半查找(二分法查找)•思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。•前提：必须在具有顺序存储结构的有序表中进行。•分三种情况：1）若中间项的值等于x,则说明已查到。2）若x小于中间项的值，则在线性表的前半部分查找；3）若x大于中间项的值，则在线性表的后半部分查找。•特点：比顺序查找方法效率高。最坏的情况下，需要比较log2n次。利用折半查找查找23的过程如下图：(08,14,23,37,46,55,68,79,91)lowhighmid(08,14,23,37,46,55,68,79,91)lowhigh=mid-1mid(08,14,23,37,46,55,68,79,91)low=mid+1highmidmid=(low+high)/2不进位取整(123456789)排序技术•排序的功能：将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列•我们只讨论顺序存储的线性表的排序方法排序方法插入排序选择排序交换排序直接插入排序O(n2)希尔排序简单选择排序O(n2)堆排序起泡排序O(n2)快速排序交换排序•冒泡排序（起泡排序）思想：小的浮起，大的沉底。4936416511783665364156364165413641561178363641491156492525251149495611111125252525排序n个记录的文件最多需要n-1趟冒泡排序快速排序•思想：通过一趟排序将待排序列分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分排序，以达到整个序列有序快速排序过程示意图：key初始序列235266718lowhigh一次交换185266723lowhigh二次交换182366752三次交换[186]23[6752]//完成一趟排序后分别进行快速排序插入排序简单插入排序所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中待排元素序列：[53]2736156942第一次排序：[2753]36156942第二次排序：[273653]156942第三次排序：[15273653]6942第四次排序：[1527365369]42第五次排序：[152736425369]希尔排序•基本思想如下：将整个序列分割成基于小的子序列，分别进行插入排序•将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完成。最坏情况O(n1.5)49386597761327h=3h=22738134976659713273849657697选择类排序法简单选择排序法基本思想如下：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面，然后对剩下的子表采用同样的方法，直到子表为空为止初态83916839168391683916ijkijkijkijk互换第一趟13986堆排序是具有特定条件的顺序存储的完全二叉树，其特定条件是：任何一个非叶子结点的关键字大于等于（或小于等于）子女的关键字的值。112536497856堆顶元素为最小值最坏情况O(n*log2n)