计算机科学导论讲稿.pptx

《计算机科学导论讲稿.pptx》由会员分享，可在线阅读，更多相关《计算机科学导论讲稿.pptx（84页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第4 4章章 程序设计基础程序设计基础2023/4/42计算机科学导论计算机科学导论学习目标学习目标u了解程序设计的基础知识、程序设计风格的重要性、了解程序设计的基础知识、程序设计风格的重要性、基本的查找和排序方法。基本的查找和排序方法。u掌握结构化程序设计方法和面向对象程序设计方法的掌握结构化程序设计方法和面向对象程序设计方法的思想、几种基本的数据结构。思想、几种基本的数据结构。u学习计算机首先要学习程序设计，良好的程序设计技学习计算机首先要学习程序设计，良好的程序设计技能和风格有助于加深对计算机的理解和进一步学习。能和风格有助于加深对计算机的理解和进一步学习。第第4 4章章 程序设计基础

2、程序设计基础2023/4/43计算机科学导论计算机科学导论4.1 程序设计基础程序设计基础程序设计步骤如下：程序设计步骤如下：(1)(1)确定要解决的问题确定要解决的问题。(2)(2)分析问题分析问题。在着手解决问题之前，应该通过分。在着手解决问题之前，应该通过分析，充分理解问题，明确原始数据、解题要求、析，充分理解问题，明确原始数据、解题要求、需要输出的数据及形式等。需要输出的数据及形式等。(3)(3)选择计算方法选择计算方法。(4)(4)确定数据结构和算法确定数据结构和算法。算法是解题的过程。首。算法是解题的过程。首先集中精力于算法的总体规划，然后逐层降低问先集中精力于算法的总体规划，然后

3、逐层降低问题的抽象性，逐步充实细节，直到最终把抽象的题的抽象性，逐步充实细节，直到最终把抽象的问题具体化成可用程序语句表达的算法。这是一问题具体化成可用程序语句表达的算法。这是一个自上而下、逐步细化的过程。个自上而下、逐步细化的过程。2023/4/44计算机科学导论计算机科学导论4.1 程序设计基础程序设计基础(5)(5)绘制流程图绘制流程图。(6)(6)编写程序编写程序。利用程序设计语言表示算法，编写。利用程序设计语言表示算法，编写代码。代码。(7)(7)调试并测试程序调试并测试程序。调试程序包括编译和连接等。调试程序包括编译和连接等操作。程序员还要对程序执行的结果进行分析，只操作。程序员还

4、要对程序执行的结果进行分析，只有能够得到正确结果的程序才是所需的程序。有能够得到正确结果的程序才是所需的程序。(8)(8)整理资料，交付使用整理资料，交付使用。高质量程序设计目标是结构化程度高、可读性好、效率高质量程序设计目标是结构化程度高、可读性好、效率高、可靠性高、便于维护。高、可靠性高、便于维护。2023/4/45计算机科学导论计算机科学导论u1自上而下自上而下与与自下而上自下而上先将一个大问题分解成若干个子问题，把比较复先将一个大问题分解成若干个子问题，把比较复杂的子问题继续分解成更加简单的二级子问题，杂的子问题继续分解成更加简单的二级子问题，直至每个子问题都有显而易见的解决办法，然后

5、直至每个子问题都有显而易见的解决办法，然后在在实现时采用自下而上的方法实现时采用自下而上的方法，逐一编写解决各，逐一编写解决各个子问题的程序。个子问题的程序。设计程序时采用自上而下的方设计程序时采用自上而下的方法法比采用自下而上的方法效率要高得多。比采用自下而上的方法效率要高得多。4.2.1 结构化程序设计方法结构化程序设计方法2023/4/46计算机科学导论计算机科学导论采用自上而下解决问题的思路如图采用自上而下解决问题的思路如图:4.2.1 结构化程序设计方法结构化程序设计方法2023/4/47计算机科学导论计算机科学导论 用这种方法逐步分解，直到作者认为可以直接将各小段表达为文字语句为止

6、。这种方法就叫 做“自顶向下，逐步细化”。2023/4/48计算机科学导论计算机科学导论u2结构化方法结构化方法结构化方法有助于在正式编写程序之前充分结构化方法有助于在正式编写程序之前充分理解问题的实质和实现方法，并且可以在具理解问题的实质和实现方法，并且可以在具体编码过程中提供指导。体编码过程中提供指导。4.2.1 结构化程序设计方法结构化程序设计方法2023/4/49计算机科学导论计算机科学导论u结构化方法通常遵循以下原则结构化方法通常遵循以下原则:(1)(1)用户参与的原则用户参与的原则(2)(2)先分析、再设计、后实现的原则。先分析、再设计、后实现的原则。(3)(3)自上而下的原则自上

