2010数据结构实验指导书

《数据结构》实验指导书实验一、顺序表实验目的：熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作。

实验要求：了解并熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作的实现和应用。

实验内容：编写程序实现下列的要求：(1) 设数据元素为整数，实现这样的线性表的顺序存储表示。

(2) 键盘输入10个数据元素，利用顺序表的基本操作，建立该表。

(3) 利用顺序表的基本操作，找出表中的最大的和最小的数据元素（用于比较的数据元素为整数）。

(4) * 若数据元素为学生成绩（含姓名、成绩等字段），重新编程，实现上面的要求。

要求尽可能少地修改前面的程序来得到新程序。

（这里用于比较的字段为分数）练习及思考题：（1）顺序表的操作上有什么特点？（2）不固定数据元素的个数，而通过特殊数据来标记输入数据的结束，实现这样的输入操作。

实验二、链表实验目的：熟悉链式表的逻辑特性、存储表示方法的特点和链式表的基本操作。

实验要求：了解并熟悉链式表的逻辑特性、存储表示方法和链式表的基本操作的实现和应用。

实验内容：编写程序实现下列的要求：(1) 设学生成绩表中的数据元素为学生成绩（含姓名、成绩字段），实现这样的线性表的链式存储表示。

(2) 键盘输入若干个数据元素（用特殊数据来标记输入数据的结束），利用链表的基本操作（前插或后插算法），建立学生成绩单链表。

(3) 键盘输入关键字值x，打印出表中所有关键字值<=x的结点数据。

（用于比较的关键字字段为分数）。

(4) 输入关键字值x，删除表中所有关键字值<=x的结点。

（用于比较的关键字字段为分数）。

练习及思考题：（1）不同类型的数据元素所对应的链式表在类型定义和操作实现上有什么异同？（2）有头结点的链式表，有什么特点？实验三、栈的应用实验目的：熟悉栈的逻辑特性、存储表示方法和栈的基本操作。

实验要求：了解并熟悉栈的逻辑特性、顺序和链式存储表示方法和栈的基本操作的实现和应用。

实验内容：(1) 判断一个表达式中的括号（仅有一种括号，小、中或大括号）是否配对。

《数据结构》实验指导书齐晓轩编沈阳大学信息工程学院目录实验一：C语言运行环境、算法设计 1 实验二：顺序表的基本操作 3 实验三：线性链表的基本操作 5 实验四：顺序栈的基本操作 6 实验五：队列的基本操作7 实验六：串的基本操作8 实验七：数组和矩阵11 实验八：二叉树的基本操作12 实验九：图13 实验十：查找14 实验十一：排序15课程编号：1241331 课程类别：基础必修课适用层次：本科适用专业：计算机科学与技术计算机科学与技术（电子商务）课程总学时：80 适用学期：第4学期实验学时：30 开设实验项目数：11撰写人：齐晓轩审核人：刘天惠教学院长：范立南实验一：C语言运行环境、算法设计一、实验目的与要求1．熟悉TC环境的组成及使用方法。

2．了解C语言程序从编辑、编译、连接到运行并得到运行结果的过程。

3．学习把算法改成C程序的方法。

二、实验类型验证型三、实验原理及说明算法是指为了完成某一特定功能的指令序列，它阐述程序设计的总体思路。

四、实验仪器安装C语言环境（TC或VC++）的计算机若干台五、实验内容和步骤1．在开始实验之前，先建立自己的工作目录，可用自己的班级加学号或姓名命名。

2．熟悉VC环境的组成及使用。

3．了解算法设计。

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

编写自大到小依次输出顺序读入的三个数X、Y和Z的值的程序，并在TC或VC++环境下调试通过，最后写出程序的运行结果。

要求:包括主函数，排序函数和输出函数三部分。

在主程序中任意输入三个数，调用排序函数进行排序，在输出函数中输出排序结果。

六、注意事项注意算法在C语言编程环境中无法直接运行，需要改成C程序才能正确执行。

