《数据结构和算法数据结构和算法实验》由会员分享，可在线阅读，更多相关《数据结构和算法数据结构和算法实验（70页珍藏版）》请在金锄头文库上搜索。
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）能从文件中追加
3、新的图书数据 （7）对已经遗失的图书从系统中删除相应的图书信息,涉及： 数据录入 数据查询 数据维护 数据排序、输出,需要： 建一张表 确定表中前后数据的关系 实现对表进行操作的方法,例3:扑克牌接龙游戏,洗牌 发牌、出牌、移牌 比较、判断 输赢判断,（1）表示所有扑克牌 （2）实现各种游戏动作,特点：两个数据之间有一定顺序 主要操作有：插入、查找、修改、删除 称这类问题的数学模型为线性表(线性结构),学生成绩管理系统,扑克牌接龙游戏,例4 人机对奕,井字棋、中国象棋、国际象棋 对奕过程中可能出现的棋盘状态称为格局,格局之间的关系由下棋规则确定 从一个格局中可以派生出若干个新格局 从新格局又可
4、以派生出更新的格局 整个对奕过程可能派生出的所有格局就象一棵倒挂的树 树根为对奕开始的格局 树叶为可能出现的一种结局 对奕的过程就是从树根走到树叶的过程,表示每一种格局 表示格局之间的派生关系 给出对奕的算法：从所有儿子格局中找出 最有利的格局,需要,例5 文件系统,/ (root),bin,lib,user,etc,math,ds,clg,yin,tao,xie,Stack.cpp,Queue.cpp,Tree.cpp,这类问题的数学模型称为树（树型结构、层次结构） 树的特点： 除根外每个结点有唯一一个双亲(上级，祖先) 除叶子结点外，每个结点可以有多于一个儿子 树的操作：各种遍历搜索,例6
5、 多叉路口交通灯管制 多叉路口需要设几种颜色的灯才能使车辆互不相撞且车流量最大,需要：表示圆圈（道路） 表示边（是否冲突） 给出染色方法,四色定理-着色问题,例7 最短路径问题 油田铺设管道，把原油送到加工厂，要求所铺设的管道最短,农夫过河,一个农夫带着只狼、一只羊和棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请求出农夫将所有的东西运过河的方案。,出发地,目的地,人羊狼菜 （初始） 人
6、羊狼 人羊菜 人狼菜 羊狼菜（不可能）,出发地,目的地,人（不可能） 羊 狼 菜 空（结束）,狼菜 人菜（不可能） 羊菜（不可能） 人羊 人狼（不可能）,出发地所有状态,特点：任何两个数据之间都可以有关系(单向、双向) 操作：遍历、染色、最短路径 这种数学模型称为图,用计算机解决一个实际问题的步骤：,问题分析 建立模型 确定算法 设计程序 上机调试 结 果,数据结构 是一门研究计算机的操作对象 以及操作对象之间的关系 和对操作对象实施的典型操作 的学科,1.1 什么是数据结构,操作对象 关系 典型操作,1.2 基本概念和术语,数据：Data 数据是计算机化的信息（对现实世界的事物采用计算机能够
7、识别、存储和处理的形式所进行的描述） 数值性数据 非数值性数据,数据元素：Data Element 数据的基本单位，如格局、结点 通常作为一个整体进行考虑和处理 数据元素的组成成员称为数据项,数据项：Data Item 数据的最小单位 一个数据元素由多个数据项组成,数据对象：Data Object 具有相同性质的数据元素的集合 如所有书目、所有扑克牌、所有格局、所有道路,数据类型：Data Type,数据结构：Data Structure,（1）相互间存在一种或多种特定关系的数据元素的集合 一种或多种关系称为结构 有4种基本结构：,数据的逻辑结构,数据的逻辑结构,线性结构 线性表（表，栈，队列
8、，串等） 非线性结构 树（二叉树，Huffman树， 二叉排序树等） 图（有向图，无向图等）,图 树 二叉树 线性表,数据的存储结构（物理结构）,逻辑结构到物理存储空间的映射,内存,. . . . .,顺序、链式、索引、散列,a1,a2,a3,a4,a5,逻辑结构,物理结构（一）,物理结构（二）,a1,a2,a3,a4,a5,a3,a4,a2,a5,a1,0,struct student /数据类型 int num; char name12; char sex; int age; int score5; int scoresum; s50; /数据对象,数据项,s0、s1、s2、. 数据元素
9、数组-数据关系的表示,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=, , , , ,（3）数据之间的结构关系 它包括数
10、据的逻辑结构和 数据的物理结构 （4）是一类普通数据的表示及其相关操作 （5）根据各种不同的数据集合和数据之间的关系研究如何表示、存储、操作这些数据的技术,研究数据结构从三个方面进行： （1）逻辑结构 （2）存储结构 （3）操作（运算） 对数据进行的处理， 定义在数据的逻辑结构上 具体实现于数据的存储结构,引用,引用（reference）作用是为变量起一个别名 例如：int a; int 说明：（1）b是一个引用变量，它的作用与a相同 （2）b与a占用相同的内存空间,假设变量a的地址为1000，值为123,定义了int &b=a后:,（3）b的作用域与a相同，在其作用域内，不能作为其它变量或其
11、它变量的别名 （4）定义一个引用变量的同时必须初始化-说明它是谁的别名,输出： a=10 b=10 a=100,main( ) int a=10; 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 ,抽象
12、数据类型 (ADT: Abstract Data Types),描述数据逻辑结构的工具,(1)ADT是指一个数学模型及其在该模型上的一组操作 (2)ADT只考虑数学模型上数据元素之间的逻辑关系， 而忽略其物理结构,(3)ADT是一个逻辑数据类型以及定义在该类型上的一组操作，每个操作由它的输入/出定义，而隐藏其实现细节和物理结构，如定义一个整数类型及在整数类型上的操作,(4)ADT由三元组构成：（D，S，P） D 数据对象 S 关系 P 操作集,(5)约定格式为： ADT 抽象数据类型名 数据对象： 数据关系： 基本操作： ADT 抽象数据类型名,基本操作的格式： 基本操作名（参数表） 初始条件
13、： 操作结果：,形式参数： 赋值参数-传值 引用参数-传地址,ADT List 数据对象:D=aiaiElemSet,i=1,2,3，,n,n0 数据关系:R=ai-1 ,aiD,i=2,3， ,n 基本操作: ReadFile( 初始条件:表L已经存在. 操作结果:在表L中删除元素a,PrintList(L); 初始条件:表L已经存在. 操作结果:依次输出表L的所有元素 ,1. 学生成绩管理系统 2电话簿管理系统 3学校图书管理系统 4职工工资管理系统,功能:输入、查询、修改、打印,/定义表示学生结构体 struct stu int num; char name10; char class1
14、0; 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; ;,/定义表示职工结构体 struct employe int num; char name10; float jiben; float jiangjin; float butie;
15、;,1.3 抽象数据类型的表示与实现,1原则： 通过已有的类型定义或组合成新的类型 用类C语言描述,2C+引用参数,3各种预定义和约定,数据元素的类型为ElemType 数据存储结构用typedef定义,typedef struct int num; char name10; char sex; int age; . 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;,基本操作的描述 函数类型 函数名（函数参数表） / 算法说明 语句序列 /函数名,int f1(int n, int ,Status f1(int n, int ,1.4 算法和算法分析,一、算法的
