数据结构与算法

第一章数据结构与算法

数据结构与算法全文共59页，当前为第1页。1.1算法算法的基本概念所谓算法是指解题方案的准确而完整的描述。数据结构与算法全文共59页，当前为第2页。一.算法的基本特征可行性:执行后能得到满意结果。确定性:算法中每个步骤必须明确定义，不允许多义性。有穷性:算法必须在有限时间内做完。拥有足够的情报:确保算法有效还取决于情报是否足够。数据结构与算法全文共59页，当前为第3页。二.算法的基本要素算法对数据的运算和操作：算术运算、逻辑运算、关系运算、数据传输。算法的控制结构:顺序、选择、循环数据结构与算法全文共59页，当前为第4页。四.算法复杂度算法的时间复杂度执行算法所需要的计算工作量算法的空间复杂度执行算法所需要的内存空间数据结构与算法全文共59页，当前为第5页。1.2数据结构的基本概念数据结构作为计算机的一门学科，主要研究以下三个方面的问题:P71.数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。2.在对数据进行处理时，各数据元素在计算机中在存储关系，即数据的存储结构。3.对各种数据结构进行的运算。数据结构与算法全文共59页，当前为第6页。一.数据的逻辑结构数据结构是指相互有关联的数据元素的集合。更通俗地说，数据结构是指带有结构的数据元素的集合。P11一个数据结构应包含以下两个方面的信息：元素的信息数据元素之间的前后件关系。所谓数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。前后件：前驱、后件。数据结构与算法全文共59页，当前为第7页。二.数据的存储结构

数据的逻辑结构是在计算机存储空间的存放形式称为数据的存储结构。数据结构与算法全文共59页，当前为第8页。三.数据结构的图形表示ABCDEF其中D称为是E的前件,C的后件.其他相同.父亲儿子女儿其中“父亲”是“儿子”和“女儿”的前件，“儿子”和“女儿”是“父亲”的后件。数据结构与算法全文共59页，当前为第9页。四.线性结构和非线性结构空数据结构:一个元素都没有。数据结构一般分为:线性结构和非线性结构。非空线性结构满足:有且只有一个根节点；每个节点最多有一个前件节点、也最多有一个后件节点。如果一个数据结构不是线性结构，则称之为非线性结构。数据结构与算法全文共59页，当前为第10页。1.3线性表与顺序存储结构

线性表是最简单、最常用的一种数据结构。线性表是n(n>=0)个元素构成的有限序列(a1,a2,……an)。(1)有且只有一个根结点a1,它无前件；(2)有且只有一个终端结点an,它无后件；(3)其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数称为线性表的长度,当n=0时，称为空表.数据结构与算法全文共59页，当前为第11页。一.线性表的顺序存储结构线性表在计算机中采用顺序存储。线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构具有以下两个特点:线性表中所有元素所占的存储空间是连续的。线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。数据结构与算法全文共59页，当前为第12页。二.线性表的插入运算线性表为:(a1,a2

…ai-1,ai,ai+1…an)在第i个位置之前上插入新的结点x:线性表变为:(a1,a2

…ai-1,x,ai,ai+1…an)长度变为n+1。在最好的情况下,不需要移动表中的元素。在最坏的情况下,需要移动表中的所有元素。在平均情况下,需要移动表中一半的元素。数据结构与算法全文共59页，当前为第13页。三.线性表的删除运算线性表为:(a1,a2

……ai-1,ai,ai+1……an)在第i个位置上删除新的结点ai:线性表变为:(a1,a2

……ai-1,ai+1……an)长度变为n-1。在最好的情况下,不需要移动表中的元素。在最坏的情况下,需要移动表中的所有元素。在平均情况下,需要移动表中一半的元素。数据结构与算法全文共59页，当前为第14页。1.4栈和队列1.什么是栈？栈是限定在一端进行插入和删除运算的线性表。允许插入与删除的一端称为栈顶，不允许插入与删除的一端称为栈底。假设栈s=(a1,a2,……an),则a1称为栈底元素，an成为栈顶元素。栈也称为先进后出或后进先出的线性表。数据结构与算法全文共59页，当前为第15页。1.4栈和队列anan-1…a2a1进栈退栈topbottom栈:后进先出表数据结构与算法全文共59页，当前为第16页。1.4栈和队列2.栈的顺序存储及其运算P21