7、而下的原则(4)(4)阶段成果文档化阶段成果文档化4.2.1 结构化程序设计方法结构化程序设计方法2023/4/410计算机科学导论计算机科学导论u3结构化程序设计方法结构化程序设计方法 使用使用顺序、选择、循环顺序、选择、循环3 3种基本控制结构。种基本控制结构。4.2.1 结构化程序设计方法结构化程序设计方法2023/4/411计算机科学导论计算机科学导论A AB Ba ab b顺序结构示意图顺序结构示意图 顺序结构顺序结构 顺序结构是一种最简单、最基本的结构，在顺序结顺序结构是一种最简单、最基本的结构，在顺序结构内，构内，各块是按照它们出现的先后顺序依次执行各块是按照它们出现的先后顺序依

8、次执行。下图表示了一个顺序结构形式，从图中可以看出它下图表示了一个顺序结构形式，从图中可以看出它有一个入口有一个入口a a点，一个出口点，一个出口b b点，在结构内点，在结构内A A框和框和B B框框都是顺序执行的处理框。都是顺序执行的处理框。2023/4/412计算机科学导论计算机科学导论已知梯形两底已知梯形两底a、b和高和高h，设计设计一个求梯形面一个求梯形面积积的算的算法，并画出流程法，并画出流程图图。2023/4/413计算机科学导论计算机科学导论 选择结构选择结构 选择结构中包含一个判断框，根据给定的条件选择结构中包含一个判断框，根据给定的条件S S是否成立而选择执行是否成立而选择执

9、行A A框或框或B B框，当条件成立时，执框，当条件成立时，执行行A A，否则执行，否则执行B B。判断框中的两个分支，执行完。判断框中的两个分支，执行完A A或或B B后都必须汇合在一起，从出口后都必须汇合在一起，从出口b b 退出，然后接着执退出，然后接着执行其后的过程。行其后的过程。SABabYN选择结构流程图选择结构流程图2023/4/414计算机科学导论计算机科学导论设计设计一个算法，一个算法，输输出出a，b，c中的最大中的最大值值。2023/4/415计算机科学导论计算机科学导论 循环结构循环结构 循循环环结结构构是是指指在在一一定定条条件件下下反反复复执执行行一一个个程程序序块块

10、的的结结构构。循循环环结结构构也也是是只只有有一一个个入入口口，一个出口。一个出口。whilewhile循环循环 当当给给定定的的条条件件S S成成立立时时，执执行行A A框框操操作作，执执行行完完A A操操作作后后，再再判判断断S S条条件件是是否否成成立立，如如果果成成立立，再再次次执执行行A A操操作作，如如此此重重复复执执行行A A操操作作，直直到到判判断断p p条条件件不不成成立立才才停停止止循循环环。此此时时不不执执行行A A操操作作，而从出口而从出口b b脱离循环结构。脱离循环结构。ASabYN2023/4/416计算机科学导论计算机科学导论abYNSA do-whiledo-w

11、hile循环循环 先先执执行行A A框框操操作作，然然后后判判断断给给定定条条件件S S是是否否成成立立，如如果果成成立立，再再次次执执行行A A操操作作；然然后后再再对对S S进进行行判判断断，如如此此反反复复，直直到到给给定定的的S S条条件件不不成成立立为为止止。此此时时不不再再执执行行A A框，从出口框，从出口b b脱离循环。脱离循环。2023/4/417计算机科学导论计算机科学导论设计一个算法，计算设计一个算法，计算1+2+3+100的值。的值。2023/4/418计算机科学导论计算机科学导论u3结构化程序设计方法结构化程序设计方法 使用使用顺序、选择、循环顺序、选择、循环3 3种基

12、本控制结构。种基本控制结构。4.2.1 结构化程序设计方法结构化程序设计方法2023/4/419计算机科学导论计算机科学导论u4模块化方法模块化方法一个复杂的问题可以划分为多个简单问题的组合。一个复杂的问题可以划分为多个简单问题的组合。在自顶向下、逐步细化的过程中，把复杂问题分解在自顶向下、逐步细化的过程中，把复杂问题分解成一个个简单问题的最基本方法就是模块化。成一个个简单问题的最基本方法就是模块化。模块化便于问题的分析，模块体现了信息隐藏的概模块化便于问题的分析，模块体现了信息隐藏的概念。模块常用子程序加以实现。念。模块常用子程序加以实现。4.2.1 结构化程序设计方法结构化程序设计方法20

