1、数据结构与算法数据结构与算法数据结构与算法实验数据结构与算法实验2014.9-2015.1纸上得来终觉浅，绝知此事要躬行纸上得来终觉浅，绝知此事要躬行读读+写写+讨论讨论所有作业按时交，注释不少于所有作业按时交，注释不少于30%30%所有作业分为必做（所有作业分为必做（80%80%）和选做（）和选做（20%20%）上课时间上课时间:周一周一6-7节节 周四周四1-2节节上机时间上机时间:周一周一8-9节节答疑时间答疑时间:周一周一16:30-17:30 408讨论时间讨论时间:周四周四 9:40-10:40 508？放慢速度？时常复习以前讲的？8个小时？只会课上讲的？答疑了吗？讲但不是全部部分
2、内容需要自己学习希望预习复习自主学习希望：提前5分钟到教室，不迟到 不吃东西 手机静音 随时提问，积极响应 按时交作业对老师的希望？数据结构学什么数据结构的地位和作用怎么学好数据结构教学内容)(211nnnxaxx特点：用数学方程进行数值运算用数学方程进行数值运算 称这类问题的数学模型数学模型是数学方程数学方程第一章绪论例1：数学方程（1）用二分法求方程的根（2）用迭代法求a的平方根例例2:图书管理系统图书管理系统建立一个小型图书管理系统，该系统具有输入、建立一个小型图书管理系统，该系统具有输入、查询、排序、修查询、排序、修改、插入、删除改、插入、删除、输出等功能。、输出等功能。实验要求：实验
3、要求：（1）从文件中读入图书信息，每本图书至少包括书号、书名、作者、出版社、出版日期、单价等信息；图书数量不少于16本（2）能根据书号或书名或出版社查询所有满足条件的图书（3）系统界面自行设计（4）能够按照书名或出版日期排序（5）能能修改图书除书号外的所有信息（6）能从文件中追加新的图书数据（7）对已经遗失的图书从系统中删除相应的图书信息涉及：涉及：l数据录入数据录入l数据查询数据查询l数据维护数据维护l数据排序、输出数据排序、输出需要：需要：建一张表建一张表确定表中前后数据的关系确定表中前后数据的关系实现对表进行操作的方法实现对表进行操作的方法书号书号书名书名作者作者出版社出版社出版日期出版
4、日期数量数量单价单价例例3:扑克牌接龙游戏扑克牌接龙游戏 洗牌洗牌 发牌、出牌、移牌发牌、出牌、移牌 比较、判断比较、判断 输赢判断输赢判断（1）表示所有扑克牌）表示所有扑克牌（2）实现各种游戏动作）实现各种游戏动作 特点：两个数据之间有一定顺序特点：两个数据之间有一定顺序 主要操作有：插入、查找、修改、删除主要操作有：插入、查找、修改、删除 称这类问题的数学模型为称这类问题的数学模型为线性表线性表(线性结构线性结构)学生成绩管理系统学生成绩管理系统扑克牌接龙游戏扑克牌接龙游戏.例例4 人机对奕人机对奕.井字棋、中国象棋、国际象棋井字棋、中国象棋、国际象棋对奕过程中可能出现的棋盘状态称为格局对
5、奕过程中可能出现的棋盘状态称为格局格局之间的关系由下棋规则确定格局之间的关系由下棋规则确定从一个格局中可以派生出若干个新格局从一个格局中可以派生出若干个新格局从新格局又可以派生出更新的格局从新格局又可以派生出更新的格局 整个对奕过程可能派生出的所有格局就象一棵倒挂的树整个对奕过程可能派生出的所有格局就象一棵倒挂的树树根为对奕开始的格局树根为对奕开始的格局树叶为可能出现的一种结局树叶为可能出现的一种结局对奕的过程就是从树根走到树叶的过程对奕的过程就是从树根走到树叶的过程表示每一种格局表示每一种格局表示格局之间的派生关系表示格局之间的派生关系给出对奕的算法：从所有儿子格局中找出给出对奕的算法：从所
6、有儿子格局中找出 最有利的格局最有利的格局需要需要/(root)binlibuseretcmathdsclgyintaoxieStack.cppQueue.cppTree.cpp这类问题的数学模型称为这类问题的数学模型称为树树（树型结构、层次结构）树的特点：树的特点：除根外每个结点有唯一一个双亲除根外每个结点有唯一一个双亲(上级，祖先)除叶子结点外，每个结点可以有多于一个儿子除叶子结点外，每个结点可以有多于一个儿子树的操作：各种遍历搜索树的操作：各种遍历搜索例例6 多叉路口交通灯管制多叉路口交通灯管制 多叉路口需要设几种颜色的灯才能使车辆互不相撞多叉路口需要设几种颜色的灯才能使车辆互不相撞且车
7、流量最大且车流量最大需要：表示圆圈（道路）需要：表示圆圈（道路）表示边（是否冲突）表示边（是否冲突）给出染色方法给出染色方法四色定理-着色问题例例7 最短路径问题最短路径问题 油田铺设管道，把原油送到加工厂，要求所铺设油田铺设管道，把原油送到加工厂，要求所铺设的管道最短的管道最短农夫过河农夫过河 一个农夫带着只狼、一只羊和棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请求出农夫将所有的东
8、西运过河的方案。出发地目的地人羊狼菜人羊狼菜（初始）（初始）人羊狼人羊狼人羊菜人羊菜人狼菜人狼菜羊狼菜（不可能）出发地目的地人（不可能）羊羊狼狼菜菜空（结束）空（结束）狼菜狼菜人菜（不可能）羊菜（不可能）人羊人羊人狼（不可能）出发地所有状态出发地所有状态特点：任何两个数据之间都可以有关系特点：任何两个数据之间都可以有关系(单向、双向单向、双向)操作：遍历、染色、最短路径操作：遍历、染色、最短路径这种数学模型称为这种数学模型称为图图l用计算机解决一个实际问题的步骤：用计算机解决一个实际问题的步骤：典型的数学模型：表、树、图典型的数学模型：表、树、图各种模型的典型算法各种模型的典型算法典型的查找、
9、排序算法典型的查找、排序算法简单的算法设计方法简单的算法设计方法l数据结构数据结构是一门研究是一门研究计算机的计算机的操作对象操作对象 以及以及操作操作对象之间的对象之间的关系关系 和和对对操作操作对象实施的典型对象实施的典型操作操作 的学科的学科1.1 什么是数据结构什么是数据结构操作对象操作对象关系关系典型操作典型操作1.2 基本概念和术语基本概念和术语数据数据：DataData 数据是计算机化的信息（对现实世界的事物采用计算机能够识别、存储和处理的形式所进行的描述）数值性数据数值性数据 非数值性数据非数值性数据 数据元素数据元素：Data Element 数据的基本单位，如格局、结点数据
10、的基本单位，如格局、结点 通常作为一个整体进行考虑和处理通常作为一个整体进行考虑和处理 数据元素的组成成员称为数据项数据元素的组成成员称为数据项 ：Data Structure数学数学模型模型表表 树树 图图 实例实例图书图书管理管理扑克牌扑克牌游戏游戏人机人机对弈对弈目录目录管理管理信号灯信号灯设置设置管道管道铺设铺设数据数据元素元素图书图书牌牌格局格局目录目录道路道路连接点连接点数据数据项项书名、书名、书号、书号、作者等作者等花色、花色、点数、点数、正反正反行、行、列、列、值值名字、名字、物理物理位置位置起点、起点、终点、终点、颜色颜色地理地理位置位置数据数据对象对象所有所有图书图书54张
11、牌张牌所有所有格局格局所有所有目录目录所有所有道路道路所有连所有连接点接点关系关系顺序顺序先后先后派生派生从属从属冲突冲突架设架设 线性结构 线性表（表，栈，队列，串等）非线性结构 树（二叉树，HuffmanHuffman树树，二叉排序树二叉排序树等）等）图（有向图，无向图等）图图 树树 二叉树二叉树 线性表线性表逻辑结构到物理存储空间的映射逻辑结构到物理存储空间的映射 内存.顺序、链式、索引、散列顺序、链式、索引、散列 a1a2a3a4a5逻辑结构逻辑结构物理结构（一）物理结构（一）物理结构（二）物理结构（二）a1a2a3a4a5a3a4a2a5a10struct student /数据类型
12、 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、.数据元素数据元素链表链表-数据关系的表示数据关系的表示head为首的数据元素构成数据对象为首的数据元素构成数据对象顺序顺序链式链式索引索引散列散列 例：例：DS1=（D，S）D=V1,V2,V3,V4S=,（3）数据之
13、间的结构关系）数据之间的结构关系 它包括数据的逻辑结构和它包括数据的逻辑结构和 数据的物理结构数据的物理结构（4）是一类普通数据的表示及其相关操作）是一类普通数据的表示及其相关操作（5）根据各种不同的数据集合和数据之间的关系研究）根据各种不同的数据集合和数据之间的关系研究如何表示、存储、操作这些数据的技术如何表示、存储、操作这些数据的技术 研究数据结构从三个方面进行：研究数据结构从三个方面进行：（1）逻辑结构逻辑结构（2）存储结构存储结构（3）操作操作（运算）（运算）对数据进行的处理，对数据进行的处理，定义在数据的逻辑结构上定义在数据的逻辑结构上 具体实现于数据的存储结构具体实现于数据的存储结
14、构引用引用引用（引用（referencereference）作用是为变量起一个别名）作用是为变量起一个别名例如：例如：int a;int&b=a;int a;int&b=a;说明：（说明：（1 1）b b是一个引用变量，它的作用与是一个引用变量，它的作用与a a相同相同 （2 2）b b与与a a占用相同的内存空间占用相同的内存空间1231000a假设变量假设变量a的地址为的地址为1000，值为，值为123定义了定义了int&b=a后后:1231000ab（3 3）b b的作用域与的作用域与a a相同，在其作用域内，不能相同，在其作用域内，不能作为其它变量或其它变量的别名作为其它变量或其它变量
15、的别名 （4 4）定义一个引用变量的同时必须初始化）定义一个引用变量的同时必须初始化-说明它是谁的别名说明它是谁的别名输出：输出：a=10 b=10 a=100main()int a=10;int&b=a；printf(a=%dn,a);printf(b=%dn,b);b=100;printf(a=%dn,a);（5 5）定义引用变量的作用是使得函数调用时，）定义引用变量的作用是使得函数调用时，实参与形参之间不仅有传值方式，还有传地址方式实参与形参之间不仅有传值方式，还有传地址方式 引用变量做参数，相当于传地址引用变量做参数，相当于传地址void swap(int&x,int&y)int t;
16、t=x;x=y;y=t;void main()int a=3,b=4;swap(a,b);printf(a=%d,b=%dn,a,b);输出：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&z，int&t)z=(x-y)*(x+2*y);t=x*x+y*y;int main()int a=3,b=4,c,d;f(a,b,c,d);printf(a=%d,c=%d,d=%d n,a,c,d);ADT L
17、istADT List 数据对象数据对象:D=a:D=ai iaai iElemSet,i=1,2,3ElemSet,i=1,2,3，,n,n0,n,n0 数据关系数据关系:R=a:R=aai-1 i-1,a,ai iD,i=2,3D,i=2,3，,n,n 基本操作基本操作:ReadFile(&L);ReadFile(&L);操作结果操作结果:从键盘上读入文件名从键盘上读入文件名,从文件中读入数据到表从文件中读入数据到表L L中中.SearchList(L,a);SearchList(L,a);初始条件初始条件:表表L L已经存在已经存在.操作结果操作结果:在表在表L L查找元素查找元素a,a
18、,找到返回该元素指针找到返回该元素指针 找不到返回找不到返回NULL.NULL.InsertList(&L,a);初始条件初始条件:表表L已经存在已经存在.操作结果操作结果:在表在表L插入元素插入元素aDeleteList(&L,a);初始条件初始条件:表表L已经存在已经存在.操作结果操作结果:在表在表L中删除元素中删除元素aPrintList(L);初始条件初始条件:表表L已经存在已经存在.操作结果操作结果:依次输出表依次输出表L的所有元素的所有元素1.学生成绩管理系统学生成绩管理系统2电话簿管理系统电话簿管理系统3学校图书管理系统学校图书管理系统4职工工资管理系统职工工资管理系统功能功能:
19、输入、查询、修改、打印输入、查询、修改、打印/定义表示学生结构体定义表示学生结构体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 date day;/定义表示职工
20、结构体定义表示职工结构体struct employe int num;char name10;float jiben;float jiangjin;float butie;3各种预定义和约定各种预定义和约定数据元素的类型为数据元素的类型为ElemType数据存储结构用数据存储结构用typedef定义定义typedef struct int num;char name10;char sex;int age;.ElemType;typedef struct char 起点起点30;char 终点终点20;int 颜色号颜色号;.ElemType;用用&x表示引用参数表示引用参数x函数类型为函数类型
21、为Status时表示函数的返回值为函数的时表示函数的返回值为函数的 执行状态执行状态,一般为一般为Error或或Ok辅助变量可以不说明辅助变量可以不说明以注释的形式表示：以注释的形式表示：算法的功能算法的功能参数表中各参数的定义和输入参数表中各参数的定义和输入/出属性出属性各种变量的作用、入口初值和应满足的条件各种变量的作用、入口初值和应满足的条件预定义的常量和类型：#define TRUE 1#define FALSE0#define OK1#define ERROR 0#define INFEASIBLE-1#define OVERFLOW-2typedef int Status;int
22、f1(int n,int&sum)int score;int i;sum=0;for(i=0;in;i+)scanf(%d,&score);if(score0)return 0;sum+=score;return 1;Status f1(int n,int&sum)int score;int i;sum=0;for(i=0;in;i+)scanf(%d,&score);if(score0)return ERROR;sum+=score;return OK;一、算法的概念例：用辗转相除法求两个正整数的最大公因子例：用辗转相除法求两个正整数的最大公因子1输入输入m和和n2若若mn,则交换则交换m和
23、和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
24、;sum=sum+term;sum=0;term=1;for(i=1;i0,n(c0,n0 0 0)0)，使得对，使得对任意的任意的nnnn0 0 ，都有都有f(n)f(n)c c g(n)g(n)，称称f(n)f(n)在集合在集合O(g(n)O(g(n)中，简称中，简称 f(n)f(n)是是O(g(n)O(g(n)的，的，或或 f(n)=O(g(n)f(n)=O(g(n)大大 O O 表示法：表达函数增长率上限表示法：表达函数增长率上限0大大O O表示法表示法?大大表示法表示法?大大表示法表示法 最坏 平均最好时间规模n顺序查找：从一个规模为 n 的一维数组中找出一个给定的 K 值 最好情况
25、：比较一次最坏情况：比较n次平均情况：2111ninni#define N 10main()int i,j,t,aN;printf(input 10 number:);for(i=0;iN;i+)scanf(%d,&ai);for(i=1;iN;i+)for(j=0;jaj+1)t=aj;aj=aj+1;aj+1=t;printf(the sorted number:n);for(i=0;iN;i+)printf(%3d,ai);printf(n);3空间复杂度 S（n）大大O O表示法的运算法则表示法的运算法则 加法规则加法规则:f1(n)+f2(n)=:f1(n)+f2(n)=(max(f
26、1(n),f2(n)(max(f1(n),f2(n)乘法规则乘法规则:f1(n)f2(n)=: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秒，因此需
27、要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
28、n41.36常用的算法设计方法常用的算法设计方法 穷举法(顺序查找，百钱买百鸡)贪心法(Huffman树，Dijkstra 算法，Prim 算法 递归法,分治法(折半检索，快速排序，归并排序)回溯法 动态规划法(最短路 Floyd 算法)分枝界限法 并行算法 分布式算法15数据结构在计算机科学中的地位数据结构在计算机科学中的地位WebWeb信息处理信息处理队列、图、字符、队列、图、字符、散列、排序、检索散列、排序、检索人工智能人工智能表、集合、有表、集合、有向图、搜索树向图、搜索树图形图像图形图像队列、栈、图队列、栈、图、树、索引、树、索引数据库原理数据库原理线性表、排序线性表、排序、B+B+
29、树树操作系统操作系统队列、表、队列、表、排序、树排序、树编译原理编译原理字符串、栈、散字符串、栈、散列表、语法树列表、语法树数据结构数据结构数据结构实验数据结构实验算法设计与分析算法设计与分析高级语言程序设计高级语言程序设计程序设计实践程序设计实践离散数学离散数学 学会如何有效地组织信息，以便支持高效的数据学会如何有效地组织信息，以便支持高效的数据处理处理 掌握常用的基本数据结构及其应用掌握常用的基本数据结构及其应用u学会合理地组织数据，有效地表示数据，有学会合理地组织数据，有效地表示数据，有效地处理数据效地处理数据u基本掌握算法分析技术基本掌握算法分析技术u提高算法设计能力提高算法设计能力u提高使用计算机解决问题的能力提高使用计算机解决问题的能力从问题求解出发从问题求解出发在在的三个层次组织知识体系的三个层次组织知识体系从从的角度学习数据结构与算法，的角度学习数据结构与算法，培养学生独立地实现常用基本数据结构的抽象数据类培养学生独立地实现常用基本数据结构的抽象数据类型，注重实践能力和工程能力的培养型，注重实践能力和工程能力的培养为将来从事计算机学科的学习、开发和研究，或其他为将来从事计算机学科的学习、开发和研究，或其他学科应用计算机进行问题求解打下坚实的基础学科应用计算机进行问题求解打下坚实的基础
