数据结构实训报告

山东科技大学泰山科技学院课程实训说明书课程：数据结构（C语言版）题目：单链表、二叉树院系：信息工程系 专业班级：计算机科学与技术 学号：201443****** 学生姓名：*** 指导教师：2015年12月18日成绩评语：指导教师第页一、设计目的课程设计题一：链表操作1、设计目的（1）掌握线性表的在顺序结构和链式结构实现。（2）掌握线性表在顺序结构和链式结构上的基本操作。2、设计内容和要求（1）利用链表的插入运算建立线性链表，然后实现链表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、计数、输出、排序、逆置要单独写成函数），并能在屏幕上输出操作前后的结果。课程设计题二：二叉树的基本操作1、设计目的（1）掌握二叉树的概念和性质（2）掌握任意二叉树存储结构。（3）掌握任意二叉树的基本操作。2、设计内容和要求（1）对任意给定的二叉树（顶点数自定）建立它的二叉链表存储结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。（2）求二叉树高度、结点数、度为1的结点数和叶子结点数。运行环境（软、硬件环境）软件环境MicrosoftVisualC++6.0硬件环境计算机一台处理器：Intel(R)Core(TM)i3-4010UCPU@1.70GHz1.70GHz数据结构及算法设计的思想课程设计题一：链表操作定义一个创建链表的函数，通过该函数可以创建一个链表，并为下面的函数应用做好准备。（因为每个新生成的结点的插入位置在表尾，则算法中必须维持一个始终指向已建立的链表表尾的指针。）（2）定义一个遍历查找（按序号差值）的算法，通过此算法可以查找到链表中的每一个结点是否存在。（单链表是一种顺序存取的结构，为找第i个数据元素，必须先找到第i-1个数据元素。因此，查找第i个数据元素的基本操作为：移动指针，比较j和i。令指针p始终指向线性表中第j个数据元素。设单链表的长度为n，要查找表中第i个结点，仅当1≤i≤n时，i的值是合法的。）（3）定义插入结点的算法，通过定义这个算法，并结合这查找前驱和后继的算法便可以在连链表的任意位置进行插入一个新结点。（在链表中插入结点只需要修改指针。但同时，若要在第i个结点之前插入元素，修改的是第i-1个结点的指针。因此，在单链表中第i个结点之前进行插入的基本操作为:找到线性表中第i-1个结点，然后修改其指向后继的指针。）（4）定义删除结点的操作，这个算法用于对链表中某个指定位置的结点的删除工作。（在单链表中删除第i个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。）（5）定义一个计数的算法，通过此算法可以统计链表中结点的个数。（6）定义输出链表的算法，通过对第一步已经定义好的创建链表函数的调用，在这一步通过调用输出链表的函数算法来实现对链表的输出操作。（7）定义一个排序（冒泡排序）的算法，通过此算法对表中元素按照一定顺序进行排列。（8）定义一个逆置单链表的操作，通过定义此算法，可以逆置输出单链表。（将原链表中的头结点和第一个元素结点断开（令其指针域为空），先构成一个新的空表，然后将原链表中各结点，从第一个结点起，依次插入这个新表的头部（即令每个插入的结点成为新的第一个元素结点））课程设计题二：二叉树的基本操作IchildDataRchild定义二叉树链表：二叉树的链式存储方式下每个结点包含3个域，分别记录该结点的属性值及左右子树的位置。其左右子树的位置是通过指针方式体现，其中Ichild是指向该结点左子树的指针，rchild为指向该结点右子数的指针。结点结构：二叉树的创建：根据先序遍历结果建立二叉树，将第一个输入的结点作为二叉树的根结点，后继输入的结点序列是二叉树左右子树先序遍历的结果，由它们生成二叉树的左子数；再接下来输入的结点序列为二叉树右子树先序遍历的结果，应该由它们生成二叉树的右子树。而由二叉树左子树先序遍历的结果生成二叉树的左子树和由二叉树右子树先序遍历的结果生成二叉树的右子树的过程均与由整棵二叉树的先序遍历结果生成该二叉树的过程完全相同，只是所处理的对象范围不同，所以可以用递归方式实现之。使用CreatBitree建立一颗二叉树时，必须按其先序遍历的顺序输入结点的值，遍历过程中遇到空子树时，必须使用“#”代替。例如：ABC##DE#G##F###（3）二叉树的先序遍历：首先访问根结点；然后按照先序遍历的方式访问根结点的左子树；再按照先序遍历的方式访问根结点的右子数。（4）二叉树的中序遍历：首先按照中序遍历的方式访问根结点的左子树；然后访问根结点；最后按照中序遍历的方式访问根结点的右子树。（5）二叉树的后序遍历：首先按照后序遍历的方式访问根结点的左子树；然后按照后序遍历的方式访问根结点的右子树；最后访问根结点。（6）求二叉树的高度：二叉树T，如果T为空，则高度为0；否则，其高度为其左子树的高度和右子树的高度的最大值再加1。（7）求二叉树的结点数：二叉树T，若T为空，则T中所含结点的个数为0；否则，T中所含结点个数等于左子树中所含结点个数加上右子树中所含结点的个数再加1。（8）求二叉树度为1的结点数：二叉树T，若T为空，则T中度为1的结点数为0；否则，T所含度为1的结点数等于左子树不为空右子树为空和左子树为空右子树不为空的结点个数之和。（9）求二叉树的叶子结点数：求二叉树中叶子结点的个数，即求二叉树的所有结点中左、右子数均为空的结点个数之和。数据结构及算法设计课程设计题一：链表操作typedefstructLNode//线性表的单链表存储结构voidCreatList_L(LinkList&L,intn);//头插法建表（逆序建表）voidGetElem_L(LinkList&L);//按序号查值StatusListInsert_L(LinkList&L,inti,ElemTypee);//插入StatusListDelete_L(LinkList&L,inti,ElemType&e);//删除voidListLength(LinkList&L);//计数voidPrintList(LinkList&L);//输出voidListSort(LinkList&L);//冒泡排序voidOpposeList(LinkList&L);//逆置课程设计题二：二叉树的基本操作typedefstructBiTNode//二叉树的二叉链表存储结构StatusCreateBiTree(BiTree&T)//建立二叉树的存储结构——二叉链表（先序）。StatusPreOrderTraverse(BiTree&T,Status(*Visit)(ElemTypee))//先序遍历二叉树基本操作的递归算法在二叉链表上的实现StatusInOrderTraverse(BiTree&T,Status(*Visit)(ElemTypee))//中序遍历二叉树基本操作的递归算法在二叉链表上的实现StatusPostOrderTraverse(BiTree&T,Status(*Visit)(ElemTypee))//后序遍历二叉树基本操作的递归算法在二叉链表上的实现StatusVisit(ElemTypee)//对二叉树中的数据元素访问intBiTreeDepth(BiTree&T)//求二叉树的高度intCountNode(BiTree&T)//二叉树的结点数intNodeOne(BiTree&T)//二叉树中度为1的结点数intCountLeaf(BiTree&T)//统计二叉树叶子结点源代码课程设计题一：链表操作#include<stdio.h>#include<stdlib.h>#defineOK1#defineERROR0typedefintStatus;typedefintElemType;typedefstructLNode{ ElemTypedata; structLNode*next;}LNode,*LinkList;inti,j,k; LinkListL,p,q,s,r,head; voidCreatList_L(LinkList&L,intn);//头插法建表（逆序建表） voidGetElem_L(LinkList&L);//按序号查值 StatusListInsert_L(LinkList&L,inti,ElemTypee);//插入 StatusListDelete_L(LinkList&L,inti,ElemType&e);//删除 voidListLength(LinkList&L);//计数 voidPrintList(LinkList&L);//输出 voidListSort(LinkList&L);//冒泡排序 voidOpposeList(LinkList&L);//逆置voidCreatList_L(LinkList&L,intn){//逆位序输入n个元素的值，建立带表头结点的单链线性表L。 L=(LinkList)malloc(sizeof(LNode)); L->next=NULL;//先建立一个带头结点的单链表 for(i=n;i>0;--i){ p=(LinkList)malloc(sizeof(LNode));//生成新结点 scanf("%d",&p->data);//输入元素值 p->next=L->next;//插到表头 L->next=p; }}//头插法建表（逆序建表）voidGetElem_L(LinkList&L){//L为带头接点的单链表的头指针。当第i个元素存在时，其赋值给e并返回ERROR inti,e; p=L->next; j=1;//初始化，p指向第一个结点，j为计时器 printf("请输入查找位置:\n");scanf("%d",&i); while(p&&j<i){//顺指针向后查找，直到p指向第i个元素或p为空 p=p->next; ++j; } if(!p||j>i) printf("第%d个元素不存在!",i);//第i个元素不存在 e=p->data;//取第i个元素 printf("查找结果为:%d\n",e); }//按序号查值StatusListInsert_L(LinkList&L,inti,ElemTypee){//在带头接点的单链线性表L中第i个位置之前插入元素e p=L; j=0; printf("请输入插入位置:\n");scanf("%d",&i); while(p&&j<i-1){ p=p->next; ++j; }//寻找第i-1个结点 if(!p||j>i-1) returnERROR;//i小于1或者大于表长加1 s=(LinkList)malloc(sizeof(LNode));//生成新结点 printf("请输入插入元素:\n");scanf("%d",&e); s->data=e;//插入L中 s->next=p->next; p->next=s; printf("插入后的链表为：\n"); PrintList(L); returnOK;}//插入StatusListDelete_L(LinkList&L,inti,ElemType&e){//在带头接点的单链线性表L中，删除第i个元素，并由e返回其值 p=L; j=0; printf("请输入删除元素位置:\n");scanf("%d",&i); while(p->next&&j<i-1){//寻找第i个结点，并命令p指向其前趋 p=p->next; ++j; } if(!(p->next)||j>i-1) returnERROR;//删除位置不合理 q=p->next; p->next=q->next;//删除并释放结点 e=q->data; free(q); printf("删除后的链表为：\n"); PrintList(L); returnOK;}//删除voidListLength(LinkList&L){ p=L; intj=0; //线性链表最后一个结点的指针为空 while((p->next)!=NULL) { j++; p=p->next; } printf("单链表总共有%d个元素\n",j);printf("\n");}//计数voidPrintList(LinkList&L){ p=L->next; if(p==NULL) printf("\n链表为空!"); else while(p) { printf("%d",p->data); p=p->next; } printf("\n");}//输出voidListSort(LinkList&L)//排序{ intt; intcount=0; p=L->next; while(p) { count++; p=p->next; } for(i=0;i<count-1;i++) { p=L->next; for(j=0;j<count-i-1;j++,p=p->next) { if(p->data>p->next->data) { t=p->data; p->data=p->next->data; p->next->data=t; } } } printf("排序后的链表为：\n"); p=L->next; while(p) { printf("%d",p->data); p=p->next; } printf("\n");}//冒泡排序(升序)voidOpposeList(LinkList&L){ p=L; p=p->next; L->next=NULL; while(p){ q=p; p=p->next; q->next=L->next; L->next=q; }printf("逆置后的链表为：\n");PrintList(L);}//逆置intmain(){inta,n,e;printf("************【请先建立单链表】************\n"); printf("请输入元素个数值:\n"); scanf("%d",&n); printf("请输入%d个元素:\n",n); CreatList_L(L,n);for(;;){ printf("请选择如下操作码\n");printf("\n");printf("*****【1】查找*****\n"); printf("*****【2】插入*****\n"); printf("*****【3】删除*****\n"); printf("*****【4】计数*****\n"); printf("*****【5】输出*****\n"); printf("*****【6】排序*****\n"); printf("*****【7】逆置*****\n");printf("******************************************\n");scanf("%d",&a);switch(a){ case1:GetElem_L(L);break; case2:ListInsert_L(L,i,e);break; case3:ListDelete_L(L,i,e);break; case4:ListLength(L);break; case5:PrintList(L);break; case6:ListSort(L);break; case7:OpposeList(L);break;default:printf("选择错误!\n"); } } return0;}课程设计题二：二叉树的基本操作#include<stdio.h>#include<stdlib.h>#defineOK1#defineERROR0#defineOVERFLOW0typedefcharElemType;typedefintStatus;typedefintTElemType;//二叉树的二叉链表存储结构typedefstructBiTNode{ TElemTypedata; structBiTNode*lchild,*rchild;}BiTNode,*BiTree;charch;//建立二叉树的存储结构——二叉链表（先序）。StatusCreateBiTree(BiTree&T){//按先序次序输入二叉树结点的值（一个字符），空格字符表示空树，构造二叉树链表表示的二叉树T。 scanf("%c",&ch); if(ch=='#') T=NULL; else{ if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW); T->data=ch;//生成根结点 CreateBiTree(T->lchild);//构造左子树 CreateBiTree(T->rchild);//构造右子树 } return0;}//先序遍历二叉树基本操作的递归算法在二叉链表上的实现StatusPreOrderTraverse(BiTree&T,Status(*Visit)(ElemTypee)){ if(T){if(!Visit(T->data))returnERROR;PreOrderTraverse(T->lchild,Visit);PreOrderTraverse(T->rchild,Visit);}returnOK;}//中序遍历二叉树基本操作的递归算法在二叉链表上的实现StatusInOrderTraverse(BiTree&T,Status(*Visit)(ElemTypee)){ if(T){InOrderTraverse(T->lchild,Visit);if(!Visit(T->data))returnERROR;InOrderTraverse(T->rchild,Visit);}returnOK;}//后序遍历二叉树基本操作的递归算法在二叉链表上的实现StatusPostOrderTraverse(BiTree&T,Status(*Visit)(ElemTypee)){ if(T){PostOrderTraverse(T->lchild,Visit);PostOrderTraverse(T->rchild,Visit);if(!Visit(T->data))returnERROR;;}returnOK;}StatusVisit(ElemTypee){//对二叉树中的数据元素访问if(e=='\0'){returnERROR;}else{printf("%c",e);}returnOK;}//求二叉树的高度intBiTreeDepth(BiTree&T){ intDepthall,Depthl,Depthr; if(T==NULL) Depthall=0; else{ Depthl=BiTreeDepth(T->lchild); Depthr=BiTreeDepth(T->rchild); Depthall=(Depthl>Depthr?Depthl:Depthr)+1; } returnDepthall;}//二叉树的结点数intCountNode(BiTree&T){ if(T==NULL) return0; else return(CountNode(T->lchild)+CountNode(T->rchild)+1);}//二叉树中度为1的结点数intNodeOne(BiTree&T){ if(T==NULL) return0; else{ if((T->lchild==NULL&&T->rchild!=NULL)||(T->lchild!=NULL&&T->rchild==NULL)) return1; else return(NodeOne(T->lchild)+NodeOne(T->rchild)); }}//统计二叉树叶子结点intCountLeaf(BiTree&T){ if(T==NULL) return0; else{ if((!T->lchild)&&(!T->rchild))//无左、右子树 return1; else return(CountLeaf(T->lchild)+CountLeaf(T->rchild)); }}intmain(){ BiTreeT;Status(*visit)(ElemTypee)=Visit;inta;printf("************【请先建立二叉树】************\n"); printf("请输入二叉树的元素(空节点以#号表示):\n"); CreateBiTree(T);for(;;){ printf("请选择如下操作码\n");printf("\n");printf("*****【1】先序遍历*****\n"); printf("*****【2】中序遍历*****\n"); printf("*****【3】后序遍历*****\n"); printf("*****【4】求二叉树的高度*****\n"); printf("*****【5】二叉树的结点数*****\n"); printf("*****【6】二叉树中度为1的结点数-***\n"); printf("*****【7】统计二叉树叶子结点--*****\n");printf("**********************************************\n");scanf("%d",&a);switch(a){ case1:PreOrderTraverse(T,visit);printf("\n");break; case2:InOrderTraverse(T,visit);printf("\n");break; case3:PostOrderTraverse(T,visit);printf("\n");break;case4:printf("二叉树的高度为：%d\n",BiTreeDepth(T));break; case5:printf("二叉树的结点数为：%d\n",CountNode(T));break; case6:printf("度为1的结点数为：%d\n",NodeOne(T));break; case7:printf("二叉树的叶子结点数为：%d\n",CountLeaf(T));break;default:printf("选择错误!\n"); } } return0;}运行结果分析课程设计题一：链表操作利用链表的插