数据结构与算法实验

《数据结构与算法实验》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构与算法数据结构与算法实验2012.9-2013.1纸上得来终觉浅，绝知此事要躬行读+写+讨论学习方法上课时间:周二1-2节周四1-2节上机时间:周四3-4节答疑时间:周一15:00-16:30239周三13:00-15:00239所有作业按时交，注释不少于30%书面作业晚依天9折放慢速度？9/25时常复习以前讲的？8个小时？全部/部分？只会课上讲的？答疑了吗？讲但不是全部部分内容需要自己学习希望预习北大：计算概论周4学时（48）3学分程序设计实习周4学时3学分数据结构与算法周4学时3学分数据结构与算法实习周2学时2学分首师大：C语言程序设计4+2面向对象程序设计3+2数据结构与算法4+

2、2算法设计与分析3复旦大学3+2浙江大学4湖南师大4+1南京师大4+2华东师大3+2上海师大3+2杭州电子科技大学4+1希望：提前5分钟到教室，不迟到不吃东西手机静音随时问，积极响应按时交作业对老师的希望？数据结构学什么数据结构的地位和作用怎么学好数据结构教学内容特点：用数学方程进行数值运算称这类问题的数学模型是数学方程第一章绪论例1：数学方程（1）用二分法求方程的根（2）用迭代法求a的平方根例2:学生成绩管理系统建立一个小型的学生成绩管理系统，该系统具有输入、查询、修改、打印功能。实验要求：（1）每位学生数据中包含学号、姓名、性别、年龄、五门课的成绩。要求学生人数不少于16人，从文件中输入数

3、据（2）能根据学号或姓名查询任一学生某门课程成绩或所有课程成绩（3）系统界面自行设计（4）能修改学生的任何一个数据，并设置相应的修改口令（5）能按总成绩从高到低显示所有学生的数据，包括每个学生的平均分，并输出到文件。涉及：数据录入数据查询数据维护数据排序、输出需要：建一张表确定表中前后数据的关系实现对表进行操作的方法学号姓名性别数学物理化学英语总成绩例3:扑克牌接龙游戏洗牌发牌、出牌、移牌比较、判断输赢判断（1）表示所有扑克牌（2）实现各种游戏动作特点：两个数据之间有一定顺序主要操作有：插入、查找、修改、删除称这类问题的数学模型为线性表(线性结构)学生成绩管理系统扑克牌接龙游戏........

4、....例4人机对奕..............................井字棋、中国象棋、国际象棋对奕过程中可能出现的棋盘状态称为格局格局之间的关系由下棋规则确定从一个格局中可以派生出若干个新格局从新格局又可以派生出更新的格局整个对奕过程可能派生出的所有格局就象一棵倒挂的树树根为对奕开始的格局树叶为可能出现的一种结局对奕的过程就是从树根走到树叶的过程表示每一种格局表示格局之间的派生关系给出对奕的算法：从所有儿子格局中找出最有利的格局需要87143291365141015111212356791011481213141515谜问题例5文件系统/(root)binlibuseretcmat

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

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

7、素的集合如所有书目、所有扑克牌、所有格局、所有道路数据类型：DataType数据结构：DataStructure（1）相互间存在一种或多种特定关系的数据元素的集合一种或多种关系称为结构有4种基本结构：数学模型表树图实例学生成绩管理扑克牌游戏人机对弈目录管理信号灯设置管道铺设数据元素学生牌格局目录道路连接点数据项姓名、学号、性别等花色、点数、正反行、列、值名字、物理位置起点、终点、颜色地理位置数据对