2020/2/29
计算机科学导论
25/30
4.3 数据结构（与教材第8章相关）
4.3.1 数据结构与问题求解 4.3.2 数据结构的基本概念和术语 4.3.3 基本数据结构介绍
线性结构 树形结构 图状结构
2020/2/29
计算机科学导论
26/30
4.3.1 数据结构与问题求解
计算机求解问题的步骤是： （1）从具体问题抽象出一个数学模型； （2）设计解此数学模型的算法； （3）编出程序，直至得到最终的解答。
第4讲 程序设计基础知识
4.1 算法
了解什么是算法，算法的描述方式。
4.2 程序设计语言
以c语言为例，介绍高级程序设计语言的基本语 法、程序结构，以及程序设计的一般方法，应用 高级语言进行程序设计。
4.3 数据结构
为要解决的目标问题设计出高效的数据逻辑结 构和存储结构，保证算法和程序的效率；
2020/2/29
2020/2/29
计算机科学导论
21/30
（2）结构化语言控制结构
顺序结构
➢程序示例：通过键盘输入一个三角形的底和高，计算其 面积并输出。
main( )
{
float width,height,area;
/*定义变量*/
printf("\nEnter width and height:"); /*输出提示信息*/
main( ) {
float score; printf("\nEnter a score :"); scanf("%f",&score); if (score>=60.0)
printf("\nPassed "); else
printf("\nFailed "); }
/*定义变量*/ /*显示提示信息*/ /*通过键盘输入一个成绩*/
2020/2/29
计算机科学导论
20/30
5、控制结构
（1）最常见的控制转移语句是GOTO语句，其一般形式是： GOTO<语句标号>
一个fortran语言程序：求1～10的累加和。
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
1、字符集：每个语言都有一个基本字符集，程序是符合语 法的字符串。
以C语言为例： ① 英文字母（大、小写）：A，B，C，… ，Z ；a，b ，c，… ，z ② 数字：0，1，2，…，9 ③ 特殊字符：＋, ，*，/，％，＝，_，（，）～，！ ，◎，＃，$，^，&等 ④ 转义字符：\n，\t，\v，\b，\r，\f，\a，\"，\，\\， \ddd，\xhh等
2020/2/29
计算机科学导论
11/30
③ 高级语言
➢由自然语言和数学公式表示的语言。 ➢是一种独立于机器硬件的语言。 ➢高级语言程序需要编译后才能执行。
高级语言程序片段
Z=X + Y
//把内存单元X中的数与Y中的数相加，结果存入Z单元
2020/2/29
计算机科学导论
12/30
影响较大的高级语言：
2020/2/29
计算机科学导论
19/30
4、子程序
（1）子程序：可独立编译的程序单元。 （2）子程序一般具备如下三种机制：
➢ 子程序说明，它给出子程序与其他程序单元的接口； ➢ 子程序体，它实现子程序的数据结构和控制结构； ➢ 调用方式。 （3）不同语言的子程序： ➢ C的基本程序单位是函数； ➢ PASCAL的基本程序单位的子程序（过程与函数）； ➢ MODULA程序的组成单位是模块module； ➢ ADA的基本程序模块是程序包（package）。
2020/2/29
计算机科学导论
15/30
⑥ 人工智能程序设计语言
适合于知识表示和逻辑推理。 常用人工智能程序设计语言
LISP
可以解决人工智能中的符号处理问题。
PROLOG
自动实现模式匹配、自动回溯这两种人工智能中常用的基本操 作。
2020/2/29
计算机科学导论
16/30
4.2.2 程序设计语言的机制
/*大于等于60输出Passed*/
/*小于60输出Failed*/
2020/2/29
计算机科学导论
23/30
循环结构
➢程序示例：从键盘上输入10个整数，求其累加和并输出。
main( )
{
int i, num, sum;
/*定义变量*/
sum=0;
/*累加变量清零*/
for (i=1; i<=10;i++)
0011 0000 01101110 //把0000号寄存器中的数存入地址为01101110的内存单元中
2020/2/29
计算机科学导论
10/30
② 汇编语言
➢由助记符指令构成的语言。 ➢也是一种依附于机器硬件的语言。 ➢汇编语言源程序需要汇编后才能执行。
汇编语言程序片段
MOV R5, X //把内存单元X中的数装入R5寄存器 ADD R5, Y //把R5中的数与Y单元中的数相加，结果存入R5 MOV Z, R5 //把R5中的数存入Z单元中
执行的一些命令的集合，是解决问题的 具体算法在计算机中的实现。
2020/2/29
计算机科学导论
3/30
4.1.3、算法的特点及评价标准
算法必须具有以下特性： ➢ 有穷性。 ➢ 确定性。 ➢ 有效性。 ➢ 输入及输出。
2020/2/29
计算机科学导论
4/30
4.1.4、算法的表示 （1）用自然语言表示
PASCAL语言 C语言
2020/2/29
计算机科学导论
14/30
⑤ 面向对象程序设计语言
➢ 将问题分解为对象。使人们对复杂系统的认识过程与程 序设计过程尽可能一致。
➢ 对象将自己的属性和方法封装成类。 ➢ 对象之间通过消息传递来相互联系。
常用面向对象程序设计语言 Simula 67 C++ Java
(c)
真
假 if(b>max)
三种基本结构
置max=b
真 置max=c
假 if(c>max)
2020/2/29
计算机科学导论
6/30
begin
3) 用伪码表示
输入 a,b,c;
伪码是用一种介于自然语言 和计算机语言之间的文字和符 号来描述算法。接近计算机语 言，便于向计算机程序过渡。 比计算机语言形式灵活、格式 紧凑，没有严格的语法格式。
和值之分，名是一个数据项的标识，值是它的一个 可能取值。
2020//29
计算机科学导论
28/30
4、数据元素：数据的基本单位。在不同的条件下，数据
元素又可称为元素、结点、顶点、记录等。
5、数据对象或数据元素类：具有相同性质的数据元素
2020/2/29
计算机科学导论
17/30
2、名字说明 预先说明程序中将要使用的对象(常量和变量)的名字，
有利于编译程序检查对象使用方式的合法性，帮助程序员发 现错误。
➢ 有些语言（如C语言）要求对象预先显示说明。 ➢ 某些语言(例如FORTRAN和BASIC)并不要求用户显式说
明程序中对象的名字，第一次使用的名字即被看作是 对这个名字的说明。
24/30
4.2.3 程序设计风格
主要体现在5个方面
➢ 标识符的命名要风格统一、见名知义。 ➢ 一般一行写一条语句，一条长语句可以写在多行上，但
尽量不要把多条语句写在一行上。 ➢ 采用缩进格式，即同一层次的语句要对齐，低层次的语
句要缩进若干个字符，增加程序的可读性。 ➢ 适当书写注释信息，有助于阅读者对程序的理解。 ➢ 尽量少用goto语句，否则容易导致程序结构混乱。
scanf(“%f,%f”,&width,&height); /*通过键盘输入底和高*/
area=(width*height)/2.0;
/*计算面积*/
printf("\nThe arae is :%f ",area);
/*输出面积的值*/
}
2020/2/29
计算机科学导论
22/30
分支结构
➢程序示例：根据输入的学生成绩对其进行判断处理，如 果成绩及格，则输出Passed，否则输出Failed。
2020/2/29
计算机科学导论
9/30
① 机器语言
➢由二进制编码指令构成的语言。 ➢是一种依附于机器硬件的语言。 ➢机器语言程序可以直接执行。
机器语言程序片段
0001 0101 01101100 //把地址为01101100的内存单元中的数装入0101号寄存器
0001 0110 01101101 //把地址为01101101的内存单元中的数装入0110号寄存器 0101 0000 01010110 //把01101100和01101101中的数相加,结果存入0000号寄存器
关键字外部语法
置max=a; if(b>max)then
置max=b; endif if(c>max)then
置max=c;
自然语言内部语法
endif
输出max;
stop
2020/2/29
计算机科学导论
7/30
4) 用程序实现
#include "stdio.h“
int max(int x,int y,int z) {
2020/2/29
计算机科学导论