《数据结构与算法》第一章数据结构与算法实验.pptVIP

数据结构与算法 数据结构与算法实验 2016.9-2017.1;纸上得来终觉浅，绝知此事要躬行 读+写+讨论;放慢速度？ 时常复习以前讲的？ 8个小时？ 只会课上讲的？ 答疑了吗？;希望： 提前5分钟到教室，不迟到 不吃东西 手机静音 随时提问，积极响应 按时交作业;数据结构学什么 数据结构的地位和作用 怎么学好数据结构;特点：用数学方程进行数值运算 ;例2:图书管理系统;涉及： 数据录入 数据查询 数据维护 数据排序、输出;例3:扑克牌接龙游戏;特点：两个数据之间有一定顺序 主要操作有：插入、查找、修改、删除 称这类问题的数学模型为线性表(线性结构) ;;井字棋、中国象棋、国际象棋 对奕过程中可能出现的棋盘状态称为格局;格局之间的关系由下棋规则确定 从一个格局中可以派生出若干个新格局 从新格局又可以派生出更新的格局 整个对奕过程可能派生出的所有格局就象一棵倒挂的树 树根为对奕开始的格局 树叶为可能出现的一种结局 对奕的过程就是从树根走到树叶的过程;表示每一种格局 表示格局之间的派生关系 给出对奕的算法：从所有儿子格局中找出最有利的格局;例5 文件系统;这类问题的数学模型称为树（树型结构、层次结构） 树的特点： 除根外每个结点有唯一一个双亲(上级，祖先) 除叶子结点外，每个结点可以有多于一个儿子 树的操作：各种遍历有哪些信誉好的足球投注网站;例6 多叉路口交通灯管制 多叉路口需要设几种颜色的灯才能使车辆互不相撞且车流量最大;四色定理-着色问题;例7 最短路径问题 油田铺设管道，把原油送到加工厂，要求所铺设的管道最短;农夫过河 ;人羊狼菜 （初始）人羊狼 人羊菜 人狼菜 羊狼菜（不可能）;特点：任何两个数据之间都可以有关系(单向、双向) 操作：遍历、染色、最短路径 这种数学模型称为图;用计算机解决一个实际问题的步骤：;数据结构 是一门研究计算机的操作对象 以及操作对象之间的关系 和对操作对象实施的典型操作 的学科;操作对象 关系 典型操作;1.2 基本概念和术语; 数据项：Data Item 数据的最小单位 一个数据元素由多个数据项组成; 数据结构：Data Structure;;数据的逻辑结构;数据的存储结构（物理结构）;a1;struct student //数据类型 { int num; char name[12]; char sex; int age; int score[5]; int scoresum; }s[50]; //数据对象;struct stu //数据类型 {int num; int score; struct stu *next; }*head,*p1;;数据的存储结构借助于高级语言中的数据类型来描述;（2）数据元素+关系 数据结构是一个二元组： Data_structure=(D, S) D:数据元素的有穷集合 S:数据之间有穷关系的集合;（3）数据之间的结构关系 它包括数据的逻辑结构和 数据的物理结构 （4）是一类普通数据的表示及其相关操作 （5）根据各种不同的数据集合和数据之间的关系研究如何表示、存储、操作这些数据的技术;;逻辑结构;引用;（3）b的作用域与a相同，在其作用域内，不能作为其它变量或其它变量的别名 （4）定义一个引用变量的同时必须初始化-----说明它是谁的别名;（5）定义引用变量的作用是使得函数调用时， 实参与形参之间不仅有传值方式，还有传地址方式 引用变量做参数，相当于传地址;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);小汽车;(4)ADT由三元组构成：（D，S，P） D 数据对象 S 关系 P 操作集;基本操作的格式： 基本操作名（参数表） 初始条件：初始条件描述 操作结果：操作结果描述;ADT List {数据对象:D={ai∣ai∈ElemSet,i=1,2,3，…,n,n≥0} 数据关系:R={ai