数据结构与算法 数据结构与算法实验 2010.9-2011.1

教学内容 数据结构学什么 数据结构的地位和作用 怎么学好数据结构

第一章绪论 特点：用数学方程进行数值运算 称这类问题的数学模型是数学方程 例1：数学方程 （1）用二分法求方程的根 （2）用迭代法求a的平方根 特点：用数学方程进行数值运算 称这类问题的数学模型是数学方程

例2:学生成绩管理系统 建立一个小型的学生成绩管理系统，该系统具有输入、查询、修改、打印功能。 实验要求： （1）每位学生数据中包含学号、姓名、性别、年龄、五门课的成绩。要求学生人数不少于16人，从文件中输入数据 （2）能根据学号或姓名查询任一学生某门课程成绩或所有课程成绩 （3）系统界面自行设计 （4）能修改学生的任何一个数据，并设置相应的修改口令 （5）能按总成绩从高到低显示所有学生的数据，包括每个学生的平均分，并输出到文件。

涉及： 数据录入 数据查询 数据维护 数据排序输出 需要： 建一张表 确定表中前后数据的关系 给出对表进行操作的方法

例3:扑克牌接龙游戏 需要：洗牌 发牌、出牌、移牌 比较、判断 赢牌 （1）表示所有扑克牌 （2）实现各种游戏动作

称这类问题的数学模型为线性表(线性结构) 学生成绩管理系统 扑克牌接龙游戏 挖地雷游戏 特点：两个数据之间有一定顺序 主要操作有：插入、查找、修改、删除 称这类问题的数学模型为线性表(线性结构)

例4 人机对奕 ...... ...... ...... ...... ...... ...... ......

井字棋、中国象棋、国际象棋 对奕过程中可能出现的棋盘状态称为格局

格局之间的关系由下棋规则确定 从一个格局中可以派生出若干个新格局 从新格局又可以派生出更新的格局 因此，整个对奕过程可能派生出的所有格局就象 一棵倒挂的树 树根为对奕开始的格局 树叶为可能出现的一种结局 对奕的过程就是从树根走到树叶的过程

需要 表示每一种格局 表示格局之间的派生关系 给出对奕的算法：从所有儿子格局中找出 最有利的格局

8 7 6 1 2 3 4 1 4 3 5 5 6 7 8 2 9 13 14 9 10 11 12 10 15 11 12 13 14 15 15谜问题

例5 文件系统 / (root) bin lib user etc math ds sw yin tao xie Queue.cpp Stack.cpp Tree.cpp

这类问题的数学模型称为树（树型结构、层次结构） 树的特点： 除根外每个结点有唯一一个父亲(上级，祖先) 除叶子结点外，每个结点可以有多于一个儿子 树的操作：各种遍历搜索

例6 多叉路口交通灯管制 多叉路口需要设几种颜色的灯才能使车辆互不相撞且车流量最大 需要：表示圆圈（道路） 表示边（是否冲突） 给出染色方法

例7 最短路径问题 油田铺设管道，把原油送到加工厂，要求所铺设的管道最短

特点：任何两个数据之间都可以有关系(单向、双向) 操作：遍历、染色、最短路径 这种数学模型称为图 从数学上看，树型结构和图结构的基本区别就是“每个结点是否仅仅从属一个直接上级”。而线性结构和树型结构的基本区别是“每个结点是否仅仅有一个直接后继” 特点：任何两个数据之间都可以有关系(单向、双向) 操作：遍历、染色、最短路径 这种数学模型称为图

用计算机解决一个实际问题的步骤： 问题分析  建立模型 确定算法 设计程序 上机调试 结 果 典型的数学模型：表、树、图 结 果 典型的数学模型：表、树、图 各种模型的典型算法 典型的查找、排序算法

1．1什么是数据结构 数据结构 是一门研究计算机的操作对象 以及操作对象之间的关系 和对操作对象实施的典型操作 的学科

操作对象 关系 典型操作

