数据结构与算法数据结构与算法实验.ppt

《数据结构与算法数据结构与算法实验.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法数据结构与算法实验.ppt（71页珍藏版）》请在三一办公上搜索。

1、数据结构与算法数据结构与算法实验,纸上得来终觉浅，绝知此事要躬行读+写+讨论,学习方法,所有作业按时交，注释不少于30%所有作业分为必做（80%）和选做（20%）,上课时间:周一6-7节 周四1-2节上机时间:周一8-9节答疑时间:周一16:30-17:30 408讨论时间:周四 9:40-10:40 508？,放慢速度？时常复习以前讲的？8个小时？只会课上讲的？答疑了吗？,讲但不是全部部分内容需要自己学习希望预习复习自主学习,希望：提前5分钟到教室，不迟到 不吃东西 手机静音 随时提问，积极响应 按时交作业,对老师的希望？,数据结构学什么数据结构的地位和作用怎么学好数据结构,教学内容,特点：

2、用数学方程进行数值运算,称这类问题的数学模型是数学方程,第一章绪论,例1：数学方程（1）用二分法求方程的根（2）用迭代法求a的平方根,例2:图书管理系统,建立一个小型图书管理系统，该系统具有输入、查询、排序、修改、插入、删除、输出等功能。实验要求：（1）从文件中读入图书信息，每本图书至少包括书号、书名、作者、出版社、出版日期、单价等信息；图书数量不少于16本（2）能根据书号或书名或出版社查询所有满足条件的图书（3）系统界面自行设计（4）能够按照书名或出版日期排序（5）能能修改图书除书号外的所有信息（6）能从文件中追加新的图书数据（7）对已经遗失的图书从系统中删除相应的图书信息,涉及：数据录入数

3、据查询数据维护数据排序、输出,需要：建一张表确定表中前后数据的关系实现对表进行操作的方法,例3:扑克牌接龙游戏,洗牌 发牌、出牌、移牌 比较、判断 输赢判断,（1）表示所有扑克牌（2）实现各种游戏动作,特点：两个数据之间有一定顺序 主要操作有：插入、查找、修改、删除 称这类问题的数学模型为线性表(线性结构),学生成绩管理系统,扑克牌接龙游戏,.,.,例4 人机对奕,.,.,.,.,.,井字棋、中国象棋、国际象棋对奕过程中可能出现的棋盘状态称为格局,格局之间的关系由下棋规则确定从一个格局中可以派生出若干个新格局从新格局又可以派生出更新的格局 整个对奕过程可能派生出的所有格局就象一棵倒挂的树树根为

4、对奕开始的格局树叶为可能出现的一种结局对奕的过程就是从树根走到树叶的过程,表示每一种格局表示格局之间的派生关系给出对奕的算法：从所有儿子格局中找出 最有利的格局,需要,例5 文件系统,/(root),bin,lib,user,etc,math,ds,clg,yin,tao,xie,Stack.cpp,Queue.cpp,Tree.cpp,这类问题的数学模型称为树（树型结构、层次结构）树的特点：除根外每个结点有唯一一个双亲(上级，祖先)除叶子结点外，每个结点可以有多于一个儿子树的操作：各种遍历搜索,例6 多叉路口交通灯管制 多叉路口需要设几种颜色的灯才能使车辆互不相撞且车流量最大,需要：表示圆圈

5、（道路）表示边（是否冲突）给出染色方法,四色定理-着色问题,例7 最短路径问题 油田铺设管道，把原油送到加工厂，要求所铺设的管道最短,农夫过河,一个农夫带着只狼、一只羊和棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请求出农夫将所有的东西运过河的方案。,出发地,目的地,人羊狼菜（初始）人羊狼人羊菜人狼菜羊狼菜（不可能）,出发地,目的地,人（不可能）羊狼菜空（结束）,狼菜人菜（不可能）羊菜

