數(shù)據(jù)結(jié)構(gòu)實訓報告VIP

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