程序设计基础知识教育课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算机科学导论,*,/30,程序设计基础知识PPT讲座,4.1,算法与程序,（教材第,5,章）,4.1.1,算法的概念,为解决一个问题而采取得方法和步骤，称为算法。,算法就是被精确定义的一组规则，规定先做什么，再做什么，以及判断某种情况下做哪种操作；,算法是步进式的完成所需任务的过程。,4.1.,2、程序的概念,程序是编程者写的、计算机能够理解并执行的一些命令的集合，是解决问题的具体算法在计算机中的实现。,4.1.,3、算法的特点及评价标准,算法必须具有以下特性：,有穷性。,确定性。,有效性。,输入及输出。,4.1.,4、算法的表示,（1）用自然语言表示,例如，求三个数的最大值的问题，可以描述为：先比较前两个数，找到大的那个数，再让其与第三个数进行比较，找到二者中大的数即为所求。,处理A,处理B,(a),处理A,处理B,真,假,条 件,(b),处理 A,假,真,条 件,(c),三种基本结构,2）用传统流程图表示,输入a,b,c,置max=a,置max=c,真,假,if(cmax),置max=b,真,假,if(bmax),实例：,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,maximum=max(num1,num2,num3);,printf(nMaximum is:%d,maximum);,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,语言程序：求,1,10,的累加和。,顺序结构,程序示例：通过键盘输入一个三角形的底和高，计算其面积并输出。,（2）结构化语言控制结构,main(),float width,height,area;/*,定义变量*,/,printf(nEnter width and height:);/*,输出提示信息*,/,scanf(“%f,%f”,/*,通过键盘输入底和高*,/,area=(width*height)/2.0;/*,计算面积*,/,printf(nThe arae is:%f,area);/*,输出面积的值*,/,分支结构,程序示例：根据输入的学生成绩对其进行判断处理，如果成绩及格，则输出,Passed,，否则输出,Failed,。,main(),float score;/*,定义变量*,/,printf(nEnter a score:);/*,显示提示信息*,/,scanf(%f,/*,通过键盘输入一个成绩*,/,if(score=60.0),printf(nPassed);/*,大于等于,60,输出,Passed*/,else,printf(nFailed);/*,小于,60,输出,Failed*/,程序示例：从键盘上输入,10,个整数，求其累加和并输出。,循环结构,main(),int i,num,sum;/*,定义变量*,/,sum=0;/*,累加变量清零*,/,for(i=1;i=10;i+)/*,循环次数为,10*/,printf(Enter a data:n);,/*,显示提示信息*,/,scanf(%d,/*,通过键盘输入一个整数*,/,sum=sum+num;,/*,累加求和*,/,printf(“nsum=%d,sum);/*,输出累加结果*,/,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 基本,数据结构介绍,图 链表示意图,a1,an,H,a2,线性表的基础操作：构造、插入、删除、查找,1、栈和队列：,是一种操作受限的线性表。,（1）栈的操作原则：,先进后出，后进先出。LIFO,栈的基本操作：入栈、出栈、判断栈是否为空和溢出。,栈示意图,a3,a2,a1,入栈,出栈,top,（1）栈的操作原则：,先进后出，后进先出。LIFO,栈的基本操作：入栈、出栈、判断栈是否为空和溢出。,图5.13 队列示意图,a,1,a,2,a,3,a,4,a,5,入队,出队,3、树形结构：,该结构的数据元素之间存在着一对多的关系。,二叉树：,每个结点最多只有两个子树，且分左子树和右子树。,二叉树的应用：,哈夫曼编码、二分查找树、二叉排序树、堆排序。,满二叉树,完全二叉树,非完全二叉树,二叉树的存储,顺序存储结构,用一组连续的存储单元（数组）存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。,链式存储结构,用链表来表示一棵二叉树。链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点的左子结点和右子结点所在的链结点的存储地址。,非完全二叉树的链式存储,4、图形结构：,该结构的数据元素之间存在着多对多的关系，图形结构也称作网状结构。,图的类别：,无向树、有向树、带权无向树、带树有向树。,B,A,D,C,G,2,：,B,A,D,C,G,3,：,2,3,4,5,6,B,A,D,C,G,4,：,2,3,4,5,6,图的基本运算：,图的遍历（深度优先、宽度优先）、图的最小生树、最生路径、拓朴排序。,图的应用,求最短路径,网络性能分析,思考题,名词解释,：,机器语言,、汇编语言、高级语言,、程序,、算法,、数据,、数据项、,数据元素,、数据对象、,数据结构、线性结构、树,、二叉树、图。,说明程序与算法的联系和区别。,描述算法的方法有哪些？,程序设计语言有哪些类，每个类的语言有什么特点？请尽可能多列举你所知道的程序设计语言。,学习一种高级语言，应主要掌握哪些内容？,面向对象程序设计语言与面向过程程序设计语言有什么区别？,结构化程序三种基本,控制结构是什么,？,高级语言中，变量一般要先定义再使用，这样一种规定有什么好处？,什么,是,数据结构？,有哪几种基本逻辑结构？,学习数据结构课程的目的是什么？,什么是线性表、栈和队列？,什么是树和二叉树？查阅文献，举例说明树或二叉树在程序设计中的作用。,图有哪几种形式？举例说明图的应用。,程序设计语言、数据结构、算法分析与设计,3,门课程对于提高程序设计能力和培养程序设计思维各有什么作用？,