13、23/4/420计算机科学导论计算机科学导论模块设计的方法：模块化设计的思想实际上是一种模块化设计的思想实际上是一种“分而治之分而治之”的思想，把一个大任务分为若干个子任务，的思想，把一个大任务分为若干个子任务，每一个子任务就相对简单了。每一个子任务就相对简单了。在拿到一个程序模块以后，根据程序模块的在拿到一个程序模块以后，根据程序模块的功能将它划分为若干个子模块，如果这些子功能将它划分为若干个子模块，如果这些子模块的规模还嫌大，还再可以划分为更小的模块的规模还嫌大，还再可以划分为更小的模块。这个过程采用自顶向下方法来实现。模块。这个过程采用自顶向下方法来实现。2023/4/421计算机科学导

14、论计算机科学导论4.2.2 面向对象的程序设计方法面向对象的程序设计方法u1 1面向对象的思想面向对象的思想OO(Object Oriented，面向对象，面向对象)的程序设计把客观事的程序设计把客观事物看作具有属性和行为的对象，通过抽象找出同一类物看作具有属性和行为的对象，通过抽象找出同一类对象的共同属性对象的共同属性(静态特征静态特征)和行为和行为(动态特征动态特征)，形成类。，形成类。2023/4/422计算机科学导论计算机科学导论对象对象 对对对对象象象象(Object)(Object)(Object)(Object)是是是是具具具具有有有有某某某某些些些些特特特特性性性性的的的的具具

15、具具体体体体事事事事物物物物的的的的抽抽抽抽象象象象。对对象象在在现现实实生生活活中中到到处处可可见见。凡凡凡凡是是是是我我我我们们们们要要要要处处处处理理理理的的的的事事事事物物物物都都都都可可可可成成成成为为为为处处处处理理理理的的的的对对对对象象象象，包包包包括括括括可可可可见见见见的的的的事事事事物物物物（如如如如人人人人、汽汽汽汽车车车车、电电电电话等）和非可见的事物（如感情、思想等）。话等）和非可见的事物（如感情、思想等）。话等）和非可见的事物（如感情、思想等）。话等）和非可见的事物（如感情、思想等）。例例例例如如如如，一一个个人人是是一一个个对对象象，一一台台PCPC机机是是一一

16、个个对对象象；再再将将一一台台PCPC机机拆拆开开看看，便便有有显显示示器器、机机箱箱、硬硬盘盘、主主板板、处处理理器器、鼠鼠标标等等，这这每每一一个个部部件件又又是是一一个个对对象象，即即PCPC机机对对象象是是由由多多个个“子子”对对象象组组成成的的，此此时时PCPC机机可可看看作作为为一一个容器对象。个容器对象。4.2.2 面向对象的程序设计方法面向对象的程序设计方法2023/4/423计算机科学导论计算机科学导论类类 类类类类是是是是具具具具有有有有共共共共同同同同属属属属性性性性、共共共共同同同同操操操操作作作作性性性性质质质质的的的的对对对对象象象象的的的的集集集集合合合合在在例例

17、例例如如如如：桥桥梁梁是是抽抽象象的的概概念念,重重庆庆长长江江大大桥桥、西西湖湖断断桥桥就就是是具具体体的的。我我们们把把抽抽象象的的“桥桥”看看成成类类,而而具具体体的的一一座座桥桥，如重庆长江大桥看成是对象。如重庆长江大桥看成是对象。类类类类是是是是对对对对象象象象的的的的抽抽抽抽象象象象描描描描述述述述，对对对对象象象象则则则则是是是是类类类类的的的的实实实实例例例例。类类是是抽抽象象的，对象是具体的。的，对象是具体的。类类类类可可可可以以以以划划划划分分分分为为为为基基基基类类类类(根根根根类类类类)和和和和子子子子类类类类(派派派派生生生生类类类类)。子子子子类类类类以以以以其其其

18、其基类为起点，并可继承基类的特征。基类为起点，并可继承基类的特征。基类为起点，并可继承基类的特征。基类为起点，并可继承基类的特征。如如水水果果是是基基类类，苹苹果果是是子子类类，而而红红富富士士、黄黄元元帅帅等等苹苹果果品品种种又又是是苹苹果果类类的的子子类类，在在这这里里，水水果果也也称称为为是是苹苹果果的的父父类类，苹苹果果也也可可称称为为是是红红富富士士、黄黄元元帅帅等等的的父父类类。具具体体的的一个红富士苹果就是一个对象。一个红富士苹果就是一个对象。4.2.2 面向对象的程序设计方法面向对象的程序设计方法2023/4/424计算机科学导论计算机科学导论消息消息消消消消息息息息是是是是面

