实验要求

第一章实验概述一、实验目的总论《数据结构》是一门理论性、实践性很强的专业基础课程，为学好这门课，学生必须完成一定数量的上机实验。通过本课程的上机，要求在数据结构的选择和应用、算法的设计及实现等方面加深对课程基础内容的理解，同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。二、实验总体要求⒈问题分析充分地分析和理解问题本身，弄清要求做什么，包括功能要求、性能要求、设计要求和约束以及基本数据特性，数据间的联系等。⒉数据结构设计针对要求解决的问题，考虑各种可能的数据结构，并且力求从中出最佳方案(必须连同算法一起考虑)，确定主要的数据结构及全程变量。对引入的每种数据结构和全程变量要详细说明其功能、初值和操作特点。⒊算法设计算法设计分概要设计和详细设计，概要设计着重解决程序的模块设计问题，这包括考虑如何把被开发的问题程序自顶向下分解成若干顺序模块，并决定模块的接口，即模块间的相互关系以及模块之间的信息交换问题.详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出，4上机调试对程序进行编译，纠正程序中可能出现的语法错误，测试前，先运行一遍程序看看究竟将会发生什么，如果错误较多，则根据事先设计的测试方案并结合现场情况进行错误跟踪，包括打印执行路径或输出中间变量值等手段。三、实验报告的书写格式：一、设计题目。二、运行环境（软、硬件环境）简介。三、问题描述，包括目标、任务、条件和约束的描述。四、算法设计的思想五、算法的流程图六、算法设计分析七、源代码八、运行结果分析九、收获及体会将以上各项文字材料及程序清单等装订成册，形成一个完整的报告。第二章实验环境数据结构实验目前仍然以标准C语言作为算法实现的主流计算机语言。本课程使用美国微软公司的VisualC++6.0或.NET2005作为开发工具进行实验。为保证实验的顺利完成请学生参考下面的步骤完成C语言程序的编辑、编译、连接和运行。一、VisualC++6.0使用简介1、进入VisualC++6.0环境，如图1所示。图1VisualC++6.0程序的运行2、建立新的工程，如图2所示。图2建立新工程3、在左侧中如图3所示选择Win32ConsoleApplication,在Projectname中输入工程的名称。Location为工程保存的路径，可以改变，也可以保持默认。图3建立新的工程4、选择第三项，如图4所示。图4建立工程5、选择按钮OK选择Win32ConsoleApplication工程保存的路径，可以改变，也可以保持默认输入工程的名称图5信息总结6、选择如图6箭头所指向的按钮或如图7所示的菜单运行程序。图6运行程序图7程序的运行7、展开程序修改程序为自己的代码。图8代码的编写二、.NET2005使用简介1、进入.NET2005环境，如图1所示。图1.NET2005程序的运行2、建立新的工程，如图2所示。图2建立新工程4、在左侧中如图3所示选择Win32,在选择Win32ConsoleApplication,在名称中输入工程的名称，如test。图3建立新的工程4、可以直接选择“完成”，如图4所示。图4建立工程选择Win32输入工程的名称选择Win32ConsoleApplication5、进入编程环境图5运行程序图6程序的运行6、展开程序修改程序为自己的代码。图7代码的编写注意：使用F9设置跟踪点，利用F5进行程序的跟踪调试。数据结构参考：头文件DATASTRU.H定义了参考程序中使用的数据结构，具体的代码和加入方法如下。#defineDATATYPE1int#defineDATATYPE2char#defineKEYTYPEint#defineMAXSIZE100#defineMAXLEN40#defineVEXTYPEint#defineADJTYPEinttypedefstruct{DATATYPE1datas[MAXSIZE];intlast;}SEQUENLIST;typedefstructnode{DATATYPE2data;structnode*next;}LINKLIST;typedefstructdnode{DATATYPE2data;structdnode*prior,*next;}DLINKLIST;typedefstruct{DATATYPE1data[MAXSIZE];inttop;}SEQSTACK;typedefstructsnode{DATATYPE2data;structsnode*next;}LINKSTACK;typedefstruct{DATATYPE1data[MAXSIZE];intfront,rear;}SEQQUEUE;typedefstructqnode{DATATYPE1data;structqnode*next;}LINKQLIST;typedefstruct{LINKQLIST*front,*rear;}LINKQUEUE;typedefstruct{charch[MAXSIZE];intlen;}SEQSTRING;typedefstruct{char*ch;intlen;}HSTRING;typedefstruct{inti,j;DATATYPE1v;}NODE;typedefstruct{intm,n,t;NODEdata[MAXLEN];}SPMATRIX;typedefstruct{DATATYPE2bt[MAXSIZE];intbtnum;}BTSEQ;typedefstructnode1{DATATYPE2data;structnode1*lchild,*rchild;}BTCHINALR;typedefstructnode2{DATATYPE2data;structnode2*lchild,*rchild,*parent;}BTCHINALRP;typedefstruct{DATATYPE2data;intparent;}PTNODE;typedefstruct{PTNODEnodes[MAXSIZE];intnodenum;}PTTREE;typedefstructcnode{intchild;structcnode*next;}CHILDLINK;typedefstruct{DATATYPE2data;CHILDLINK*headptr;}CTNODE;typedefstruct{CTNODEnodes[MAXSIZE];intnodenum,rootset;}CTTREE;typedefstructcsnode{DATATYPE2data;structcsnode*firstchild,*nextsibling;}CSNODE;typedefstruct{VEXTYPEvexs[MAXLEN];ADJTYPEarcs[MAXLEN][MAXLEN];intvexnum,arcnum;intkind;}MGRAPH;typedefstructnode3{intadjvex;structnode3*next;}EDGENODE;typedefstruct{VEXTYPEvertex;EDGENODE*link;intid;}VEXNODE;typedefstruct{VEXNODEadjlist[MAXLEN];intvexnum,arcnum;intkind;}ADJGRAPH;typedefstruct{KEYTYPEkey;}SSELEMENT;typedefstruct{SSELEMENTr[MAXSIZE];intlen;}SSTABLE;typedefstructnode4{KEYTYPEkey;structnode4*lchild,*rchild;}BSTNODE;typedefstructnode5{KEYTYPEkey;structnode5*next;}CHAINHASH;typedefstruct{KEYTYPEkey;}HASHTABLE;typedefstruct{KEYTYPEkey;}RECNODE;第三章实验内容实验一线性表的基本操作一、实验目的1）掌握顺序表、链表的概念，学会对顺序表、链表进行操作。2）实现顺序表、链表的存储结构，逐步培养解决实际问题的能力二、实验内容顺序表、链表结构的生成,插入,删除,定位,查找三、实验步骤1、定义节点2、生成一个单链表（正序建立单链表或逆序建立单链表）3、单链表中插入一个元素4、在单链表中删除一个元素5、按序号查找一个元素6、按值（关键字）查找一个元素7、显示单链表所有元素实验二二叉树建立及遍历一、实验目的：1）掌握二叉树的概念和基本操作。2）掌握二叉树的创建和遍历。3）通过本实验可以使学生掌握二叉树的相关算法和概念。4）培养解决实际问题、编写程序的能力。二、实验内容生成二叉树（必作）递归先序遍历该二叉树（遍历算法三选一）递归中序遍历该二叉树（遍历算法三选一）非递归先序遍历该二叉树（遍历算法三选一）三、实验步骤1、输入（先序）数据，以二叉链表作为存储结构，建立二叉树。2、采用递归算法对其进行遍历（先序、中序或后序），将遍历结果打印输出。3、测试数据，如：ABCффDEфGффFффф（其中ф表示空格字符）则输出结果为先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA实验三图的建立和基本操作一、实验目的：熟悉图的常用存储结构和基本操作。二、实验内容以数组（邻接矩阵）或邻接表为存储结构，建立一个图。输出图的深度优先序列或广度优先序列。三、实验步骤1、定义图的数组或邻接表存储表示。2、构造一个图G（如p168图7.13所示）。3、输出图G的深度优先序列或广度优先序列。实验四二叉排序树查找一、实验目的：1、掌握查找的含义。2、掌握基本查找操作的实现。3、掌握二叉排序树的查找、建立、结点插入和删除算法。二、实验内容写出二叉排序树的查找、插入、建立、删除和打印算法。[参考算法]：1、二叉排序树的查找算法。①若查找树为空，查找失败。②查找树非空，将给定值key与查找树的根结点关键码比较。③若相等，查找成功，结束查找过程，否则，a．当给key小于根结点关键码，查找将在以左子女为根的子树上继续进行，转①b．当给key大于根结点关键码，查找将在以右子女为根的子树上继续进行，转①2、二叉排序树的插入算法。设待插入结点的关键码为key，为将其插入，先要在二叉排序树中进行查找，若查找成功，按二叉排序树定义，待插入结点已存在，不用插入；查找不成功时，则插入之。因此，新插入结点一定是作为叶子结点添加上去的。构造一棵二叉排序树则是逐个插入结点的过程。3、二叉排序树删除操作。在二叉排序树中删除一个结点就相当于删除一个有序序列中的某一条记录，当某个记录被删除后仍然要保持序列的有序性。因此当把二叉排序树中某一个结点删除后，不能把以该结点为根的整棵子树都删除，应当保证整棵二叉排序树结构的完整性，保持二叉排序树原有的特点。假设用P指向二叉排序树上被删除的结点，指针f指向p所指向的结点的双亲结点，删除的关键是如何找一个S结点来替换P结点（即P所指向的结点）的，要分成如下三种情况分别进行处理：1）要删除的结点P为叶子结点。2）要删除的结点P只有左子树或右子树。3）要删除的结点P既有左子树又有右子树。。4、二叉排序树的打印算法。二叉排序树的打印可以利用二叉树的特点，对整个二叉排序树进行中序遍历，所得到的结果为一个按关键字大小进行非递减排列的序列。三、实验步骤1、定义二叉排序树的查找算法函数。2、二叉排序树的插入算法函数。3、建立二叉排序树的插入算法。4、二叉排序树删除一个结点的操作实现。5、打印二叉排序树。