大学计算机基础第09讲教案 数据结构与算法

第9讲数据结构与算法

课时内容数据结构与算法授课时间课时4

0数据结构的概念和描述方法。

0程序设计的概念；结构化程序设计的基本原则。

教学目标

0算法的概念和描述方法。

0程序设计的基本控制结构和基本方法。

0掌握程序设计•的基本概念

教学重点

0掌握程序设il•的基本方法

0掌握算法的持征及描述方法

教学难点

0掌握结构化程序设计的三种基本结构

1、教学思路：从数据结构的基本概念开始，由浅入深地介绍数据结构、募法的基本概

念、常用算法、程序、程序设计、程序设计的基本控制结构、常用的程序设计语言

等知识，通过程序设计的实例介绍，让读者了解程序设计的基本方法和步骤。2、

教学手段：

（1）通过演示讲解基础知识，讲解结束后进行练习；

教学设计

（2）对于重点操作可以着重演示，并加强举例说明：

（3）通过一个简单明了的例子来说明程序的重要性及简要的实现方法和步骤（如图

书馆的图书管理系统、学生成绩管理系统等学生比较熟悉的系统）。

3、教学资料及要求：让学生了解程序设计的基本控制结构，并对程序设计的基本方法

和步骤有一个初步的认识。

教学内容

知识回顾：在前而讲解了网络的基本概念、功能、组成、分类、相关的协议、接入网络的方法、IP

地址、WWW服务、搜索引擎等。

讨论问题：1.什么是计算:机程序？

2.你感觉程序能峥做什么事情？结合实际应用进行举例说明。

内容大纲：具体可结合本章的PPT课件进行配合讲解。

任务一数据结构

任务要求：了解数据结构的基本概念；

相关知识：数据结构是计第:机存储、组织数据的方式。

任务实现：

（-）数据结构概述

据结构有两个要素•：一是数据元素的集合，通常记为山二是d上的关系，它反映了数据元素之

间的关系，通常记为s0一个数据结构可以表示成：

b=（d,s）

式中，b表示数据结构。用s反映d中各数据元素之间的关系。数据结构研究的对象是数据的逻

辑结构和数据的物理结构。

1.数据的逻辑结构

2.数据的物理结构

（二）数组

1.一维数组

一维数组是最简单的数组，只有一个下标，其逻辑结构是线性表。

2.二维数组

与一维数组对应，二维数组有两个卜标，分别表示行、列信息。

（三）链表

1.单徒表：单链表是仅有一个数据域和一个指针域。

2.双向链表：在某些应用中，对线性链表中的每个节点设置两个指针：一个称为左指针，用

以指向其前驱节点；另一个称为右指针，用以指向其后继节点。这样的链表称为双向链表。

（四）栈

栈是一种特殊的线性表，是限定只在一端进行插入和删除的线性表。

栈的基本运算有3种：入栈、退栈和读栈顶元素。

（五）队列

队列是只允许在一端进行删除，在另一端进行插入的顺序表。通常将允许删除的这一端称为队

头，允许插入的这一端称为队尾。队列需要用两个指针进行管理：一个是队头指针，指向队头元

素：另一个是队尾指针，指向下一个入队元素的存储位置。

（六）树和二叉树

1.树的定义

2.树是由n（n，0）个有限节点组成的一个具有层次关系的集合。把它叫作“树”，是因为它

看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

3.树的基本概念：根，父节点，子节点，叶子节点，度，深度，子数。

4.二叉树：在二叉树中，每一个节点的度最大为2,即所有子树（左子树或右子树）也均为二

叉树。另外，二叉树中的每个节点的了树被明显地分为左了树和右了树。在二叉树中，个节点可

以只有左子树，也可以只有右子树。二叉树的四个性质。

（七）图

图是由顶点的有穷非空集合和顶点之间边的集合组成的。图中每一条边的两个顶点互为邻接

点。如果图中的每条边是有方向的，则称该图是有向图。有向图中的边也称为弧，通常用尖括号表

示。如果图中的每条边是没有方向的，则称该图是无向图。

图的遍历方法有两种：一种是深度优先搜索遍历（Depth-FirstSearch,DFS）,另一种是广度

优先搜索遍历（Breadth-FirstSearch,BFS）。

任务二算法概述

任务要求：了解算法的概念、特征、描述方法。

相关知识：如何完成葬法的设计与实现。

任务实现：

（-）算法的概念

算法是程序设计的精髓，它的定义是在有限步骤内求解某一问题所使用的一组定义明确的规

则。学习算法要先了解以卜五个方面的内容。

（1）设计算法。算法设计工作是不可能完全自动化的，应学习和了解已经被实践证明有用的一

些基本的算法设计方法，这些基本的设计方法不仅适用于计算机科学，而且适用于电气工程、运筹

