第3章计算机导论课件

计算机导论第三章算法与数据结构学习目标理解算法的基本概念理解数据结构的基本概念掌握算法的表示方法了解常用的几种数据结构了解算法的设计目标和方法任务1：了解算法的基本概念软件的核心是程序，程序包含两方面内容：1．数据描述：定义数据结构。

2．操作描述：说明操作及操作步骤，即算法

数据是操作的对象，操作的目的是对数据进行加工处理得到想要的结果。程序通过算法处理数据获得有效结果，解决现实世界中存在的各种问题。任务1：了解算法的基本概念算法——是解决问题所需的操作步骤的集合，是程序设计的根本。算法应正确地制定操作执行的步骤。算法制定的操作步骤应具有：确定性、有穷性和可行性。算法有输入和输出。任务1：了解算法的基本概念总结：算法的确定性、有穷性和可行性，使得容易把算法转变为程序，程序的每一步骤都可以在计算机上实现。计算机在合理的时间范围内，通过依序执行算法制定的步骤，处理算法的输入数据，从而获得输出数据。任务1：了解算法的基本概念【例3-1】求5最一般的计算方法或操作步骤是：步骤1：求1×2，得到结果2步骤2：用步骤1所得积2乘以3，得到结果6。步骤3：用步骤2所得积6乘以4，得到结果24。步骤4：用步骤3所得积24乘以5，得到最终结果120。简单的算法例子---1任务1：了解算法的基本概念简单的算法例子---2【例3-2】求5！步骤1：令p=1步骤2：令i=2步骤3：使p×i，乘积依然存入变量p中，可表示为：p←p×i步骤4：使i的值加1，可表示为：i←i+1步骤5：如果i≤5，则返回步骤3的位置，从步骤3开始再次执行本算法。如果i＞5，则算法结束。【例3-3】设一次测验中满分100分，有30个学生，当学生成绩大于60时，打印“passed”；成绩小于60时，打印“failed”。设n表示学生的个数，变量i表示第i个学生，变量gradei表示第i个学生的成绩。算法如下：步骤1：i＝1；步骤2：输入gradei；步骤3：i＝i+1；步骤4：如果i>30，结束输入，进行下一步骤5；否则，返回步骤2；步骤5：i＝1；步骤6：如果gradei>=60，则打印“passed”；步骤7：如果gradei<60，则打印“failed”；步骤8：i＝i+1;步骤9：如果i<=30，则返回步骤6，否则算法结束。任务2：算法的表示算法有多种表示方法，常用的有：

自然语言

流程图

伪码

任务2：算法的表示自然语言自然语言就是人们日常使用的语言，可以是英语、汉语，也可以是其它语种。自然语言的优点是丰富且不拘泥于形式，灵活自由、通俗易懂。但它的缺点也很明显，文字冗长不够简明且缺乏结构，尤其是容易产生歧义。任务2：算法的表示流程图流程图是算法的图形表示，由一些具有特定意义的图形符号组成。它直观形象，可读性好。美国国家标准协会ANSI(AmericanNationalStandardsInstitute)规定了一些常用的流程图符号，已成为世界各国程序工作者普遍采用的标准

任务2：算法的表示伪码

伪码是一种非正式的语言，采用文字和非图形符号表示算法，介于自然语言和计算机语言之间。它如同一篇文章，自上而下书写，每一行或多行表达一个基本操作。任务2：算法的表示用伪码表示算法：求5！Begin置p的初值为1置i的初值为2 whilei≤5p←p×ii←i+1endwhile打印p的值End用伪码表示例3-3

Begini1Whilei<=30输入gradeii1+1Endwhilei1Whilei<=30Ifgradei>＝60Print“passed”ElsePrint“failed”Endifii+1Endwhileend任务3：数据结构的基本概念程序是对数据和算法的描述。数据是算法操作的对象，操作处理初始数据使数据发生变化，产生结果数据。数据是程序的基础。数据结构的基本概念如下：“数据”是客观事物的符号表示，计算机科学中指所有能输入到计算机中并能被计算机程序处理的符号的总称，包括数字、字符、声音、图形、图像等。计算机进行数据输入和输出时使用的基本数据单位称为“数据元素”。一个数据元素可由多个数据项组成。“数据项”是不可分割的最小数据单位。“数据对象”是性质相同的数据元素的集合，是数据的一个子集。“数据类型”指数据的内在形式，即数据在加工计算中的特征。数据类型决定了数据的取值范围和可以对数据进行的操作。任务3：数据结构的基本概念

