第9章-程序设计基础

第9章程序设计基础9.1程序和程序设计语言9.2程序设计9.3算法9.4数据结构11、计算机程序的概念

指用某种程序设计语言编写的为解决某个实际问题或完成某项任务的指令序列。9.1程序和程序设计语言2PrivateSubcmdComp_Click()

Rem

计算圆的面积

DimrAsSingle，AreaAsSingler=Val(txtInput1.Text)Area=3.14159*r*r

txtCircle.Text=Str(Area)EndSub例:用VB编写的能实现输入圆的半径，计算圆的面积。程序代码：32、程序设计语言及分类

计算机语言是编写计算机程序所用的语言,是人与计算机进行交流的工具。常用语言:VisualBasic、C语言、VisualC++、、Java、Delphi……（1）程序设计语言的定义4（2）计算机语言的分类按照计算机语言的发展过程，分为：机器语言汇编语言低级语言高级语言5低级语言

高级语言计算机语言机器语言汇编语言PASCALCBASICFORTRAN依赖于机器独立于机器6机器语言第一代语言，由0、1代码组成。为了解决某一特定问题，需要选用指令系统中的某些指令，按照要求组织起来就组成程序。

计算机(机器)唯一能直接执行的语言。7例如，计算15+10的机器代码程序如下：

10110000000011110010110000001010111101008汇编语言第二代语言，也称符号语言，便于识别记忆，用助记符表示一条机器指令。如：

ADD表示加法

MOV将数据送寄存器9例如，计算15+10的汇编程序代码：

MOVA，15ADDA，10HLT10高级语言

第三代语言：面向过程语言。与人们日常熟悉的自然语言和数学语言更接近。如：FORTRAN、BASIC、PASCAL、C等。

第四代语言：面向对象程序设计语言。

如：VB、VC++、VFP、Delphi、JAVA等。

其他：LISP（用于人工智能）

PROLOG（用于人工智能）

Ada（用于军事）

11例如，要计算15+10，并输出结果，用VisualBasic编写的程序段：

DimAAsIntegerA=15+10PrintA

123、语言处理程序

（1）语言处理系统语言处理系统的作用是将汇编语言程序或高级语言程序变换成可在计算机上运行的程序,或最终的计算结果，或其他中间形式。13语言处理系统包括：语言处理程序（翻译程序）：用于将汇编语言程序或高级语言程序翻译成目标程序。正文编辑程序：用于建立和修改源程序。连接程序：用于将多个分别编译或汇编过的目标程序和库文件进行组合。装入程序：用于将目标程序装入内存执行。14正文编辑编译连接装入执行结果程序模块1程序模块n……源程序1源程序n目标程序1目标程序n库文件可执行的目标程序语言处理系统15概念

语言处理程序是指预先编制好的起翻译作用的翻译程序。作用将汇编语言和高级语言编制的程序(源程序)翻译成机器语言程序(目标程序)。（2）语言处理程序16源程序语言处理程序（翻译程序）目标程序源程序：用源语言（汇编语言或高级语言）写的有待翻译的程序。目标程序：也称为结果程序，是源程序通过翻译程序加工以后所生成的程序。翻译程序：是指一个把源程序翻译成等价的目标程序的程序。17汇编程序：编译程序

解释程序汇编语言源程序机器语言目标程序高级语言源程序机器语言目标程序语言处理程序的分类根据所处理的语言和处理方法的不同分为三种类型：18编译方式（相当于“笔译”）效率高，高级语言大多采用。实现算法较为复杂。适合于翻译规模大、结构复杂、运行时间长的大型应用程序。

可以一次性地产生高效运行的目标程序，并把它保存在外存上，以备多次执行。如：

PASCAL、C、BASIC、FORTRAN等。

19高级语言源程序编译程序目标程序可执行程序执行结果连接程序编译执行编译方式的工作过程为：20解释方式（相当于“口译”）

边翻译边执行，即逐句扫描、逐句翻译、逐句执行。

