实验2 查找算法的实现和应用?实验目的
1. 熟练掌握静态查找表的查找方法;
2. 熟练掌握动态查找表的查找方法;
3. 掌握hash表的技术.
?实验内容
1.用二分查找法对查找表进行查找;
2.建立二叉排序树并对该树进行查找;
3.确定hash函数及冲突处理方法,建立一个hash表并实现查找。
程序代码
#include
using namespace std;
int main()
{
int arraay[10]={1,2,3,4,5,6,7,8,9,10};
int binary_search(int a[10],int t);
cout<<"Enter the target:";
int target;
cin>>target;
binary_search(arraay,target);
return 0;
}
int binary_search(int a[10],int t)
{
int bottom=0,top=9;
while(bottom { int mid=(bottom+top)/2; if(a[mid] bottom=mid+1; else top=mid; } if(top cout<<"Not present!"; else { int position=bottom; if(a[bottom]==t) cout<<"Success!"; else cout<<"Not present!"; } return 0; } 结果 二叉排序树 #include #include #include using namespace std; typedef int keyType; typedef struct Node { keyType key; struct Node* left; struct Node* right; struct Node* parent; }Node,*PNode; void inseart(PNode* root, keyType key) { PNode p = (PNode)malloc(sizeof(Node)); p -> key = key; p -> left = p -> right = p -> parent = NULL; if((*root) == NULL) { *root = p; return ; } if((*root)->left == NULL && (*root)->key > key) { p->parent=(*root); (*root)->left=p; return; } if((*root)->right == NULL && (*root)->key < key) { p->parent=(*root); (*root)->right=p; return; } if((*root) -> key > key) { inseart(&(*root) -> left, key); } else if((*root) -> key < key) { inseart(&(*root) -> right, key); } else return ; } PNode search(PNode root,keyType key) { if(root == NULL) { return NULL; } if(key > root -> key) { return search(root -> right, key); } else if(key < root -> key) { return search(root -> left, key); } else return root; } void create(PNode* root, keyType* keyArray, int length) { int i; for(i = 0; i < length; i++) { inseart(root, keyArray[i]); } } int main() { int i; PNode root = NULL; int a[100]; int n; scanf("%d",&n); for(i = 0; i < n; i++) { scanf("%d",&a[i]); } create(&root, a,n); int m; while(~scanf("%d",&m)){ if(search(root,m) ->key){ printf("YES\n"); } } return 0; } 结果 哈希hash #include //#include #include using namespace std; enum Result{ ok = 2, success = 1, unsuccess = 0, duplicate = -1, fail = -2, }; typedef int elemtype; typedef struct{ elemtype* elem; int count; int sizeindex; }hashTable; void Inithash(hashTable &H, int n){ H.elem = new elemtype[n]; H.count = 0; H.sizeindex = n; for(int i = 0; i < n; i++) { H.elem[i] = 0; } } int hash(elemtype K, int sizeindex) { // int count = H.count; int haAddr = K % sizeindex; return haAddr; } int SearchHash(hashTable &H, elemtype K, int &haAddr, int &c) { int d = 1; int sizeindex = H.sizeindex; haAddr = hash(K, sizeindex); while(H.elem[haAddr] != NULL && H.elem[haAddr] != K) { haAddr = (K % sizeindex + d) % sizeindex; d++; c++; cout<<"产生冲突,解决中…………"< if(c > H.sizeindex - 2) { cout<<"冲突次数过多,重新建立哈希表"< break; } } if(K == H.elem[haAddr]) { cout<<"chenggong"< return success; } else { cout<<"fail"< return unsuccess; } } int InsertHash(hashTable &H, elemtype e) { int collision = 0; int haAddr = -1; if(SearchHash(H, e, haAddr, collision) == success) { cout<<"存在该元素!!!"< return duplicate; } else if(collision < H.sizeindex - 2) H.elem[haAddr] = e; H.count++; cout<<"插入成功!!!"< return ok; } else { cout<<"冲突次数过多,重新建立哈希表"< return fail; } } int hashsearch(hashTable &H, elemtype e) { int p = 0; for(int i = 0; i < H.sizeindex; i++) { if(H.elem[i] == e) { //H.elem[i] == 0; p = 1; cout <<"hashaddress = "< if(p == 0) return unsuccess; else return success; } } } void PrintHash(hashTable H) { int num = 1; cout<<"哈希表为……!"< for(int i = 0; i < H.sizeindex; i++) { if(num % 10 == 0) cout < if(H.elem[i] != NULL) { cout < num++; } else continue; cout < } void Performance(hashTable &H){ //hashTable H; int sizeindex; cout <<"哈希表容量为……!"< cin >>sizeindex; Inithash(H, sizeindex); int e = 1; cout<<"输入插入元素,否则输入'0'"< cin>>e; while(e != 0) { InsertHash(H, e); cout<<"输入插入元素,否则输入'0'"< cin >>e; } PrintHash(H); int k = 1; cout<<"输入要查找元素:"; //int k; cin>>k; hashsearch(H,k); int status = hashsearch(H,k); if(!status) cout<<"该元素不存在"< } int main() { hashTable H; Performance(H); cin.get(); cin.get(); return 0; } 结果 实验2 查找算法的实现和应用?实验目的 1. 熟练掌握静态查找表的查找方法; 2. 熟练掌握动态查找表的查找方法; 3. 掌握hash表的技术. ?实验内容 1.用二分查找法对查找表进行查找; 2.建立二叉排序树并对该树进行查找; 3.确定hash函数及冲突处理方法,建立一个hash表并实现查找。 程序代码 #include cout<<"Not present!"; } return 0; } 结果 二叉排序树 #include 上机实验要求及规范 《数据结构》课程具有比较强的理论性,同时也具有较强的可应用性和实践性,因此上机实验是一个重要的教学环节。一般情况下学生能够重视实验环节,对于编写程序上机练习具有一定的积极性,但是容易忽略实验的总结,忽略实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。拿到一个题目,一般不要急于编程,而是应该按照面向过程的程序设计思路(关于面向对象的训练将在其它后继课程中进行),首先理解问题,明确给定的条件和要求解决的问题,然后按照自顶向下,逐步求精,分而治之的策略,逐一地解决子问题。具体步骤如下: 1.问题分析与系统结构设计 充分地分析和理解问题本身,弄清要求做什么(而不是怎么做),限制条件是什么。按照以数据结构为中心的原则划分模块,搞清数据的逻辑结构(是线性表还是树、图?),确定数据的存储结构(是顺序结构还是链表结构?),然后设计有关操作的函数。在每个函数模块中,要综合考虑系统功能,使系统结构清晰、合理、简单和易于调试。最后写出每个模块的算法头和规格说明,列出模块之间的调用关系(可以用图表示),便完成了系统结构设计。 2.详细设计和编码 详细设计是对函数(模块)的进一步求精,用伪高级语言(如类C语言)或自然语言写出算法框架,这时不必确定很多结构和变量。 编码,即程序设计,是对详细设计结果的进一步求精,即用某种高级语言(如C/C++语言)表达出来。尽量多设一些注释语句,清晰易懂。尽量临时增加一些输出语句,便于差错矫正,在程序成功后再删去它们。 3.上机准备 熟悉高级语言用法,如C语言。熟悉机器(即操作系统),基本的常用命令。静态检查主要有两条路径,一是用一组测试数据手工执行程序(或分模块进行);二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑,在这个过程中再加入一些注释和断言。如果程序中逻辑概念清楚,后者将比前者有效。 4.上机调试程序 调试最好分块进行,自底向上,即先调试底层函数,必要时可以另写一个调用驱动程序,表面上的麻烦工作可以大大降低调试时所面临的复杂性,提高工作效率。 5.整理实验报告 在上机实验开始之前要充分准备实验数据,在上机实践过程中要及时记录实验数据,在上机实践完成之后必须及时总结分析,写出实验报告。 一,实验题目 实验十一:图实验 采用邻接表存储有向图,设计算法判断任意两个顶点间手否存在路径。 二,问题分析 本程序要求采用邻接表存储有向图,设计算法判断任意两个顶点间手否存在路径,完成这些操作需要解决的关键问题是:用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 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]; //定义表头结点数组 重庆文理学院软件工程学院实验报告册 专业:_____软件工程__ _ 班级:_____软件工程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.实验目的 (1)掌握图的逻辑结构 (2)掌握图的邻接矩阵的存储结构 (3)验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 (1)建立无向图的邻接矩阵存储 (2)进行深度优先遍历 (3)进行广度优先遍历 3.设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template #include 数据结构实验报告 一.题目要求 1)编程实现二叉排序树,包括生成、插入,删除; 2)对二叉排序树进行先根、中根、和后根非递归遍历; 3)每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4)分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率,并说明在什么情况下二叉排序树效率高,为什么? 二.解决方案 对于前三个题目要求,我们用一个程序实现代码如下 #include 实验报告 实验六图的应用及其实现 一、实验目的 1.进一步功固图常用的存储结构。 2.熟练掌握在图的邻接表实现图的基本操作。 3.理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。 二、实验内容 一>.基础题目:(本类题目属于验证性的,要求学生独立完成) [题目一]:从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网 的类型定义和基本操作,完成上述功能。 [题目二]:从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 测试数据:教材图7.29 【题目五】连通OR 不连通 描述:给定一个无向图,一共n个点,请编写一个程序实现两种操作: D x y 从原图中删除连接x,y节点的边。 Q x y 询问x,y节点是否连通 输入 第一行两个数n,m(5<=n<=40000,1<=m<=100000) 接下来m行,每行一对整数 x y (x,y<=n),表示x,y之间有边相连。保证没有重复的边。 接下来一行一个整数 q(q<=100000) 以下q行每行一种操作,保证不会有非法删除。 输出 按询问次序输出所有Q操作的回答,连通的回答C,不连通的回答D 样例输入 3 3 1 2 1 3 2 3 5 Q 1 2 D 1 2 Q 1 2 D 3 2 Q 1 2 样例输出 C C D 【题目六】 Sort Problem An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not. 【Input】 Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n<= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. 1 <= m <= 100. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input. 【Output】 For each problem instance, output consists of one line. This line should be one of the following three: Sorted sequence determined: y y y… y. Sorted sequence cannot be determined. Inconsistency found. 长春大学计算机学院网络工程专业 数据结构实验报告 实验名称:实验二栈和队列的操作与应用 班级:网络14406 姓名:李奎学号:041440624 实验地点:日期: 一、实验目的: 1.熟练掌握栈和队列的特点。 2.掌握栈的定义和基本操作,熟练掌握顺序栈的操作及应用。 3.掌握链队的入队和出队等基本操作。 4.加深对栈结构和队列结构的理解,逐步培养解决实际问题的编程能力。 二、实验内容、要求和环境: 注:将完成的实验报告重命名为:班级+学号+姓名+(实验二),(如:041340538张三(实验二)),发邮件到:ccujsjzl@https://www.wendangku.net/doc/0b8950763.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 的元素个数,即栈的长度, 编写此函数 邻接矩阵的实现 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 姓名: 学号: 班级: 2010年12月15日 实验一线性表的应用 【实验目的】 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。、; 2、以线性表的各种操作(建立、插入、删除、遍历等)的实现为重点; 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现; 4、通过本章实验帮助学生加深对C语言的使用(特别是函数的参数调用、指针类型的 应用和链表的建立等各种基本操作)。 【实验内容】 约瑟夫问题的实现:n只猴子要选猴王,所有的猴子按1,2,…,n编号围坐一圈,从第一号开始按1,2…,m报数,凡报到m号的猴子退出圈外,如此次循环报数,知道圈内剩下一只猴子时,这个猴子就是猴王。编写一个程序实现上述过程,n和m由键盘输入。【实验要求】 1、要求用顺序表和链表分别实现约瑟夫问题。 2、独立完成,严禁抄袭。 3、上的实验报告有如下部分组成: ①实验名称 ②实验目的 ③实验内容:问题描述:数据描述:算法描述:程序清单:测试数据 算法: #include 实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列,要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include 求A QB #include 洛阳理工学院实验报告 附:源程序: #include { InsertBST(&((*bst)->lchild),key); return OK; } else if(key>(*bst)->key) { InsertBST(&((*bst)->rchild),key); return OK; } } void CreateBST(BSTree *bst) { int key; *bst=NULL; scanf("%d", &key); while (key!=ENDKEY) { InsertBST(bst, key); scanf("%d", &key); } } BSTree SearchBST(BSTree bst, int key) { if(!bst) return NULL; else if(bst->key==key) return bst; //查找成功 else if(bst->key>key) return SearchBST(bst->lchild,key); else return SearchBST(bst->rchild,key); 《数据结构》实验报告 实验序号:1 实验项目名称:概论 附源程序清单: 1. #include 2. #include 实验六图的应用及其实现 一、实验目的 1.进一步功固图常用的存储结构。 2.熟练掌握在图的邻接表实现图的基本操作。 3.理解掌握AOE网在邻接表上的实现及解决简单的应用问题。 二、实验内容 [题目]:从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 三、实验步骤 (一)、数据结构与核心算法的设计描述 本实验题目是基于图的基本操作以及邻接表的存储结构之上,着重拓扑排序算法的应用,做好本实验的关键在于理解拓扑排序算法的实质及其代码的实现。 (二)、函数调用及主函数设计 以下是头文件中数据结构的设计和相关函数的声明: typedef struct ArcNode // 弧结点 { int adjvex; struct ArcNode *nextarc; InfoType info; }ArcNode; typedef struct VNode //表头结点 { VertexType vexdata; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct //图的定义 { AdjList vertices; int vexnum,arcnum; int kind; }MGraph; typedef struct SqStack //栈的定义 { SElemType *base; SElemType *top; int stacksize; }SqStack; int CreateGraph(MGraph &G);//AOE网的创建 int CriticalPath(MGraph &G);//输出关键路径 (三)、程序调试及运行结果分析 (四)、实验总结 在做本实验的过程中,拓扑排具体代码的实现起着很重要的作用,反复的调试和测试占据着实验大量的时间,每次对错误的修改都加深了对实验和具体算法的理解,自己的查错能力以及其他各方面的能力也都得到了很好的提高。最终实验结果也符合实验的预期效果。 四、主要算法流程图及程序清单 1、主要算法流程图: 2、程序清单: 创建AOE网模块: int CreateGraph(MGraph &G) //创建有向网 { int i,j,k,Vi,Vj; ArcNode *p; cout<<"\n请输入顶点的数目、边的数目"< 附录A 实验报告 课程:数据结构(c语言)实验名称:图的建立、基本操作以及遍历系别:数字媒体技术实验日期: 12月13号 12月20号 专业班级:媒体161 组别:无 姓名:学号: 实验报告内容 验证性实验 一、预习准备: 实验目的: 1、熟练掌握图的结构特性,熟悉图的各种存储结构的特点及适用范围; 2、熟练掌握几种常见图的遍历方法及遍历算法; 实验环境:Widows操作系统、VC6.0 实验原理: 1.定义: 基本定义和术语 图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E),其中:V(G)是顶点(V ertex)的非空有限集E(G)是边(Edge)的有限集合,边是顶点的无序对(即:无方向的,(v0,v2))或有序对(即:有方向的, 无向图中顶点V i的度TD(V i)是邻接矩阵A中第i行元素之和有向图中, 顶点V i的出度是A中第i行元素之和 顶点V i的入度是A中第i列元素之和 邻接表 实现:为图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点Vi的边(有向图中指以Vi为尾的弧) 特点: 无向图中顶点Vi的度为第i个单链表中的结点数有向图中 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 逆邻接表:有向图中对每个结点建立以Vi为头的弧的单链表。 图的遍历 从图中某个顶点出发访遍图中其余顶点,并且使图中的每个顶点仅被访问一次过程.。遍历图的过程实质上是通过边或弧对每个顶点查找其邻接点的过程,其耗费的时间取决于所采用的存储结构。图的遍历有两条路径:深度优先搜索和广度优先搜索。当用邻接矩阵作图的存储结构时,查找每个顶点的邻接点所需要时间为O(n2),n为图中顶点数;而当以邻接表作图的存储结构时,找邻接点所需时间为O(e),e 为无向图中边的数或有向图中弧的数。 实验内容和要求: 选用任一种图的存储结构,建立如下图所示的带权有向图: 要求:1、建立边的条数为零的图; 数据结构教程 上机实验报告 实验七、图算法上机实现 一、实验目的: 1.了解熟知图的定义和图的基本术语,掌握图的几种存储结构。 2.掌握邻接矩阵和邻接表定义及特点,并通过实例解析掌握邻接矩阵和邻接表的类型定义。 3.掌握图的遍历的定义、复杂性分析及应用,并掌握图的遍历方法及其基本思想。 二、实验内容: 1.建立无向图的邻接矩阵 2.图的xx优先搜索 3.图的xx优先搜索 三、实验步骤及结果: 1.建立无向图的邻接矩阵: 1)源代码: #include "stdio.h" #include "stdlib.h" #define MAXSIZE 30 typedefstruct{charvertex[MAXSIZE];//顶点为字符型且顶点表的长度小于MAXSIZE intedges[MAXSIZE][MAXSIZE];//边为整形且edges为邻近矩阵 }MGraph;//MGraph为采用邻近矩阵存储的图类型 voidCreatMGraph(MGraph *g,inte,int n) {//建立无向图的邻近矩阵g->egdes,n为顶点个数,e为边数inti,j,k; printf("Input data of vertexs(0~n-1): \n"); for(i=0;i 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)测试数据:1)9 2)4500 三,概要设计 1.为了实现上述程序功能,需要: 构造一个空的顺序栈s 将十进制整数除以2的余数入栈 将余数按顺序出栈 2.本程序包含7个函数: 1)主函数main(); 2)顺序栈判栈空函数stackempty(seqstack *s) 3)顺序栈置空栈函数seqstack *initstack(seqstack *s) 4)顺序栈入栈函数push(seqstack *s,int x) 5)顺序栈出栈函数pop(seqstack *s) 6)顺序栈取栈顶元素函数gettop(seqstack *s) 7)将十进制数转换为二进制数函数setnum(int num) 各函数间关系如下: 四,详细设计 1,顺序表的结构类型定义: typedef struct{ int data[maxlen]; int top; }seqstack; 2,顺序栈入栈函数的伪代码: void push(seqstack *s,int x){ if(s->top<=maxlen-1&&s->top>=-1){ s->top++; s->data[s->top]=x;} else printf("error");} 3,顺序栈出栈函数的伪代码: void pop(seqstack *s){ if(s->top>=0) s->top--; else printf("error"); } 4,将十进制数转换为二进制数函数伪代码: void setnum(int num){ seqstack s; initstack(&s); while(num){ int k=num%2; push(&s,k); num=num/2;} while(!stackempty(&s)){ int x=gettop(&s); printf("%d",x); pop(&s); } } 五,源代码 #include "stdio.h" #define maxlen 100 typedef struct{ //定义顺序栈的结构类型 int data[maxlen]; int top; }seqstack; int stackempty(seqstack *s){ //顺序栈判栈空算法if(s->top>=0) return 0; else return 1; } seqstack *initstack(seqstack *s){ //顺序栈置空栈算法s->top=-1; return s; }数据结构实验
计10--数据结构专题实验rev2
数据结构实验十一:图实验
数据结构实验答案1
数据结构实验报告图实验
数据结构实验报告
数据结构_实验六_报告
数据结构实验
数据结构实验报告图实验
数据结构实验报告
数据结构实验
数据结构实验六
数据结构实验1
数据结构实验六 图的应用及其实现
数据结构实验报告(图)
数据结构图实验报告
数据结构实验报告及心得体会
数据结构实验六 堆栈实验