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

吉林工業(yè)職業(yè)技術(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)PAGEPAGE19（數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)報(bào)告）目錄一、 實(shí)訓(xùn)目的 1二、 實(shí)訓(xùn)題目 2三、 實(shí)訓(xùn)步驟 2四、 實(shí)訓(xùn)內(nèi)容 3五、 實(shí)訓(xùn)心得 19六、 參考文獻(xiàn) 19實(shí)訓(xùn)目的通過實(shí)訓(xùn)，對(duì)所學(xué)數(shù)據(jù)結(jié)構(gòu)和程序設(shè)計(jì)的基本知識(shí)和基本理論有更進(jìn)一步的了解和認(rèn)識(shí)，將理論和實(shí)際相結(jié)合，能夠根據(jù)數(shù)據(jù)對(duì)象的特性，學(xué)會(huì)數(shù)據(jù)組織的方法，能把現(xiàn)實(shí)世界中的實(shí)際問題在計(jì)算機(jī)內(nèi)部表示出來。主要是培養(yǎng)學(xué)生綜合利用C語言進(jìn)行程序設(shè)計(jì)的能力和創(chuàng)新能力以及綜合解決問題的能力。運(yùn)用算法分析與程序設(shè)計(jì)的一般方法進(jìn)行實(shí)際項(xiàng)目的開發(fā)。本次實(shí)訓(xùn)盡量選取與實(shí)際結(jié)合緊密或?qū)W生比較感興趣的項(xiàng)目，本次實(shí)訓(xùn)學(xué)生需要具備熟練的程序設(shè)計(jì)基礎(chǔ)、數(shù)據(jù)結(jié)構(gòu)和計(jì)算機(jī)應(yīng)用基礎(chǔ)知識(shí)，具備程序編寫、調(diào)試的基本能力，具有一定的文字表達(dá)和報(bào)告撰寫能力，具備辦公軟件使用能力。通過實(shí)訓(xùn)，考查語言基本概述掌握是否牢固，并考查與后續(xù)課程較為密切的結(jié)構(gòu)體，鏈表，文件的運(yùn)用熟練程度，加強(qiáng)對(duì)基本概念的理解和復(fù)習(xí)，最重要的是了解基本軟件的設(shè)計(jì)步驟，還有對(duì)軟件調(diào)試的掌握。能夠根據(jù)數(shù)據(jù)對(duì)象的特性，學(xué)會(huì)數(shù)據(jù)組織的方法，能把現(xiàn)實(shí)世界中的實(shí)際問題在計(jì)算機(jī)內(nèi)部表示出來，并培養(yǎng)基本的、良好的程序設(shè)計(jì)技能。實(shí)訓(xùn)題目（一）單項(xiàng)題目1、二叉樹遍歷【問題描述】建立二叉樹，實(shí)現(xiàn)二叉樹的先序遍歷、中序、后序和層序遍歷（用遞歸或非遞歸的方法都可以）。【要求】編寫菜單程序。能夠輸入二叉樹的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立二叉樹存儲(chǔ)結(jié)構(gòu)的輸入函數(shù)、輸出先序遍歷序列的函數(shù)；輸出中序遍歷序列的函數(shù)；輸出后序遍歷序列的函數(shù)；輸出層序遍歷序列的函數(shù)。（二）綜合題目1、圖書管理系統(tǒng)【問題描述】建立一個(gè)圖書信息文件，包括書號(hào)（num）、書名（bookname）、作者（name）、出版社（publish）、價(jià)格（price）等。【要求】建立一個(gè)圖書信息文件，包括書號(hào)（num）、書名（bookname）、作者（name）、出版社（publish）、價(jià)格（price）等。實(shí)訓(xùn)步驟1、問題分析正確理解問題，分析問題究竟“做什么”，分析問題已知的信息及其作用，分析在解決中對(duì)信息處理的規(guī)則、要求、限制條件，分析問題解決后應(yīng)該輸出什么樣的結(jié)果（輸出形式、格式、內(nèi)容）。并分析得出判定結(jié)果是否正確的標(biāo)準(zhǔn)。2、設(shè)計(jì)分析得出解決問題的思路、主要流程、采用的數(shù)據(jù)結(jié)構(gòu)類型的說明、主要算法的思想。3、設(shè)計(jì)方案采用的數(shù)據(jù)結(jié)構(gòu)類型的定義、主要算法的描述及說明。4、詳細(xì)設(shè)計(jì)根據(jù)問題要求和已得到的算法編寫程序。5、調(diào)試程序發(fā)現(xiàn)程序中存在的語法錯(cuò)誤和一些邏輯錯(cuò)誤，并修改，使程序能夠運(yùn)行。6、運(yùn)行程序選擇若干具有代表性的輸入數(shù)據(jù)（包括合理數(shù)據(jù)和不合理數(shù)據(jù)），進(jìn)行測(cè)試，盡量使程序的各語句和分支都被檢查到，以便發(fā)現(xiàn)程序中的錯(cuò)誤和漏洞，以便改進(jìn)算法和程序。7、使用說明包括程序源代碼、算法（程序）流程圖、開發(fā)過程中各階段的有關(guān)記錄、算法的正確性證明、程序的測(cè)試結(jié)果、對(duì)輸入輸出要求及格式的詳細(xì)描述。實(shí)訓(xùn)內(nèi)容（一）個(gè)人題目1、二叉樹遍歷【問題描述】建立二叉樹，實(shí)現(xiàn)二叉樹的先序遍歷、中序、后序和層序遍歷（用遞歸或非遞歸的方法都可以）?！疽蟆烤帉懖藛纬绦?。能夠輸入二叉樹的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立二叉樹存儲(chǔ)結(jié)構(gòu)的輸入函數(shù)、輸出先序遍歷序列的函數(shù)；輸出中序遍歷序列的函數(shù)；輸出后序遍歷序列的函數(shù)；輸出層序遍歷序列的函數(shù)?！驹O(shè)計(jì)分析】1、總體設(shè)計(jì)(基本概念)樹的概念樹（Tree）是n（n>=0）個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹中：1) 有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；2) 當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m（m>0）個(gè)互不相交的有限集T1，T2Tm，其中每一個(gè)集合又是一棵樹，并且稱為根的子樹（SubTree）?！纠咳鐖D1所示：圖1圖1是有8個(gè)結(jié)點(diǎn)的樹，其中A是根，其余結(jié)點(diǎn)分成2個(gè)互不相交的子集：T1={B，D}，T2={C，E，F(xiàn)，G，H}；T1和T2都是根A的子樹，且本身也是一棵樹?！驹O(shè)計(jì)方案】1．創(chuàng)建二叉樹（可從鍵盤輸入各結(jié)點(diǎn)的值）2．按某種方式對(duì)二叉樹進(jìn)行遍歷3．樹型結(jié)構(gòu)是一種非常重要的非線性結(jié)構(gòu)。樹在客觀世界是廣泛存在的，在計(jì)算機(jī)領(lǐng)域里也得到了廣泛的應(yīng)用。在編譯程序里，也可用樹來表示源程序的語法結(jié)構(gòu)，在數(shù)據(jù)庫(kù)系統(tǒng)中，數(shù)形結(jié)構(gòu)也是信息的重要組織形式。4．節(jié)點(diǎn)的有限集合（N大于等于0）。在一棵非空數(shù)里：（1）、有且僅有一個(gè)特定的根節(jié)點(diǎn)；（2）、當(dāng)N大于1時(shí)，其余結(jié)點(diǎn)可分為M（M大于0）個(gè)互不相交的子集，其中每一個(gè)集合又是一棵樹，并且稱為根的子樹。樹的定義是以遞歸形式給出的。5．二叉樹是另一種樹形結(jié)構(gòu)。它的特點(diǎn)是每個(gè)結(jié)點(diǎn)最多有兩棵子樹，并且，二叉樹的子樹有左右之分，其次序不能顛倒。從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結(jié)點(diǎn)及左、右子樹這三個(gè)基本部分組成。因此，在任一給定結(jié)點(diǎn)上，可以按某種次序執(zhí)行三個(gè)操作：（1）訪問結(jié)點(diǎn)本身(N)，（2）遍歷該結(jié)點(diǎn)的左子樹(L)，（3）遍歷該結(jié)點(diǎn)的右子樹(R)。以上三種操作有六種執(zhí)行次序：NLR、LNR、LRN、NRL、RNL、RLN?！驹敿?xì)設(shè)計(jì)】本程序源代碼如下：/*源程序*//*Note:YourchoiceisCIDE*/#include"stdio.h"#include<iostream>#include<stdio.h>#include<stdlib.h>#defineMax20typedefcharDataType;#defineMaxStackSize50usingnamespacestd;typedefstructNode{DataTypedata; structNode*leftChild; structNode*rightChild; }BiTreeNode;typedefBiTreeNode*DataType2;typedefstruct{DataType2stack[MaxStackSize];inttop;}SeqStack;typedefstruct{DataType2quene[MaxStackSize];intfront;intrear;}Quene;voidStackInitiate(SeqStack*S) {S->top=0; }intStackNotEmpty(SeqStackS){if(S.top<=0) return0;elsereturn1;}intStackPush(SeqStack*S,DataType2x){if(S->top>=MaxStackSize){printf("堆棧已滿無法插入!\n");return0;}else{S->stack[S->top]=x;S->top++;return1;}}intStackPop(SeqStack*S,DataType2*d){if(S->top<=0){printf("堆棧已空無數(shù)據(jù)元素出棧!\n");return0;}else{S->top--;*d=S->stack[S->top];return1;}}intStackTop(SeqStackS,DataType2*d){if(S.top<=0){printf("堆棧已空!\n");return0;}else{*d=S.stack[S.top-1];return1;}}typedefstructnode{ chardata; structnode*lchild; structnode*rchild;}BTNode;typedefBTNode*BTree;intNodeNum,leaf;BTreeCreatBTree(void){BTreeT;charch;if((ch=getchar())=='*')return(NULL);else{ T=(BTNode*)malloc(sizeof(BTNode)); T->data=ch; T->lchild=CreatBTree(); T->rchild=CreatBTree(); return(T);}}voidPreorder(BTreeT){ if(T){ printf("%c",T->data); Preorder(T->lchild); Preorder(T->rchild); }}voidInorder(BTreeT){ if(T) { Inorder(T->lchild); printf("%c",T->data); Inorder(T->rchild); }}voidPostorder(BTreeT){ if(T) { Postorder(T->lchild); Postorder(T->rchild); printf("%c",T->data); }}intTreeDepth(BTreeT){ inthl,hr,max; if(T) { hl=TreeDepth(T->lchild); hr=TreeDepth(T->rchild); max=hl>hr?hl:hr; NodeNum=NodeNum+1; if(hl==0&&hr==0) leaf=leaf+1; return(max+1); } elsereturn(0);}voidLevelorder(BTreeT){ intfront=0,rear=1; BTNode*cq[Max],*p; cq[1]=T; while(front!=rear) { front=(front+1)%NodeNum; p=cq[front]; printf("%c",p->data); if(p->lchild!=NULL) { rear=(rear+1)%NodeNum; cq[front]=p->lchild; cq[rear]=p->lchild; } if(p->rchild!=NULL) { rear=(rear+1)%NodeNum; cq[front]=p->rchild; cq[rear]=p->rchild; } }}voidmain(){ BTreeroot; inti,depth; printf("\n"); printf("創(chuàng)建二叉樹，請(qǐng)輸入完全二叉樹的先序序列，用*代表虛結(jié)點(diǎn):"); root=CreatBTree();//返回根結(jié)點(diǎn) do{ printf("\t1:先序遍歷\n"); printf("\t2:中序遍歷\n"); printf("\t3:后序遍歷\n"); printf("\t4:深度、結(jié)點(diǎn)數(shù)、葉子數(shù)\n"); printf("\t5:層次遍歷\n"); printf("備注：選擇層次遍歷之前，需要先選擇4，求出該樹的結(jié)點(diǎn)數(shù)。"); printf("\t0:Exit\n"); scanf("%d",&i);//輸入菜單序號(hào) switch(i) { case1:printf("先序遍歷結(jié)果為:"); Preorder(root); break; case2:printf("中序遍歷結(jié)果為:"); Inorder(root); break; case3:printf("后序遍歷結(jié)果為:"); Postorder(root); break; case4:depth=TreeDepth(root); printf("深度=%d結(jié)點(diǎn)數(shù)=%d",depth,NodeNum); printf("葉子數(shù)=%d",leaf); break; case5:printf("層次遍歷為:"); Levelorder(root); break; default:exit(1); } printf("\n"); } while(i!=0);}【使用說明】本程序在turboc2.0環(huán)境下運(yùn)行，迷宮大小為20×20，需要修改迷宮大小時(shí)，可以修改程序中N值的大小。迷宮圖由系統(tǒng)自動(dòng)隨機(jī)生成，每次生成的迷宮圖是不同的。按enter健顯示最終搜索結(jié)果。按Q健退出程序?！具\(yùn)行調(diào)試】圖（1）二叉樹遍歷主界面圖（2）（二）綜合題目1、圖書管理系統(tǒng)【問題描述】建立一個(gè)圖書信息文件，包括書號(hào)（num）、書名（bookname）、作者（name）、出版社（publish）、價(jià)格（price）等?！疽蟆烤帉懖藛纬绦?，功能包括：建立圖書信息、插入記錄，刪除記錄、修改記錄、按照書號(hào)或書名查詢記錄、顯示記錄、根據(jù)圖書價(jià)格進(jìn)行排序。定義圖書信息結(jié)構(gòu)體名稱為book。書號(hào)（num）、書名（bookname）、作者（name）、出版社（publish）均為字符型數(shù)組。價(jià)格（price）為單精度型數(shù)據(jù)?！驹O(shè)計(jì)分析】系統(tǒng)目標(biāo)分析每個(gè)學(xué)校都有圖書館，最初由于圖書數(shù)量和種類較少，人工手動(dòng)管理比較方便和靈活。隨著社會(huì)的發(fā)展，圖書的數(shù)量和種類越來越多，人工手動(dòng)管理會(huì)降低工作的效率，希望建立一個(gè)圖書館圖書信息管理系統(tǒng)，是為了解決了人工手動(dòng)管理圖書信息在實(shí)踐的問題，從而達(dá)到系統(tǒng)化、規(guī)范化、標(biāo)準(zhǔn)化的水平。該系統(tǒng)的建立不但給管理者帶來了方便，也節(jié)省了工作時(shí)間從而提高了工作效率。

