文档库 最新最全的文档下载
当前位置:文档库 › 数据结构实验十二

数据结构实验十二

数据结构实验十二
数据结构实验十二

一、实验目的

1.理解动态查找表的动态生成过程;

2.掌握二叉排序树的建立和查找;

二、实验环境

1.硬件:每个学生需配备计算机一台。操作系统:DOS或Windows;

2.软件:DOS或Windows操作系统+Turbo

c;

三、实验要求

1.定义二叉排序树的数据结构;

2.实现二叉排序树的插入算法与查找算法,并建立二叉排序树;

3.进行数据查找和建树过程的比较。

四、实验内容

1.已知一个个数为12的数据元素序列为{Dec,

Feb,Nov,Oct,June,Sept,Aug,Apr,May,Jul y,Jan,Mar},要求:

(1)按各数据元素的顺序构造一棵二叉排序树,并中序打印排序结果。

(2)查找数据“Sept”是否存在。

2.已知一棵二叉排序树,其根结点的地址为root。请编写一个程序,构造出一棵具有相同结点的满二叉树,且它同样是二叉排序树。提示:可利用中序遍历,分别找出各个结点序列的中点元素,然后重新构造一棵二叉树排序树。

五、代码如下

#include

#include

#define TRUE 1 #define FALSE 0

#define OK 1

#define ERROR 0

typedef int Status;

#define EQ(a,b)((a)==(b))

#define LT(a,b)((a)<(b))

#define LQ(a,b)((a)<=(b))

typedef int KeyType;

typedef struct{

KeyType key;//关键字

char others[5];//其他数据

}ElemType;

typedef struct BiTNode{

ElemType data;

struct BiTNode*lchild;

struct BiTNode*rchild;

}BiTNode,*BiTree;

void ylx_InitBiTree(BiTree &T){

T=NULL;//构造空二叉树

}// InitBiTree

void ylx_DestroyBiTree(BiTree &T){

if(T){ylx_DestroyBiTree(T->lchild);

ylx_DestroyBiTree(T->rchild);

free(T);

T=NULL;}

}// DestroyBiTree

void ylx_InOrderTraverse(BiTree T,void(*Visit)(ElemType)){

if(T){ylx_InOrderTraverse(T->lchild,Visi t);

Visit(T->data);

ylx_InOrderTraverse(T->rchild,Visit);}

}//InOrderTraverse

void ylx_Visit(ElemType c){

printf("%s\n",c.others);

}//Visit

void ylx_Input(ElemType &c){

scanf("%d%s",&c.key,c.others);

}//Input

void ylx_Inputkey(KeyType &k){

scanf("%d",&k);

}//Inputkey

BiTree ylx_SearchBST1(BiTree T,KeyType key){

if(!T||EQ(key,T->data.key))

return T;

else if LT(key,T->data.key)

return

ylx_SearchBST1(T->lchild,key);

else

return

ylx_SearchBST1(T->rchild,key);

}//SearchBST1

Status ylx_SearchBST(BiTree &T,KeyType key,BiTree f,BiTree &p){

if(!T){

p=f;//p指向查找路径上访问的最后一个结点

return FALSE;}

else if EQ(key,T->data.key){

p=T;//p指向该数据元素结点

return TRUE;}

else if LT(key,T->data.key)

return

ylx_SearchBST(T->lchild,key,T,p);

else//key大于T所指结点的关键字

return

ylx_SearchBST(T->rchild,key,T,p);

}// SearchBST

Status ylx_InsertBST(BiTree &T,ElemType e){

BiTree p,s;

if(!ylx_SearchBST(T,e.key,NULL,p)){

s=(BiTree)malloc(sizeof(BiTNode));

s->data=e;

s->lchild=s->rchild=NULL;

if(!p)//树T空

T=s;

else if LT(e.key,p->data.key)

p->lchild=s;

else

p->rchild=s;

return TRUE;}

else

return FALSE;

}//InsertBST