七、预习与思考题1．程序和算法的区别。

实验二：顺序表的基本操作一、实验目的与要求1．理解和掌握顺序表的结构类型定义方法。

2．掌握建立顺序表的基本方法。

3．掌握显示顺序表元素的基本方法。

《数据结构》实验指导书第一部分前言一、实验的目的《数据结构》是计算机学科一门重要的专业基础课程,也是计算机学科的一门核心课程。

本课程的另一重要教学目的是训练学生进行复杂程序设计的技能和培养良好程序设计的习惯，要做到这一点，上机实习是必须的。

数据结构实验是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。

通常，实验课题中的问题比平时的习题复杂得多，也更接近实际。

实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，训练学生实际动手进行程序设计和调试程序的能力，加深对数据结构相关概念和算法的理解。

通过完成本实验课程的实验，学生应学会并掌握本课程的基本和重点知识，深刻理解逻辑结构、物理结构和算法设计之间的关系，初步学会算法分析的方法，并能在一定范围内运用所掌握的分析方法进行算法分析，培养软件工作所需要的动手能力和作为一个软件工作者所应具备的科学工作方法和作风。

二、实验前的准备工作1．每个学生需配备一台计算机，操作系统需Windows2000/XP以上版本，软件需Visual C++6.0以上版本。

2．实验前要求学生按实验要求编写好相关实验程序，准备上机调试运行。

三、实验的步骤（一）建立一个文件夹，如“数据结构”，用来存放自己的所有实验程序，在该文件夹中建立子目录用来存放每个项目（一个子目录一个项目），如“顺序表”，项目中需要的所有文件都存在该文件夹中。

（二）新建一个项目文件1．双击Visual C++ 6.0快捷图标，进入Visual C++ 6.0集成开发环境；或者点击“开始”→“程序”→“Microsoft Visual Studio 6.0”→“Microsoft Visual C++ 6.0”进入Visual C++ 6.0集成开发环境。

2．单击“File”菜单，选择“New”命令3．创建一个项目文件并保存在项目所在文件夹中；3. 创建源程序文件并保存在项目所在文件夹中；4．输入源程序；5．单击“保存”按钮保存源程序。

数据结构实验指导书淮阴工学院计算机工程学院二O一一年八月目录实验1 线性表及其应用 (1)实验2 栈和队列及其应用 (5)实验3 二叉树及其应用 (10)实验4 图及其应用 (13)实验5 查找 (14)实验6 排序 (16)实验1 线性表及其应用实验目的1.加深对线性表的结构特性的理解；2.熟练掌握单链表类的描述方法及其C++实现；3.掌握线性表的链式存储结构的应用方法；4.从时间和空间的角度对操作算法进行分析；5.加强程序的设计能力和调试能力。

实验学时：建议2~4学时实验内容内容1：制作体育彩票（10选7）的选号器类。

【说明】（1）体育彩票（10选7）的7个号可以重复；（2）建议选号器类从单链表类继承。

用首尾相连的链式结构，这样可以更逼真地模拟“摇奖”过程；而每个号的“摇动”次数可用随机数来确定。

（3）怎样产生随机数？可以利用C++语言中的种子函数srand( )和产生伪随机数函数rand( )来实现。

（include<STDLIB.H>）a)首先，给srand(m )提供一个“种子”m，它的取值范围是从0～65535。

b)然后，调用rand( )，是伪随机数，它会根据提供给srand( )的“种子”值返回一个随机数（在0～32767之间）。

c)根据需要多次调用rand( )，从而不断地得到新的随机数。

d)无论何时，你都可以给srand( )提供一个新的“种子”，从而进一步“随机化”rand( )的输出结果。

例如，取m=17，则执行了srand(17)之后，再执行rand( )函数，将得到输出值94；第二次调用rand( )，会得到26,……反复调用rand( )就能产生一系列的随机数。

注意：若m不变，则rand( )的输出系列也不变，总是94,26,602,…等等。

