1、第4讲 程序设计基础知识 4.1 算法 了解什么是算法，算法的描述方式。4.2 程序设计语言 以c语言为例，介绍高级程序设计语言的基本语法、程序结构，以及程序设计的一般方法，应用高级语言进行程序设计。4.3 数据结构 为要解决的目标问题设计出高效的数据逻辑结构和存储结构，保证算法和程序的效率；4.1算法与程序（教材第5章）4.1.1算法的概念l 为解决一个问题而采取得方法和步骤，称为算法。l 算法就是被精确定义的一组规则，规定先做什么，再做什么，以及判断某种情况下做哪种操作；l 算法是步进式的完成所需任务的过程。4.1.2、程序的概念l程序是编程者写的、计算机能够理解并执行的一些命令的集合，是
2、解决问题的具体算法在计算机中的实现。4.1.3、算法的特点及评价标准 算法必须具有以下特性：有穷性。确定性。有效性。输入及输出。4.1.4、算法的表示（1）用自然语言表示 例如，求三个数的最大值的问题，可以描述为：先比较前两个数，找到大的那个数，再让其与第三个数进行比较，找到二者中大的数即为所求。处理处理A处理处理B(a)处理处理A处理处理B真真假假条条 件件(b)处理处理 A假假真真条条 件件(c)三种基本结构三种基本结构2 2）用传统流程图表示）用传统流程图表示 输入输入a,b,c置置max=a置置max=c真真假假if(cmax)置置max=b真真假假if(bmax)实例：实例：3 3)
3、用伪码表示用伪码表示l伪码是用一种介于自然语言和计算机语言之间的文字和符号来描述算法。接近计算机语言，便于向计算机程序过渡。比计算机语言形式灵活、格式紧凑，没有严格的语法格式。l关键字外部语法 l自然语言内部语法begin 输入 a,b,c;置max=a;if(bmax)then 置max=b;endif if(cmax)then 置max=c;endif 输出max;stop#include stdio.h“int max(int x,int y,int z)int m=x;if(ym)m=y;if(zm)m=z;return m;void main()int num1,num2,num3;
4、int maximum;printf(“nEnter three integers:”);scanf(%d,%d,%d,&num1,&num2,&num3);maximum=max(num1,num2,num3);printf(nMaximum is:%d,maximum);4 4)用程序实现用程序实现4.2 程序设计语言(教材第6章)4.2.1 程序设计语言程序设计语言的种类的种类：机器语言汇编语言高级语言结构化程序设计语言 面向对象程序设计语言人工智能程序设计语言机器语言机器语言 由二进制编码指令构成的语言。由二进制编码指令构成的语言。是一种依附于机器硬件的语言。是一种依附于机器硬件的语言
5、。机器语言程序可以直接执行。机器语言程序可以直接执行。机器语言程序片段机器语言程序片段0001 0101 01101100 /把地址为把地址为01101100的内存单元中的数装入的内存单元中的数装入0101号寄存器号寄存器0001 0110 01101101 /把地址为把地址为01101101的内存单元中的数装入的内存单元中的数装入0110号寄存器号寄存器0101 0000 01010110 /把把01101100和和01101101中的数相加中的数相加,结果存入结果存入0000号寄存号寄存器器0011 0000 01101110 /把把0000号寄存器中的数存入地址为号寄存器中的数存入地址为
6、01101110的内存单元中的内存单元中汇编语言汇编语言由助记符指令构成的语言。由助记符指令构成的语言。也是一种依附于机器硬件的语言。也是一种依附于机器硬件的语言。汇编语言源程序需要汇编后才能执行。汇编语言源程序需要汇编后才能执行。汇编语言程序片段汇编语言程序片段 MOV R5,X /把内存单元把内存单元X中的数装入中的数装入R5寄存器寄存器 ADD R5,Y /把把R5中的数与中的数与Y单元中的数相加，结果存入单元中的数相加，结果存入R5 MOV Z,R5 /把把R5中的数存入中的数存入Z单元中单元中 高级语言高级语言由自然语言和数学公式表示的语言。由自然语言和数学公式表示的语言。是一种独立
7、于机器硬件的语言。是一种独立于机器硬件的语言。高级语言程序需要编译后才能执行。高级语言程序需要编译后才能执行。高级语言程序片段高级语言程序片段 Z=X+Y /把内存单元把内存单元X中的数与中的数与Y中的数相加，结果存入中的数相加，结果存入Z单元单元 影响较大的高级语言：影响较大的高级语言：FORTRAN语言：FORTRAN是FORmula TRANslator（公式翻译器）的缩写。ALGOL语言：ALGOL是ALGOrithm Language（算法语言）的缩写。COBOL语言：COBOL是COmmon Business-Oriented Language（面向商业的通用语言）的缩写。BASI
8、C语言：BASIC是Beginners All-purpose Symbolic Instruction Code（初学者通用符号指令码）的缩写。结构化程序设计语言的特点结构化程序设计语言的特点 l 采用三种基本控制结构，程序结构清晰。采用三种基本控制结构，程序结构清晰。l 采用模块化程序设计方法。采用模块化程序设计方法。常用结构化程序设计语言常用结构化程序设计语言 l PASCAL语言语言 l C语言语言 面向对象程序设计语言面向对象程序设计语言 将问题分解为对象。使人们对复杂系统的认识过程与程序设计过程尽可能一致。对象将自己的属性和方法封装成类。对象之间通过消息传递来相互联系。常用面向对象
9、程序设计语言常用面向对象程序设计语言 l Simula 67 l C+l Java人工智能程序设计语言人工智能程序设计语言适合于知识表示和逻辑推理。适合于知识表示和逻辑推理。常用人工智能程序设计语言常用人工智能程序设计语言 lLISP l可以解决人工智能中的符号处理问题。可以解决人工智能中的符号处理问题。lPROLOG l自动实现模式匹配、自动回溯这两种人工智能中常用的基本操自动实现模式匹配、自动回溯这两种人工智能中常用的基本操作。作。4.2.2 程序设计语言的机制1 1、字符集：、字符集：每个语言都有一个基本字符集，程序是符合语法的字符串。以以C语言为例：语言为例：英文字母（大、小写）：英文
10、字母（大、小写）：A，B，C，Z；a，b，c，z 数字：数字：0，1，2，9 特殊字符：特殊字符：,，*，/，_，（，），！，（，），！，$，&等等 转义字符：转义字符：n，t，v，b，r，f，a，ddd，xhh等等 2、名字说明 预先说明程序中将要使用的对象预先说明程序中将要使用的对象(常量和变量常量和变量)的名字的名字，有利于编译程序检查对象使用方式的合法性，帮助，有利于编译程序检查对象使用方式的合法性，帮助程序员发现错误。程序员发现错误。有些语言（有些语言（如如C C语言语言）要求对象预先显示说明。）要求对象预先显示说明。某些语言某些语言(例如例如FORTRANFORTRAN和和BASI
11、CBASIC)并不要求用户显式说并不要求用户显式说明程序中对象的名字，第一次使用的名字即被看作是明程序中对象的名字，第一次使用的名字即被看作是对这个名字的说明。对这个名字的说明。（1）什么是数据类型？数据类型定义是一种抽象机制，它刻画了一组数据对象和作用在数据对象上的一组操作。抽象数据类型是数据类型的发展，它使用户可以引用复杂的实体，而不必考虑这些实体的表示方法。（2）数据类型的作用 数据类型检查是保证程序可靠性的一条有效途径，编译器通过对操作中不同操作数类型的检查，确定操作的合法性。3 3、数据类型定义和检查、数据类型定义和检查（1 1）子程序：可独立编译的程序单元。）子程序：可独立编译的程
12、序单元。（2 2）子程序一般具备如下三种机制：）子程序一般具备如下三种机制：子程序说明，它给出子程序与其他程序单元的接口；子程序体，它实现子程序的数据结构和控制结构；调用方式。（3 3）不同语言的子程序：）不同语言的子程序：C的基本程序单位是函数；PASCAL的基本程序单位的子程序（过程与函数）；MODULA程序的组成单位是模块module；ADA的基本程序模块是程序包（package）。4、子程序（1）最常见的控制转移语句是GOTO语句，其一般形式是：GOTO GOTO 5 5、控制结构、控制结构 integer x,sum x=0.0 sum=0.0 10 x=x+1 sum=sum+x
13、if(x.lt.10)goto 10 print*,sum end一个fortran语言程序：求110的累加和。顺序结构顺序结构程序示例：通过键盘输入一个三角形的底和高，计算其程序示例：通过键盘输入一个三角形的底和高，计算其面积并输出。面积并输出。（2）结构化语言控制结构）结构化语言控制结构main()float width,height,area;/*定义变量*/printf(nEnter width and height:);/*输出提示信息*/scanf(“%f,%f”,&width,&height);/*通过键盘输入底和高*/area=(width*height)/2.0;/*计算面积
14、*/printf(nThe arae is:%f,area);/*输出面积的值*/分支结构分支结构程序示例：根据输入的学生成绩对其进行判断处理，如果成绩及格，则输出Passed，否则输出Failed。main()float score;/*定义变量*/printf(nEnter a score:);/*显示提示信息*/scanf(%f,&score);/*通过键盘输入一个成绩*/if(score=60.0)printf(nPassed);/*大于等于60输出Passed*/else printf(nFailed);/*小于60输出Failed*/程序示例：从键盘上输入程序示例：从键盘上输入10
15、个整数，求其累加和并输出。个整数，求其累加和并输出。循环结构循环结构main()int i,num,sum;/*定义变量*/sum=0;/*累加变量清零*/for(i=1;i=10;i+)/*循环次数为10*/printf(Enter a data:n);/*显示提示信息*/scanf(%d,&num);/*通过键盘输入一个整数*/sum=sum+num;/*累加求和*/printf(“nsum=%d,sum);/*输出累加结果*/4.2.3 程序设计风格主要体现在主要体现在5个方面个方面 标识符的命名要风格统一、见名知义。一般一行写一条语句，一条长语句可以写在多行上，但尽量不要把多条语句写在
16、一行上。采用缩进格式，即同一层次的语句要对齐，低层次的语句要缩进若干个字符，增加程序的可读性。适当书写注释信息，有助于阅读者对程序的理解。尽量少用goto语句，否则容易导致程序结构混乱。4.3 数据结构（与教材第8章相关）4.3.1 数据结构与问题求解4.3.2 数据结构的基本概念和术语4.3.3 基本数据结构介绍l 线性结构l 树形结构l 图状结构计算机求解问题的步骤是：计算机求解问题的步骤是：（1 1）从具体问题抽象出一个数学模型；）从具体问题抽象出一个数学模型；（2 2）设计解此数学模型的算法；）设计解此数学模型的算法；（3 3）编出程序，直至得到最终的解答。）编出程序，直至得到最终的解
17、答。数据结构是非数值计算问题求解的基础。数据结构是非数值计算问题求解的基础。与程序设计语言课程相比，数据结构面向应用与程序设计语言课程相比，数据结构面向应用 4 4.3 3.1.1 数据结构与问题求解数据结构与问题求解4 4.3 3.2.2 数据结构的基本概念和术语数据结构的基本概念和术语1 1、数据、数据：信息的载体，它能够被计算机识别、存储信息的载体，它能够被计算机识别、存储和加工处理。和加工处理。2 2、信息、信息：数据的语义解释，它能被人理解。数据的语义解释，它能被人理解。3 3、数据项、数据项：数据不可分割的最小单位。数据项有名数据不可分割的最小单位。数据项有名和值之分，和值之分，名
18、名是一个数据项的标识，是一个数据项的标识，值值是它的一个是它的一个可能取值。可能取值。4 4、数据元素、数据元素：数据的基本单位。在不同的条件下，数据数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。元素又可称为元素、结点、顶点、记录等。5 5、数据对象或数据元素类、数据对象或数据元素类：具有相同性质的数据元素具有相同性质的数据元素的集合。的集合。6 6、数据结构、数据结构：指互相之间存在着一种或多种关系的数据指互相之间存在着一种或多种关系的数据元素的集合。数据元素之间的关系称为结构。元素的集合。数据元素之间的关系称为结构。1 1、逻辑结构逻辑结构：从具体问题抽象出来的
19、数学模型，是从用户角度从具体问题抽象出来的数学模型，是从用户角度看到的数据元素之间的关系。看到的数据元素之间的关系。常用的逻辑结构有：常用的逻辑结构有：（1 1）线性结构：）线性结构：数据元素之间存在着一对一的关系。数据元素之间存在着一对一的关系。线性表，栈、队列、数组、字符串。线性表，栈、队列、数组、字符串。（2 2）树形结构：）树形结构：数据元素之间存在着一对多的关系。数据元素之间存在着一对多的关系。（3 3）图形结构：）图形结构：该结构的数据元素之间存在着多对多的关系该结构的数据元素之间存在着多对多的关系，图形结构也称作网状结构。，图形结构也称作网状结构。4 4.3 3.2.2 数据结构
20、的逻辑结构和物理结构数据结构的逻辑结构和物理结构2 2、物理结构、物理结构：也称存储结构，是数据结构在计算机中的表示。存储结构有两种：（1 1）顺序存储：）顺序存储：逻辑上相邻的元素存储在物理位置相邻的存储单元中。数组就是顺序存储。（2 2）链式存储：）链式存储：逻辑上相邻的元素不要求其物理位置相邻，链式存储结构通常借助于程序设计语言中的指针来实现。1 1、线性表：、线性表：该结构的数据元素之间存在着一对一的逻辑关系。通常记为：(a1，a2，ai-1，ai，ai+1，an)（1 1）顺序表：）顺序表：用地址连续的一块存储空间顺序存放线性表的各元素。（2 2）单链表：）单链表：不用地址连续的一块
21、存储空间顺序存放线性表的各元素，元素之间的逻辑关系由指针指向。4 4.3 3.3.3 基本基本数据结构介绍数据结构介绍图图 链表示意图链表示意图a1anHa2线性表的基础操作：构造、插入、删除、查找线性表的基础操作：构造、插入、删除、查找1 1、栈和队列：、栈和队列：是一种操作受限的线性表。是一种操作受限的线性表。（1 1）栈的操作原则：）栈的操作原则：先进后出，后进先出。先进后出，后进先出。LIFOLIFO 栈的基本操作：入栈、出栈、判断栈是否为空和溢出。栈的基本操作：入栈、出栈、判断栈是否为空和溢出。栈示意图栈示意图 a3 a2 a1入栈入栈出栈出栈top （1 1）栈的操作原则：）栈的操
22、作原则：先进后出，后进先出。先进后出，后进先出。LIFOLIFO 栈的基本操作：入栈、出栈、判断栈是否为空和溢出。栈的基本操作：入栈、出栈、判断栈是否为空和溢出。图图5.13 队列示意图队列示意图a1 a2 a3 a4 a5 入队入队出队出队3 3、树形结构：、树形结构：该结构的数据元素之间存在着一对多的该结构的数据元素之间存在着一对多的关系。关系。二叉树：二叉树：每个结点最多只有两个子树，且分左子树每个结点最多只有两个子树，且分左子树和右子树。和右子树。二叉树的应用：二叉树的应用：哈夫曼编码、二分查找树、二叉排序树、堆排序。满二叉树满二叉树完全二叉树完全二叉树非完全二叉树非完全二叉树二叉树的
23、存储二叉树的存储顺序存储结构顺序存储结构l用一组连续的存储单元（数组）存放二叉树中的结点。一般用一组连续的存储单元（数组）存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。是按照二叉树结点从上至下、从左到右的顺序存储。链式存储结构链式存储结构l用链表来表示一棵二叉树。链表中每个结点由三个域组成，用链表来表示一棵二叉树。链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点的左除了数据域外，还有两个指针域，分别用来给出该结点的左子结点和右子结点所在的链结点的存储地址。子结点和右子结点所在的链结点的存储地址。非完全二叉树的链式存储非完全二叉树的链式存储4
24、4、图形结构：、图形结构：该结构的数据元素之间存在着多对多的关系该结构的数据元素之间存在着多对多的关系，图形结构也称作网状结构。，图形结构也称作网状结构。图的类别：图的类别：无向树、有向树、带权无向树、带树有向树。无向树、有向树、带权无向树、带树有向树。BADCG2：BADCG3：23456BADCG4：23456图的基本运算：图的基本运算：图的遍历（深度优先、宽度优先）、图的遍历（深度优先、宽度优先）、图的最小生树、最生路径、拓朴排序。图的最小生树、最生路径、拓朴排序。图的应用图的应用求最短路径求最短路径网络性能分析网络性能分析思考题思考题名词解释：机器语言、汇编语言、高级语言、程序、算法、
25、数据、数据项、数据元素、数据对象、数据结构、线性结构、树、二叉树、图。说明程序与算法的联系和区别。描述算法的方法有哪些？程序设计语言有哪些类，每个类的语言有什么特点？请尽可能多列举你所知道的程序设计语言。学习一种高级语言，应主要掌握哪些内容？面向对象程序设计语言与面向过程程序设计语言有什么区别？结构化程序三种基本控制结构是什么？高级语言中，变量一般要先定义再使用，这样一种规定有什么好处？什么是数据结构？有哪几种基本逻辑结构？学习数据结构课程的目的是什么？什么是线性表、栈和队列？什么是树和二叉树？查阅文献，举例说明树或二叉树在程序设计中的作用。图有哪几种形式？举例说明图的应用。程序设计语言、数据结构、算法分析与设计3门课程对于提高程序设计能力和培养程序设计思维各有什么作用？