void main(){

int i,n;

BiTree t,p;

KeyType j;

ElemType r;

Status k;

printf("输入数据元素的个数:");

scanf("%d",&n);

ylx_InitBiTree(t);//构造空二叉树

printf("输入关键字(a-z或A-Z对应输入1-26)和数据:\n");

for(i=0;i

ylx_Input(r);

k=ylx_InsertBST(t,r);//将数据元素r插入二叉排序数树t中

if(!k)

printf("已存在关键字为%d的数据,故%s无法插入.\n",

r.key,r.others);}

printf("中序遍历二叉排序树为:\n");

ylx_InOrderTraverse(t,ylx_Visit);

printf("输入待查找的关键字的值:");

ylx_Inputkey(j);

p=ylx_SearchBST1(t,j);//递归查找等于j 的关键字的结点

if(p){

printf("关键字为%d的结点%s存在\n",

j,p->data.others);}

else

ylx_DestroyBiTree(t);//销毁二叉排序树

}

六、运行结果截图

数据结构实验答案1

重庆文理学院软件工程学院实验报告册 专业:_____软件工程__ _ 班级:_____软件工程2班__ _ 学号:_____201258014054 ___ 姓名:_____周贵宇___________ 课程名称:___ 数据结构 _ 指导教师:_____胡章平__________ 2013年 06 月 25 日

实验序号 1 实验名称实验一线性表基本操作实验地点S-C1303 实验日期2013年04月22日 实验内容1.编程实现在顺序存储的有序表中插入一个元素(数据类型为整型)。 2.编程实现把顺序表中从i个元素开始的k个元素删除(数据类型为整型)。 3.编程序实现将单链表的数据逆置,即将原表的数据(a1,a2….an)变成 (an,…..a2,a1)。(单链表的数据域数据类型为一结构体,包括学生的部分信息:学号,姓名,年龄) 实验过程及步骤1. #include #include #include #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define ElemType int #define MAXSIZE 100 /*此处的宏定义常量表示线性表可能达到的最大长度*/ typedef struct

{ 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)隐含在各部分的技术和方法丰富,也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性,设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练,突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时,觉得无从下手,做起来特别费劲。实验中的内容和教科书的内容是密切相关的,解决题目要求所需的各种技术大多可从教科书中找到,只不过其出现的形式呈多样化,因此需要仔细体会,在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程,理解和掌握算法设计所需的技术,为整个专业学习打好基础,要求运用所学知识,上机解决一些典型问题,通过分析、设计、编码、调试等各环节的训练,使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法,如算法设计的构思方法,动态链表,算法的编码,递归技术,与特定问题相关的技术等,要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上,掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时,要求完成以下六个题目: 实习一约瑟夫环问题(2学时)

数据结构实验二11180

理工学院实验报告 系部计算机系班级学号 课程名称数据结构实验日期 实验名称链表的基本操作成绩 实验目的: (1)掌握线性表的链式存储结构的特点; (2)掌握线性表的基本操作:初始化、插入、删除、查找数据元素等运算在链式存储结构上的实现。 实验条件:计算机一台,vc++6.0 实验容与算法思想: 容: 建立一有序的链表,实现下列操作: 1.把元素x插入表中并保持链表的有序性; 2.查找值为x的元素,若找到将其删除; 3.输出表中各元素的值。 算法思想:先创建并初始化一个顺序表(void init_linklist(LinkList)),通过循环,输入一串数据void CreateFromTail(LinkList L);创建主函数;编写算法,完成子函数(查找locate,插入insList,删除DelList,输出output)模块;调用子函数,完成实验要求 运行结果:

附:源程序: #include #include #define OK 1 #define ERROR 0 typedef char ElemType; typedef struct Node { ElemType data; struct Node* next; }Node,*LinkList; void init_linklist(LinkList *l) { *l=(LinkList)malloc(sizeof(Node)); (*l)->next=NULL; } void CreateFromTail(LinkList L) { Node *r, *s; char c; int flag =1; r=L; while(flag) { c=getchar(); if(c!='$') {

数据结构课程实验指导书