解释程序结构简单、易于实现，便于实现人——机对话，但效率较低。如：BASIC等。解释程序高级语言源程序执行结果逐句解释并执行解释程序的工作过程：214、常用计算机语言介绍FORTRANC、C++、VisualC++JavaBasic、VisualBasic

221、程序设计的步骤（1）分析问题和建立模型（2）算法设计（3）编制程序（4）调试运行程序（5）编写程序文档9.2程序设计232、程序设计的方法（1）结构化程序设计（2）面向对象的程序设计24

1、算法的概念算法是为解决某个问题而采用的一组明确的、有一定顺序的步骤。9.3算法252、算法的特征：确定性有穷性可行性有0个或多个输入有1个或多个输出

3、算法的描述：自然语言传统流程图

N-S流程图伪代码26自然语言举例1:

输入半径r,输出其面积。算法描述:

S1:

输入r

S2:

将PI*r*rSS3:

输出面积S

27开始输入X、YX>Y?X

TempY

XTemp

Y否结束输出X、Y是[算法示例1]输入两个数，将大数存于X，小数存于Y。流程图：通过图形表示算法28

伪代码表示

用一种介于自然语言和计算机语言之间的文字和符号来描述算法。举例:

任意输入两个数X,Y,输出其中的大数.算法:

输入X,Y

IFX<YTHENYmax

ELSEXmax

输出max输入X、YX<YTFX

TempY

XTemp

Y输出X、YN-S结构流程图将X、Y按从大到小输出304、算法的评价

对同一问题的求解，可以设计不同的算法。算法评价：

正确易理解易调试和易测试时间复杂度空间复杂度31时间复杂度概念:

一个算法在计算机上运行所花的时间。表示：采用O表示，O表示数量级。

基本参数为n，即算法基本步骤的运算次数。复杂性表达为n的函数，记为O(f(n))。当n增大时，运行时间以正比于f(n)的速度增长。32时间复杂度算法的时间复杂度一般表示为以下几种数量级的形式：

O(1)常数级

O(logn)对数级

O(n)线性级

O(nc)多项式级

O(cn)指数级

O(n!)阶乘级33例：

Fori=1Ton-1y=y+1语句①

Forj=0To（2*n）

x=x+1语句②

NextjNextI语句①执行次数：n-1语句②执行次数:(n-1)*(2n+1)=2n2-n-1时间复杂度:O(n2)34执行算法程序所需的内存空间。包括:算法程序所占的存储空间输入的初始数据所占的空间算法执行中需要的额外存储空间(执行过程中的工作单元、数据结构附加的存储空间等)空间复杂度35

1.数据结构的概念

2.数据的逻辑结构

3.数据的存储结构

4.数据的运算9.4数据结构36数据结构研究对象是程序设计中计算机操作对象以及它们之间的关系和运算，也就是研究如何在计算机中组织数据，如何处理数据。数据结构研究的内容包括三部分：数据的逻辑结构数据的存储结构数据的运算

1.数据结构的概念37数据结构的定义：

指相互间存在一种或多种特定关系的数据元素的集合。或通俗地说，数据结构是带有结构的数据元素的集合。

这里，数据元素是指计算机操作对象的个体。它是数据的基本单位。结构是指数据元素之间的相互关系。

38数据元素具有广泛的含义。一般来说，现实世界中客观存在的一切个体都可以是数据元素。一般情况下，在具有相同特征的数据元素集合中，各个元素之间存在某种关系（即联系）。

39如：描述一年四季的季节名：春、夏、秋、冬表示作为数值的各个数：

18、11、35、23、16

表示家庭成员的各成员：父亲、儿子、女儿

如一年四季中，“春”是“夏”的前趋，“夏”是“春”的后继。

通常把数据元素之间固有的关系简单地用前趋和后继关系来描述。40数据的逻辑结构的定义

数据的逻辑结构是数据间关系的描述。它抽象地反映数据元素间的逻辑关系。数据的逻辑结构的分类

根据各元素之间的前趋和后继关系的不同特性，可将数据的逻辑结构分为线性结构和非线性结构两大类。