19、面面面向向向向对对对对象象象象系系系系统统统统中中中中实实实实现现现现对对对对象象象象间间间间的的的的通通通通讯讯讯讯和和和和请请请请求求求求任任任任务的操作。务的操作。务的操作。务的操作。消息传递是程序运行的基本处理活动。消息传递是程序运行的基本处理活动。消息传递是程序运行的基本处理活动。消息传递是程序运行的基本处理活动。4.2.2 面向对象的程序设计方法面向对象的程序设计方法2023/4/425计算机科学导论计算机科学导论类的特性类的特性（1 1 1 1）继承性）继承性）继承性）继承性 子子类类不不但但具具有有父父类类的的全全部部属属性性和和方方法法，而而且且允允许许用用户户根根据据需需要

20、要对对已已有有的的属属性性和和方方法法进进行行修修改改，或或添添加加新新的的属属性性和和方方法法，这种特性称为类的继承性。这种特性称为类的继承性。（2 2 2 2）封装性）封装性）封装性）封装性 类类类类的的的的封封封封装装装装性性性性是是是是指指指指类类类类的的的的内内内内部部部部信信信信息息息息对对对对用用用用户户户户是是是是隐隐隐隐蔽蔽蔽蔽的的的的。如如同同一一台台电电视视机机的的使使用用者者只只需需了了解解其其外外部部按按钮钮（用用户户接接口口）的的功功能能与与用法，而无需知道电视机的内部构造与工作原理一样。用法，而无需知道电视机的内部构造与工作原理一样。（3 3 3 3）多态性）多态

21、性）多态性）多态性 类的多态性是指一些相关联的类包括同名的方法程序类的多态性是指一些相关联的类包括同名的方法程序类的多态性是指一些相关联的类包括同名的方法程序类的多态性是指一些相关联的类包括同名的方法程序，但，但方法程序的内容不同。方法程序的内容不同。4.2.2 面向对象的程序设计方法面向对象的程序设计方法2023/4/426计算机科学导论计算机科学导论4.3 基本数据结构基本数据结构u数据结构数据结构(Data Structure)是系统设计是系统设计和程序开发的重要基础。和程序开发的重要基础。2023/4/427计算机科学导论计算机科学导论4.3.1 基本概念基本概念u1数据、数据类型数据

22、、数据类型数据是对客观事物的符号表示。数据是对客观事物的符号表示。在计算机系统内，在计算机系统内，数据通常是指能够输入到计算机中并被计算机进行数据通常是指能够输入到计算机中并被计算机进行处理的符号的集合处理的符号的集合。例如，数字、字母、汉字、图例如，数字、字母、汉字、图形、图像、声音等信息在计算机内部的表示都是数据，形、图像、声音等信息在计算机内部的表示都是数据，可以是数值数据，也可以是非数值数据。可以是数值数据，也可以是非数值数据。数据类型是指具有相同取值范围和可以实施同种操数据类型是指具有相同取值范围和可以实施同种操作的数据的集合。作的数据的集合。例如，在程序设计语言中，通常例如，在程序

23、设计语言中，通常定义了字符型、整数型、数组等多种数据类型。定义了字符型、整数型、数组等多种数据类型。2023/4/428计算机科学导论计算机科学导论u2数据元素、数据项、数据对象数据元素、数据项、数据对象能够独立并完整地描述客观世界实体的能够独立并完整地描述客观世界实体的基本数据单元基本数据单元称为数据元素称为数据元素，它是组成数据的基本单位。在不同的，它是组成数据的基本单位。在不同的应用环境中，数据元素有时可以称为结点、记录等。应用环境中，数据元素有时可以称为结点、记录等。数据项是组成数据元素的不可分割的最小单位数据项是组成数据元素的不可分割的最小单位。最简。最简单的数据元素是由一个数据项构

24、成的。单的数据元素是由一个数据项构成的。同类数据元素的集合称为数据对象。同类数据元素的集合称为数据对象。4.3.1 基本概念基本概念2023/4/429计算机科学导论计算机科学导论学学 号号姓姓 名名高等数学高等数学大学英语大学英语政治经济学政治经济学平均成绩平均成绩1王五王五807678782李四李四907887853张张三三888989894高二高二789095875苏苏三三80999491表中的每一行是一个结点（或记录），即数据元素；表中的每一行是一个结点（或记录），即数据元素；它是由学号、姓名、各科成绩及平均成绩等数据项组成。它是由学号、姓名、各科成绩及平均成绩等数据项组成。4.3.1

