的顺序不变。设计程序实现。要求:采用顺序存储表示实现;采用链式存储表示方法实现;比较两种方法的优劣。 2. 从单链表中删除指定的元素x,若x在单链表中不存在,给出提示信息。 要求: ①指定的值x由键盘输入; ②程序能处理空链表的情况。 3.设有头结点的单链表,编程对表中的任意值只保留一个结点,删除其余值相同的结点。 要求: ①该算法用函数(非主函数)实现; ②在主函数中调用创建链表的函数创建一个单链表, 并调用该函数,验证算法的正确性。 LinkedList Exchange(LinkedList HEAD,p)∥HEAD是单链表头结点的指针,p是链表中的一个结点。本算法将p所指结点与其后 继结点交换。 {q=head->next;∥q是工作指针,指向链表中当前待处理结点。 pre=head;∥pre是前驱结点指针,指向q的前驱。 while(q!=null && q!=p){pre=q;q=q->next;} ∥
数据结构课程设计题目及要求
实验一~实验四任选一题;实验五~实验九任选一题。 实验一运动会分数统计 一、实验目的: (1)熟练掌握线性表的两种存储方式 (2)掌握链表的操作和应用。 (3)掌握指针、结构体的应用 (4)按照不同的学校,不同项目和不同的名次要求,产生各学校的成绩单、团体总分报表。 二、实验内容: 【问题描述】 参加运动会的n个学校编号为1~n。比赛分成m个男子项目和w个女子项目,项目编号分别为1~m和m+1~m+w。由于各项目参加人数差别较大,有些项目取前五名,得分顺序为7,5,3,2,1;还有些项目只取前三名,得分顺序为5,3,2。写一个统计程序产生各种成绩单和得分报表。 【基本要求】 产生各学校的成绩单,内容包括各校所取得的每项成绩的项目号、名次(成绩)、姓名和得分;产生团体总分报表,内容包括校号、男子团体总分、女子团体总分和团体总分。 【测试数据】 对于n=4,m=3,w=2,编号为奇数的项目取前五名,编号为偶数的项目取前三名,设计一组实例数据。 【实现提示】 可以假设m≤20,m≤30,w≤20,姓名长度不超过20个字符。每个项目结束时,将其编号、类型符(区分取前五名还是前三名)输入,并按名次顺序输入运动员姓名、校名(和成绩)。 【选作内容】 允许用户指定某些项目可采取其他名次取法。
实验二停车场管理 一、实验目的: (1)熟练掌握栈顺存和链存两种存储方式。 (2)掌握栈的基本操作及应用。 (3)以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。 二、实验内容: 【问题描述】 设停车场是一个可停放n辆汽车的长通道,且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序,依次由北向南排列(大门在最南端,最先到达的第一辆车信放在车场的最北端),若车场内已停满n辆汽车,则后来的汽车只能在门外的便道上等候,一旦有车开走,则排在便道上的第一辆车即可开入;当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路,待该辆车开出大门外,其他车辆再按原次序进入车场院,每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 【基本要求】 以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项:汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为:若是车辆到达,则输出汽车在停车场内或便道上的停车位置;若是车辆离去,则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停留的时间不收费)。栈以顺序结构实现,队列以链表结构实现。 【测试数据】 设n=2,输入数据为:(A,1,5),(A,1,15),(A,3,20),(A,4,25),(A,5,30),(D,2,35),(D,4,40),(E,0,0)。其中:A表示到达(Arrival);D表示离去(Departure);E表示输入结束(End)。 【实现提示】 需另设一个栈,临时停放为给要离去的汽车让路而从停车场退出来的汽车,也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车,包含两个数据项:汽车的牌照号码和进入停车场的时刻。 【选作内容】 (1)两个栈共享空间,思考应开辟数组的空间是多少? (2)汽车可有不同种类,则他们的占地面积不同收费标准也不同,如1辆客车和1.5辆小汽车的占地面积相同,1辆十轮卡车占地面积相当于3辆小汽车的占地面积。(3)汽车可以直接从便道开走,此时排在它前面的汽车要先开走让路,然后再依次排到队尾。 (4)停放在便道上的汽车也收费,收费标准比停放在停车场的车低,请思考如何修改结构以满足这种要求。
数据结构实验五
1. 实验步骤: 先定义顺序表的结点: typedef struct { KeyType key; InfoType otherinfo; }ElemType; typedef struct { ElemType *R; int length; }SqList; 然后定义一个随机取数的函数,存到顺序表中: void CreateList(SqList &L,int n) 然后定义一个显示顺序表的函数,将顺序表中的数据显示出来: void ListTraverse(SqList L) 然后通过排序函数,将所有的数据按照从大到小的顺序排列: void BubbleSort(SqList &L) 实验结果: 测试数据: 38 86 9 88 29 18 58 27 排序后: 9 18 27 29 38 58 86 88 BubbleSort排序方法中数据的比较次数为:27 疑难小结: 这个程序的难点在于排序函数,总是把从第几个数开始排序以及怎样循环弄错。 源代码: #include using namespace std; #include typedef int KeyType; typedef char * InfoType; typedef struct { KeyType key; InfoType otherinfo; }ElemType; typedef struct { ElemType *R; int length; }SqList; int CmpNum; void CreateList(SqList &L,int n) { int i;
数据结构实验报告-答案
数据结构(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] 留在原位
数据结构实验五A
《数据结构与算法分析》 实验报告书 学期:2014 - 2015 学年第 2 学期 班级:信息管理与信息系统2班 学号: 1310030217 姓名:田洪斌 实验类别:(★)基础型()设计型 实验时间: 成绩: 信息管理系
一、实验内容 实现程序,按满二叉树给元素编号并输入的方式构造二叉树。 二、实验目的 1、掌握二叉树的静态及操作特点; 2、掌握二叉树的各种遍历方法; 3、掌握二叉树的存储、线索化等在C语言环境中的实现方法; 4、掌握哈夫曼树的构造方法及编码方法。 三、需求分析 用二叉树结构表示来完成输入、编辑、调试、运行的全过程。并规定: a.手动输入数字建立二叉树 b.程序可以输入、调试、运行、显示、遍历 c.测试数据:用户手动输入的数据 四、系统设计 1.数据结构设计 在本程序中对二叉树的存储主要用的是顺序存储结构,将二叉树存储在一个一维数组中。数据的输入输出都是采用整型数据进行。在主函数中只是定义数据类型,程序的实现功能化主要是在主函数中通过给要调用的函数参数来实现程序要求的功能。 2.程序结构设计 (1)程序中主要函数功能: main()/////////////////////////////////////////////主函数 menu()/////////////////////////////////////////////菜单 BiTree CreateBiTree()///////////////////////先序建立二叉树 (2)函数调用关系 见图4-1。
图4-1 函数关系图 五、 调试分析 1.算法和函数中出现了一些系统无法识别的变量,照成程序出现了错 误。原因是没有注意算法与源程序的区别。算法是简单的对源程序进行描述 的,是给人阅读的,所以有些变量没有定义我们就能看懂。而程序中的变量一定要先定义才能够被引用,才能被计算机识别。 2.在调试过程中遇到问题是利用C++程序进行调试的,找出错误并改正。 3.数据输出函数运行不正常,经检查程序,发现是定义错误,更改后错误排除; 六、 测试结果 1.运行时输入正确密码进入主界面,系统根据输入的数字选项来调用相应的函数。主要实现“功能选择”的界面,在这个界面里有显示系统的五大功能,根据每个功能前面的序号进行选择。以下为该界面: main BiTree CreateB iTree() meun()
数据结构-实验五-图
数据结构与算法课程实验报告实验五:图的相关算法应用 姓名:cll 班级: 学号:
【程序运行效果】 一、实验内容: 求有向网络中任意两点之间的最短路 实验目的: 掌握图和网络的定义,掌握图的邻接矩阵、邻接表和十字链表等存储表示。掌握图的深度和广度遍历算法,掌握求网络的最短路的标号法和floyd算法。 二、问题描述: 对于下面一张若干个城市以及城市间距离的地图,从地图中所有可能的路径中求出任意两个城市间的最短距离及路径,给出任意两个城市间的最短距离值及途径的各个城市。 三、问题的实现: 3.1数据类型的定义 #define MAXVEX 50 //最大的顶点个数 #define MAX 100000 typedef struct{ char name[5]; //城市的名称
}DataType; //数据结构类型 typedef struct{ int arcs[MAXVEX][MAXVEX]; //临接矩阵 DataType data[MAXVEX]; //顶点信息 int vexs; //顶点数 }MGraph,*AdjMetrix; //邻接矩阵表示图 3.2主要的实现思路: 用邻接矩阵的方法表示各城市直接路线的图,之后用Floyd算法求解两点直接的最短距离,并用递归的方法求出途经的城市。 主要源程序代码: #include #include #define MAXVEX 50 #define MAX 100000 typedef struct{ char name[5]; //城市的名称 }DataType; //数据结构类型 typedef struct{ int arcs[MAXVEX][MAXVEX]; //临接矩阵 DataType data[MAXVEX]; //顶点信息 int vexs; //顶点数 }MGraph,*AdjMetrix; //创建临接矩阵 void CreatGraph(AdjMetrix g,int m[][MAXVEX],DataType d[],int n){ /*g表示邻接矩阵,m[][MAXVEX]表示输入的邻接矩阵,d[]表示各城市的名称,n表示城市数目*/ int i,j; g->vexs = n; for(i=0;i < g->vexs;i++){ g->data[i] = d[i]; for(j=0;jvexs;j++){ g->arcs[i][j] = m[i][j]; } } } //求最短路径 void Floyd(AdjMetrix g,int F[][10],int path[][10]){ int i,j,k; for(i=0;ivexs;i++){ for(j=0;jvexs;j++){
数据结构实验报告-答案.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();//函数,删除所有结点,释放内存
《数据结构》实验指导书
数据结构实验课程大纲 本大纲是针对计算机科学与技术专业本科对数据结构的基本要求而编写的。 一、目的与任务 数据结构是一门实践性很强的课程,每个学生必须完成一定数量的上机作业。通过上机作业,要求在数据结构的逻辑特性和存贮表示、基本数据结构的选择和应用、算法设计及其实现等方面加深对课程基本内容的理解。同时,在程序设计方法、程序设计风格及上机操作等基本技能和科学作风方面受到比较系统的、严格的训练。提高分析问题和用计算机解决实际问题的能力。为后续课程的学习以及为应用软件特别是非数值软件的开发打下良好的理论基础和实践基础。 二、课程内容 1.顺序表的表示和运算(0-2学时) 2.链表的表示和运算(2学时) 3.栈的应用(2-3学时) 4.队列的应用(2-3学时) 5.二叉树的基本操作和应用(2-6学时) 6.图及其应用(2-6学时) 7.排序(4-6学时) 8.查找(2-4学时) 三、基本要求 1.逐步理解和掌握程序设计和上机操作的基本方法和技能。 2.理解并实现各种基本数据结构的存贮表示、运算方法及其典型应用;学会根据实际问题的要求设计算法的 数据结构,并具有一定的比较和选用数据结构及算法的能力。 3.理解并实现常用的查找和排序的基本方法。 四、学时分配
五、实验内容 注:带*的内容以及练习与思考题,可根据实际学时、专业方向特点等具体要求,做相应调整或从略。 实验一、顺序表 实验目的: 熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作。 实验要求: 了解并熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作的实现和应用。 实验内容: 编写程序实现下列的要求: (1) 设数据元素为整数,实现这样的线性表的顺序存储表示。 (2) 键盘输入10个数据元素,利用顺序表的基本操作,建立该表。 (3) 利用顺序表的基本操作,找出表中的最大的和最小的数据元素(用于比较的数据元素为整数)。 (4) * 若数据元素为学生成绩(含姓名、成绩等字段),重新编程,实现上面的要求。要求尽可能少地修改前面的程序来得到新程序。(这里用于比较的字段为分数) 练习及思考题: (1)不同类型的数据元素所对应的顺序表在类型定义和操作实现上有什么异同? (2)顺序表的操作上有什么特点? (3)不固定数据元素的个数,而通过特殊数据来标记输入数据的结束,实现这样的输入操作。 实验二、链表 实验目的: 熟悉链式表的逻辑特性、存储表示方法的特点和链式表的基本操作。 实验要求: 了解并熟悉链式表的逻辑特性、存储表示方法和链式表的基本操作的实现和应用。 实验内容: 编写程序实现下列的要求: (1) 设学生成绩表中的数据元素为学生成绩(含姓名、成绩字段),实现这样的线性表的链式存储表示。 (2) 键盘输入若干个数据元素(用特殊数据来标记输入数据的结束),利用链表的基本操作(前插或后插算法),建立学生成绩单链表。 (3) 键盘输入关键字值x,打印出表中所有关键字值<=x的结点数据。(用于比较的关键字字段为分数)。 (4) 输入关键字值x,删除表中所有关键字值<=x的结点。(用于比较的关键字字段为分数)。 (5) * 释放该链表(删除所有结点)。 (6) * 若要求建立的学生成绩单链表为有序表,重新编写算法和程序实现前面的要求(3)。(用于比较的字段为分数)。 练习及思考题: (1)不同类型的数据元素所对应的链式表在类型定义和操作实现上有什么异同? (2)有头结点的链式表,有什么特点?
数据结构课程实验报告-实验5
数据结构课程实验报告-实验5
HUNAN UNIVERSITY 课程实习报告 题目:四则运算表达式求值 学生姓名康小雪 学生学号 20090810310 专业班级计科三班 指导老师李晓鸿 完成日期2010-10-24
一、需求分析 1.该程序可以从通过从键盘输入一个中缀表达式,判断该表达式是否合法,若合法将 其转化为后缀表达式,并计算其结果,否则说明该表达式错误 2..输入的表达式包含数字和运算符及括号,之间用空格隔开 3.数字可以为整数和小数 4.运算结果保留两位小数 输入输出举例 输入:21+23*(12-6) 输出:21 23 12 6 -*+ 二、概要设计 在表达式中每个运算符应对应两个操作数,与二叉树中非叶子结点和叶子结点之间的关系刚好相同,于是,本题可采用二叉树来将中缀表达式变为后缀表达式。 最后用堆栈来实现后缀表达式的计算。 抽象数据类型 二叉树 ADT BiTree {
数据对象D:D是具有相同特性的数据元素集合 数据关系R: 若D为空集,则R为空集,则称BinaryTree 为空二叉树; 若D不为空集,否则R={H},H是如下二元关系: (1)在D中存在唯一的称为根的数据元素root,它在关系H下无前驱; (2)若D-{root}≠空集,则存在D-{root}的一个划分{D1,Dr} 且D1∩Dr=空集; (3)若D1≠空集,则D1中存在唯一元素x1,∈H,且存在D1shang de guanxi H1=H;ruo Dr≠空集,则Dr中存 在唯一的元素,xr,∈H,且 存在Dr上的关系Hr∈ H;H={,,H1,Hr}; (4)(D1,{H1})是一棵符合本定义的二叉树,称为根的左子树,(Dr,{Hr})是一棵 符合本定义的二叉树,称为根的右子树基本操作P: InitBiTree(&T)
数据结构实验报告图实验
邻接矩阵的实现 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; } }
《数据结构与算法》上机实验要求
《数据结构与算法》课程实验内容与要求 一、课程简介 本课程着重讲述①线性结构、树型结构、图等典型数据结构的逻辑特点、存储结构及其相应的基本算法。②各种查找算法③典型内部排序算法。 二、实验的作用、地位和目的 数据结构是一门技术基础课,通过实验深刻理解各种逻辑结构、存储结构的特性,培养为实际问题分析其数据对象、基本操作,选择逻辑结构、存储结构灵活应用基本算法,设计出具有专业水准的应用程序的能力。 三、实验方式与要求 ①首先要求学生在课下完成问题分析、算法设计,基本完成程序设计。 ②实验时,每位学生使用一台微机,独立调试,完成程序。 ③程序调试好后,由指导教师检测运行结果,并要求学生回答相关的问题。教师评出检查成绩。 ④学生记录程序的输入数据,运行结果及源程序。 ⑤在一周内完成实验报告。 四、考核方式与实验报告要求 实验成绩由指导教师根据学生的实验完成情况、源程序质量、回答问题情况、实验报告质量、实验纪律等方面给分。 学生在实验后的一周内提交实验报告。实验报告按照首页附件中实验报告模版书写。实验报告中应包括如下内容: ?实验内容按任课教师下达的实验任务填写(具体实验题目和要求); ?实验过程与实验结果应包括如下主要内容: 算法设计思路简介 算法描述:可以用自然语言、伪代码或流程图等方式 算法的实现和测试结果:包括算法运行时的输入、输出,实验中出现的问题及解决办法等 ?源程序清单与实验结果或其它说明可打印,并装订在实验报告首页之后。 ?实验报告雷同者,本次实验成绩为0分或雷同实验报告平分得分
五、实验的软硬件环境 硬件环境:PⅡ以上微型计算机 软件环境:Windows98/2000, VC++6.0或turbo C 六、实验内容安排 实验一线性表应用 实验时间:2016年3月14日1-4节(地点:7-215) 实验目的:理解线性表的逻辑特点;掌握顺序表、链表存储结构,以及线性表的基本操作,如插入、删除、查找,以及线性表合并等操作在顺序存储结构和链式存储结构上的实现算法,并能够在实际问题背景下的灵活运用线性表来解决问题,实现相应算法。 具体实验题目与要求:(任课教师根据实验大纲自己指定) 每位同学可从下面题目中选择1-2题实现: 1.一元稀疏多项式简单的计算器 1)问题描述:用线性表表示一元稀疏多项式,设计一个一元多项式运算器 2)要求: (1)采用单链表存储结构一元稀疏多项式 (2)输入并建立多项式 (3)输出多项式 (4)实现多项式加、减运算 2.单链表基本操作练习 1)问题描述:在主程序中提供下列菜单: 1…建立链表 2…连接链表 3…输出链表 0…结束 2)实验要求:算法中包含下列过程,分别完成相应的功能: CreateLinklist(): 从键盘输入数据,创建单链表 ContLinklist():将前面建立的两个单链表首尾相连 OutputLinklist():输出显示单链表 3.约瑟夫环问题 1)问题描述:有编号为1, 2…n 的n 个人按顺时针方向围坐一圈,每人持有一个正整数密码。开始给定一个正整数m,从第一个人按顺时针方向自1开始报数,报到m者出列,不再参加报数,这时将出列者的密码作为m,从出列者顺时针方向的下一人开始重新自1开始报数。如此下去,直到所有人都出列。试设计算法,输出出列者的序列。 2)要求: 采用顺序和链式两种存储结构实现 实验报告格式及要求:按附件中实验报告模版书写。(具体要求见四)