栈空栈满正常dcbagfedcba进栈时会发生上溢错误退栈时会发生下溢错误数据结构与算法全文共59页，当前为第17页。1.4栈和队列1.什么是队列

队列是指只允许在一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，允许删除的一端称为队头.假设队列q=(a1,a2,……an),则a1称为队头元素，an成为队尾元素。数据结构与算法全文共59页，当前为第18页。队列(queue)的运算示意ABCD一个队列插入(入队)删除(退队)BCDABCDEfrontrearfrontfrontrearrear数据结构与算法全文共59页，当前为第19页。1.4栈和队列2.循环队列及其算法循环队列：将队列的存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。m…21frontrear数据结构与算法全文共59页，当前为第20页。1.4栈和队列frontrear123n分析可知：当front=rear时，不能确定循环队列是空还是满，于是需要要一个标记S,用来判断队列的状态:S=0

表示队列为空S=1

表示队列为非空由此得出：队列为空的条件是:s=0队列为满的条件是:s=1且front=rear数据结构与算法全文共59页，当前为第21页。1.5线性链表1.什么是链式存储？线性表顺序存储的缺点：插入删除时移动大量元素；有“上溢”情况；空间不便于动态分配。在链式存储方式中,每个结点有两部分组成:一部分用于存放数据元素的值,称为数据域；另一部分存放指针,称为指针域。在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的.数据结构与算法全文共59页，当前为第22页。2.线性单链表在线性单链表中,结点的数据域存放数据元素的值,指针域存放下一个数据元素的存储序号,即指向后件结点.V(i)Next(i)数据域指针域

数据1

数据nnull