25、 基本概念基本概念u2数据元素、数据项、数据对象数据元素、数据项、数据对象2023/4/430计算机科学导论计算机科学导论u3 3数据结构数据结构数据结构数据结构是指数据元素之间的相互关系的集是指数据元素之间的相互关系的集合，包括了数据的合，包括了数据的逻辑结构、物理结构逻辑结构、物理结构以及以及数据的运算。数据的运算。4.3.1 基本概念基本概念2023/4/431计算机科学导论计算机科学导论31u数据结构数据结构主要研究主要研究：1.1.数据集合中数据元素之间所数据集合中数据元素之间所固有固有的关系的关系，即，即数据数据逻辑结构逻辑结构；2.2.数据处理时数据在计算机中的数据处理时数据在计

26、算机中的存储关系存储关系，即，即数据数据存储结构存储结构；3.3.对数据所进行的对数据所进行的操作操作，即，即算法算法。4.3.1 基本概念基本概念2023/4/432计算机科学导论计算机科学导论4.3.1 基本概念基本概念2023/4/433计算机科学导论计算机科学导论33数据逻辑结构数据逻辑结构 u数数据据结结构构中中数数据据元元素素之之间间所所固固有有的的关关系系描描述成述成前后件前后件（前驱与后继）关系。（前驱与后继）关系。u数据之间数据之间前后件关系前后件关系是是它们之间的它们之间的逻辑关逻辑关系系，与与它们在计算机中它们在计算机中存储位置无关存储位置无关，因，因此将这种关系此将这种

27、关系称为数据逻辑结构称为数据逻辑结构。2023/4/434计算机科学导论计算机科学导论34一个数据结构可以表示为：一个数据结构可以表示为：S=S=（D D，R R）S S:数据结构数据结构D D:数据元素集合数据元素集合R:R:D D中数据元素之间中数据元素之间前后件关系前后件关系集合集合，即数据逻辑结构即数据逻辑结构两两个个元元素素之之间间前前后后件件关关系系用用一一个个二二元元组组表示，如：表示，如：(a a1 1,a a2 2)2023/4/435计算机科学导论计算机科学导论35事实上可能有：事实上可能有：如如树形树形结构中的结构中的一个元素一个元素有多个后件有多个后件或如或如网状网状结

28、构中的结构中的一个元素一个元素有多个前件有多个前件因此一般来说，数据之间有因此一般来说，数据之间有4 4种种基本逻辑结构：基本逻辑结构：u 集合集合u 线性线性u 树形树形u 图形图形2023/4/436计算机科学导论计算机科学导论36线性结构线性结构一对一关系一对一关系 集合集合 松散关系松散关系树形结构树形结构一对多关系一对多关系图形结构图形结构多对多关系多对多关系2023/4/437计算机科学导论计算机科学导论37u非线性结构非线性结构：有多个有多个开始开始结点和多个结点和多个终端终端结点，每个结点可有多个前件和多个后件结点，每个结点可有多个前件和多个后件u线性结构线性结构：有且只有有且

29、只有一个一个开始开始结点和一个结点和一个终端终端结点，并且每个结点最多只有一个前结点，并且每个结点最多只有一个前件和一个后件，线性结构件和一个后件，线性结构也称为也称为线性表线性表。u根据根据前后件关系的前后件关系的复杂程度复杂程度，数据逻辑结，数据逻辑结构分为构分为2 2类类。2023/4/438计算机科学导论计算机科学导论38数据物理结构数据物理结构 u定义：定义：数据在计算机数据在计算机存储器中的存储方式存储器中的存储方式 称为称为数据存储结构数据存储结构（或数据物理结构）。（或数据物理结构）。u数据结构中数据元素之间数据结构中数据元素之间在计算机中的在计算机中的位置关系位置关系与与逻辑

30、关系逻辑关系不一定相同不一定相同。u在数据在数据存储结构中，存储结构中，不仅要不仅要存放各个数据元素信息，存放各个数据元素信息，还要还要存放数据元素之间存放数据元素之间前后件关系前后件关系信息。信息。u数据数据存储结构存储结构是是逻辑结构逻辑结构在计算机存储器中的在计算机存储器中的表示表示2023/4/439计算机科学导论计算机科学导论39数据元素在计算机中通常有数据元素在计算机中通常有四种四种存储方式：存储方式：u 顺序顺序u 链式链式u 索引索引u 散列散列常用常用顺序顺序存储结构和存储结构和链式链式存储结构。存储结构。数据物理结构数据物理结构 2023/4/440计算机科学导论计算机科学

31、导论40顺序存储结构顺序存储结构u在存储器中开辟一块在存储器中开辟一块连续连续的单元用于存放数据，的单元用于存放数据，逻辑上相邻的逻辑上相邻的结点结点在物理位置上也邻接在物理位置上也邻接，结点之，结点之间的逻辑关系是由存储单元间的逻辑关系是由存储单元相邻关系相邻关系来体现。来体现。数据地址A12000HA22001HA32002HA42003H2023/4/441计算机科学导论计算机科学导论41链式存储结构链式存储结构结点结点由两部分组成由两部分组成：数据域数据域用于存放数据元素用于存放数据元素值值 指针域指针域用于存放前件或后件的用于存放前件或后件的存储地址存储地址链式存储结构是链式存储结构

