《数据结构》实验报告三
学校:班级:
学号:姓名:
日期:2011.6.7 程序名:作业二叉树的递归操作.cpp 一、上机实验的问题和要求:
要求采用二叉链表作为存储结构,完成二叉树的建立,前序、中序和后序遍历的操作,求所有叶子及结点总数的操作等。具体实现要求:
1.基于先序遍历的构造算法:输入是二叉树的先序序列,但必须在
其中加入虚结点以示空指针的位置。假设虚结点输入时用空格字符表示。
2.用广义表表示所建二叉树。
3.用凹入表表示所建二叉树。
4.分别利用前序遍历、中序遍历、后序遍历所建二叉树。
5.求二叉树结点总数,观察输出结果。
6.求二叉树叶子总数,观察输出结果。
7.交换各结点的左右子树,用广义表表示法显示新的二叉树。
8.(★)二叉树采用链接存储结构,其根结点指针为T,设计一个
算法对这棵二叉树的每个结点赋值:(注意要修改DataType类型) 叶结点的值为3
?只有左孩子或右孩子的结点则其值分别等于左孩子或右孩子
的值
?左、右孩子均有的结点,则其值等于左、右孩子结点的值之和
?用广义表表示法显示所建二叉树
阅读理解建立Huffman树的算法,对该算法进行运行及调试。具体实现要求:
1.调试并运行Huffman算法,验算《回家作业六》的第3题。
2.(★)求Huffman树的带权路径长度WPL。
二、程序设计的基本思想,原理和算法描述:
(包括程序的结构,数据结构,输入/输出设计,符号名说明等)基本思想:对任意一棵二叉树,试将其所有节点的左、右子树交换。并将交换前、后不同的二叉树分别用前序、中序、和后序三种不同的方法进行遍历。
基本原理:同基本线性表、特殊线性表相似,二叉树也有顺序和链式两种基本的存储结构。因此针对不同的存储结构,在实现左右子树交换的过程中方法会有不同。在程序实现过程中要求不同功能分别用单个的函数实现,其中按层遍历二叉树的函数用顺序方法实现,其他函数用链式方法实现。
基本原理:(1)创建二叉树。(2)用三种不同的方法遍历交换左右子树前的二叉树。(3)交换二叉树中所有结点的左右子树。(4)用三种不同的方法遍历交换左右子树后的二叉树。
三、源程序及注释:
//要求采用二叉链表作为存储结构,完成二叉树的建立,前序、中序和后序遍历的操作,求所有叶子及结点总数的操作等
#include
#include
#include
#include
#define NULL 0
typedef char DataType;
typedef struct BinTNode
{
DataType data;
struct BinTNode *rchild,*lchild;
}BinTNode,*BinTree;
//创建二叉数
void Create(BinTree *T)
{
char ch;
if((ch = getchar()) == '*') //输入'*'时该节点为空
*T = NULL;
else
{
*T = (BinTree)malloc(sizeof(BinTNode));
(*T)->data = ch;
Create(&(*T)->lchild);
Create(&(*T)->rchild);
}
}
//先序遍历二叉树
void PreOrder(BinTree T)
{
if(T)
{
printf("%c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
//中序遍历二叉树
void InOrder(BinTree T)
{
if(T)
InOrder(T->lchild);
printf("%c",T->data);
InOrder(T->rchild);
}
}
//后序遍历二叉树
void PostOrder(BinTree T)
{
if(T)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%c",T->data);
}
}
//用广义表表示二叉树
void ListPrint(BinTree T)
{
if(T)
{
printf("%c",T->data);
if(T->lchild != NULL || T->rchild != NULL)
{
printf("(");
ListPrint(T->lchild);
if(T->lchild != NULL)
printf(",");
ListPrint(T->rchild);
printf(")");
}
}
}
//用凹入表表示二叉树
/*对于凹入表表示二叉树,其实就是把二叉树结点的深度表示出来*/ void DisplayPrint(BinTree T,int lay)
{
if(T)
{
for(int i=0;i printf(" "); printf("%c\n",T->data); DisplayPrint(T->lchild,lay+1); DisplayPrint(T->rchild,lay+1); } //求结点的个数 int Node(BinTree T) { int static N=0; if(T) { Node(T->lchild); N++; Node(T->rchild); } return N; } //求叶子的个数 int Leaf(BinTree T) { int static L=0; if(T) { Leaf(T->lchild); if(!(T->lchild||T->rchild))//没有左子树和右子树,就是叶子L++; Leaf(T->rchild); } return L; } //交换左子树和右子树 void Change(BinTree *T) { if(*T) { BinTNode *temp; Change(&(*T)->lchild); Change(&(*T)->rchild); temp=(*T)->lchild; (*T)->lchild=(*T)->rchild; (*T)->rchild=temp; } } void main() { BinTree T; printf("输入先序序列:"); Create(&T); printf("输出先序遍历:"); PreOrder(T); printf("\n"); printf("输出中序遍历:"); InOrder(T); printf("\n"); printf("输出后序遍历:"); PostOrder(T); printf("\n"); printf("输出广义表表示法:"); ListPrint(T); printf("\n"); printf("输出凹入表表示法:\n"); DisplayPrint(T,1); printf("结点的个数:nodes = %d\n",Node(T)); printf("叶子的个数:leaves = %d\n",Leaf(T)); Change(&T); printf("交换左右子树,并用广义表表示法:"); ListPrint(T); printf("\n"); } 四、运行输出结果: 五、调试和运行程序过程中产生的问题及采取的措施: 有语法错误和打程序时的拼写错误,主要就是根据出错的地方进行单方面的调试。 六、对算法的程序的讨论、分析,改进设想,其它经验教训: 在算法实现上,从算法的效率看,非递归方法具有较好的时间效率,递归方法书写形式较为简捷,更为直观,一般具有较好的空间效率。 在按要求访问树中某些结点的数据元素时,选择一种合适的访问顺序是有必要的。 利用树对不同数据元素进行组合,在排序和某些特殊应用情景下是一种不错的选择。 七、对实验方式、组织、设备、题目的意见和建议: 对题目可以更加综合一下,与后面学到的图结合起来,那么它的作用会更大。 #include<> #include<> #include<> #define MAXSIZE 100 typedef int DataType; typedef struct stack { DataType data[MAXSIZE]; int top; }sqstack; sqstack *InitStack(sqstack *S)出* 1.顺序栈的初始化*┃\n"); printf("\t┃* * *┃\n"); printf("\t┃************************************************************┃\n"); printf("\t┃* * *┃\n"); printf("\t┃* 2.元素的入栈* 3.元素的出栈*┃\n"); printf("\t┃* * *┃\n"); printf("\t┃************************************************************┃\n"); printf("\t┃* * *┃\n"); printf("\t┃* 4.取栈顶元素* 5.判空*┃\n"); printf("\t┃* * *┃\n"); printf("\t┃************************************************************┃\n"); printf("\t┃* *┃\n"); printf("\t┃* 6.将十进制数转换为其他进制数*┃\n"); printf("\t┃* *┃\n"); printf("\t┃************************************************************┃\n"); printf("\t┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n"); while ((m='0')&&(m='1')&&(m='2')&&(m='3')&&(m='4')&&(m='5')&&(m='6')&&(m='7')) { printf("\n请选择你需要操作的步骤(0至7):"); fflush(stdin); scanf("%c",&m); switch(m) { case '0': { exit(0); break; } 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程,是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法,介绍了常用的多种查找和排序技术,并做了性能分析和比较,内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因,使得掌握这门课程具有较大的难度: (1)内容丰富,学习量大,给学习带来困难; (2)贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点; (3)所用到的技术多,而在此之前的各门课程中所介绍的专业性知识又不多,因而加大了学习难度; (4)隐含在各部分的技术和方法丰富,也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性,设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练,突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时,觉得无从下手,做起来特别费劲。实验中的内容和教科书的内容是密切相关的,解决题目要求所需的各种技术大多可从教科书中找到,只不过其出现的形式呈多样化,因此需要仔细体会,在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程,理解和掌握算法设计所需的技术,为整个专业学习打好基础,要求运用所学知识,上机解决一些典型问题,通过分析、设计、编码、调试等各环节的训练,使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法,如算法设计的构思方法,动态链表,算法的编码,递归技术,与特定问题相关的技术等,要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上,掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时,要求完成以下六个题目: 实习一约瑟夫环问题(2学时) 图实验一,邻接矩阵的实现 1.实验目的 (1)掌握图的逻辑结构 (2)掌握图的邻接矩阵的存储结构 (3)验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 (1)建立无向图的邻接矩阵存储 (2)进行深度优先遍历 (3)进行广度优先遍历 3.设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template #include 实验2 查找算法的实现和应用?实验目的 1. 熟练掌握静态查找表的查找方法; 2. 熟练掌握动态查找表的查找方法; 3. 掌握hash表的技术. ?实验内容 1.用二分查找法对查找表进行查找; 2.建立二叉排序树并对该树进行查找; 3.确定hash函数及冲突处理方法,建立一个hash表并实现查找。 程序代码 #include cout<<"Not present!"; } return 0; } 结果 二叉排序树 #include 数据结构实验报告 一.题目要求 1)编程实现二叉排序树,包括生成、插入,删除; 2)对二叉排序树进行先根、中根、和后根非递归遍历; 3)每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4)分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率,并说明在什么情况下二叉排序树效率高,为什么? 二.解决方案 对于前三个题目要求,我们用一个程序实现代码如下 #include 实验三的实验报告 学期: 2010 至_2011 第 2 学期 2011年 3月 27日课程名称: 数据结构专业:信息与计算科学 09 级5班实验编号: 03 实验项目:栈和队列实验指导教师 _冯山_姓名:朱群学号: 2009060548 实验成绩: 一实验目的: (1)熟练掌握栈和队列的抽象数据类型及其结构特点; (2)实现基本的栈和队列的基本操作算法程序。 二实验内容:(类C算法的程序实现,任选其一) (1) 设计与实现基本的堆栈和队列结构下的各种操作(如堆栈的PUSH、POP 等操作)(必做); (2)以表达式计算为例,完成一个可以进行算术表达式计算功能的算法设计 与实现(选做); (3)以迷宫问题为例,以堆栈结构完成迷宫问题的求解算法和程序(选做)。三实验准备: 1) 计算机设备;2)程序调试环境的准备,如TC环境;3)实验内容的算法分 析与代码设计与分析准备。 四实验步骤: 1.录入程序代码并进行调试和算法分析; 2.编写实验报告。 五实验过程 一设计与实现基本的堆栈结构下的各种操作(如堆栈的PUSH、POP等操作)(1)问题描述 实现堆栈各种基本操作,如Pop,Push,GetTop等操作,即输入数据,通过Push入栈,再通过Pop操作输出出栈的元素,即入栈a,b,c,d,出栈d,c,b,a (2)算法实现及基本思想 堆栈是后进先出的线性表,由Push输入元素,Pop输出元素,堆栈的Push 操作思想,即插入元素e为新的的栈顶元素,先判断栈满与否,追加存储空间,然后将e值赋给栈顶指针Top。输入数据时用for循环 堆栈的Pop操作思想,先判断栈是否为空,若栈不空,则删除栈的栈顶元素,用e返回其值, (3)数据结构 栈的顺序存储结构 Typedef struct { 数据结构实验报告全集 实验一线性表基本操作和简单程序 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、了解函数指针。 二、实验内容 1、(必做题)每个学生的成绩信息包括:学号、语文、数学、英语、总分、加权平均分;采用链表存储若干学生的成绩信息;输入学生的学号、语文、数学、英语成绩;计算学生的总分和加权平均分(语文占30%,数学占50%,英语占20%);输出学生的成绩信息。 三、算法描述 (采用自然语言描述) 首先创建链表存储n个学生的成绩信息,再通过键盘输入学生的信息,创建指针p所指结点存储学生的成绩信息,从键盘读入学生人数,求出学生的总分和加权平均分,输出结果。 四、详细设计 (画出程序流程图) 五、程序代码 (给出必要注释) #include 姓名: 学号: 班级: 2010年12月15日 实验一线性表的应用 【实验目的】 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。、; 2、以线性表的各种操作(建立、插入、删除、遍历等)的实现为重点; 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现; 4、通过本章实验帮助学生加深对C语言的使用(特别是函数的参数调用、指针类型的 应用和链表的建立等各种基本操作)。 【实验内容】 约瑟夫问题的实现:n只猴子要选猴王,所有的猴子按1,2,…,n编号围坐一圈,从第一号开始按1,2…,m报数,凡报到m号的猴子退出圈外,如此次循环报数,知道圈内剩下一只猴子时,这个猴子就是猴王。编写一个程序实现上述过程,n和m由键盘输入。【实验要求】 1、要求用顺序表和链表分别实现约瑟夫问题。 2、独立完成,严禁抄袭。 3、上的实验报告有如下部分组成: ①实验名称 ②实验目的 ③实验内容:问题描述:数据描述:算法描述:程序清单:测试数据 算法: #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 长春大学计算机学院网络工程专业 数据结构实验报告 实验名称:实验二栈和队列的操作与应用 班级:网络14406 姓名:李奎学号:041440624 实验地点:日期: 一、实验目的: 1.熟练掌握栈和队列的特点。 2.掌握栈的定义和基本操作,熟练掌握顺序栈的操作及应用。 3.掌握链队的入队和出队等基本操作。 4.加深对栈结构和队列结构的理解,逐步培养解决实际问题的编程能力。 二、实验内容、要求和环境: 注:将完成的实验报告重命名为:班级+学号+姓名+(实验二),(如:041340538张三(实验二)),发邮件到:ccujsjzl@https://www.wendangku.net/doc/ec2402834.html,。提交时限:本次实验后24小时之内。 阅读程序,完成填空,并上机运行调试。 1、顺序栈,对于输入的任意一个非负十进制整数,打印输出与其等值的八进制数 (1)文件SqStackDef. h 中实现了栈的顺序存储表示 #define STACK_INIT_SIZE 10 /* 存储空间初始分配量*/ #define STACKINCREMENT 2 /* 存储空间分配增量*/ typedef struct SqStack { SElemType *base; /* 在栈构造之前和销毁之后,base 的值为NULL */ SElemType *top; /* 栈顶指针*/ int stacksize; /* 当前已分配的存储空间,以元素为单位*/ }SqStack; /* 顺序栈*/ (2)文件SqStackAlgo.h 中实现顺序栈的基本操作(存储结构由SqStackDef.h 定义) Status InitStack(SqStack &S) { /* 构造一个空栈S */ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); /* 存储分配失败*/ S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } int StackLength(SqStack S) { // 返回S 的元素个数,即栈的长度, 编写此函数 实验报告 学院(系)名称:计算机科学与工程学院 姓名赵振宇学号20175302 专业 计算机科学与技术 班级 2017级4班实验项目 实验三:图的遍历与应用 课程名称 数据结构与算法 课程代码 0661913 实验时间 2019年5月27日 第3、4节 实验地点 7-219 考核标准实验过程25分 程序运行20分 回答问题15分 实验报告30分 特色功能5分 考勤违纪情况5分 成绩 成绩栏 其它批改意见: 教师签字: 考核内容 评价在实验课堂中的表现,包括实验态度、编写程序过程等内容等。 □功能完善,□功能不全□有小错□无法运行 ○正确○基本正确○有提示○无法回答 ○完整○较完整 ○一般 ○内容极少○无报告 ○有 ○无 ○有 ○无一、实验目的 1、实验目的:通过实验使学生理解图的主要存储结构,掌握图的构造算法、图的深度优先和广度优先遍历算法,能运用图解决具体应用问题。 二、实验题目与要求 要求:第1题为必做题,2,3,4至少选一 1.输入指定的边数和顶点数建立图,并输出深度优先遍历和广度优先遍历的结果。 1)问题描述:在主程序中设计一个简单的菜单,分别调用相应的函数功能:1…图的建立2…深度优先遍历图3…广度优先遍历图0…结束 2)实验要求:在程序中定义下述函数,并实现要求的函数功能:CreateGraph():按从键盘的数据建立图 DFSGrahp():深度优先遍历图 BFSGrahp():广度优先遍历图 3)实验提示: 图的存储可采用邻接表或邻接矩阵; 图存储数据类型定义(邻接表存储) #define MAX_VERTEX_NUM8//顶点最大个数 typedef struct ArcNode {int adjvex; struct ArcNode*nextarc; int weight;//边的权 }ArcNode;//表结点 #define VertexType int//顶点元素类型 typedef struct VNode {int degree,indegree;//顶点的度,入度 VertexType data; ArcNode*firstarc; }Vnode/*头结点*/,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum;//顶点的实际数,边的实际数}ALGraph; 4)注意问题: 注意理解各算法实现时所采用的存储结构。 注意区别正、逆邻接。 2.教学计划编制问题 南京工程学院实验报告 操作的函数程序清单,分别用顺序表和链表结构完成,并在首页上表明团队名称、成员及个人的工作(函数),未来的成绩评定时将包含这一部分的团队成绩及个人的工作成绩。 一、实验目的 1.熟悉上机环境,进一步掌握语言的结构特点。 2.掌握线性表的顺序存储结构的定义及实现。 3.掌握线性表的链式存储结构——单链表的定义及实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21,23,14,5,56,17,31},然后在第i个位置插入元素68。 3.建立一个带头结点的单链表,结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、程序主要语句及作用(main函数程序清单) 程序1的主要代码(附简要注释) #include 实验目的 (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 数据结构实验3 《数据结构与算法》实验报告 实验序号:3 实验项目名称:链式表的操作学号1507112104 姓名陈忠表专业、班15商智实验地点指导教师林开标实验时间16.11.09 一、实验目的及要求 1. 通过实验理解单链表的逻辑结构; 2. 通过实验掌握单链表的基本操作和具体的函数实现。 二、实验设备(环境)及要求 微型计算机; windows 操作系统; Microsoft Visual Studio 6.0集成开发环境。 三、实验内容与步骤 链式表表示和实现线性表的如下: #include"stdio.h" #include"stdlib.h" typedef struct node //定义结点 { int data; //结点的数据域为整型 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自 定义LinkList单链表类型 LinkList CreatListR1(); //函数,用尾插入法建立带头结点的单链表 ListNode *LocateNode(LinkList head, int key); //函数,按值查找结点 void DeleteList(LinkList head,int key); //函数,删除指定值的结点 void printlist(LinkList head); //函数,打印链表中的所有值 void DeleteAll(LinkList head); //函数,删除所有结点,释放内存 //==========主函数============== void main() { int num; char ch; LinkList head; head=CreatListR1(); //用尾插入 法建立单链表,返回头指针 printlist(head); //遍历链表 输出其值 printf(" Delete node (y/n):"); //输入 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.熟悉上机环境,进一步掌握语言的结构特点。 2.掌握线性表的顺序存储结构的定义及实现。 3.掌握线性表的链式存储结构——单链表的定义及实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21,23,14,5,56,17,31},然后在第i个位置插入元素(学号)。 3.建立一个带头结点的单链表,结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、程序主要语句及作用 程序1的主要代码(附简要注释) #include p->rchild=NULL; p->data=n; } else if(n>p->data) p->rchild=initBST(n,p->rchild); else p->lchild=initBST(n,p->lchild); return p; } void inorder(BSTNODE *BT){ if(BT!=NULL){ inorder(BT->lchild); printf("%d",BT->data); inorder(BT->rchild); } } BSTNODE *search_btree(BSTNODE *root,int key) { if(!root) {printf("Emptu btree\n"); return root;} while(root->data!=key) { if(key 图实验 一,邻接矩阵的实现 1.实验目的 (1)掌握图的逻辑结构 (2)掌握图的邻接矩阵的存储结构 (3)验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 (1)建立无向图的邻接矩阵存储 (2)进行深度优先遍历 (3)进行广度优先遍历 3.设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template 《数据结构》实验报告 一、实验名称 实验三:排序 二、实验目的 通过本实验,加深对排序概念的理解,能够对三类不同排序方法进行复杂度分析。掌握简单排序方法、先进排序方法和基数排序方法的变化过程及算法设计与分析。 三、实验要求 (1)学生提前准备好实验报告,预习并熟悉实验步骤; (2)遵守实验室纪律,在规定的时间内完成要求的内容; (3)1~2人为1小组,实验过程中独立操作、相互学习; 四、实验内容及步骤 (一)选择排序算法的实现 1、正确设计程序,并编译、链接成可执行文件 (1)首先正确写出排序顺序表的结构体typedef struct SqList (2)正确写出选择排序算法SelectSort (3)写出主程序main ,提供输入与输出操作 本程序的特点是对于用户给定的一组关键字序列(49,38,65,49,76,13,27,52),采用选择排序将其变成一个有序表,并输出排序结果。详见附1。 2、进行程序测试 直接运行可执行文件,观察输出结果,结果正确,如图 1 所示。 图1 3、算法的时间复杂度分析 本算法为二重循环,基本操作为“比较”与“交换”,二者的时间复杂度均为O(n2),由于二者是顺序结构,因此算法的整体时间复杂度为T(n)= O(n2)。 (二)插入排序算法的实现 1、正确设计程序,并编译、链接成可执行文件 (1)首先正确写出排序顺序表的结构体typedef struct SqList (2)正确写出插入排序算法InsertSort (3)写出主程序main ,提供输入与输出操作 本程序的特点是对于用户给定的一组关键字序列(49,38,65,97,76,13,27,49),采用插入排序将其变成一个有序表,并输出排序结果。详见附2。数据结构实验三(顺序栈的基本操作)
数据结构实验报告格式
数据结构实验报告图实验
数据结构实验
数据结构实验报告
数据结构 实验报告三
数据结构实验报告全集
数据结构实验报告[3]
数据结构实验报告
数据结构实验报告模板
数据结构实验
数据结构实验三
数据结构实验报告
数据结构实验报告.
数据结构实验3
数据结构实验报告及心得体会
《数据结构》实验3实验报告
数据结构实验报告图实验
数据结构实验报告三