本科实验报告课程名称：数据结构B实验项目：线性结构、树形结构、图结构、查找、排序实验地点：逸夫楼202专业班级：软件1108学号：2011005063学生姓名：刘浩指导教师：张欣萍2012年1月7日实验项目：实验一线性表一、实验目的和要求1、实验目的：本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。2、实验要求：要求仔细阅读并理解下列例题，上机通过，并观察其结果，然后独立完成后面的实习题。二、实验内容和原理[问题描述]：设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表仍然有序。[输入]:顺序表的长度，初始化顺序表的数据，插入的数据X。[输出]：已建立顺序表，插入X后顺序表。[存储结构]：顺序存储结构。实验原理：[算法的基本思想]：建立一个顺序表。调用插入X的函数ListInsert_sq（），比X大的数往后移，从而实现新的顺序表有序。三、主要仪器设备计算机Win-TC四、操作方法与实验步骤#include<stdio.h>#include<stdlib.h>voidInsert(int*p,intlength,intn){inti,j;intflag=0;if(n>=p[length-1]){p[length]=n;flag=1;}else{for(i=length-2;i>=0;i--){if(n>=p[i]){for(j=length;j>=i+2;j--){p[j]=p[j-1];}p[i+1]=n;flag=1;break;}}}if(flag==0){for(j=length;j>=1;j--){p[j]=p[j-1];}p[0]=n;}}intmain(){intL[10]={1,3,5,7,10,17,21};intlength=7;inti,x;printf("InputaLinktable<astring>:\n");for(i=0;i<length;i++){printf("%4d",L[i]);}printf("\nPleaseinputafigureyouwanttoinsert:\n");scanf("%d",&x);Insert(L,length,x);printf("Afterinsert'sLinkis:\n",x);for(i=0;i<=length;i++){printf("%4d",L[i]);}printf("\n");getch();}五、实验数据记录和处理六、实验结果与分析优点：可以将任意整数插入到已知表中，简介，明了。缺点：插入或删除元素时不方便，需要移动大量的元素，这个程序只能在固定的整数顺序表中插入整数，不方便。时间复杂度为：O（n）。七、讨论、心得通过这次实验，使我加深了对线性顺序表的存储结构，顺序表的插入，删除等操作的理解和应用，对课本上的内容更加理解透彻，认识到知识运用到实践中是多么的神奇。虽然实验中遇到一些困难，但在老师的帮助和我们的讨论中已经解决，同时对我的操作能力有了很大的提升。实验项目：实验二树一、实验目的和要求1、实验目的：熟悉树的各种表示方法和各种遍历方式，掌握有关算法的实现，了解树在计算机科学及其它工程技术中的应用。2、实验要求：要求仔细阅读并理解下列例题，上机通过，并观察其结果，然后独立完成后面的实习题.实验内容和原理[问题描述]：编写递归算法，计算二叉树中叶子结点的数目。[输入]：输入叶子结点的计数m。一棵二叉树的结点若无子树，则可将其子树看作“.”，输入时，按照前序序列的顺序输入该结点的内容。对下图，其输入序列为ABD..EH...CF.I..G..。[输出]:若为空二叉树，则输出：Thisisaemptybinarytree.m=0。若二叉树不空,则输出叶子结点的个数m(m>0).[存储结构]:采用二叉链表存储。实验原理：[算法的基本思想]在原实验的基础上进行修改即可实现该题的要求：计数叶子结点的个数。在例题的基础上在输入一个计数器m,赋予初值m=0，当一个结点的左子树和右子树都为空时，则此结点为叶子结点，m相应的加1.依次遍历二叉树的各个结点即可。三、主要仪器设备计算机Win-TC四、操作方法与实验步骤#include<stdio.h>#include<alloc.h>structnode{charinfo;structnode*llink,*rlink;};typedefs