数据结构实验二汇总
《数据结构》实验报告二
学校：班级：
学号：姓名：
日期：程序名：
一、上机实验的问题和要求：
单链表的查找、插入与删除。设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求：
1.从键盘输入20个整数，产生不带表头的单链表，并输入结点值。
2.从键盘输入1个整数，在单链表中查找该结点的位置。若找到，则显示“找到了”；否
则，则显示“找不到”。
3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插
入在对应位置上，输出单链表所有结点值，观察输出结果。
4.从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。
5.将单链表中值重复的结点删除，使所得的结果表中个结点值均不相同，输出单链表所有
结点值，观察输出结果。
6.删除其中所有数据值为偶数的结点，输出单链表所有结点值，观察输出结果。
7.把单链表变成带表头结点的循环链表，输出循环单链表所有结点值，观察输出结果。
8.（★）将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元
素，而B链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表A和单链表B的所有结点值，观察输出结果。
二、程序设计的基本思想，原理和算法描述：
（包括程序的结构，数据结构，输入/输出设计，符号名说明等）
这是一个带头结点的线性链表，数据域存放整形数据，由用户输入。头结点数据域存链表长度，所以程序中有个求链表长度的函数
int LengthList(LinkList L); //求链表长度
L是指向头结点的指针，将长度值存入语句为
L->data = LengthList(L);
为了实时观察链表情况，程序中有个输出链表数据的函数
void PrintList(LinkList L); //输出链表
程序可以实现8种不同的操作，这8种不同的操作由8个函数实现，分别是
void CreateList(LinkList &L); //创建链表
void Locate(LinkList L); //查询数值
void InsertList(LinkList &L); //插入数值
void DeleteList(LinkList &L); //选择删除
void Deleterepeat(LinkList &L); //删除重复结点
void DeleteEven(LinkList &L); //删除数值为偶数的结点
void Rotate(LinkList &L); //变为循环链表
void Divide(LinkList &L); //分解成两个链表
这些基本操作的实现算法都比较简单，有些跟书本上一样，有些需要自己稍作思考才能写出，具体程序见第三部分
8种不同的操作可以由用户通过按A-H这八个字母键来选择，分别是A:创建B:查询C:插入D:选择删除E:删除重复F:删除偶数G:变为循环链表H:分解为两个链表，见第四部分输出截图，可以清晰的看到整个过程
主程序中用开关语句实现:
char operate;
printf("\n\n输入字符选择链表操作类型\nA:创建B:查询C:插入D:选择删除E:删除重复F:删除偶数\nG:变为循环链表H:分解为两个链表\n");
scanf("%c",&operate);
switch (operate)
{
case 'a':
case 'A': CreateList(L);break;
case 'b':
case 'B': Locate(L);break;
case 'c':
case 'C': InsertList(L); break;
case 'd':
case 'D': DeleteList(L);break;
case 'e':
case 'E': Deleterepeat(L);break;
case 'f':
case 'F': DeleteEven(L);break;
case 'g':
case 'G': Rotate(L);break;
case 'h':
case 'H': Divide(L);break;
case '\n':goto label;
default: printf("输入有误，请重新输入！");break;
}
三、源程序及注释：
#include
#include
typedef struct LNode //链表结点
{
int data;
struct LNode *next;
}LNode,*LinkList;
int over_flag=0; //主函数结束标识符
void CreateList(LinkList &L); //创建链表
void Locate(LinkList L); //查询数值
void InsertList(LinkList &L); //插入数值
void DeleteList(LinkList &L); //选择删除
void Deleterepeat(LinkList &L); //删除重复结点
void DeleteEven(LinkList &L); //删除数值为偶数的结点
void Rotate(LinkList &L); //变为循环链表
void Divide(LinkList &L); //分解成两个链表
int LengthList(LinkList L); //求链表长度
void PrintList(LinkList L); //输出链表
/**********************************************************************
主函数
**********************************************************************/
void main(void)
{
char operate;
LinkList L;
int n;
for( n=0;n<40;n++)
{
printf("\n\n输入字符选择链表操作类型\nA:创建B:查询C:插入D:选择删除E:删除重复F:删除偶数\nG:变为循环链表H:分解为两个链表\n");
label:scanf("%c",&operate);
switch (operate)
{
case 'a':
case 'A': CreateList(L);break;
case 'b':
case 'B': Locate(L);break;
case 'c':
case 'C': InsertList(L); break;
case 'd':
case 'D': DeleteList(L);break;
case 'e':
case 'E': Deleterepeat(L);break;
case 'f':
case 'F': DeleteEven(L);break;
case 'g':
case 'G': Rotate(L);break;
case 'h':
case 'H': Divide(L);break;
case '\n':goto label; //排除换行键的影响
default: printf("输入有误，请重新输入！");break;
}
if(over_flag)return;
}
}
/**********************************************************************
创建链表
**********************************************************************/ void CreateList(LinkList &L)
{
int temp;
printf("创建链表：\n请输入创建链表所需的整数值(以-1结束):");
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
LinkList q=L;
scanf("%d",&temp);
while(temp!=-1)
{
LinkList p;
p = (LinkList)malloc(sizeof(LNode));
p->data = temp;
p->next = NULL;
q->next = p;
q = q->next;
scanf("%d",&temp);
}
L->data = LengthList(L);
PrintList(L);
}
/**********************************************************************
查询元素
**********************************************************************/ void Locate(LinkList L)
{ if(!L)printf("错误：链表未创建！");
int element;
printf("查询数值：\n输入要查询的数值：");
scanf("%d",&element);
LinkList p=L->next;
int i =1;
while(p)
{
if(p->data==element)
{
printf("找到了，它是链表的第%d个元素。\n",i);
return ;
}
p=p->next;
i++;
}
printf("找不到。\n");
}
/**********************************************************************
插入数值
**********************************************************************/ void InsertList(LinkList &L)
{
int x,i;
printf("插入数值：\n输入要插入的数值和插入的位置：");
scanf("%d",&x);
scanf("%d",&i);
LinkList p = L;
int j = 0;
while (p && j < i-1)
{
p = p->next;
++j;
}
if (!p || j > i-1)
{
printf("输入位置错误!") ;
return;
}
LinkList s = (LinkList)malloc(sizeof(LNode));
s->data = x;
s->next = p->next;
p->next = s;
L->data = LengthList(L);
PrintList(L);
}
/**********************************************************************
选择位置删除节点
**********************************************************************/ void DeleteList(LinkList &L)
{
int i;
LinkList p = L;
printf("选择位置删除结点：\n输入要删除数值的位置：");
scanf("%d",&i);
int j = 0;
while (p->next && j < i-1)
{
p = p->next;
++j;
}
if (!(p->next) || j > i-1)
{
printf("输入位置错误!") ;
return;
}
LinkList q = p->next;
p->next = q->next;
free(q);
L->data = LengthList(L);
PrintList(L);
}
/**********************************************************************
删除重复结点
**********************************************************************/ void Deleterepeat(LinkList &L)
{
printf("删除重复结点后的链表为：\n");
int n=1;
int a[20];
LinkList q=L->next;
LinkList p=q->next;
a[0]=q->data;
while(p)
{
for(int i=0;i { if(p->data==a[i]) { LinkList r=p; q->next=p->next; p=p->next; free(r); break; } } if(i==n) { a[n++]=p->data; p=p->next; q=q->next; } } L->data = LengthList(L); PrintList(L); } /********************************************************************** 删除数值为偶数的结点 **********************************************************************/ void DeleteEven(LinkList &L) { printf("删除偶数结点后的链表为：\n"); LinkList q=L; LinkList p=L->next; while(p) { if(p->data%2==0) { LinkList r=p; q->next=p->next; p=p->next; free(r); } else { p=p->next; q=q->next; } } L->data = LengthList(L); PrintList(L); } /********************************************************************** 变为循环链表 **********************************************************************/ void Rotate(LinkList &L) { printf("变为循环链表：\n"); LinkList p=L; while(p->next)p=p->next; p->next=L; LinkList t=L->next; printf("长度：%d\t",L->data); printf("各个结点数值为："); while(t!=L) { printf("%d\t",t->data); t=t->next; } printf("\n"); printf("已经变为循环链表，其他操作将受影响,程序结束！\n"); over_flag=1; } /********************************************************************** 分解成两个链表 **********************************************************************/ void Divide(LinkList &L) { printf("分解成两个链表：\n"); LinkList A=L; LinkList B=(LinkList)malloc(sizeof(LNode)); B->next=NULL; LinkList Lb=B; int i=1; LinkList La=L; LinkList p=L->next; while(p) { if(i++%2==0) { La->next=p->next; p->next=NULL; Lb->next=p; Lb=Lb->next; p=La->next; } else { p=p->next; La=La->next; } } A->data = LengthList(A); printf("链表A:"); PrintList(A); B->data = LengthList(B); printf("链表B:"); PrintList(B); printf("已经分解成两个链表，其他操作将受影响,程序结束！\n"); over_flag=1; } /********************************************************************** 求链表长度 **********************************************************************/ int LengthList(LinkList L) { int i=0; LinkList p=L->next; while(p) { p=p->next; i++; } return i; } /********************************************************************** 输出链表 **********************************************************************/ void PrintList(LinkList L) { LinkList t=L->next; printf("长度：%d\t",L->data); printf("结点数值："); while(t) { printf("%d\t",t->data); t=t->next; } printf("\n"); } 四、运行输出结果： 五、调试和运行程序过程中产生的问题及采取的措施： 1. 主程序中我用到char operate; scanf("%c",&operate); Operate存放用户选择操作类型的字母A-H，但是当用户键入字母后，要按ENTER 键表示输入完毕，所以以后执行scanf("%c",&operate);是会把ENTER输入到operate中，从而影响了后面的操作，解决方案是加一个标记位 label :scanf("%c",&operate); 当程序发现输入为ENTER时，回到labeL处，这样解决了问题。请看下面语句，注意case '\n':goto label; label : scanf("%c",&operate); switch (operate) { case 'a': case 'A': CreateList(L);break; case 'b': case 'B': Locate(L);break; case 'c': case 'C': InsertList(L); break; case 'd': case 'D': DeleteList(L);break; case 'e': case 'E': Deleterepeat(L);break; case 'f': case 'F': DeleteEven(L);break; case 'g': case 'G': Rotate(L);break; case 'h': case 'H': Divide(L);break; case '\n':goto label; //排除换行键的影响 default: printf("输入有误，请重新输入！");break; } 2、.最后两个操作 void Rotate(LinkList &L); //变为循环链表 void Divide(LinkList &L); //分解成两个链表 一旦执行，将破坏链表的结构，无法再进行其他操作，需要结束整个程序。而在Rotate 和Divide子程序中无法直接结束主函数，所以我设置了一个主函数结束标志位 int over_flag=0; //主函数结束标识符 初值为0，当它变为1时表示主函数需要结束 子函数中写 :void Rotate(LinkList &L) { .......... over_flag=1; } void Divide(LinkList &L) { ........... over_flag=1; } 主函数中写 void main (void) { .......... if(over_flag)return; } 六、对算法的程序的讨论、分析，改进设想，其它经验教训： 原来我写的程序是8个基本操作按顺序自动执行，后来听取其他同学的意见，设置不同的字母对应这些基本操作，由用户自己选择执行，这样就比原来的程序要灵活很多，也便于用户使用和观察。 在创建链表时，原来设计的是输入固定长度的链表，后来改进为由用户输入任意长度的数据，只需要用-1 表示结束即可。 七、对实验方式、组织、设备、题目的意见和建议： 这个试验题目还可以，基本涵盖了单链表所有的简单操作，只要能写完程序并顺利运行，也就掌握了单链表的相关知识内容。但是由于涵盖内容太多，课内无法完成，必须在课外花很多时间。所以我认为在上完这一章的内容后，老师就应该要求我们做这个程序，这样早点开始，做的时间长一些，效果更应该好一点。 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （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<<" 建立一个单链表"< 重庆文理学院软件工程学院实验报告册 专业：_____软件工程__ _ 班级：_____软件工程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 《数据结构实验》的实验题目及实验报告模板 实验一客房管理（链表实验） ●实现功能：采用结构化程序设计思想，编程实现客房管理程序的各个功能函数，从而熟练 掌握单链表的创建、输出、查找、修改、插入、删除、排序和复杂综合应用等操作的算法 实现。以带表头结点的单链表为存储结构，实现如下客房管理的设计要求。 ●实验机时：8 ●设计要求： #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、 采用表尾挂入法建立一个以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 南京工程学院实验报告 操作的函数程序清单，分别用顺序表和链表结构完成，并在首页上表明团队名称、成员及个人的工作（函数），未来的成绩评定时将包含这一部分的团队成绩及个人的工作成绩。 一、实验目的 1.熟悉上机环境，进一步掌握语言的结构特点。 2.掌握线性表的顺序存储结构的定义及实现。 3.掌握线性表的链式存储结构——单链表的定义及实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、程序主要语句及作用（main函数程序清单） 程序1的主要代码(附简要注释) #include 实验报告 学院（系）名称：计算机科学与工程学院姓名 赵振宇学号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可能早已建好。数据结构实验报告格式
(完整版)数据结构实验报告全集
数据结构实验答案1
数据结构实验报告
数据结构实验二11180
数据结构实验报告图实验
数据结构实验二
数据结构实验报告模板
数据结构实验报告2
数据结构实验报告
《数据结构实验》实验题目及实验报告模板
数据结构实验二-
数据结构实验二链表
数据结构实验报告及心得体会
《数据结构》实验报告
数据结构实验报告
数据结构实验二