算法语言与数据结构（第1章）

《算法语言与数据结构（第1章）》由会员分享，可在线阅读，更多相关《算法语言与数据结构（第1章）（52页珍藏版）》请在金锄头文库上搜索。

1、算法语言与数据结构,信息与物流管理系王健,西安财经学院管理学院,课程内容： 计算机语言工具C语言 计算机软件的基础知识数据结构 课时安排： C语言36学时 数据结构36学时 上机18学时,教材： C程序设计第三版 谭浩强 清华大学出版社 数据结构C语言版 严蔚敏 清华大学出版社 参考书：程序设计基础第三版 吴文虎 清华大学出版社 数据结构C语言版 耿国华 高等教育出版社,算法语言与数据结构,算法语言与数据结构,一、教学对象 信息管理与信息系统专业第3学期二、教学目标 程序设计的重要性 程序设计的基本概念与基本方法 程序结构与相应语句 编码与上机调试 编程解题的思路与典型方法 算法及算法步骤 问

2、题规模与时空复杂度估计 数据的组织与结构 典型数据结构的性质、描述、操作 数据结构的设计与应用,算法语言与数据结构,三、教学重点 程序设计的基本概念，基本方法； 在 C语言的环境下，学会如何针对问题进行分析，得出数学模型，理出算法并编程实现； 有条有理有根有据的编程实践； 数据的几种基本结构的组织、描述、操作实现。 养成良好的编程风格与习惯； 现实问题中数据结构的设计应用 重在思维方法的学习，鼓励创新。,算法语言与数据结构,四、指导思想 1. 强化实践 这门课主张程序设计是高强度的脑力劳动，不是听会的、也不是看会的，而是练会的。这可能与以往的教学安排最大的不同之处。2. 鼓励和引导探索式的学习

3、 按照建构主义的学习理论，学生（作为学习的主体）在与客观环境（所学内容）的交互过程中构建自己的知识结构的。引导学生在解题编程的实践中探索其中带规律性的认识。将感性认识升华到理性高度。3. 突出重点 重点放在思路、算法、编程构思和程序实现上。语句只是表达工具，要求堂上积极思考，尽量当堂学懂，重在训练利用计算机编程手段分析问题和解决问题的能力。4. 养成良好的编程习惯 强调可读性; 变量要加注释； 程序构思要有说明； 学会如何调试程序; 尽可能优化; 对运行结果要做正确与否的分析。,算法语言与数据结构,5. 考试方法 已建立试题库，题目随机抽取 笔试80%，以方法、思想和编程能力为主；上机实践20

4、%。6. 学习方法 动手动脑，理论指导下的实践 有条有理的实践。实践出真知 “自学、动手、应用、上网” 在编写大量程序之后，才能感到运用自如。7. 学习心态 “自立、自信、自尊、自强”，要求做到越学越会充满信心。,算法语言与数据结构,五、教学内容安排 C程序设计部分 1. 概论：程序设计的基本概念与基本方法；怎样才能学好这门基础课 2. 程序的设计基础 编程关键：逻辑思维与问题求解人是怎样让计算机帮助自己解题的 3.数据的组织方式一：数组 4.模块化：函数与函数调用 分治思想：递归算法及其实现。 5.逻辑指代与物理指代：指针。 6.数据的组织方式二：结构体。 7.数据的组织方式三：链表与树。

5、数据结构部分 8.数据的组织（数据结构概述） 9.线性表（数组、链表） 10.线性表的应用（堆栈、队列、串） 11.非线性问题 树及树的应用 12.非线性问题 图及图的应用 13.数据操作 查找 14.数据操作 排序,第1章 语言概述,1.0 程序设计基本概念,1.0.1 程序设计基本概念 程序（program）：为解决某一问题而设计的一系列指令，能被计算机识别和执行。 程序设计(programming)：设计、书写及检查程序的过程。包括分析问题、确定解决方法、设计程序结构，使问题内容或解题计划变为计算机能够接受的指令或语句序列的过程。 语言：(language)用于传达信息的表示方法、约定和

6、规则的集合。是人们交流信息的工具和媒介。 程序设计语言：人与计算机打交道时交流信息的一类媒介和工具，由语句（statement）组成。 语句（statement）：组成语言的基本单位，包含语法和语义两个方面。 语法(syntax)：定义构造语言的正确的表达式或句子所需的各种规则。 语义(semantic)：对构成语言成分的含义的定义和说明。,1.0.2 程序设计语言程序设计语言可简单的分为低级语言和高级语言两类。 低级语言包括机器语言和汇编语言。 高级语言是由一些接近于自然语言和数学语言的语句组成。 目前最常用的高级语言有： FORTRAN、COBOL、BASIC、PASCAL、C、 ADA、

7、PROLOG。 面向对象程序设计语言如：Smalltalk、C+、Java和Visual Basic、 Visual C+ 、 Delphi等。,1.0 程序设计基本概念,程序设计语言发展： 机器语言：（machine language）计算机直接使用的二进制形式的程序语言或机器代码。 汇编语言：（assembler language）一种面向机器的用符号表示的低级程序设计语言。相当于机器指令的助记符号，与机器语言很接近。 高级语言：（highlevel language）是易为人们所理解的完全符号化的程序设计语言。 源程序：用户用高级语言编写的程序称为，C源程序文件名字后缀一般必须为“.c“

8、。 程序加工：高级语言编写的程序，计算机不能直接执行，需要把这个程序转换成二进制代码的机器语言程序。这种转换过程称为程序加工。 汇编程序（assembler）：将汇编语言程序翻译成机器语言程序的程序。 编译程序（compiler)：把用高级语言写的源程序转换为相应的机器语言目标模块(object module)的程序。,1.1 程序设计基本概念,1.0 程序设计基本概念,程序加工过程： 编译 目标模块包括程序及连接程序的控制信息。目标程序文件名字后缀“.obj“。 连接（linker）：将目标模块和其它一些必要的功能模块装配在一起，生成可执行文件，执行程序文件后缀为“.exe“。 演示程序执行

