当前位置:文档之家› 东北大学数据结构实验一

东北大学数据结构实验一

实 验 报 告

一、实验目的 对队列的理解

对STL 中的queue 的使用

实验仿真一个网络打印过程

二、实验内容与实验步骤流程图

这个任务队列的测试使用STL 队列适配器。程序要求完成模拟的实现共享打印机。这个打印机使用先进先出队列。仿真是通过读取和处理事件数据文件的列表。一个有效的数据文件中的每一行包含信息打印作业和提交这份工作的时间。

具体地说,每一行中包含的信息是提交工作的时间(以秒为单位),和在页面的工作长及工作的计算机的名称。在模拟的开始,每个这些事件的每一个应该被程序所读,存储在继承工作负载队列。程序应该通过循环递增计数器或while-loop 模拟时间的流逝。程序应该将计数器初始化为零,然后依次增加1秒。当模拟等于当前时间的打印作业的提交时间在工作队列的前面,一个打印作业完成。当这一切发生的时候,从工作队列取出这个事件,然后把它放在另一个队列对象。这课程名称:数据结构 班级:软件赴日 实验成绩:

实验名称:打印机队列模拟程序的设计

学号:201247 批阅教师签字: 实验编号:实验一

姓名:袁 实验日期:2014年5 月 24 日 指导教师:

组号: 实验时间: 时 分- 时 分

个队列对象存储已完成的打印作业。当程序仿真其他的打印工作的时候,这些工作在队列等待。

Win8,Visual C++ 6.0

四、实验过程与分析

(1)实验主要函数及存储结构

main.cpp –包括主函数和主要的功能

simulator.h –仿真类的声明

simulator.cpp –仿真类的定义

event.h –事件类的声明

event.cpp - 事件类的定义

job.h –作业类的声明

job.cpp –作业类的定义

arbitrary.run –包括任意打印作业数的数据文件

arbitrary.out –输出arbitrary.run

bigfirst.run –包括打印较大作业的数据文件

bigfirst.out –输出bigfirst.run

(2)实验代码

#ifndef FIFO_H //fifo.h

#define FIFO_H

#include "simulator.h"

class fifo:public simulator{

protected:

queue waiting;

priority_queue priority_waiting;

public:

fifo(int seconds_per_page);

void simulate(string file);

};

bool operator < (event evtleft,event evtright);

#endif

#include "fifo.h" //fifo.cpp

#include

using namespace std;

fifo::fifo(int seconds_per_page):simulator(seconds_per_page){

}

void fifo::simulate(string file){

int finish_time = 0;

float agg_latency = 0;

int totaljob =0;

event evt;

if(file.find("arbitrary")!= string::npos){

string outfile ="arbitrary.out";

ofstream osf(outfile.c_str());

loadworkload(file);

osf<<"FIFO Simulation\n"<

for(int time =1;!waiting.empty()||!workload.empty();time++){

while(!workload.empty() && time == workload.front().arrival_time()){ evt= workload.front();

osf<<"\tArriving: "<

waiting.push(workload.front());

workload.pop();

}

if(!waiting.empty() && time >= finish_time){

totaljob ++;

evt = waiting.front();

agg_latency += time - evt.arrival_time();

osf<<"\tServicing: "<

waiting.pop();

finish_time = time + evt.getjob().getnumpages() * seconds_per_page;

}

}

osf<<"\n\ttotal job "<

osf<<"\taggregate latency: "<

osf<<"\tmean latency : "<

cout<<"The log file name is arbitrary.out"<

return;

}

if(file.find("bigfirst") != string::npos){

string outfile = "bigfirst.out";

ofstream osf(outfile.c_str());

loadworkload(file);

osf<<"FIFO Simulation\n"<

for(int time =1;!priority_waiting.empty()||!workload.empty();time++){ while(!workload.empty() && time == workload.front().arrival_time()){

evt= workload.front();

osf<<"\tArriving: "<

priority_waiting.push(workload.front());

workload.pop();

}

if(!priority_waiting.empty() && time >= finish_time){

totaljob ++;

evt = priority_waiting.top();

agg_latency += time - evt.arrival_time();

osf<<"\tServicing: "<

priority_waiting.pop();

finish_time = time + evt.getjob().getnumpages() * seconds_per_page;

}

}

osf<<"\n\ttotal job "<

osf<<"\taggregate latency: "<

osf<<"\tmean latency : "<

cout<<"The log file name is bigfirst.out"<

return;

}

cerr<<"The program don't know what algorithm to use"<

cerr<<"You should specify the file name with arbitrary or bigfirst"<

}

