文档库 最新最全的文档下载
当前位置:文档库 › 数据结构 车厢问题 实验报告

数据结构 车厢问题 实验报告

数据结构 车厢问题 实验报告
数据结构 车厢问题 实验报告

数据结构实验报告

实验名称:实验二——题目5

学生姓名:

班级:

班内序号:

学号:

日期:2011年11月7日

1.实验要求

利用队列结构实现车厢重排问题。车厢重排问题如下:

一列货车共有n节车厢,每个车厢都有自己的编号,编号范围从1~n。给定任意次序的车厢,通过转轨站将车厢编号按顺序重新排成1~n。转轨站共有k个缓冲轨,缓冲轨位于入轨和出轨之间。开始时,车厢从入轨进入缓冲轨,经过缓冲轨的重排后,按1~n的顺序进入出轨。缓冲轨按照先进先出方式,编写一个算法,将任意次序的车厢进行重排,输出每个缓冲轨中的车厢编号。

2. 程序分析

将每个轨道视为一个队列,每一个车厢视为一个结构体的结点,结点存储车厢编号以及下一节车厢的地址。用尾插法建立队列,并根据队列队尾入队,队头出队的特点实现结点的出队以及入队。由于车厢在重排过程中将会频繁进行入队以及出队的操作,如果采用顺序存储结构,则在结点出入队时是操作将会十分不方便,还会占用大量多余的空间和时间,故选用链式存储结构,可以直接调动结点,十分简洁。

重排过程比如:编号为3的车厢进入缓冲轨1,则下一个编号小于3的车厢则必须进入下一个缓冲轨2,而编号大于3的车厢则进入缓冲轨1,排在3号车厢的后面。在把车厢c 移至缓冲轨是,车厢c应该移动到这样的缓冲轨中:该缓冲轨中队尾车厢的编号小于c;如果有多个缓冲轨满足这一条件,则选择对位车厢编号最大的缓冲轨,否则选择一个空的缓冲轨。这样,出轨的时候才可以按照从小到大的顺序重新编排。

2.1 存储结构

2.2 关键算法分析

1. 移动车厢算法(车厢要从a队列移至b队列)

·自然语言描述

(1)判断a队列是否为空,为空则输出“队列下溢”,提示出错。

(2) 否则,设置工作指针p 指向a 队列的队头元素,

(3) 将b 的尾指针指向next 域指向p ;

(4) b 队列的尾指针后移,指向p 指向的结点;

(5) a 头结点指向p 后一个结点

(6) p 的next 域置为空,完成一次车厢的移动

(7) a 队列车厢数减1,b 队列车厢数加1

·伪代码描述

两个队列,车厢要从a 队列移至b 队列;

(1)bus* p=a.front->next;

(2)if(!p) cout<<"Underflow"<

(3)b.rear->next=p;

(4)b.rear=b.rear->next;

(5)a.front->next=p->next;

(6)p->next=NULL;

(7)if(!(a.front->next))a.rear=a.front;

(8)a.Number--;b.Number++;

图示

a

b

算法时间复杂度O(1),空间复杂度S(1)。

2. 重排车厢算法

·自然语言描述

next_out 记录下一个要输出的车厢号,初始值为1;Num_hc 个缓冲轨。 (1)依次取出入轨中的每一个车厢编号,若编号与next_out 相等,则将该车厢移动到出

轨,next_out 增一,并输出该步骤。此时完成一次调度,函数返回值为true

(2)若入轨中没有符合要求的车厢,考察每一个缓冲轨队列的第一个车厢编号,若与

next_out 相等,则将该车厢移入出轨,next_out 增一,并输出该步骤。此时完成一次调度,函数返回值为true

(3)若入轨和缓冲轨的队友元素没有标号为next_out 的车厢,则考察每个缓冲轨的尾车

厢编号,找到小于入轨中第一个车厢编号的的最大队尾元素所在的缓冲轨并输出该步骤。此时完成一次调度,函数返回值为true

