程序设计基础知识

1、2021-7-1计算机科学导论1/30 第4讲 程序设计基础知识 4.1 算法 了解什么是算法，算法的描述方式。 4.2 程序设计语言 以c语言为例，介绍高级程序设计语言的基本语 法、程序结构，以及程序设计的一般方法，应用 高级语言进行程序设计。 4.3 数据结构 为要解决的目标问题设计出高效的数据逻辑结 构和存储结构，保证算法和程序的效率； 2021-7-1计算机科学导论2/30 4.1算法与程序（教材第5章） 4.1.1算法的概念 l 为解决一个问题而采取得方法和步骤，称为算 法。 l 算法就是被精确定义的一组规则，规定先做什 么，再做什么，以及判断某种情况下做哪种操 作； l 算法是步进

2、式的完成所需任务的过程。 2021-7-1计算机科学导论3/30 4.1.2、程序的概念 l程序是编程者写的、计算机能够理解并执 行的一些命令的集合，是解决问题的具体 算法在计算机中的实现。 2021-7-1计算机科学导论4/30 4.1.3、算法的特点及评价标准 算法必须具有以下特性： 有穷性。 确定性。 有效性。 输入及输出。 2021-7-1计算机科学导论5/30 4.1.4、算法的表示 （1）用自然语言表示 例如，求三个数的最大值的问题，可以描 述为：先比较前两个数，找到大的那个数，再 让其与第三个数进行比较，找到二者中大的数 即为所求。 2021-7-1计算机科学导论6/30 处理处

3、理A 处理处理B (a) 处理处理A 处理处理B 真真 假假 条条 件件 (b) 处理处理 A 假假 真真 条条 件件 (c) 三种基本结构三种基本结构 2 2）用传统流程图表示）用传统流程图表示 输入输入a,b,c 置置max=a 置置max=c 真真 假假 if(cmax) 置置max=b 真真 假假 if(bmax) 实例：实例： 2021-7-1计算机科学导论7/30 3 3) ) 用伪码表示用伪码表示 l伪码是用一种介于自然语言 和计算机语言之间的文字和符 号来描述算法。接近计算机语 言，便于向计算机程序过渡。 比计算机语言形式灵活、格式 紧凑，没有严格的语法格式。 l关键字外部语法

4、 l自然语言内部语法 begin 输入 a,b,c; 置max=a; if(bmax)then 置max=b; endif if(cmax)then 置max=c; endif 输出max; stop 2021-7-1计算机科学导论8/30 #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; int maximum; printf(“nEnter three integers: ”); scanf(%d

5、,%d,%d, maximum=max(num1,num2,num3); printf(nMaximum is: %d ,maximum); 4 4) ) 用程序实现用程序实现 2021-7-1计算机科学导论9/30 4.2 程序设计语言(教材第6章) 4.2.1 程序设计语言程序设计语言的种类的种类： 机器语言 汇编语言 高级语言 结构化程序设计语言 面向对象程序设计语言 人工智能程序设计语言 2021-7-1计算机科学导论10/30 机器语言机器语言 由二进制编码指令构成的语言。由二进制编码指令构成的语言。 是一种依附于机器硬件的语言。是一种依附于机器硬件的语言。 机器语言程序可以直接执行

6、。机器语言程序可以直接执行。 机器语言程序片段机器语言程序片段 0001 0101 01101100 /把地址为把地址为01101100的内存单元中的数装入的内存单元中的数装入0101号寄存器号寄存器 0001 0110 01101101 /把地址为把地址为01101101的内存单元中的数装入的内存单元中的数装入0110号寄存器号寄存器 0101 0000 01010110 /把把01101100和和01101101中的数相加中的数相加,结果存入结果存入0000号寄存号寄存 器器 0011 0000 01101110 /把把0000号寄存器中的数存入地址为号寄存器中的数存入地址为0110111