在構(gòu)造系統(tǒng)時(shí)，首先從需求出發(fā)構(gòu)造數(shù)據(jù)庫(kù)表，然后再由數(shù)據(jù)庫(kù)表結(jié)合需求劃分系統(tǒng)功能模塊。這樣，就把一個(gè)大的系統(tǒng)分解成了幾個(gè)小系統(tǒng)。這里把系統(tǒng)的層次劃分為了三個(gè)部分：一個(gè)自由態(tài)：即面向任何用戶的界面，提供登錄功能，以便不同身份的用戶登錄子系統(tǒng)；一個(gè)是一般用戶態(tài)：即圖書有服務(wù)子系統(tǒng)；還有一個(gè)是管理員界面：提供圖書的管理和維護(hù)功能。對(duì)于不同子系統(tǒng)之間的功換，采用了登錄功能和用戶注銷功能。系統(tǒng)劃分了子系統(tǒng)后，下一步的工作是繼續(xù)劃分子系統(tǒng)的小模塊。先考慮在進(jìn)入子系統(tǒng)時(shí)應(yīng)該做什么，進(jìn)入系統(tǒng)之后又應(yīng)該做什么，提供那些服務(wù)等。例如，對(duì)于圖書信息服務(wù)子系統(tǒng)，在用戶進(jìn)入時(shí)首先得調(diào)用相關(guān)數(shù)據(jù)庫(kù)表，找出用戶的圖書借閱情況；進(jìn)入系統(tǒng)后，子系統(tǒng)得提供圖書查詢、圖書借閱和還書功能。另外，針對(duì)本系統(tǒng)的特殊情況，同時(shí)也考慮系統(tǒng)的可移植性，在系統(tǒng)中增加了數(shù)據(jù)庫(kù)路徑的維護(hù)部分。最后，考慮到系統(tǒng)的安全性，還在系統(tǒng)中特別增加了“加密界面”的功能。【設(shè)計(jì)方案】本數(shù)據(jù)庫(kù)管理系統(tǒng)主要由圖書檢索、圖書管理、數(shù)據(jù)維護(hù)、圖書統(tǒng)計(jì)、打印輸出、系統(tǒng)維護(hù)六大模塊組成,如圖1所示。各模塊功能如下：1、主控模塊主控模塊的功能是控制各個(gè)分支模塊,它是實(shí)現(xiàn)各模塊功能的總控制臺(tái)2、圖書檢索模塊是圖書管理系統(tǒng)的重要模塊之一,是讀者快速查詢圖書的途徑本模塊的功能是按書名、書號(hào)、作者、出版社、圖書分類查詢數(shù)據(jù)維護(hù)模塊是由圖書管理員控制的模塊,它由增加、修改和刪除讀者,增加、修改刪除圖書,瀏覽修改讀者、瀏覽修改圖書等程序組成。在軟件設(shè)計(jì)時(shí)考慮到讀者編號(hào)、書名、書號(hào)是唯一的,因此,在修改讀者或圖書中,讀者記錄或圖書記錄一經(jīng)登記“讀者編號(hào)”和“姓名”便不能修改,在刪除讀者或圖書時(shí)只要讀者有借出圖書未還或庫(kù)存圖書原有數(shù)量與現(xiàn)有庫(kù)存量不符便不能刪除。5、數(shù)據(jù)統(tǒng)計(jì)模塊由讀者統(tǒng)計(jì)、圖書統(tǒng)計(jì)、借出圖書分類統(tǒng)計(jì)、到期未歸還圖書讀者統(tǒng)計(jì)幾部分組成我們小組的信息系統(tǒng)開發(fā)課程設(shè)計(jì)題目是：圖書管理系統(tǒng)開發(fā)。系統(tǒng)開發(fā)的總的設(shè)計(jì)目標(biāo)是實(shí)現(xiàn)圖書管理的系統(tǒng)化、規(guī)范化和自動(dòng)化，實(shí)現(xiàn)對(duì)圖書資料的集中統(tǒng)一的管理。本系統(tǒng)主要實(shí)現(xiàn)對(duì)圖書館信息的管理，主要功能為管理有關(guān)讀者，書籍，借閱和管理者的信息等。本系統(tǒng)結(jié)構(gòu)分為讀者信息管理模塊，書籍信息管理模塊，借閱信息管理模塊，管理者信息管理模塊。讀者信息管理部分有兩方面的功能，可以瀏覽讀者的信息，可以對(duì)讀者信息進(jìn)行維護(hù)。書籍信息管理可以瀏覽書籍的信息，可以對(duì)書籍信息進(jìn)行維護(hù)。借閱信息管理可以顯示當(dāng)前數(shù)據(jù)庫(kù)中書籍借閱情況，可以對(duì)借閱信息進(jìn)行維護(hù)。管理者信息管理可以顯示數(shù)據(jù)庫(kù)中管理者的情況，可以對(duì)管理者信息進(jìn)行維護(hù)?？梢?，本系統(tǒng)并不復(fù)雜，主要解決的問題是利用關(guān)鍵字對(duì)數(shù)據(jù)庫(kù)進(jìn)行查詢?！驹敿?xì)設(shè)計(jì)】本程序源代碼如下：/*源程序*//*Note:YourchoiceisCIDE*//*Note:YourchoiceisCIDE*/#include<stdio.h>#include<math.h>#include<string.h>#include<stdlib.h>structbooks_list{charauthor[20];/*作者名*/charbookname[20];/*書名*/charpublisher[20];/*出版單位*/charpbtime[15];/*出版時(shí)間*/charloginnum[10];/*登陸號(hào)*/floatprice;/*價(jià)格*/charclassfy[10];/*分類號(hào)*/structbooks_list*next;/*鏈表的指針域*/};structbooks_list*Create_Books_Doc();/*新建鏈表*/voidInsertDoc(structbooks_list*head);/*插入*/voidDeleteDoc(structbooks_list*head,intnum);/*刪除*/voidPrint_Book_Doc(structbooks_list*head);/*瀏覽*/voidsearch_book(structbooks_list*head);/*查詢*/voidinfo_change(structbooks_list*head);/*修改*/voidsave(structbooks_list*head);/*保存數(shù)據(jù)至文件*//*瀏覽操作*/voidPrint_Book_Doc(structbooks_list*head){structbooks_list*p;if(head==NULL||head->next==NULL)/*判斷數(shù)據(jù)庫(kù)是否為空*/{printf("\n━━━━沒有圖書記錄!━━━━\n\n");return;}p=head;printf("┏━━━┳━━━┳━━━┳━━━┳━━━━┳━━━┳━━━┓\n");printf("┃登錄號(hào)┃書名┃作者┃出版單位┃出版時(shí)間┃分類號(hào)┃價(jià)格┃\n");printf("┣━━━╋━━━╋━━━╋━━━╋━━━━╋━━━╋━━━┫\n");/*指針從頭節(jié)點(diǎn)開始移動(dòng)，遍歷至尾結(jié)點(diǎn)，依次輸出圖書信息*/while(p->next!=NULL){p=p->next;printf("┃%-6.6s┃%-10.10s┃%-10.10s┃%-10.10s┃%-12.12s┃%-6.6s┃%.2f┃\n",p->loginnum,p->bookname,p->author,p->publisher,p->pbtime,p->classfy,p->price);/*循環(huán)輸出表格*/}printf("┗━━━┻━━━┻━━━┻━━━┻━━━━┻━━━┻━━━┛\n");printf("\n");}/*刪除操作*/voidDeleteDoc(structbooks_list*head){structbooks_list*s,*p;/*s為中間變量，p為遍歷時(shí)使用的指針*/chartemp[20];intpanduan;/*此變量用于判斷是否找到了書目*/panduan=0;p=s=head;printf("[請(qǐng)輸入您要?jiǎng)h除的書名]:");scanf("%s",temp);/*遍歷到尾結(jié)點(diǎn)*/while(p!=NULL){if(strcmp(p->bookname,temp)==0){panduan++;break;}p=p->next;}if(panduan==1){for(;s->next!=p;)/*找到所需刪除卡號(hào)結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)*/{s=s->next;}s->next=p->next;/*將后一節(jié)點(diǎn)地址賦值給前一節(jié)點(diǎn)的指針域*/free(p);printf("\n━━━━刪除成功!━━━━\n");}else/*未找到相應(yīng)書目*/{printf("您輸入的書目不存在，請(qǐng)確認(rèn)后輸入!\n");}return;}intmain(void){structbooks_list*head;charchoice;head=NULL;for(;;)/*實(shí)現(xiàn)反復(fù)輸入選擇*/{printf("┏━━━━━━━━━━━━━━━━━━━┏━┓\n");printf("┃┃socat圖書管理系統(tǒng)┃┃\n");printf("┃┗━━━━━━━━━━━━━━━━━━━┛┃\n");printf("┃●[1]圖書信息錄入┃\n");printf("┃┃\n");printf("┃●[2]圖書信息瀏覽┃\n");printf("┃┃\n");printf("┃●[3]圖書信息查詢┃\n");printf("┃┃\n");printf("┃●[4]圖書信息修改┃\n");printf("┃┃\n");printf("┃●[5]圖書信息刪除┃\n");printf("┃┃\n");printf("┃●[6]退出系統(tǒng)┃\n");printf("┗━━━━━━━━━━━━━━━━━━━━━━━┛\n");printf("請(qǐng)選擇:");fflush(stdin);scanf("%c",&choice);if(choice=='1'){if(