b.rear

b.front

(4)如果这样的缓冲轨存在,则将入轨中的第一个车厢移至该缓冲轨并输出该步骤。此时完成一次调度,函数返回值为true

(5)如果没有这样的缓冲轨,但有多于一个空缓冲轨,则把入轨中的第一个车厢移至一个空缓冲轨并输出该步骤。此时完成一次调度,函数返回值为true

(6)如果没有空缓冲轨,则车厢无法重排,算法结束,函数返回值为false

(7)如果入轨中没有车厢,则排序完成,算法结束,函数返回值为false

·伪代码描述

1.如果入轨中的车厢编号等于next_out

1.1将该车厢移到出轨

1.2next_out++

1.3输出该步骤,函数返回值为true

2.否则,考察缓冲队列

For(int i=1;i

2.1取队列i的队头元素NO

2.2如果NO==next_out,则

2.2.1将队列i的队头元素移到出轨,并输出

2.2.2next_out++

2.2.3输出该步骤以及缓冲轨的情况,函数返回值true

3.如果入轨和缓冲轨的队头元素没有编号为next_out的车厢,则

3.1求小于入轨中第一车车厢编号的最大队尾元素所在的队列编号nextH

3.2求第一个空缓冲轨的编号vacantH

3.3如果nextH存在,则把入轨中的第一个车厢移至缓冲轨nextH,函数返回值为

true,输出该步骤以及缓冲轨情况

3.4如果nextH不存在,但有空缓冲轨,则把入轨中的第一个车厢移至一个空缓冲

轨函数返回至为true;否则车厢无法完成重排,算法结束,函数返回值为false

4.如果如果入轨中没有车厢,则重排完成,算法结束,函数返回值为false

算法的时间复杂度为O(n),空间复杂度为S(4)

2.3 其他

程序中的车厢移动函数包括两个,为重载函数,但算法是一样的。

3. 程序运行结果

测试条件:问题规模的数量级是1,车厢数量为5,车厢排序为:4 2 1 5 3,缓冲轨数量为2,运行结果如下:

当缓冲轨数目为1时,运行结果如下:

测试结论:程序可以完成程序所要求的车厢重排功能,并能随时跟踪缓冲轨中的车厢情况;

当所给条件无法完成重排时,会给用户提示。

4. 总结

原来程序中重排的函数只能调用一次调度,要完成整个车厢的重排工作,必须要实现循环,故将重排函数的返回值设为bool型,通过do-while完成这个循环,设置了一个变量judge 来决定循环的终止条件。如果排序完成则返回true,未完成则返回false。

这次试验使我熟悉了链队列的特点以及操作方法,并且体会到了其在实际运用中的重要性。同时,车厢要完成重排需要考虑到各种情况,在编写算法的过程中锻炼了我的逻辑思维能力和考虑问题的周密性。

下一步需要改进的是:如果车厢数量较多,用户在输入时可能会出现错误,如果在重排之前编写一个能够检验用户输入情况是否有错的函数就会使程序更加完美。同时算法中使用

了许多if嵌套的语句,使得程序的可读性变差,也增加了时间复杂度。

数据结构实验报告格式

《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程,是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法,介绍了常用的多种查找和排序技术,并做了性能分析和比较,内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因,使得掌握这门课程具有较大的难度: (1)内容丰富,学习量大,给学习带来困难; (2)贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点; (3)所用到的技术多,而在此之前的各门课程中所介绍的专业性知识又不多,因而加大了学习难度; (4)隐含在各部分的技术和方法丰富,也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性,设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练,突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时,觉得无从下手,做起来特别费劲。实验中的内容和教科书的内容是密切相关的,解决题目要求所需的各种技术大多可从教科书中找到,只不过其出现的形式呈多样化,因此需要仔细体会,在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程,理解和掌握算法设计所需的技术,为整个专业学习打好基础,要求运用所学知识,上机解决一些典型问题,通过分析、设计、编码、调试等各环节的训练,使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法,如算法设计的构思方法,动态链表,算法的编码,递归技术,与特定问题相关的技术等,要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上,掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时,要求完成以下六个题目: 实习一约瑟夫环问题(2学时)

人事管理系统-软件工程实验报告

软件工程实验报告 课题:人事管理系统学生姓名: 学号: 专业班级: 指导教师: 同组成员:

需求分析 一、实验目的 掌握软件需求的结构化分析方法。 二、实验任务与实验要求 导出系统详细的逻辑模型,这里用数据流图来表示。 三、实验内容 (1)功能分析 经过初步分析“人事管理系统”应该具备以下主要功能。 1、职员个人信息资料的增加、修改和删除; 2、职员的考勤录入和查询; 3、职员工资结算和查询; 4、人事管理人员的变化和操作授权; 由于是使用计算机管理,就带来了新的功能:用户登陆、操作人员的管理、基本数据的维护、由数据安全产生的数据备份与恢复。 (2)、关系模式 在满足函数依赖和无损连接的基础上,使数据的设计更加合理。在本系统中只有3个实体,那就是普通员工、管理员、超级管理员,他们权限的不听通过角色来区分。在整个系统中超级管理员只有一人,管理员二人。一个人只可以在普通员工、管理员、超级管理员中处于一个角色,而不可以兼任。其具体的关系模式如下: 普通员工(员工号,密码,姓名,性别,出生年月,身份证号,联系电话,就职时间) 管理员(管理员号,密码,姓名,性别,出生年月,身份证号,联系电话,就职时间) 超级管理员(超级管理员号,密码,姓名,性别,出生年月,身份证号,联系电话,就职时间) 工资(员工号,时间,基本工资,提成,奖金) 考勤(员工号,时间,迟到,早退,管理员号) 注意:“”表示主码,“”表示既是主码又是外码。 E-R图如下所示

数据字典设计: 为了方便数据库的管理和维护,本系统只设计一个数据库workers.mdb,其中包含worker(员工信息表)、manager(考勤信息表)、booklist(工资信息表) 表1-1 worker(员工信息表)各字段设计 表1-2 monit (考勤信息表)各字段设计

数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 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、学习编制可行性研究报告。 二、实验要求 硬件:Intel Pentium 120 或以上级别的CPU,大于16MB的内存。 软件:Win dows 95/98/2000 操作系统,Office 97/2000 软件 学时:2学时 写岀此项实验报告 三、实验内容 1、可行性研究(结构化分析)方法; 2、绘制数据流图,使用Word写实验报告。 四、实验步骤 1 ?引言 1.1 编写目的 可行性研究的目的是为了对问题进行研究,以最小的代价在最短的时间内确定问题是否可解。 经过对此项目进行详细调查研究,初拟系统实现报告,对软件开发中将要面临的问题及其解决方案进行初步设计及合理安排。明确开发风险及其所带来的经济效益。本报告经审核后,交软件经理审查。 1 . 2 项目背景 (1 )待开发的软件产品名称:旅行社机票预定系统。 (2)本项目的提岀者:冯剑。开发者:李翀。用户:旅行社 (3)本软件产品将用于旅行社的机票预定和费用的记录。

1 . 3术语说明 DFD (数据流图):一种描述书记变换的图形工具,是结构化分析方法最普遍采用的表示手段,但数据流图并不是结构化分析模型的全部,数据字典和小说明为数据流图提供了补充,并用以验证图形表示的正确性、一致性和完整性,三者共同构成了被建系统的模型。 1 . 4.系统参考文献 参考文献见附录 2?可行性研究的前提 2.1基本要求 ⑴功能 本软件实现的功能有:为游客提供机票预定服务,提高旅游局的服务质量和服务效率。 对航班数据库的查询和修改,对机票费用记帐数据库的查询和修改,记录旅客信息(姓名、性别、年龄、身份证号、单位、旅行时间、目的地)、航班时间和班次,打印机票和帐单。 (2) 性能 时间:提供的信息必须及时的反映在工作平台上。售票系统的定单必须无差错的存 储在机场的主服务器上。对服务器上的数据必须进行及时正确的刷新。一笔业务在一分钟内完成。空间:运行空间 2M。 (3) 系统的输入和输岀 输入:旅行社定票单。数据完整,详实。 输岀:机票、帐单。简捷,快速,实时。 (4) 处理流程 旅行社将定票信息输入定票系统,系统输岀机票和帐单给旅客。 5 )安全保密要求