图书信息表书

号

书

名作

者借阅状态TP316450数据库技术何立功已借出TP316457数据结构严蔚敏未借出TP316250C程序设计和

明已借出…图书管理中常用的是对图书借阅情况的管理，这就需要分析和却额定有关图书的数据结构，建立图书的数据对象；图书的数据对象由图书的数据元素组成，每个图书数据元素表示一本书的信息，即是这里的一行。书号、书名、作者、借阅状态称为基本项，即数据项，它是有独立意义的最小标识单位；数据结构数据结构包括三个方面的内容：一组数据中各数据之间的逻辑关系；这组数据在计算机中的存储方式；对这组数据所能施加的运算的集合。数据的逻辑结构描述的是数据之间的逻辑关系。数据的逻辑结构包括四种：集合、线性结构、树形结构和图形结构。数据的存储结构又称为数据的物理结构，是数据在计算机中的表示或映像数据的存储结构有两种，分别为顺序存储结构和链式存储结构。数据的运算集合数据处理必涉及到相关的运算，可以有插入、删除、查找等操作。任务3：数据结构的基本概念图书信息表的顺序存储结构TP316450数据库技术何立功已借出TP316457数据结构严蔚敏未借出TP316250C程序设计和

明已借出任务3：数据结构的基本概念图书信息表的链式存储结构任务4：线性表线性表是最常用且最简单的一种数据逻辑结构，定义n(≥0)个数据元素的有限序列,记作(a1,…ai-1,ai,ai+1,…,an)其中，ai

是表中数据元素，其中a1是开始结点，an是终端结点。

n

是表长度(n=0时称为空表)。逻辑特征n>0时有且仅有一个“第一个”数据元素有且仅有一个“最后一个”数据元素除第一个数据元素外，其它元素有且仅有一个直接前驱除最后一个数据元素外，其它元素有且仅有一个直接后继任务4：线性表在计算机内，可以用不同的方式表示线性表，其中最简单和最常见的是用一组地址连续的存储单元依次存储线性表的数据元素，构成线性表的顺序存储结构。对于顺序存储结构线性表，逻辑上相邻，物理上也相邻。线性表第一个数据元素的位置，称为线性表的起始位置或基地址。确定了基地址的顺序存储结构线性表，其中任意元素的存储位置都可以通过公式计算获得。线性表的顺序存储结构是一种随机存取结构。对这种存储结构的线性表进行插入或删除操作时，就需要移动大量数据元素。任务4：线性表

顺序存储结构线性表的插入过程任务4：线性表顺序存储结构线性表的删除过程线性表的链式存储结构：称为线性链表，线性链表中的结点是数据元素及其逻辑关系在计算机中的映像。结点的数据域表示数据元素，结点的指针域描述数据元素间的逻辑关系。整个链表的存取必须从头指针开始进行，头指针指示链表的第一个结点、即第一个数据元素的存储位置。对线性表中任意元素的访问通常也只能由头指针开始顺序进行，由于可以通过改变结点指针域的值来改变数据元素间的逻辑关系，对线性链表进行插入删除操作无须移动大量元素。任务4：线性表链式存储结构线性表的插入过程abdef∧h插入新结点前cs

新结点c插入新结点c后任务4：线性表链式存储结构线性表的删除过程abdef∧h删除结点d前f∧abdeh删除结点d后任务5：栈栈是限定仅在表尾进行插入和删除操作的线性表。对栈来说表尾端有其特殊的含义，称为栈顶，相应的表头端称为栈底。不含元素的空表，称为空栈。假设栈S有（a1，a2，…，an）共n个数据元素，即S=(a1，a2，…，an)，则称a1为栈底元素，an为栈顶元素。栈中元素按照a1，a2，…，an的顺序进栈，an，an-1，…a2，a1的顺序退栈。也就是说，退栈的第一个元素应为栈顶元素。栈的修改是按照“后进先出”的原则进行。因此，栈又称后进先出（LastInFirstOut）的线性表，简称LIFO。