2.数据的逻辑结构41线性结构：每个元素最多有一个前趋、一个后继，如线性表、堆栈、队列等。

非线性结构：如果一个数据结构不是线性结构，则称为非线性结构，如树、图等。

42

①集合②线性结构③树形结构④图形结构

基本的数据结构

43

①

集合

结构中的数据元素间除了“同属于一个集合”的关系外，别无其他关系。

②线性结构

线性结构的数据元素只按先后次序连接，数据元素间存在一对一的关系。线性结构在程序设计中应用最为广泛。常用的线性结构有：

线性表、堆栈、队列…基本的数据结构44

线性表是最常用、最简单的一类线性逻辑结构，它由n（n≥0）个具有相同类型的数据元素构成的有限序列。线性表中元素的数据类型可以为任意已知的数据类型。a1a2a3…ai…an线性表45说明：

在一个稍复杂的线性表中，一个元素可以由若干个数据项组成。例如，一个班级的学生成绩表中，表的每一行可看作一个数据元素，可以把这个表格理解为一个线性表的逻辑结构。46

堆栈是一种操作上受限的线性表，它只允许在一端进行插入和删除操作。允许进行操作的一端称为栈顶，栈顶的位置是随插入和删除操作动态变化的。不允许操作的一端称为栈底。

这种结构的特点是“后进先出”，因此堆栈也被称为“后进先出表”。

堆栈47数据入栈次序为：

a1，a2，……，an数据出栈次序为：

an，an-1，……，a1

设有一堆栈S，有一个元素序列a1，a2，……，an，an所在位置是栈顶，a1所在位置是栈底。栈顶Top栈底baseanan-1…ai…a1入栈出栈48队列也是一种操作上受限的特殊线形表，它只允许在表的一端进行插入操作，在另一端进行删除操作。队列中允许插入的一端称为队尾，允许删除的一端称为队首。因此，这样的队列又称为“先进先出表”。

队列49上图中队列入队次序为：a1，a2，……，an上图中队列出队次序为：a1，a2，……，an队尾队首a1,a2,a3,……,an出队列入队列50

树形结构的数据元素是分层次的纵向连接，数据元素间存在一对多的关系。③树形结构51根结点：A兄弟结点：B、C、D叶子结点：K、L相关术语：

根结点、子树、父亲结点、孩子结点（子结点）、兄弟结点、叶子结点、节点的度、树的度、节点的层数树的深度52在树形结构中，常用的是二叉树。它是一种特殊的树结构，它只有一个根结点，它的每个结点最多有两个子结点，且有先后次序。左边的结点称为左孩子，右边的结点称为右孩子。根结点右孩子左孩子二叉树53

图形结构的数据元素有各种各样的复杂连结，数据元素间存在多对多的关系。图是由一组数据元素（称为顶点）的有限集和描述顶点间相互关系的边（或弧）的有限集组成。图分为：有向图和无向图。

④图形结构54有向图：在有向图中，顶点与顶点之间的连线是具有方向的，这样的连线称为弧。无向图：在无向图中，顶点与顶点间的连线是没有方向的，这样的连线称为边。55数据的逻辑结构在计算机存储器中的表示（又称映像）称为数据的存储结构（或物理结构）。数据的存储结构包括两个方面内容，即数据元素的表示和关系的表示。数据的逻辑结构通过不同的存储映像方法（顺序映像和非顺序映像）可得到不同的存储结构。

3.数据的存储结构56数据的存储结构分为四种：顺序存储结构链接存储结构索引存储结构散列存储结构

线性结构可采用顺序、链接、索引、散列四种存储结构，而树形结构和图形结构等非线性结构一般采用链接存储结构。57①顺序存储结构

用一块连续存储区域存储线性数据结构。结点间的逻辑关系用存储单元的自然顺序关系来表达的。顺序存储结构一般也被称为紧凑存储结构。

优点:

结构简单，可节省存储空间。缺点:

由于要求连续的存储单元，因此可能产生较多的碎片。58

