数据结构实验报告
实验名称：实验二——栈与队列
学生姓名：大学霸
班级：xxxxxxxxxx
班内序号：19
学号：xxxxxxxxxx
日期：2012年11月17日
1．实验要求
a. 实验目的
通过选择下面五个题目之一进行实现，掌握如下内容：
进一步掌握指针、模板类、异常处理的使用
掌握栈的操作的实现方法
掌握队列的操作的实现方法
学习使用栈解决实际问题的能力
学习使用队列解决实际问题的能力
b. 实验内容
利用栈结构实现迷宫求解问题。迷宫求解问题如下：
心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶
2. 程序分析
本程序的功能是用递归的方法找到所有走出迷宫的路径，并将路径输出，同时在这些路径中找出最优解。
首先，读取后台预定的迷宫TXT地图（实际上是10×10的数字矩阵，0代表空地，3代表墙，可以很直观地修改）,把数据赋给arr二维数组，内容不发生改变。
然后，将这个迷宫地图输出，判断迷宫是否有完整通路，如果能走出便进行下一步，如果不能，提示错误
迷宫有完整通路，可使用回溯的方法，即从入口出发，顺着某一个方向进行探索，若能走通，则此步进栈，继续往前进；否则沿着原路返回，换另一个方向探索，直至出口位置，求得一条通路……重复上述步骤，找出所有可能的路径，统计每一步
在程序的最后，将每一种路径的长度进行比较，找出最短的一个或多个路径
2.1 存储结构
定义结点的结构体
struct Point
{
int X;
int Y;
};
进行前进后退等操作时即是对X、Y值的改变，同时也代表二维数组元素的行数、列数
迷宫图的数据用二维数组来存储，用0表示空地可以前进，用3表示墙走不通
当执行寻找路径时，从一个节点到下一个结点系统会自动调用栈
2.2 关键算法分析
关键算法
1.找出迷宫走法
回溯法，利用递归穷举可能解
每走一步：
[1] 如果当前位置=出口，把完整路径输出，结束
[2] 否则：
[2.1] 假设当前位置为路径；
[2.2] 如果东面未走过：向东走一步
[2.3] 如果南面未走过：向南走一步
[2.4] 如果西面未走过：向西走一步
[2.5] 如果北面未走过：向北走一步
[3] 设置当前位置走不通，回溯，并将此位置标记
2.读取迷宫图
[1] 进行循环体
[1.1] 输入要读取的迷宫图maze
[1.2] 如果存在跳出循环，下一环节
[1.3 ]如果不存在显示错误
输入的迷宫图有误，重新上面的步骤
[2] 定义文件流对象fin
[3] 根据maze选择打开不同的迷宫图TXT文件，建立关联
[4] 判断文件是否能打开
[4.1] 如果能打开，逐行提取数字，赋给二维数组arr，关闭文件
[4.2] 如果不能打开，提示错误
3.打印还未走过的迷宫图
[1] 从第一行到第十行循环
[2] 从第一列到第十列循环
[2.1] 此节点如果为墙，打印“■”
[2.2]其他为空地，打印空格
4.判断是否能走通
[1] 从最后一行倒序循环
[1.1] 如果找到不是墙的元素，返回能走通
[2]从最后一列倒序循环
[2.1] 如果找到不是墙的元素，返回能走通
[3] 返回不能走通
5.打印走通后的迷宫图
[1] 将路径计数器k置0
[2] 从第一行到第十行循环
[2.1] 从第一列到第十列循环
[2.1.1] 此节点如果为墙，打印“■”
[2.1.2] 此节点如果为路径，打印“*”，k加1
[2.1.3] 此节点如果未走过，打印空格
[3] 将k存到向量PathLength（专门比较路径长度）
打印一共走了k步
6.找出最优解
[1] 定义最短路径数组ShortestPath
假设最短路径长度ShortestLength为向量PathLength的第一个元素值[2] 在向量PathLength里进行循环
[2.1] 如果PathLength里某个元素值小于最短路径长度ShortestLength
[2.2] 将最小路径长度ShortestLength等于这个元素值
[3] 在向量PathLength里进行循环
[3.1] 如果PathLength里某个元素值等于最短路径长度ShortestLength
[3.2]将这个元素的下标存入最短路径数组ShortestPath
[4] 打印最短路径数组ShortestPath里的所有元素，即为最优解
[5] 打印最短路径长度ShortestLength
代码详尽分析
1.找出迷宫走法
每走一步：
[1] 如果当前位置=出口，把完整路径输出，结束
[2] 否则：
[2.1] 假设当前位置为路径；
[2.2] 如果东面未走过：向东走一步
[2.3] 如果南面未走过：向南走一步
[2.4] 如果西面未走过：向西走一步
[2.5] 如果北面未走过：向北走一步
[3] 设置当前位置走不通，回溯，并将此位置标记
C++实现
void next(int arr[][10],Point cur)
{
[1] if(cur.X == 9 || cur.Y == 9) //如果走出迷宫
{ cout<<"第"<<++Path<<"种路径：\n"; PrintPath(arr); arr[cur.X][cur.Y] = 0;} //打印完整路径
[2] else
{
[2.1] arr[cur.X][cur.Y] = 2;//假设当前位置为路径
[2.2] if (arr[cur.X+1][cur.Y] ==0)
{
Point t=cur; t.X++; next(arr,t);//向右}
[2.3] if (arr[cur.X][cur.Y+1] ==0)
{
Point t=cur; t.Y++; next(arr,t);//向下}
[2.4] if (arr[cur.X-1][cur.Y] ==0)
{
Point t=cur; t.X--; next(arr,t);//向左}
[2.5] if (arr[cur.X][cur.Y-1] ==0)
{
Point t=cur; t.Y--; next(arr,t);//向上}
[3] arr[cur.X][cur.Y] = 1; // 标记此处走不通
}
arr[cur.X][cur.Y]=0;
}
2.读取迷宫图
[1] 进行循环体
[1.1] 输入要读取的迷宫图maze
[1.2] 如果存在跳出循环，下一环节
[1.3 ]如果不存在显示错误
输入的迷宫图有误，重新上面的步骤
[2] 定义文件流对象fin
[3] 根据maze选择打开不同的迷宫图TXT文件，建立关联
[4] 判断文件是否能打开
[4.1] 如果能打开，逐行提取数字，赋给二维数组arr，关闭文件
[4.2] 如果不能打开，提示错误
C++实现
[1]do{
cout<<"请选择迷宫(1~5): ";
[1.1] cin>>maze;// 输入要读取的迷宫图maze
[1.2] if(maze>=1&&maze<=5) break;// 如果存在跳出循环，下一环节[1.3] else cout<<"无此迷宫！"< while(1); [2] ifstream fin;// 定义文件流对象fin [3] switch (maze)// 根据maze选择打开不同的迷宫图TXT文件，建立关联 { case 1: fin.open("maze1.txt"); break; case 2: fin.open("maze2.txt"); break; case 3: fin.open("maze3.txt"); break; case 4: fin.open("maze4.txt"); break; case 5: fin.open("maze5.txt"); break; default: break; } //输出迷宫 [4] if(fin.is_open())//判断文件是否能打开 { cout<<"迷宫载入中...."< [4.1] for (int i=0;i<10;i++) { for (int j=0;j<10;j++) { fin>>arr[i][j];// 逐行提取数字，赋给二维数组arr } } fin.close(); PrintMaze(arr); } else [4.2] cout<<" 迷宫不能打开！"< 3. 打印还未走过的迷宫图 [1] 从第一行到第十行循环 [2] 从第一列到第十列循环 [2.1] 此节点如果为墙，打印“■” [2.2]其他为空地，打印空格 C++实现 void PrintMaze(int arr[][10]) { [1] for (int i=0;i<10;i++) { [2] for (int j=0;j<10;j++) { [2.1] if (arr[i][j]==3) cout<<"■";//此节点如果为墙，打印“■” [2.2] else cout<<" ";//其他为空地，打印空格 } cout< } cout< } 4.判断是否能走通 [1] 从最后一行倒序循环 [1.1] 如果找到不是墙的元素，返回能走通 [2]从最后一列倒序循环 [2.1] 如果找到不是墙的元素，返回能走通 [3] 返回不能走通 C++实现 bool IsThrough(int arr[][10]) { [1] for(int i=8;i>=1;i--) { [1.1] if(arr[9][i]==0) return true;// 如果找到不是墙的元素，返回能走通 } [2] for(int i=8;i>=1;i--) { [2.1] if(arr[i][9]==0) return true;// 如果找到不是墙的元素，返回能走通 } [3] return false; } 5.打印走通后的迷宫图 [1] 将路径计数器k置0 [2] 从第一行到第十行循环 [2.1] 从第一列到第十列循环 [2.1.1] 此节点如果为墙，打印“■” [2.1.2] 此节点如果为路径，打印“*”，k加1 [2.1.3] 此节点如果未走过，打印空格 [3] 将k存到向量PathLength（专门比较路径长度） [4] 打印“一共走了k步” C++实现 void PrintPath(int arr[][10]) { [1] int k=0; [2] for (int i=0;i<10;i++)//行循环 { [2.1] for (int j=0;j<10;j++)//列循环 { [2.1.1] if (arr[i][j]==3) cout<<"■";//此节点如果为墙，打印“■” [2.1.2] else if (arr[i][j]==2){ cout<<" *";k++;}//此节点如果为路径，打印“*”，k加1 [2.1.3] else cout<<" ";//此节点如果未走过，打印空格 } cout< } [3] PathLength.push_back(k);//插入路径长度向量 [4] cout<<"一共走了"< cout< } 6.找出最优解 [1] 定义最短路径数组ShortestPath 假设最短路径长度ShortestLength为向量PathLength的第一个元素值 [2] 在向量PathLength里进行循环 [2.1] 如果PathLength里某个元素值小于最短路径长度ShortestLength [2.1.1] 将最小路径长度ShortestLength等于这个元素值 [3] 在向量PathLength里进行循环 [3.1] 如果PathLength里某个元素值等于最短路径长度ShortestLength [3.1.1]将这个元素的下标存入最短路径数组ShortestPath [4] 打印最短路径数组ShortestPath里的所有元素，即为最优解 [5] 打印最短路径长度ShortestLength C++实现 void PrintShortest() { [1] int ShortestPath[50]={0}; int ShortestLength=PathLength[0]; ShortestPath[0]=1; [2] for(unsigned i=1;i { [2.1] if(PathLength[i] { [2.1.1] ShortestLength=PathLength[i]; } } int k=0; [3] for(unsigned i=0;i { [3.1] if(PathLength[i]==ShortestLength) [3.1.1] ShortestPath[k++]=i+1; } cout<<"最短路径为："; [4] for(int i=0;i<50;i++) if(ShortestPath[i]) cout< cout< [5] cout<<"共走了"< } 2.3 其他 我在调试程序时，已经预写了几个迷宫地图文件maze1.txt、maze2.txt……保存在工程文件夹下。类似的，其他开发者可以编写新的地图，加以改进、创新 3. 程序运行结果 3.1测试主函数流程图 3.2 运行截图 打开迷宫并打印 迷宫不存在 输出所有参考路径 找出最优解 3.时间复杂度 最不理想的情况即二维数组每个元素都向四个方向探索一遍，假设迷宫大小为N ×N，时间复杂度o(4n2)即o(n2) 在此10×10迷宫为o(1) 4. 总结 第三章介绍了堆栈与队列这两种受限制的线性结构。其基本算法与顺序表和链表运算方法相同，不同的是堆栈遵循“先进后出”的规则，在这个小实验中，递归函数的调用用到了栈，系统在栈空间中为函数建立工作记录，存储递归函数断点位置，当被调函数执行完成时，系统从其工作记录中取出断点位置，并将此工作记录退栈，回到主调函数的断点处继续进行。编写这一程序让我更加深了系统调用栈的原理。 最初编程时想的是在程序中就把这个二维数组写好，后来联想到可以使用文件流，在使用时就读取这个文件，等于是为用户增加了一个外部接口，用户可以在外部就自己编写迷宫。在学习栈的机制时又同时复习了文件流输入。 这次编程过程中发现想好每一个模块的功能后很容易写出来，但是把这些连接起来花了我一些功夫，就像数据结构老师所说过的，有时写语句不是很难，有时候难的是把架子搭起来。这次是很有体会，觉得还是自己在编程的过程中要注意每一个部分的有机组合，整个程序才能完整运行 由于这周临近期末，只是编写了利用递归函数走迷宫，也没来得及实现用书上介绍的栈即非递归的方法来实现，比较可惜。下一步我将考虑把这个问题用STL中的STACK栈来解决 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时） 数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"< 数据结构实验报告 姓名：班级： 学号： 日期：2015年9月27日 上机环境：win7系统，mircosoft visual++ 1．实验名称：线性表 2．实验题目 编写一个程序algo2-1.cpp，实现顺序表的各种基本运算（假设顺序表的元素类型为char）并在此基础上设计一个主程序完成如下功能： (1)初始化顺序表L； (2)依次采用尾插入法插入a,b,c,d,e元素； (3)输出顺序表L； (4)输出顺序表L的长度； (5)判断顺序表L是否为空； (6)输出顺序表L的第3个元素； (7)输出元素a的位置； (8)在第4个元素位置上插入f元素； (9)输出顺序表L； (10)删除L的第3个元素； (11)输出顺序表L； (12)释放顺序表。 3．实验程序 #include typedef char ElemType; typedef struct { ElemType data[MaxSize]; int length; }SqList; void InitList(SqList *&L) { L= (SqList *)malloc(sizeof(SqList));//分配存放线性表的空间L->length=0;//置空线性表长度为0 } void DestroyList(SqList *L) { free(L); } bool ListEmpty(SqList *L) { return(L->length==0); } int ListLength(SqList *L) { return(L->length); } 重庆文理学院软件工程学院实验报告册 专业：_____软件工程__ _ 班级：_____软件工程2班__ _ 学号：_____201258014054 ___ 姓名：_____周贵宇___________ 课程名称：___ 数据结构 _ 指导教师：_____胡章平__________ 2013年 06 月 25 日 实验序号 1 实验名称实验一线性表基本操作实验地点S-C1303 实验日期2013年04月22日 实验内容1.编程实现在顺序存储的有序表中插入一个元素（数据类型为整型）。 2.编程实现把顺序表中从i个元素开始的k个元素删除（数据类型为整型）。 3.编程序实现将单链表的数据逆置，即将原表的数据（a1,a2….an）变成 (an,…..a2,a1)。（单链表的数据域数据类型为一结构体，包括学生的部分信息：学号，姓名，年龄） 实验过程及步骤1. #include { ElemType elem[MAXSIZE]; /*线性表占用的数组空间*/ int last; /*记录线性表中最后一个元素在数组elem[ ]中的位置（下标值），空表置为-1*/ }SeqList; #include "common.h" #include "seqlist.h" void px(SeqList *A,int j); void main() { SeqList *l; int p,q,r; int i; l=(SeqList*)malloc(sizeof(SeqList)); printf("请输入线性表的长度:"); scanf("%d",&r); l->last = r-1; printf("请输入线性表的各元素值:\n"); for(i=0; i<=l->last; i++) { scanf("%d",&l->elem[i]); } px(l,i); printf("请输入要插入的值:\n"); 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 理工学院实验报告 系部计算机系班级学号 课程名称数据结构实验日期 实验名称链表的基本操作成绩 实验目的： （1）掌握线性表的链式存储结构的特点； （2）掌握线性表的基本操作：初始化、插入、删除、查找数据元素等运算在链式存储结构上的实现。 实验条件：计算机一台，vc++6.0 实验容与算法思想： 容： 建立一有序的链表，实现下列操作： 1.把元素x插入表中并保持链表的有序性； 2.查找值为x的元素，若找到将其删除； 3.输出表中各元素的值。 算法思想：先创建并初始化一个顺序表（void init_linklist(LinkList)），通过循环，输入一串数据void CreateFromTail(LinkList L);创建主函数；编写算法，完成子函数（查找locate，插入insList，删除DelList，输出output）模块；调用子函数，完成实验要求 运行结果： 附：源程序： #include 图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template #include 洛阳理工学院实验报告 系部计算机系班级学号姓名 课程名称数据结构实验日期 实验名称链表的基本操作成绩 实验目的： （1）掌握线性表的链式存储结构的特点； （2）掌握线性表的基本操作：初始化、插入、删除、查找数据元素等运算在链式存储结构上的实现。 实验条件：计算机一台，vc++6.0 实验内容与算法思想： 内容： 建立一有序的链表，实现下列操作： 1.把元素x插入表中并保持链表的有序性； 2.查找值为x的元素，若找到将其删除； 3.输出表中各元素的值。 算法思想：先创建并初始化一个顺序表（void init_linklist(LinkList)），通过循环，输入一串数据void CreateFromTail(LinkList L);创建主函数；编写算法，完成子函数（查找locate，插入insList，删除DelList，输出output）模块；调用子函数，完成实验要求 运行结果： 附：源程序： #include 2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList [内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template 数据结构实验报告 二．程序设计相关信息 （1）实验题目：编写一个程序algo2-3.cpp，实现双链表的各种基本运算，并在此基础上设计一个主程序完成如下功能： 1.初始化双链表h； 2.依次采用尾插法插入a，b，c，d，e元素； 3.输出双链表h； 4.输出双链表h长度； 5.输出双链表h是否为空； 6.判断双链表h的第3个元素； 7.输出元素‘a’的位置； 8.在第4个元素位置上插入‘f’元素； 9.输出双链表h； 10.删除L的第3个元素； 11.输出双链表h； 12.释放双链表h。 （2）实验目的：熟悉双链表的基本操作并掌握尾插法建表。 （3）算法描述或流程图 (4)源代码 #include typedef struct DNode { char data; struct DNode *next; struct DNode *prior; }DNode,DLinkList; void initlist(DLinkList *&h) { h=(DLinkList*)malloc(sizeof(DLinkList)) ; h->next=NULL; h->prior=NULL; } void destroylist(DLinkList *&h) { DLinkList *p=h,*q=p->next; while(q!=NULL) {free(p); p=q; q=p->next; } free(p); } int getelem(DLinkList *h,int i,char &e) {int j=0; DLinkList *p=h; while(j 姓名： 学号： 班级： 2010年12月15日 实验一线性表的应用 【实验目的】 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。、； 2、以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点； 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现； 4、通过本章实验帮助学生加深对C语言的使用（特别是函数的参数调用、指针类型的 应用和链表的建立等各种基本操作）。 【实验内容】 约瑟夫问题的实现：n只猴子要选猴王，所有的猴子按1,2，…，n编号围坐一圈，从第一号开始按1,2…，m报数，凡报到m号的猴子退出圈外，如此次循环报数，知道圈内剩下一只猴子时，这个猴子就是猴王。编写一个程序实现上述过程，n和m由键盘输入。【实验要求】 1、要求用顺序表和链表分别实现约瑟夫问题。 2、独立完成，严禁抄袭。 3、上的实验报告有如下部分组成： ①实验名称 ②实验目的 ③实验内容：问题描述：数据描述：算法描述：程序清单：测试数据 算法： #include 实 验 报 告 一、实验目的 1) 加深对图的表示法和图的基本操作的理解，并可初步使用及操作； 2) 掌握用图对实际问题进行抽象的方法，可以解决基本的问题； 3) 掌握利用邻接表求解非负权值、单源最短路径的方法，即利用Dijkstra 算法求最短 路径，同时掌握邻接表的建立以及使用方法，能够解决相关的问题； 4) 学会使用STL 中的map 抽象实际问题，掌握map ，List,，priority_queue 等的应 用。 二、实验内容与实验步骤 （1） 实验内容： 使用图这种抽象的数据结构存储模拟的欧洲铁路路线图，通过Dijkstra 算法求出欧洲旅行最少花费的路线。该实验应用Dijkstra 算法求得任意两个城市之间的最少路费，并给出路费最少的路径的长度和所经过的城市名。 （2） 抽象数据类型及设计函数描述 1) 抽象数据类型 class City ： 维护一个城市的信息，包括城市名name ，是否被访问过的标记visted ，从某个城市到达该城市所需的总费用total_fee 和总路径长度total_distance ，求得最短路径后路径中到达该城市的城市名from_city 。 class RailSystem ： 用邻接表模拟欧洲铁路系统，该邻接表使用数据结构map 实现，map 的key-value 课程名称：数据结构 班级： 实验成绩： 实验名称：欧洲旅行 学号： 批阅教师签字： 实验编号：实验二 姓名： 实验日期：2013 年6 月 18 日 指导教师： 组号： 实验时间： 值对的数据类型分别为string和list<*Service>，对应出发城市名和该城市与它能 够到达的城市之间的Service链表。 class Service： 为铁路系统模拟了两个城市之间的直接路线，包括两个城市之间直接到达的费用 fee，两城市之间的直接距离distance。 部分设计函数描述 ●RailSystem(const string& filename) 构造函数，调用load_services(string const &filename)函数读取数据 ●load_services(string const &filename) 读取传入的文件中的数据并建立上述两个map以模拟欧洲铁路路线图 ●reset(void) 遍历cities图，初始化所有城市的信息：visted未访问，total_distance最大 值，total_fee费用最大值，from_city为空 ●~RailSystem(void) 析构函数，用delete将两个map中所有使用new操作符开辟的空间删除 ●void output_cheapest_route(const string& from, const string& to, ostream& out); 输出两城市间的最少费用的路径，调用calc_route(string from, string to)函 数计算最少费用 ●calc_route(string from, string to) 使用Dijkstra算法计算from和to两个城市间的最少费用的路径 （3）采用的存储结构 1)map 实验目的 （1）学会用先序创建一棵二叉树。 （2）学会采用递归算法对二叉树进行先序、中序、后序遍历。 （3）学会打印输出二叉树的遍历结果。 实验内容 【问题描述】建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。 【基本要求】 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。 【测试数据】 ABCффDEфGффFффф(其中ф表示空格字符) 则输出结果为先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA 【选作内容】 采用非递归算法实现二叉树遍历。 实验步骤 （一）需求分析 1、在这个过程中，接受遍历的二叉树是从键盘接受输入（先序），以二叉链表作为存储结构，建立的二叉树。因此，首先要创建一棵二叉树，而这棵二叉树是先序二叉树。本演示程序中，集合的元素设定为大写字母ABCDEFG，输出的先序，中序，后序遍历分别为ABCDEGF,CBEGDFA,CGBFDBA。二叉树可以表示为： 接受的输入数据在进行递归的先序，中序，后序遍历后，分别将结果打印出来。 2、在程序运行的过程中可以看到，以计算机提示用户执行的方式进行下去，即在计算机终端上提示“输入二叉树的先序序列”后，由用户在键盘上输入ABC##DE#G##F###，之后相应的选择遍历及遍历结果显示出来。 3、程序执行的命令包括：首先是二叉树的先序序列被创建输入，其次是对输入进去的先序序列有次序的进行先序，中序，后序遍历。最后是打印出二叉树的遍历结果。 4、测试数据 （1）在键盘上输入的先序序列ABC##DE#G##F### （2）先序遍历结果ABCDEGF 云南大学数学与统计学实验教学中心 实 验 报 告 一、实验目的： 通过实验掌握线性链表的建立及基本操作，巩固课堂内容，练习其程序的设计与实现。 由于顺序存储结构的操作相对比较简单，而且在前期课程《高级语言程序设计》中使用得也多， 所以本次实验侧重于对线性链表存储结构上的操作及应用的实现。 二、实验内容： 本实验包含以下几个子问题： 1、 采用表尾挂入法建立一个以LA 为头指针的单链表： 2、 3、 就地逆转以LB 为头指针的单链表，即得到如下形式的单链表： 4、 将逆转后的LB 表接到LA 表之尾并构成循环链： LA 二、实验要求： 1. 每一个子问题用一个C 语言的函数来完成。 2. 对每一个子问题的结果用一个打印函数输出其结果以验证程序运行是否正确。 打印函数必须是公共的，即：用一个输出函数，既可以对单链表又可对循环链表实现， 打印输出。 3.用主函数调用各个子函数，以完成题目要求。 4.程序设计时应尽量考虑通用性，若改变题给数据仍能实现要求。 [实现提示]： ．第3小题题中的“就地逆转”即只允许引入除LB外的两个工作指针来实现。 即可以以循环方式从链表首部起逐个地修改各个结点的指针：从NEXT（向后）指针改变为PRIOR（向前）的指针，并注意保存搜索时的指针。 三、实验环境 Windows win7 程序设计语言C 四、实验过程（请学生认真填写）： 1. 实验设计的（各）流程图： 2. 程序设计的代码及解释（必须给出）： /*----------------------------------LinkList-------------------------------------*/ /*基本要求---------------------------------------------------------------------*/ /*采用表尾挂入法建立一个以LA为头指针的单链表--------------*/ /*采用表首插入法建立一个以LB为头指针的单链表.---------------*/ /*就地逆转以LB为头指针的单链表，即得到如下形式的单链表.*/ /*将逆转后的LB表接到LA表之尾并构成循环链-------------------*/ /*每一个子问题用一个C语言的函数来完成--------------------------*/ /* 打印函数必须是公共的-------------------------------------------------*/ /*-------------------------------------Start-------------------------------------*/ /*--------------------------------------------------------------------------------*/ #include 2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨 实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。 三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 《数据结构》实验报告 实验序号：4 实验项目名称：栈的操作 附源程序清单： 1. #include { return false; } else { st->top++; //移动栈顶位置 st->data[st->top]=x; //元素进栈 } return true; } bool Pop(SqStack *st,ElemType &e) //出栈 { if(st->top==-1) { return false; } else { e=st->data[st->top]; //元素出栈 st->top--; //移动栈顶位置} return true; } //函数名：Pushs //功能：数组入栈 //参数：st栈名,a->数组名，i->数组个数 bool Pushs(SqStack *st,ElemType *a,int i) { int n=0; for(;n 实验报告 学院（系）名称：计算机科学与工程学院姓名 赵振宇学号20175302专业计算机科学与技术班级2017级4班 实验项目实验二：二叉树的操作课程名称数据结构与算法 课程代码0661913实验时间 2019年5月21日第3、4节实验地点7-219考核 标准 实验过程25分程序运行20分回答问题15分实验报告30分特色功能5分考勤违纪情况5分成绩成绩 栏其它批改意见: 教师签字：考核 内容评价在实验课堂中的表现，包括实验态度、编 写程序过程 等内容等。□功能完善,□功能不全□有小错□无法运行○正确○基本正确○有提示○无法回答○完整○较完整○一般○内容极少 ○无报告○有○无○有 ○无一、实验目的 实验目的：通过实验使学生深刻理解二叉树性质，验证二叉树的遍历算法，并能在遍历算法基础上实现较复杂算法设计。 二、实验题目与要求 要求：第1题必做，2-5题中至少选择1题。 1.以二叉链表为存储结构，实现二叉树的创建、遍历 1）问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能： 1…建立树 2…前序遍历树 3…中序(非递归)遍历树 4…后序遍历树 0…结束 2）实验要求：在程序中定义下述函数，并实现要求的函数功能： CreateTree()：按从键盘输入的前序序列，创建树 PreOrderTree()：前序遍历树（递归） InOrderTree()：中序(非递归)遍历树 LaOrderTree():后序遍历树（递归） 3）注意问题: ?注意理解递归算法的执行步骤。 ?注意字符类型数据在输入时的处理。 ?重点理解如何利用栈结构实现非递归算法 2.在二叉树中，P所指结点为二叉树中任一给定的结点，编写算法求从根结点到P所指结点之间的路径。 1）实验要求：以二叉链表作为存储结构 2）实验提示：采用非递归后序遍历二叉树，当后序遍历访问到P所指结点时，此时栈中所有结点均为P所指结点的祖先，由这些祖先便构成了一条从根结点到P所指结点之间的路径。 3.试编写按层次顺序遍历二叉树的算法 1）问题描述：编写按层次顺序遍历二叉树的算法 2）实验要求：以二叉链表作为存储结构 4.编写算法求二叉树高度及宽度。 1）问题描述：二叉树高度是指树中所有节点的最大层数，二叉树宽度是指在二叉树的各层上，具有节点数最多的那一层上的节点总数。 2）实验要求：以二叉链表作为存储结构 5.实现一个哈夫曼编/译码系统 1）问题描述：利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码。对于双工信道，每端都需要一个完整的编码/译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。 2）实验要求：一个完整的系统应具有以下功能： (1)I：初始化(Initialization)。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。 (2)E：编码(Encoding)。利用已建好的哈夫曼树对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 (3)D：译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 (4)P：打印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。 (5)T：打印哈夫曼树(Tree printing)。将已在内存中的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。 3)实现提示： (1)文件CodeFile的基类型可以设为字节型。 (2)用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“E”为止。 (3)在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。数据结构实验报告格式
(完整版)数据结构实验报告全集
数据结构实验报告(2)
数据结构实验答案1
数据结构实验报告
数据结构实验二11180
数据结构实验报告图实验
数据结构实验二
数据结构实验报告模板
数据结构实验报告2
数据结构实验报告
数据结构实验二-
数据结构实验报告.
数据结构实验二链表
数据结构实验报告及心得体会
《数据结构》实验报告
数据结构实验二
相关主题
文本预览