数据结构实验指导书 一、实验目的 《数据结构》是计算机学科一门重要的专业基础课程,也是计算机学科的一门核心课程。本课程较为系统地论述了软件设计中常用的数据结构以及相应的存储结构与实现算法,并做了相应的性能分析和比较,课程内容丰富,理论系统。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因,使得掌握这门课程具有较大的难度: 1)理论艰深,方法灵活,给学习带来困难; 2)内容丰富,涉及的知识较多,学习有一定的难度; 3)侧重于知识的实际应用,要求学生有较好的思维以及较强的分析和解决问题的能力,因而加大了学习的难度; 根据《数据结构》课程本身的特性,通过实验实践内容的训练,突出构造性思维训练的特征,目的是提高学生分析问题,组织数据及设计大型软件的能力。 课程上机实验的目的,不仅仅是验证教材和讲课的内容,检查自己所编的程序是否正确,课程安排的上机实验的目的可以概括为如下几个方面: (1)加深对课堂讲授内容的理解 实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常,实验题中的问题比平时的习题复杂得多,也更接近实际。实验着眼于原理与应用的结合点,使学生学会如何把书上学到的知识用于解决实际问题,培养软件工作所需要的动手能力;另一方面,能使书上的知识变" 活" ,起到深化理解和灵活掌握教学内容的目的。 不少学生在解答习题尤其是算法设计时,觉得无从下手。实验中的内容和教科书的内容是密切相关的,解决题目要求所需的各种技术大多可从教科书中找到,只不过其出

现的形式呈多样化,因此需要仔细体会,在反复实践的过程中才能掌握。 (2) 培养学生软件设计的综合能力 平时的练习较偏重于如何编写功能单一的" 小" 算法,而实验题是软件设计的综合训练,包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧,多人合作,以至一整套软件工作规范的训练和科学作风的培养。 通过实验使学生不仅能够深化理解教学内容,进一步提高灵活运用数据结构、算法和程序设计技术的能力,而且可以在需求分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点,使学生学会如何把书本上和课堂上学到的知识用于解决实际问题,从而培养计算机软件工作所需要的动手能力。 (3) 熟悉程序开发环境,学习上机调试程序一个程序从编辑,编译,连接到运行,都要在一定的外部操作环境下才能进行。所谓" 环境" 就是所用的计算机系统硬件,软件条件,只有学会使用这些环境,才能进行 程序开发工作。通过上机实验,熟练地掌握程序的开发环境,为以后真正编写计算机程序解决实际问题打下基础。同时,在今后遇到其它开发环境时就会触类旁通,很快掌握新系统的使用。 完成程序的编写,决不意味着万事大吉。你认为万无一失的程序,实际上机运行时可能不断出现麻烦。如编译程序检测出一大堆语法错误。有时程序本身不存在语法错误,也能够顺利运行,但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误,只能靠自己的上机经验分析判断错误所在。程序的调试是一个技巧性很强的工作,尽快掌握程序调试方法是非常重要的。分析问题,选择算法,编好程序,只能说完成一半工作,另一半工作就是调试程序,运行程序并得到正确结果。 二、实验要求 常用的软件开发方法,是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题目的远不如从实际问题中的复杂程度度高,但为了培养一个软件工作者所应具备的科学工作的方法和作风,也应遵循以下五个步骤来完成实验题目: 1) 问题分析和任务定义 在进行设计之前,首先应该充分地分析和理解问题,明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型,而是对所需完成的任务作出明确的回答。例如:输入数据的类型、值的范围以及输入的

数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1.实验目的 (1)掌握使用Visual C++ 6.0上机调试程序的基本方法; (2)掌握线性表的基本操作:初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2.实验要求 (1)认真阅读和掌握和本实验相关的教材内容。 (2)认真阅读和掌握本章相关内容的程序。 (3)上机运行程序。 (4)保存和打印出程序的运行结果,并结合程序进行分析。 (5)按照你对线性表的操作需要,重新改写主程序并运行,打印出文件清单和运行结果 实验代码: 1)头文件模块 #include iostream.h>//头文件 #include//库头文件-----动态分配内存空间 typedef int elemtype;//定义数据域的类型 typedef struct linknode//定义结点类型 { elemtype data;//定义数据域 struct linknode *next;//定义结点指针 }nodetype; 2)创建单链表