1．2基本概念和术语 数据：Data 数据是计算机化的信息（对现实世界的事物采用计算机能够识别、存储和处理的形式所进行的描述） 数值性数据 非数值性数据 数据元素：Data Element 数据的基本单位，如格局、结点 通常作为一个整体进行考虑和处理 数据元素的组成成员称为数据项

数据类型：Data Type 数据项：Data Item 数据的最小单位 一个数据元素由多个数据项组成 数据对象：Data Object 具有相同性质的数据元素的集合 如所有书目、所有扑克牌、所有格局、所有道路 数据类型：Data Type

数据结构：Data Structure （1）相互间存在一种或多种特定关系的数据元素的集合 一种或多种关系称为结构 有4种基本结构：

数学 模型 表  树  图  实例 学生成绩管理 扑克牌游戏 人机对弈 目录管理 信号灯设置 管道铺设 数据 元素 学生 牌 格局 目录 道路 连接点 项 姓名、学号、性别等 花色、点数、正反 行、 列、 值 名字、物理 位置 起点、终点、颜色 地理位置 对象 所有学生 54张牌 所有格局 所有目录 所有道路 所有连接点 关系 顺序 先后 派生 从属 冲突 架设

数据项 s[0]、s[1]、s[2]、......... 数据元素 数组-----数据关系的表示 struct student //数据类型 { int num; char name[12]; char sex; int age; int score[5]; int scoresum; }s[50]; //数据对象 数据项 s[0]、s[1]、s[2]、......... 数据元素 数组-----数据关系的表示

数据项 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, V4} S={<V1,V2>, <V1,V4>, <V2,V3>, <V2,V4>, <V3,V4>} 其中： 关系的描述是数据元素之间的逻辑关系， 称为数据的逻辑结构 数据元素及其逻辑关系在机内的表示 称为数据的物理结构，或数据的存储结构

逻辑结构 a1 a2 a3 a4 a5 物理结构（一） a1 a2 a3 a4 a5 物理结构（二） a3 a4 a2 a5 a1

关系的表示方法 顺序映象 非顺序映象 顺序存储结构 链式存储结构 数据的存储结构借助于高级语言中的数据类型来描述

（3）数据之间的结构关系 它包括数据的逻辑结构和 数据的物理结构 （4）是一类普通数据的表示及其相关操作 （5）根据各种不同的数据集合和数据之间的关系研究如何表示、存储、操作这些数据的技术

（1）逻辑结构 （2）存储结构 （3）操作（运算）： 对数据进行的处理， 定义在数据的逻辑结构上 具体实现于数据的存储结构 研究数据结构从三个方面进行： （1）逻辑结构 （2）存储结构 （3）操作（运算）： 对数据进行的处理， 定义在数据的逻辑结构上 具体实现于数据的存储结构

引用 a a b 1000 123 1000 123 引用（reference）作用是为变量起一个别名 例如：int a; int &b=a ; 说明：（1）b是一个引用变量，它的作用与a相同 （2）b与a占用相同的内存空间 假设变量a的地址为1000，值为123 123 1000 a 123 1000 a b 定义了int b=&a后:

（3）b的作用域与a相同，在其作用域内，不能作为其它变量或其它变量的别名 （4）定义一个引用变量的同时必须初始化-----说明它是谁的别名 main( ) {int a=10; int &b=a； printf(“a=%d\n”,a); printf(“b=%d\n”,b); b=100; } 输出： a=10 b=10 a=100

（5）定义引用变量的作用是使得函数调用时， 实参与形参之间不仅有传值方式，还有传地址方式 引用变量做参数，相当于传地址 void swap(int &x, int &y) {int t; t=x; x=y; y=t; } void main( ) {int a=3, b=4; swap( a, b); printf(“a=%d, b=%d\n”, a,b); 比较： void swap1(int x, int y) {int t; t=x; x=y; y=t; } void swap2(int *x, int *y) t=*x; *x=*y; *y=t; 输出： a=4,b=3

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: Abstract Data Types) 描述数据逻辑结构的工具 交通工具 发动交通工具( ); 前进( ); 后退( ); 左转( ); 右转( ); 停止( );

