第一篇:数据结构第一次实验要求
数据结构实验课
第一组实验(202_.05.6)
一、线性表
1、题集P79,实验1.1
1)把描述的问题中包含的相关对象及其之间的关系找出来;
2)画一张对象及其关系图;
3)把每个对象投影到一个线性表;
4)把关系投影到表上或表间操作;
5)用C或C++实现;
6)上机调试。
2、参照教材P31,算法2.12,实现合并有序单链表(均带头节点)操作;
3、自学题集P83实习报告,用对象及其关系图描述问题,并分析它们的实现细节;
4、从你学习、生活环境中举出一个线性表的应用实例,分析它包含的对象及其之间的关系。尝试着用线性表顺序表示和链式表示来实现。
二、队列与栈
1、从你学习生活中找出一个典型的队列的实例,分析它的特点,并参照教材P60~65中的算法,分别实现这个队列的链式表示和顺序表示。
2、从你学习生活中找出一个典型的栈的实例,分析并与队列实例进行比较,找出它们的异同,并参照教材P45~47中的内容,实现栈的两种存储模式。
3、回文识别:自定义顺序栈及队列,并在实现“回文识别算法”中运用.题集P26, 3.31
三、要求:把自己严格按照一个入门专业人员来要求。
1、以上实验要求可以以组为单位讨论完成,但每组人数不得超过5人,且需要分配一个小组长负责本组的学习组织和进展跟踪;
2、把以上实验中需要的分析步骤和分析结果写成正式的报告,以组为单位在实验课上进行讲解(尽量让每一位同学表达一次);
3、实现部分在课下组织讨论,尽量提前写出详细实现草稿,实验课上进行调试和实验结果汇报;
4、讨论和汇报过程中,每位同学要做好笔记,分析对比自己和他人在处理问题中存在的不同,总结自己的不足和长处,以及其他同学给你的借鉴,为进一步改进自己的学习方式方法以及态度给出切实可行的建议。
第二篇:《数据结构》上机实验的目的和要求
《数据结构》上机实验的目的和要求
通过上机实验加深对课程内容的理解,增加感性认识,提高软件设计、编写及调试程序的能力。
要求所编的程序能正确运行,并提交实验报告。实验报告的基本要求为:
1、需求分析:陈述程序设计的任务,强调程序要做什么,明确规定:
(1)输入的形式和输出值的范围;
(2)输出的形式;
(3)程序所能达到的功能;
(4)测试数据:包括正确的输入输出结果和错误的输入及输出结果。
2、概要设计:说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。
3、详细设计:提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。
4、调试分析:
(1)调试过程中所遇到的问题及解决方法;
(2)算法的时空分析;
(3)经验与体会。
5、用户使用说明:说明如何使用你的程序,详细列出每一步操作步骤。
6、测试结果:列出对于给定的输入所产生的输出结果。若有可能,测试随输入规模的增长所用算法的实际运行时间的变化。
第三篇:数据结构实验教案
第一次实验 线性表
(一)实验目的和要求:
1.熟悉VC集成环境
2.会定义线性表的顺序结构和链式结构
3.熟悉对线性表的基本操作,如插入、删除等
(二)实验内容和原理或涉及的知识点(综合性实验):
自己编写程序实现线性表的建立、插入、删除等功能。
写出线性表、顺序表、链表的定义,简单写出主要算法的思路。
(三)实验条件:安装有VC的计算机
(四)实验设计方案
设计的顺序表算法有: 1.初始化顺序表 2.顺序表的插入操作 3.顺序表的删除操作 设计的链表算法有: 1.建立链表
2.链表的插入操作 3.链表的删除操作 4.链表数据元素的访问
(五)实验过程、数据和实验结果记录
程序代码(略)
实验过程中输入/输出数据、程序运行结果的记录。(一定要有!)
第二次实验 栈和队列
(一)实验目的和要求:
1.熟练掌握栈和队列的结构,以及这种数据结构的特点 2.会定义顺序栈、循环队列,能实现栈、队列的基本操作 3.会利用栈解决典型问题,如数制转换等
(二)实验内容和原理或涉及的知识点(综合性实验):
自己编写程序实现栈(或者队列)的各种基本操作,如初始化、入栈、出栈、判断栈是否为空等
写出栈的定义,简单写出主要算法的思路。
(三)实验条件:安装有VC的计算机
(四)实验设计方案
设计的算法有: 1.初始化栈 2.入栈 3.出栈
4.判断栈是否为空 5.十进制转换为八进制
(五)实验过程、数据和实验结果记录
程序代码(略)
实验过程中输入/输出数据、程序运行结果的记录。(一定要有!)
第三次实验 二叉树
(一)实验目的和要求:
1.熟练掌握二叉树的结构,以及这种数据结构的特点 2.会定义二叉树的链式存储结构
3.能实现二叉树的建立、遍历等功能,需要完成先序遍历、中序遍历和后序遍历递归算法
(二)实验内容和原理或涉及的知识点(综合性实验):
自己编写程序实现二叉树的各种基本操作,如二叉树的建立(头插法或者尾插法),遍历等 写出二叉树的定义,简单写出主要算法的思路。
(三)实验条件:安装有VC的计算机
(四)实验设计方案
设计的算法有: 1.递归建立二叉树 2.先序遍历二叉树 3.中序遍历二叉树 4.后序遍历二叉树
(五)实验过程、数据和实验结果记录
程序代码(略)
实验过程中输入/输出数据、程序运行结果的记录。(一定要有!)
第四次实验
查找
(一)实验目的和要求:
1.熟练掌握查找算法的基本思想,以及算法的适用条件
2.会定义静态查找表的顺序结构,能实现顺序查找、二分查找
(二)实验内容和原理或涉及的知识点(综合性实验):
自己编写程序实现顺序查找、二分查找。
写出静态查找表的定义,简单写出主要算法的思路。
(三)实验条件:安装有VC的计算机
(四)实验设计方案
设计的算法有: 1.建立静态查找表 2.顺序查找
3.建立有序的静态查找表 4.二分查找
(五)实验过程、数据和实验结果记录
程序代码(略)
实验过程中输入/输出数据、程序运行结果的记录。(一定要有!)
第四篇:数据结构实验指导书
目 录
实验规则················································2 实验环境················································2 实验报告要求············································3 实验一 单链表
(一)······································4 实验二 单链表
(二)······································5 实验三 栈···············································6 实验四 二叉树···········································7 实验五 最短路径·········································8 实验六 内部排序·········································9
实 验 规 则
为了顺利完成实验教学任务,确保人身、设备的安全,培养严谨、踏实、实事求是的科学作风和爱护国家财产的优良品质,特制定以下实验规则:
1、实验前必须充分预习,完成指定的预习任务。预习要求如下:
(1)认真阅读指导书,进行必要的设计与计算。(2)熟悉实验内容。
(3)预先复习,并按要求编写程序。(4)未完成预习任务者不得进入实验室。
2、遵守以下纪律:
(1)在实验室不得做和实验无关的事情。
(2)进行任课老师指定内容以外的实验,必须经指导教师同意。(3)遵守纪律,不迟到。
(4)保持实验室内安静、整洁,爱护公物,不许乱写乱画。
实 验 环 境
本实验在386以上的微机上进行,运行环境为VC6.0。
实验报告要求
1、实验题目 2.实验目的 3.实验环境
4.实验内容与完成情况(可以附上自主设计的源程序)5.出现的问题及对问题的解决方案 6.实验思考:(学生对本次实验的收获的总结)
实验一 单链表
(一)一、实验目的
掌握线性表的链式存储结构及其基本操作。
二、预习要求
1、看懂书上的算法,深入理解链表的物理存储模式和逻辑模式。
2、根据要求,编写程序准备上机调试。
三、实验内容
实现一个简单的学生信息管理系统,该系统的功能有:
1、利用单链表建立学生基本信息表
2、浏览每个学生的信息
3、根据学号查询某个学生的基本信息
4、添加学生信息到单链表中
5、删除一个学生的信息
四、实现提示
设计结点的结构体类型,包括学生的学号、姓名、年龄、性别;要求设计一个简单的菜单界面,根据需要选择所要进行的操作;构造函数,每一个函数实现上述的一个功能。
实验二 单链表
(二)一、实验目的
掌握线性表的链式存储结构及其基本操作。
二、预习要求
1、看懂书上的算法,深入理解链表的物理存储模式和逻辑模式。
2、根据要求,编写程序准备上机调试。
三、实验内容
1、实现单链表的就地逆置。
2、建立两个非递减有序单链表,然后合并成一个非递减链表。
3、建立两个非递减有序单链表,然后合并成一个非递增链表。
4、编写一个主函数,调试上述算法。
四、选做题、思考题
1、如何用带表头结点的单链表作为多项式的存储表示,实现两个多项式的相加。
2、约毖夫环的实现。
3、如何利用文件实现学生信息的存取。
实验三 栈
一、实验目的
深入了解并掌握栈的特性及其在实际中的应用;熟练掌握栈的算法实现;运用栈操作求解实际问题。
二、预习要求
1、看懂书上的算法,深入理解栈的特性和存储结构,以便在实际问题背景下灵活运用。
2、根据要求,编写程序准备上机调试。
三、实验内容
利用栈实现数据的分类,要求当输入为偶数时进栈1,当输入为奇数时进栈2,最后分别从栈1和栈2输出偶数和奇数序列。
四、实现提示
1、开辟一个连续的存储空间,实现两个栈顺序存储空间的共享;分别在两端设置栈顶指针,并按要求实现栈操作。
2、采用顺序存储实现栈的初始化、入栈、出栈操作。
五、选做题、思考题
1、两栈空间共享时,栈满的条件是什么?
2、为停车场编制进行管理的模拟程序(习题集P96,2.1)。
3、编写程序,利用栈实现表达式求值。
实验四 二叉树
一、实验目的
通过实践掌握二叉树的存储结构和遍历思想;掌握二叉树的常见算法的程序实现。
二、预习要求
二叉树的三种遍历方法。
三、实验内容
1、输入字符序列,建立二叉链表。
2、利用栈,编写非递归算法,编程实现二叉树的中序遍历。
3、求二叉树的叶子结点个数。
4、在主函数中设计一个简单的菜单,分别调试上述算法。
四、选做题、思考题
1、如何实现二叉树的后序遍历(非递归)。
2、如何求二叉树的高度。
实验五 最短路径(旅游景点导游咨询模拟)
一、实验目的
利用图的最短路径原理为用户提供路径咨询,掌握求最短路径的算法并编程实现。
二、预习要求
学习了解图的存储结构,掌握求最短路径的两种算法。
三、实验内容
设计一个旅游景点导游模拟程序,为来访的客人提供景点最短路径的信息查询服务,任意选取n城市,构成一个有向带权图,图中顶点表示城市,边上的权值表示两点间的距离,根据用户指定的始点和终点输出相应的最短路径。
四、实现提示
咨询以用户和计算机的对话方式进行,由用户输入起始点和终点,输出信息:最短路径是多少?并指出所经过的城市。存储结构可选用邻接矩阵。
五、选做题、思考题
1.如何实现对城市信息进行编辑(如:添加或删除)的功能。
2.用邻接表作存储结构,求一指定景点出发,到其余各景点的最短路径。
实验六 内部排序
一、实验目的
直观感受算法的关键字比较次数和关键字移动次数。
二、预习要求
1、常见的排序算法(插入排序、交换排序、选择排序、归并排序、基数排序等)的思想、特点及其适用条件。
2、根据要求,编写程序准备上机调试。
三、实验内容
1、对直接插入排序和简单选择排序算法进行关键字比较次数和关键字移动次数的比较。
2、利用链式存储结构,编写程序,实现直接插入排序和冒泡排序。
四、实现提示
测试数据可以为几组典型的数据:正序、逆序、乱序。
五、选做题、思考题
1、快速排序算法的非递归实现。
2、结合实验,理解针对不同待排元素的特点而选择不同排序方法的重要性。
3、如何对本实验进行时间、空间的复杂度分析。
第五篇:数据结构 实验指导书
数 据 结 构 实 验 指 导 书
数据结构实验指导书
目录
数据结构实验指导书.......................................................................................................................1
目录...........................................................................................................................................1 实验指导书概述...............................................................................................................................2 上机实验题目...................................................................................................................................3
实验一 C语言相关知识复习................................................................................................3
一、实验目的...................................................................................................................3
二、实验内容...................................................................................................................3 实验二 单链表的插入、删除...............................................................................................3
一、实验目的...................................................................................................................3
二、实验内容...................................................................................................................3
三、实现提示...................................................................................................................4 实验三 栈及其应用.................................................................................................................5
一、实验目的...................................................................................................................5
二、实验内容...................................................................................................................5 实验四 二叉树的递归算法.....................................................................................................6
一、实验目的...................................................................................................................6
二、实验内容...................................................................................................................6 实验五 图的遍历.....................................................................................................................7
一、实验目的...................................................................................................................7
二、实验内容...................................................................................................................7 实验六 有序表的查找.............................................................................................................7
一、实验目的...................................................................................................................7
二、实验内容...................................................................................................................7 实验七 哈希表.........................................................................................................................7
一、实验目的...................................................................................................................7
二、实验内容...................................................................................................................7 实验八 内部排序算法的应用.................................................................................................8
一、实验目的...................................................................................................................8
二、实验内容...................................................................................................................8
实验指导书概述
“数据结构”是计算机专业一门重要的专业技术基础课程,是一门关键性核心课程。本课程系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法,介绍了多种常用的查找和排序技术,并对其进行了性能分析和比较,内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。
由于以下原因,使得掌握这门课程具有较大难度: 内容多,时间短,给学习带来困难;
贯穿全书的动态链表存储结构和递归技术是学习中的重点和难点; 隐含在各部分的技术和方法丰富,也是学习的重点和难点; 先修课程中所介绍的专业性知识不多,加大了学习难度。
由于数据结构课程的技术性与实践性,《数据结构课程实验》的设置十分必要。为了帮助学生更好地学习本课程,理解和掌握算法设计所需的技术,为整个专业学习打好基础,要求运用所学知识,上机解决一些典型问题,通过分析、设计、编码、调试等各环节的训练,使学生深刻理解、牢固掌握所用到的一些技术。
上机实践是对学生的一种全面综合训练,是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通过上机实践,使学生在可能短的时间内对数据结构知识的实践和应用有一个比较全面和系统的认识,达到理论与实践相结合的目的。
为了达到上述目的,本指导书安排了8个实验题目,它们与教科书的各章有紧密的关系,使学生在实验后能加深对课程内容的理解,增强动手能力。
每个实验题目采取了统一的格式,由问题描述、基本要求、测试数据、实现提示等部分组成。
问题描述旨在为读者建立问题提出的背景环境,指明问题“是什么”;
要求则对问题进一步求精,划出问题的边界,指出具体的参量或前提条件,并规定该题的最低限度要求;
测试部分旨在为检查学生上机作业提供方便,在完成实习题时应自己设计完整和 严格的测试方案,当数据输入量较大时,提倡以文件形式向程序提供输入数据;
实现提示对实现中的难点及其解法思路等问题作了简要提示,个别问题给出了参考实现。
下面带*的题目为选做题目。
上机实验题目
实验一 C语言相关知识复习
一、实验目的
复习C语言中函数、数组、结构体、文件等概念,掌握它们的描述与操作方法;熟悉掌握C++中typedef、引用参数调用(&)的概念及使用方法,为理解数据结构课程的后续内容以及算法书写奠定基础。
二、实验内容 问题描述:编写一个函数,求一个整数数组中的最大、最小值。
要求:在函数声明中采用引用参数传递方式实现最大、最小值的返回。测试:在主函数中输入10个数,调用此函数,打印输出最大和最小值。2 关于指针的使用:
用malloc方式分别申请两个指针,并实现两个指针内容的比较大小操作。要求:此功能在一个函数内实现,该函数接受两个整数值,存储到两个指针内容中,输出两者中的最大值。
测试:从主函数中输入两个数,调用该函数,打印输出交换后的值。
实验二 单链表的插入、删除
一、实验目的
1、熟悉某种数据结构在计算机上实现的方法。
2、掌握单链表的定义、创建、插入、删除、遍历等基本操作的实现。
3、体会单链表操作、有序表插入、删除的一般方法。
二、实验内容
问题描述:已知递增有序的单链表A,编写算法实现向A中插入或删除一个元素,并保持A的有序性。
实验要求:
1、结点的数据均为整型。
2、若表中已经存在此元素,则不插入
三、实现提示
1.在已知的线性表中插入或删除,需要下面的辅助函数:线性表的创建、线性表的遍历
2.在单链表表中插入或删除,需依次实现:
a)单链表结构的定义
b)单链表的创建(头插法或尾插法建表)c)单链表的遍历
d)单链表的插入、删除(采用顺序查找方法,顺头指针往后,查找插入或删除位置,再修改指针)
//头文件
#include “stdlib.h” //预定义常量 #define NULL 0
//单链表的定义
typedef struct LNode{ int data;struct LNode *next;}LNode,*LinkList;//单链表的创建
void Create_List(LinkList &L){ int data;LinkList p,q;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;
q=L;
scanf(“%d”,&data);while(data!=0){
p=(LinkList)malloc(sizeof(LNode));
p->data=data;
p->next=q->next;
q->next=p;
q=p;
scanf(“%d”,&data);} }
//单链表的遍历
void TranverseList(LinkList L){
LinkList p;
p=L->next;
if(p==NULL)
{
printf(“niln”);
return;
}
while(p!=NULL)
{
printf(“%d ”,p->data);
p=p->next;
}
printf(“n”);}
实验三 栈及其应用
一、实验目的
1、熟悉栈的顺序表示与实现。
2、熟悉栈的应用。
3、理解并掌握递归函数的设计与实现。
二、实验内容 问题描述:利用栈实现十进制数n转化为d进制数 要求:
1)输入一个n和d,打印输出d进制数序列。
2)利用顺序栈来实现十进制数n转化为其他d进制数。此时,需要同时实现初始化空栈、入栈、出栈、判栈空等辅助功能。测试数据:
(1)输入n:1348
d:8 输出:2504(2)输入n:9
d:8 输出:11(3)输入n:0
d:8 输出:0 2 问题描述:利用栈实现算术表达式求值。要求:
1)参与运算的操作数为10以内的数值。测试数据:
自拟。
实验四 二叉树的递归算法
一、实验目的
1、掌握二叉树的表示与实现。
2、掌握二叉树的定义、创建、遍历等基本操作的实现。
3、熟悉求二叉树深度等递归算法的设计与实现。
二、实验内容
问题描述:已知二叉树t,分别采用顺序存储结构、二叉链表存储结构实现求二叉树的深度,并对二叉树分别进行中序遍历。要求:
1、二叉树分别采用顺序或二叉链表存储。
2、树中的数据类型约定为整型。测试数据:
1、输入序列:-+aØØ*bØØ-cØØdØØ/eØØfØØ创建二叉树; 输出:深度:5
前序序列:-+a*b-cd/ef
中序序列:a+b*c-d-e/f
后序序列:abcd-*+ef/-T:d / e f
2、t=nil
输入:Ø
输出:深度:0 实验五 图的遍历
一、实验目的
熟悉图的基本操作,掌握图遍历的设计与实现。
二、实验内容
问题描述:已知的描述校园景点的图,实现对该图的深度优先和广度优先遍历。要求:
图采用邻接矩阵存储,顶点信息包括景点的名称和简单描述。
实验六 有序表的查找
一、实验目的
1、理解各种查找方法的基本思想
2、熟悉有序表查找方法的算法实现
二、实验内容 已知一有序的序列{1,3,5,7,9},采用折半法分别查找3和6。
2已知输入一无序的序列{5,1,3,9,7},创建一棵二叉排序树,然后对其遍历,输出递增有序的序列。
实验七 哈希表
一、实验目的
理解哈希表的概念和基本操作;熟悉哈希表的创建、查找、插入的算法实现。
二、实验内容
问题描述:已知11位好友的名字各不相同,设计并实现一个哈希表,根据好友的名字,可以取得其生日。要求:
1、好友的信息包含名字和生日两个数据项,其中好友的名字为主键,用汉语拼音形式存放;
2、哈希函数采取:好友名字中所有拼音字母ASCII码值的和 MOD 11(除以1取余);
3、采取线性探测再散列的方式处理冲突。
实验八 内部排序算法的应用
一、实验目的
理解各种内部排序方法的基本思想;熟悉各种内部排序方法的算法实现
二、实验内容
问题描述:已知一序列{503,087,512,061,908,170,897,275,653,426},分别采取下列排序方法对其进行排序:
(1)直接插入排序;
(2)简单选择排序;
(3)起泡排序;(4)快速排序;(5)堆排序。