所以，建议摇号的“种子”选当前日期或时间，以保证每天的摇号值都不相同。

【选做内容】实现摇奖和对奖操作。

内容2：约瑟夫（Joseph）环问题【问题描述】约瑟夫问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈,从1起报到k则出圈，下一个人再从1报起，如此下去直到圈中只有一人为止。

《数据结构》实验指导书软件学院2011年9月概述实习目的和要求《数据结构》在计算机科学中是一门实践性较强的专业基础课, 上机实习是对学生的一种全面综合训练, 是与课堂听讲、自习和练习相辅相成的必不可少的一个教学环节。

实习着眼于原理与应用的结合, 使学生学会把学到的知识用于解决实际问题, 起到深化理解和灵活掌握教学内容的目的。

同时, 通过本课程的上机实习, 使学生在程序设计方法及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

实习包括的步骤1. 简要描述题目要求, 对问题的描述应避开算法及所涉及的数据类型, 只是对所需完成的任务做出明确的陈述, 例如输入数据的类型、值的范围以及输入的形式, 输出数据的类型、值的范围以及输出的形式。

2. 选定数据结构, 写出算法, 根据自顶向下发展算法的方法, 首先描述算法的基本思想, 然后进行算法细化, 再对所设计的算法的时间复杂性和空间复杂性进行简单分析。

3. 准备好上机所需的程序, 选定一种程序设计语言（如C 语言）, 手工编好上机程序, 并进行反复检查, 使程序中的逻辑错误和语法错误减少到最低程度。

对程序中有疑问的地方, 应做出标记, 以便在上机时给予注意。

4．上机输入和调试程序, 在调试程序过程中除了系统的问题以外, 一般应自己独立解决。

在程序调试通过后, 打印输出程序清单和运行结果。

5．上机结束后, 总结和整理实习报告。

实习报告的内容1．简述题目要解决的问题是什么, 并说明输入和输出数据的形式。

2．简述存储结构和算法的基本思想。

3．列出调试通过的源程序。

4．列出上面程序对应的运行结果。

分析程序的优缺点、时空性能以及改进思想, 写出心得体会。

实验一线性表一. 目的与要求本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现, 提高分析和解决问题的能力。

要求仔细阅读并理解下列例题, 上机通过, 并观察其结果, 然后独立完成后面的实习题。

《数据结构》实验指导书实验一线性表【实验目的】1、掌握用Turbo c上机调试线性表的基本方法；2、掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；3、运用线性表解决线性结构问题。

【实验学时】4 学时【实验类型】设计型【实验内容】1、顺序表的插入、删除操作的实现；2、单链表的插入、删除操作的实现；3、两个线性表合并算法的实现。

(选做)【实验原理】1、当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。

若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置；2、当我们在线性表的链式存储结构上的第i个位置上插入一个元素时，只需先确定第i个元素前一个元素位置，然后修改相应指针将新元素插入即可。

若是欲删除第i个元素时，也必须先确定第i个元素前一个元素位置，然后修改相应指针将该元素删除即可；3、详细原理请参考教材。

【实验步骤】一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素1、通过键盘读取元素建立线性表；2、指定一个元素，在此元素之前插入一个新元素；3、指定一个元素，删除此元素。

二、用C语言编程实现建立一个单链表，并在此表中插入一个元素和删除一个元素1、通过键盘读取元素建立单链表；2、指定一个元素，在此元素之前插入一个新元素；3、指定一个元素，删除此元素。

三、用C语言编程实现两个按递增顺序排列线性表的合并1、编程实现合并按递增顺序排列的两个顺序表算法；2、编程实现合并按递增顺序排列的两个单链表算法。

【思考问题】结合实验过程，回答下列问题：1、何时采用顺序表处理线性结构的问题为最佳选择；2、何时采用链表处理线性结构的问题为最佳选择。

