1、第一章第一章 数据结构与算法数据结构与算法 1.1算法算法算法的基本概念算法的基本概念 所谓所谓算法算法是指解题方案的是指解题方案的准确而完整的描述。准确而完整的描述。一一.算法的基本特征算法的基本特征(可行性可行性:执行后能得到满意结果。执行后能得到满意结果。(确定性确定性:算法中每个步骤必须明确定义，算法中每个步骤必须明确定义，不允许多义性。不允许多义性。(有穷性有穷性:算法必须在有限时间内做完。算法必须在有限时间内做完。(拥有足够的情报拥有足够的情报:确保算法有效还取决确保算法有效还取决于情报是否足够。于情报是否足够。二二.算法的基本要素算法的基本要素(算法对数据的运算和操作算法对数据的
2、运算和操作：算术运算、：算术运算、逻辑运算、关系运算、数据传输。逻辑运算、关系运算、数据传输。(算法的控制结构算法的控制结构:顺序、选择、循环顺序、选择、循环四四.算法复杂度算法复杂度(算法的时间复杂度算法的时间复杂度执行算法所需要的执行算法所需要的计算工作量计算工作量(算法的空间复杂度算法的空间复杂度执行算法执行算法所需要的内存空间所需要的内存空间1.2数据结构的基本概念数据结构的基本概念数据结构作为计算机的一门学科，主要研究数据结构作为计算机的一门学科，主要研究以下三个方面的问题以下三个方面的问题:P71.数据集合中各数据元素之间所固有的逻辑数据集合中各数据元素之间所固有的逻辑关系，即关系
3、，即数据的逻辑结构数据的逻辑结构。2.在对数据进行处理时，各数据元素在计算在对数据进行处理时，各数据元素在计算机中在存储关系，即机中在存储关系，即数据的存储结构数据的存储结构。3.对各种数据结构进行的对各种数据结构进行的运算运算。一一.数据的逻辑结构数据的逻辑结构数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。更通俗地说，数据结构是指带有结构的数据更通俗地说，数据结构是指带有结构的数据元素的集合。元素的集合。P11一个数据结构应包含以下两个方面的信息：一个数据结构应包含以下两个方面的信息：元素的信息元素的信息数据元素之间的前后件关系。数据元素之间的前后件关系。所
4、谓所谓数据的逻辑结构数据的逻辑结构是指反映数据元素之间是指反映数据元素之间逻辑关系逻辑关系的数据结构。的数据结构。前后件：前驱、后件。前后件：前驱、后件。二二.数据的存储结构数据的存储结构 数据的逻辑结构是在计算机存储空数据的逻辑结构是在计算机存储空间的存放形式称为间的存放形式称为数据的存储结构。数据的存储结构。三三.数据结构的图形表示数据结构的图形表示ABCDEF其中其中D称为是称为是E的的前件前件,C的的后件后件.其他相同其他相同.父亲父亲儿子儿子女儿女儿其中其中“父亲父亲”是是“儿子儿子”和和“女儿女儿”的的前件前件，“儿子儿子”和和“女儿女儿”是是“父亲父亲”的的后件后件。四四.线性结
5、构和非线性结构线性结构和非线性结构空数据结构空数据结构:一个元素都没有。一个元素都没有。数据结构一般分为数据结构一般分为:线性结构线性结构和和非线性结构非线性结构。非空线性结构满足非空线性结构满足:有且只有一个有且只有一个根节点根节点；每；每个节点最多有一个个节点最多有一个前件节点前件节点、也最多有一个、也最多有一个后后件节点件节点。如果一个数据结构不是线性结构，则称之为如果一个数据结构不是线性结构，则称之为非线性结构非线性结构。1.3线性表与顺序存储结构线性表与顺序存储结构 线性表线性表是最简单、最常用的一种数据结构。是最简单、最常用的一种数据结构。线性表是线性表是n(n=0)个元素构成的有
6、限序列个元素构成的有限序列(a1,a2,an)。(1)有且只有一个根结点有且只有一个根结点a1,它无前件；它无前件；(2)有且只有一个终端结点有且只有一个终端结点an,它无后件；它无后件；(3)其他所有结点有且只有一个前件，也有且只其他所有结点有且只有一个前件，也有且只有一个后件。有一个后件。线性表中结点的个数称为线性表中结点的个数称为线性表的长度线性表的长度,当当n=0时，称为时，称为空表空表.一一.线性表的顺序存储结构线性表的顺序存储结构线性表在计算机中采用线性表在计算机中采用顺序存储顺序存储。线性表的顺序存储指的是用线性表的顺序存储指的是用的数据元素。的数据元素。线性表的顺序存储结构具有
7、以下两个特点线性表的顺序存储结构具有以下两个特点:(线性表中所有元素所占的存储空间是线性表中所有元素所占的存储空间是连续连续的。的。(线性表中各数据元素在存储空间中是按线性表中各数据元素在存储空间中是按逻逻辑顺序辑顺序依次存放的。依次存放的。二二.线性表的插入运算线性表的插入运算线性表为线性表为:(a1,a2 ai-1,ai,ai+1an)在第在第i个位置之前上插入新的结点个位置之前上插入新的结点x:线性表变为线性表变为:(a1,a2 ai-1,x,ai,ai+1an)长度变为长度变为n+1。在在最好的情况下最好的情况下,不需要不需要移动表中的元素。移动表中的元素。在在最坏的情况下最坏的情况下
8、,需要移动表中的需要移动表中的所有所有元素。元素。在在平均情况下平均情况下,需要移动需要移动表中一半表中一半的元素。的元素。三三.线性表的删除运算线性表的删除运算线性表为线性表为:(a1,a2 ai-1,ai,ai+1an)在第在第i个位置上删除新的结点个位置上删除新的结点ai:线性表变为线性表变为:(a1,a2 ai-1,ai+1an)长度变为长度变为n-1。在在最好的情况下最好的情况下,不需要不需要移动表中的元素。移动表中的元素。在在最坏的情况下最坏的情况下,需要移动表中的需要移动表中的所有所有元素。元素。在在平均情况下平均情况下,需要移动需要移动表中一半表中一半的元素。的元素。1.4栈和
9、队列栈和队列1.什么是栈？什么是栈？栈是栈是限定在一端进行插入和删除运算限定在一端进行插入和删除运算的线性的线性表。表。允许插入与删除的一端称为允许插入与删除的一端称为栈顶栈顶，不允许插，不允许插入与删除的一端称为入与删除的一端称为栈底栈底。假设栈假设栈s=(a1,a2,an),则则a1称为栈底元素，称为栈底元素，an成为栈顶元素。成为栈顶元素。栈也称为栈也称为先进后出先进后出或或后进先出后进先出的线性表的线性表。1.4栈和队列栈和队列anan-1a2a1进栈进栈退栈退栈toptopbottombottom栈栈:后进先出表后进先出表1.4栈和队列栈和队列2.栈的顺序存储及其运算栈的顺序存储及其
10、运算 P21 栈空栈空栈满栈满正常正常dcbagfedcba进栈时会发进栈时会发生生上溢上溢错误错误退栈时会发退栈时会发生生下溢下溢错误错误1.4栈和队列栈和队列1.什么是队列什么是队列 队列是指只允许队列是指只允许在一端进行插入在一端进行插入，而在，而在另一另一端进行删除端进行删除的线性表。的线性表。允许插入的一端称为允许插入的一端称为队尾队尾，允许删除的一端，允许删除的一端称为称为队头队头.假设队列假设队列q=(a1,a2,an),则则a1称为队头元称为队头元素，素，an成为队尾元素。成为队尾元素。队列队列(queue)的运算示意的运算示意ABCD一个队列一个队列插入插入(入队入队)删除删
11、除(退队退队)BCDABCDEfrontrearfrontfrontrearrear1.4栈和队列栈和队列2.循环队列及其算法循环队列及其算法循环队列：将队列的存储空间的最后一个位循环队列：将队列的存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。置绕到第一个位置，形成逻辑上的环状空间。m21frontrear1.4栈和队列栈和队列frontrear123n分析可知：当分析可知：当front=rear时，不能确定循环队列是时，不能确定循环队列是空还是满，于是需要要一空还是满，于是需要要一个标记个标记S,用来判断队列的用来判断队列的状态状态:S=0 表示队列为表示队列为空空S=1 表示
12、队列为表示队列为非空非空由此得出：由此得出：队列为空的条件是队列为空的条件是:s=0队列为满的条件是队列为满的条件是:s=1且且front=rear1.5线性线性链表链表1.什么是链式存储？什么是链式存储？线性表顺序存储的缺点：插入删除时移动大量元素；线性表顺序存储的缺点：插入删除时移动大量元素；有有“上溢上溢”情况；空间不便于动态分配。情况；空间不便于动态分配。在链式存储方式中在链式存储方式中,每个结点有两部分组成每个结点有两部分组成:一部分用一部分用于存放数据元素的值于存放数据元素的值,称为称为数据域数据域；另一部分存放指；另一部分存放指针针,称为称为指针域指针域。在链式存储结构中在链式存
13、储结构中,存储数据结构的存储空间可以不存储数据结构的存储空间可以不连续连续,各数据结点的存储顺序与数据元素之间的逻辑各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致关系可以不一致,而数据元素之间的逻辑关系是由指而数据元素之间的逻辑关系是由指针域来确定的针域来确定的.2.线性单链表线性单链表在线性单链表中在线性单链表中,结点的结点的数据域数据域存放数据元素存放数据元素的值的值,指针域指针域存放下一个数据元素的存储序号存放下一个数据元素的存储序号,即指向后件结点即指向后件结点.V(i)Next(i)数据域数据域指针域指针域 数据数据1 数据数据nnull 数据数据2HEAD1B1023A14
14、56D878E910C6ABCDE11101066883.线性双向链表线性双向链表在线性单链表中从一个结点只能找到它的下在线性单链表中从一个结点只能找到它的下一个结点一个结点,但找不到前一个结点但找不到前一个结点.为解决这一问为解决这一问题题,将线性链表中每一个结点设置两个指针将线性链表中每一个结点设置两个指针:左左指针指针和和右指针右指针.这样的链表称为这样的链表称为双向链表双向链表.00head4.带链的栈和队列带链的栈和队列 P27(1)栈也是线性表。栈也是线性表。带链的栈称为可利用栈。带链的栈称为可利用栈。(2)队列也是线性表。也可以采用链式存储结构。队列也是线性表。也可以采用链式存储
15、结构。toptopa10an-1anan0a2a1frontrear5.线性链表的基本运算线性链表的基本运算l插入：插入：l删除：删除：l合并：合并：l分解：分解：l逆转：逆转：l复制：复制：l排序：排序：l查找：查找：(1).在线性链表中查找指定元素在线性链表中查找指定元素在非空线性链表中寻找包含指定元素值在非空线性链表中寻找包含指定元素值x的的前一个结点前一个结点p的基本方法的基本方法:从头结点指向的结点开始往后沿指针进行扫从头结点指向的结点开始往后沿指针进行扫描描,直到后面已没有结点或下一个结点的数据直到后面已没有结点或下一个结点的数据域为域为x为止为止.(2).线性链表的插入线性链表的
16、插入线性链表插入过程中线性链表插入过程中不发生数据元素移动不发生数据元素移动现现象，只要改变有关结点的指针即可，提高了象，只要改变有关结点的指针即可，提高了效率。效率。HEAD(3).线性链表的删除线性链表的删除线性链表删除过程中不发生数据元素移动现线性链表删除过程中不发生数据元素移动现象，只要改变有关结点的指针即可，提高了象，只要改变有关结点的指针即可，提高了效率。效率。HEAD6.双向链表的基本运算双向链表的基本运算(插入插入)00head6.双向链表的基本运算双向链表的基本运算(删除删除)00head7.循环链表及其基本运算循环链表及其基本运算单链表的最后一个结点的指针域为单链表的最后一
17、个结点的指针域为HULL;如果如果将它改为存放链表中头结点的地址，这样就构成将它改为存放链表中头结点的地址，这样就构成了一个环。了一个环。HEAD非空循环链表非空循环链表HEAD空循环链表空循环链表其插入与删除其插入与删除操作与单链表操作与单链表相同相同1.6树与二叉树树与二叉树树是一种简单的非线性结构树是一种简单的非线性结构.具有层次结构。具有层次结构。基本术语基本术语:P32父结点父结点、根结点根结点、子结点子结点、叶子结点叶子结点。结点的度结点的度、树的度树的度，树的深度树的深度、子树子树。abcsdqwvxuverfghtpynm1.二叉树的定义二叉树的定义非空二叉树具有以下非空二叉树
18、具有以下两个特点两个特点：(1)非空二叉树非空二叉树只有一个根结点只有一个根结点(2)每一个结点每一个结点最多有两棵子树最多有两棵子树，且分别称为该结点，且分别称为该结点的左子树和右子树。的左子树和右子树。在二叉树中，每一个结点的度最大为在二叉树中，每一个结点的度最大为2，即所有子，即所有子树也均为二叉树。在二叉树中，一个结点可以只有树也均为二叉树。在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左左子树而没有右子树，也可以只有右子树而没有左子树，当一个结点既没有左子树也没有右子树时，子树，当一个结点既没有左子树也没有右子树时，该结点称为叶子结点。该结点称为叶子结点。2.
19、二叉树的基本性质二叉树的基本性质性质性质1:在二叉树的第在二叉树的第k层上至多有层上至多有2K-1个结点个结点性质性质2:深度为深度为m的二叉树至多有的二叉树至多有2m-1个结点。个结点。性质性质3:对任意一棵二叉树，度为对任意一棵二叉树，度为0的结点数总的结点数总比度为比度为2的结点数的结点数多多1。(n0=n2+1)性质性质4:具有具有n个结点的完全二叉树深度至少为个结点的完全二叉树深度至少为log2n+1。(性质性质2反推反推)3.满二叉树与完全二满二叉树与完全二叉树叉树满二叉树满二叉树:除最后一层外除最后一层外,每一层上的所有结每一层上的所有结点都有两个子结点点都有两个子结点.即所有层
20、的结点数均达到即所有层的结点数均达到最大值最大值.完全二叉树完全二叉树:除最后一层外除最后一层外,每一层上的结点每一层上的结点数均达到最大值数均达到最大值,在最后一层上只缺少右边的在最后一层上只缺少右边的若干结点若干结点.3.满二叉树与完全二叉树满二叉树与完全二叉树完全二叉树还具有以下两个性质：完全二叉树还具有以下两个性质：性质性质5:具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为log2n+1性质性质6:设完全二叉树共有设完全二叉树共有n个结点，如果从根结点开个结点，如果从根结点开始，按层序用自然数始，按层序用自然数1,2,3n给结点进行编号，则给结点进行编号，则对于编号为对
21、于编号为k的结点有如下特点：的结点有如下特点：若若k=1则该结点为要根结点。则该结点为要根结点。若若2k=n，则编号为，则编号为k的结点，其左子树为的结点，其左子树为2k,右结右结点为点为2k+1若若2k+1=n，则编号为，则编号为k的结点的右子树编号为的结点的右子树编号为2k+1。1234567891011121314154.二叉树的存储结构二叉树的存储结构在计算机中，二叉树通常采用在计算机中，二叉树通常采用链式存储结构链式存储结构。存储结点的结构存储结点的结构:数据域数据域,左指针域左指针域,右指针域右指针域。L(i)V(i)R(i)ABCDEFGPY5.二叉树的遍历二叉树的遍历二叉树的遍
22、历二叉树的遍历是指不重复地访问二叉树是指不重复地访问二叉树中的所有结点中的所有结点.(1)前序前序遍历遍历(根根-左左-右右)(2)中序中序遍历遍历(左左-根根-右右)(3)后序后序遍历遍历(左左-右右-根根)A AB BC CD DE EF F前序遍历：前序遍历：中序遍历：中序遍历：后序遍历：后序遍历：FCEADBGHP前序遍历：前序遍历：中序遍历：中序遍历：后序遍历：后序遍历：ABCDEYXZF1.7查找技术查找技术所谓所谓查找查找是指在一个给定的数据结构中查找某个指是指在一个给定的数据结构中查找某个指定的元素。定的元素。1.顺序查找顺序查找:从表的一端开始从表的一端开始,顺序扫描顺序扫描
23、,依次将扫描依次将扫描的关键字和待寻找的的关键字和待寻找的k值比较值比较,若相等若相等,则查找成功则查找成功;若若扫描完毕扫描完毕,仍未找到仍未找到,则扫描失败。则扫描失败。以下情况只能采用顺序查找以下情况只能采用顺序查找:(1)线性表示无序表；线性表示无序表；(2)有序线性表采用链式存储结构有序线性表采用链式存储结构平均情况下平均情况下，大约要与，大约要与表中一半表中一半的元素进行比较的元素进行比较.最坏情况下最坏情况下，要查找要查找n次次.1.7查找技术查找技术2.二分法查找二分法查找:只适用于只适用于顺序存储顺序存储的的有序表有序表.设有序表的长度为设有序表的长度为n,被查元素为被查元素
24、为x,则查找方法则查找方法:将将x与线性表的中间项相比较；与线性表的中间项相比较；若中间项等于若中间项等于x,则说明查到，查找结束；则说明查到，查找结束；若若x小于中间项小于中间项,则在线性表的前半部分查找则在线性表的前半部分查找;若若x大于中间项大于中间项,则在线性表的后半部分查找则在线性表的后半部分查找.最坏的情况下最坏的情况下，查找查找 log2n 次次1.7查找技术查找技术8，17，25，44，68，77，98，100，115，125查找查找k=98一次查找后一次查找后:二次查找后二次查找后:midhighlow三次查找三次查找:lowmidhighlow midhigh最坏的情况下最
25、坏的情况下，查找查找 log2n 次次成功成功1.8排序技术排序技术所谓所谓排序排序是指将一个无序序列整理是指将一个无序序列整理成按值成按值非递减非递减顺序排列的有序序列顺序排列的有序序列.交换类排序法交换类排序法插入类排序法插入类排序法选择类排序法选择类排序法交换类排序法交换类排序法1.冒泡排序冒泡排序:是一种最简单的交换类排序法是一种最简单的交换类排序法,它它是通过相邻数据元素的交换逐步将线性表变是通过相邻数据元素的交换逐步将线性表变成有序成有序.从表头开始扫描整个线性表从表头开始扫描整个线性表,比较相邻两个数比较相邻两个数据的大小据的大小,若前面的数大于后面的数若前面的数大于后面的数,则
26、将它们则将它们进行交换进行交换.依次进行依次进行,则第一次可找出最大的数则第一次可找出最大的数.此后此后,将其余的数再进行相同的比较将其余的数再进行相同的比较.最坏的情况下最坏的情况下，查找，查找 n(n-1)/2 次次原序列原序列49 38 65 97 76 13 27 3038 49769797132797 9730第第1遍比较遍比较38 49 65 76 13 27 30 97第第2遍比较遍比较38 49 65 13 27 30 76 97第第3遍比较遍比较38 49 13 27 30 65 76 97第第4遍比较遍比较38 13 27 30 49 65 76 97第第5遍比较遍比较13
27、 27 30 38 49 65 76 97第第6遍比较遍比较13 27 30 38 49 65 76 97第第7遍比较遍比较13 27 30 38 49 65 76 972.快速排序快速排序 任取待排序列中的某个元素（一般为第一任取待排序列中的某个元素（一般为第一个元素）作基准，通过一趟排序，将待排元个元素）作基准，通过一趟排序，将待排元素分为左右两个子序，左子序列元素排序码素分为左右两个子序，左子序列元素排序码均小于或等于基准元素排序码，右子序列元均小于或等于基准元素排序码，右子序列元素排序码均大于基准元素排序码。然后分别素排序码均大于基准元素排序码。然后分别对两个子序排序，直至整个序列有序
28、。对两个子序排序，直至整个序列有序。插入类排序插入类排序每次将一个待排的纪录，按其关键字大每次将一个待排的纪录，按其关键字大小插入到前面已经排好序的子文件中的小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。适当位置，直到全部记录插入完成为止。l简单插入排序法简单插入排序法l希尔排序法希尔排序法一、简单插入排序示例一、简单插入排序示例简单的插入类排序最坏的情况：简单的插入类排序最坏的情况：n(n-1)/22.希尔排序法希尔排序法先将整个待排元素序列分割成若干个子先将整个待排元素序列分割成若干个子序列，分别进行直接插入排序，待整个序列，分别进行直接插入排序，待整个序列中的元素
29、基本有序时，再对全体元序列中的元素基本有序时，再对全体元素进行一次直接插入排序。素进行一次直接插入排序。在最坏的情况下：在最坏的情况下：希尔希尔排序法需要的比较次数是排序法需要的比较次数是 O(n1.5)选择类排序选择类排序每一趟从待排序的记录中选出关键字最每一趟从待排序的记录中选出关键字最小的纪录，顺序放在已排好序的子序列最小的纪录，顺序放在已排好序的子序列最后。直到全部记录排序完毕。后。直到全部记录排序完毕。q简单选择排序法简单选择排序法q堆排序法堆排序法简单的选择排序的过程示例最坏的简单选择类排序法需要比较最坏的简单选择类排序法需要比较n(n-1)/2 次次1.堆排序堆排序l图9185533647302412所有根结点的大于或等于左右孩子的值-大根堆。所有根结点的小于或等于左右孩子的值-小根堆。在最坏的情况下：堆排序法需要的比较次数是 O(nlog2n)查找技术查找技术排序技术排序技术顺序查找顺序查找二分法查找二分法查找交换类排序交换类排序插入类排序插入类排序选择选择 类排类排序序快速排序法快速排序法冒泡排序法冒泡排序法希尔排序法希尔排序法简单插入排序法简单插入排序法简单选择排序法简单选择排序法堆排序法堆排序法nlog2nO(nlog2n)n(n-1)/2最快情况下的次数最快情况下的次数（时间复杂度）（时间复杂度）
