数据结构(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;
typedefListNode*LinkList; // 自定义LinkList单链表类型
LinkList CreatListR1();//函数,用尾插入法建立带头结点的单链表
LinkList CreatList(void); //函数,用头插入法建立带头结点的单链表ListNode *LocateNode(); //函数,按值查找结点
void DeleteList(); //函数,删除指定值的结点
void printlist();//函数,打印链表中的所有值
voidDeleteAll(); //函数,删除所有结点,释放内存ListNode * AddNode();???? //修改程序:增加节点.用头插法,返回头指针
//==========主函数==============
void main()
{
?charch[10],num[5];
?LinkListhead;
head=CreatList(); //用头插入法建立单链表,返回头指针
printlist(head);//遍历链表输出其值
?printf(" Delete node (y/n):"); //输入"y"或"n"去选择是否删除结点?scanf("%s”,num);
?if(strcmp(num,”y")==0 || strcmp(num,”Y”)==0){
??printf("Please input Delete_data:");
?scanf("%s",ch);//输入要删除的字符串
?DeleteList(head,ch);
?printlist(head);
?}
printf(” Add node ?(y/n):"); //输入"y"或"n"去选择是否增加结点
?scanf(”%s",num);
?if(strcmp(num,"y")==0 || strcmp(num,"Y")==0)
{
??head=AddNode(head);
?}
printlist(head);
?DeleteAll(head); //删除所有结点,释放内存
}
//==========用尾插入法建立带头结点的单链表===========
LinkList CreatListR1(void)
{
char ch[10];
LinkList head=(LinkList)malloc(sizeof(ListNode)); //生成头结点
ListNode *s,*r,*pp;
r=head;
r—>next=NULL;
printf("Input #to end "); //输入"#"代表输入结束
printf(”\nPlease input Node_data:”);
scanf(”%s",ch); //输入各结点的字符串
while(strcmp(ch,”#”)!=0) {
pp=LocateNode(head,ch);//按值查找结点,返回结点指针
?if(pp==NULL) {//没有重复的字符串,插入到链表中?s=(ListNode *)malloc(sizeof(ListNode));
???strcpy(s-〉data,ch);
r->next=s;
??r=s;
?r->next=NULL;
?}
?printf(”Input # to end ”);
??printf("Please input Node_data:");
?scanf(”%s",ch);
}
return head; //返回头指针
}
//==========用头插入法建立带头结点的单链表===========
LinkList CreatList(void)
{
char ch[100];
?LinkListhead,p;
?head=(LinkList)malloc(sizeof(ListNode));
head->next=NULL;
?while(1)
{
?printf("Input # to end ");
?printf("Pleaseinput Node_data:”);
?scanf(”%s”,ch);
?if(strcmp(ch,"#”))
??{
??if(LocateNode(head,ch)==NULL)
??{
?strcpy(head-〉data,ch);
??p=(LinkList)malloc(sizeof(ListNode));
????p-〉next=head;
?head=p;
??}
?}
??else
?break;
}
?return head;
}
//==========按值查找结点,找到则返回该结点的位置,否则返回NULL==========ListNode *LocateNode(LinkList head,char *key)
{
ListNode *p=head->next; //从开始结点比较
while(p!=NULL && strcmp(p—>data,key)!=0) //直到p为NULL或p —〉data为key止
p=p—>next; //扫描下一个结点
return p; //若p=NULL则查找失败,否则p指向找到的值为key的结点}
//==========修改程序:增加节点=======
ListNode * AddNode(LinkList head)
{
char ch[10];
?ListNode *s,*pp;
printf("\nPlease input a New Node_data:”);
scanf(”%s”,ch); //输入各结点的字符串
?pp=LocateNode(head,ch);//按值查找结点,返回结点指针
?printf("ok2\n");
if(pp==NULL) { //没有重复的字符串,插入到链表中
?s=(ListNode*)malloc(sizeof(ListNode));
?strcpy(s-〉data,ch);
printf("ok3\n");
s->next=head-〉next;
?head—>next=s;
}
return head;
}
//==========删除带头结点的单链表中的指定结点=======
void DeleteList(LinkList head,char*key)
{
ListNode *p,*r,*q=head;
p=LocateNode(head,key); //按key值查找结点的
if(p==NULL){ //若没有找到结点,退出
printf("position error”);
exit(0);
}
while(q—>next!=p) //p为要删除的结点,q为p的前结点
??q=q-〉next;
r=q—〉next;
q—〉next=r—>next;
free(r); //释放结点
}
//===========打印链表=======
void printlist(LinkListhead)
{
ListNode *p=head->next; //从开始结点打印
while(p){
?printf(”%s,",p->data);
??p=p—>next;
}
printf("\n");
}
//==========删除所有结点,释放空间===========
void DeleteAll(LinkList head)
{
ListNode *p=head,*r;
while(p-〉next){
?r=p->next;
?free(p);
?p=r;
}
?free(p);
}
实验结果:
Input # to end Please inputNode_data:bat
Input # to end Please input Node_data:cat
Input # to end Please input Node_data:eat
Input # to end Please input Node_data:fat
Input # to end Please input Node_data:hat
Input # to end Please input Node_data:jat
Input # toend Please input Node_data:lat
Input# to endPleaseinput Node_data:mat
Input #to endPlease input Node_data:#
mat, lat, jat,hat, fat, eat, cat, ba t,
Delete node (y/n):y
Please input Delete_data:hat
mat,lat,jat, fat,eat, cat, bat,
Insert node(y/n):y
Please input Insert_data:put
position :5
mat,lat, jat, fat,eat, put, cat, bat,
请按任意键继续. . 。
示意图:
head
head
head
心得体会:
本次实验使我们对链表的实质了解更加明确了,对链表的一些基本操作也更加熟练了。另外实验指导书上给出的代码是有一些问题的,这使我们认识到实验过程中不能想当然的直接编译执行,应当在阅读并完全理解代码的基础上再执行,这才是实验的意义所在.
?实验2
实验题目:二叉树操作设计和实现
实验目的:
掌握二叉树的定义、性质及存储方式,各种遍历算法。
实验要求:
采用二叉树链表作为存储结构,完成二叉树的建立,先序、中序和后序以及按层次遍历的操作,求所有叶子及结点总数的操作.
实验主要步骤:
1、分析、理解程序.
2、调试程序,设计一棵二叉树,输入完全二叉树的先序序列,用#代表虚结点(空指针),
如ABD###CE##F##,建立二叉树,求出先序、中序和后序以及按层次遍历序列,求所有叶子及结点总数。
实验代码
#include"stdio。h”
#include”stdlib.h"
#include”st ring.h”
#define Max 20 //结点的最大个数
typedef struct node{
chardata;
struct node *lchild,*rchild;
}BinTNode;//自定义二叉树的结点类型
typedef BinTNode *BinTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数,leaf为叶子数
//==========基于先序遍历算法创建二叉树==============
//=====要求输入先序序列,其中加入虚结点”#”以示空指针的位置========== BinTree CreatBinTree(void)
{
BinTree T;
charch;
if((ch=getchar())=='#')
return(NULL); //读入#,返回空指针
else{
?T= (BinTNode *)malloc(sizeof(BinTNode)); //生成结点
??T—>data=ch;
T—>lchild=CreatBinTree(); //构造左子树
??T—>rchild=CreatBinTree();//构造右子树
?return(T);
}
}
//========NLR 先序遍历=============
voidPreorder(BinTree T)
{
if(T) {
?printf("%c",T-〉data);//访问结点
Preorder(T->lchild); //先序遍历左子树
Preorder(T->rchild);//先序遍历右子树
}
}
//========LNR 中序遍历===============
void Inorder(BinTree T)
{
if(T) {
?Inorder(T—>lchild); //中序遍历左子树
?printf(”%c”,T->data);//访问结点
Inorder(T-〉rchild); //中序遍历右子树
}
}
//==========LRN后序遍历============
void Postorder(BinTree T)
{
if(T) {
?Postorder(T—〉lchild); //后序遍历左子树?Postorder(T->rchild); //后序遍历右子树
?printf(”%c",T—〉data); //访问结点
}
}
//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法======== int TreeDepth(BinTree T)
{
int hl,hr,max;
if(T){
hl=TreeDepth(T—〉lchild);//求左深度
??hr=TreeDepth(T—>rchild); //求右深度
?max=hl>hr? hl:hr;//取左右深度的最大值
?NodeNum=NodeNum+1; //求结点数
?if(hl==0&&hr==0)leaf=leaf+1; //若左右深度为0,即为叶子。
?return(max+1);
}
else return(0);
}
//====利用”先进先出"(FIFO)队列,按层次遍历二叉树========== void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定义结点的指针数组cq
cq[1]=T; //根入队
while(front!=rear)
{
front=(front+1)%NodeNum;
?p=cq[front]; //出队
??printf(”%c",p-〉data); //出队,输出结点的值
if(p-〉lchild!=NULL){
? rear=(rear+1)%NodeNum;
cq[rear]=p—〉lchild; //左子树入队
??}
?if(p->rchild!=NULL){
?rear=(rear+1)%NodeNum;
??cq[rear]=p-〉rchild;//右子树入队
?}
}
}
//====数叶子节点个数==========
int countleaf(BinTree T)
{
int hl,hr;
if(T){
?hl=countleaf(T->lchild);
hr=countleaf(T—>rchild);
?if(hl==0&&hr==0)//若左右深度为0,即为叶子。
?return(1);
?elsereturn hl+hr;
}
?else return 0;
}
//==========主函数=================
void main()
{
BinTree root;
char i;
int depth;
printf(”\n”);
printf("Creat Bin_Tree; Input preorder:”); //输入完全二叉树的先序序列,
// 用#代表虚结点,如ABD###CE##F## root=CreatBinTree();//创建二叉树,返回根结点
do{ //从菜单中选择遍历方式,输入序号。
?printf("\t********** select************\n");?printf("\t1: PreorderTraversal\n”);
?printf("\t2:Iorder Traversal\n”);
printf("\t3: Postorder traversal\n");
printf("\t4: PostTreeDepth,Nodenumber,Leaf number\n");
?printf("\t5: Level Depth\n"); //按层次遍历之前,先选择4,求出该树的结点数。
?printf("\t0: Exit\n");
printf("\t*******************************\n”);
fflush(stdin);
?scanf("%c”,&i); //输入菜单序号(0-5)
switch (i—’0'){
?case 1: printf("Print Bin_tree Preorder: ”);
?Preorder(root);//先序遍历
??break;
?case 2: printf("Print Bin_Tree Inorder:");
?Inorder(root);//中序遍历
break;
case 3:printf(”Print Bin_Tree Postorder: ");
?Postorder(root); //后序遍历
break;
case4:
depth=TreeDepth(root); //求树的深度及叶子数
??printf("BinTree Depth=%d BinTreeNode number=%d”,depth,Node Num);
??printf(" BinTree Leaf number=%d”,countleaf(root));
??break;
?case 5: printf(”LevePrint Bin_Tree: ”);
Levelorder(root); //按层次遍历
??break;
?default:exit(1);
}
printf(”\n”);
} while(i!=0);
}
实验结果:
Creat Bin_Tree; Input preorder:ABD###CE##F##
********** select************
1: Preorder Traversal
2:Iorder Traversal
《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程,是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法,介绍了常用的多种查找和排序技术,并做了性能分析和比较,内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因,使得掌握这门课程具有较大的难度: (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<<" 建立一个单链表"<
数据结构实验报告 一.题目要求 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 华北电力大学 实验报告| | 实验名称数据结构实验 课程名称数据结构 | | 专业班级:学生姓名: 学号:成绩: 指导教师:实验日期:2015/7/3 实验报告说明: 本次实验报告共包含六个实验,分别为:简易停车场管理、约瑟夫环(基于链表和数组)、二叉树的建立和三种遍历、图的建立和两种遍历、hash-telbook和公司招工系统。 编译环境:visual studio 2010 使用语言:C++ 所有程序经调试均能正常运行 实验目录 实验一约瑟夫环(基于链表和数组) 实验二简易停车场管理 实验三二叉树的建立和三种遍历 实验四图的建立和两种遍历 实验五哈希表的设计 实验一:约瑟夫环 一、实验目的 1.熟悉循环链表的定义和有关操作。 二、实验要求 1.认真阅读和掌握实验内容。 2.用循环链表解决约瑟夫问题。 3.输入和运行编出的相关操作的程序。 4.保存程序运行结果 , 并结合输入数据进行分析。 三、所用仪器设备 1.PC机。 2.Microsoft Visual C++运行环境。 四、实验原理 1.约瑟夫问题解决方案: 用两个指针分别指向链表开头和下一个,两指针依次挪动,符合题意就输出结点数据,在调整指针,删掉该结点。 五、代码 1、基于链表 #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 《数据结构实验》的实验题目及实验报告模板 实验一客房管理(链表实验) ●实现功能:采用结构化程序设计思想,编程实现客房管理程序的各个功能函数,从而熟练 掌握单链表的创建、输出、查找、修改、插入、删除、排序和复杂综合应用等操作的算法 实现。以带表头结点的单链表为存储结构,实现如下客房管理的设计要求。 ●实验机时:8 ●设计要求: #include 《数据结构》实验报告 ◎实验题目: 无向图的建立与遍历 ◎实验目的:掌握无向图的邻接链表存储,熟悉无向图的广度与深度优先遍历。 ◎实验内容:对一个无向图以邻接链表存储,分别以深度、广度优先非递归遍历输出。 一、需求分析 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.掌握线性表的顺序存储结构的定义及实现。 3.掌握线性表的链式存储结构——单链表的定义及实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21,23,14,5,56,17,31},然后在第i个位置插入元素68。 3.建立一个带头结点的单链表,结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、程序主要语句及作用(main函数程序清单) 程序1的主要代码(附简要注释) #include 本科实验报告 课程名称:数据结构(C语言版) 实验项目:线性表、树、图、查找、内排序实验地点:明向校区实验楼208 专业班级:学号: 学生姓名: 指导教师:杨永强 2019 年 1 月10日 #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 数据结构实验报告 第 6 次实验 学号:20141060106 姓名:叶佳伟 一、实验目的 1、复习图的逻辑结构、存储结构及基本操作; 2、掌握邻接矩阵、邻接表及图的创建、遍历; 3、了解图的应用。 二、实验内容 1、(必做题)假设图中数据元素类型是字符型,请采用邻接矩阵或邻接表实现图的以下基本操作: ( 1)构造图(包括有向图、有向网、无向图、无向网); ( 2)根据深度优先遍历图; ( 3)根据广度优先遍历图。 三、算法描述 (采用自然语言描述) 四、详细设计 (画出程序流程图) 五、程序代码 (给出必要注释) #include int adj;/*顶点关系类型,对无权图,用1(是)或0(否)表示相邻否;对带权图,则为权值*/ char *info;/*弧相关信息指针*/ }AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char vexs[MAX_VERTEX_NUM][5];/*顶点向量*/ AdjMatrix arcs; /*邻接矩阵*/ int vexnum, arcnum;/*图的当前顶点数和弧数*/ int kind; }MGraph; void CreateDG(MGraph *G); void CreateDN(MGraph *G); void CreateUDG(MGraph *G); void CreateUDN(MGraph *G); int LocateVex(MGraph *G, char v[]); void print(MGraph *G); int main(void) { MGraph *G; G = (MGraph *)malloc(sizeof(MGraph)); printf("请选者0-有向图,1-有向网,2-无向图,3-无向网: "); scanf("%d", &G->kind); switch(G->kind) { case DG : CreateDG(G); print(G); break; case DN : CreateDN(G); print(G); break; case UDG : CreateUDG(G); print(G); break; case UDN : CreateUDN(G); 数据结构(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.掌握邻接矩阵和邻接表定义及特点,并通过实例解析掌握邻接 矩阵和邻接表的类型定义。 3.掌握图的遍历的定义、复杂性分析及应用,并掌握图的遍历方 法及其基本思想。 二、实验内容: 1.建立无向图的邻接矩阵 2.图的深度优先搜索 3.图的广度优先搜索 三、实验步骤及结果: 1.建立无向图的邻接矩阵: 1)源代码: #include "" #include "" #define MAXSIZE 30 typedef struct { char vertex[MAXSIZE]; ertex=i; irstedge=NULL; irstedge; irstedge=p; p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } int visited[MAXSIZE]; ertex); irstedge; ertex=i; irstedge=NULL; irstedge;irstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } typedef struct node { int data; struct node *next; }QNode; ertex); irstedge;ertex); //输出这个邻接边结点的顶点信息 visited[p->adjvex]=1; //置该邻接边结点为访问过标志 In_LQueue(Q,p->adjvex); //将该邻接边结点送人队Q } 华南农业大学信息学院 综合性、设计性实验 起止日期:2011秋 学院软件学院专业班级10软件工程7班学号20103100070 4 姓名黄定康 实 验 题 目 实现平衡二叉排序树的各种算法 自我评价 项目算法设计独立完成情况算法熟练程度测试 通过 成功失败独立帮助掌握了解不懂 插入新结点√√√√ 前序、中序、后序遍历二叉树 (递归) √√√√ 前序、中序、后序遍历的非递 归算法 √√√√ 层次遍历二叉树√√√√ 在二叉树中查找给定关键字√√√√ 交换各结点的左右子树√√√√ 求二叉树的深度√√√√ 叶子结点数√√√√ 删除某结点√√√√ ●A---------完成实验要求的全部功能并运行通过,算法有一定的新意,程序代码 符合书写规范,实验报告叙述清晰完整,有详尽的分析和总结。 ●B---------完成实验要求的全部功能,程序代码符合书写规范,实验报告叙述 清晰完整。 ●C---------完成实验要求的大部分功能,实验报告良好。 ●D---------未按时完成实验,或者抄袭。 成 绩 教师签名:杨秋妹 实验报告 题目:实现平衡二叉排序树的各种算法 班级:10软件工程7班 姓名:黄定康 学号:201031000704 完成日期:2011/12/07 (一)分析题目要求 (1)函数说明 void R_rotate(ptr& t) -右旋转函数,从T开始做右旋转 int coutdeep(ptr t)-计算深度函数 void L_rotate(ptr& t)-左旋转函数 void leftbalance(ptr&t)-左平衡函数,从T开始做左平衡处理 void rightbalance(ptr&t)-右平衡函数 int insertA VL(ptr& t,int e,int & taller)-插入结点函数 void preorder(ptr t)-(递归)先序遍历 void preorder_2(ptr t)-(非递归)先序遍历 void inorder(ptr t)-(递归)中序遍历 void inorder_2(ptr t)-(非递归)中序遍历 void posorder(ptr t)-(递归)后序遍历 void posorder_2(ptr t)-(非递归)后序遍历 void dfs(ptr t,int type)-(递归)深度优先遍历(包含中序先序后续) void dfs_2(ptr t,int type)-(递归) 深度优先遍历 int bfs(ptr t)-层次便利 int delete_node(ptr& t,int&shorter,int temp);-删除结点函数 int Delete(ptr& t,int shorter)-删除结点函数 int transfer(ptr&t)-左右子树交换函数 int countleaf(ptr t)-计算叶节点 int checkup(ptr t,int temp)- 从树t中查找temp是否存在,存在返回1否则返回0 int main()-主函数 void show_menu(ptr t)-简单的菜单函数 (2)输入形式及输入值范围 输入形式:当树没创建时,先在第一行输入树的节点数目n,第二行再输入n个大于0的不重复整数,以空格隔开。删除结点时,直接输入要删除结点的值。 输入范围:所有int类型的大于零的值,注意不能重复输入。数据结构实验报告图实验
数据结构实验报告完整
数据结构图的遍历实验报告
数据结构实验报告模板
数据结构实验报告图实验
《数据结构实验》实验题目及实验报告模板
数据结构实验报告无向图
数据结构实验报告及心得体会
数据结构实验报告图实验
数据结构实验报告
数据结构实验报告
数据结构实验报告
数据结构实验报告
数据结构实验报告 - 答案汇总
数据结构图实验报告
数据结构实验报告