数据结构实验报告-答案

数据结构(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] 留在原位

数据流图实验报告

数据流图实验报告 篇一:软件工程实验报告 篇二:需求分析实验报告 软件工程实践报告 计科12—1班 杨光敏 08123234 (一)软件需求分析 1.实验目的 学习图形工具软件VISIO,掌握结构化需求分析方法,熟练绘制数据流图;学习快速原型工具的使用。 2.基本要求 (1)针对银行ATM系统进行需求分析工作,了解银行ATM系统的功能、流程;(2)安装VISIOXX以上版本软件,熟练应用Visio绘制DFD图,绘制银行ATM系统数据流图,完成系统的软件逻辑模型; (3)安装Axure RP Pro 或者Balsamiq Mockups快速原型软件,学习绘制软件原型,完成银行ATM系统的软件原型。 3.系统概述 (1)ATM系统为银行提供一套高效稳定可靠的终端服务平台,为储户登录,

存款,取款,查询,打印凭条,转账,修改密码等操作提供便利。 图1 ATM工作流程 (2).用户特点 本软件的用户主要是银行的广大持卡人,大多都具有使用ATM经验。另外,我们的系统要实现的一个重要目标就是当储户取钱出现故障时能在下笔业务进行之前自动恢复。以此来方便用户和保障用户的利益。本系统还为用户提供了足够的界面友好性和易操作性。即使是一个对ATM系统完全陌生的客户,也可以在交易界面的提示下顺利完成交易。 另外一部分的用户是银行工作人员,本系统不予考虑。 4需求说明 (1) 基本描述 ATM终端可以接受一张可识别的银行储蓄卡,通过储户身份验证后,同储户进行各种交互,例如:查询、存款、取款、打印凭条等;处理储户相应的要求,执行对应操作,为储户服务。该系统要求须保持一定时间内的交易记录,系统应每天自动汇总各种交易数据与服务器进行对账。同时,在通讯失败或其他交易结果不确定的情况下,ATM要自动发起冲正交易,以保证账务的完整性。 本系统的实现需要记录一些相关信息,其中包括的信息有:用户信息和交易信息。