7、0的内存单元中的内存单元中 2021-7-1计算机科学导论11/30 汇编语言汇编语言 由助记符指令构成的语言。由助记符指令构成的语言。 也是一种依附于机器硬件的语言。也是一种依附于机器硬件的语言。 汇编语言源程序需要汇编后才能执行。汇编语言源程序需要汇编后才能执行。 汇编语言程序片段汇编语言程序片段 MOV R5, X /把内存单元把内存单元X中的数装入中的数装入R5寄存器寄存器 ADD R5, Y /把把R5中的数与中的数与Y单元中的数相加，结果存入单元中的数相加，结果存入R5 MOV Z, R5 /把把R5中的数存入中的数存入Z单元中单元中 2021-7-1计算机科学导论12/30 高级

8、语言高级语言 由自然语言和数学公式表示的语言。由自然语言和数学公式表示的语言。 是一种独立于机器硬件的语言。是一种独立于机器硬件的语言。 高级语言程序需要编译后才能执行。高级语言程序需要编译后才能执行。 高级语言程序片段高级语言程序片段 Z=X + Y /把内存单元把内存单元X中的数与中的数与Y中的数相加，结果存入中的数相加，结果存入Z单元单元 2021-7-1计算机科学导论13/30 影响较大的高级语言：影响较大的高级语言： FORTRAN语言：FORTRAN是FORmula TRANslator （公式翻译器）的缩写。 ALGOL语言：ALGOL是ALGOrithm Language（算法

9、 语言）的缩写。 COBOL语言：COBOL是COmmon Business-Oriented Language（面向商业的通用语言）的缩写。 BASIC语言：BASIC是Beginners All-purpose Symbolic Instruction Code（初学者通用符号指令码） 的缩写。 2021-7-1计算机科学导论14/30 结构化程序设计语言的特点结构化程序设计语言的特点 l 采用三种基本控制结构，程序结构清晰。采用三种基本控制结构，程序结构清晰。 l 采用模块化程序设计方法。采用模块化程序设计方法。 常用结构化程序设计语言常用结构化程序设计语言 l PASCAL语言语言 l

10、 C语言语言 2021-7-1计算机科学导论15/30 面向对象程序设计语言面向对象程序设计语言 将问题分解为对象。使人们对复杂系统的认识过程与程 序设计过程尽可能一致。 对象将自己的属性和方法封装成类。 对象之间通过消息传递来相互联系。 常用面向对象程序设计语言常用面向对象程序设计语言 l Simula 67 l C+ l Java 2021-7-1计算机科学导论16/30 人工智能程序设计语言人工智能程序设计语言 适合于知识表示和逻辑推理。适合于知识表示和逻辑推理。 常用人工智能程序设计语言常用人工智能程序设计语言 lLISP l可以解决人工智能中的符号处理问题。可以解决人工智能中的符号处

11、理问题。 lPROLOG l自动实现模式匹配、自动回溯这两种人工智能中常用的基本操自动实现模式匹配、自动回溯这两种人工智能中常用的基本操 作。作。 2021-7-1计算机科学导论17/30 4.2.2 程序设计语言的机制 1 1、字符集：、字符集：每个语言都有一个基本字符集，程序是符合语 法的字符串。 以以C语言为例：语言为例： 英文字母（大、小写）：英文字母（大、小写）：A，B，C， ，Z ；a，b ，c， ，z 数字：数字：0，1，2，9 特殊字符：特殊字符：, ，*，/，_，（，），！，（，），！ ，$， /*定义变量*/ printf(nEnter width and height:)