(1)ADT是指一个数学模型及其在该模型上的一组操作 而忽略其物理结构 (3)ADT是一个逻辑数据类型以及定义在该类型上的一组操作，每个操作由它的输入/出定义，而隐藏其实现细节，如定义一个整数类型及在整数类型上的操作

(4)ADT由三元组构成：（D，S，P） D 数据对象 S 关系 P 操作集 (5)约定格式为： ADT 抽象数据类型名 { 数据对象：<数据对象的定义> 数据关系：<数据关系的定义> 基本操作：<基本操作的定义> }ADT 抽象数据类型名

基本操作的格式： 基本操作名（参数表） 初始条件：<初始条件描述> 操作结果：<操作结果描述> 形式参数： 赋值参数--------传值 引用参数-------传地址

1. 学生成绩管理系统 2．电话簿管理系统 3．学校人员管理系统 4．职工工资管理系统 功能:输入、查询、修改、打印 //定义表示学生结构体 struct stu {int num; char name[10]; char class[10]; int score[5]; }; //定义表示联系方式的结构体 struct call { char name[10]; char class[10]; int telephone; char mobile[12]; char addr[20]; }; //定义表示职工结构体 struct call { int num; char name[10]; char position[10]; char zhicheng; char mobile[20]; }; //定义表示职工结构体 struct call { int num; char name[10]; float jiben; float jiangjin; float butie; };

ADT List {数据对象:D={ai∣ai∈ElemSet,i=1,2,3，…,n,n≥0} 数据关系:R={<ai-1 ,ai>∣ai-1 ,ai∈D,i=2,3， …,n} 基本操作: ReadFile(&L); 操作结果:从键盘上读入文件名 从文件中读入数据到表L中. SearchList(&L,a); 初始条件:表L已经存在. 操作结果:在表L查找元素a,找到返回该元素指针 找不到返回NULL. InsertList(&L,a); 操作结果:在表L插入元素a PrintList(L); 操作结果:依次输出表L的所有元素 }

1．3抽象数据类型的表示与实现 1．原则： 通过已有的类型定义或组合成新的类型 用类C语言描述 2．C++引用参数 引用（reference）是一种新的变量类型 它的作用是为变量起一个别名

typedef struct { char 起点[30]; char 终点[20]; int 颜色号; ………. }ElemType; 3．各种预定义和约定 数据元素的类型为ElemType 数据存储结构用typedef定义 typedef struct { int num; char name[10]; char sex; int age; ………. }ElemType; typedef struct { char 起点[30]; char 终点[20]; int 颜色号; ………. }ElemType;

用&x表示引用参数x 函数类型为Status时表示函数的返回值为函数的 执行状态, 一般为Error或Ok 辅助变量可以不说明 以注释的形式表示： 算法的功能 参数表中各参数的定义和输入/出属性 各种变量的作用、入口初值和应满足的条件

预定义的常量和类型： #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; 基本操作的描述 函数类型 函数名（函数参数表） { // 算法说明 语句序列 }//函数名

1.4算法和算法分析 一、算法的概念 算法是解决某一个/一类问题的一个有序的有穷序列，该序列确定了解决问题的方法和步骤。 例：用辗转相除法求两个正整数的最大公因子 1．输入m和n 2．若m<n, 则交换m和n 3．m除以n，余数为r 4．若r= =0，则n为最大公因子，输出n，否则执行5 5．nm，rn，转3

三、算法设计的要求： 可读性 健壮性/容错性 有效性 二、算法的特征 有穷性 确定性 可行性 输入 输出 例：用辗转相除法求两个正整数的最大公因子 1．输入m和n 2．若m<n, 则交换m和n 3．m除以n，余数为r 4．若r=0，则n为最大公因子，输出n，否则执行5 5．nm，rn，转3 二、算法的特征 有穷性 确定性 可行性 输入 输出 三、算法设计的要求： 正确性 可读性 健壮性/容错性 有效性