nodetype *create()//建立单链表,由用户输入各结点data域之值,//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"<> d; if(d==0) break;//以0表示输入结束 if(i==1)//建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));//表示指针h h->data=d;h->next=NULL;t=h;//h是头指针 } else//建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t始终指向生成的单链表的最后一个节点

数据结构实验报告

数据结构实验报告 一.题目要求 1)编程实现二叉排序树,包括生成、插入,删除; 2)对二叉排序树进行先根、中根、和后根非递归遍历; 3)每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4)分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率,并说明在什么情况下二叉排序树效率高,为什么? 二.解决方案 对于前三个题目要求,我们用一个程序实现代码如下 #include #include #include #include "Stack.h"//栈的头文件,没有用上 typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL) { T = (BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1; } else if(keydata){ InsertBST(T->lChild,key); } else if(key>T->data){ InsertBST(T->rChild,key); } else return 0; } BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL; inti=0; while(i

数据结构实验二

洛阳理工学院实验报告 系部计算机系班级学号姓名 课程名称数据结构实验日期 实验名称链表的基本操作成绩 实验目的: (1)掌握线性表的链式存储结构的特点; (2)掌握线性表的基本操作:初始化、插入、删除、查找数据元素等运算在链式存储结构上的实现。 实验条件:计算机一台,vc++6.0 实验内容与算法思想: 内容: 建立一有序的链表,实现下列操作: 1.把元素x插入表中并保持链表的有序性; 2.查找值为x的元素,若找到将其删除; 3.输出表中各元素的值。 算法思想:先创建并初始化一个顺序表(void init_linklist(LinkList)),通过循环,输入一串数据void CreateFromTail(LinkList L);创建主函数;编写算法,完成子函数(查找locate,插入insList,删除DelList,输出output)模块;调用子函数,完成实验要求 运行结果:

附:源程序: #include #include #define OK 1 #define ERROR 0 typedef char ElemType; typedef struct Node { ElemType data; struct Node* next; }Node,*LinkList; void init_linklist(LinkList *l) { *l=(LinkList)malloc(sizeof(Node)); (*l)->next=NULL; } void CreateFromTail(LinkList L) { Node *r, *s; char c; int flag =1; r=L; while(flag) { c=getchar(); if(c!='$') {

实验指导-数据结构B教案资料

实验指导-数据结构B

附录综合实验 1、实验目的 本课程的目标之一是使得学生学会如何从问题出发,分析数据,构造求解问题的数据结构和算法,培养学生进行较复杂程序设计的能力。本课程实践性较强,为实现课程目标,要求学生完成一定数量的上机实验。从而一方面使得学生加深对课内所学的各种数据的逻辑结构、存储表示和运算的方法等基本内容的理解,学习如何运用所学的数据结构和算法知识解决应用问题的方法;另一方面,在程序设计方法、C语言编程环境以及程序的调试和测试等方面得到必要的训练。 2、实验基本要求: 1)学习使用自顶向下的分析方法,分析问题空间中存在哪些模块,明确这些模块之间的关系。 2)使用结构化的系统设计方法,将系统中存在的各个模块合理组织成层次结构,并明确定义各个结构体。确定模块的主要数据结构和接口。 3)熟练使用C语言环境来实现或重用模块,从而实现系统的层次结构。模块的实现包括结构体的定义和函数的实现。 4)学会利用数据结构所学知识设计结构清晰的算法和程序,并会分析所设计的算法的时间和空间复杂度。 5)所有的算法和实现均使用C语言进行描述,实验结束写出实验报告。