学等领域。

（2）表示算法.描述算法的方法有多种形式，如自然语言和算法语言,各自有适用的环境和特

点°

（3）确认算法。算法确认的目的是使人们确信这一算法能够正确无误地工作，即该算法具有可

计算性。正确的算法用计算机算法语言描述，构成计算机程序，计算机程序在计算机上运行;得到

筑法运算的结果。

（4）分析算法。算法分析是对一个算法需要多少计算时间和存储空间进行定量的分析。分析算

法可以预测这一嵬法适合在什么样的环境中有效运行，对解决同一问题的不同算法的有效性做出比

较。

（5）验证算法。用计算机语言描述的算法是否可计算、是否有效合理，需对程序进行测试，

测试程序的工作主要包括调试和制作时空分布图。

（二）算法的特征

（1）确定性。算法的每一种运算必须有确定的意义，它规定运算所执行的动作应该是无歧义

的，并且目的是明确的。

（2）可行性。要求算法中有待实现的运算都是基本的，每种运算至少在原理上能由人用纸和笔

在有限的时间内完成。

（3）输入。一个算法可能有多个输入，在算法运算开始之前给出算法所需数据的初值，这些输

入取自特定的对象集合。

（4）输出。作为算法运算的结果，一个算法会产生一个或多个输出，输出是同输入有某种特定

关系的量。

（5）有穷性。一个算法会在执行了有限步的运算后终上。

（三）算法的描述

（1）自然语言

自然语言就是日常使用的语言，可以使用中文，也可以使用英文。用自然语言描述的算法，通

俗易懂，但是文字冗长，准确性不好，易于产生歧义性。因此，一般情况下不提倡用自然语言来描

述算法。

（2）伪码

伪码不是一种现实存在的编程语言。使用伪码的目的是为了使被描述的算法可以容易地以任何

一种编程语言实现。它可能综合使用多种编程语言中语法、保留字，甚至会用到自然语言。因此，

伪代码必须结构清晰，代码简单，可读性好，并且类似自然语言。

【例1】描述“对两个数按照从大到小的顺序输出”的算法。

伪码

Begin：

InpvtrMlAftft-hA//I；\-A

人数据》B〃^人Eil'it.r.B

If（A>B）

（

Prim〃・人8

Else

PrintBA〃愉BA

End

对于例题可以进行简单的介绍。

（3）流程图

流程图是•种传统的算法表示法，它利用几何图形的框来代表各种不同性质的操作，用流程线

来指示算法的执行方向。

I喻人网T”・便亶中

.由4・6II㈱出d/

（结束）

流程图

（4）N-S结构图

N-S结构图是美国的两位学者IkeNassi和BenSchneiderman提出的。他们认为，既然任何算法

都是由顺序结构、选择（分支）结构和循环结构3种基本程序结构组成的，所以各基本结构之间的

流程线就是多余的，因此，”S图用一个大矩形框来表示算法.它是算法的一种结构化描述方法，

是一种适合于结构化程序设计的流程图，求两个数按大小顺序输出的N-S结构图如图所示。

输入的个股，保存到交Rd依8中

■出喻出8,4

N-SIgIM

任务三常用算法

任务要求：了解几个常用算法。

相关知识：累加求和算法，连乘求积算法，求最值算法，冒泡排序算法，查找算法，统计算

法，常见的人工智能算法。

任务实现：

（-）累加求和算法

定义一个变量s（往往初值为0）作为累加器使用，再定义一个变量用来保存加数。一般在累加

算法中的加数都是有规律可循的，可结合循环程序来实现。

（二）连乘求积算法

设一个变量P，作为累乘器使用，初值一般为1;设一个变量k用来保存每次需要乘的乘数，在

循环体中执行P=P*k的语句即可。

求10!=1X2X3X…X10的结果-

（三）求最值算法

求解此类问题的基本步骤可以概括如卜"

①定义x代表N个数中的一个数。

②定义一个存放最大值的变量max,定义一个存放最小值的变量min。

③分别令max二所有数据中的第1个数，min=所有数据中的第1个数。

④构建循环体,然后将x与max比较,如果x比max大，令uax=x：将x与min比较，如果x比min

小，令min=x。

⑤构建循环条件，根据问题的具体要求，选用相应的循环语句。

⑥输出max和min的值。

（四）排序算法

查找也称为检索，是在较大的数据集中找出或定位某些数据的过程，即在大量的信息中寻找一

个特定的信息元素。在计算机中进行查找的方法是根据表中的记录的组织结构确定的，被用于查找

的数据元素的属性一般称为关键字。

顺序查找也称为线性查找，是一种最简单的查找方法，可用于有序列表，也可用于无序列

表。