12、; /*输出提示信息*/ scanf(“%f,%f”, /*通过键盘输入底和高*/ area=(width*height)/2.0; /*计算面积*/ printf(nThe arae is :%f ,area); /*输出面积的值*/ 2021-7-1计算机科学导论23/30 分支结构分支结构 程序示例：根据输入的学生成绩对其进行判断处理，如 果成绩及格，则输出Passed，否则输出Failed。 main( ) float score; /*定义变量*/ printf(nEnter a score :);/*显示提示信息*/ scanf(%f,/*通过键盘输入一个成绩*/ if (scor

13、e=60.0) printf(nPassed );/*大于等于60输出Passed*/ else printf(nFailed );/*小于60输出Failed*/ 2021-7-1计算机科学导论24/30 程序示例：从键盘上输入程序示例：从键盘上输入10个整数，求其累加和并输出。个整数，求其累加和并输出。 循环结构循环结构 main( ) int i, num, sum;/*定义变量*/ sum=0;/*累加变量清零*/ for (i=1; i=10;i+)/*循环次数为10*/ printf(Enter a data:n );/*显示提示信息*/ scanf(%d , /*通过键盘输入一个

14、整数*/ sum=sum+num;/*累加求和*/ printf(“nsum=%d,sum);/*输出累加结果*/ 2021-7-1计算机科学导论25/30 4.2.3 程序设计风格 主要体现在主要体现在5个方面个方面 标识符的命名要风格统一、见名知义。 一般一行写一条语句，一条长语句可以写在多行上，但 尽量不要把多条语句写在一行上。 采用缩进格式，即同一层次的语句要对齐，低层次的语 句要缩进若干个字符，增加程序的可读性。 适当书写注释信息，有助于阅读者对程序的理解。 尽量少用goto语句，否则容易导致程序结构混乱。 2021-7-1计算机科学导论26/30 4.3 数据结构（与教材第8章相关

15、） 4.3.1 数据结构与问题求解 4.3.2 数据结构的基本概念和术语 4.3.3 基本数据结构介绍 l 线性结构 l 树形结构 l 图状结构 2021-7-1计算机科学导论27/30 计算机求解问题的步骤是：计算机求解问题的步骤是： （1 1）从具体问题抽象出一个数学模型；）从具体问题抽象出一个数学模型； （2 2）设计解此数学模型的算法；）设计解此数学模型的算法； （3 3）编出程序，直至得到最终的解答。）编出程序，直至得到最终的解答。 数据结构是非数值计算问题求解的基础。数据结构是非数值计算问题求解的基础。 与程序设计语言课程相比，数据结构面向应用与程序设计语言课程相比，数据结构面向应

16、用 4 4. .3 3.1 .1 数据结构与问题求解数据结构与问题求解 2021-7-1计算机科学导论28/30 4 4. .3 3.2 .2 数据结构的基本概念和术语数据结构的基本概念和术语 1 1、数据、数据：信息的载体，它能够被计算机识别、存储信息的载体，它能够被计算机识别、存储 和加工处理。和加工处理。 2 2、信息、信息：数据的语义解释，它能被人理解。数据的语义解释，它能被人理解。 3 3、数据项、数据项：数据不可分割的最小单位。数据项有名数据不可分割的最小单位。数据项有名 和值之分，和值之分，名名是一个数据项的标识，是一个数据项的标识，值值是它的一个是它的一个 可能取值。可能取值。

17、 2021-7-1计算机科学导论29/30 4 4、数据元素、数据元素：数据的基本单位。在不同的条件下，数据数据的基本单位。在不同的条件下，数据 元素又可称为元素、结点、顶点、记录等。元素又可称为元素、结点、顶点、记录等。 5 5、数据对象或数据元素类、数据对象或数据元素类：具有相同性质的数据元素具有相同性质的数据元素 的集合。的集合。 6 6、数据结构、数据结构：指互相之间存在着一种或多种关系的数据指互相之间存在着一种或多种关系的数据 元素的集合。数据元素之间的关系称为结构。元素的集合。数据元素之间的关系称为结构。 2021-7-1计算机科学导论30/30 1 1、逻辑结构逻辑结构：从具体问

18、题抽象出来的数学模型，是从用户角度从具体问题抽象出来的数学模型，是从用户角度 看到的数据元素之间的关系。看到的数据元素之间的关系。 常用的逻辑结构有：常用的逻辑结构有： （1 1）线性结构：）线性结构：数据元素之间存在着一对一的关系。数据元素之间存在着一对一的关系。 线性表，栈、队列、数组、字符串。线性表，栈、队列、数组、字符串。 （2 2）树形结构：）树形结构：数据元素之间存在着一对多的关系。数据元素之间存在着一对多的关系。 （3 3）图形结构：）图形结构：该结构的数据元素之间存在着多对多的关系该结构的数据元素之间存在着多对多的关系 ，图形结构也称作网状结构。，图形结构也称作网状结构。 4

19、4. .3 3.2 .2 数据结构的逻辑结构和物理结构数据结构的逻辑结构和物理结构 2021-7-1计算机科学导论31/30 2 2、物理结构、物理结构：也称存储结构，是数据结构在计算机 中的表示。存储结构有两种： （1 1）顺序存储：）顺序存储：逻辑上相邻的元素存储在物理位 置相邻的存储单元中。数组就是顺序存储。 （2 2）链式存储：）链式存储：逻辑上相邻的元素不要求其物理 位置相邻，链式存储结构通常借助于程序设计语 言中的指针来实现。 2021-7-1计算机科学导论32/30 1 1、线性表：、线性表：该结构的数据元素之间存在着一对一的逻辑关系。 通常记为： (a1，a2，ai-1，ai，

20、ai+1，an) （1 1）顺序表：）顺序表：用地址连续的一块存储空间顺序存放线性表的 各元素。 （2 2）单链表：）单链表：不用地址连续的一块存储空间顺序存放线性表 的各元素，元素之间的逻辑关系由指针指向。 4 4. .3 3.3 .3 基本基本数据结构介绍数据结构介绍 图图 链表示意图链表示意图 a1 an H a2 线性表的基础操作：构造、插入、删除、查找线性表的基础操作：构造、插入、删除、查找 2021-7-1计算机科学导论33/30 1 1、栈和队列：、栈和队列：是一种操作受限的线性表。是一种操作受限的线性表。 （1 1）栈的操作原则：）栈的操作原则：先进后出，后进先出。先进后出，后

21、进先出。LIFOLIFO 栈的基本操作：入栈、出栈、判断栈是否为空和溢出。栈的基本操作：入栈、出栈、判断栈是否为空和溢出。 栈示意图栈示意图 a3 a2 a1 入栈入栈出栈出栈 top 2021-7-1计算机科学导论34/30 （1 1）栈的操作原则：）栈的操作原则：先进后出，后进先出。先进后出，后进先出。LIFOLIFO 栈的基本操作：入栈、出栈、判断栈是否为空和溢出。栈的基本操作：入栈、出栈、判断栈是否为空和溢出。 图图5.13 队列示意图队列示意图 a1 a2 a3 a4 a5 入队入队 出队出队 2021-7-1计算机科学导论35/30 3 3、树形结构：、树形结构：该结构的数据元素之

22、间存在着一对多的该结构的数据元素之间存在着一对多的 关系。关系。 2021-7-1计算机科学导论36/30 二叉树：二叉树：每个结点最多只有两个子树，且分左子树每个结点最多只有两个子树，且分左子树 和右子树。和右子树。 二叉树的应用：二叉树的应用：哈夫曼编码、二分查找树、二叉排序树、 堆排序。 满二叉树满二叉树 完全二叉树完全二叉树非完全二叉树非完全二叉树 2021-7-1计算机科学导论37/30 二叉树的存储二叉树的存储 顺序存储结构顺序存储结构 l用一组连续的存储单元（数组）存放二叉树中的结点。一般用一组连续的存储单元（数组）存放二叉树中的结点。一般 是按照二叉树结点从上至下、从左到右的顺序存储。是按照二叉树结点从上至下、从左到右的顺序存储。 链式存储结构链式存储结构 l用链表来表示一棵二叉树。链表中每个结点由三个域组成，用链表来表示一棵二叉树。链表中每个结点由三个域组成， 除了数据域外，还有两个指针域，分别用来给出该结点的左除了数据域外，还有两个指针域，分别用来给出该结点的左 子结点和右子结点所在的链结点的存储地址。子结点和右子结点所在的链结点的存储地址。 非完全二叉树的链式存储非完全二叉树