数据结构与算法实验.ppt

1、数据结构与算法 数据结构与算法实验 2012.9-2013.1,纸上得来终觉浅，绝知此事要躬行 读+写+讨论,学习方法,上课时间:周二1-2节 周四1-2节 上机时间:周四3-4节 答疑时间:周一15:00-16:30 239 周三13:00-15:00 239,所有作业按时交，注释不少于30% 书面作业晚依天9折,放慢速度？ 9/25 时常复习以前讲的？ 8个小时？ 全部/部分？ 只会课上讲的？ 答疑了吗？,讲但不是全部 部分内容需要自己学习 希望预习,北大： 计算概论 周4学时（48） 3学分 程序设计实习 周4学时 3学分 数据结构与算法 周4学时 3学分 数据结构与算法实习 周2学时

2、2学分,首师大： C语言程序设计 4+2 面向对象程序设计 3+2 数据结构与算法 4+2 算法设计与分析 3,复旦大学 3+2 浙江大学 4 湖南师大 4+1 南京师大 4+2 华东师大 3+2 上海师大 3+2 杭州电子科技大学 4+1,希望： 提前5分钟到教室，不迟到 不吃东西 手机静音 随时问，积极响应 按时交作业,对老师的希望？,数据结构学什么 数据结构的地位和作用 怎么学好数据结构,教学内容,特点：用数学方程进行数值运算,称这类问题的数学模型是数学方程,第一章绪论,例1：数学方程 （1）用二分法求方程的根 （2）用迭代法求a的平方根,例2:学生成绩管理系统,建立一个小型的学生成绩管

3、理系统，该系统具有输入、查询、修改、打印功能。 实验要求： （1）每位学生数据中包含学号、姓名、性别、年龄、五门课的成绩。要求学生人数不少于16人，从文件中输入数据 （2）能根据学号或姓名查询任一学生某门课程成绩或所有课程成绩 （3）系统界面自行设计 （4）能修改学生的任何一个数据，并设置相应的修改口令 （5）能按总成绩从高到低显示所有学生的数据，包括每个学生的平均分，并输出到文件。,涉及： 数据录入 数据查询 数据维护 数据排序、输出,需要： 建一张表 确定表中前后数据的关系 实现对表进行操作的方法,例3:扑克牌接龙游戏,洗牌 发牌、出牌、移牌 比较、判断 输赢判断,（1）表示所有扑克牌 （

4、2）实现各种游戏动作,特点：两个数据之间有一定顺序 主要操作有：插入、查找、修改、删除 称这类问题的数学模型为线性表(线性结构),学生成绩管理系统,扑克牌接龙游戏,.,.,例4 人机对奕,.,.,.,.,.,井字棋、中国象棋、国际象棋 对奕过程中可能出现的棋盘状态称为格局,格局之间的关系由下棋规则确定 从一个格局中可以派生出若干个新格局 从新格局又可以派生出更新的格局 整个对奕过程可能派生出的所有格局就象一棵倒挂的树 树根为对奕开始的格局 树叶为可能出现的一种结局 对奕的过程就是从树根走到树叶的过程,表示每一种格局 表示格局之间的派生关系 给出对奕的算法：从所有儿子格局中找出 最有利的格局,需

5、要,8,7,1,4,3,2,9,13,6,5,14,10,15,11,12,1,2,3,5,6,7,9,10,11,4,8,12,13,14,15,15谜问题,例5 文件系统,/ (root),bin,lib,user,etc,math,ds,clg,yin,tao,xie,Stack.cpp,Queue.cpp,Tree.cpp,这类问题的数学模型称为树（树型结构、层次结构） 树的特点： 除根外每个结点有唯一一个双亲(上级，祖先) 除叶子结点外，每个结点可以有多于一个儿子 树的操作：各种遍历搜索,例6 多叉路口交通灯管制 多叉路口需要设几种颜色的灯才能使车辆互不相撞且车流量最大,需要：表示圆

