《数据结构》课程实验指导书汇.doc

数学与计算机学院 《数据结构》课程实验指导书 适用专业: 计算机科学与技术 目 录 第二部分 实验指导 3 实验一 线性表的插入和删除 3 实验二 线性结构（二）－栈和队列 13 实验三 查找算法 18 实验四 排序算法 25 实验五 二叉树的操作 27 实验六 图的操作 31 第一部分 绪论 本指导书是根据《数据结构》课程实验教学大纲编写的，适用于计算机科学与技术专业。 本课程实验的作用与任务（楷体小三号） 该课程实验的作用与任务是让同学们掌握 序 号 实验项目名称 学 时 教学目标、要求 1 线性结构 （线性表的插入和删除 4 掌握用Turbo C上机调试线性表的基本方法； 掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。 掌握握单链表的基本操作：插入、删除、查找等运算 *2 线性结构（二） 4 掌握栈的基础知识、结构特点及应用； 掌握队列的结构特点和基本操作 3 查找算法 3 掌握查找表的定义和存贮； 掌握查找常用方法及过程； 实现顺序查找、二分查找、二叉排序树查找等算法。 4 排序算法 3 掌握常用的排序方法，并掌握用高级语言实现排序算法的方法； 深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用； 了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。 5 二叉树的操作 4 进一步掌握指针变量、动态变量的含义； 掌握二叉树的结构特征，以及各种存储结构的特点及适用范围； 掌握用指针类型描述、访问和处理二叉树的运算。 6 图的操作 4 掌握图的基本存储方法； 掌握有关图的操作算法并用高级语言实现； 熟练掌握图的两种有哪些信誉好的足球投注网站路径的遍历方法。 合　　计 18 注：有*号的表示是选开的实验，学生自由上机完成。 第二部分 实验指导 实验一 线性表的插入和删除 实验目的 掌握用Turbo C上机调试线性表的基本方法； 掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。 掌握握单链表的基本操作：插入、删除、查找等运算 实验要求 1、顺序表要用函数creatlist()随机生成,用三个函数完成顺序表的插入，删除和按值查找。 2、用四个函数实现单链表的建立、插入、删除和查找。 3、保存和打印出程序的运行结果，并结合程序进行分析。 4、打印出文件清单。 实验原理 线性表是最常用的而且也是最简单的一种数据结构，线性表是N个数据元素的有限序列。例如26个英文元素的字母表：（A，B，C，D，···）。其数据结构的描述为：Linear_list=(D,R)其中：D={ai|ai属于D0,i=1,2,3,···}R={N},N={ai-1,ai|i=2,3,4,···}。本实验是以数组的形式把有序表存放在计算机内存的一个连续的区域内，这样便有：LOC(ai+1)=LOC(ai)+m。其中m是存放每个元素所占的内存字数。LOC(ai)=LO+m·(i-1)。其中LO是ai的地址，即首地址。 主要仪器及耗材 计算机，Turbo C 2.0 软件。 实验内容与步骤 程序1：线性表基本操作的实现　　这个程序中演示了顺序表的创建、插入、删除和查找，请修改并完成。  程序如下： #include stdio.h #include stdlib.h /*顺序表的定义：*/ #define ListSize 100 typedef struct { int data[ListSize]; /*向量data用于存放表结点*/ int length; /*当前的表长度*/ }SeqList; void main() { void CreateList(SeqList *L,int n); void PrintList(SeqList *L,int n); int LocateList(SeqList *L,int x); void InsertList(SeqList *L,int x,int i); void DeleteList(SeqList *L,int i); SeqList L; int i,x; int n=10; /*THE LENGTH OF LIST*/ L.length=0; clrscr(); CreateList(L,n); /*CREAT THE LIST*/ PrintList(L,n); /*PRINT THE LIST*/ printf(INPUT THE RESEARCH ELEMENT); scanf(%d,x); i=LocateList(L,x); printf(the research posit