数据2HEAD…数据结构与算法全文共59页，当前为第23页。1B1023A1456D878E910C6ABCDE1110106688数据结构与算法全文共59页，当前为第24页。3.线性双向链表在线性单链表中从一个结点只能找到它的下一个结点,但找不到前一个结点.为解决这一问题,将线性链表中每一个结点设置两个指针:左指针和右指针.这样的链表称为双向链表.00head…数据结构与算法全文共59页，当前为第25页。4.带链的栈和队列P27(1)栈也是线性表。带链的栈称为可利用栈。(2)队列也是线性表。也可以采用链式存储结构。topa10an-1an…an0a2a1…frontrear数据结构与算法全文共59页，当前为第26页。5.线性链表的基本运算插入：删除：合并：分解：逆转：复制：排序：查找：数据结构与算法全文共59页，当前为第27页。(1).在线性链表中查找指定元素在非空线性链表中寻找包含指定元素值x的前一个结点p的基本方法:从头结点指向的结点开始往后沿指针进行扫描,直到后面已没有结点或下一个结点的数据域为x为止.数据结构与算法全文共59页，当前为第28页。(2).线性链表的插入线性链表插入过程中不发生数据元素移动现象，只要改变有关结点的指针即可，提高了效率。HEAD…数据结构与算法全文共59页，当前为第29页。(3).线性链表的删除线性链表删除过程中不发生数据元素移动现象，只要改变有关结点的指针即可，提高了效率。HEAD…数据结构与算法全文共59页，当前为第30页。6.双向链表的基本运算(插入)00head…数据结构与算法全文共59页，当前为第31页。6.双向链表的基本运算(删除)00head…数据结构与算法全文共59页，当前为第32页。7.循环链表及其基本运算单链表的最后一个结点的指针域为HULL;如果将它改为存放链表中头结点的地址，这样就构成了一个环。HEAD…非空循环链表HEAD空循环链表其插入与删除操作与单链表相同数据结构与算法全文共59页，当前为第33页。1.6树与二叉树树是一种简单的非线性结构.具有层次结构。基本术语:P32父结点、根结点、子结点、叶子结点。结点的度、树的度，树的深度、子树。数据结构与算法全文共59页，当前为第34页。abcsdqwvxuverfghtpynm数据结构与算法全文共59页，当前为第35页。1.二叉树的定义非空二叉树具有以下两个特点：(1)非空二叉树只有一个根结点(2)每一个结点最多有两棵子树，且分别称为该结点的左子树和右子树。在二叉树中，每一个结点的度最大为2，即所有子树也均为二叉树。在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树，当一个结点既没有左子树也没有右子树时，该结点称为叶子结点。数据结构与算法全文共59页，当前为第36页。2.二叉树的基本性质性质1:在二叉树的第k层上至多有2K-1个结点性质2:深度为m的二叉树至多有2m-1个结点。性质3:对任意一棵二叉树，度为0的结点数总比度为2的结点数多1。(n0=n2+1)性质4:具有n个结点的完全二叉树深度至少为[log2n]+1。(性质2反推)数据结构与算法全文共59页，当前为第37页。3.满二叉树与完全二叉树满二叉树:除最后一层外,每一层上的所有结点都有两个子结点.即所有层的结点数均达到最大值.完全二叉树:除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点.数据结构与算法全文共59页，当前为第38页。3.满二叉树与完全二叉树完全二叉树还具有以下两个性质：性质5:具有n个结点的完全二叉树的深度为[log2n]+1性质6:设完全二叉树共有n个结点，如果从根结点开始，按层序用自然数1,2,3…n给结点进行编号，则对于编号为k的结点有如下特点：若k=1则该结点为要根结点。若2k<=n，则编号为k的结点，其左子树为2k,右结点为2k+1若2k+1<=n，则编号为k的结点的右子树编号为2k+1。数据结构与算法全文共59页，当前为第39页。123456789101112131415数据结构与算法全文共59页，当前为第40页。4.二叉树的存储结构在计算机中，二叉树通常采用链式存储结构。存储结点的结构:数据域,左指针域,右指针域。L(i)V(i)R(i)数据结构与算法全文共59页，当前为第41页。ABCDEFGPY数据结构与算法全文共59页，当前为第42页。5.二叉树的遍历二叉树的遍历是指不重复地访问二叉树中的所有结点.(1)前序遍历(根-左-右)(2)中序遍历(左-根-右)(3)后序遍历(左-右-根)ABCDEF数据结构与算法全文共59页，当前为第43页。前序遍历：中序遍历：后序遍历：FCEADBGHP数据结构与算法全文共59页，当前为第44页。前序遍历：中序遍历：后序遍历：ABCDEYXZF数据结构与算法全文共59页，当前为第45页。1.7查找技术所谓查找是指在一个给定的数据结构中查找某个指定的元素。1.顺序查找:从表的一端开始,顺序扫描,依次将扫描的关键字和待寻找的k值比较,若相等,则查找成功;若扫描完毕,仍未找到,则扫描失败。以下情况只能采用顺序查找:(1)线性表示无序表；(2)有序线性表采用链式存储结构平均情况下，大约要与表中一半的元素进行比较.最坏情况下，要查找n次.数据结构与算法全文共59页，当前为第46页。1.7查找技术2.二分法查找:只适用于顺序存储的有序表.设有序表的长度为n,被查元素为x,则查找方法:将x与线性表的中间项相比较；若中间项等于x,则说明查到，查找结束；若x小于中间项,则在线性表的前半部分查找;若x大于中间项,则在线性表的后半部分查找.最坏的情况下，查找log2n

次数据结构与算法全文共59页，当前为第47页。1.7查找技术8，17，25，44，68，77，98，100，115，125查找k=98一次查找后:二次查找后:midhighlow三次查找:lowmidhighlowmidhigh最坏的情况下，查找log2n

次成功数据结构与算法全文共59页，当前为第48页。1.8排序技术所谓排序是指将一个无序序列整理成按值非递减顺序排列的有序序列.交换类排序法插入类排序法选择类排序法数据结构与算法全文共59页，当前为第49页。交换类排序法1.冒泡排序:是一种最简单的交换类排序法,它是通过相邻数据元素的交换逐步将线性表变成有序.从表头开始扫描整个线性表,比较相邻两个数据的大小,若前面的数大于后面的数,则将它们进行交换.依次进行,则第一次可找出最大的数.此后,将其余的数再进行相同的比较.最坏的情况下，查找n(n-1)/2

次数据结构与算法全文共59页，当前为第50页。原序列493865977613273038497697971327979730第1遍比较3849657613273097第2遍比较38496513273076

97第3遍比较38491327306576

97第4遍比较38132730496576

97第5遍比较13273038496576

97第6遍比较13273038496576

97第7遍比较13273038496576

97数据结构与算法全文共59页，当前为第51页。2.快速排序

任取待排序列中的某个元素（一般为第一个元素）作基准，通过一趟排序，将待排元素分为左右两个子序，左子序列元素排序码均小于或等于基准元素排序码，右子序列元素