《数据结构》实验报告1

xxx 实验报告 一、实验目的 1.熟悉上机环境,进一步掌握语言的结构特点。 2.掌握线性表的顺序存储结构的定义及实现。 3.掌握线性表的链式存储结构——单链表的定义及实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21,23,14,5,56,17,31},然后在第i 个位置插入元素68。 3.建立一个带头结点的单链表,结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、程序主要语句及作用 1)程序1的主要代码(附简要注释) #include using namespace std; #define MAXSIZE 1024 en>=MAXSIZE) { printf("the list is overflow\n"); return ERROR; } else if((i<1)||(i>(*L).len+1)) { printf("position is not corrent.\n"); return ERROR; } else{ for(j=(*L).len-1;j>=i-1;j--) ec[j+1]=(*L).vec[j]; ec[i]=x; len++;

部分的时间都用在了编程上,主要是因为C语言掌握的问题,C语言基础不好特别是对于C语言中链表的一些定义和基本操作不够熟练,导致在编程过程中还要不断的拿着c语言的教材查找,所以今后还要对C语言多练习,多动手,多思考。 2.数据结构有很强的逻辑性,因此我认为如果在上机之前先把逻辑搞清楚很重要,不管是对算法的设计还是对程序的调试都有很大帮助。 3.经过一次上机实践,我认为实践课很重要,上理论课只是纸上谈兵,只是被动地接受,而实践课上能将学过的知识利用起来,同时还有一些东西只能是自己上机实践才能慢慢探索出的。 所以我在做试验的时候特别费劲,特别吃力,这也是事出有因的。通过自我反省,总结不足之处后,我还是脚踏实地去查找资料,包括请教老师,上网搜索数据库线性表操作的优秀代码,经过不断的验证,修改和深入的研究,最终使得自己的程序得以运行,实现了实验的最终目的和要求。 也许每次实验都是有个过程的,虽然过程比较繁琐和艰难,但是我觉得只要认真的分析实验内容,积极搜索实验所需材料,再多多请教老师和同学,那么实验就不会困难重重。 自己要学习的地方太多,以后更要努力学习数据结构。