bool operator < (event evtleft,event evtright){

return evtleft.getjob().getnumpages() < evtright.getjob().getnumpages();

}

五、实验结果总结

经测试,功能较为完整。代码流程简图如下:

通过这次实验,我了解了有关队列方面的知识。掌握了队列的逻辑结构,抽象数据类型,队列的存储方式等。运用先进先出表,仿真了网络打印队列。这都使我对数据结构的学习有了新的认识与帮助。在实验过程中,我也遇到了许多困难,从开始时对队列运算的不熟悉,到逐渐查找资料,从而完成了实验。在今后的学习中,我将继续努力,

加强对堆栈,队列等知识的学习,以达到精益求精。

六、附录

-《数据结构与算法分析》以及网上资料

数据结构实验

实验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

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;

数据结构实验报告

数据结构实验报告 一.题目要求 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、掌握线性表的基本操作,如建立、查找、插入和删除等。 二、实验容 定义一个包含学生信息(学号,,成绩)的顺序表和链表(二选一),使其具有如下功能: (1) 根据指定学生个数,逐个输入学生信息; (2) 逐个显示学生表中所有学生的相关信息; (3) 根据进行查找,返回此学生的学号和成绩; (4) 根据指定的位置可返回相应的学生信息(学号,,成绩); (5) 给定一个学生信息,插入到表中指定的位置; (6) 删除指定位置的学生记录; (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include #include #include #include #define OK 1 #define ERROR 0 #define OVERFLOW -2

typedef int Status; // 定义函数返回值类型 typedef struct { 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;

40875][东北大学]20年7月考试《数据结构Ⅱ》考核作业(答案)

东北大学继续教育学院 数据结构II 试卷(作业考核线上1) A 卷 学习中心:奥鹏远程教育沈阳学习中心(直属)[32]院校学号:C09024011930344 姓名何家强 (共 6 页) [ A]1.抽象数据类型的三个组成部分分别为 A.数据对象、数据关系和基本操作 B.数据元素、逻辑结构和存储结构 C.数据项、数据元素和数据类型 D.数据元素、数据结构和数据类型 [ B]2.要求相同逻辑结构的数据元素具有相同的特性,其含义为 A. 数据元素具有同一的特点 B. 不仅数据元素包含的数据项的个数相同,而且其对应数据项的类型要一致 C. 每个数据元素都一样 D. 仅需要数据元素包含的数据项的个数相同 [ D]3.下列各式中,按增长率由小至大的顺序正确排列的是 A.n,n!,2n ,n3/2 B.n3/2,2n,n logn,2100 C.2n,log n,n logn,n3/2 D.2100,logn, 2n, n n [B ]4. 在下列哪种情况下,线性表应当采用链表表示为宜 A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 [ C]5.设指针p指向双链表的某一结点,则双链表结构的对称性是 A. p->prior->next=p->next->next; B. p->prior->prior=p->next->prior; C. p->prior->next=p-> next->prior; D. p->next->next= p->prior->prior;