其基本思想是：从查找表（数据结构线性表）的一端开蛤，顺序扫描线性表，依次将扫描到

的节点关键字同给定值key相比较，如果当前扫描到的节点关理字同key相等，则表示查找成功；如

果扫描结束后，没有找到关健字等于key的节点，表示查找失败。

（五）查找算法

查找也称为检索，是在较大的数据集中找出或定位某些数据的过程，即在大量的信息中寻找一

个特定的信息元素。在计算机中进行查找的方法是根据表中的记录的组织结构确定的，被用于查找

的数据元素的属性一般称为关键字。

顺序查找也称为线性查找，是一种最简单的查找方法，可用于有序列表，也可用于无序列

表。

（六）统计算法

统计算法一般用于求解特定值问题。

输入一串字符，统计其中的字母个数、数字个数和其他字符的个数。

（七）常见的人工智能算法

I.线性叵I归（LinearRegression）

2.逻辑回归（LogisticRegression）

3.决策树（DecisionTree）

4.随机森林（RandomForest）

5.支持向量机（SVM）

6.K最近邻（KNN）

7.K均值聚类（KMeans）

8.人工神经网络（AXN）

9.卷积神经网络（C'N）

10.生成对抗网络（GAN）

任务四程序设计念

任务要求：了解程序设计的基本概念；

相关知识：程序的概念非常普遍.简单地说，程序可以看作对•系列动作的执行过程的描述。

任务实现：

计算机程序是指为了得到某种结果而由计算机等具有信息处理能力的装置执行的代码化指令序列。

由丁程序为订算机规定了“算的步骤，因此为了更好地使用il算机，我们必须先来了解程序的

几个性质。

（1）目的性：程序必须有一个明确的目的。

（2）分步性：程序给出了解决问题的步骤。

（3）有限性：解决问题的步骤必须是有限的。如果有无穷多个步骤，那么在计和机上就无法实

现。

（4）可操作性：程序总是实施各种操作于某些对象的，它必须是可操作的。

（5）有序性：解题步骤不是杂乱无章地堆积在一起，而是要按一定顺序排列的（这是最重要的

一点）。

（一）了解程序设计的概念

目前的冯•诺依星型计算机，还不能直接接受任务，而只能按照人们事先确定的方案，执行人

们规定好的操作步骤。通常计算机处理一个问题（程序设计）.需要经过以下步骤。

（1）分析问题，确定解决方案。当一个实际问题提出后，应首先对以下问题作详细的分析：需

要提供哪些原始数据，需要对其进行什么处理，在处理时需要有什么样的硬件和软件环境，需要以

什么样的格式输出结果等。在以上分析的基础上，确定相应的处理方案。

（2）建立数学模型。建立数学模型就是要把处理的问题数学化、公式化，有些问题比较直观，

可不去讨论数学模型问题：有些问题符合某些公式或有现成的数学模型可以直接利用：但是多数问

题都没有对应的数学模型可以直接利用，这就需要创建新的数学模型，如果有可能还应对数学模型

做进一步的优化处理。

（3）确定算法（算法设计）。计算机的算法比较灵活，一般要优选逻辑简单、运算速度快、精

度高的算法用于程序设计。此外，还要考虑内存空间占用合理、编程容易等特点。算法可以使用伪

代码或流程图等方法进行描述。

（4）编写源程序。要让计算机完成某项工作，必须将已设计好的操作步骤以若干条指令组成的

程序的形式刊写出来，让计算机按程序的要求一步一步地执行。

（5）程序调试。程序调试就是为了纠正程序中可能出现的错误，它是程序设计中非常重要的一

步。没有经过调试的程序，很难保证没有错误，就是非常熟练的程序员也不能保证这点，因此，

程序调试是不可缺少的重:要步骤。

（6）整理资料。程序编写、调试结束以后，为了使用户能够了解程序的具体功能，掌握程序的

运行操作，有利于程序的修改、阅读和交流，必须将程序设计的各个阶段形成的资料和有关说明加

以整理，写成程序说明I。

（二）结构化程序设计的基本原则

结构化程序设计方法的主要原则可以概括为“自顶向下，逐步求精，模块化和限制使用GoT。

语句”。

（1）自顶向下。程序设计时，应先考虑总体，后考虑细节：先考虑全局目标，后考虑局部目

标。即首先把一个复杂的大问题分解为若干相对独立的小问题。

（2）逐步求精。对复杂问题，应设计一些子目标作为过渡，逐步细化。

（3）模块化。一个复杂问题，肯定是由若干个简单的问题构成的。模块化就是把程序要解决的

总目标分解为子目标，再进•步分解为具体的小目标。我们可以把每一个小目标叫作一个模块。

（4）限制使用GoTo语句。

（一）面向对象的程序设计