【实验报告要求】1、根据对线性表的理解，如何创建顺序表和单链表；2、实现顺序表插入和删除操作的程序设计思路；3、实现链表插入和删除操作的程序设计思路；4、实现两表合并操作的程序设计思路；5、调试程序过程中遇到的问题及解决方案；6、本次实验的结论与体会。

计算机科学与技术专业数据结构课程设计指导书数据结构课程教学组2009.8.2【课程设计目的】“数据结构”是计算机科学与技术专业一门十分重要的专业技术基础课，计算机科学各领域及有关的应用软件都要使用到各种数据结构。

在我国，”数据结构与算法”已经作为理工科非计算机专业必修的信息技术基础课程之一。

世界上许多科技人员对学习、研究数据结构和算法都非常重视，对于从事计算机科学及其应用的科技工作者来说，数据结构与算法更是必须透彻地掌握的重要基础。

学习数据结构与算法的最终目的是解决实际的应用问题，特别是非数值计算类型的应用问题。

课程设计是加强学生实践能力的一个强有力手段。

课程设计所安排的题目，在难度和深度方面都大于平时的上机训练，要求同学在完成设计和编程大型作业的过程中，深化对数据结构与算法课程中基本概念、理论和方法的理解；训练综合运用所学知识处理实际问题的能力，强化面向对象的程序设计理念；使同学的程序设计与调试水平有一个明显的提高。

课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。

严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。

【课程设计要求】学生必须仔细阅读《数据结构》课程设计任务书与本指导书，认真主动完成课设的要求。

有问题及时主动通过各种方式与教师联系沟通。

学生要发挥自主学习的能力，充分利用时间，安排好课程设计的时间计划，并在课程设计过程中不断检测自己的计划完成情况，及时向教师汇报。

课程设计按照教学要求需要两周时间完成，由于安排的课内机时有限而且数据结构课程本身没有课内上机学时, 为保证完成课程设计任务，每位同学必须做好充分准备。

数据结构课程是多门重要专业课的先行课程，难度较大，需要较好的程序设计和调试能力。

如果学生能够按照要求，从时间和精力上保证完全的投入，相信能够有很大的收获。

具体要求如下：1.诚实代码要求：每个学生要独立完成设计任务，严禁抄袭现象。

数据结构实验指导书吉林大学珠海学院计算机系2012.12实验目的与要求《数据结构》是计算机学科重要的专业基础课，北京市高校已将该课作为理工科非计算机专业的提高课程，北京大学将此课列为理工科非计算机专业必修课已经超过15 年。

该课程主要研究信息在计算机中的组织和表示方法。

上机实验是本课程教学至关重要的环节，通过上机实验，使学生在数据结构的逻辑结构定义、存储表示、操作的实现、数据结构的选择和应用、算法实践等方面加深对课程内容的理解，训练学生进行复杂程序设计的技能和培养良好程序设计的习惯。

考虑到大一上学期学习过C程序设计，本学期有C课程设计和C++程序设计，故数据结构课程的实验不安排验证性实验，按课程设计要求。

具体说是期初布置题目，按学号顺序确定如下题目，学生自己准备，期中检查，15周开始验收。

验收时间安排在周末。

实验内容从以下题目中选一题题目一、航空客运订票系统题目二、文章编辑题目三、宿舍管理查询软件题目四、校园导航系统题目五、散列法的实验研究题目六、小型图书馆管理系统（链表的插入，排序，查询，删除）题目七、学生搭配问题题目八、敢死队问题题目九、教学计划编制问题题目十、活期储蓄帐目管理题目十一、通讯录的制作题目十二、二叉排序树的实现题目十三、利用栈求表达式的值题目十四、走迷宫游戏题目十五、顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现题目十六、线索二叉树的应用题目十七、稀疏矩阵实现与应用题目十八、树的应用题目十九、图的遍历和生成树求解实现题目二十、排序综合题目二十一、纸牌游戏题目二十二、利用栈求表达式的值，可供小学生作业，并能给出分数题目二十三、数制转换问题题目二十四、停车场问题题目二十五、学生成绩管理系统题目二十六、哈夫曼编码/译码器题目二十七、特殊矩阵的压缩存储算法的实现题目二十八、产品进销存管理系统题目二十九、客户消费积分管理系统题目三十、约瑟夫环题目三十一、任意长的整数加法题目三十二、广义表的应用题目三十三、关键路径问题题目三十四、构造可以使n个城市连接的最小生成树题目三十五、神秘国度的爱情故事题目三十六、利用Hash技术统计C源程序中关键字的频度题目一、航空客运订票系统通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）；查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。