[D ]6. 已知指针p和q分别指向某带头结点的单链表中第一个结点和最后一个结点。假设指 针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为 A. s->next=q;p->next=s->next; B. s->next=p;q->next=s->next; C. p->next=s->next;s->next=q; D. q->next=s->next;s->next=p; [A ]7. 栈和队列的共同特点是 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 [D ]8. 对于链队列,在进行插入运算时. A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 [B ]9.设有一个顺序栈的入栈序列是1、2、3,则3个元素都出栈的不同排列个数为 A.4 B.5 C. 6 D. 7 [D ]10.设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是 A.A,B,C,D B.D,C,B,A C. A,C,D,B D. D,A,B,C [ C]11.表达式a*(b+c)-d的后缀表达式是 A.abcd*+- B.abc*+d- C.abc+*d- D.-+*abcd [B ]12.某二叉树的先序序列和后序序列正好相反,则该二叉树的特点一定是 A. 空或只有一个结点 B.高度等于其结点数 C. 任一结点无左孩子 D.任一结点无右孩子 [ B]13.下面的说法中正确的是 (1)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。 (2)按二叉树定义,具有三个结点的二叉树共有6种。 A.(1),(2) B.(1) C.(2) D.(1),(2)都错 [ B]14.树有先序遍历和后序遍历,树可以转化为对应的二叉树。下面的 说法正确的是 A.树的后序遍历与其对应的二叉树的先序遍历相同 B.树的后序遍历与其对应的二叉树的中序遍历相同 C.树的先序序遍历与其对应的二叉树的中序遍历相同 D.以上都不对 [D ]15.下列说法正确的是 (1)二又树按某种方式线索化后,任一结点均有前趋和后继的线索 (2)二叉树的先序遍历序列中,任意一个结点均处于其子孙结点前 (3)二叉排序树中任一结点的值大于其左孩子的值,小于右孩子的值 A.(1)(2)(3) B.(1)(2) C.(1)(3) D.都不对 [D ]16. 二叉树的第k层的结点数最多为 A.2k-1 B.2K+1

数据结构实验-互联网域名查询实验报告

实验报告 实验课程:数据结构 实验项目:实验三互联网域名查询 专业:计算机科学与技术 班级: 姓名: 学号: 指导教师:

目录一、问题定义及需求分析 (1)问题描述 (2)实验任务 (3)需求分析 二、概要设计: (1)抽象数据类型定义 (2)主程序流程 (3) 模块关系 三、详细设计 (1)数据类型及存储结构 (2)模块设计 四、调试分析 (1)调试分析 (2)算法时空分析 (3)经验体会 五、使用说明 (1)程序使用说明 六、测试结果 (1)运行测试结果截图 七、附录 (1)源代码

一、问题定义及需求分析 (1)实验目的 互联网域名查询 互联网域名系统是一个典型的树形层次结构。从根节点往下的第一层是顶层域,如cn、com等,最底层(第四层)是叶子结点,如www等。因此,域名搜索可以看成是树的遍历问题。 (2)实验任务 设计搜索互联网域名的程序。 (3)需求分析: 1)采用树的孩子兄弟链表等存储结构。 2)创建树形结构。 3)通过深度优先遍历搜索。 4)通过层次优先遍历搜索。 二、概要设计: 采用孩子兄弟链表存储结构完成二叉树的创建; 主程序流程: 创建根节点域名输入域名拆分根据孩子兄弟链表表示的树进行插入调用层次优先遍历输出遍历结果调用深度优先遍历输出遍历结果结束程序 模块关系: 输入域名 创建孩子兄弟树 层次优先遍历输出结果 深度优先遍历输出结果 结束 三、详细设计 孩子兄弟链表结构: typedef struct CSNode{ ElemType data[10]; struct CSNode *firstchild, *nextsibling; }*CSTree;

数据结构实验报告

姓名: 学号: 班级: 2010年12月15日

实验一线性表的应用 【实验目的】 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。、; 2、以线性表的各种操作(建立、插入、删除、遍历等)的实现为重点; 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现; 4、通过本章实验帮助学生加深对C语言的使用(特别是函数的参数调用、指针类型的 应用和链表的建立等各种基本操作)。 【实验内容】 约瑟夫问题的实现:n只猴子要选猴王,所有的猴子按1,2,…,n编号围坐一圈,从第一号开始按1,2…,m报数,凡报到m号的猴子退出圈外,如此次循环报数,知道圈内剩下一只猴子时,这个猴子就是猴王。编写一个程序实现上述过程,n和m由键盘输入。【实验要求】 1、要求用顺序表和链表分别实现约瑟夫问题。 2、独立完成,严禁抄袭。 3、上的实验报告有如下部分组成: ①实验名称 ②实验目的 ③实验内容:问题描述:数据描述:算法描述:程序清单:测试数据 算法: #include #include typedef struct LPeople { int num; struct LPeople *next; }peo; void Joseph(int n,int m) //用循环链表实现 { int i,j; peo *p,*q,*head; head=p=q=(peo *)malloc(sizeof(peo)); p->num=0;p->next=head; for(i=1;inum=i;q->next=p;p->next=head; } q=p;p=p->next; i=0;j=1; while(i