3、实验项目与内容: 1、线性表的基本运算及多项式的算术运算 内容:实现顺序表和单链表的基本运算,多项式的加法和乘法算术运算。 要求:能够正确演示线性表的查找、插入、删除运算。实现多项式的加法和乘法运算操作。 2、二叉树的基本操作及哈夫曼编码译码系统的实现 内容:创建一棵二叉树,实现先序、中序和后序遍历一棵二叉树,计算二叉树结点个数等操作。哈夫曼编码/译码系统。 要求:能成功演示二叉树的有关运算,实现哈夫曼编码/译码的功能,运算完毕后能成功释放二叉树所有结点占用的系统内存。 3、图的基本运算及智能交通中的最佳路径选择问题 内容:在邻接矩阵和邻接表两种不同存储结构上实现图的基本运算的算法,实现图的深度和宽度优先遍历算法,解决智能交通中的路径选择问题。设有n 个地点,编号为0~n-1,m条路径的起点、终点和代价由用户输入提供,寻找最佳路径方案(例如花费时间最少、路径长度最短、交通费用最小等,任选其一即可)。 要求:设计主函数,测试上述运算。 4、各种内排序算法的实现及性能比较 内容:验证教材的各种内排序算法。分析各种排序算法的时间复杂度。 要求:使用随机数产生器产生较大规模数据集合,运行上述各种排序算法,使用系统时钟测量各算法所需的实际时间,并进行比较。

数据结构实验报告-答案

数据结构(C语言版) 实验报告

专业班级学号姓名 实验1 实验题目:单链表的插入和删除 实验目的: 了解和掌握线性表的逻辑结构和链式存储结构,掌握单链表的基本算法及相关的时间性能分析。 实验要求: 建立一个数据域定义为字符串的单链表,在链表中不允许有重复的字符串;根据输入的字符串,先找到相应的结点,后删除之。 实验主要步骤: 1、分析、理解给出的示例程序。 2、调试程序,并设计输入数据(如:bat,cat,eat,fat,hat,jat,lat,mat,#),测 试程序的如下功能:不允许重复字符串的插入;根据输入的字符串,找到相应的结点并删除。 3、修改程序: (1)增加插入结点的功能。 (2)将建立链表的方法改为头插入法。 程序代码: #include"" #include"" #include"" #include"" typedef struct node . . 示意图:

head head head 心得体会: 本次实验使我们对链表的实质了解更加明确了,对链表的一些基本操作也更加熟练了。另外实验指导书上给出的代码是有一些问题的,这使我们认识到实验过程中不能想当然的直接编译执行,应当在阅读并完全理解代码的基础上再执行,这才是实验的意义所在。

实验2 实验题目:二叉树操作设计和实现 实验目的: 掌握二叉树的定义、性质及存储方式,各种遍历算法。 实验要求: 采用二叉树链表作为存储结构,完成二叉树的建立,先序、中序和后序以及按层次遍历 的操作,求所有叶子及结点总数的操作。 实验主要步骤: 1、分析、理解程序。 2、调试程序,设计一棵二叉树,输入完全二叉树的先序序列,用#代表虚结点(空指针), 如ABD###CE##F##,建立二叉树,求出先序、中序和后序以及按层次遍历序列,求 所有叶子及结点总数。 实验代码 #include"" #include"" #include"" #define Max 20 ertex=a; irstedge=NULL; irstedge; G->adjlist[i].firstedge=s; irstedge; R[i] 留在原位

数据结构实验十一:图实验

一,实验题目 实验十一:图实验 采用邻接表存储有向图,设计算法判断任意两个顶点间手否存在路径。 二,问题分析 本程序要求采用邻接表存储有向图,设计算法判断任意两个顶点间手否存在路径,完成这些操作需要解决的关键问题是:用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1,数据的输入形式和输入值的范围:输入的图的结点均为整型。 2,结果的输出形式:输出的是两结点间是否存在路径的情况。 3,测试数据:输入的图的结点个数为:4 输入的图的边得个数为:3 边的信息为:1 2,2 3,3 1 三,概要设计 (1)为了实现上述程序的功能,需要: A,用邻接表的方式构建图 B,深度优先遍历该图的结点 C,判断任意两结点间是否存在路径 (2)本程序包含6个函数: a,主函数main() b,用邻接表建立图函数create_adjlistgraph() c,深度优先搜索遍历函数dfs() d,初始化遍历数组并判断有无通路函数dfs_trave() e,输出邻接表函数print() f,释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示: 四,详细设计 (1)邻接表中的结点类型定义:

typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; (2)邻接表中头结点的类型定义: typedef struct{ char vexdata; arcnode *firstarc; }adjlist; (3)邻接表类型定义: typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; (4)深度优先搜索遍历函数伪代码: int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } (5)初始化遍历数组并判断有无通路函数伪代码: void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五,源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组

