中南大学数据结构试验报告

《数据结构》实验报告课程名称数据结构学生姓名指导教师学院信息科学与工程学院专业班级通信工程实验一线性表基本操作和简单程序1．实验目的掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。2．实验要求（1）认真阅读和掌握和本实验相关的教材内容。（2）认真阅读和掌握本章相关内容的程序。（3）上机运行程序。3.实验代码：1）头文件模块#includeiostream.h//头文件#includemalloc.h//库头文件-----动态分配内存空间typedefintelemtype;//定义数据域的类型typedefstructlinknode//定义结点类型{elemtypedata;//定义数据域structlinknode*next;//定义结点指针}nodetype;2）创建单链表nodetype*create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束{elemtyped;//定义数据元素dnodetype*h=NULL,*s,*t;//定义结点指针inti=1;cout建立一个单链表endl;while(1){cout输入第i结点data域值：;cind;if(d==0)break;//以0表示输入结束if(i==1)//建立第一个结点{h=(nodetype*)malloc(sizeof(nodetype));//表示指针hh-data=d;h-next=NULL;t=h;//h是头指针}else//建立其余结点{s=(nodetype*)malloc(sizeof(nodetype));s-data=d;s-next=NULL;t-next=s;t=s;//t始终指向生成的单链表的最后一个节点}i++;}returnh;}3）输出单链表中的元素voiddisp(nodetype*h)//输出由h指向的单链表的所有data域之值{nodetype*p=h;cout输出一个单链表:endl;if(p==NULL)cout空表;while(p!=NULL){coutp-data;p=p-next;}coutendl;}4）计算单链表的长度intlen(nodetype*h)//返回单链表的长度{inti=0;nodetype*p=h;while(p!=NULL){p=p-next;i++;}returni;}5）寻找第i个节点nodetype*find(nodetype*h,inti)//返回第i个节点的指针{nodetype*p=h;intj=1;if(ilen(h)||i=0)returnNULL;//i上溢或下溢celse{while(p!=NULL&&j1)//查找第i个节点，并由p指向该节点{j++;p=p-next;}returnp;}}6）单链表的插入操作nodetype*ins(nodetype*h,inti,elemtypex)//在单链表head中第i个节点//（i=0）之后插入一个data域为x的节点{nodetype*p,*s;s=(nodetype*)malloc(sizeof(nodetype));//创建节点ss-data=x;s-next=NULL;if(i==0)//i=0:s作为该单链表的第一个节点{s-next=h;h=s;}else{p=find(h,i);//查找第i个节点，并由p指向该节点if(p!=NULL){s-next=p-next;p-next=s;}returnh;}}7）单链表的删除操作nodetype*del(nodetype*h,inti)//删除第i个节点{nodetype*p=h,*s;intj=1;if(i==1)//删除第1个节点{h=h-next;free(p);}else{p=find(h,i-1);//查找第i-1个节点，并由p指向该节点if(p!=NULL&&p-next!=NULL){s=p-next;//s指向要删除的节点p-next=s-next;free(s);}elsecout输入i的值不正确endl;}returnh;}8）释放节点空间voiddispose(nodetype*h)//释放单链表的所有节点占用的空间{nodetype*pa=h,*pb;if(pa!=NULL){pb=pa-next;if(pb==NULL)//只有一个节点的情况free(pa);else{while(pb!=NULL)//有两个及以上节点的情况{free(pa);pa=pb;pb=pb-next;}free(pa);}}}4.实验心得体会线性表是最简单的、最常用的一种数据结构，是实现其他数据结构的基础。我们需要做到熟练掌握线性表的基本操作，为以后学习的内容做铺垫。实验二二叉树的基本操作1.实验目的（1）进一步掌握指针变量的用途和程序设计方法。（2）掌握二叉树的结构特征，以及链式存储结构的特点及程序设计方法。（3）掌握构造二叉树的基本方法。（4）掌握二叉树遍历算法的设计方法。3．实验要求（1）认真阅读和掌握和本实验相关的教材内容。（2）掌握一个实际二叉树的创建方法。（3）掌握二叉链存储结构下二叉树操作的设计方法和遍历操作设计方法。4．实验内容（1）定义二叉链存储结构。（2）设计二叉树的基本操作（初始化一棵带头结点的二叉树、左结点插入、右结点插入、中序遍历二叉树等）。（3）按照建立一棵实际二叉树的操作需要，编写建立二叉树、遍历二叉树的函数。（4）编写测试主函数并上机运行。打印出运行结果，并结合程序运行结果进行分析。实验代码：//二叉树的基本操作#includestdio.h#definemax30#defineNULL0typedefstructBNode{chardata;/*数据域*/structBNode*lchild,*rchild;/*指向左右子女*/}BinTree;voidpreorder(BinTree*t);/*声明先根遍历函数*/voidinorder(BinTree*t);/*声明中根遍历函数*/voidpostorder(BinTree*t);/*声明后根遍历函数*/intleafs(BinTree*b);/*声明求叶子数函数*/inttreedeep(BinTree*p);/*声明求树的深度函数*/BinTree*swap(BinTree*p);/*声明交换二叉树的所有结点的左右子树的函数*//*将字符串中的第i个字符开始的m个字符作为数据生成对应的二叉树*/BinTree*cre_tree(char*str,inti,intm){BinTree*p;if(i=m)/*无效结点*/returnNULL;p=(BinTree*)malloc(sizeof(BinTree));/*生成新结点*/p-data=str[i];p-lchild=cre_tree(str,2*i+1,m);/*创建新结点的左子树*/p-rchild=cre_tree(str,2*i+2,m);/*创建新结点的右子树*/returnp;}voidmain(){inti,n;charstr[max];BinTree*root;/*根结点*/printf(请输入二叉树的结点数:);scanf(%d,&n);getchar();/*输入数字*/printf(请输入长度为%d的字符串:,n);for(i=0;in;i++)scanf(%c,&str[i]);printf(\n);root=cre_tree(str,0,n);printf(二叉树已成功创建!结点序列为：);for(i=0;in;i++)printf(%c,str[i]);printf(\n);/*先根遍历*/printf(\n先根遍历结果:);preorder(root);printf(\n);/*中根遍历*/printf(\n中根遍历结果:);inorder(root);printf(\n);/*后根遍历*/printf(\n后根遍历结果:);postorder(root);printf(\n);printf(\n叶子数为：%d\n,leafs(root));printf(\n树的深度为：%d\n,treedeep(root));printf(\n交换左右子树后先序遍历序列为：);preorder(swap(root));printf(\n\n);}voidpreorder(BinTree*t){if(t!=NULL){printf(%c,t-data);if(t-lchild){printf(-);preorder(t-lchild);}if(t-rchild){printf(-);preorder(t-rchild);}}}voidinorder(BinTree*t){if(t!=NULL){inorder(t-lchild);printf(%c,t-data);inorder(t-rchild);}}voidpostorder(BinTree*t){if(t!=NULL){postorder(t-lchild);postorder(t-rchild);printf(%c,t-data);}}intleafs(BinTree*b)/*求叶子数*/{intnum1,num2;if(b==NULL)return(0);elseif(b-lchild==NULL&&b-rchild==NULL)return(1);else{num1=leafs(b-lchild);num2=leafs(b-rchild);return(num1+num2);}}inttreedeep(BinTree*p)/*求树的深度*/{intldeep,rdeep,deep;if(p==NULL)deep=0;else{ldeep=treedeep(p-lchild);rdeep=treedeep(p-rchild);deep=(ldeeprdeep?ldeep:rdeep)+1;}returndeep;}BinTree*swap(BinTree*p)/*交换二叉树的所有结点的左右子树*/{BinTree*stack[max];intk=0;stack[k]=NULL;if(p!=NULL){stack[++k]=p-lchild;p-lchild=p-rchild;p-rchild=stack[k];p-lchild=swap(p-lchild);p-rchild=swap(p-rchild);}returnp;}6.实验心得：通过本次实验，将课本上的只是用于实际操作。进一步掌握指针变量的用途和程序设计方法。二叉树的结构特征，以及链式存储结构的特点及程序设计方法。构造二叉树的基本方法。二叉树遍历算法的设计方法。掌握了二叉树的基本操作。实验三图的相关操作1.实验要求1.1熟悉图的各种存储方法。1.2掌握遍历图的递归和非递归的算法。1.3理解图的有关算法。2.实验内容#includestdio.h#definemaxsize1024/*假定线性表的最大长度为1024*/#definen100/*图的顶点最大个数*/typedefintdatatype;/*假定线性表元素的类型为整型*/typedefcharVEXTYPE;/*顶点的数据类型*/typedeffloatADJTYPE;/*权值类型*/typedefstruct{VEXTYPEvexs[n];/*顶点信息数组*/ADJTYPEarcs[n][n];/*边权数组*/intnum;/*顶点的实际个数*/}GRAPH;/*1.置空图*/voidGraphInit(GRAPH*L){L-num=0;}/*2.求结点数*/intGraphVexs(GRAPH*L){return(L-num);}/*