数据结构与算法实验报告软件学院软件工程专业10080218祁伟双北京工业大学软件学院实验报告课程名称__数据结构与算法_______实验名称___数据结构与算法课设___班级_软工2班___姓名_祁伟双____学号___10080218__实验日期_2011.12_实验报告要求：1.实验目的2.实验内容3.实验步骤4.运行结果5.流程图6.实验体会实验目的：掌握线性表的基本结构和操作方法，培养学生灵活使用表解决实际问题的能力。掌握栈与队列的基本结构和操作方法，并能利用其解决实际问题。掌握树形结构的特点，二叉树的存储方式以及相应操作。熟练掌握顺序搜索、折半搜索和索引搜索等基本搜索算法，熟悉这些算法适合在何种存储结构下实现；掌握图形结构的特点、存储方式以及相应基本运算的编程实现。实验内容：已知一条记录包含有学号和成绩两个数据项，要求按成绩由大到小建立两个有序表（可用顺序表或者链式表实现），然后再将两个有序表并合并成一个有序表（有能力的同学才做这个合并）。第一个表输入的数据如下（学号，成绩）：(1,70),(2,85),(3,75),(4,90)，第二个表输入的数据如下（学号，成绩）：(5,60),(6,80),(7,76),(8,50)。假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序任意，即([]())或[([][])]等都为正确的格式，而[(])为不正确的格式。利用栈编程序检验表达式中的括号是否合法。即检验左右括号是否配对出现任务1：按先序遍历序列建立二叉树的二叉链表，已知先序序列为：ABCFFDEFGFFFFFF。(F表示空格)。并写一个函数treenodes()统计该二叉树的节点个数。如果有可能，写一个输出函数treeprint()用树形结构打印出该二叉树。任务2：编写出按照层次遍历的思想对树的左孩子右兄弟表示方法的存储结构进行逐层遍历的算法，并给出测试程序及运行结果。任务3：编写出在利用四个数组表示一个二叉树的存储结构的情况下，根据给定序号找出所有祖先节点的算法，设计出先序、中序及后序遍历的递归算法并根据给定的数据给出测试结果。[说明]以上任务中选做2个，计算机各专业及电控学院学生必须选择任务2作为任务之一。其他理工科各专业学生任意选择2个，文科学生选任务1或任务3之一。(1)用邻接矩阵或者邻接表存储结构形式表示一个图，图中每个顶点代表一个字符（自定义），打印出深度优先搜索和广度优先搜索的节点序列。（2）如果可能，则实现最小生成树、拓扑排序、关键路径或者最短路径的算法。实验步骤:1、确定存储格式2、确定类及类里的函数3、编写类函数4、编写主函数5、调试函数实验一代码：#include<iostream.h>#include<string.h>#include<ctype.h>#include<malloc.h>/*malloc()等*/#include<limits.h>/*INT_MAX等*/#include<stdio.h>/*EOF(=^Z或F6),NULL*/#include<stdlib.h>/*atoi()*/#include<io.h>/*eof()*/#include<math.h>/*floor(),ceil(),abs()*/#include<process.h>/*exit()*//*函数结果状态代码*/#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1/*#defineOVERFLOW-2因为在math.h中已定义OVERFLOW的值为3,故去掉此行*/typedefintStatus;/*Status是函数的类型,其值是函数结果状态代码，如OK等*/typedefintBoolean;/*Boolean是布尔类型,其值是TRUE或FALSE*/typedefintElemType;/*实现一组整数的操作,将int型特定义为通用的ElemType类型名*////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////#defineLIST_INIT_SIZE10/*线性表存储空间的初始分配量*/#defineLISTINCREMENT2/*线性表存储空间的分配增量*/typedefstruct{ElemTyp