《数据结构与算法》PPT课件.ppt

《《数据结构与算法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构与算法》PPT课件.ppt（59页珍藏版）》请在装配图网上搜索。

1、数据结构与算法 数据结构与算法实验 2010.9-2011.1,数据结构学什么 数据结构的地位和作用 怎么学好数据结构,教学内容,特点：用数学方程进行数值运算,称这类问题的数学模型是数学方程,第一章绪论,例1：数学方程 （1）用二分法求方程的根 （2）用迭代法求a的平方根,例2:学生成绩管理系统,建立一个小型的学生成绩管理系统，该系统具有输入、查询、修改、打印功能。 实验要求： （1）每位学生数据中包含学号、姓名、性别、年龄、五门课的成绩。要求学生人数不少于16人，从文件中输入数据 （2）能根据学号或姓名查询任一学生某门课程成绩或所有课程成绩 （3）系统界面自行设计 （4）能修改学生的任何一个

2、数据，并设置相应的修改口令 （5）能按总成绩从高到低显示所有学生的数据，包括每个学生的平均分，并输出到文件。,涉及： 数据录入 数据查询 数据维护 数据排序输出,需要： 建一张表 确定表中前后数据的关系 给出对表进行操作的方法,例3:扑克牌接龙游戏,需要：洗牌 发牌、出牌、移牌 比较、判断 赢牌,（1）表示所有扑克牌 （2）实现各种游戏动作,特点：两个数据之间有一定顺序 主要操作有：插入、查找、修改、删除 称这类问题的数学模型为线性表(线性结构),学生成绩管理系统,扑克牌接龙游戏,挖地雷游戏,.,.,例4 人机对奕,.,.,.,.,.,井字棋、中国象棋、国际象棋 对奕过程中可能出现的棋盘状态称

3、为格局,格局之间的关系由下棋规则确定 从一个格局中可以派生出若干个新格局 从新格局又可以派生出更新的格局 因此，整个对奕过程可能派生出的所有格局就象 一棵倒挂的树 树根为对奕开始的格局 树叶为可能出现的一种结局 对奕的过程就是从树根走到树叶的过程,表示每一种格局 表示格局之间的派生关系 给出对奕的算法：从所有儿子格局中找出 最有利的格局,需要,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,sw,yin,

4、tao,xie,Stack.cpp,Queue.cpp,Tree.cpp,这类问题的数学模型称为树（树型结构、层次结构） 树的特点： 除根外每个结点有唯一一个父亲(上级，祖先) 除叶子结点外，每个结点可以有多于一个儿子 树的操作：各种遍历搜索,例6 多叉路口交通灯管制 多叉路口需要设几种颜色的灯才能使车辆互不相撞且车流量最大,需要：表示圆圈（道路） 表示边（是否冲突） 给出染色方法,例7 最短路径问题 油田铺设管道，把原油送到加工厂，要求所铺设的管道最短,特点：任何两个数据之间都可以有关系(单向、双向) 操作：遍历、染色、最短路径 这种数学模型称为图,用计算机解决一个实际问题的步骤：,问题分析

5、 建立模型 确定算法 设计程序 上机调试 结 果,数据结构 是一门研究计算机的操作对象 以及操作对象之间的关系 和对操作对象实施的典型操作 的学科,11什么是数据结构,操作对象 关系 典型操作,12基本概念和术语,数据：Data 数据是计算机化的信息（对现实世界的事物采用计算机能够识别、存储和处理的形式所进行的描述） 数值性数据 非数值性数据,数据元素：Data Element 数据的基本单位，如格局、结点 通常作为一个整体进行考虑和处理 数据元素的组成成员称为数据项,数据项：Data Item 数据的最小单位 一个数据元素由多个数据项组成,数据对象：Data Object 具有相同性质的数据

6、元素的集合 如所有书目、所有扑克牌、所有格局、所有道路,数据类型：Data Type,数据结构：Data Structure,（1）相互间存在一种或多种特定关系的数据元素的集合 一种或多种关系称为结构 有4种基本结构：,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

7、,*p1;,数据项,*p1、*head、. 数据元素 链表-数据关系的表示 head为首的数据元素构成数据对象,（2）数据元素+关系 数据结构是一个二元组： Data_structure=(D, S) D:数据元素的有穷集合 S:数据之间有穷关系的集合,例：DS1=（D，S） D=V1，V2，V3, V4 S=, , , , ,其中： 关系的描述是数据元素之间的逻辑关系， 称为数据的逻辑结构 数据元素及其逻辑关系在机内的表示 称为数据的物理结构，或数据的存储结构,a1,a2,a3,a4,a5,逻辑结构,物理结构（一）,物理结构（二）,a1,a2,a3,a4,a5,a3,a4,a2,a5,a1,