9、过程：,1.0 程序设计基本概念,1.1 C语言的发展简史和特点,1语言的诞生与发展（1）在C语言诞生以前，系统软件主要是用汇编语言编写的。由于汇编语言程序依赖于计算机硬件，其可读性和可移植性都很差；但一般的高级语言又难以实现对计算机硬件的直接操作（这正是汇编语言的优势），于是人们盼望有一种兼有汇编语言和高级语言特性的新语言。（2）语言是贝尔实验室于70年代初研制出来的，后来又被多次改进，并出现了多种版本。80年代初，美国国家标准化协会（ANSI），根据语言问世以来各种版本对语言的发展和扩充，制定了ANSI C标准（1989年再次做了修订）。本书以ANSI C新标准来介绍。 （3）目前，在微机

10、上广泛使用的语言编译系统有Microsoft C、Turbo C 、Borland C等。虽然它们的基本部分都是相同的，但还是有一些差异， 所以请大家注意自己所使用的编译系统的特点和规定（参阅相应的手册）。 本书选定的上机环境是TC V2.0（DOS操作系统）。,CPL语言,BCPL语言,B语言,C语言,C+语言,规模较大，难以实现,无数据类型,功能更强大，面向对象,接近硬件，但过于简单，功能有限,用其编写了UNIX操作系统,1.1 C语言的发展简史和特点,2 C语言的特点C语言同时具有汇编语言和高级语言的优势。（1）语言简洁、紧凑，使用方便、灵活。（2）运算符极其丰富。（3）生成的目标代码质

11、量高，程序执行效率高。（4）可移植性好（较之汇编语言）。（5）可以直接操纵硬件。 3. C语言的结构在C语言中，除实现顺序、选择和循环三种基本结构等的9条控制语句外，输入输出操作均由标准库函数（不是C语言的组成部分）来实现。所以学习C语言，不仅要学习这9条控制语句和各种运算符，而且要学习并掌握常用标准库函数的使用。,1.1 C语言的发展简史和特点,1.2 语言程序的结构与书写规则,1.2.1 语言程序的总体结构示例 一个完整的语言程序，是由一个main()函数（又称主函数）和若干个其它函数结合而成的，或仅由一个main()函数构成。案例1.1 仅由main()函数构成的语言程序。/*案例代码文

12、件名：obama_1.C*/ /*功能：仅由main()函数构成的语言程序示例*/main() printf(“This is a C program.n”);程序运行结果：This is a C program.,案例1.2 求最大值的语言程序。 /*案例代码文件名：AL1_2.C*/ /*功能：由main()函数和1个其它函数max()构成的语言程序示例*/int max(int x, int y) return( xy ? x : y ); main() int num1,num2;printf(“Input the first integer number: ”);scanf(“%d”

13、, 程序运行情况：Input the first integer number:6Input the second integer number:9max=9,1.2 语言程序的结构与书写规则,案例1.3 计算三角函数的语言程序。/ Sample1.c 1 #include /预编译命令,将标准输入输出函数/作为头文件包扩到用户源文件中 2 #include /预编译命令,将系统提供的数学函数/作为头文件包扩到用户源文件中 3 void main( ) /主函数，名为main，/void是类型说明符（无返回值） 4 /函数体.开始 5 float a,b,c; /声明部分.定义变量类型 6 b

14、=30.0; /执行部分.赋值语句 7 a=sin(b*3.14159/180); /执行部分.赋值语句 8 printf(“%fn“,a); /执行部分.输出语句 9 /函数体.结束,1.2 语言程序的结构与书写规则,案例1.4 C+程序实例#include void main(void) cout“ This is a C+ program. n“;cout“Welcome to c+!n“; ,1.2 语言程序的结构与书写规则,1.2 语言程序的结构与书写规则,1.2.2 语言程序的总体结构说明,3、“ #include ”这条命令是让文件”的stdio.h内容包含到新建的程序中去。C+

15、中(“iostream .h”)与之对应。 4、 stdio.h 是C系统定义的一个 “头文件”，在这个头文件中设置了C的输入/输出 ( I / O ) 相关环境，定义了输入函数/流 scanf()/ cin 和输出函数/流 printf() /cout 对象。,1.2 语言程序的结构与书写规则,案例1.5 计算三角函数的语言程序。/* calc.c*/ 1 #include 2 #include 3 void main( ) 4 printf(“%fn“, sin(30.0*3.14159/180); ,1、 以符号“#”开头的行，称为编译予处理行。 2、 “#include” 称为文件予处

16、理命令。,5、“#include”，这条命令是让系统中已经有的常用的数学函数包含到新建的程序中去。有了它你才能使用正弦、余弦函数的公式。 6、main( ) 是每一个C程序都必须有的，称为主函数。你可以把它看成是程序的入口。在 main 面前的 void 表示我们写的这个主函数 main( ) 没有返回值，即它不代表计算出来的是什么值，它仅仅是规范了完成计算器所作的一系列步骤，这些步骤用花括号 括起。 关于 main( ) 主函数的详细说明将在第二章中介绍。在这个计算三角函数的程序中实际上只有一行代码， printf(“%fn”，三角函数算式)。按照这种模式，两头不动，你只要改变中间部分就可以计算任何算式（当然是 math.h 支持的才行）这里printf是系统的关键字，代表标准输出设备，表示输出操作，可将其右侧的数据送至显示器上。程序中右侧就是三角函数算式的数值。 “n ”表示在屏幕显示计算结果之后，换一行。(c+ “endl ”),