32、是通过指针通过指针反映数据间的逻辑关系。反映数据间的逻辑关系。a14003Ha22506Ha32509Ha42000H2001H4003H3004H2506H2507H2509H2510H2023/4/442计算机科学导论计算机科学导论回回 顾顾程序设计步骤程序设计步骤程序设计方法程序设计方法l结构化程序设计方法结构化程序设计方法l面向对象的程序设计方法面向对象的程序设计方法 数据结构的基本概念数据结构的基本概念2023/4/443计算机科学导论计算机科学导论4.3.2 几种典型的数据结构几种典型的数据结构1 1线性表线性表2 2栈栈3 3队列队列4 4线性表线性表5 5图图2023/4/44

33、4计算机科学导论计算机科学导论定义定义 线性表是一组线性表是一组特征相同特征相同数据的有限序列，表数据的有限序列，表示为：示为：L=(a1,a2,a3,an)L=(a1,a2,a3,an)。有限个有限个同类的数据元素同类的数据元素构成的序列。构成的序列。4.3.2 几种典型的数据结构几种典型的数据结构1 1线性表线性表2023/4/445计算机科学导论计算机科学导论有且仅有一个有且仅有一个“第一个第一个”数据元素数据元素有且仅有一个有且仅有一个“最后一个最后一个”数据元素数据元素除第一个数据元素外，其它元素有且仅有一个除第一个数据元素外，其它元素有且仅有一个直直接前驱接前驱除最后一个数据元素外

34、，其它元素有且仅有一个除最后一个数据元素外，其它元素有且仅有一个直接后继直接后继4.3.2 几种典型的数据结构几种典型的数据结构1 1线性表线性表2023/4/446计算机科学导论计算机科学导论u例如英文字母表（例如英文字母表（A A，B B，C C，Z Z）是线）是线性表，表中的每个字母就是一个数据元素。性表，表中的每个字母就是一个数据元素。u一副扑克的点数（一副扑克的点数（2 2，3 3，4 4，J J，Q Q，K K，A A）也是线性表，其中每一张牌的点数是）也是线性表，其中每一张牌的点数是一个数据元素。一个数据元素。4.3.2 几种典型的数据结构几种典型的数据结构1 1线性表线性表20

35、23/4/447计算机科学导论计算机科学导论 线性表通常采用顺序和链表两种物理实现。线性表通常采用顺序和链表两种物理实现。对于经常变化的表，通常采取链表结构。对于经常变化的表，通常采取链表结构。线性表常用的运算主要有：插入、删除、线性表常用的运算主要有：插入、删除、查询和遍历。查询和遍历。4.3.2 几种典型的数据结构几种典型的数据结构1 1线性表线性表2023/4/448计算机科学导论计算机科学导论482.2.栈栈栈是只能栈是只能在表的在表的一端一端进行插入和删除运算的线性表进行插入和删除运算的线性表 u允允许许插插入入和和删删除除运运算算的的一一端端称称为为栈栈顶顶，另另一一端端称称为为栈

36、底栈底。插入插入元素操作称为元素操作称为入栈入栈删除删除元素操作称为元素操作称为出栈出栈4.3.2 几种典型的数据结构几种典型的数据结构2023/4/449计算机科学导论计算机科学导论49 a a1 1 a a2 2 a an n栈底栈底bottombottom栈顶栈顶toptop入栈入栈出栈出栈2023/4/450计算机科学导论计算机科学导论4.3.2 几种典型的数据结构几种典型的数据结构栈是一种栈是一种“后进先出后进先出”或或“先进后出先进后出”的数据结构。的数据结构。2023/4/451计算机科学导论计算机科学导论例如用桶堆积物品，先堆进来的压在底下，例如用桶堆积物品，先堆进来的压在底下

37、，随后一件一件往堆。取走时，只能从上面随后一件一件往堆。取走时，只能从上面一件一件取。一件一件取。4.3.2 几种典型的数据结构几种典型的数据结构2023/4/452计算机科学导论计算机科学导论523.3.队列队列 只允许：只允许：在在一端一端进行进行插入插入运算，运算，而在而在另一端另一端进行进行删除删除运算的线性表。运算的线性表。u允许允许删除删除的一端称为的一端称为队首（队头）队首（队头）u允许允许插入插入的一端称为的一端称为队尾队尾4.3.2 几种典型的数据结构几种典型的数据结构2023/4/453计算机科学导论计算机科学导论533.3.队列队列4.3.2 几种典型的数据结构几种典型的

