数据结构导论精.ppt

数据结构导论第1页，本讲稿共41页目录8.1数据结构8.2数据结构的应用举例8.3数据结构的分类8.4排序8.5查找第2页，本讲稿共41页8-1 数据结构的概念要想成为一个专业的开发人员，至少需要以下3个条件：（1）能够熟练地选择和设计各种数据结构和算法。（2）至少要能够熟练地掌握一门程序设计语言。（3）熟知所涉及的相关应用领域的知识。其中，后两个条件比较容易实现，而第一个条件则需要花相当多时间和精力才能够达到，它是区分一个程序设计人员水平高低的重要标志，数据结构贯穿程序设计的始终，缺乏数据结构和算法的深厚功底，很难设计出高水平的具有专业水准的应用程序。第3页，本讲稿共41页l数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由哪些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。第4页，本讲稿共41页第5页，本讲稿共41页学 号姓 名高等数学大学英语政治经济学平均成绩1王五王五807678782李四李四907887853张三张三888989894高二高二789095875苏三苏三80999491我们可以把表称为一个数据结构，表中的每一行是一个结点（或记录），它是由学号、姓名、各科成绩及平均成绩等数据项组成。该表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在前面的结点（亦称为直接前趋）最多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继）也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继，故称为终端结点。例如，表中张三所在结点的直接前趋结点和直接后继结点分别是李四和高二所在结点，上述结点间的关系构成了这张学生成绩表的逻辑结构。第6页，本讲稿共41页该表的存储结构则是指用计算机语言如何表示结点之间的这种关系，即表中的结点是顺序邻接地存储在一片连续的单元中，还是用指针将这些结点链接在一起？在这张表中，可能要经常查看某一学生的成绩，当学生退学时要删除相应的结点，进来新学生时要增加结点。究竟怎样进行查找、删除、插入，这就是数据的运算问题。搞清楚了上述的3个问题，也就弄清了学生成绩表这个数据结构。数据结构定义为：按某种逻辑关系组织起来的一批数据，应用计算机语言，按一定的存储方式将它们存储在计算机的存储器中，并在这些数据上定义了一个运算的集合，就叫做一个数据结构。第7页，本讲稿共41页8-2 数据结构的应用实例在计算机发展初期，人们使用计算机主要是处理数值计算问题。由于当时所涉及的运算对象是简单的整型、实型或布尔型数据，所以程序设计者的主要精力是集中于程序设计的技巧上，而无需重视数据结构。随着计算机应用领域的扩大和软硬件的发展，“非数值问题”越来越显得重要。根据统计，当今处理非数值问题占用了90%以上的机器时间，这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。解决此类问题的关键已不再是分析数学和计算方法，而是能设计出合适的数据结构，才能有效地解决问题。第8页，本讲稿共41页从提出一个实际问题到计算机解出答案需要经过下列步骤：l首先从实际问题抽象出一个数学模型，l然后设计一个解此数学模型的算法，l最后编写程序、进行测试、调试直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象以及这些操作对象之间含有的关系，然后用数学语言加以描述。例如，在分析了一个物理现象或化学现象变化的规律之后可以得到一组代数方程或微分方程。然而，更多的问题无法用数学方程加以描述。第9页，本讲稿共41页【例例8-18-1】电话号码查询系统电话号码查询系统l编一个查询某个城市或单位的私人电话号码的程序。要求对任意给出的一个姓名，若该人有电话号码，则迅速找到其电话号码；否则指出该人没有电话号码。l要解此问题首先构造一张电话号码登记表。表中每个结点存放两个数据项：姓名和电话号码。l但对一个有上百万私人电话的城市就不实用了。若这张表是按姓氏排列的，则可另造一张姓氏索引表。查找过程是先在索引表中查对姓氏，然后根据索引表中的地址到电话号码登记表中核查姓名，这样查找登记表时就无需查找其他姓氏的名字了。因此，在这种新的结构上产生的查找算法就更为有效。第10页，本讲稿共41页【例例8-28-2】田径赛的时间安排问题田径赛的时间安排问题l设某校的田径选拔赛共设6个项目的比赛，即跳高、跳远、标枪、铅球、100米和200米短跑，规定每个选手至多参加3个项目的比赛。现有5名选手报名参赛，选手所选择的项目如表8-2所示。表8-2 参赛选手比赛项目表姓 名 项目1 项目2 项目3苏三跳高跳远100米张五标枪铅球李八标枪100米 200米周亮铅球200米 跳高单于跳远200米图中A、B、F分别对应于6个竞赛项目。第11页，本讲稿共41页例8-38-3】多叉路口交通灯的管理问题。圆圈中的号码分别表示4种颜色的交通灯。第12页，本讲稿共41页8-3 数据结构的具体分类l数据结构分为两大类：线性结构和非线性结构。线性结构的逻辑特征是：有且仅有一个开始结点和一个终端结点，并且所有结点最多只有一个直接前趋和一个直接后继。结点和结点的关系是一对一。非线性结构的逻辑特征是一个结点可能有多个直接前趋和直接后继。结点和结点的关系是一对多或多对多。第13页，本讲稿共41页8-3-1 8-3-1 线性表线性表u线性表的逻辑特征是在非空的线性表中，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai（2in-1）都有且仅有一个直接前趋ai-1和一个直接后继a i+1。很明显，线性表是一种典型的线性结构。例如英文字母表（A，B，C，Z）是线性表，表中的每个字母就是一个数据元素。u一副扑克的点数（2，3，4，J，Q，K，A）也是线性表，其中每一张牌的点数是一个数据元素。第14页，本讲稿共41页8-3-2 栈栈是指能在某一端插入和删除的特殊线性表。例如用桶堆积物品，先堆进来的压在底下，随后一件一件往堆。取走时，只能从上面一件一件取。栈也称为后进先出表（LIFO表）。第15页，本讲稿共41页8-3-3 8-3-3 队列队列队列队列:“先进先出”（First In First Out，FIFO）的数据结构：即插入在表一端进行，而删除在表的另一端进行，我们将这种数据结构称为队或队列，把允许插入的一端叫队尾（rear），把允许删除的一端叫队头（front）。如图8-5所示是一个有5个元素的队列。入队的顺序依次为a1、a2、a3、a4、a5，出队时的顺序将依然是a1、a2、a3、a4、a5。第16页，本讲稿共41页【例例8-48-4】队列的应用队列的应用舞伴问题舞伴问题 （1）问题叙述假设在周末舞会上，男士和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。（2）问题分析先入队的男士或女士亦先出队配成舞伴。因此该问题具有典型的先进先出特性，可用队列作为算法的数据结构。在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。第17页，本讲稿共41页8-3-4 8-3-4 树l树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很像自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树夹形象表示 第18页，本讲稿共41页l树结构的特点是：它的每一个结点都可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前趋。以下具体地给出树的定义及树的数据结构表示。树是由一个或多个结点组成的有限集合，它很像一株倒悬着的树，从树根到大分枝、小分枝、直到叶子，把数据联系起来，这种数据结构就叫做树结构，简称树。树中每个分叉点称为结点，起始结点称为树根，任意两个结点间的连接关系称为树枝，结点下面不再有分枝称为树叶。结点的前趋结点称为该结点的“双亲”，结点的后趋结点称为该结点的“子女”或“孩子”，同一结点的“子女”之间互称“兄弟”。第19页，本讲稿共41页l在图中，结点A为树的根，根的每个分支称为子树（Subtree），子树也是一棵树；结点子树的根为结点的孩子（Child），如B、C、D为结点A的孩子，而A为B、C、D的双亲（Parent）；同一个双亲的孩子之间为兄弟（Sibling）关系；没有孩子的结点为树的叶子（Leaf），H、F、G、D为树的叶子。第20页，本讲稿共41页8-3-5 图l图（Graph）是一种比线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，即每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，虽然每一层上的数据元素可能和下一层中多个元素（孩子）相关，但只能和上一层中一个元素（双亲）相关；而在图形结构中，结点之间的关系可以是任意的，任意两个数据元素之间都可能相关。第21页，本讲稿共41页（a）有向图 （b）无向图第22页，本讲稿共41页8-3-6 8-3-6 文件 l文件（File）是性质相同的记录的集合。文件的数据量通常很大，一般放置在外存上。数据结构中讨论的文件主要是数据库意义上的文件，不是操作系统意义上的文件。操作系统中研究的文件是一维的无结构连续字符序列。数据库中所研究的文件是带有结构的记录集合，每个记录可由若干个数据项构成。记录是文件中存取的基本单位，数据项是文件可使用的最小单位。数据项有时也称为字段（Field），或者称为属性（Attribute）。第23页，本讲稿共41页8-4 排序n排序是数据处理中经常使用的一种重要运算。如何进行排序，特别是高效率地进行排序是计算机应用中的重要课题之一。n所谓排序，就是要整理文件中的记录，使之按关键字递增（或递减）次序排列起来。其确切定义如下：输入n个记录R1，R2，Rn，其相应的关键字分别为K1，K2，Kn。，输出结果为Ril，Ri2，Rin，使得Ki1Ki2Kin。（或Ki1Ki2Kin）。n插入排序n选择排序n交换排序n快速排序 第24页，本讲稿共41页8-4-1 8-4-1 插入排序(Insert Sort)(Insert Sort)l基本思想：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。【8-5】：初始关键字 49 38 65 97 76 13 27 49 J=2(38)38 49 65 97 76 13 27 49 J=3(65)38 49 65 97 76 13 27 49 J=4(97)38 49 65 97 76 13 27 49 J=5(76)38 49 65 76 97 13 27 49 J=6(13)13 38 49 65 76 97 27 49 J=7(27)13 27 38 49 65 76 97 49 J=8(49)13 27 38 49 49 65 76 97 第25页，本讲稿共41页8-4-2 选择排序（SelectSortSelectSort）基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。【8-6】：初始关键字 49 38 65 97 76 13 27 49第一趟排序后 13 38 65 97 76 49 27 49第二趟排序后 13 27 65 97 76 49 38 49第三趟排序后 13 27 38 97 76 49 65 49第四趟排序后 13 27 38 49 49 97 65 76第五趟排序后 13 27 38 49 49 97 97 76第六趟排序后 13 27 38 49 49 76 76 97第七趟排序后 13 27 38 49 49 76 76 97最后排序结果 13 27 38 49 49 76 76 97第26页，本讲稿共41页8-4-3 8-4-3 冒泡排序冒泡排序(BubbleSort)l基本思想：l两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。第27页，本讲稿共41页排序过程：设想被排序的数组R1.N垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上漂浮，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。【8-7】：49 1313131313131338 4927272727272765 3849383838383897 6538494949494976 9765494949494913 7697656565656527 2776977676767649 49497697979797第28页，本讲稿共41页8-4-4 快速排序（QuickSortQuickSort）l基本思想：l在当前无序区R1.H中任取一个数据元素作为比较的“基准”（不妨记为X），用此基准将当前无序区划分为左右两个较小的无序区：R1.I-1和RI+1.H，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R1.I-1X.KeyRI+1.H（1IH），当R1.I-1和RI+1.H均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。第29页，本讲稿共41页排序过程：【8-8】：初始关键字 49 38 65 97 76 13 27 49第一次交换后 27 38 65 97 76 13 49 49 第二次交换后 27 38 49 97 76 13 65 49 J向左扫描，位置不变，第三次交换后 27 38 13 97 76 49 65 49 I向右扫描，位置不变，第四次交换后 27 38 13 49 76 97 65 49J向左扫描 27 38 13 49 76 97 65 49（一次划分过程）初始关键字 49 38 65 97 76 13 27 49一趟排序之后 27 38 13 49 76 97 65 49 二趟排序之后 13 27 38 49 49 6576 97三趟排序之后 13 27 38 49 49 6576 97最后的排序结果 13 27 38 49 49 65 76 97第30页，本讲稿共41页8-5 查找l由于查找运算的使用频率很高，几乎在任何一个计算机系统软件和应用软件中都会涉及到，所以当问题所涉及的数据量相当大时，查找方法的效率就显得格外重要。在一些实时查询系统中尤其如此。第31页，本讲稿共41页8-5-1 查找的基本概念n查找（Searching）的定义是：给定一个值K，在含有n个结点的表中找出关键字等于给定值K的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的指示信息。n顺序查找 n折半查找 第32页，本讲稿共41页8-5-2 8-5-2 顺序查找顺序查找n顺序查找是一种最简单的查找方法，实际就是顺藤摸瓜。它的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定的值K比较，若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。第33页，本讲稿共41页8-5-3 8-5-3 折半查找l折半查找又称二分查找，它是一种效率较高的查找方法。但是，二分查找要求线性表是有序表，即表中结点按关键字有序，并且要用数组作为表的存储结构。l折半查找的基本思想是：首先将待查的K值和有序表R0到Rn-1的中间位置mid的结点的关键字比较，若相等，则查找完成；否则，若Rmid.keyK，则说明待查找的结点只可能在左子表R0到Rmid-1中，我们只要在左子表中继续进行二分查找，若Rmid.keyK，则说明待查找的结点只可能在右子表Rmid+1到Rn-1中，我们只要在右子表中继续进行二分查找。这样，经过一次关键字比较就缩小了一半的查找区间。如此进行下去，直到找到关键字为K的结点，或者当前的查找区间为空（表示查找失败）。第34页，本讲稿共41页例如，假设被查找的有序表中关键字序列为：05，13，19，21，37，56，64，75，80，88，92当给定的K值分别是21和85时，进行折半查找的过程如图8-8所示，图中用方括号表示当前的查找区间，用“”表示中间位置指示器mid。图8-8 折半查找过程示例（a）查找K=21的过程（3次比较后查找成功）（b）查找K=85的过程（3次比较后查找失败）第35页，本讲稿共41页8-6 数据结构在VB编程中的实现方法lBasic语言拥有较高的普及率，同时在Windows操作系统中Visual Basic以功能强、代码量小，容易上手和所见即所得的可视化界面赢得了广大Basic程序编制者的交口称赞。然而，在诸如数值计算、结构计算及项目管理系统的编程中如何构建数据结构，并设计出相应的算法。实际上在VB中利用数组（尤其动态数组）和自定义数据类型（Type Statement）完全可以描述诸如链表、栈、队列和二叉树这样的结构，并实现排序、查找等运算，且机制上也非常灵活。第36页，本讲稿共41页【8-9】用名为queue的自定义数据类型声明一个固定大小的数组：Type queuedata As Integer 用作数据场next As Integer 用作指针场End TypeConst max=10Dim a(10)As queue第37页，本讲稿共41页【例8-10】用queue将a(10)初始化为一个单向链接表For i=0 To 9 a(i).next=i+1 i+1为下一个元素的指针a(i).data=10*rndNext i第38页，本讲稿共41页【例8-11】队列的进队及出队操作Dim top1 As integer定义指向队头的指针变量Dim bottom As integer定义指向队尾的指针变量Dim linshi 变量Public Function removequeue(a1 As Integer)出队函数If bottom=top1 Then bottom=top1队空 Debug.Print 队空 top1=0:bottom=0 Else bottom=a(bottom).next bottom指针后移，为元素出队作准备 j=a(bottom).data 元素a1出队 Debug.Print 出队,b,j,bottom,jEnd IfEnd Function第39页，本讲稿共41页Public Function insertqueue(ByVal a1 As Integer)进队函数If a(top1).next=bottom Then a(top1).next=bottom队满 max=max+1 Redim Preserve a(max)as queue linshi=a(top1).next 队满，准备插入新节点 a(top1).next=max 插入新节点的指针 top1=max top1指针指向新位置，为新元素a1进队作准备 a(top1).next=linshi 新节点插入结束 a(top1).data=a1 新元素a1进队Elsetop1=a(top1).next 队不满，top1指针后移，新元素a1准备进队 a(top1).data=a1 新元素a1进队 Debug.Print 进队,t,i,top1,a(top1).dataEnd IfEnd Function第40页，本讲稿共41页本章结束第41页，本讲稿共41页