计算机科学与技术专业数据结构课程设计指导书数据结构课程教学组2009.8.2【课程设计目的】“数据结构”是计算机科学与技术专业一门十分重要的专业技术基础课，计算机科学各领域及有关的应用软件都要使用到各种数据结构。

在我国，”数据结构与算法”已经作为理工科非计算机专业必修的信息技术基础课程之一。

世界上许多科技人员对学习、研究数据结构和算法都非常重视，对于从事计算机科学及其应用的科技工作者来说，数据结构与算法更是必须透彻地掌握的重要基础。

学习数据结构与算法的最终目的是解决实际的应用问题，特别是非数值计算类型的应用问题。

课程设计是加强学生实践能力的一个强有力手段。

课程设计所安排的题目，在难度和深度方面都大于平时的上机训练，要求同学在完成设计和编程大型作业的过程中，深化对数据结构与算法课程中基本概念、理论和方法的理解；训练综合运用所学知识处理实际问题的能力，强化面向对象的程序设计理念；使同学的程序设计与调试水平有一个明显的提高。

课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。

严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。

【课程设计要求】学生必须仔细阅读《数据结构》课程设计任务书与本指导书，认真主动完成课设的要求。

有问题及时主动通过各种方式与教师联系沟通。

学生要发挥自主学习的能力，充分利用时间，安排好课程设计的时间计划，并在课程设计过程中不断检测自己的计划完成情况，及时向教师汇报。

课程设计按照教学要求需要两周时间完成，由于安排的课内机时有限而且数据结构课程本身没有课内上机学时, 为保证完成课程设计任务，每位同学必须做好充分准备。

数据结构课程是多门重要专业课的先行课程，难度较大，需要较好的程序设计和调试能力。

如果学生能够按照要求，从时间和精力上保证完全的投入，相信能够有很大的收获。

具体要求如下：1.诚实代码要求：每个学生要独立完成设计任务，严禁抄袭现象。

引言概述正文内容
1.实验环境配置
1.1硬件要求
计算机硬件配置要求
操作系统要求
附加硬件设备要求（如虚拟机等）
1.2软件要求
编程语言要求（如C/C++、Java等）开发环境配置（如IDE、编译器等）1.3实验库和工具
实验需要使用的库文件和工具
如何获取和配置实验库和工具
2.实验内容介绍
2.1实验目标和背景
数据结构实验的作用和意义
实验背景和相关应用领域介绍
2.2实验概述
实验内容的大致流程和步骤
实验中可能遇到的问题和挑战
2.3实验要求
对学生实验流程和实验结果的要求
实验过程中需要注意的事项和技巧
3.实验步骤
3.1实验准备
配置实验环境
获取实验所需数据和文件
3.2实验具体步骤
根据实验要求将数据结构知识应用到具体问题中根据实验要求实现相应的算法和数据结构
3.3实验示例代码
提供示例代码以供学生参考和学习
解析示例代码中的关键步骤和实现细节
4.实验答案
4.1实验题目
实验题目及相关说明
确定实验的具体要求和目标
4.2实验答案解析
对实验答案的具体实现进行解析
对实验中可能遇到的问题和错误进行分析和解决4.3实验答案示例
提供实验答案的示例代码
解析实验答案中的关键实现步骤和说明
5.实验总结
5.1实验成果评估
对学生实验成果进行评估
分析实验结果的优点和不足
5.2实验心得
学生对本次实验的收获和感想
学生对未来实验的建议和展望
总结。