数据结构实验报告图实验

图实验一,邻接矩阵的实现 1.实验目的 (1)掌握图的逻辑结构 (2)掌握图的邻接矩阵的存储结构 (3)验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 (1)建立无向图的邻接矩阵存储 (2)进行深度优先遍历 (3)进行广度优先遍历 3.设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10;

template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif MGraph.cpp

#include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) {

数据结构实验报告模板

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);//重载赋

实验分析数据流和绘制数据流图

实验报告课程名称_软件工程导论__________ 学院____计算机工程学院_________班级14软件1班 学号2014144141 姓名秦川 2016年11月8日

批阅教师时间实验成绩 课程名称软件工程 学号2014144141姓名秦川实验日期2016.11.8实验名称实验2分析数据流和绘制数据流图 实验目的: 1、掌握数据流的分析方法 2、掌握数据流图的绘制 实验内容: 任务一绘制数据流图 任务二分析数据流和绘制数据流图 案例一:总务办公管理系统 案例二:火车票预订系统 实验原理: 数据流图(DFD)是软件系统系统的逻辑模型,仅仅描绘数据在软件中流动(从输入移动到输出)的过程中所经受的变换(即加工处理)。 数据流图的绘制方法:根据数据流图的四种成分:源点或终点,处理,数据存储和数据流,从问题描述中提取数据流图的四种成分;然后依据“自顶向下、从左到右、由粗到细、逐步求精”的基本原则进行绘制。 基本符号如下:

实验过程与结果: 1.运行Microsoft Office Visio2007 运行Microsoft Office Visio2007 2.选择“软件和数据库”中的“数据流模型图”模板 选中数据流模型图模板

3.用鼠标选拉图标进行绘图 任务一绘制数据流图 试绘制工资管理系统的数据流图,根据数据流图的符号说明仔细理解下图含义: 这是学校教职工工资管理系统,教师根据课时表,职工根据任务表来确定个人工资情况,数据按以下方向传递: 首先,对课时表或任务表进行审核,审核后的数据经排序形成专用表格; 再进行一系列额外计算,包括个人所得说、住房公积金、保险费得出具体所发工资,并将工资表发给银行; 然后,向教职工展示工资所得明细; 最后,形成编制报表,更新分类表后,交于会计。 其中,人事科负责人事数据,教师与职工的工资由银行发放,会计做好报表的统计。

数据结构实验一 实验报告

班级::学号: 实验一线性表的基本操作 一、实验目的 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;

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

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;

数据结构实验报告-答案.doc

