数据结构与算法数据结构与算法实验课件

1、数据结构与算法数据结构与算法实验2014.9-2015.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)binlibuseretcmathdsclgyintaoxieStack.cppQueue.cppTree.cpp这类问题的数学模型称为树（树型结构、层次结构）树的特点： 除根外每个结点有唯一一个双亲(上级，祖先) 除叶子结点外，每个结点可以有多于一个儿子树的操作：各种遍历搜索例6 多叉路口交通灯管制 多叉路口需要设几种颜色的灯才能使车辆互不相撞且车流量最大需要：表示圆圈（道路） 表示边（是否冲突） 给出染色方法

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

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

7、 通常作为一个整体进行考虑和处理 数据元素的组成成员称为数据项 数据项：Data Item 数据的最小单位 一个数据元素由多个数据项组成 数据对象：Data Object 具有相同性质的数据元素的集合 如所有书目、所有扑克牌、所有格局、所有道路 数据类型：Data Type 数据结构：Data Structure（1）相互间存在一种或多种特定关系的数据元素的集合 一种或多种关系称为结构 有4种基本结构：数据的逻辑结构数学模型表树图实例图书管理扑克牌游戏人机对弈目录管理信号灯设置管道铺设数据元素图书牌格局目录道路连接点数据项书名、书号、作者等花色、点数、正反行、列、值名字、物理位置起点、终点、颜

8、色地理位置数据对象所有图书54张牌所有格局所有目录所有道路所有连接点关系顺序先后派生从属冲突架设数据的逻辑结构线性结构 线性表（表，栈，队列，串等） 非线性结构 树（二叉树，Huffman树， 二叉排序树等） 图（有向图，无向图等） 图 树 二叉树 线性表数据的存储结构（物理结构）逻辑结构到物理存储空间的映射 内存.顺序、链式、索引、散列 a1a2a3a4a5逻辑结构物理结构（一）物理结构（二）a1a2a3a4a5a3a4a2a5a10struct student /数据类型 int num; char name12; char sex; int age; int score5; int sc

9、oresum;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, V4S=, , , ,

10、（3）数据之间的结构关系 它包括数据的逻辑结构和 数据的物理结构（4）是一类普通数据的表示及其相关操作（5）根据各种不同的数据集合和数据之间的关系研究如何表示、存储、操作这些数据的技术 研究数据结构从三个方面进行：（1）逻辑结构（2）存储结构（3）操作（运算） 对数据进行的处理， 定义在数据的逻辑结构上 具体实现于数据的存储结构引用引用（reference）作用是为变量起一个别名例如：int a; int &b=a ;说明：（1）b是一个引用变量，它的作用与a相同 （2）b与a占用相同的内存空间1231000a假设变量a的地址为1000，值为123定义了int &b=a后:1231000ab（

11、3）b的作用域与a相同，在其作用域内，不能作为其它变量或其它变量的别名 （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）定义引用变量的作用是使得函数调用时， 实参与形参之间不仅有传值方式，还有传地址方式 引用变量做参数，相当于传地址void swap(int &x, int &y)int t; t=x; x=y; y=t;void main( )int a=3, b=4; sw

12、ap( 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: Ab

13、stract Data Types) 描述数据逻辑结构的工具(1)ADT是指一个数学模型及其在该模型上的一组操作(2)ADT只考虑数学模型上数据元素之间的逻辑关系， 而忽略其物理结构(3)ADT是一个逻辑数据类型以及定义在该类型上的一组操作，每个操作由它的输入/出定义，而隐藏其实现细节和物理结构，如定义一个整数类型及在整数类型上的操作(4)ADT由三元组构成：（D，S，P） D 数据对象 S 关系 P 操作集(5)约定格式为： ADT 抽象数据类型名 数据对象： 数据关系： 基本操作：ADT 抽象数据类型名基本操作的格式： 基本操作名（参数表） 初始条件： 操作结果： 形式参数： 赋值参数-传

14、值 引用参数-传地址ADT List数据对象:D=aiaiElemSet,i=1,2,3，,n,n0 数据关系:R=ai-1 ,aiD,i=2,3， ,n 基本操作:ReadFile(&L); 操作结果:从键盘上读入文件名,从文件中读入数据到表L中.SearchList(L,a); 初始条件:表L已经存在. 操作结果:在表L查找元素a,找到返回该元素指针 找不到返回NULL.InsertList(&L,a); 初始条件:表L已经存在. 操作结果:在表L插入元素aDeleteList(&L,a); 初始条件:表L已经存在. 操作结果:在表L中删除元素aPrintList(L); 初始条件:表L已

15、经存在. 操作结果:依次输出表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 pub

16、lish20; 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;typedef struct char 起点30; ch

17、ar 终点20; int 颜色号; .ElemType;用&x表示引用参数x函数类型为Status时表示函数的返回值为函数的 执行状态, 一般为Error或Ok辅助变量可以不说明以注释的形式表示：算法的功能参数表中各参数的定义和输入/出属性各种变量的作用、入口初值和应满足的条件预定义的常量和类型：#define TRUE 1#define FALSE0#define OK1#define ERROR0#define INFEASIBLE-1#define OVERFLOW-2typedef int Status;基本操作的描述函数类型 函数名（函数参数表） / 算法说明 语句序列/函数名int

18、 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 算法和算法分析一、算法的概念 算法是解决某一个/一类问题的一个有序的有穷序列，

19、该序列确定了解决问题的方法和步骤。例：用辗转相除法求两个正整数的最大公因子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;

20、sum=0;term=1;for(i=1; i0, n00) ，使得对任意的nn0 ， 都有f(n) c g(n) ， 称f(n)在集合O(g(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; iN; i+) scanf(%

21、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表示法的运算法则 加法规则: 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秒，因此需要231,481 天(634年）例：假设CPU每秒处理106个指令，对于输入规模为108的问题，时间代价为nlog n 的算法要运行多长时间？ 操作次数为 T(n) = T(108) = 108 log 108 = 2.66109运