数据结构课程设计2017.ppt

数据结构课程设计题目 题目一 大数算术表达式求值 题目二 求解马踏棋盘问题 题目三 校园导游 题目一 大数算术表达式求值 问题描述 表达式求值是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。 以字符序列的形式从终端上输入语法正确的、不含变量的整数（大数）表达式。实现对算术四则混合运算表达式的求值，显示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。 输出格式要求 要求分步骤输出，每一步输出格式： STEP X OP Stack pop： XXXX （或 OP Stack push： XXXX ） NUM Stack pop：XXXX （或 NUM Stack push： XXXX ） …… NUM Stack push： XXXX 这里要求打印出该步具体的出栈入栈顺序，OP stack表示运算符栈、 NUM stack表示运算数栈。 每步最后打印两个栈的状态，格式： OP Stack ： [0] XXX [1]XXX NUM Stack： [0] XXX [1]XXX [2]XXX 题目二 求解马踏棋盘问题 问题描述 将马随机放在国际象棋8*8的棋盘的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。试求出马的行走路线。要求： 编制非递归程序； 打印求出的行走路线； 将数字1，2，…，64依次填入的8*8方阵，输出之。 问题分析 每次在多个可走位置中随机选择一个，用适当结构妥善管理位置，试探失败时回溯。 问题分析 7 7 7 7 5 5 5 5 添加策略： 为每一个位置设置一个权值，表示该位置可以到达的位置数；移动时向权值大的位置移动 输出格式要求 A B C D E F G H 1 2 3 4 5 6 7 8 马位置表示： （D4） 马移动输出格式： 1 STEP FROM TO 1 （D4） （C6） 2 （C6） （A7） 64 （XX） （XX） …… 2 3 输出格式要求 棋盘输出格式： 1 2 3 4 5 6 7 8 A X X X X X X X X B X X X X X X X X C X X X X X X X X D X X X X X X X X E X X X X X X X X F X X X X X X X X G X X X X X X X X H X X X X X X X X 题目三 校园导游 问题描述 设计校园平面图，所含景点不少于10个。以图中顶点表示学校各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。要求： 为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径； 为来访客人提供图中景点间的推荐路线（遍历各节点的最短路线）和各景点之间的介绍。 图信息 1. 南大门广场 2. 光谷体育馆 3. 眼镜湖 4.紫松 5.青年园 6.集贸市场 7.光电实验室 8.东九孔子像 9.瑜园 10.珞珈山 11.韵苑 12.爱因斯坦广场 图信息 各景点简介自己填写 50 32 30 40 20 40 40 40 26 25 20 39 100 10 10 20 30 1. 南大门广场 2. 光谷体育馆 3. 眼镜湖 4.紫松 8.东九… 9.瑜园 10.珞珈山 11.韵苑 12.爱因斯… 7.光电… 5.青年园 6.集贸市场 问题分析 节点组成无向图，则可用最短路径求解： Dijkstra 算法 Floyd算法 输出格式要求 顺序打印景点和介绍，格式要求： STEP1： 景点名 景点介绍 两个景点间打印两景点距离和以走距离： DISTANCE：XXX and ?TRAVELLED：XXX 最后打印总的路程长度： TOTAL：XXX