程序设计基础知识.ppt

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