*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第1章 基本数据结构与算法,1.1 算法,算法的概念,算法复杂度,1.,算法的基本概念,算法是指解题方案的准确而完整的描述,.,作为一个算法,一般具有的特征为,:,可行性,:,针对实际问题设计的算法,考虑其可行性,能够得到满意的结果,.,确定性,:,算法中的每一个步骤都必须是明确定义的,不允许有摸棱两可的解释,也不允许有多义性,.,有穷性,:,算法必须能执行有限个步骤之后终止,.,有零个或多个输入,有一个或多个输入,综上所述,算法是一个严谨地定义运算顺序的规则,并且每一个规则都是有效的、明确的，此顺序将在有限的次数终止。,重要知识点,2.算法复杂度,算法的复杂度主要包括时间复杂度和空间复杂度。,1）算法的时间复杂度,算法的时间复杂度是指执行算法所需要的工作量。算法的工作量用算法执行的基本运算次数来度量。,2）算法的空间复杂度,算法的空间复杂度是指执行这个算法所需要的内存空间。,1.2 数据结构的基本概念,1.数据结构的定义,数据结构是指反映数据元素之间关系的数据元素的表示。通俗的讲，数据结构是指带有结构的数据元素的集合。,（1）数据的逻辑结构,数据的逻辑结构是反映数据元素之间的逻辑关系的数据结构。,一个数据结构应包含以下方面的信息：,1）表示数据元素的信息,2）表示各元素之间的前后件关系,（2）数据的存储结构,数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也叫数据的物理结构）,一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等。而采用不同的存储结构，其数据处理的效率是不同的，因此，在进行数据处理时，选择合适的存储结构是很重要的。,2.数据结构的图形表示,一个数据结构除了用二元关系表示外，还可以用直观的图形表示。在数据结构的图形表示中，对于数据集合中的每一个数据元素用中间标有值的方法方框表示，一般称为数据结点，并简称为结点。为了进一步表示个数据元素之间的前后关系，对于关系中的每一个元组，用一条有向线段从前件结点指向后件接点。,3.线性结构与非线性结构,根据数据结构中各元素之间的前后件关系的复杂程度，一般将数据结构分成两大类型：线性结构和非线性结构。,如果一个非空的数据结构满足以下条件：,1）有且仅有一个根结点,2）每一个结点最多有一个前件，也最多有一个后件。,则称为该数据结构为线性结构。线性结构又称线性表。如果一个数据结构不是线性结构，就称之为非线性结构。,1.3线性表及其顺序存储结构,1.线性表的基本概念,线性表是由n(n=0)个数据元素a,1,a,2,a,3,a,n,组成的一个有限序列,表中的每一个数据元素，除了第一个外，有且仅有一个前件，有且仅有一个后件，或者可以表示为（a,1,a,2,a,3,a,n）。,其中a,1,a,2,a,3,a,n,是数据元素，通常也称为线性表的结点。,2.线性表的顺序存储结构,线性表的顺序存储结构具有以下基本特点：,（1）线性表中所有元素所占的存储空间是连续的。,（2）线性表中各元素在存储空间中是按逻辑顺序依次存放的。,由此可以看出，在线性表的顺序存储结构中，其前后件两个元素在存放空间中是紧邻的，且前件元素一定存储在后件元素的后面。,3.线性表的插入、删除运算,1.4 栈和队列,栈及其基本运算,队列及其基本运算,1.,栈,(Stack),只允许在一端插入和删除的顺序表,允许插入和删除的一端称为,栈顶,(,top,),，另一端称为,栈底,(,bottom,),特点,后进先出,(LIFO),栈的基本运算有三种：入栈、出栈和读栈顶元素,重要知识点,定义,队列是只允许在一端删除，在另一端插入的顺序表,允许删除的一端叫做队头(,front,)，允许插入的一端叫做队尾(,rear,)。,特性,先进先出(,FIFO,First In First Out,),向队列的队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。,2.队列及其基本运算,(,Queue),队列的进队和出队,进队时队尾指针先进一,rear=rear,+1,，,再将新元素按,rear,指示位置加入。,出队时队头指针先进一,front=front,+1,，,再将下标为,front,的,元素取出。,队满时再进队将溢出出错；队空时再出队将队空处理。,定义,将队列的存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。,队列初始化：,front（队头指针）,=,rear（队尾指针）,=0;,队空条件：,front,=,rear,;,循环队列中元素个数=,rear-,front,循环队列,(Circular Queue),循环队列的进队和出队,1.5 线性链表,一种物理存储上,非连续、非顺序,的线性存储结构，数据元素间的逻辑顺序是通过链表中的指针链接次序实现的。,1.线性表的基本概念,线性表的链式存储结构称为线性链表。线性链表分为单链表、双向链表和循环链表三种类型。,为了适应线性表的链式存储结构,计算机存储空间被划分为一个个小块，每一小块占若干字节,通常称这些小块为存储结点。,为了存储线性表中的每一个元素,一方面要存储数据元素的值,另一方面要存储各数据元素之间的前后件关系。为此,节点构成：,数据域指针域,数据域,存储数据元素的值,；指针域,存放下一个数据元素的存储序号（即存储结点的地址），即指向后件结点。,h,不带头节点的链表,h,带头节点的链表,1.单链表,只有,一个方向,的指针域的链表叫单链表。,带头结点的单链表,在单链表中，增加头结点的目的是：为了运算方便,三、循环单链表,循环单链表的定义,循环单链表是单链表的另一种形式,其特点是链表中最后一个结点的指针不再是空的,而是指向头结点或第一个结点,整个链表形成一个环。从表中任一个结点出发，都可找到表中其它结点。,一个带头结点的循环单链表,空循环链表,1.6 树和二叉树,二叉树及其基本性质,二叉树的遍历,树的定义,树是由,n,(,n,0),个结点组成的,有限,集合,它是一种简单的非线性结构,具有明显的层次特性。如果,n,=0,，称为空树,.,重要知识点,b,a,c,g,d,e,f,h,i,二叉树（Binary Tree）及其基本性质,1.什么是二叉树,1,).非空二叉树只有一个根结点,2).每一个结点最多有两个子树,分别称为左子树和右,子树,结点的度:,一个结点所拥有的后件个数.,树的度:,所有结点中最大的度,树的深度:,树的最大层次,2.二叉树的基本性质,性质1,二叉树的第,i,层最多有 2,i,-1,个结点。(,i,1),性质2,深度为,k,的二叉树最多有 2,k,-1个结点。(,k,1),性质3,对任何一棵非空二叉树,如果其叶结点个数为,n,0,度为2的非叶结点个数为,n,2,则有,n,0,n,21,性质4 具有n个结点的二叉树的深度至少为,log,2,n,+1,3.满二叉树与完全二叉树,定义1,满二叉树(Full Binary Tree),在一颗二叉树中，如果所有的分支结点都存在左子树和右子树，并且所有的叶结点都在同一层上。,定义2,完全二叉树(Complete Binary Tree),除最后一层外,每一层上的结点数都达到最大值;在最后一层上只缺少右边的若干结点.,满二叉树也是完全二叉树,而完全二叉树不一定是满二叉树.,完全二叉树的性质,性质5,具有n个结点的完全二叉树的深度为,log2n,+1,性质6,如果将一棵有,n,个结点的完全二叉树自顶向下，同一层自左向右连续给结点从0开始编号1,1,2,n,，则对于编号为,i,的结点为结点,i,(i=1,2,3,n),。则有以下关系：,若,i=,1,则,i,无双亲，,根结点；,若i1,则 i 的双亲为i/2,若2,i,=,n,则 编号为,i,的结点的左孩子结点的序号为2,i；,否则该结点无左子结点(显然也没有右孩子),若2*,i,+1=,n,则 序号为,i结点,的右孩子结点的序号为2*,i,+1,否则该结点为i的结点无右孩子,二叉树的存储,在计算机中，二叉树通常采用,链表存储结构。,用于存储二叉树的各元素的存储结点也有两部分组成：,数据域和指针域,。但是使用两个指针域。如下图所示,Lchild,Data,Rchild,Data：保存结点本身信息,Lchild：指向该结点的左孩子的存储地址，称为左指针域；,Rchild:指向该结点的右孩子的存储地址，称为右指针域；,由于每个结点有两个指针域，因此形象称之为,二叉链表,。,4.,二叉树的遍历,二叉树的遍历是指不重复的访问二叉树中所有结点,。,1.中序遍（LDR）,中序遍历二叉树算法的原则,是：,若二叉树为空，则空操作；,否则,中序遍历左子树,(L),；,访问根结点,(D),；,中序遍历右子树,(R),。,对右图采用中序遍历的结果为：,ACBDFEHGP,G,F,C,D,A,E,H,B,P,2.前序遍历（DLR）,前序遍历二叉树算法的框架是,若二叉树为空，则空操作；,否则,访问根结点,(D),；,前序遍历左子树,(L),；,前序遍历右子树,(R),。,遍历结果：,FCADBEGHP,F,C,D,A,E,H,B,P,G,F,C,D,A,E,H,B,P,3.后序遍历（LRD）,后序遍历二叉树算法的框架是,若二叉树为空，则空操作；,否则,后序遍历左子树,(L),；,后序遍历右子树,(R),；,访问根结点,(,D,),。,遍历结果：,ABDCHPGEF,G,F,C,D,A,E,H,B,P,1.1.7 查找技术,所谓,查找,是指在一个给定的数据结构中查找某个指定的元素。,1.顺序查找,顺序查找是指在线性表中查找指定的元素，方法是：从线性表的第一个元素开始，依次将线性表中的元素与被查找的元素进行比较，若相等则表示找到；若线性表中的所有元素与被查找的元素不相等，则表示查找不成功。,2.二分查找,二分查找只使用于顺序存储的有序表。设线性表的长度为n，被查找的元素为x，基本思想如下：,首先将x与中点项mid=（n-1）/2进行比较。,若中间项的值等于的 x值，则查找成功，结束查找；,若 x大于中间项的值，则在线性表的后半部分以相同的方法进行查找；,若 x小于中间项的值，则在线性表的前半部分以相同的方法进行查找。,这个过程一直进行到查找成功或子表的长度为0为止。,显然，对于长度为n的有序线性表，在最坏的情况下，查找只需要比较,log,2,n次,1.8 排序,排序,：,将一组杂乱无章的数据按一定的规律顺次排列起来,1.交换排序(Exchange Sort),（1）,起泡排序(Bubble Sort),起泡排序的基本方法是：设待排序对象序列中的对象个数为 n。,首先从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中前面的元素大于后面的元素，则将它们交换，称之为消去了一个逆序，依次排序结束后，表中最大元素位于线性表末尾。,然后，从后往前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若后面的元素小于前面的元素，则将它们交换，这样又消去了一个逆序。,对剩下的线性表重复上诉过程，直到剩下的线形表变空为止，此时的先行表已经为有序。,最坏情况下，,起泡排序 需要的比较次数为n（n-1）/2,快速排序(Quick Sort),快速排序方法的基本思想是任取待排序对象序列中的某个对象(例如取第一个对象)T作为基准，将线形表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果将整个线形表序列划分为左右两个子序列：,左侧子序列中所有对象的关键码都小于或等于T的关键码,右侧子序列中所有对象的关键码都大于T的关键码,T则排在这两个子序列中间(这也是该对象最终应安放的位置)。,然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。,插入排序(Insert Sorting),插入排序的基本方法是：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上