数据结构与算法.ppt

《数据结构与算法.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法.ppt（59页珍藏版）》请在优知文库上搜索。

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.

9、4栈和队列栈和队列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 表示队列为表示队列为空空

12、S=1 表示队列为表示队列为非空非空由此得出：由此得出：队列为空的条件是队列为空的条件是:s=0队列为满的条件是队列为满的条件是:s=1且且front=rear1.5线性线性链表链表1.什么是链式存储？什么是链式存储？线性表顺序存储的缺点：插入删除时移动大量元素；线性表顺序存储的缺点：插入删除时移动大量元素；有有“上溢上溢”情况；空间不便于动态分配。情况；空间不便于动态分配。在链式存储方式中在链式存储方式中,每个结点有两部分组成每个结点有两部分组成:一部分用一部分用于存放数据元素的值于存放数据元素的值,称为称为数据域数据域；另一部分存放指；另一部分存放指针针,称为称为指针域指针域。在链式存储结

13、构中在链式存储结构中,存储数据结构的存储空间可以不存储数据结构的存储空间可以不连续连续,各数据结点的存储顺序与数据元素之间的逻辑各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致关系可以不一致,而数据元素之间的逻辑关系是由指而数据元素之间的逻辑关系是由指针域来确定的针域来确定的.2.线性单链表线性单链表在线性单链表中在线性单链表中,结点的结点的数据域数据域存放数据元素存放数据元素的值的值,指针域指针域存放下一个数据元素的存储序号存放下一个数据元素的存储序号,即指向后件结点即指向后件结点.V(i)Next(i)数据域数据域指针域指针域 数据数据1 数据数据nnull 数据数据2HEAD1B1

14、023A1456D878E910C6ABCDE11101066883.线性双向链表线性双向链表在线性单链表中从一个结点只能找到它的下在线性单链表中从一个结点只能找到它的下一个结点一个结点,但找不到前一个结点但找不到前一个结点.为解决这一问为解决这一问题题,将线性链表中每一个结点设置两个指针将线性链表中每一个结点设置两个指针:左左指针指针和和右指针右指针.这样的链表称为这样的链表称为双向链表双向链表.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.循环链表及其基本运算循环链表及其基本运算单链表的最后一个结点的指针域为单链表的最后一个结点的指针域为HULL;如果如果将它改为存放链表中头结点的地址，这样就构成将它改为存放链表中头结点的地址，这样就构成了一个环。了一个环。HEAD非空循环链表非空循环链表HEAD空循环链表空循环链表其插入与删除其插入与删除操作与单链表操作与单链表相同相同1.6树与二叉树树与二叉树树是一种简单的非线性结构树是一种简单的非线性结构. 具有层次结构。具有层次结构。基本术语基本术语:P32父结