实验一 数据结构基础.doc

衡阳师范学院地理信息系统专业实验指导 数据结构（C+）实验一 数据结构基础班级： 08级GIS 班 姓名：胡婷艳 学号： 08180108 实验目的：1、 掌握C+编程的基础知识与基本技能2、 熟练C+数据结构的基本概念，了解数据结构、算法及其性能度量的方法3、 掌握ADT与伪代码的书写方法与技能实验内容：1、为整数定义一个抽象数据类型。它包含整数的常见运算，每一个运算对应一个函数，有它的输入输出定义。思路指导：ADT integer is Data 整数 Operations: Constructor 输入：一个整数 处理： 将这个整数赋给Data Set 输入：一个整数 处理： 把这个参数赋给Data minus： 输入：无 输出：一个整数 处理：将当前整数取负，把结果输出 addition： 输入：一个整数 输出：一个整数 处理：将当前整数与输入的整数相加，把结果输出 subtraction： 输入：一个整数 输出：一个整数 处理：用当前整数减去输入的整数，把结果输出 multiplication： 输入：一个整数 输出：一个整数 处理：将当前整数与输入的整数相乘，把结果输出 division： 输入：一个非零整数 输出：一个整数 处理：用当前整数除以输入的整数，把商输出(把余数忽略） mod： 输入：一个非零整数 输出：一个整数 处理：用当前整数除以输入的整数，把余数输出(把商忽略） exponent： 输入：一个非负整数 输出：一个整数 处理：计算当前整数的输入整数次幂，把结果输出 equality： 输入：一个整数 输出:一个布尔值 处理:判断当前整数与输入的整数是否相等，输出比较结果(true or false） unequality: 输入：一个整数 输出：一个布尔值 处理：判断当前整数与输入的整数是否不等，输出比较结果(true or false） more： 输入：一个整数 输出：一个布尔值 处理：判断当前整数是否大于输入的整数，输出比较结果(true or false) no more： 输入：一个整数 输出：一个布尔值 处理：判断当前整数是否小于等于输入的整数，输出比较结果(true or false） 1ess： 输入：一个整数 输出：一个布尔值 处理：判断当前整数是否小于输入的整数，输出比较结果(true or false） no_less： 输入：一个整数 输出：一个布尔值 处理：判断当前整数是否大于等于输入的整数，输出比较结果(true or false）End ADT integer2、 什么叫做数据结构？试举一个简单的例子说明。答：数据结构是指相互之间存在一定关系的数据元素的集合。举例：一个成绩登记表中每个学生的学号，姓名，及成绩等信息是数据元素，每个学生则是一个数据对象，整个成绩表则是一个数据结构。4、 设有数据逻辑结构为：画出这个逻辑结构的示意图，并确定相对于关系R，哪些结点是开始结点，哪些是终端结点。K2K1K8K3K4K5K9K6K7K1，k2是开始结点；K6，k7是终端结点。5、随机产生n个整数，然后根据自顶向下，逐步求精的思想，一步一步用某个算法将它们从小到大排序。设定算法思路后设计并实现你的程序，给出你的算法思路与实现代码。思路提示： 实验思考题：考虑一个多叉路口，在这个路口中，共有五条道路相交，其中C和E是单行线，其他为双行线。任务是：为这个路口建立一个安全的交通信号灯管理的数学模型。答首先需要研究这个路口所有车辆的行驶路线中存在的冲突问题。 经过初步分析发现，这个问题可以归结为对车辆的可能行驶方向做某种分组，分组的结果要求：任一个组中各个方向行驶的车辆可以同时安全行驶而不发生碰撞。显然，对这个问题存在许多不同解决方案。也就是有许多可行约分组方案。最简单的方案就是把每个可能的行驶路线分为一组。但是，如果分组越少，可以同时行驶的车辆也就越多，从而使管理系统的效率就越高。根据这个路口的实际情况，可以确定13个可能通行的方向，A-B， A-C ，A-D ，B-A， B-C ，B-D ，D-A ，D-B， D-C ，E-A ，E-B ，E-C ，E-D。其中有些方向明显不能同时进行，如A-B 与B-C等。为了叙述方便，我们下面把A-B简写成AB，并用一个小椭圆的图把它框起来，看成一个结点；在不能同时行驶的路线间画一条连织(表示它们互相冲突)，便可以得到下图所示的网状图形。 经过上面分析，就可以把要解决的问题借助图的模型清楚而严格地表达出来。分析结果是把原来的一个实际(信号灯)问题转变成了另一个比较抽象问题。这个问题就是：要求将上图中 的结点分组，使有线相连（互相冲突)的结点不在同一个组里。实验作业题：1、 编程实现任意类型两个对象的值的交换。#includeusing namespace std;template class Swappublic:Swap();void change();private:T type1;T type2;template Swap:Swap()type1=0;type2=0;template void Swap:change()cintype1type2;T a;a=type1;type1=type2;type2=a;couttype1 type2endl;int main()Swap temp;temp.change();Swap temp1;temp1.change();Swap temp2;temp2.change();Swap temp3;temp3.change();return 0;2、 编程求解20000以内的回文数。#include using namespace std;int Ispalindrome(int n);int main()for(int i=0;i20000;i+)if(Ispalindrome(i)coutit;coutendl;return 0;int Ispalindrome(int n)int k,m=0;k=n;while(k)m=m*10+k%10;k=k/10;return (m=n);实验心得体会与总结： 数据结构这门学