6、（不可能）人羊人狼（不可能）,出发地所有状态,特点：任何两个数据之间都可以有关系(单向、双向)操作：遍历、染色、最短路径这种数学模型称为图,用计算机解决一个实际问题的步骤：,问题分析 建立模型 确定算法 设计程序 上机调试 结 果,数据结构是一门研究计算机的操作对象 以及操作对象之间的关系 和对操作对象实施的典型操作 的学科,1.1 什么是数据结构,操作对象关系典型操作,1.2 基本概念和术语,数据：Data 数据是计算机化的信息（对现实世界的事物采用计算机能够识别、存储和处理的形式所进行的描述）数值性数据非数值性数据,数据元素：Data Element 数据的基本单位，如格局、结点 通常作为

7、一个整体进行考虑和处理 数据元素的组成成员称为数据项,数据项：Data Item 数据的最小单位 一个数据元素由多个数据项组成,数据对象：Data Object 具有相同性质的数据元素的集合 如所有书目、所有扑克牌、所有格局、所有道路,数据类型：Data Type,数据结构：Data Structure,（1）相互间存在一种或多种特定关系的数据元素的集合 一种或多种关系称为结构 有4种基本结构：,数据的逻辑结构,数据的逻辑结构,线性结构 线性表（表，栈，队列，串等）非线性结构 树（二叉树，Huffman树，二叉排序树等）图（有向图，无向图等）,图 树 二叉树 线性表,数据的存储结构（物理结构）

8、,逻辑结构到物理存储空间的映射,内存,.,顺序、链式、索引、散列,a1,a2,a3,a4,a5,逻辑结构,物理结构（一）,物理结构（二）,a1,a2,a3,a4,a5,a3,a4,a2,a5,a1,0,struct student/数据类型 int num;char name12;char sex;int age;int score5;int scoresum;s50;/数据对象,数据项,s0、s1、s2、.数据元素数组-数据关系的表示,struct stu/数据类型int num;int score;struct stu*next;*head,*p1;,数据项,*p1、*head、.数据元素

9、链表-数据关系的表示head为首的数据元素构成数据对象,数据的存储结构借助于高级语言中的数据类型来描述,顺序链式索引散列,顺序映象,非顺序映象,（2）数据元素+关系 数据结构是一个二元组：Data_structure=(D,S)D:数据元素的有穷集合 S:数据之间有穷关系的集合,例：DS1=（D，S）D=V1,V2,V3,V4S=,（3）数据之间的结构关系 它包括数据的逻辑结构和 数据的物理结构（4）是一类普通数据的表示及其相关操作（5）根据各种不同的数据集合和数据之间的关系研究如何表示、存储、操作这些数据的技术,研究数据结构从三个方面进行：（1）逻辑结构（2）存储结构（3）操作（运算）对数据

10、进行的处理，定义在数据的逻辑结构上 具体实现于数据的存储结构,引用,引用（reference）作用是为变量起一个别名例如：int a;int 说明：（1）b是一个引用变量，它的作用与a相同（2）b与a占用相同的内存空间,假设变量a的地址为1000，值为123,定义了int&b=a后:,（3）b的作用域与a相同，在其作用域内，不能作为其它变量或其它变量的别名（4）定义一个引用变量的同时必须初始化-说明它是谁的别名,输出：a=10 b=10 a=100,main()int a=10;int,（5）定义引用变量的作用是使得函数调用时，实参与形参之间不仅有传值方式，还有传地址方式 引用变量做参数，相当

