数据结构与算法数据结构与算法实验

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

1、数据结构与算法数据结构与算法实验2014.9-2015.1纸上得来终觉浅，绝知此事要躬行读+写+讨论学习方法所有作业按时交，注释不少于30%所有作业分为必做（80%）和选做（20%）上课时间:周一6-7节周四1-2节上机时间:周一8-9节答疑时间:周一16:30-17:30408讨论时间:周四9:40-10:40508？放慢速度？时常复习以前讲的？8个小时？只会课上讲的？答疑了吗？讲但不是全部部分内容需要自己学习希望预习复习自主学习希望：提前5分钟到教室，不迟到不吃东西手机静音随时提问，积极响应按时交作业对老师的希望？数据结构学什么数据结构的地位和作用怎

2、么学好数据结构教学内容特点：用数学方程进行数值运算称这类问题的数学模型是数学方程第一章绪论例1：数学方程（1）用二分法求方程的根（2）用迭代法求a的平方根例2:图书管理系统建立一个小型图书管理系统，该系统具有输入、查询、排序、修改、插入、删除、输出等功能。实验要求：（1）从文件中读入图书信息，每本图书至少包括书号、书名、作者、出版社、出版日期、单价等信息；图书数量不少于16本（2）能根据书号或书名或出版社查询所有满足条件的图书（3）系统界面自行设计（4）能够按照书名或出版日期排序（5）能能修改图书除书号外的所有信息（6）能从文件中追加新的图书数据（7）对

3、已经遗失的图书从系统中删除相应的图书信息涉及：数据录入数据查询数据维护数据排序、输出需要：建一张表确定表中前后数据的关系实现对表进行操作的方法书号书名作者出版社出版日期数量单价例3:扑克牌接龙游戏洗牌发牌、出牌、移牌比较、判断输赢判断（1）表示所有扑克牌（2）实现各种游戏动作特点：两个数据之间有一定顺序主要操作有：插入、查找、修改、删除称这类问题的数学模型为线性表(线性结构)学生成绩管理系统扑克牌接龙游戏............例4人机对奕..............................井字棋、中国象棋、国际象棋对奕过程中可能出现的棋盘状态称

4、为格局格局之间的关系由下棋规则确定从一个格局中可以派生出若干个新格局从新格局又可以派生出更新的格局整个对奕过程可能派生出的所有格局就象一棵倒挂的树树根为对奕开始的格局树叶为可能出现的一种结局对奕的过程就是从树根走到树叶的过程表示每一种格局表示格局之间的派生关系给出对奕的算法：从所有儿子格局中找出最有利的格局需要例5文件系统/(root)binlibuseretcmathdsclgyintaoxieStack.cppQueue.cppTree.cpp这类问题的数学模型称为树（树型结构、层次结构）树的特点：除根外每个结点有唯一一个双亲(上级，祖先)除叶子结点

5、外，每个结点可以有多于一个儿子树的操作：各种遍历搜索例6多叉路口交通灯管制多叉路口需要设几种颜色的灯才能使车辆互不相撞且车流量最大需要：表示圆圈（道路）表示边（是否冲突）给出染色方法四色定理-着色问题例7最短路径问题油田铺设管道，把原油送到加工厂，要求所铺设的管道最短农夫过河一个农夫带着—只狼、一只羊和—棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和—件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白

6、菜。请求出农夫将所有的东西运过河的方案。出发地目的地人羊狼菜（初始）人羊狼人羊菜人狼菜羊狼菜（不可能）出发地目的地人（不可能）羊狼菜空（结束）狼菜人菜（不可能）羊菜（不可能）人羊人狼（不可能）出发地所有状态特点：任何两个数据之间都可以有关系(单向、双向)操作：遍历、染色、最短路径这种数学模型称为图用计算机解决一个实际问题的步骤：问题分析建立模型确定算法设计程序上机调试结果典型的数学模型：表、树、图各种模型的典型算法典型的查找、排序算法简单的算法设计方法数据结构是一门研究计算机的操作对象以及操作对象之间的关系和对操作对象实施的典型操作的学科1.

7、1什么是数据结构操作对象关系典型操作1.2基本概念和术语数据：Data数据是计算机化的信息（对现实世界的事物采用计算机能够识别、存储和处理的形式所进行的描述）数值性数据非数值性数据数据元素：DataElement数据的基本单位，如格局、结点通常作为一个整体进行考虑和处理数据元素的组成成员称为数据项数据项：DataItem数据的最小单位一个数据元素由多个数据项组成数据对象：DataObject具有相同性质的数据元素的集合如所有书目、所有扑克牌、所有格局、所有道路数据类型：DataType数据结构：DataStructure（1）相互间存在一种或多种特定

8、关系的数据元素的集合一种或多种关系称为结构有4种基本结构：数据的逻辑结构数学模型