chapter_1ppt整理.ppt

第一章 绪论 主要内容 为什么要学习数据结构？ 什么是数据结构？ 基本概念和术语 抽象数据类型的表示与实现 算法和算法的量度 1、为什么要学习数据结构？ 介于数学、计算机软件、硬件三者之间的核心课程 一般程序设计（尤指非数值计算的程序设计）的基础 设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。 2、什么是数据结构？ Niklaus Wirth： Algorithm + Data Structures = Programs 程序:为计算机处理问题编制一组指令集 算法: 处理问题的策略 数据结构: 问题的数学模型 数值计算的程序设计问题 非数值计算的程序设计问题 例1:图书馆书目检索系统自动化问题 概括地说： 数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。 3、基本概念和术语（1） 3、基本概念和术语（2） 3、基本概念和术语（3） 3、基本概念和术语（4） 3、基本概念和术语（5） 3、基本概念和术语（6） 3、基本概念和术语（7） 3、基本概念和术语（8） 4、抽象数据类型的表示与实现 抽象数据类型的定义格式 5、算法和算法的量度 5.1 算法及其表示 5.2 算法设计的要求 5.3 算法效率的度量 5.4 算法的存储空间需求 5.1 算法及其表示 有下述两段描述,违反了算法哪些特性？ （1） void exam1() { n=2; while(n%2==0) n=n+2; printf(“%d”, n); } （2） void exam2() { y=0; x=5/y; printf(“%d, %d”,x,y); } 5.2 算法设计的要求 5.3 算法效率的度量 事后统计：运用计算机的计时功能统计算法的运行时间 缺陷: (1)要运行算法对应的程序； (2)时间统计结果依赖于计算机软、硬件环境； 事前分析估计　和算法执行时间相关的因素有： 算法采用的策略 问题的规模 书写程序的语言 编译器产生的机器代码的质量 计算机执行指令的速度。 算法的时间量度 例2: 例3: 选择法排序 (1)void select_sort(int a[],int n) (2){ for(i=0;in-1;++i) (3) { j=i; (4) for(k=i+1;kn;++k) (5) if(a[k]a[j]) j=k; (6) if(j!=i) a[j]-a[i]; (7) } (8)} 例4：起泡法排序 例：百钱买百鸡问题(2) 例 ：百钱买百鸡问题(3) 方法4：用一重循环 由x+y+z = 100和5*x+3*y+z/3=100合并为一个方程： 14*x+8*y = 200, 进一步简化为: 7*x+4*y=100 x不超过14，并可以进一步判断x必为4的倍数，有： for(i=0;i=14;i+=4) { j = (100 –7*i)/4; k=100 –i –j; printf(“%d,%d,%d\n”, i,j,k); } 方法一的循环次数为：100*100*100次； O(n3) 方法二的循环次数为：100*100次； O(n2) 方法三的循环次数为：21*33次； O(n2) 方法四的循环次数为：4次。 O(n) 5.4 算法的存储空间需求 本章小结 1、掌握名词术语和基本概念 2、理解算法五个要素的含义 3、掌握计算语句频度和估算算法时间复杂度的方法 作业： （纸或本 9月17日交） 1、有如下所示的逻辑结构图，试给出其数据结构二元组表示。 2、下列是用二元组表示的数据结构，画出它对应的逻辑图形表示，并指出它属于何种结构。 A=(K,R),其中：K={a,b,c,d,e,f,g,h} R={r} r={d,b,d,g,d,a,b,c,g,e,g,h,e,f} 3、分析下面程序段中循环语句的执行次数。 4、设n为正整数，计算下列程序的时间复杂度。 方法2：用两重循环： for(i=0;i100;i++) for(j=0;j100;j++) { k=100 –i –j ;//小鸡的数目可以由母鸡数和公鸡数得到。 if(k%3==0 5*i+3*j+k/3==100) printf(“%d,%d,%d\n”,i,j,k); } 方法3：用两重循环