11、于传地址,void swap(int,输出：a=4,b=3,比较：void swap1(int x,int y)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),描述数据逻辑结构的工具,(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 stuint 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;char publish20;struct da

14、te 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;,用&x表示引用参数x函数类型为Status时表示函数的返回值为函数的 执行状态,一般为Err

15、or或Ok辅助变量可以不说明以注释的形式表示：算法的功能参数表中各参数的定义和输入/出属性各种变量的作用、入口初值和应满足的条件,预定义的常量和类型：#define TRUE 1#define FALSE0#define OK1#define ERROR0#define INFEASIBLE-1#define OVERFLOW-2typedef int Status;,基本操作的描述函数类型 函数名（函数参数表）/算法说明 语句序列/函数名,int f1(int n,int,Status f1(int n,int,1.4 算法和算法分析,一、算法的概念 算法是解决某一个/一类问题的一个有序的有

16、穷序列，该序列确定了解决问题的方法和步骤。,例：用辗转相除法求两个正整数的最大公因子1输入m和n2若mn,则交换m和n3m除以n，余数为r4若r=0，则n为最大公因子，输出n，否则执行55nm，rn，转3,三、算法设计的要求：正确性 可读性 健壮性/容错性 有效性,二、算法的特征%,例：用辗转相除法求两个正整数的最大公因子1输入m和n2若mn,则交换m和n3m除以n，余数为r4若r=0，则n为最大公因子，输出n，否则执行55nm，rn，转3,四、算法的效率,sum=0;for(i=1;i=n;i+)term=1;for(j=1;j=i;j+)term=term*j;sum=sum+term;,

17、sum=0;term=1;for(i=1;i=n;i+)term=term*i;sum=sum+term;,决定因素:1.策略2.问题的输入规模3.编译产生的代码质量4.机器指令执行的速度,1.策略2.问题的输入规模,1效率：时间、空间,2时间复杂度(渐进分析)算法中最基本、主要的运算执行的次数作为算法执行时间长短的度量称为算法的时间复杂度，它是问题规模的函数，记作T(n)一般以量级的形式来讨论时间复杂度,事先估计事后估计,事先估计,函数 f，g 定义域为自然数，值域非负实数集 定义：如果存在正数 c 和n0(c0,n00)，使得对任意的nn0，都有f(n)c g(n)，称f(n)在集合O(g

18、(n)中，简称 f(n)是O(g(n)的，或 f(n)=O(g(n)大 O 表示法：表达函数增长率上限,0,大O表示法,?大表示法?大表示法,最坏 平均最好,时间,规模n,顺序查找：从一个规模为 n 的一维数组中找出一个给定的 K 值,最好情况：比较一次最坏情况：比较n次平均情况：,#define N 10main()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;i+)printf(%3d,ai);printf(n);,

19、3空间复杂度 S（n）,大O表示法的运算法则,加法规则:f1(n)+f2(n)=(max(f1(n),f2(n),乘法规则:f1(n)f2(n)=(f1(n)f2(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秒

20、，因此需要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)=nlog n 即nlogn 3600 106 n 133,000,000对T(n)=2n 即2n3600 106 n41.36,常用的算

21、法设计方法穷举法(顺序查找，百钱买百鸡)贪心法(Huffman树，Dijkstra 算法，Prim 算法递归法,分治法(折半检索，快速排序，归并排序)回溯法动态规划法(最短路 Floyd 算法)分枝界限法并行算法分布式算法,15数据结构在计算机科学中的地位,Web信息处理队列、图、字符、散列、排序、检索,人工智能表、集合、有向图、搜索树,图形图像队列、栈、图、树、索引,数据库原理线性表、排序、B+树,操作系统队列、表、排序、树,编译原理字符串、栈、散列表、语法树,数据结构,数据结构实验,算法设计与分析,高级语言程序设计,程序设计实践,离散数学,课程目标,学会如何有效地组织信息，以便支持高效的数据处理掌握常用的基本数据结构及其应用学会合理地组织数据，有效地表示数据，有效地处理数据基本掌握算法分析技术提高算法设计能力提高使用计算机解决问题的能力,从问题求解出发在基础理论、抽象和设计的三个层次组织知识体系从逻辑、存储、运算的角度学习数据结构与算法，培养学生独立地实现常用基本数据结构的抽象数据类型，注重实践能力和工程能力的培养为将来从事计算机学科的学习、开发和研究，或其他学科应用计算机进行问题求解打下坚实的基础,学习内容,三种典型的数据结构及典型操作两类典型算法算法设计与分析基本知识,