6、圈（道路） 表示边（是否冲突） 给出染色方法,着色问题,例7 最短路径问题 油田铺设管道，把原油送到加工厂，要求所铺设的管道最短,特点：任何两个数据之间都可以有关系(单向、双向) 操作：遍历、染色、最短路径 这种数学模型称为图,用计算机解决一个实际问题的步骤：,问题分析 建立模型 确定算法 设计程序 上机调试 结 果,数据结构 是一门研究计算机的操作对象 以及操作对象之间的关系 和对操作对象实施的典型操作 的学科,1.1 什么是数据结构,操作对象 关系 典型操作,1.2 基本概念和术语,数据：Data 数据是计算机化的信息（对现实世界的事物采用计算机能够识别、存储和处理的形式所进行的描述） 数

7、值性数据 非数值性数据,数据元素：Data Element 数据的基本单位，如格局、结点 通常作为一个整体进行考虑和处理 数据元素的组成成员称为数据项,数据项：Data Item 数据的最小单位 一个数据元素由多个数据项组成,数据对象：Data Object 具有相同性质的数据元素的集合 如所有书目、所有扑克牌、所有格局、所有道路,数据类型：Data Type,数据结构：Data Structure,（1）相互间存在一种或多种特定关系的数据元素的集合 一种或多种关系称为结构 有4种基本结构：,struct student /数据类型 int num; char name12; char sex

8、; int age; int score5; int scoresum; s50; /数据对象,数据项,s0、s1、s2、. 数据元素 数组-数据关系的表示,struct stu /数据类型 int num; int score; struct stu *next; *head,*p1;,数据项,*p1、*head、. 数据元素 链表-数据关系的表示 head为首的数据元素构成数据对象,（2）数据元素+关系 数据结构是一个二元组： Data_structure=(D, S) D:数据元素的有穷集合 S:数据之间有穷关系的集合,例：DS1=（D，S） D=V1,V2,V3, V4 S=, , ,

9、 , ,其中： 关系的描述是数据元素之间的逻辑关系， 称为数据的逻辑结构 数据元素及其逻辑关系在机内的表示 称为数据的物理结构，或数据的存储结构,数据的逻辑结构,a1,a2,a3,a4,a5,逻辑结构,物理结构（一）,物理结构（二）,a1,a2,a3,a4,a5,a3,a4,a2,a5,a1,0,关系的表示方法,数据的存储结构借助于高级语言中的数据类型来描述,顺序映象 非顺序映象,链式存储结构,（3）数据之间的结构关系 它包括数据的逻辑结构和 数据的物理结构 （4）是一类普通数据的表示及其相关操作 （5）根据各种不同的数据集合和数据之间的关系研究如何表示、存储、操作这些数据的技术,研究数据结构

