数据结构实验报告(实验3,实验4)
肇庆学院计算机学院/软件学院
实验报告
专业15物联网工程班级1班姓名林忠杰学号201524134151 课程名称数据结构
学年2015—2016 学期1 / 2□课程类别专业必修 限选□任选□实践□
评分：批阅老师：2016年12 月 6 日
实验3 栈的基本操作
●实验目的
（1）熟悉栈的定义和栈的基本操作。
（2）掌握顺序存储栈和链接存储栈的基本运算。
（3）加深对栈结构的理解，逐步培养解决实际问题的编程能力。
●实验内容
（一）基础题
（1）编写栈的基本操作函数。
（2）调用栈的基本操作函数完成栈的基本操作：建立栈、读取栈顶函数、从栈中删除元素、输出栈中的所有元素。
（二）提高题
编写一个判定表达式中的括号是否正确匹配的函数。
●实验结果
1、基础题
（1）画出数据结构基本运算的流程图
（2）程序运行主要结果截图
测试用例：依次输入元素34，43，56，45进栈，程序运行结果如下图
测试用例：让元素45,56出栈，程序运行结果如下图
（3）程序源代码
#include
#define max 10
int push(int *stack,int maxn,int *toppt,int x)
{
if(*toppt>=maxn)
return 1;
stack[*toppt]=x;
++(*toppt);
return 0;
}
int pop(int *stack,int *toppt,int *cp)
{
if(toppt==0)
return 1;
--(*toppt);
*cp=stack[*toppt];
return 0;
}
void OutputStack(int *stack,int toppt)
{
int i;
for(i=toppt-1;i>=0;i--)
printf("%d ",stack[i]);
printf("\n");
}
void main()
{
int s[max],i;
int top=0;
int op;
while(1)
{
printf("请选择操作，1:进栈；2:出栈；0:退出\n");
fflush(stdin);
scanf("%d",&op);
switch(op)
{
case 0: return;
case 1:
printf("请输入进栈元素：");
scanf("%d",&i);
if(push(s,max,&top,i)==0)
{
printf("进栈成功，栈内元素为：\n");
OutputStack(s,top);
}
else
printf("栈满\n");
break;
case 2:
if(pop(s,&top,&i)==0)
{
printf("出栈元素为：[%d],栈内元素为：\n",i);
OutputStack(s,top);
}
else
printf("栈空\n");
break;
}
}
}
2、提高题
（1）画出数据结构基本运算的流程图
（2）程序运行主要结果截图
测试用例：输入表达式([][](())) ，程序运行结果如图
测试用例：输入表达式[][[]() ，程序运行结果如图
（3）程序源代码
#include
#include
#include
#define MAX 100
int push(int *stack,int maxn,int *toppt,char x) {
if(*toppt>=maxn)
return 1;
stack[*toppt]=x;
++(*toppt);
return 0;
}
int pop(int *stack,int *toppt,char *cp)
{
if(toppt==0)
return 1;
--(*toppt);
*cp=stack[*toppt];
return 0;
}
int correct(char *exp,int max)
{
int flag=0;
char s[MAX];
int top=0;
char c;int i;
for(i=0;i<=max&&flag==0;i++)
{
if(exp[i]=='('||exp[i]=='['||exp=='{')
push(s,MAX,&top,exp[i]);
if(exp[i]==')'||exp[i]==']'||exp[i]=='}')
{
flag=pop(s,&top,&c);
if((exp[i]==')'&&c!='(')||(exp[i]==']'&&c!='[')||(exp[i]=='}'&&c!='{'))
flag=1;
}
}
if(top!=0)
flag=1;
return flag;
}
void main()
{
char exp[1024];
int top=0;
while(1)
{
printf("请输入表达式，输入0 结束程序：\n");
gets(exp);exp[MAX]='\0';
if(strcmp(exp,"0")==0)
return;
if(correct(exp,strlen(exp))!=0)
printf("表达式括号不匹配\n");
else
printf("表达式括号匹配\n");
}
}
实验4队列的基本操作
●实验目的
（1）掌握链接存储队列的进队和出队等基本操作。
（2）掌握环形队列的进队和出队等基本操作。
（3）加深对队列结构的理解，逐步培养解决实际问题的编程能力。
●实验内容
（一）基础题1
（1）编写链接队列的基本操作函数。
（2）调用上述函数实现下列操作：建立队列、读取队列的第一个元素、从队列中删除元素、输出队列中的所有元素。
（二）基础题2
（1）编写环形队列的基本操作函数。
（2）调用上述函数完成下列操作：建立队列、读取队列的第一个元素、从队列中删除元素、输出队列中的所有元素。
（三）提高题
使用队列结构对医务室事件进行模拟，输出医生的总等待时间和病人的平均等待时间。
●实验结果
1、基础题1
（1）画出数据结构基本运算的流程图
（2）程序运行主要结果截图
测试用例：依次输入元素23,34,43,56,45进入队列，程序运行结果如图
测试用例：让元素23,34出队，程序运行结果如图
（3）程序源代码
#include
#include
typedef struct queue{
int data;
struct queue *link;
}Q;
void EnQueue(Q **head,Q **tail,int x)
{
Q *p;
p=(Q *)malloc(sizeof(Q));
p->data=x;
p->link=NULL;
if(*head==NULL)
*head=*tail=p;
else
{
(*tail)->link=p;
*tail=p;
}
}
int DeQueue(Q **head,Q **hail,int *cp)
{
Q *p;
p=*head;
if(*head==NULL)
return 1;
*cp=(*head)->data;
*head=(*head)->link;
if(*head==NULL)
*hail=NULL;
free(p);
return 0;
}
void OutputQueue(Q *head)
{
while(head!=NULL)
{
printf("%d ",head->data);
head=head->link;
}
printf("\n");
}
int main()
{
Q *head,*tail;
int op,i;
head=tail=NULL;
while(1)
{
printf("请选择操作，1:进队；2:出队；0:退出\n");
fflush(stdin);
scanf("%d",&op);
switch(op)
{
case 0:return 0;
case 1:
printf("\n请输入进队元素：");
scanf("%d",&i);
EnQueue(&head,&tail,i);
printf("队内元素为：");
OutputQueue(head);printf("\n");
break;
case 2:
if(DeQueue(&head,&tail,&i)==0)
{
printf("\n出队元素为：%d\n队内元素为：",i);
OutputQueue(head);
printf("\n");
}
else
printf("队空\n\n");
break;
}
}
}
2、基础题2
（1）画出数据结构基本运算的流程图
（2）程序运行主要结果截图
测试用例：依次输入入队元素34,67,45,56，程序运行结果如图
测试用例：让元素34,67出队，程序运行结果如图
（3）程序源代码
#include
#include
#define MAXN 5
int EnQueue(int *queue,int maxn,int *head,int *tail,int x) {
if((*tail+1)%maxn==*head)
return 1;
*tail=(*tail+1)%maxn;
queue[*tail]=x;
return 0;
}
int DeQueue(int *queue,int maxn,int *head,int *tail,int *cp) {
if(*head==*tail)
return 1;
*head=(*head+1)%maxn;
*cp=queue[*head];
return 0;
}
void OutputQueue(int *queue,int maxn,int h,int t)
{
while(h!=t)
{
h=(h+1)%maxn;
printf("%d ",queue[h]);
}
printf("\n");
}
int main()
{
int q[MAXN];
int qh=0,qt=0;
int op,i;
while(1)
{
printf("请选择操作，1:进队2:出队0:退出\n");
fflush(stdin);
scanf("%d",&op);
switch(op)
{
case 0:return 0;
case 1:
printf("请输入进队元素：");
scanf("%d",&i);
if(EnQueue(q,MAXN,&qh,&qt,i)!=0)
printf("队列满\n");
else{
printf("入队成功，队内元素为：\n");
OutputQueue(q,MAXN,qh,qt);
}
break;
case 2:
if(DeQueue(q,MAXN,&qh,&qt,&i)==0)
{
printf("出队元素为：%d ,队内元素为：\n",i);
OutputQueue(q,MAXN,qh,qt);
}
else
printf("队空\n");
break;
}
}
}
3、提高题
（1）画出数据结构基本运算的流程图
（2）程序运行主要结果截图
测试用例：输入病人人数为13，程序运行结果如图
测试用例：输入病人人数为5，程序运行结果如图
测试用例：分别输入病人人数为21，-4，0，程序运行结果如图
（3）程序源代码
#include
#include
#include
typedef struct{
int arrive,treat;
}PA;
typedef struct queue{
PA data;
struct queue *link;
}QE;
void Enqueue(QE **head,QE **tail,PA x)
{
QE *p;
p=(QE*)malloc(sizeof(QE));
p->data=x;
p->link=NULL;
if(*head==NULL)
*head=*tail=p;
else
{
(*tail)->link=p;
*tail=p;
}
}
int Dequeue(QE **head,QE **tail,PA *cp)
{
QE *p;
p=*head;
if(*head==NULL)
return 1;
*cp=(*head)->data;
*head=(*head)->link;
if(*head==NULL)
*tail=NULL;
free(p);
return 0;
}
void Outputqueue(QE *head)
{
while(head!=NULL){
printf("到达时间：%d 处理时间：%d\n",head->data.arrive,head->data.treat);
head=head->link;
}
}
void Initdata(PA *pa,int n)
{
int parr=0;
int i;
for(i=0;i { pa[i].arrive=parr+rand()%15; pa[i].treat=rand()%9+1; parr=pa[i].arrive; printf("第%d 个病人到达的时间为%d ,处理时间为%d\n",i+1,parr,pa[i].treat); } } int main() { QE *head,*tail; PA *p,curr; int n,i,finish,nowtime,dwait,pwait; head=tail=NULL; while(1) { n=0; nowtime=dwait=pwait=0; printf("请输入病人总数（1~20），输入0 结束程序:\n"); scanf("%d",&n); if(n==0) return 0; if(n>20||n<0) continue; if((p=(PA*)malloc(n*sizeof(PA)))==NULL) { printf("内存申请错误\n"); return 0; } Initdata(p,n); for(i=0;i { if(head==NULL){ if(p[i].arrive-nowtime>0) dwait+=p[i].arrive-nowtime; nowtime=p[i].arrive; Enqueue(&head,&tail,p[i++]); } Dequeue(&head,&tail,&curr); pwait+=nowtime-curr.arrive; finish=nowtime+curr.treat; while(i Enqueue(&head,&tail,p[i++]); nowtime=finish; } free(p); printf("医生等待时间为%d ,病人平均等待时间为%.2f\n",dwait,(float)pwait/n); printf("\n"); } return 0; } 小结 在编程实验过程中，体会了栈结构和队列结构在实际问题中的应用。比如栈结构应用的括号匹配问题，可以利用栈结构具有的“后进后出”特性来设计算法，每读入一个括号，便将左括号直接入栈，等待相匹配的同类右括号，若读入右括号，且与当前栈顶的左括号同类型，则二者匹配，将栈顶的左括号出栈；当输入的表达式序列处理完，而栈中仍有等待匹配的元素时，或者输入序列未完，而栈已空，均属于不匹配情况。当输入序列和栈同时变空时，说明所有括号完全匹配。另外，注意到的另一个问题，对于进栈和进队操作，由于受到事先开辟的栈区容量限制，可能产生上溢，因此在进栈和进队操作时，都必须先进行判满操作，以免发生上溢。 在队列的提高题时，因为需要生成随机数列，而课本中提供的函数random函数无法在VC下运行，因此百度学习了VC下可以使用的函数srand和rand函数，刚开始使用的时候，是以time作种子，先调用srand((unsigned)time(NULL))，然后再调用rand函数，后来发现，用这种方法生成的随机数，基本都是相同的数字，我自己分析认为，由于程序运行时间较短，所以同时生成几个随机数时的时间相同，导致了生成的随机数都相同，因此删除了srand函数的调用，只使用rand函数，便解决了同时生成多个随机数的数值相同的问题。 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时） 《数据结构与算法设计》 实验报告 ——实验四 学院： 班级： 学号： 姓名： 一、实验目的 1. 通过实验实践、巩固线性表的相关操作； 2. 熟悉VC 环境，加强编程、调试的练习； 3. 用C 语言实现线性表的抽象数据类型，实现线性表构造、插入、取数据等基本操作； 4. 理论知识与实际问题相结合，利用上述基本操作实现三种排序并输出。 二、实验内容 从键盘输入10个数，编程实现分别用插入排序、交换排序、选择排序算法进行排序，输出排序后的序列。 三、程序设计 1、概要设计 为了实现排序的功能，需要将输入的数字放入线性表中，进行进一步的排序操作。 (1)抽象数据类型： ADT SqList{ 数据对象：D={|,1,2,,,0}i i a a ElemSet i n n ∈=≥ 数据关系：R1=11{,|,,1,2,,}i i i i a a a a D i n --<>∈= 基本操作： InPut(SqList &L) 操作结果：构造一个线性表L 。 OutPut(SqList L) 初始条件：线性表L 已存在。 操作结果：按顺序在屏幕上输出L 的数据元素。 InsertSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行插入排序。 QuickSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行快速排序。 SelectSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行选择排序。 }ADT SqList ⑵主程序流程 由主程序首先调用InPut(L)函数创建顺序表，调用InsertSort(L)函数进行插入排序， 调用OutPut(L)函数显示排序结果。调用QuickSort(L)函数进行交换排序，调用OutPut(L) 函数显示排序结果。调用SelectSort(L)函数进行选择排序，调用OutPut(L)函数显示排序 结果。 ⑶模块调用关系 由主函数模块调用创建顺序表模块，排序模块与显示输出模块。 数据结构实验报告全集 实验一线性表基本操作和简单程序 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<<" 建立一个单链表"< 《数据结构》实验报告 班级： 学号： 姓名： 实验四二叉树的基本操作实验环境：Visual C++ 实验目的： 1、掌握二叉树的二叉链式存储结构； 2、掌握二叉树的建立，遍历等操作。 实验内容： 通过完全前序序列创建一棵二叉树，完成如下功能： 1)输出二叉树的前序遍历序列； 2)输出二叉树的中序遍历序列； 3)输出二叉树的后序遍历序列； 4)统计二叉树的结点总数； 5)统计二叉树中叶子结点的个数； 实验提示： //二叉树的二叉链式存储表示 typedef char TElemType; typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; 一、程序源代码 #include } void Create_BiTree(BiTree *T){ char ch; ch = getchar(); //当输入的是"#"时，认为该子树为空 if(ch == '#') *T = NULL; //创建树结点 else{ *T = (BiTree)malloc(sizeof(struct TNode)); (*T)->data = ch; //生成树结点 //生成左子树 Create_BiTree(&(*T)->lchild); //生成右子树 Create_BiTree(&(*T)->rchild); } } void TraverseBiTree(BiTree T) { //先序遍历 if(T == NULL) return; 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template #include 实验项目名称：图的遍历 一、实验目的 应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。 二、实验容 问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。 三、实验仪器与设备 计算机，Code::Blocks。 四、实验原理 用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索，并输出遍历的结果。 五、实验程序及结果 #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include typedef struct ArCell{ int adj; }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[20]; }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; int LocateVex(MGraph *G,char* v) { int c = -1,i; for(i=0;i 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. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 实验一约瑟夫问题 实验学时：3学时 实验类型：设计 实验要求：必修 一、实验目的 熟练掌握线性链表的基础知识； 能够使用C++或其他程序设计语言编程实现线性链表； 能够使用线性链表构造正确而且时间复杂度低的算法解决实际问题； 锻炼程序设计能力。 二、实验内容 M个教徒和N个非教徒在深海上遇险，必须将N个人投入海中，其余的人才能幸免于难，于是想了一个办法：所有人围成一圆圈，从第一个人开始依次报数，每数到第K个人就将他扔入大海，如此循环进行直到仅余M个人为止。设计一个算法，找出这样一个排序：使每次被扔进大海的都是非教徒。并用程序设计语言实现。 三、实验原理、方法和手段 使用循环单链表，将每个人作为一个结点，每个结点的指针域指向下一个人，采用循环链表的遍历对每隔N-1个结点的结点进行标记，直至标记出N个结点为止。该实验亦可用顺序表实现。 四、实验组织运行要求 本实验采用集中授课形式，每个同学独立完成上述实验要求。 五、实验条件 每人一台计算机独立完成实验，有如下条件： （1）硬件：联想高性能PC机； （2）软件：VC++ 6.0、VC++.Net。 六、实验步骤 （1）编写循环链表构造函数Node *Create( )，使链表中每个结点的数据域值为0，并让最后一个结点的指针域指向第一个结点； （2）编写约瑟夫问题函数 Node *Move(Node *H,int n); void Insert(Node *H,int pos,int data); （5）主函数中调用Create，Move和Insert，采用具体数据计算，输出结果。 七、实验程序 // stdafx.h : 标准系统包含文件的包含文件， // 或是经常使用但不常更改的 // 特定于项目的包含文件 // #pragma once #include"targetver.h" #include 《数据结构与算法统计》 实验报告 ——实验四 学院： 班级： 学号： 姓名： 一、实验目的 1、熟悉VC 环境，学会使用C 语言利用顺序表解决实际问题。 2、通过上机、编程调试，加强对线性表的理解和运用的能力。 3、锻炼动手编程，独立思考的能力。 二、实验内容 从键盘输入10个数，编程实现分别用插入排序、交换排序、选择排序算法进行排序，输出排序后的序列。 三、程序设计 1、概要设计 为了实现排序的功能，需要将输入的数字放入线性表中，进行进一步的排序操作。 (1)抽象数据类型： ADT SqList{ 数据对象：D={|,1,2,,,0}i i a a Elem Set i n n ∈=≥ 数据关系：R1=11{,|,,1,2,,}i i i i a a a a D i n --<>∈= 基本操作： InPut(SqList &L) 操作结果：构造一个线性表L 。 OutPut(SqList L) 初始条件：线性表L 已存在。 操作结果：按顺序在屏幕上输出L 的数据元素。 InsertSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行插入排序。 QuickSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行快速排序。 SelectSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行选择排序。 }ADT SqList ⑵主程序流程 由主程序首先调用InPut(L)函数创建顺序表，调用InsertSort(L)函数进行插入排序，调用OutPut(L)函数显示排序结果。 再由主程序首先调用InPut(L)函数创建顺序表，调用QuickSort(L)函数进行交换排序，调用OutPut(L)函数显示排序结果。 再由主程序首先调用InPut(L)函数创建顺序表，调用SelectSort(L)函数进行选择排序，调用OutPut(L)函数显示排序结果。 ⑶模块调用关系 本科实验报告 课程名称：数据结构（C语言版） 实验项目：线性表、树、图、查找、内排序实验地点：明向校区实验楼208 专业班级：学号： 学生姓名： 指导教师：杨永强 2019 年 1 月10日 #include 福建广播电视大学实验报告（学科：数据结构）姓名单位班级学号实验日期成绩评定教师签名批改日期 实验名称：实验四图的存储方式和应用 4.1建立图的邻接矩阵 【问题描述】 根据图中顶点和边的信息编制程序建立图的邻接矩阵。 【基本要求】 （1）程序要有一定的通用性。 （2）直接根据图中每个结点与其他结点的关联情况输入相关信息，程序能自动形成邻接矩阵 【测试用例】 【实现提示】 （1）对图的顶点编号。 （2）在上图中，以顶点1为例，因为顶点2,3,4与顶点1关联，可以输入信息1 2 3 4，然后设法求出与顶点1关联的结点，从而求得邻接矩阵中相应与顶点1的矩阵元素。 实验图4-1 设计程序代码如下: #include #define MaxEdgeNum 20 #define MaxValue 1000 typedef int VertexType; typedef VertexType vexlist [MaxVertexNum]; typedef int adjmatrix [MaxVertexNum] [MaxVertexNum]; void Createl(vexlist Gv,adjmatrix GA,int n,int e) { int i,j,k,w; printf("输入%d个顶点数据\n",n); for(i=0;i 《数据结构》实验报告 ◎实验题目: 无向图的建立与遍历 ◎实验目的：掌握无向图的邻接链表存储，熟悉无向图的广度与深度优先遍历。 ◎实验内容：对一个无向图以邻接链表存储，分别以深度、广度优先非递归遍历输出。 一、需求分析 1.本演示程序中，输入的形式为无向图的邻接链表形式，首先输入该无向图的顶点数和边数，接着输入顶点信息，再输入每个边的顶点对应序号。 2.该无向图以深度、广度优先遍历输出。 3.本程序可以实现无向图的邻接链表存储，并以深度、广度优先非递归遍历输出。 4.程序执行的命令包括：（1）建立一个无向图的邻接链表存储（2）以深度优先遍历输出（3）以广度优先遍历输出（4）结束 5.测试数据： 顶点数和边数：6,5 顶点信息：a b c d e f 边的顶点对应序号： 0,1 0,2 0,3 2,4 3,4 深度优先遍历输出： a d e c b f 广度优先遍历输出： a d c b e f 二概要设计 为了实现上述操作，应以邻接链表为存储结构。 1.基本操作： void createalgraph(algraph &g) 创建无向图的邻接链表存储 void dfstraverseal(algraph &g,int v) 以深度优先遍历输出 void bfstraverseal(algraph &g,int v) 以广度优先遍历输出 2.本程序包含四个模块： （1）主程序模块 （2）无向图的邻接链表存储模块 （3）深度优先遍历输出模块 （4）广度优先遍历输出模块 3.模块调用图： 三详细设计 1.元素类型，结点类型和指针类型：typedef struct node { int adjvex; struct node *next; }edgenode; typedef struct vnode { char vertex; edgenode *firstedge; }vertxnode; typedef vertxnode Adjlist[maxvernum]; typedef struct { Adjlist adjlist; int n,e; }algraph; edgenode *s; edgenode *stack[maxvernum],*p; 2.每个模块的分析： （1）主程序模块 int main() 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 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template 浙江科技学院《数据结构》实验报告 年级班级 学号 姓名 任课老师 实验指导教师 实验地点 信息学院 实验一线性表操作（一元多项式的运算） 实验目的： 1、定义线性表的链式存储 2、实现对线性表的一些基本操作和具体函数定义 实验要求： 1、定义线性表的链式存储； 2、实现对线性表的一些基本操作和具体函数定义。 3、定义输出一元多项式的函数； 4、编写主程序调用上面的函数实现一元多项式的加减。 数据输入输出要求： 输入示例： 3 2 3 3 4 5 7 5 2 1 3 3 -3 4 4 6 5 7 （说明：第一个数据3表示该第一个一元多项式的项数为3，后面的2 3 表示第一项的系数为2 指数为3；按指数递增的次序输入） 输出示例： 一元多项式1： 2x(3)+3x(4)+5x(7) 一元多项式2： 2x(1)+3x(3)-3x(4)+4x(6)+5x(7) 加的结果：2x(1)+5x(3) +4x(6)+10x(7) 减的结果：-2x(1)-1x(3)＋6x(4)-4x(6) 程序代码： #include #include 数据结构(C语言版) 实验报告 专业班级学号姓名 实验1 实验题目：单链表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序 的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序： （1）增加插入结点的功能。 （2）将建立链表的方法改为头插入法。 程序代码: #include"stdio.h" #include"string.h" #include"stdlib.h" #include"ctype.h" typedef struct node //定义结点 { char data[10]; //结点的数据域为字符串 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自定义LinkList单链表类型 LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表 LinkList CreatList(void); //函数，用头插入法建立带头结点的单链表 ListNode *LocateNode(); //函数，按值查找结点 void DeleteList(); //函数，删除指定值的结点 void printlist(); //函数，打印链表中的所有值 void DeleteAll(); //函数，删除所有结点，释放内存 班级: 姓名: 学号: 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义; 2、掌握线性表的基本操作,如建立、查找、插入与删除等。 二、实验内容 定义一个包含学生信息(学号,姓名,成绩)的顺序表与链表(二选一),使其具有如下功能: (1) 根据指定学生个数,逐个输入学生信息; (2) 逐个显示学生表中所有学生的相关信息; (3) 根据姓名进行查找,返回此学生的学号与成绩; (4) 根据指定的位置可返回相应的学生信息(学号,姓名,成绩); (5) 给定一个学生信息,插入到表中指定的位置; (6) 删除指定位置的学生记录; (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include { char num[10]; // 学号 char name[20]; // 姓名 double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK; } Status GetElem(LinkList L,int i,ElemType &e) // 访问链表,找到i位置的数据域,返回给 e { LinkList p; p=L->next;数据结构实验报告格式
北京理工大学《数据结构与算法设计》实验报告实验四
(完整版)数据结构实验报告全集
数据结构实验报告(四)
数据结构实验报告
数据结构实验报告图实验
数据结构图的遍历实验报告
数据结构实验报告模板
数据结构实验报告图实验
数据结构实验报告
北京理工大学数据结构实验报告4
数据结构实验报告
数据结构实验报告4(中央电大)
数据结构实验报告无向图
数据结构实验报告及心得体会
数据结构实验报告图实验
数据结构实验报告
数据结构实验报告 - 答案汇总
数据结构实验一 实验报告