38、数据结构 a a1 1 a a2 2 a an n队头队头出队出队队尾队尾入队入队2023/4/454计算机科学导论计算机科学导论4.3.2 几种典型的数据结构几种典型的数据结构2023/4/455计算机科学导论计算机科学导论4.3.2 几种典型的数据结构几种典型的数据结构2023/4/456计算机科学导论计算机科学导论4.4.树树在树型结构中，每个数据元素称为一在树型结构中，每个数据元素称为一个结点，除了唯一的根结点外，其他每个结点，除了唯一的根结点外，其他每个结点都有且仅有一个父结点，每个元个结点都有且仅有一个父结点，每个元素可以有多个子结点。素可以有多个子结点。树结构在客观世界中广泛存在

39、，如树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都人类社会的族谱和各种社会组织机构都可用树形象表示可用树形象表示。4.3.2 几种典型的数据结构几种典型的数据结构2023/4/457计算机科学导论计算机科学导论4.3.2 几种典型的数据结构几种典型的数据结构2023/4/458计算机科学导论计算机科学导论5.5.图图图形结构是一种比树型结构更复杂的非线图形结构是一种比树型结构更复杂的非线性结构。在图形结构中，每个数据元素称性结构。在图形结构中，每个数据元素称为一个顶点，为一个顶点，任意两个顶点之间都可能相任意两个顶点之间都可能相关关，这种相关性用一条边来表示，顶点之，这种相关

40、性用一条边来表示，顶点之间的邻接关系可以是任意的间的邻接关系可以是任意的。4.3.2 几种典型的数据结构几种典型的数据结构2023/4/459计算机科学导论计算机科学导论2023/4/460计算机科学导论计算机科学导论4.3.2 几种典型的数据结构几种典型的数据结构1 1线性表线性表2 2栈栈3 3队列队列4 4线性表线性表5 5图图2023/4/461计算机科学导论计算机科学导论4.3.3 查找查找u查找是指根据给定的某个值，在查找表中查找是指根据给定的某个值，在查找表中确定一确定一个其关键字等于给定值的记录或数据元素个其关键字等于给定值的记录或数据元素。u若表中存在这样的一个记录，则称查找

41、是成功的，若表中存在这样的一个记录，则称查找是成功的，此时查找的结果为给出整个记录的信息，或指示此时查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置；该记录在查找表中的位置；u若表中不存在关键字等于给定值的记录，则称查若表中不存在关键字等于给定值的记录，则称查找失败，此时查找的结果可给出一个找失败，此时查找的结果可给出一个“空空”记录记录或或“空空”指针。指针。2023/4/462计算机科学导论计算机科学导论1 1顺序查找顺序查找2 2二分查找二分查找3 3分块查找分块查找4.3.3 查找查找2023/4/463计算机科学导论计算机科学导论1 1顺序查找顺序查找 顺序查找是在一个队

42、列中顺序查找是在一个队列中找出与给定关键找出与给定关键字相同数值的具体位置字相同数值的具体位置。原理是让关键字与队列中的数原理是让关键字与队列中的数从第一个开从第一个开始逐个比较始逐个比较，直到找出与给定关键字相同的数，直到找出与给定关键字相同的数值为止值为止。4.3.3 查找查找2023/4/464计算机科学导论计算机科学导论2 2二分查找二分查找l将表将表中间位置中间位置记录的关键字与查找关键字进行记录的关键字与查找关键字进行比较，比较，l如果两者相等，则查找成功；否则如果两者相等，则查找成功；否则利用中间位利用中间位置记录将表分成前、后两个子表置记录将表分成前、后两个子表，l如果中间位置

43、记录的关键字小于查找关键字，如果中间位置记录的关键字小于查找关键字，则进一步查找前一子表（假定队列是从小到大则进一步查找前一子表（假定队列是从小到大排列），否则进一步查找后一子表。排列），否则进一步查找后一子表。l重复以上过程，直至找到满足条件的记录，使重复以上过程，直至找到满足条件的记录，使查找成功，或直至子表不存在为止，此时查找查找成功，或直至子表不存在为止，此时查找失败。失败。4.3.3 查找查找2023/4/465计算机科学导论计算机科学导论一个有序表中有一个有序表中有1313个记录，记录的关键字序列个记录，记录的关键字序列为（为（7 7，1414，1818，2121，2323，292