数据结构实验报告-答案 数据结构(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“typedefstructnode//定义结点{chardata[10];//结点的数据域为字符串structnode*next;//结点的指针域}ListNode;typedefListNode*LinkList;//自定义LinkList单链表类型LinkListCreatListR1();//函数,用尾插入法建立带头结点的单链表LinkListCreatList(void);//函数,用头插入法建立带头结点的单链表ListNode*LocateNode();//函数,按值查找结点voidDeleteList();//函数,删除指定值的结点voidprintlist();//函数,打印链表中的所有值voidDeleteAll();//函数,删除所有结点,释放内存

软件工程实验报告

软 件 工 程 实 验 报 告 班级:计算机科学与技术1102班 学号:1108030209 姓名:蒙雨茹

实验一:使用Microsoft Visio 1.1实验目的: (1)熟悉Visio的工作环境及组成。 (2)掌握Visio软件绘制图表的基本操作。 (3)掌握基本流程图的设计方法。 1.2实验内容: 绘制基本流程图 1.3实验步骤: (1)打开一个模板,,在主菜单中依次选择【文件】->【新建】->【选 择绘图类型】,出现“选择绘图类型”窗口,在【类别】下,单击 【流程图】,在【模板】下,单击【基本流程图】。 (2)添加形状,将【形状】窗口中模具上的自己需要的形状拖到绘图页 面中合适的位置。并添加文本、连接不同形状,使流程图完整的显 现出来。 1.4实验结果:

实验二:数据流图 2.1 实验目的 (1)熟悉Visio的工作环境及组成。 ⑵掌握Visio软件绘制图表的基本操作。 ⑶掌握数据流图的设计方法。 2.2 实验内容 习题3-3,3-4,3-5 2.3 实验步骤 (1)打开模板 ①在主菜单中,依次选择【文件】——【新建】——【选择绘图类型】,出现“选择绘图类型”窗口。 ②在左侧【类别】下,单击【软件】。 ③在右侧【模板】下,单击【数据流模型图】。 (2)绘制顶层图 ①在顶层进程页面中添加、移动图形元素并调整其大小。将所需要元素用鼠标拖动到模板里,添加所需的元素符号。 接口:输入源点或输出终点,其中注明源点或终点的名称。 进程:即处理,输入数据在此进行变换产生输出数据,其中注明进程的名称。数据存储:用于代表系统中存储的信息,其中注明信息的名称。 数据流:被加工的数据及其流向。流线上注明数据名称,箭头代表数据流动方向。 ②向图形元素中添加文本,并修改数据流图中的文字和格式。 连接图形元素。 ③使用“数据流”连接线将“接口”、“进程”和“数据存储”等形状互相连接起来。 逻辑连接:将数据流起点、终点拖拽到进程或接口中央位置,进程或接口被红色框包围时松开鼠标,这时可看到数据流符号相应端点为红色方框。拖动进程或接口,可看到流据流的端点随着进程或接口的移动而移动。

数据结构实验一 实验报告

班级: 姓名: 学号: 实验一线性表的基本操作 一、实验目的 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;

《数据结构》实验报告

《数据结构》实验报告 实验序号:4 实验项目名称:栈的操作

附源程序清单: 1. #include #define MaxSize 100 using namespace std; typedef int ElemType; typedef struct { ElemType data[MaxSize]; int top; }SqStack; void InitStack(SqStack *st) //初始化栈 { st->top=-1; } int StackEmpty(SqStack *st) //判断栈为空{ return (st->top==-1); } bool Push(SqStack *st,ElemType x) //元素进栈{ if(st->top==MaxSize-1)

{ return false; } else { st->top++; //移动栈顶位置 st->data[st->top]=x; //元素进栈 } return true; } bool Pop(SqStack *st,ElemType &e) //出栈 { if(st->top==-1) { return false; } else { e=st->data[st->top]; //元素出栈 st->top--; //移动栈顶位置} return true; } //函数名:Pushs //功能:数组入栈 //参数:st栈名,a->数组名,i->数组个数 bool Pushs(SqStack *st,ElemType *a,int i) { int n=0; for(;n数组名,i->数组个数 bool Pops(SqStack *st,ElemType *a,int i) { int n=0; for(;n

软件工程实验报告_学生成绩管理系统

软件工程实验报告 学生成绩管理系统的设计与实现 学生姓名 学号 班级 成绩 指导教师 年月日

目录 1 课题描述 (3) 2 可行性研究 (4) 2.1 编写目的 (4) 2.2 项目背景 (4) 2.3 定义(术语) (4) 2.4 数据流程和处理流程 (4) 2.5 可行性分析的前提 (5) 2.6 可行性分析 (5) 3 需求分析 (7) 3.1 学生成绩管理系统功能需求 (7) 3.2 学生成绩管理系统性能要求 (8) 3.3 数据流图 (8) 3.4 数据字典 (9) 3.5 学生信息管理系统逻辑结构图 (12) 3.6 用户信息实体关系图 (12) 4 概要设计 (13) 4.1 编写目的 (13) 4.2 项目背景 (13) 4.3 任务概述 (13) 4.4 总体设计 (13) 4.5接口设计 (17) 4.6数据结构设计 (17) 5 详细设计 (19) 5.1 系统程序流程图 (19) 5.2 界面设计 (21) 5.3 程序界面截图 (22) 5.4 程序源代码 (27) 6 软件测试 (58) 7 总结 (62)

1 课题描述 随着互联网的发展,利用INTERNET 技术来实现“无纸办公”这个概念已经深入人心,校园网作为学校信息化建设的一个平台在完成资源共享、互联网访问、教务管理、电子备课等方面发挥了重要作用。服务教学、提高教学水平和效果是校园网建设的核心目标和核心价值,本系统立足于校园实际,着眼于未来发展,建成符合标准化协议、通用性较强、实用的系统,以提高高校的现代化管理水平,实现信息资源的共享。该项目主要是服务于教学方面,进一步方便教师的工作和学生的学习,从而从侧面达到提高学校的教学方面‘软件’质量。可以说它适用于每一所高校,因此很有开发价值。我们不敢说该产品是所有该系列产品中最好的,但是我们这里要强调的是它具有使用范围广,实用性强,使用简单,所花经费少等优点。我们可以肯定的说它将在高校的使用过程中其优点将得到最充分的体现。 主要功能有三方面: 管理员,登陆,进入系统,可以进行管理员操作,进行学生信息、教师信息、课程信息的编辑、查询、删除、修改、添加、打印等操作。 学生,登陆,进入系统,可以进行查询、修改、打印等操作。 教师,登陆,进入系统,可以进行查询、学生成绩录入、修改、打印等操作。 软件系统目标: (1)本系统具有很强的可靠行,可以对录入的学生信息进行效验,对数据进行修改、删除,规定各种权限。 (2)本系统中的模块具有很强的可续性,可以方便管理人员的修改与维护。 (3)本系统操作方便、灵活、简单。 (4)本系统可高效、快速的查询到学生的基本信息。

数据结构实验报告--图实验

图实验 一,邻接矩阵的实现 1.实验目的 (1)掌握图的逻辑结构 (2)掌握图的邻接矩阵的存储结构 (3)验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 (1)建立无向图的邻接矩阵存储 (2)进行深度优先遍历 (3)进行广度优先遍历 3.设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif MGraph.cpp #include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e)

{ int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: "; cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } } template void MGraph::DFSTraverse(int v) { cout << vertex[v]; visited[v] = 1; for(int j = 0; j < vertexNum; j++) if(arc[v][j] == 1 && visited[j] == 0) DFSTraverse(j); } template void MGraph::BFSTraverse(int v) { int Q[MaxSize]; int front = -1, rear = -1; cout << vertex[v]; visited[v] = 1; Q[++rear] = v; while(front != rear) { v = Q[++front]; for(int j = 0;j < vertexNum; j++) if(arc[v][j] == 1 && visited[j] == 0){ cout << vertex[j]; visited[j] = 1;

相关文档