《数据结构》实验指导

《数据结构》实验指导 (计算机信息大类适用) 实验报告至少包含以下内容: 实验名称 实验目的与要求: 实验内容与步骤(需要你进行细化): 实验结果(若顺利完成,可简单说明;若实验过程中遇到问题,也请在此说明) 收获与体会(根据个人的实际情况进行说明,不得空缺) 实验1 大整数加法(8课时) 目的与要求: 1、线性表的链式存储结构及其基本运算、实现方法和技术的训练。 2、单链表的简单应用训练。 3、熟悉标准模版库STL中的链表相关的知识。 内容与步骤: 1、编程实现单链表的基本操作。 2、利用单链表存储大整数(大整数的位数不限)。 3、利用单链表实现两个大整数的相加运算。 4、进行测试,完成HLOJ(https://www.wendangku.net/doc/fb16348110.html,) 9515 02-线性表大整数A+B。 5、用STL之list完成上面的任务。 6、尝试完成HLOJ 9516 02-线性表大菲波数。 实验2 栈序列匹配(8课时) 目的与要求 1、栈的顺序存储结构及其基本运算、实现方法和技术的训练。 2、栈的简单应用训练。 3、熟悉标准模版库STL中的栈相关的知识。 内容与步骤: 1、编程实现顺序栈及其基本操作。 2、对于给出的入栈序列和出栈序列,判断2个序列是否相容。即:能否利用栈 将入栈序列转换为出栈序列。 3、进行测试,完成HLOJ 9525 03-栈与队列栈序列匹配。 4、用STL之stack完成上面的任务。 5、尝试完成HLOJ 9522 03-栈与队列胡同。

实验3 二叉排序树(8课时) 目的与要求 1、二叉树的链式存储结构及其基本运算、实现方法和技术的训练。 2、二叉树的遍历方法的训练。 3、二叉树的简单应用。 内容与步骤: 1、编程实现采用链式存储结构的二叉排序树。 2、实现插入节点的操作。 3、实现查找节点的操作(若查找失败,则将新节点插入二叉排序树)。 4、利用遍历算法对该二叉排序树中结点的关键字按递增和递减顺序输出,完成 HLOJ 9576 07-查找二叉排序树。 5、尝试利用二叉排序树完成HLOJ 9580 07-查找Let the Balloon Rise。 实验4 最小生成树(8课时) 目的与要求 1、图的邻接矩阵存储结构及其相关运算的训练。 2、掌握最小生成树的概念。 3、利用Prim算法求解最小生成树。 实验背景: 给定一个地区的n个城市间的距离网,用Prim算法建立最小生成树,并计算得到的最小生成树的代价。要求显示得到的最小生成树中包括了哪些城市间的道路,并显示得到的最小生成树的代价。 内容与步骤: 1、建立采用邻接矩阵的图。 2、编程实现Prim算法,求解最小生成树的代价。 3、尝试利用Prim算法完成:HLOJ 9561 06-图最小生成树。

数据结构实验报告模板

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&List) //单链表排序 ListClear(&L); //将单链表L中的所有元素删除,使单链表变为空表 ListDestroy(&L);//将单链表销毁 }ADT List 其他函数: 主函数; 结点类; 约瑟夫函数 2.1 存储结构