数据结构实验

长春大学计算机学院网络工程专业 数据结构实验报告 实验名称:实验二栈和队列的操作与应用 班级:网络14406 姓名:李奎学号:041440624 实验地点:日期: 一、实验目的: 1.熟练掌握栈和队列的特点。 2.掌握栈的定义和基本操作,熟练掌握顺序栈的操作及应用。 3.掌握链队的入队和出队等基本操作。 4.加深对栈结构和队列结构的理解,逐步培养解决实际问题的编程能力。 二、实验内容、要求和环境: 注:将完成的实验报告重命名为:班级+学号+姓名+(实验二),(如:041340538张三(实验二)),发邮件到:ccujsjzl@https://www.doczj.com/doc/07152887.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 的元素个数,即栈的长度, 编写此函数

东北大学数据结构上机实验报告3

实验三树和图应用 一、实验目的 光纤管道铺设施工问题 问题描述 设计校园内有N个教学楼及办公楼,要铺设校园光纤网,如何设计施工方案使得工程总的造价为最省。 二、实验要求 设计校园光纤网铺设的最小生成树模拟程序。 1)采用邻接表或邻接矩阵存储结构。 2)分别采用普利姆算法和克鲁斯卡尔算法实现。 输入形式 对应的教学楼、办公楼数目n,各边权值即每栋楼之间的距离 输出形式 最小生成树,即总路程最小的路 程序功能 设计校园光纤网铺设的最小生成树模拟程序 三、设计概要 流程图 抽象数据类型的定义 class prims { private:

int n; //节点的个数 int graph_edge[99][4]; //图的边 int g; //图中边的个数 int tree_edge[99][4]; //树的边 int t; //树的边的个数 int s; //源节点 int T1[50],t1; // 第一部分 int T2[50],t2; //第二部分 public: void input(); int findset(int); void algorithm(); void output(); }; 各程序模块之间的调用关系 四、详细设计 定义prims类 private中进行对图的创建 public: void input(); int findset(int); void algorithm();

void output(); 开始界面 实现prims类中图的初始化 分别输入图中的顶点个数、图的边及其权值 算法构造 t=0;//初始化边的个数为0 t1=1; T1[1]=1; //资源节点 t2=n-1; int i; for(i=1;i<=n-1;i++) T2[i]=i+1; cout<<"\n\n*****运算开始*****\n\n\n"; while(g!=0 && t!=n-1) { int min=99; int p; int u,v,w; for(i=1;i<=g;i++) { if(findset(graph_edge[i][1])!=findset(graph_edge[i][2])) //如果u和v在不同的部分{ if(min>graph_edge[i][3]) { min=graph_edge[i][3]; u=graph_edge[i][1]; v=graph_edge[i][2]; w=graph_edge[i][3]; p=i; } } } for(int l=p;l

数据结构实验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;

数据结构实验二-

实 验 报 告 一、实验目的 1) 加深对图的表示法和图的基本操作的理解,并可初步使用及操作; 2) 掌握用图对实际问题进行抽象的方法,可以解决基本的问题; 3) 掌握利用邻接表求解非负权值、单源最短路径的方法,即利用Dijkstra 算法求最短 路径,同时掌握邻接表的建立以及使用方法,能够解决相关的问题; 4) 学会使用STL 中的map 抽象实际问题,掌握map ,List,,priority_queue 等的应 用。 二、实验内容与实验步骤 (1) 实验内容: 使用图这种抽象的数据结构存储模拟的欧洲铁路路线图,通过Dijkstra 算法求出欧洲旅行最少花费的路线。该实验应用Dijkstra 算法求得任意两个城市之间的最少路费,并给出路费最少的路径的长度和所经过的城市名。 (2) 抽象数据类型及设计函数描述 1) 抽象数据类型 class City : 维护一个城市的信息,包括城市名name ,是否被访问过的标记visted ,从某个城市到达该城市所需的总费用total_fee 和总路径长度total_distance ,求得最短路径后路径中到达该城市的城市名from_city 。 class RailSystem : 用邻接表模拟欧洲铁路系统,该邻接表使用数据结构map 实现,map 的key-value 课程名称:数据结构 班级: 实验成绩: 实验名称:欧洲旅行 学号: 批阅教师签字: 实验编号:实验二 姓名: 实验日期:2013 年6 月 18 日 指导教师: 组号: 实验时间:

值对的数据类型分别为string和list<*Service>,对应出发城市名和该城市与它能 够到达的城市之间的Service链表。 class Service: 为铁路系统模拟了两个城市之间的直接路线,包括两个城市之间直接到达的费用 fee,两城市之间的直接距离distance。 部分设计函数描述 ●RailSystem(const string& filename) 构造函数,调用load_services(string const &filename)函数读取数据 ●load_services(string const &filename) 读取传入的文件中的数据并建立上述两个map以模拟欧洲铁路路线图 ●reset(void) 遍历cities图,初始化所有城市的信息:visted未访问,total_distance最大 值,total_fee费用最大值,from_city为空 ●~RailSystem(void) 析构函数,用delete将两个map中所有使用new操作符开辟的空间删除 ●void output_cheapest_route(const string& from, const string& to, ostream& out); 输出两城市间的最少费用的路径,调用calc_route(string from, string to)函 数计算最少费用 ●calc_route(string from, string to) 使用Dijkstra算法计算from和to两个城市间的最少费用的路径 (3)采用的存储结构 1)map > outgoing_services 用来保存由一个城市出发可以直接到达的城市名及这两个城市之间的路径信息。 2)list 以service为指针的list表,保存两城市间的路径。 3)map cities 用来保存所有城市信息,通过城市名查找该城市有关信息。 4)priority_queue, Cheapest> candidates 存储候选的遍历城市,City*是优先队列存储的对象类型,vector是该对象的向量集合,Cheapest是比较规则。 三、实验环境 操作系统:Windows 8 调试软件:Microsoft visual studio 2012 上机地点:综合楼311 机器台号:笔记本

数据结构 _实验1

《数据结构》实验报告 班级:网络1311 学号:10 姓名:曾梦成绩: 实验1:指针和结构体程序设计 1.实验目的 (1)复习C(或C++)语言的基本描述方法。 (2)熟练掌握数组的用法。 (3)提高运用C(或C++)语言解决实际问题的能力。 2.实验内容 设一个班有10个学生,每个学生有学号,以及数学、物理、英语、语文、体育5门课的成绩信息。分别写3个函数以实现以下3个要求: (1)求数学的平均成绩。 (2)对于有两门以上课程不及格的学生,输出他们的学号、各门课成绩及平均成绩。 (3)输出成绩优良的学生(平均成绩在85分以上或全部成绩在80分以上)的学号、各门课成绩和平均成绩。 3.实验要求 (1)利用C(或C++)语言完成程序设计。 (2)上机调试通过实验程序。 (3)输出10个学生的学号和数学、物理、英语、语文、体育5门课的成绩,检验程序运行的正确性。 (4)总结整个程序的组成和设计思想。 (5)撰写实验报告(把输入数据及运行结果用抓图的形式粘贴到实验报告上)。 4.实验程序 #include struct STUDENT { char id[10]; int score[5]; double ave; }stu[10]; void main() { int i,j,math=0,m=0,n=0,k,Tave,num=10; double mave;