链接存储结构是在结点的存储结构中附加指针字段（指针域）来存储结点间的逻辑关系。

链接存储结构中数据结点包括两部分：②链接存储结构

数据域：存放结点本身的数据。

指针域：存放指向其后继（或前趋）结点的指针，即存放与该数据元素相邻接的元素的地址。

优点:不要求连续的存储空间，使用较灵活。缺点：结点指针要占用额外的存储空间。数据域指针域59例：链接存储结构的学生表数据域：存放数据元素自身的信息，包括学号、姓名等。标识符data表示这些域的全体；指针域：存放指针，即存放与该数据元素相邻接的元素的地址。用标识符link来表示。

060结点的存储结构二叉树的链接存储结构链接存储结构举例：二叉树的链接存储结构61③索引存储结构

用数据元素的索引号来确定数据元素的存储地址。

索引存储一般有两种实现方法：建立附加的索引表，索引表里第i项的值就是第i个元素的存储地址。当每个元素所占内存单元数相等时，可用地址码的线性函数值来确定元素的存储地址。优点:检索速度快。缺点:增加了附加的索引表，会占用较多的存储空间。62根据数据元素的值，利用散列函数计算出它的地址。

④散列存储结构

数据元素与其在存储器中的存储位置之间的映像关系可以用一个函数来表示—散列函数。

优点:检索、增加、删除结点的操作速度快。缺点:采用不好的散列函数时可能出现结点单元的碰撞，而需要附加时间和空间开销。63

4.数据的运算每一种数据结构都有一个运算的集合。常用的运算有检索（查找）、插入、删除、更新、排序等。

数据的运算定义在数据的逻辑结构上，而其运算的具体实现要在其存储结构上实现。例如：从学生表中删除一个学生元素，向家族树中插入一个元素等。64

插入、删除、排序、查找、分解、合并等。线性表的运算顺序存储结构的线性表的运算链接存储结构的线性表的运算65顺序存储结构的线性表的运算插入运算：在线性表中插入一个新元素。

在一般情况下，要在第i个元素元素之前插入一个新元素的步骤:

（1）要从最后一个元素开始，直到第i个元素之间共n-i+1个元素依次后移一个位置，移动结束后，第i个位置被空出；（2）将新元素插入。

插入结束后，线性表的长度就增加1。插入、删除、排序、查找、分解、合并等。66（a）长度为8的线性表（b）插入87后的线性表（c）插入14后线性表线性表的插入运算举例：在下面图（a）所示的线性表中插入87和14。67删除运算：在线性表中删除一个元素。

在一般情况下，要删除第i个元素时，要从i+1个元素开始，直到第n个元素依次向前移动一个位置。

删除结束后，线性表的长度就减少1。68线性表的删除运算举例：在下面的图（a）所示的线性表中删除29和31（a）长度为8的线性表（b）删除29后的线性表（c）删除31后的线性表69栈的基本运算入栈运算(在栈顶插入一个新元素)

上移栈顶指针，在栈顶插入新元素。出栈运算(在栈顶取出一个元素)

取出栈顶元素，并赋给一个指定的变量。下移栈顶指针。读栈顶运算（将栈顶元素赋给一个指定的变量）将栈顶元素赋给一个指定的变量。此运算不删除栈顶元素。栈顶指针不改变。70队列的基本运算入队运算（在队尾插入一个元素）

队尾指针加1，然后在队尾插入一个元素。出队运算（在队首删除一个元素）

将队首元素赋给一个变量。队首指针加1（删除一个元素）。循环队列:

队首指针加1;

将队首元素赋给一个变量。队尾队首71链接存储结构的线性表的运算插入、删除、排序、查找、分解、合并等。插入运算在链表中指定元素前插入新元素。删除运算

删除指定的元素。72例如，在下面的（a）所示的链表中值为x的元素前插入值为值为b的元素。插入运算

查找指定元素。给新元素分配一个结点，然后将存放新元素的结点链接到指定的位置。headpqbx

0…73删除运算查找指定元素。通过改变被删除元素的所在结点的前一个结点的指针域，删除指定结点。例如，在下面的（a）所示的链表中删除值为x的元素。headqx