44、9，3131，3535，3838，4242，4646，4949，5252），给定值），给定值k k为为1414，在表中查找关，在表中查找关键字与键字与k k相等的记录。相等的记录。2023/4/466计算机科学导论计算机科学导论2023/4/467计算机科学导论计算机科学导论3 3分块查找分块查找分块查找又称索引顺序查找，它是顺序查找的分块查找又称索引顺序查找，它是顺序查找的一种改进方法。一种改进方法。分块的原则是将分块的原则是将n n个数据元素个数据元素“按块有序按块有序”划分划分为为m m块（块（m nm n）。）。每一块中的结点不必有序，每一块中的结点不必有序，但块与块之间必须但块与块之

45、间必须“按块有序按块有序”；即第；即第1 1块中任块中任一元素的关键字都必须小于第一元素的关键字都必须小于第2 2块中任一元素的块中任一元素的关键字；而第关键字；而第2 2块中任一元素又都必须小于第块中任一元素又都必须小于第3 3块中的任一元素等。块中的任一元素等。4.3.3 查找查找2023/4/468计算机科学导论计算机科学导论3 3分块查找分块查找分块查找是首先选取各块中的分块查找是首先选取各块中的最大关键字最大关键字构成构成一个索引表；一个索引表；然后查找分两个部分：先对索引表进行二分查然后查找分两个部分：先对索引表进行二分查找或已确定待查记录在哪一块中；最后在已确找或已确定待查记录在

46、哪一块中；最后在已确定的块中用顺序法进行查找。定的块中用顺序法进行查找。4.3.3 查找查找2023/4/469计算机科学导论计算机科学导论2023/4/470计算机科学导论计算机科学导论1 1顺序查找顺序查找2 2二分查找二分查找3 3分块查找分块查找4.3.3 查找查找2023/4/471计算机科学导论计算机科学导论4.3.4 排序排序排序是计算机程序设计中的一种重要操作。排序是计算机程序设计中的一种重要操作。简单地说，排序就是要整理文件中的记录，简单地说，排序就是要整理文件中的记录，使之按使之按关键字递增关键字递增(或递减或递减)次序排列起来次序排列起来。2023/4/472计算机科学导

47、论计算机科学导论4.3.4 排序排序如果按排序过程中依据的不同原则对内部排如果按排序过程中依据的不同原则对内部排序方法进行分类，则可分为序方法进行分类，则可分为直接插入排序、直接插入排序、冒泡排序、快速排序冒泡排序、快速排序等。等。2023/4/473计算机科学导论计算机科学导论1 1直接插入排序直接插入排序基本操作是将一个记录插入到已排好序的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增有序表中，从而得到一个新的、记录数增1 1的有序表。的有序表。4.3.4 排序排序2023/4/474计算机科学导论计算机科学导论1 1直接插入排序直接插入排序基本思想是：基本思想是

48、：每步将一个待排序的对象，按其每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对关键码大小，插入到前面已经排好序的一组对象的象的适当位置适当位置上，直到对象全部插入为止。上，直到对象全部插入为止。简言之，边插入边排序，保证子序列中随时都是排好简言之，边插入边排序，保证子序列中随时都是排好序的序的。4.3.4 排序排序2023/4/475计算机科学导论计算机科学导论初始关键字序列：初始关键字序列：【13】,6,3,31,9,27,5,11第一次排序：第一次排序：【6,13】,3,31,9,27,5,11第二次排序：第二次排序：【3,6,13】,31,9,27,5,11第三次排序

49、：第三次排序：【3,6,13，31】,9,27,5,11第四次排序：第四次排序：【3,6,9,13，31】,27,5,11第五次排序：第五次排序：【3,6,9,13，27,31】,5,11第六次排序：第六次排序：【3,5,6,9,13，27,31】,11第七次排序：第七次排序：【3,5,6,9,11，13，27,31】例：例：关键字序列关键字序列T=（13，6，3，31，9，27，5，11），），请写出直接插入排序的中间过程序列。请写出直接插入排序的中间过程序列。注：注：方括号方括号 中为已排序记录的关键字，下划横线的中为已排序记录的关键字，下划横线的 关键字关键字表示它对应的记录后移一个位置

50、。表示它对应的记录后移一个位置。2023/4/476计算机科学导论计算机科学导论2 2冒泡排序冒泡排序冒泡排序是通过冒泡排序是通过交换两个元素交换两个元素实现的，它的思想是：设有数组实现的，它的思想是：设有数组An+1An+1(n(n为序列中元素个数为序列中元素个数)，第一趟在序列，第一趟在序列(A0-An-1)(A0-An-1)中从前往中从前往后进行两个元素的比较，如后者小，则交换，比较后进行两个元素的比较，如后者小，则交换，比较n-1n-1次；次；第第一趟排序结束，最大元素被交换到一趟排序结束，最大元素被交换到An-1An-1中中(即沉底即沉底)，下一趟，下一趟排序只要在子序列排序只要在子