四、算法的效率 1．效率：时间、空间 2．时间复杂度 算法中最基本、主要的运算执行的次数作为算法执行时间长短的度量称为算法的时间复杂度，它是问题规模的函数，记作T(n) 一般以量级的形式来讨论时间复杂度 一个函数f(n)是g(n) 级的，当且仅当存在一个常数c和一个整数n0 (c>0, n00)，对于一切n>n0，有 f(n)  c g(n) 成立 记作：O(g(n))

3．空间复杂度 #define N 10 main( ) { int i, j, t, a[N]; S（n） #define N 10 main( ) { int i, j, t, a[N]; printf(“input 10 number:”); for(i=0; i<N; i++) scanf(“%d”,&a[i]); for(i=1; i<N; i++) for(j=0; j<N-i+1; j++) if(a[j]>a[j+1]) {t=a[j]; a[j]=a[j+1]; a[j+1]=t;} printf(“the sorted number:\n”); for(i=0; i<N; i++) printf(“%3d”,a[i]); printf(“\n”); }

4．效率对算法的影响

例：假设CPU每秒处理10 6 个指令，对于输入规模为108的问题，时间代价T(n) = 2n2的算法要运行多长时间？ 操作次数为T(n) = T(108) = 2×(108)2 = 2×1016 运行时间为2×1016/106 = 2×1010秒 每天有86,400秒，因此需要231,481 天(634年）

例：假设CPU每秒处理106个指令，对于输入规模为108的问题，时间代价为nlog n 的算法要运行多长时间？ 操作次数为 T(n) = T(108) = 108 ×log 108 = 2.66×109 运行时间为2.66×109/106 = 2.66×103秒= 44.33分钟 如果时间代价是n的3次方,需要运行时间是31709791983年

例：设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 即2n≤3600 ×106 n≤41.36

常用的算法设计方法 穷举法 (百钱买百鸡、搬砖问题) 贪心法 (Huffman树) 递归法, 分治法(折半检索) 回溯法 动态规划法 穷举法　(百钱买百鸡、搬砖问题) 贪心法　(Huffman树) 递归法, 分治法(折半检索) 回溯法 动态规划法 广度优先和深度优先搜索 分枝界限法 并行算法

1．5数据结构在计算机科学中的地位 Web信息处理 人工智能 图形图像 数据库原理 操作系统 编译原理 数据结构实验 算法设计与分析 队列、图、字符、散列、排序、检索 人工智能 表、集合、有向图、搜索树 图形图像 队列、栈、图、树、索引 数据库原理 线性表、排序、B+树 操作系统 队列、表、排序、树 编译原理 字符串、栈、散列表、语法树 数据结构实验 算法设计与分析 数据结构 程序设计实践 离散数学 高级语言程序设计

课程目标 学会如何有效地组织信息，以便支持高效的数据处理 掌握常用的基本数据结构及其应用 学会合理地组织数据，有效地表示数据，有效地处理数据 基本掌握算法分析技术 提高程序设计能力与程序的质量 提高使用计算机解决问题的能力

从问题求解出发 在基础理论、抽象和设计的三个层次组织知识体系 从逻辑、存储、运算的角度学习数据结构与算法， 培养学生独立地实现常用基本数据结构的抽象数据类型，注重实践能力和工程能力的培养 为将来从事计算机学科的学习、开发和研究，或其他学科应用计算机进行问题求解打下坚实的基础

学习内容 三种典型的数据结构及典型操作 两类典型算法 算法评价基本知识

学习方法 纸上得来终觉浅，绝知此事要躬行 读+写+讨论 上课时间:周一4-5节 周四1-2节 上机时间:周一9-10节 答疑时间:周三中午1:00-2:00 所有作业按时交，注释不少于20%