printf("成绩输入按照数学物理英语语文体育的顺序"); for(i=0;i

东北大学数据结构实验报告

. / 实验报告 课程名称:数据结构班级:实验成绩: 实验名称:顺序表和链表的应用学号:批阅教师签字: 实验编号:实验一:实验日期:2017-11-25 指导教师:组号:实验时间:18:30~22:30 一、实验目的 (1)掌握线性表的基本操作(插入、删除、查找)以及线性表合并等运算在顺序存储结构、链式存储结构上的实现。重点掌握链式存储结构实现的各种操作。 (2)掌握线性表的链式存储结构的应用。 二、实验内容与实验步骤 (1)实验内容: 实现约瑟夫环,约瑟夫环(Joseph)问题的一种描述是:编号为1、2、3……n的n个人按照顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数的上限值m,从第一个人开始按照顺时针的方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他的顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。设计一个程序求出出列顺序。 (2)抽象数据类型和设计的函数描述,说明解决设想。 首先定义一个链表,用其中的data项存储每个人的编号,用password项存储每个人所持有的密码,并且声明一个指针。之后使用CreatList_CL函数来创建一个循环链表,在其中的data和password中存入编号和密码,最后使最后一个节点的next指向L,使其能够形成循环队列。定义了函数Display来显示链表当中的内容,以确定存储的数据没有错误。定义了函数Delete_L来实现约瑟夫环中依次删除的功能,依次比较,如果某个人所持的密码和m值相等,则删除这个结点,并且输出此时该结点的编号和密码,实现出列的功能。 (3)简短明确地写出实验所采用的存储结构,并加以说明。 该实验我主要采用的是线性表的链式存储结构,首先定义了链表的结构,其中包括data 项和password项,分别存储每个人的编号和所持密码,还声明了指向下一个结点的指针,该指针可以连接各个结点,并且将最后一个结点的指针指向第一个结点使之成为一个循环链表。 三、实验环境 操作系统:Windows 7 调试软件名称:Visio Studio2017 上机地点:信息楼B405 四、实验过程与分析 (1)主要的函数或操作内部的主要算法,分析这个算法的时、空复杂度,并说明设计的巧妙之处。

数据结构实验一 实验报告

班级: 姓名: 学号: 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义; 2、掌握线性表的基本操作,如建立、查找、插入与删除等。 二、实验内容 定义一个包含学生信息(学号,姓名,成绩)的顺序表与链表(二选一),使其具有如下功能: (1) 根据指定学生个数,逐个输入学生信息; (2) 逐个显示学生表中所有学生的相关信息; (3) 根据姓名进行查找,返回此学生的学号与成绩; (4) 根据指定的位置可返回相应的学生信息(学号,姓名,成绩); (5) 给定一个学生信息,插入到表中指定的位置; (6) 删除指定位置的学生记录; (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include #include #include #include #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; // 定义函数返回值类型 typedef struct

{ 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;

东北大学数据结构实验报告

实验报告 课程名称:数据结构班级:实验成绩: 实验名称:顺序表和链表的应用学号:批阅教师签字: 实验编号:实验一:实验日期:2017-11-25 指导教师:组号:实验时间:18:30~22:30 一、实验目的 (1)掌握线性表的基本操作(插入、删除、查找)以及线性表合并等运算在顺序存储结构、链式存储结构上的实现。重点掌握链式存储结构实现的各种操作。 (2)掌握线性表的链式存储结构的应用。 二、实验容与实验步骤 (1)实验容: 实现约瑟夫环,约瑟夫环(Joseph)问题的一种描述是:编号为1、2、3……n的n个人按照顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数的上限值m,从第一个人开始按照顺时针的方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他的顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。设计一个程序求出出列顺序。 (2)抽象数据类型和设计的函数描述,说明解决设想。 首先定义一个链表,用其中的data项存储每个人的编号,用password项存储每个人所持有的密码,并且声明一个指针。之后使用CreatList_CL函数来创建一个循环链表,在其中的data和password中存入编号和密码,最后使最后一个节点的next指向L,使其能够形成循环队列。定义了函数Display来显示链表当中的容,以确定存储的数据没有错误。定义了函数Delete_L来实现约瑟夫环中依次删除的功能,依次比较,如果某个人所持的密码和m 值相等,则删除这个结点,并且输出此时该结点的编号和密码,实现出列的功能。 (3)简短明确地写出实验所采用的存储结构,并加以说明。 该实验我主要采用的是线性表的链式存储结构,首先定义了链表的结构,其中包括data 项和password项,分别存储每个人的编号和所持密码,还声明了指向下一个结点的指针,该指针可以连接各个结点,并且将最后一个结点的指针指向第一个结点使之成为一个循环链表。 三、实验环境 操作系统:Windows 7 调试软件名称:Visio Studio2017 上机地点:信息楼B405 四、实验过程与分析 (1)主要的函数或操作部的主要算法,分析这个算法的时、空复杂度,并说明设计的巧妙之处。

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

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

天津科技大学 2015—2016学年第2学期数据结构实验任务书 课程名称:数据结构实验学时: 2 实验题目:线性表的基本操作 实验环境: Visual C++ 实验目的: 1、掌握线性表的定义; 2、掌握线性表的基本操作,如建立、查找、插入和删除等。 实验内容: 定义一个包含学生信息(学号,姓名,成绩)的顺序表和链表(二选一),使其具有如下功能: (1) 根据指定学生个数,逐个输入学生信息; (2) 逐个显示学生表中所有学生的相关信息; (3) 根据姓名进行查找,返回此学生的学号和成绩; (4) 根据指定的位置可返回相应的学生信息(学号,姓名,成绩); (5) 给定一个学生信息,插入到表中指定的位置; (6) 删除指定位置的学生记录; (7) 统计表中学生个数。 实验提示: 学生信息的定义: typedef struct { char no[8]; //8位学号 char name[20]; //姓名 int score; //成绩 }Student; 顺序表的定义 typedef struct { Student *elem; //指向数据元素的基地址 int length; //线性表的当前长度 }SqList; 链表的定义:

typedef struct LNode{ Student data; //数据域 struct LNode *next; //指针域 }LNode,*LinkList; 实验要求: (1) 程序要添加适当的注释,程序的书写要采用缩进格式。 (2) 程序要具在一定的健壮性,即当输入数据非法时,程序也能适当地做出反应,如插入删除时指定的位置不对等等。 (3) 程序要做到界面友好,在程序运行时用户可以根据相应的提示信息进行操作。 (4) 根据实验报告模板详细书写实验报告,在实验报告中给出链表根据姓名进行查找的算法和插入算法的流程图。 (5) 以班为单位实验周周五上传源程序和实验报告。顺序表的源程序保存为SqList.cpp,链表的源程序保存为LinkList.cpp,实验报告命名为:实验报告1.doc。源程序和实验报告压缩为一个文件(如果定义了头文件则一起压缩),按以下方式命名:学号姓名.rar,如07081211薛力.rar。

东北大学大数据结构实践实验报告材料

实用文档 课程编号:B080109010 数据结构课程设计 总结报告 东北大学软件学院

第一章需求分析 1.1 建立主程序应用菜单选项 主程序应用菜单选项包含所实现的所有功能,并且对选项采用数字标识进行选择,对其他错误输入可以进行判别,提示输入错误。 1.2 导游线路图的创建级景区分布图的输出 用邻接链表存储景点分布图的信息,(带权无向)图的邻接链表。输出景区景点分布图(邻接矩阵)。图中边的权值∞用32767表示。 1.3 输出导游线路图 景区旅游信息管理系统中制订旅游景点导游线路策略,首先通过遍历景点,给出一个入口景点,建立一个导游线路图,导游线路图用有向图表示。 1.4 输出导游线路图中是否有回路 景区旅游信息管理系统中,创建好导游路线图后,判断该图中是否存在回路。 1.5 查找及排序 ●查找功能:可以根据用户输入的关键字进行景点的查找,关键字可以在景点名称 也可以在景点介绍中。查找成功则返回景点的相关简介,如果查找不成功请给予正 确提示。 ●排序功能:按景点欢迎度,景点的岔路数对景点进行排序并打印出来排序顺序。 1.6 输出两个景点之间最短路径和最短距离 求出两个景点间的最短路径和最短距离,并且输出道路修建规划图。算法采用迪杰斯特拉算法。 1.7 输出道路修建规划图 道路建设首先要保证能连通所有景点,但又要花最小的代价。 1.8 输出车辆的进出信息 1.8.1 具体需求: 停车场是一个可以停放n辆汽车,且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序,依次排列,若车场内已停满n辆车,后来的车只能在门外的便道上等候,一旦有车开走,则排在便道上的第一辆车即可开入;当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路,待该辆车开出大门外,其它车辆再按

数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 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始终指向生成的单链表的最后一个节点

相关主题
相关文档 最新文档