數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)報(bào)告

山東科技大學(xué)泰山科技學(xué)院課程實(shí)訓(xùn)說明書課程：數(shù)據(jù)結(jié)構(gòu)（C語言版）題目：單鏈表、二叉樹院系：信息工程系 專業(yè)班級(jí)：計(jì)算機(jī)科學(xué)與技術(shù) 學(xué)號(hào)：201443****** 學(xué)生姓名：*** 指導(dǎo)教師：2015年12月18日成績評(píng)語：指導(dǎo)教師第頁一、設(shè)計(jì)目的課程設(shè)計(jì)題一：鏈表操作1、設(shè)計(jì)目的（1）掌握線性表的在順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。（2）掌握線性表在順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)上的基本操作。2、設(shè)計(jì)內(nèi)容和要求（1）利用鏈表的插入運(yùn)算建立線性鏈表，然后實(shí)現(xiàn)鏈表的查找、插入、刪除、計(jì)數(shù)、輸出、排序、逆置等運(yùn)算（查找、插入、刪除、計(jì)數(shù)、輸出、排序、逆置要單獨(dú)寫成函數(shù)），并能在屏幕上輸出操作前后的結(jié)果。課程設(shè)計(jì)題二：二叉樹的基本操作1、設(shè)計(jì)目的（1）掌握二叉樹的概念和性質(zhì)（2）掌握任意二叉樹存儲(chǔ)結(jié)構(gòu)。（3）掌握任意二叉樹的基本操作。2、設(shè)計(jì)內(nèi)容和要求（1）對(duì)任意給定的二叉樹（頂點(diǎn)數(shù)自定）建立它的二叉鏈表存儲(chǔ)結(jié)構(gòu)，并利用棧的五種基本運(yùn)算（置空棧、進(jìn)棧、出棧、取棧頂元素、判?？眨?shí)現(xiàn)二叉樹的先序、中序、后序三種遍歷，輸出三種遍歷的結(jié)果。（2）求二叉樹高度、結(jié)點(diǎn)數(shù)、度為1的結(jié)點(diǎn)數(shù)和葉子結(jié)點(diǎn)數(shù)。運(yùn)行環(huán)境（軟、硬件環(huán)境）軟件環(huán)境MicrosoftVisualC++6.0硬件環(huán)境計(jì)算機(jī)一臺(tái)處理器：Intel(R)Core(TM)i3-4010UCPU@1.70GHz1.70GHz數(shù)據(jù)結(jié)構(gòu)及算法設(shè)計(jì)的思想課程設(shè)計(jì)題一：鏈表操作定義一個(gè)創(chuàng)建鏈表的函數(shù)，通過該函數(shù)可以創(chuàng)建一個(gè)鏈表，并為下面的函數(shù)應(yīng)用做好準(zhǔn)備。（因?yàn)槊總€(gè)新生成的結(jié)點(diǎn)的插入位置在表尾，則算法中必須維持一個(gè)始終指向已建立的鏈表表尾的指針。）（2）定義一個(gè)遍歷查找（按序號(hào)差值）的算法，通過此算法可以查找到鏈表中的每一個(gè)結(jié)點(diǎn)是否存在。（單鏈表是一種順序存取的結(jié)構(gòu)，為找第i個(gè)數(shù)據(jù)元素，必須先找到第i-1個(gè)數(shù)據(jù)元素。因此，查找第i個(gè)數(shù)據(jù)元素的基本操作為：移動(dòng)指針，比較j和i。令指針p始終指向線性表中第j個(gè)數(shù)據(jù)元素。設(shè)單鏈表的長度為n，要查找表中第i個(gè)結(jié)點(diǎn)，僅當(dāng)1≤i≤n時(shí)，i的值是合法的。）（3）定義插入結(jié)點(diǎn)的算法，通過定義這個(gè)算法，并結(jié)合這查找前驅(qū)和后繼的算法便可以在連鏈表的任意位置進(jìn)行插入一個(gè)新結(jié)點(diǎn)。（在鏈表中插入結(jié)點(diǎn)只需要修改指針。但同時(shí)，若要在第i個(gè)結(jié)點(diǎn)之前插入元素，修改的是第i-1個(gè)結(jié)點(diǎn)的指針。因此，在單鏈表中第i個(gè)結(jié)點(diǎn)之前進(jìn)行插入的基本操作為:找到線性表中第i-1個(gè)結(jié)點(diǎn)，然后修改其指向后繼的指針。）（4）定義刪除結(jié)點(diǎn)的操作，這個(gè)算法用于對(duì)鏈表中某個(gè)指定位置的結(jié)點(diǎn)的刪除工作。（在單鏈表中刪除第i個(gè)結(jié)點(diǎn)的基本操作為:找到線性表中第i-1個(gè)結(jié)點(diǎn)，修改其指向后繼的指針。）（5）定義一個(gè)計(jì)數(shù)的算法，通過此算法可以統(tǒng)計(jì)鏈表中結(jié)點(diǎn)的個(gè)數(shù)。（6）定義輸出鏈表的算法，通過對(duì)第一步已經(jīng)定義好的創(chuàng)建鏈表函數(shù)的調(diào)用，在這一步通過調(diào)用輸出鏈表的函數(shù)算法來實(shí)現(xiàn)對(duì)鏈表的輸出操作。（7）定義一個(gè)排序（冒泡排序）的算法，通過此算法對(duì)表中元素按照一定順序進(jìn)行排列。（8）定義一個(gè)逆置單鏈表的操作，通過定義此算法，可以逆置輸出單鏈表。（將原鏈表中的頭結(jié)點(diǎn)和第一個(gè)元素結(jié)點(diǎn)斷開（令其指針域?yàn)榭眨葮?gòu)成一個(gè)新的空表，然后將原鏈表中各結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)起，依次插入這個(gè)新表的頭部（即令每個(gè)插入的結(jié)點(diǎn)成為新的第一個(gè)元素結(jié)點(diǎn)））課程設(shè)計(jì)題二：二叉樹的基本操作IchildDataRchild定義二叉樹鏈表：二叉樹的鏈?zhǔn)酱鎯?chǔ)方式下每個(gè)結(jié)點(diǎn)包含3個(gè)域，分別記錄該結(jié)點(diǎn)的屬性值及左右子樹的位置。其左右子樹的位置是通過指針方式體現(xiàn)，其中Ichild是指向該結(jié)點(diǎn)左子樹的指針，rchild為指向該結(jié)點(diǎn)右子數(shù)的指針。結(jié)點(diǎn)結(jié)構(gòu)：二叉樹的創(chuàng)建：根據(jù)先序遍歷結(jié)果建立二叉樹，將第一個(gè)輸入的結(jié)點(diǎn)作為二叉樹的根結(jié)點(diǎn)，后繼輸入的結(jié)點(diǎn)序列是二叉樹左右子樹先序遍歷的結(jié)果，由它們生成二叉樹的左子數(shù)；再接下來輸入的結(jié)點(diǎn)序列為二叉樹右子樹先序遍歷的結(jié)果，應(yīng)該由它們生成二叉樹的右子樹。而由二叉樹左子樹先序遍歷的結(jié)果生成二叉樹的左子樹和由二叉樹右子樹先序遍歷的結(jié)果生成二叉樹的右子樹的過程均與由整棵二叉樹的先序遍歷結(jié)果生成該二叉樹的過程完全相同，只是所處理的對(duì)象范圍不同，所以可以用遞歸方式實(shí)現(xiàn)之。使用CreatBitree建立一顆二叉樹時(shí)，必須按其先序遍歷的順序輸入結(jié)點(diǎn)的值，遍歷過程中遇到空子樹時(shí)，必須使用“#”代替。例如：ABC##DE#G##F###（3）二叉樹的先序遍歷：首先訪問根結(jié)點(diǎn)；然后按照先序遍歷的方式訪問根結(jié)點(diǎn)的左子樹；再按照先序遍歷的方式訪問根結(jié)點(diǎn)的右子數(shù)。（4）二叉樹的中序遍歷：首先按照中序遍歷的方式訪問根結(jié)點(diǎn)的左子樹；然后訪問根結(jié)點(diǎn)；最后按照中序遍歷的方式訪問根結(jié)點(diǎn)的右子樹。（5）二叉樹的后序遍歷：首先按照后序遍歷的方式訪問根結(jié)點(diǎn)的左子樹；然后按照后序遍歷的方式訪問根結(jié)點(diǎn)的右子樹；最后訪問根結(jié)點(diǎn)。（6）求二叉樹的高度：二叉樹T，如果T為空，則高度為0；否則，其高度為其左子樹的高度和右子樹的高度的最大值再加1。（7）求二叉樹的結(jié)點(diǎn)數(shù)：二叉樹T，若T為空，則T中所含結(jié)點(diǎn)的個(gè)數(shù)為0；否則，T中所含結(jié)點(diǎn)個(gè)數(shù)等于左子樹中所含結(jié)點(diǎn)個(gè)數(shù)加上右子樹中所含結(jié)點(diǎn)的個(gè)數(shù)再加1。（8）求二叉樹度為1的結(jié)點(diǎn)數(shù)：二叉樹T，若T為空，則T中度為1的結(jié)點(diǎn)數(shù)為0；否則，T所含度為1的結(jié)點(diǎn)數(shù)等于左子樹不為空右子樹為空和左子樹為空右子樹不為空的結(jié)點(diǎn)個(gè)數(shù)之和。（9）求二叉樹的葉子結(jié)點(diǎn)數(shù)：求二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)，即求二叉樹的所有結(jié)點(diǎn)中左、右子數(shù)均為空的結(jié)點(diǎn)個(gè)數(shù)之和。數(shù)據(jù)結(jié)構(gòu)及算法設(shè)計(jì)課程設(shè)計(jì)題一：鏈表操作typedefstructLNode//線性表的單鏈表存儲(chǔ)結(jié)構(gòu)voidCreatList_L(LinkList&L,intn);//頭插法建表（逆序建表）voidGetElem_L(LinkList&L);//按序號(hào)查值StatusListInsert_L(LinkList&L,inti,ElemTypee);//插入StatusListDelete_L(LinkList&L,inti,ElemType&e);//刪除voidListLength(LinkList&L);//計(jì)數(shù)voidPrintList(LinkList&L);//輸出voidListSort(LinkList&L);//冒泡排序voidOpposeList(LinkList&L);//逆置課程設(shè)計(jì)題二：二叉樹的基本操作typedefstructBiTNode//二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)StatusCreateBiTree(BiTree&T)//建立二叉樹的存儲(chǔ)結(jié)構(gòu)——二叉鏈表（先序）。StatusPreOrderTraverse(BiTree&T,Status(*Visit)(ElemTypee))//先序遍歷二叉樹基本操作的遞歸算法在二叉鏈表上的實(shí)現(xiàn)StatusInOrderTraverse(BiTree&T,Status(*Visit)(ElemTypee))//中序遍歷二叉樹基本操作的遞歸算法在二叉鏈表上的實(shí)現(xiàn)StatusPostOrderTraverse(BiTree&T,Status(*Visit)(ElemTypee))//后序遍歷二叉樹基本操作的遞歸算法在二叉鏈表上的實(shí)現(xiàn)StatusVisit(ElemTypee)//對(duì)二叉樹中的數(shù)據(jù)元素訪問intBiTreeDepth(BiTree&T)//求二叉樹的高度intCountNode(BiTree&T)//二叉樹的結(jié)點(diǎn)數(shù)intNodeOne(BiTree&T)//二叉樹中度為1的結(jié)點(diǎn)數(shù)intCountLeaf(BiTree&T)//統(tǒng)計(jì)二叉樹葉子結(jié)點(diǎn)源代碼課程設(shè)計(jì)題一：鏈表操作#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);//按序號(hào)查值 StatusListInsert_L(LinkList&L,inti,ElemTypee);//插入 StatusListDelete_L(LinkList&L,inti,ElemType&e);//刪除 voidListLength(LinkList&L);//計(jì)數(shù) voidPrintList(LinkList&L);//輸出 voidListSort(LinkList&L);//冒泡排序 voidOpposeList(LinkList&L);//逆置voidCreatList_L(LinkList&L,intn){//逆位序輸入n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表L。 L=(LinkList)malloc(sizeof(LNode)); L->next=NULL;//先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表 for(i=n;i>0;--i){ p=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點(diǎn) scanf("%d",&p->data);//輸入元素值 p->next=L->next;//插到表頭 L->next=p; }}//頭插法建表（逆序建表）voidGetElem_L(LinkList&L){//L為帶頭接點(diǎn)的單鏈表的頭指針。當(dāng)?shù)趇個(gè)元素存在時(shí)，其賦值給e并返回ERROR inti,e; p=L->next; j=1;//初始化，p指向第一個(gè)結(jié)點(diǎn)，j為計(jì)時(shí)器 printf("請(qǐng)輸入查找位置:\n");scanf("%d",&i); while(p&&j<i){//順指針向后查找，直到p指向第i個(gè)元素或p為空 p=p->next; ++j; } if(!p||j>i) printf("第%d個(gè)元素不存在!",i);//第i個(gè)元素不存在 e=p->data;//取第i個(gè)元素 printf("查找結(jié)果為:%d\n",e); }//按序號(hào)查值StatusListInsert_L(LinkList&L,inti,ElemTypee){//在帶頭接點(diǎn)的單鏈線性表L中第i個(gè)位置之前插入元素e p=L; j=0; printf("請(qǐng)輸入插入位置:\n");scanf("%d",&i); while(p&&j<i-1){ p=p->next; ++j; }//尋找第i-1個(gè)結(jié)點(diǎn) if(!p||j>i-1) returnERROR;//i小于1或者大于表長加1 s=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點(diǎn) printf("請(qǐng)輸入插入元素:\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){//在帶頭接點(diǎn)的單鏈線性表L中，刪除第i個(gè)元素，并由e返回其值 p=L; j=0; printf("請(qǐng)輸入刪除元素位置:\n");scanf("%d",&i); while(p->next&&j<i-1){//尋找第i個(gè)結(jié)點(diǎn)，并命令p指向其前趨 p=p->next; ++j; } if(!(p->next)||j>i-1) returnERROR;//刪除位置不合理 q=p->next; p->next=q->next;//刪除并釋放結(jié)點(diǎn) e=q->data; free(q); printf("刪除后的鏈表為：\n"); PrintList(L); returnOK;}//刪除voidListLength(LinkList&L){ p=L; intj=0; //線性鏈表最后一個(gè)結(jié)點(diǎn)的指針為空 while((p->next)!=NULL) { j++; p=p->next; } printf("單鏈表總共有%d個(gè)元素\n",j);printf("\n");}//計(jì)數(shù)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("************【請(qǐng)先建立單鏈表】************\n"); printf("請(qǐng)輸入元素個(gè)數(shù)值:\n"); scanf("%d",&n); printf("請(qǐng)輸入%d個(gè)元素:\n",n); CreatList_L(L,n);for(;;){ printf("請(qǐng)選擇如下操作碼\n");printf("\n");printf("*****【1】查找*****\n"); printf("*****【2】插入*****\n"); printf("*****【3】刪除*****\n"); printf("*****【4】計(jì)數(shù)*****\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("選擇錯(cuò)誤!\n"); } } return0;}課程設(shè)計(jì)題二：二叉樹的基本操作#include<stdio.h>#include<stdlib.h>#defineOK1#defineERROR0#defineOVERFLOW0typedefcharElemType;typedefintStatus;typedefintTElemType;//二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)typedefstructBiTNode{ TElemTypedata; structBiTNode*lchild,*rchild;}BiTNode,*BiTree;charch;//建立二叉樹的存儲(chǔ)結(jié)構(gòu)——二叉鏈表（先序）。StatusCreateBiTree(BiTree&T){//按先序次序輸入二叉樹結(jié)點(diǎn)的值（一個(gè)字符），空格字符表示空樹，構(gòu)造二叉樹鏈表表示的二叉樹T。 scanf("%c",&ch); if(ch=='#') T=NULL; else{ if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW); T->data=ch;//生成根結(jié)點(diǎn) CreateBiTree(T->lchild);//構(gòu)造左子樹 CreateBiTree(T->rchild);//構(gòu)造右子樹 } return0;}//先序遍歷二叉樹基本操作的遞歸算法在二叉鏈表上的實(shí)現(xiàn)StatusPreOrderTraverse(BiTree&T,Status(*Visit)(ElemTypee)){ if(T){if(!Visit(T->data))returnERROR;PreOrderTraverse(T->lchild,Visit);PreOrderTraverse(T->rchild,Visit);}returnOK;}//中序遍歷二叉樹基本操作的遞歸算法在二叉鏈表上的實(shí)現(xiàn)StatusInOrderTraverse(BiTree&T,Status(*Visit)(ElemTypee)){ if(T){InOrderTraverse(T->lchild,Visit);if(!Visit(T->data))returnERROR;InOrderTraverse(T->rchild,Visit);}returnOK;}//后序遍歷二叉樹基本操作的遞歸算法在二叉鏈表上的實(shí)現(xiàn)StatusPostOrderTraverse(BiTree&T,Status(*Visit)(ElemTypee)){ if(T){PostOrderTraverse(T->lchild,Visit);PostOrderTraverse(T->rchild,Visit);if(!Visit(T->data))returnERROR;;}returnOK;}StatusVisit(ElemTypee){//對(duì)二叉樹中的數(shù)據(jù)元素訪問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;}//二叉樹的結(jié)點(diǎn)數(shù)intCountNode(BiTree&T){ if(T==NULL) return0; else return(CountNode(T->lchild)+CountNode(T->rchild)+1);}//二叉樹中度為1的結(jié)點(diǎn)數(shù)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)); }}//統(tǒng)計(jì)二叉樹葉子結(jié)點(diǎn)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("************【請(qǐng)先建立二叉樹】************\n"); printf("請(qǐng)輸入二叉樹的元素(空節(jié)點(diǎn)以#號(hào)表示):\n"); CreateBiTree(T);for(;;){ printf("請(qǐng)選擇如下操作碼\n");printf("\n");printf("*****【1】先序遍歷*****\n"); printf("*****【2】中序遍歷*****\n"); printf("*****【3】后序遍歷*****\n"); printf("*****【4】求二叉樹的高度*****\n"); printf("*****【5】二叉樹的結(jié)點(diǎn)數(shù)*****\n"); printf("*****【6】二叉樹中度為1的結(jié)點(diǎn)數(shù)-***\n"); printf("*****【7】統(tǒng)計(jì)二叉樹葉子結(jié)點(diǎn)--*****\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("二叉樹的結(jié)點(diǎn)數(shù)為：%d\n",CountNode(T));break; case6:printf("度為1的結(jié)點(diǎn)數(shù)為：%d\n",NodeOne(T));break; case7:printf("二叉樹的葉子結(jié)點(diǎn)數(shù)為：%d\n",CountLeaf(T));break;default:printf("選擇錯(cuò)誤!\n"); } } return0;}運(yùn)行結(jié)果分析課程設(shè)計(jì)題一：鏈表操作利用鏈表的插