面向对象的程序设计（ObjectOrientedProgramming,OOP）是20世纪80年代提出的，它汲取

了结构化程序设计中好的思想，引入了新的概念和思维方式。通常，在面向对象的程序设计风格

中，会将一个问题分解为一些相互关联的子集，每个子集内部都包含了相关的数据和函数。同时，

它会以某种方式将这些子集分为不同等级，而一个对象就是己定义的某个类型的变量。

面向对象技术具有许多E月显的优点,书要体现在以下3个方面.

（1）可重用性。

（2）可维护性。

（3）表示方法的一致性。

（三）程序设计的基本结构

1.顺序结构

顺序结构要求程序中的各个操作按照它们出现的先后顺序执行。顺序结构是一种简单的程序设

计结构，它是最基本、最常用的结构，是任何从简单到复杂的程序的主体基本结构，其流程图如图

所示。

(a)流程图(b)N-S结构图

顺序结构的流程图

举例：

(1)输入圆的半径，求面积。

<2)输入矩形的长和宽，求其而枳。

(3)买水果：苹果2元1斤，香蕉3元1斤，输入两者的斤数后给出应付金额，然后输入实付金

额后再输出找零。

2.选择结构

(1)两路分支选择结构

两路分支选择是指根据判断结构入口点处的条件来决定下一步的程序流向。如果条件为真则执

行语句组1,否则执行语句组2。值得注意的是，在这两个分支中只能选择一条且必须选择一条执

行，但不论选择了哪一条分支执行，最后流程都一定到达结构的出口点处，其流程图如图所示。

语句组2

(a)流程图

(b)N-S结构图

两路分支选择结构的流程图

举

①

输入两个数，输出其较大者。

②

③断一个数是否为奇数。

④输入一个数，判断其是否小于0。

输入三个数，输出其最大者。

(2)多路分支选择结构

多路分支选择是指程序流程中遇到了多个分支，程序执行方向将根据条件确定。如果条件1为

真，则执行语句组1,如果条件2为真，则执行语句组2,如果条件n为真，则执行语句组n。如果所

有分支的条件都不满足，则执行语句组n+1(该分支可以缺省)。

不论选择了哪一条分支，最后流程要到达同一个出口处。多路分支选择结构的流程如图所示。

语句组।|语句扭2|……|语句的〃|语句组/1

(a)流程图(b)N-S结构图

多路分支选择结构的流程

举例：

①输入三个数，输出其最大者。

②输入一元二次方程的系数a,b,c,求方程的根。

可根据学生的程度及掌握的情况是否讲解虚根。

③输入三个数，输出其最大者。

3.循环结构

所谓循环，是指一个客观事物在其发展过程中，从某一环节开始有规律地反复经历相似的若干

环节的现象。循环的主要环节具有“同处同构”的性质，即它们“出现位置相同，构造本质相

同”。

下面介绍两种循环结构：''当"型循环和“直到”型循环。

①“当”型循环是指先判断条件，当满足给定的条件时执行循环体，并且在循环终端处流程

自动返回到循环入口：如果条件不满足，则退出循环体直接到达流程出口处。“当”型循环结枸的

流程如图所示。

②“直到”型循环是指从结构入口处直接执行循环体，在循环终端处判断条件，如果条件不

满足，则返回入口处继续执行循环体，直到条件为真时才退出循环到达流程出口处。“直到”型循

环结构的流程如图所示。

(b)N-S结构图

“当”型循环结构的流程“直到”型循环结构的流程

举例：

①求1+2+3+...+10的和。

②判断一个数是否为素数。

③输入如下的图形。

**1

******123

**********12345

***ojo|c****3f0)C***1234567

***:{eic**^o1c123456789

（四）程序设计语言简介

1.机器语言

2.汇编语言

3.高级语言

用高级语言编写的程序需耍被翻译成目标程序（即机器语言程序）才能被计算机执行。将高级语言翻

译为机器语言的方式主要有两种：解释方式和编译方式。

（1）解释方式：让计算机运行解释程序，解释程序逐句取出源程序中的语句，对其进行解释执行，输

入数据，产生结果。解释方式的主要优点是交互性好，调试程序时，程序员能一边执行一边直接改错，能

较快得到一个正确的程序：缺点是逐句解称执行，整体运行速度慢。

（2）编译方式：先运行编译程序，将源程序全部翻译为计算机可直接执行的二进制程序（称为「标程

序），然后让计算机执行目标程序，输入数据，产生结果。编译方式的主要优点是计尊机运行目标程序快，

缺点是修改源程序后必须重新编译以产生新的目标程序。

任务五课程思政

<-）算法设计中的家国情怀与责任担当

案例1：动态规划与国家科技成就

内容：在讲解动态规划算法时，以“北斗卫星导航系