0

74二叉树的遍历

指不重复地访问二叉树中的所有结点。根据访问结点的次序不同，二叉树的遍历分为三种：前序遍历、中序遍历和后序遍历。75前序遍历：先访问根结点，再遍历左子树，最后遍历右子树。(中、左、右）中序遍历：先遍历左子树，然后访问根结点，最后遍历右子树。(左、中、右）后序遍历：先遍历左子树，再遍历右子树，最后访问根结点。(左、右、中）二叉树的遍历76二叉树的遍历举例前序遍历结果：(中、左、右）

F，C，A，D，B，E，G，H，P中序遍历结果：(左、中、右）

A，C，B，D，F，E，H，G，P后序遍历结果：(左、右、中）

A，B，D，C，H，P，G，E，F77复习思考题一.选择题1.计算机能直接执行的是

程序。A.编译语言B.机器语言C.高级语言D.智能语言2.编译程序和解释程序的主要区别是

。A.后者生成目标代码，而前者不生成B.前者生成目标代码，而后者不生成C.后者生成源程序，而前者不生成D.前者生成源程序，而后者不生成BB783.结构化程序设计语言设计主要强调的是

。

A.程序的规模B.程序的易读性

C.程序的执行效率D.程序的可移植性复习思考题B794.下面描述中，符合结构化程序设计风格的是

。

A.使用顺序、选择和重复（循环）三种基本结构表示程序的控制结构

B.模块只有一个入口，可以有多个出口

C.注重提高程序的执行效率

D.不适用GOTO语句复习思考题A805.在下列选项中，那个不是算法一般应该具有的基本特征？

。

A.确定性B.可行性C.无穷性D.有输出6.算法的有穷性是指

。

A.算法程序的运行时间是有限的

B.算法程序所处理的数据量是有限的

C.算法程序的长度是有限的

D.算法只能被优先的用户使用复习思考题CA817.算法的时间复杂度是指

。

A.执行算法程序所需要的时间

B.算法程序的长度

C.算法执行过程中所需要的基本运算次数

D.算法程序中的指令条数复习思考题C828.算法的空间复杂度是指

。A.算法程序的长度B.算法程序中的指令条数C.算法程序所占的存储空间D.算法执行过程中所需要的存储空间复习思考题D839.以下数据结构中不属于线性结构的是

。

A.队列B.线性表C.二叉树D.栈10.数据的存储结构是指

。

A.数据所占的存储空间量

B.数据的逻辑结构在计算机中的表示

C.数据在计算机中的顺序存储方式

D.存储在外存的数据复习思考题CB8411.下列关于栈的叙述中正确的是

。A.在栈中只能插入数据B.在栈中只能删除数据C.栈是“先进先出”的线性表D.栈是“后进先出”的线性表复习思考题D8512.下列关于队列的叙述中正确的是

。A.在队列中只能插入数据B.在队列中只能删除数据C.队列是“先进先出”的线性表D.队列是“先进后出”的线性表复习思考题C8613.线性表的顺序存储结构和线性表的链式存储结构分别是

。A.顺序存取的存储结构、顺序存取的存储结构B.随机存取的存储结构、顺序存取的存储结构C.随机存取的存储结构、随机存取的存储结构D.任意存取的存储结构、任意存取的存储结构复习思考题B8714.用链表表示线性表的优点是

。A.便于插入和删除操作B.数据元素的物理顺序与逻辑顺序相同C.花费的存储空间较顺序存储少D.便于随机存取复习思考题A8815.在一棵二叉树上第5层的节点数最多是

。A.8B.16C.32D.15复习思考题B89二.填空题1.计算机程序是指

。2.源程序是指

，目标程序是指

。3.结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、

和限制使用GOTO语句。复习思考题用某种计算机程序设计语言编写的解决某个问题或完成某项任务的指令序列用源语言编写的程序翻译后生成的低级语言代码模块化

904.面向对象的程序设计是以

为中心来分析和