[内容要求] 1、存储结构:顺序表、单链表或其他存储结构,需要画示意图,可参考书上P59 页图2-9 2.2 关键算法分析 结点类: template class CirList;//声明单链表类 template class ListNode{//结点类定义; friend class CirList;//声明链表类LinkList为友元类; Type data;//结点的数据域; ListNode*next;//结点的指针域; public: ListNode():next(NULL){}//默认构造函数; ListNode(const Type &e):data(e),next(NULL){}//构造函数 Type & GetNodeData(){return data;}//返回结点的数据值; ListNode*GetNodePtr(){return next;}//返回结点的指针域的值; void SetNodeData(Type&e){data=e;}//设置结点的数据值; void SetNodePtr(ListNode*ptr){next=ptr;} //设置结点的指针值; }; 单循环链表类: templateclass CirList { ListNode*head;//循环链表头指针 public: CirList(){head=new ListNode();head->next=head;}//构造函数,建立带头节点的空循环链表 ~CirList(){CirListClear();delete head;}//析构函数,删除循环链表 void Clear();//将线性链表置为空表 void AddElem(Type &e);//添加元素 ListNode *GetElem(int i)const;//返回单链表第i个结点的地址 void CirListClear();//将循环链表置为空表 int Length()const;//求线性链表的长度 ListNode*ListNextElem(ListNode*p=NULL);//返回循环链表p指针指向节点的直接后继,若不输入参数,则返回头指针 ListNode*CirListRemove(ListNode*p);//在循环链表中删除p指针指向节点的直接后继,且将其地址通过函数值返回 CirList&operator=(CirList&List);//重载赋

2017数据结构实验指导书

《数据结构》实验指导书 贵州大学 电子信息学院 通信工程

目录 实验一顺序表的操作 (3) 实验二链表操作 (8) 实验三集合、稀疏矩阵和广义表 (19) 实验四栈和队列 (42) 实验五二叉树操作、图形或网状结构 (55) 实验六查找、排序 (88) 贵州大学实验报告 (109)

实验一顺序表的操作 实验学时:2学时 实验类型:验证 实验要求:必修 一、实验目的和要求 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。 2、以线性表的各种操作(建立、插入、删除等)的实现为重点。 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现。 二、实验内容及步骤要求 1、定义顺序表类型,输入一组整型数据,建立顺序表。 typedef int ElemType; //定义顺序表 struct List{ ElemType *list; int Size; int MaxSize; }; 2、实现该线性表的删除。 3、实现该线性表的插入。 4、实现线性表中数据的显示。 5、实现线性表数据的定位和查找。 6、编写一个主函数,调试上述算法。 7、完成实验报告。 三、实验原理、方法和手段 1、根据实验内容编程,上机调试、得出正确的运行程序。 2、编译运行程序,观察运行情况和输出结果。 四、实验条件 运行Visual c++的微机一台 五、实验结果与分析 对程序进行调试,并将运行结果进行截图、对所得到的的结果分析。 六、实验总结 记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等,并将其写入实验报告中。

【附录----源程序】 #include #include using namespace std; typedef int ElemType; struct List { ElemType *list; int Size; int MaxSize; }; //初始化线性表 bool InitList(List &L) { L.MaxSize=20; L.list=new ElemType[L.MaxSize]; for(int i=0;i<20&&L.list==NULL;i++) { L.list=new ElemType[L.MaxSize]; } if(L.list==NULL) { cout<<"无法分配内存空间,退出程序"<L.Size+1||pos<1) { cout<<"位置无效"<

数据结构实验1

《数据结构》实验报告 实验序号:1 实验项目名称:概论

附源程序清单: 1. #include void main() { int i; int num[10]; int *p; for(i=0;i<=9;i++) num[i]=i+1; for(p=(num+9);p>=(num+0);p--) printf("%d ",*p); printf("\n"); }

2. #include void main() { void swap(int *a,int *b); int i; int a[10]; int *p,*max,*min; for(i=0;i<10;i++) scanf("%d",&a[i]); max=min=a; for(i=0;i<10;i++) { if(*maxa[i]) min=&a[i]; } p=a; swap(p,max); swap((p+9),min); for(p=a;p<=(a+9);p++) printf("%d ",*p); printf("\n"); } void swap(int *a,int *b) { int temp; temp=*a; *a=*b; *b=temp; } 3. #include #include #include #include typedef struct { char num[5]; char name[20]; float score1; float score2; float score3; float average;

数据结构实验指导书及答案(徐州工程学院)

《数据结构实验》实验指导书及答案