8、0,关系的表示方法,数据的存储结构借助于高级语言中的数据类型来描述,顺序映象 非顺序映象,链式存储结构,（3）数据之间的结构关系 它包括数据的逻辑结构和 数据的物理结构 （4）是一类普通数据的表示及其相关操作 （5）根据各种不同的数据集合和数据之间的关系研究如何表示、存储、操作这些数据的技术,研究数据结构从三个方面进行： （1）逻辑结构 （2）存储结构 （3）操作（运算）： 对数据进行的处理， 定义在数据的逻辑结构上 具体实现于数据的存储结构,引用,引用（reference）作用是为变量起一个别名 例如：int a; int 说明：（1）b是一个引用变量，它的作用与a相同 （2）b与a占用相同

9、的内存空间,假设变量a的地址为1000，值为123,定义了int b= int ,（5）定义引用变量的作用是使得函数调用时， 实参与形参之间不仅有传值方式，还有传地址方式 引用变量做参数，相当于传地址,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) 描述数据逻辑

10、结构的工具,交通工具,发动交通工具( ); 前进( ); 后退( ); 左转( ); 右转( ); 停止( );,(1)ADT是指一个数学模型及其在该模型上的一组操作 (2)ADT只考虑数学模型上数据元素之间的逻辑关系， 而忽略其物理结构,(3)ADT是一个逻辑数据类型以及定义在该类型上的一组操作，每个操作由它的输入/出定义，而隐藏其实现细节，如定义一个整数类型及在整数类型上的操作,(4)ADT由三元组构成：（D，S，P） D 数据对象 S 关系 P 操作集,(5)约定格式为： ADT 抽象数据类型名 数据对象： 数据关系： 基本操作： ADT 抽象数据类型名,基本操作的格式： 基本操作名（参

11、数表） 初始条件： 操作结果：,形式参数： 赋值参数-传值 引用参数-传地址,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 call int num; cha

12、r name10; char position10; char zhicheng; char mobile20; ;,/定义表示职工结构体 struct call int num; char name10; float jiben; float jiangjin; float butie; ;,ADT List 数据对象:D=aiaiElemSet,i=1,2,3，,n,n0 数据关系:R=ai-1 ,aiD,i=2,3， ,n 基本操作: ReadFile( 初始条件:表L已经存在. 操作结果:依次输出表L的所有元素 ,13抽象数据类型的表示与实现,1原则： 通过已有的类型定义或组合成新的类

13、型 用类C语言描述,2C+引用参数 引用（reference）是一种新的变量类型 它的作用是为变量起一个别名,3各种预定义和约定,数据元素的类型为ElemType 数据存储结构用typedef定义,typedef struct int num; char name10; char sex; int age; . ElemType;,用,基本操作的描述 函数类型 函数名（函数参数表） / 算法说明 语句序列 /函数名,1.4算法和算法分析,一、算法的概念 算法是解决某一个/一类问题的一个有序的有穷序列，该序列确定了解决问题的方法和步骤。,例：用辗转相除法求两个正整数的最大公因子 1输入m和n 2

14、若mn0，有 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; i+) printf(“%3d”,ai); printf(“n”); ,3空间复杂度 S（n）,4效率对算法的影响,例：假设CPU每秒处理10 6 个指令，对于输入规模为108的问题，时间代价T(n) = 2n2的算法要运行多长时间？,操

15、作次数为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

16、106 n 42 , 426 对T(n) = nlog n 即nlogn 3600 106 n 133 , 000 , 000 对T(n)=2n 即2n3600 106 n41.36,常用的算法设计方法 穷举法 (百钱买百鸡、搬砖问题) 贪心法 (Huffman树) 递归法, 分治法(折半检索) 回溯法 动态规划法 广度优先和深度优先搜索 分枝界限法 并行算法,15数据结构在计算机科学中的地位,Web信息处理 队列、图、字符、散列、排序、检索,人工智能 表、集合、有向图、搜索树,图形图像 队列、栈、图、树、索引,数据库原理 线性表、排序、B+树,操作系统 队列、表、排序、树,编译原理 字符串、

17、栈、散列表、语法树,数据结构,数据结构实验,算法设计与分析,高级语言程序设计,程序设计实践,离散数学,课程目标,学会如何有效地组织信息，以便支持高效的数据处理 掌握常用的基本数据结构及其应用 学会合理地组织数据，有效地表示数据，有效地处理数据 基本掌握算法分析技术 提高程序设计能力与程序的质量 提高使用计算机解决问题的能力,从问题求解出发 在基础理论、抽象和设计的三个层次组织知识体系 从逻辑、存储、运算的角度学习数据结构与算法， 培养学生独立地实现常用基本数据结构的抽象数据类型，注重实践能力和工程能力的培养 为将来从事计算机学科的学习、开发和研究，或其他学科应用计算机进行问题求解打下坚实的基础,学习内容,三种典型的数据结构及典型操作 两类典型算法 算法评价基本知识,纸上得来终觉浅，绝知此事要躬行 读+写+讨论,学习方法,上课时间:周一4-5节 周四1-2节 上机时间:周一9-10节 答疑时间:周三中午1:00-2:00,所有作业按时交，注释不少于20%,