数据结构 实验指导书.doc

《数据结构 实验指导书.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构实验指导书目录数据结构实验指导书1目录1实验指导书概述2上机实验题目3实验一C语言相关知识复习3一、实验目的3二、实验内容3实验二单链表的插入、删除4一、实验目的4二、实验内容4三、实现提示4实验三栈及其应用6一、实验目的6二、实验内容6实验四二叉树的递归算法6一、实验目的6二、实验内容7实验五图的遍历8一、实验目的8二、实验内容8实验六有序表的查找8一、实验目的8二、实验内容8实验七哈希表8一、实验目的8二、实验内容8实验八内部排序算法的应用9一、实验目的9二、实验内容9实验指导书概述“数据结构”是计算机

2、专业一门重要的专业技术基础课程，是一门关键性核心课程。本课程系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了多种常用的查找和排序技术，并对其进行了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。由于以下原因，使得掌握这门课程具有较大难度：·内容多，时间短，给学习带来困难；·贯穿全书的动态链表存储结构和递归技术是学习中的重点和难点；·隐含在各部分的技术和方法丰富，也是学习的重点和难点；·先修课程中所介绍的专业性知识不多，加大了学习难度。　由于数

3、据结构课程的技术性与实践性，《数据结构课程实验》的设置十分必要。为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。　上机实践是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通过上机实践，使学生在可能短的时间内对数据结构知识的实践和应用有一个比较全面和系统的认识，达到理论与实践相结合的目的。　　为了达到上述目的，本指导书安排

4、了8个实验题目，它们与教科书的各章有紧密的关系，使学生在实验后能加深对课程内容的理解，增强动手能力。　　每个实验题目采取了统一的格式，由问题描述、基本要求、测试数据、实现提示等部分组成。　　问题描述旨在为读者建立问题提出的背景环境，指明问题“是什么”；　　要求则对问题进一步求精，划出问题的边界，指出具体的参量或前提条件，并规定该题的最低限度要求；　　测试部分旨在为检查学生上机作业提供方便，在完成实习题时应自己设计完整和严格的测试方案，当数据输入量较大时，提倡以文件形式向程序提供输入数据；　　实现提示对实现中的难点及

5、其解法思路等问题作了简要提示，个别问题给出了参考实现。　　下面带*的题目为选做题目。上机实验题目实验一C语言相关知识复习一、实验目的复习C语言中函数、数组、结构体、文件等概念，掌握它们的描述与操作方法；熟悉掌握C++中typedef、引用参数调用（&）的概念及使用方法，为理解数据结构课程的后续内容以及算法书写奠定基础。二、实验内容1问题描述：编写一个函数，求一个整数数组中的最大、最小值。要求：在函数声明中采用引用参数传递方式实现最大、最小值的返回。测试：在主函数中输入10个数，调用此函数，打印输出最大和最小值。2关

6、于指针的使用：用malloc方式分别申请两个指针，并实现两个指针内容的比较大小操作。要求：此功能在一个函数内实现，该函数接受两个整数值，存储到两个指针内容中，输出两者中的最大值。测试：从主函数中输入两个数，调用该函数，打印输出交换后的值。实验二单链表的插入、删除一、实验目的1、熟悉某种数据结构在计算机上实现的方法。2、掌握单链表的定义、创建、插入、删除、遍历等基本操作的实现。3、体会单链表操作、有序表插入、删除的一般方法。二、实验内容问题描述：已知递增有序的单链表A，编写算法实现向A中插入或删除一个元素，并保持A的

7、有序性。实验要求：1、结点的数据均为整型。2、若表中已经存在此元素，则不插入三、实现提示1.在已知的线性表中插入或删除，需要下面的辅助函数：线性表的创建、线性表的遍历2.在单链表表中插入或删除，需依次实现：a)单链表结构的定义b)单链表的创建（头插法或尾插法建表）c)单链表的遍历d)单链表的插入、删除（采用顺序查找方法，顺头指针往后，查找插入或删除位置，再修改指针）//头文件#include"stdlib.h"//预定义常量#defineNULL0//单链表的定义typedefstructLNode{intdata

8、;structLNode*next;}LNode,*LinkList;//单链表的创建voidCreate_List(LinkList&L){intdata;LinkListp,q;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;q=L;scanf("%d",&data);while(data!=0){p=(Li