数据结构和算法数据结构和算法实验纸上得来终觉浅，绝知此事要躬行纸上得来终觉浅，绝知此事要躬行读读+ +写写+ +讨论讨论学习方法学习方法所有作业按时交，注释不少于所有作业按时交，注释不少于30%30%所有作业分为必做（所有作业分为必做（80%80%）和选做（）和选做（20%20%）:6-7节节周四周四1-2节节:8-9节节答疑时间答疑时间:16:30-17:30408讨论时间讨论时间:9:40-10:40508？放慢速度？ 时常复习以前讲的？8个小时？只会课上讲的？答疑了吗？讲但不是全部部分内容需要自己学习希望预习复习自主学习希望： 提前5分钟到教室，不迟到 不吃东西 手机静音 随时提问，积极响应 按时交作业对老师的希望？数据结构学什么数据结构的地位和作用怎么学好数据结构教学内容特点：用数学方程进行数值运算用数学方程进行数值运算 称这类问题的数学模型数学模型是数学方程数学方程第一章绪论例1：数学方程（1）用二分法求方程的根（2）用迭代法求a的平方根例例2:图书管理系统图书管理系统建立一个小型图书管理系统，该系统具有输入、查询、排序、修建立一个小型图书管理系统，该系统具有输入、查询、排序、修改、插入、删除、输出等功能。改、插入、删除、输出等功能。实验要求：实验要求：（1）从文件中读入图书信息，每本图书至少包括书号、书名、作者、出版社、出版日期、单价等信息；图书数量不少于16本（2）能根据书号或书名或出版社查询所有满足条件的图书（3）系统界面自行设计（4）能够按照书名或出版日期排序（5）能能修改图书除书号外的所有信息（6）能从文件中追加新的图书数据（7）对已经遗失的图书从系统中删除相应的图书信息涉及：涉及：l数据录入数据录入l数据查询数据查询l数据维护数据维护l数据排序、输出数据排序、输出需要：需要：建一张表建一张表确定表中前后数据的关系确定表中前后数据的关系实现对表进行操作的方法实现对表进行操作的方法书号书号书名书名作者作者出版社出版社出版日期出版日期数量数量单价单价例例3:扑克牌接龙游戏扑克牌接龙游戏洗牌洗牌发牌、出牌、移牌发牌、出牌、移牌比较、判断比较、判断输赢判断输赢判断（1）表示所有扑克牌）表示所有扑克牌（2）实现各种游戏动作）实现各种游戏动作特点：两个数据之间有一定顺序特点：两个数据之间有一定顺序主要操作有：插入、查找、修改、删除主要操作有：插入、查找、修改、删除称这类问题的数学模型为称这类问题的数学模型为线性表线性表(线性结构线性结构)学生成绩管理系统学生成绩管理系统扑克牌接龙游戏扑克牌接龙游戏.例例4 人机对奕人机对奕.井字棋、中国象棋、国际象棋井字棋、中国象棋、国际象棋对奕过程中可能出现的棋盘状态称为格局对奕过程中可能出现的棋盘状态称为格局格局之间的关系由下棋规则确定格局之间的关系由下棋规则确定从一个格局中可以派生出若干个新格局从一个格局中可以派生出若干个新格局从新格局又可以派生出更新的格局从新格局又可以派生出更新的格局整个对奕过程可能派生出的所有格局就象一棵倒挂的树整个对奕过程可能派生出的所有格局就象一棵倒挂的树树根为对奕开始的格局树根为对奕开始的格局树叶为可能出现的一种结局树叶为可能出现的一种结局对奕的过程就是从树根走到树叶的过程对奕的过程就是从树根走到树叶的过程表示每一种格局表示每一种格局表示格局之间的派生关系表示格局之间的派生关系给出对奕的算法：从所有儿子格局中找出给出对奕的算法：从所有儿子格局中找出最有利的格局最有利的格局需要需要例5 文件系统/(root)binlibuseretcmathdsclgyintaoxie这类问题的数学模型称为这类问题的数学模型称为树树（树型结构、层次结构）树的特点：树的特点：除根外每个结点有唯一一个双亲除根外每个结点有唯一一个双亲(上级，祖先)除叶子结点外，每个结点可以有多于一个儿子除叶子结点外，每个结点可以有多于一个儿子树的操作：各种遍历搜索树的操作：各种遍历搜索例例6多叉路口交通灯管制多叉路口交通灯管制多叉路口需要设几种颜色的灯才能使车辆互不相撞多叉路口需要设几种颜色的灯才能使车辆互不相撞且车流量最大且车流量最大需要：表示圆圈（道路）需要：表示圆圈（道路）表示边（是否冲突）表示边（是否冲突）给出染色方法给出染色方法四色定理-着色问题例例7最短路径问题最短路径问题油田铺设管道，把原油送到加工厂，要求所铺设的油田铺设管道，把原油送到加工厂，要求所铺设的管道最短管道最短农夫过河农夫过河 一个农夫带着只狼、一只羊和棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请求出农夫将所有的东西运过河的方案。出发地目的地人羊狼菜人羊狼菜（初始）（初始）人羊狼人羊狼人羊菜人羊菜人狼菜人狼菜羊狼菜（不可能）出发地目的地人（不可能）羊羊狼狼菜菜空（结束）空（结束）狼菜狼菜人菜（不可能）羊菜（不可能）人羊人羊人狼（不可能）出发地所有状态出发地所有状态特点：任何两个数据之间都可以有关系特点：任何两个数据之间都可以有关系(单向、双向单向、双向)操作：遍历、染色、最短路径操作：遍历、染色、最短路径这种数学模型称为这种数学模型称为图图l用计算机解决一个实际问题的步骤：用计算机解决一个实际问题的步骤：问题分析问题分析 建立模型建立模型 确定算法确定算法 设计程序设计程序 上机调试上机调试 结结果果典型的数学模型：表、树、图典型的数学模型：表、树、图各种模型的典型算法各种模型的典型算法典型的查找、排序算法典型的查找、排序算法简单的算法设计方法简单的算法设计方法l数据结构数据结构是一门研究是一门研究计算机的计算机的操作对象操作对象以及以及操作操作对象之间的对象之间的关系关系和和对对操作操作对象实施的典型对象实施的典型操作操作的学科的学科1.1什么是数据结构什么是数据结构操作对象操作对象关系关系典型操作典型操作1.2基本概念和术语基本概念和术语数据数据：DataData 数据是计算机化的信息（对现实世界的事物采用计算机能够识别、存储和处理的形式所进行的描述） 数值性数据数值性数据 非数值性数据非数值性数据数据元素数据元素：DataElement数据的基本单位，如格局、结点数据的基本单位，如格局、结点通常作为一个整体进行考虑和处理通常作为一个整体进行考虑和处理数据元素的组成成员称为数据项数据元素的组成成员称为数据项数据项数据项：Data ItemData Item 数据的最小单位数据的最小单位数据的最小单位数据的最小单位一个数据元素由多个数据项组成一个数据元素由多个数据项组成一个数据元素由多个数据项组成一个数据元素由多个数据项组成数据对象：Data Object 具有相同性质的数据元素的集合具有相同性质的数据元素的集合具有相同性质的数据元素的集合具有相同性质的数据元素的集合如所有书目、所有扑克牌、所有格局、所有道路如所有书目、所有扑克牌、所有格局、所有道路如所有书目、所有扑克牌、所有格局、所有道路如所有书目、所有扑克牌、所有格局、所有道路 数据类型：Data Type数据结构数据结构：Data Structure（1 1）相互间存在一种或多种特定关系的数据元素的集合）相互间存在一种或多种特定关系的数据元素的集合）相互间存在一种或多种特定关系的数据元素的集合）相互间存在一种或多种特定关系的数据元素的集合一种或多种关系称为结构一种或多种关系称为结构一种或多种关系称为结构一种或多种关系称为结构有有有有4 4种基本结构：种基本结构：种基本结构：种基本结构：数据的逻辑结构数据的逻辑结构数学数学模型模型表表树树图图实例实例图书图书管理管理扑克牌扑克牌游戏游戏人机人机对弈对弈目录目录管理管理信号灯信号灯设置设置管道管道铺设铺设数据数据元素元素图书图书牌牌格局格局目录目录道路道路连接点连接点数据数据项项书名、书名、书号、书号、作者等作者等花色、花色、点数、点数、正反正反行、行、列、列、值值名字、名字、物理物理位置位置起点、起点、终点、终点、颜色颜色地理地理位置位置数据数据对象对象所有所有图书图书54张牌张牌所有所有格局格局所有所有目录目录所有所有道路道路所有连所有连接点接点关系关系顺序顺序先后先后派生派生从属从属冲突冲突架设架设数据的逻辑结构数据的逻辑结构线性结构 线性表（表，栈，队列，串等） 非线性结构 树（二叉树，HuffmanHuffman树，树， 二叉排序树等）二叉排序树等） 图（有向图，无向图等） 图图 树树 二叉树二叉树 线性表线性表 数据的存储结构（物理结构）数据的存储结构（物理结构）逻辑结构到物理存储空间的映射逻辑结构到物理存储空间的映射 内存.顺序、链式、索引、散列顺序、链式、索引、散列a1a2a3a4a5逻辑结构逻辑结构物理结构（一）物理结构（一）物理结构（二）物理结构（二）a1a2a3a4a5a3a4a2a5a10struct student /数据类型 int num; char name12; char sex; int age; int score5; int scoresum;s50; /数据对象数数据据项项s0、s1、s2、.数据元素数据元素数组数组-数据关系的表示数据关系的表示structstu/数据类型intnum;intscore;structstu*next;*head,*p1;数数据据项项*p1、*head、.数据元素数据元素链表链表-数据关系的表示数据关系的表示head为首的数据元素构成数据对象为首的数据元素构成数据对象数据的存储结构借助于高级语言中的数据类型来描述数据的存储结构借助于高级语言中的数据类型来描述数据的存储结构借助于高级语言中的数据类型来描述数据的存储结构借助于高级语言中的数据类型来描述顺序顺序链式链式索引索引散列散列顺序映象顺序映象顺序映象顺序映象非顺序映象非顺序映象非顺序映象非顺序映象（2 2）数据元素）数据元素）数据元素）数据元素+ +关系关系关系关系数据结构是一个二元组：数据结构是一个二元组：数据结构是一个二元组：数据结构是一个二元组：Data_structure=(D,S)Data_structure=(D,S)D:D:数据元素的有穷集合数据元素的有穷集合数据元素的有穷集合数据元素的有穷集合S:S:数据之间有穷关系的集合数据之间有穷关系的集合数据之间有穷关系的集合数据之间有穷关系的集合例：例：DS1=（D，S）D=V1,V2,V3,V4S=,（3）数据之间的结构关系）数据之间的结构关系它包括数据的逻辑结构和它包括数据的逻辑结构和数据的物理结构数据的物理结构（4）是一类普通数据的表示及其相关操作）是一类普通数据的表示及其相关操作（5）根据各种不同的数据集合和数据之间的关系研究）根据各种不同的数据集合和数据之间的关系研究如何表示、存储、操作这些数据的技术如何表示、存储、操作这些数据的技术研究数据结构从三个方面进行：研究数据结构从三个方面进行：（1）逻辑结构）逻辑结构（2）存储结构）存储结构（3）操作（运算）操作（运算）对数据进行的处理，对数据进行的处理，定义在数据的逻辑结构上定义在数据的逻辑结构上具体实现于数据的存储结构具体实现于数据的存储结构引用引用引用（引用（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相同，在其作用域内，不能相同，在其作用域内，不能作为其它变量或其它变量的别名作为其它变量或其它变量的别名 （4 4）定义一个引用变量的同时必须初始化）定义一个引用变量的同时必须初始化-说明它是谁的别名说明它是谁的别名输出：输出：a=10b=10a=100main()inta=10;int&b=a；printf(a=%dn,a);printf(b=%dn,b);b=100;printf(a=%dn,a);（5 5）定义引用变量的作用是使得函数调用时，）定义引用变量的作用是使得函数调用时， 实参与形参之间不仅有传值方式，还有传地址方式实参与形参之间不仅有传值方式，还有传地址方式 引用变量做参数，相当于传地址引用变量做参数，相当于传地址voidswap(int&x,int&y)intt;t=x;x=y;y=t;voidmain()inta=3,b=4;swap(a,b);printf(a=%d,b=%dn,a,b);输出：a=4,b=3比较：比较：voidswap1(intx,inty)intt;t=x;x=y;y=t;voidswap2(int*x,int*y)intt;t=*x;*x=*y;*y=t;voidf(intx,inty,int&z，int&t)z=(x-y)*(x+2*y);t=x*x+y*y;intmain()inta=3,b=4,c,d;f(a,b,c,d);printf(a=%d,c=%d,d=%dn,a,c,d);抽象数据类型 (ADT: Abstract Data Types) 描述数据逻辑结构的工具描述数据逻辑结构的工具(1)ADT(1)ADT是指一个数学模型及其在该模型上的一组操作是指一个数学模型及其在该模型上的一组操作是指一个数学模型及其在该模型上的一组操作是指一个数学模型及其在该模型上的一组操作(2)ADT(2)ADT只考虑数学模型上数据元素之间的逻辑关系，只考虑数学模型上数据元素之间的逻辑关系，只考虑数学模型上数据元素之间的逻辑关系，只考虑数学模型上数据元素之间的逻辑关系，而忽略其物理结构而忽略其物理结构而忽略其物理结构而忽略其物理结构(3)ADT(3)ADT是一个逻辑数据类型以及定义在该类型上的一是一个逻辑数据类型以及定义在该类型上的一是一个逻辑数据类型以及定义在该类型上的一是一个逻辑数据类型以及定义在该类型上的一组操作，每个操作由它的输入组操作，每个操作由它的输入组操作，每个操作由它的输入组操作，每个操作由它的输入/ /出定义，而隐藏其实现出定义，而隐藏其实现出定义，而隐藏其实现出定义，而隐藏其实现细节和物理结构，如定义一个整数类型及在整数类型细节和物理结构，如定义一个整数类型及在整数类型细节和物理结构，如定义一个整数类型及在整数类型细节和物理结构，如定义一个整数类型及在整数类型上的操作上的操作上的操作上的操作(4)ADT由三元组构成：（由三元组构成：（D，S，P）D数据对象数据对象S关系关系P操作集操作集(5)约定格式为：约定格式为：ADT抽象数据类型名抽象数据类型名数据对象：数据对象：数据关系：数据关系：基本操作：基本操作：ADT抽象数据类型名抽象数据类型名基本操作的格式：基本操作的格式：基本操作名（参数表）基本操作名（参数表）初始条件：初始条件：操作结果：操作结果：形式参数：形式参数：赋值参数赋值参数-传值传值引用参数引用参数-传地址传地址ADT ListADT 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,找到返回该元素指针找到返回该元素指针 找不到返回找不到返回NULL.NULL.InsertList(&L,a);初始条件初始条件:表表L已经存在已经存在.操作结果操作结果:在表在表L插入元素插入元素aDeleteList(&L,a);初始条件初始条件:表表L已经存在已经存在.操作结果操作结果:在表在表L中删除元素中删除元素aPrintList(L);初始条件初始条件:表表L已经存在已经存在.操作结果操作结果:依次输出表依次输出表L的的所有元素所有元素1.学生成绩管理系统学生成绩管理系统2簿管理系统簿管理系统3学校图书管理系统学校图书管理系统4职工工资管理系统职工工资管理系统功能功能:输入、查询、修改、打印输入、查询、修改、打印/定义表示学生结构体定义表示学生结构体structstuintnum;charname10;charclass10;intscore5;/定义表示联系方式的结构体定义表示联系方式的结构体structcallcharname10;charclass10;inttelephone;charmobile12;charaddr20;/定义表示图书结构体定义表示图书结构体structbookintnum;charname10;charauthor10;charpublish20;structdateday;/定义表示职工结构体定义表示职工结构体structemployeintnum;charname10;floatjiben;floatjiangjin;floatbutie;1.3抽象数据类型的表示与实现抽象数据类型的表示与实现1原则：原则：通过已有的类型定义或组合成新的类型通过已有的类型定义或组合成新的类型用类用类C语言描述语言描述2C+引用参数引用参数3各种预定义和约定各种预定义和约定数据元素的类型为数据元素的类型为ElemType数据存储结构用数据存储结构用typedef定义定义typedefstructintnum;charname10;charsex;intage;.ElemType;typedefstructchar起点起点30;char终点终点20;int颜色号颜色号;.ElemType;用用&x表示引用参数表示引用参数x函数类型为函数类型为Status时表示函数的返回值为函数的时表示函数的返回值为函数的执行状态执行状态,一般为一般为Error或或Ok辅助变量可以不说明辅助变量可以不说明以注释的形式表示：以注释的形式表示：算法的功能算法的功能参数表中各参数的定义和输入参数表中各参数的定义和输入/出属性出属性各种变量的作用、入口初值和应满足的条件各种变量的作用、入口初值和应满足的条件预定义的常量和类型：#defineTRUE1#defineFALSE0#defineOK1#defineERROR 0#defineINFEASIBLE -1#defineOVERFLOW -2typedefintStatus;基本操作的描述基本操作的描述基本操作的描述基本操作的描述函数类型函数类型函数类型函数类型 函数名（函数参数表）函数名（函数参数表）函数名（函数参数表）函数名（函数参数表）/算法说明算法说明算法说明算法说明 语句序列语句序列语句序列语句序列/函数名函数名函数名函数名int 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.4算法和算法分析算法和算法分析一、算法的概念 算算算算法法法法是是是是解解解解决决决决某某某某一一一一个个个个/ /一一一一类类类类问问问问题题题题的的的的一一一一个个个个有有有有序序序序的的的的有有有有穷穷穷穷序序序序列，该序列确定了解决问题的方法和步骤。列，该序列确定了解决问题的方法和步骤。列，该序列确定了解决问题的方法和步骤。列，该序列确定了解决问题的方法和步骤。例：用辗转相除法求两个正整数的最大公因子例：用辗转相除法求两个正整数的最大公因子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;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 值 最好情况：比较一次最坏情况：比较n次平均情况：#defineN10main()inti,j,t,aN;printf(input10number:);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(thesortednumber: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(f1(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每秒处理106个指令，对于输入规模为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)=108log108=2.66109运行时间为运行时间为2.66109/106=2.66103秒分钟秒分钟例：设CPU每秒处理106个指令，则每小时能够解决的最大问题规模 T(n)/1063600对T(n)=2n2， 即2n23600 106n 42,426对对T(n)=nlog n 即nlogn3600 106 n 133,000,000对对T(n)=2n即即2n3600106 n常用的算法设计方法常用的算法设计方法穷举法(顺序查找，百钱买百鸡)贪心法(Huffman树，Dijkstra 算法，Prim 算法递归法, 分治法(折半检索，快速排序，归并排序)回溯法动态规划法(最短路 Floyd 算法 )分枝界限法并行算法分布式算法15数据结构在计算机科学中的地位数据结构在计算机科学中的地位WebWeb信息处理信息处理队列、图、字符、队列、图、字符、散列、排序、检索散列、排序、检索人工智能人工智能表、集合、有表、集合、有向图、搜索树向图、搜索树图形图像图形图像队列、栈、图、队列、栈、图、树、索引树、索引数据库原理数据库原理线性表、排序、线性表、排序、B+B+树树操作系统操作系统队列、表、队列、表、排序、树排序、树编译原理编译原理字符串、栈、散字符串、栈、散列表、语法树列表、语法树数据结构数据结构数据结构实验数据结构实验算法设计与分析算法设计与分析高级语言程序设计高级语言程序设计程序设计实践程序设计实践离散数学离散数学从问题求解出发从问题求解出发在在基础理论、抽象和设计基础理论、抽象和设计的三个层次组织知识体系的三个层次组织知识体系从从逻辑、存储、运算逻辑、存储、运算的角度学习数据结构与算法，的角度学习数据结构与算法，培养学生独立地实现常用基本数据结构的抽象数据类型，培养学生独立地实现常用基本数据结构的抽象数据类型，注重实践能力和工程能力的培养注重实践能力和工程能力的培养为将来从事计算机学科的学习、开发和研究，或其他学为将来从事计算机学科的学习、开发和研究，或其他学科应用计算机进行问题求解打下坚实的基础科应用计算机进行问题求解打下坚实的基础