任务5：栈栈的示意图任务5：栈栈也有两种存储结构栈的顺序存储结构，简称顺序栈。栈的链式存储结构简称链栈，一个链栈由栈顶指针唯一确定。

对栈这样一种元素多变的数据结构来说，链式存储结构显得更适宜。任务5：栈栈顶指针和数据元素间的关系空栈栈中1个元素任务5：栈栈顶指针和数据元素间的关系栈满退出两个元素任务5：栈链栈示意图任务6:队列队列是一种先进先出（FirstInFirstOut）的线性表，简称为FIFO。队列只允许在表的一端进行插入操作，而在表的另一端进行删除操作。在队列中，将允许插入元素的表端，称为队尾。允许删除元素的表端，称为队头。假设队列Q有（a1，a2，…，an）共n个数据元素，即Q=(a1，a2，…，an)，

a1就是队头元素，an则是队尾元素。数据元素是按照a1，a2，…，an的顺序进入队列的，也只能按照这个顺序退出队列。也就是说，只有在a1，a2，…，an-1都离开队列以后，an才能退出队列。任务6:队列出队列a1a2…

an

入队列队头队尾队列的示意图链队列示意图任务7:树树型结构是重要的非线性数据结构，其中以树和二叉树最常用。树在客观世界中广泛存在，在计算机领域中也有广泛的应用。树是n（n≥0）个结点的有限集。在一棵非空树中：①有且仅有一个特定的称为根的结点；②当n＞1时，其余结点可分为m个互不相交的有限集T1，T2，…，Tm，其中每一个集合本身又是一棵树，并且称为根的子树。任务7:树只有根结点的树一般的树任务7:树二叉树的5种基本形态空二叉树仅有根结点的二叉树右子树为空的二叉树左、右子树非空的二叉树左子树为空的二叉树任务8:图图是一种较线性结构和树形结构更为复杂的数据结构。图的数据元素之间的关系可以是任意的，任意两个数据元素间都可能相关。在线性表中，数据元素之间的逻辑关系为线性关系，每个数据元素只有一个直接前驱和一个直接后继。在树中，数据元素之间存在明显的层次关系。任务8:图图中的数据元素通常称为顶点。有向图无向图图没有顺序映象的存储结构，通常都采用链式存储结构，且其每个结点包含一个数据域和多个指针域，形成多重链表，以利于表达图的顶点间的任意关系。任务9:算法的设计算法可分为数值计算和非数值计算两类。各种数值计算都有比较成熟的算法可供选用。通常应用中需要设计的是有关非数值计算问题的算法，其操作对象为诸如表、树、图之类的数据结构。在计算机中查找和排序是典型的非数值计算问题。通常一个“好”的算法应具备正确性、可读性和健壮性，并满足效率与存储量需求。任务9:算法的设计正确性：设计算法最先应该达到的是正确性目标。另一方面，正确的算法不应含有语法或逻辑错误，应能无误地处理合法输入数据，得到满足要求的结果。任务9:算法的设计可读性：算法的主要目的是为了人们阅读和交流，其次才是机器执行。良好的可读性有助于人们对算法的正确理解，同时也是算法具备可靠性和可维护性等性能指标的基础。

算法应有良好的“文体”，结构清楚、层次分明、思路清晰。通常一个“好”的算法应具备正确性、可读性和健壮性，并满足效率与存储量需求。任务9:算法的设计算法的效率指的是算法执行时间算法的存储量需求指的是算法执行时所需的最大存储空间。效率和存储量需求都与算法所解决问题的规模或复杂度有关。对于同一个问题有多个算法可以解决，执行时间短的算法效率高。而效率高的算法有时可能需要相对更大的存储空间。时间和空间常常是对立的统一体，需要权衡以作出取舍，或者用空间的代价换取时间，或者用时间的代价换取空间。任务9:算法的设计---查找和排序算法所谓“查找”即为在一个含有众多数据元素的数据结构中找出某个特定的数据元素，特定的数据元素可以通过关键字标识。关键字是数据元素中某个或某些数据项的值，用来唯一标识一个数据元素。即不同的数据元素其关键字不相同。查找某个数据元素的方法，依赖于数据元素所存在的数据结构。也就是说，在计算机