数据结构实验指导书

数据结构实验指导书江西农业大学计算机与信息学院学院软件教研室实验一动态分配的实现一．实验目的1.熟悉C语言上机环境，进一步掌握C语言的结构特点。2.掌握动态分配内存空间的概念及操作。3.掌握形参和实参值传递和地址传递的原理。二．实验内容1.Page4例题0-2。2.Page7例题0-3。3.Page9例题0-4。实验二顺序表及其应用一．实验目的1.掌握线性表的顺序存储结构的定义及C语言实现。2.掌握线性表在顺序存储结构即顺序表中的各种基本操作。二．实验内容1.Page33例题2-1顺序表的测试程序.2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第3就个位置插入元素68，最后依次显示当前线性表中的数据元素。实现提示1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。在此，我们利用C语言的结构体类型定义顺序表：#defineMAXSIZE100typedefintdatatype;/*线性表中存放整型元素*/typedefstruct{datatypelist[MAXSIZE];intsize;/*顺序表的长度*/}seqlist;将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。2.注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。实验三单链表及其应用一。实验目的1.掌握线性表的链式存储结构——单链表的定义及C语言实现。2.掌握线性表在链式存储结构——单链表中的各种基本操作。二．实验内容1.Page45例题2-3单链表的测试程序.2.利用前面的实验建立一个有序的单链表L={5，12，14，18，23，34}，然后将元素15插入到单链表中要求单链表还是有序的单链表，最后依次显示当前单链表中的数据元素。实现提示单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下：typedefintdatatype;typedefstructnode{datatypedata;//数据域structnode*next;//指针域}slnode;注意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到C语言的标准函数malloc()，如给指针变量p分配一个结点的地址：p=(slnode*)malloc(sizeof(slnode));该语句的功能是申请分配一个类型为slnode的结点的地址空间，并将首地址存入指针变量p中。当结点不需要时可以用标准函数free(p)释放结点存储空间，这时p为空值（NULL）。实验四栈一．实验目的1.掌握栈的顺序表示和实现。2．了解栈的先进后出的性质。二．实验内容1．Page62顺序堆栈的测试程序。2．Page66利用前面实验的顺序堆栈的打包文件，实现括号匹配算法。实验五队列一．实验目的1.实现队列的链式表示和实现。2．了解队列先进后出的性质。二．实验内容1．Page80例题3-3实现判断一个字符序列是否是回文。实验六串的应用一．实验目的1．掌握串的操作特点。2．认识串和线形表操作上的不同。二．实验内容1．Page104静态数组下串的模式匹配算法的实现。实验七数组一．实验目的1．掌握稀疏矩阵的压缩存储。2．掌握稀疏矩阵的转置算法。二．实验内容1．Page125例题5-3用三元组顺序表存储稀疏矩阵，并实现矩阵的转置。实验八树和二叉树一．实验目的1.通过实验，掌握二叉树的建立与存储。2.通过实验，掌握二叉树的遍历方法。二．实验内容1.建立自己的头文件BT.H，内容包括二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法。2.建立二叉树,并通过调用函数,输出先序遍历、中序遍历与后序遍历的结果。思考与提高1.如何用孩子兄弟表示法存储树？2.熟悉并掌握赫夫曼树。实验九图的实现一．实验目的1.掌握图的基本存储方法；2.掌握有关图的操作算法并用高级语言实现；3.熟练掌握图的两种搜索路径的遍历方法。二．实验内容1．Page8-2,在图的邻接矩阵下实现图的广度和深度优先遍历。实验十查找一．实验目的1.掌握查找的不同方法，并能用高级语言实现查找算法；2.熟练掌握二叉排序树的构造和查找方法。3.了解静态查找表及哈希表查找方法。二．实验内容1.从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中。2.在二叉排序树中查找某一结点。3.用其它查找算法进行排序（课后自己做）。思考与提高1.用其它的查找方法完成该算法。2.比较各种算法的时间及空间复杂度。