10、从三个方面进行： （1）逻辑结构 （2）存储结构 （3）操作（运算） 对数据进行的处理， 定义在数据的逻辑结构上 具体实现于数据的存储结构,引用,引用（reference）作用是为变量起一个别名 例如：int a; int 说明：（1）b是一个引用变量，它的作用与a相同 （2）b与a占用相同的内存空间,假设变量a的地址为1000，值为123,定义了int int ,（5）定义引用变量的作用是使得函数调用时， 实参与形参之间不仅有传值方式，还有传地址方式 引用变量做参数，相当于传地址,void swap(int ,输出： a=4,b=3,比较： void swap1(int x, int y)

11、int t; t=x; x=y; y=t; void swap2(int *x, int *y) int t; t=*x; *x=*y; *y=t; ,void f (int x, int y, int ,抽象数据类型 (ADT: Abstract Data Types),数据类型 int char float struct,描述数据逻辑结构的工具,(1)ADT是指一个数学模型及其在该模型上的一组操作 (2)ADT只考虑数学模型上数据元素之间的逻辑关系， 而忽略其物理结构,(3)ADT是一个逻辑数据类型以及定义在该类型上的一组操作，每个操作由它的输入/出定义，而隐藏其实现细节，如定义一个整数类

12、型及在整数类型上的操作,(4)ADT由三元组构成：（D，S，P） D 数据对象 S 关系 P 操作集,(5)约定格式为： ADT 抽象数据类型名 数据对象： 数据关系： 基本操作： ADT 抽象数据类型名,基本操作的格式： 基本操作名（参数表） 初始条件： 操作结果：,形式参数： 赋值参数-传值 引用参数-传地址,ADT List 数据对象:D=aiaiElemSet,i=1,2,3，,n,n0 数据关系:R=ai-1 ,aiD,i=2,3， ,n 基本操作: ReadFile( 初始条件:表L已经存在. 操作结果:在表L中删除元素a,PrintList(L); 初始条件:表L已经存在. 操作

13、结果:依次输出表L的所有元素 ,1. 学生成绩管理系统 2电话簿管理系统 3学校图书管理系统 4职工工资管理系统,功能:输入、查询、修改、打印,/定义表示学生结构体 struct stu int num; char name10; char class10; int score5; ;,/定义表示联系方式的结构体 struct call char name10; char class10; int telephone; char mobile12; char addr20; ;,/定义表示图书结构体 struct book int num; char name10; char author10

14、; char publish20; struct date day; ;,/定义表示职工结构体 struct employe int num; char name10; float jiben; float jiangjin; float butie; ;,1.3 抽象数据类型的表示与实现,1原则： 通过已有的类型定义或组合成新的类型 用类C语言描述,2C+引用参数,3各种预定义和约定,数据元素的类型为ElemType 数据存储结构用typedef定义,typedef struct int num; char name10; char sex; int age; . ElemType;,用,基

15、本操作的描述 函数类型 函数名（函数参数表） / 算法说明 语句序列 /函数名,int f1(int n, int ,Status f1(int n, int ,1.4 算法和算法分析,一、算法的概念 算法是解决某一个/一类问题的一个有序的有穷序列，该序列确定了解决问题的方法和步骤。,例：用辗转相除法求两个正整数的最大公因子 1输入m和n 2若mn, 则交换m和n 3m除以n，余数为r 4若r=0，则n为最大公因子，输出n，否则执行5 5nm，rn，转3,三、算法设计的要求： 正确性 可读性 健壮性/容错性 有效性,二、算法的特征%,例：用辗转相除法求两个正整数的最大公因子 1输入m和n 2若

16、mn, 则交换m和n 3m除以n，余数为r 4若r=0，则n为最大公因子，输出n，否则执行5 5nm，rn，转3,四、算法的效率,sum=0; for(i=1; i=n; i+) term=1; for(j=1; j=i;j+) term=term*j; sum=sum+term; ,sum=0;term=1; for(i=1; i=n; i+) term=term*i; sum=sum+term; ,决定因素: 1.策略 2.问题的输入规模 3.编译产生的代码质量 4.机器指令执行的速度,1.策略 2.问题的输入规模,1效率：时间、空间,2时间复杂度 算法中最基本、主要的运算执行的次数作为算

17、法执行时间长短的度量称为算法的时间复杂度，它是问题规模的函数，记作T(n) 一般以量级的形式来讨论时间复杂度 一个函数f(n)是g(n) 级的，当且仅当存在一个常数c和一个整数n0 (c0, n00)，对于一切nn0，有 f(n) c g(n) 成立 记作：O(g(n),事先估计 事后估计,事先估计,#define N 10 main( ) int i, j, t, aN; printf(“input 10 number:”); for(i=0; iaj+1) t=aj; aj=aj+1; aj+1=t; printf(“the sorted number:n”); for(i=0; iN;

18、i+) printf(“%3d”,ai); printf(“n”); ,3空间复杂度 S（n）,4效率对算法的影响,O(logn)O(n)O(nlogn)O(n2)O(n3)O(2n)O(n!)O(nn),例：假设CPU每秒处理10 6 个指令，对于输入规模为108的问题，时间代价T(n) = 2n2的算法要运行多长时间？,操作次数为T(n) = T(108) = 2(108)2 = 21016 运行时间为21016/106 = 21010秒 每天有86,400秒，因此需要231,481 天(634年）,例：假设CPU每秒处理106个指令，对于输入规模为108的问题，时间代价为nlog n 的算法要运行多长时间？,操作次数为 T(n) = T(108) = 108 log 108 = 2.66109 运行时间为2.66109/106 = 2.66103秒= 44.33分钟,例：设CPU每秒处理106个指令，则每小时能够解决的最大问题规模 T(n) / 106 3600 对T(n) = 2n2， 即2n2 3600 106 n 42 , 426 对T(n) = n