数据结构与算法1.ppt

《大学计算机基础》 第6章 数据结构与算法 程序是什么？ 程序=数据结构+算法！ 算法与数据结构一览表 例：某校对100个学生进行奖励，学生信息存在磁盘文件“file.dat”中，条件是其三门成绩全部在90分以上才能进行奖励，打印出被奖励学生的学号。 以C语言为例，程序代码如下： #include stdio.h Void main() { struct stu /*数据类型*/ { int num; float score[3]; }a[100]; /* 定义变量*/ FILE *fp； Int I,j; fp=fopen(“file.dat”,”r”); /* 打开文件file.dat*/ for(i=0;i100;i++) { Fread(a[i],sizeof(struct stu),1,fp); /* 从文件中读取数据*/ for(j=0;j3;j++) if(a[i].score[j]90) /* 判断三门成绩是否全都高于90分*/ break; if(j=3) /* 如果符合条件，输出其学号*/ printf(“num:%d”,a[i].num); } Fclose(fp); } 由此可见，程序包括：对数据的描述，在程序中要指定数据的类型和数据的组织形式。 对操作的描述，即对数据的操作处理步骤 第6章 数据结构与算法 数据结构（data structure） ： 对数据的描述。即在程序中要指定数据的类型和数据的组织形式。 算法（algorithm）： 对操作的描述。即对数据的操作处理步骤。 程序：就是用计算机语言表示的数据结构和算法。 程序设计：用计算机语言编写程序的过程。两个基本步骤： 1、设计数据结构和算法。 2、用一种计算机语言表示出来。 因此，数据结构与算法是程序设计的基础。 6.1 算 法 6.1.1 算法的基本概念 算法（algorithm）： 对操作的描述。即对数据的操作处理步骤。 算法的表示方法： 自然语言、流程图、N-S流程图、伪代码、计算机语言 案例：计算sum=1+2+3+…+n的算法 一、用自然语言描述 1、输入n，即数据个数； 2、设置累加器sum，初始制为0；设置计数器i，初始值为1。 3、当i小于或等于n时，做累加，即将sum与i相加，其和再放入sum中。计数器i取下一个数，即i等于i+1，直到i大于n时终止。 4、输出累加和sum。 二、流程图描述： 三、N-S图描述： sum=1+2+3+…+n的算法 N-S图是美国学者I.Nassi和B.Shneiderman在1973年提出的一种流程图，其主要特点是不带有流程线，整个算法完全写在一个大的矩形框中。 四、伪代码描述： sum=1+2+3+…+n的算法  就是用文字和符号的方式来描述算法。在实际应用中，人们往往用接近于某种程序语言的代码形式作为伪代码。这样可以方便编程。 伪代码方式 五、计算机语言描述：程序用C语言描述sum=1+2+3+…+n的算法 main() { int n; int sum=0,i=1; scanf(“%d”,n); for(i=1;i=n;i++) {sum=sum+i;} printf(“sum=%d\n”,sum); } 一、算法的5个基本特征 1、可行性 2、确定性 3、有穷性 4、有零个或多个输入 5、有一个或多个输出 二、算法的2个基本要素 1、对数据的运算和操作 2、算法的控制结构。  算法的基本要素之一：对数据的运算和操作 在计算机系统中，基本的运算和操作有以下四类： ① 算术运算：主要包括加、减、乘、除等运算。 ② 逻辑运算：主要包括“逻辑与”、“逻辑或”、“逻辑非” 等运算。 ③ 关系运算：主要包括“大