信电工程学院计算机科学和技术教研室编 2011.12 数据结构实验所有代码整理 作者郑涛 声明:在这里我整理了数据结构实验的所有代码,希望能对大家的数据结构实验的考试有所帮助,大家可以有选择地浏览,特别针对一些重点知识需要加强记忆(ps:重点知识最好让孙天凯给出),希望大家能够在数据结构实验的考试中取得令人满意的成绩,如果有做的 不好的地方请大家谅解并欢迎予以指正。 实验一熟悉编程环境 实验预备知识: 1.熟悉本课程的语言编译环境(TC或VC),能够用C语言编写完整的程序,并能够发现和改正错误。 2.能够灵活的编写C程序,并能够熟练输入C程序。 一、实验目的 1.熟悉C语言编译环境,掌握C程序的编写、编译、运行和调试过程。 2.能够熟练的将C程序存储到指定位置。 二、实验环境 ⒈硬件:每个学生需配备计算机一台。 ⒉软件:Windows操作系统+Turbo C; 三、实验要求 1.将实验中每个功能用一个函数实现。 2.每个输入前要有输入提示(如:请输入2个整数当中用空格分割:),每个输出数据都要求有内容说明(如:280和100的和是:380。)。 3.函数名称和变量名称等用英文或英文简写(每个单词第一个字母大写)形式说明。 四、实验内容 1.在自己的U盘中建立“姓名+学号”文件夹,并在该文件夹中创建“实验1”文件夹(以后每次实验分别创建对应的文件夹),本次实验的所有程序和数据都要求存储到本文件夹中(以后实验都按照本次要求)。

2.编写一个输入某个学生10门课程成绩的函数(10门课程成绩放到结构体数组中,结构体包括:课程编号,课程名称,课程成绩)。 3.编写一个求10门成绩中最高成绩的函数,输出最高成绩和对应的课程名称,如果有多个最高成绩,则每个最高成绩均输出。 4.编写一个求10门成绩平均成绩的函数。 5.编写函数求出比平均成绩高的所有课程及成绩。 #include #include struct subject { int subject_id; char subject_name[20]; double subject_grades; }; struct subject sub[10]; void input() { int i; printf("please input:\n"); for(i=0;i<10;i++) { scanf("%d %s %lf",&sub[i].subject_id,&sub[i].subject_name,&sub[i].subject_g rades); } printf("you just input:\n"); for(i=0;i<3;i++) { printf("%d %s %lf\n",sub[i].subject_id,sub[i].subject_name,sub[i].subject_g rades); } } void subject_max() { int i,flag; double max=sub[0].subject_grades; for(i=0;i<10;i++) { if(sub[i].subject_grades>max)

数据结构实验报告及心得体会

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;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1; } for(i=0;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1;

数据结构实验

实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列,要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include main() { intn,m,i=0,j=0,k=0,a[5],b[5],c[10];/* 必须设个m做为数组的输入的计数器,不能用i ,不然进行到while 时i 直接为5*/ for(m=0;m<=4;m++)scanf("%d",&a[m]);// 输入数组a for(m=0;m<=4;m++)scanf("%d",&b[m]);// 输入数组b while(i<5&&j<5) {if(a[i]b[j]){c[k]=b[j];k++;j++;} else{c[k]=a[i];k++;i++;j++;}// 使输入的两组数组中相同的数只输出一 个 } if(i<5) for(n=i;n<5;n++) {c[k]=a[n];k++;} elseif(j<5) for(n=j;n<5;n++) {c[k]=b[n];k++;} for(i=0;i

求A QB #include main() { inti,j,k=0,a[5],b[5],c[5];//A=a[5],B=b[5],A n B=c[5] for(i=0;i<5;i++)scanf("%d",&a[i]);// 输入a 数组 for(i=0;i<5;i++)scanf("%d",&b[i]);〃输入b 数组 for(i=0;i<5;i++) {for(j=0;j<5;j++) if(a[i]==b[j]){c[k]=a[i];k++;}// 当有元素重复时,只取一个放入 c 中} for(i=0;i #defineN4 main() { inti,j,m,k,a[N+1];//k 为最后输出数组的长度变量

相关文档