《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)

《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)《數(shù)據(jù)結(jié)構(gòu)》Ｃ語言版實(shí)驗(yàn)指導(dǎo)目錄TOC\o"1-3"\h\z《數(shù)據(jù)結(jié)構(gòu)》上機(jī)實(shí)驗(yàn)的目的和要求 1實(shí)驗(yàn)一順序結(jié)構(gòu)線性表的實(shí)現(xiàn) 2實(shí)驗(yàn)二單鏈表的插入和刪除 8實(shí)驗(yàn)三棧的實(shí)現(xiàn) 11實(shí)驗(yàn)四二叉樹操作實(shí)現(xiàn) 14實(shí)驗(yàn)五哈夫曼樹的建立與編碼實(shí)現(xiàn) 18實(shí)驗(yàn)六圖的遍歷操作 28實(shí)驗(yàn)七排序 34實(shí)驗(yàn)八查找 40《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì) 45PAGE50《數(shù)據(jù)結(jié)構(gòu)》上機(jī)實(shí)驗(yàn)的目的和要求通過上機(jī)實(shí)驗(yàn)加深對課程內(nèi)容的理解，增加感性認(rèn)識，提高軟件設(shè)計(jì)、編寫及調(diào)試程序的能力。要求所編的程序能正確運(yùn)行，并提交實(shí)驗(yàn)報告。實(shí)驗(yàn)報告的基本要求為：需求分析：陳述程序設(shè)計(jì)的任務(wù)，強(qiáng)調(diào)程序要做什么，明確規(guī)定：輸入的形式和輸出值的范圍；輸出的形式；程序所能達(dá)到的功能；測試數(shù)據(jù)：包括正確的輸入輸出結(jié)果和錯誤的輸入及輸出結(jié)果。概要設(shè)計(jì)：說明用到的數(shù)據(jù)結(jié)構(gòu)定義、主程序的流程及各程序模塊之間的調(diào)用關(guān)系。詳細(xì)設(shè)計(jì)：提交帶注釋的源程序或者用偽代碼寫出每個操作所涉及的算法。調(diào)試分析：調(diào)試過程中所遇到的問題及解決方法；算法的時空分析；經(jīng)驗(yàn)與體會。用戶使用說明：說明如何使用你的程序，詳細(xì)列出每一步操作步驟。測試結(jié)果：列出對于給定的輸入所產(chǎn)生的輸出結(jié)果。若有可能，測試隨輸入規(guī)模的增長所用算法的實(shí)際運(yùn)行時間的變化。

實(shí)驗(yàn)一順序結(jié)構(gòu)線性表的實(shí)現(xiàn)一、目的：掌握順序表的表示方法，存儲結(jié)構(gòu)及其基本操作的實(shí)現(xiàn)。二、要求：建立一順序表，實(shí)現(xiàn)其基本操作。三、示例程序：說明：一個完整的程序是由輸入，處理，輸出三部分組成的，每個部分還可以分為若干小部分，如輸入，又可以分為聲明，初始化變量，接收數(shù)據(jù)，預(yù)處理數(shù)據(jù)等。書上列出的算法是解決問題的基本思路，也可以是解決問題的處理過程，并未給出詳細(xì)的輸入與輸出，這一部分需要在練習(xí)過程中加入，在解決實(shí)際問題時，還需要做靈活的處理。Ｃ語言本身有自身的特點(diǎn)，其基本思想是與機(jī)器的指令碼相關(guān)的。要理解程序時必須明確這些特點(diǎn)，并從算法所根據(jù)的數(shù)據(jù)結(jié)構(gòu)下手，然后才能明白給出的程序中其算法的意義。本例程序用于演示順序表的基本操作，希望同學(xué)們好好掌握。#include<stdio.h>#include<string.h>#include<stdlib.h>#include<iostream.h>#defineLIST_INIT_SIZE50#defineLISTINCREMENT10#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineCANCEL0typedefstruct{int*elem;intlength;intlistsize;}sqlist;intcompare(intX,intY){if(X==Y)returnX;elsereturnFALSE;}//compare的關(guān)系判斷voidvisit(int&y){y=2*y;cout<<y<<"";}//將y值增加為原來的2倍intinitlist(sqlist&L){L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));if(!L.elem)returnERROR;elseL.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}//構(gòu)造一個空的線性表Lintdestroylist(sqlist&L){free(L.elem);returnOK;}//銷毀線性表Lintclearlist(sqlist&L){L.length=0;returnOK;}//將L重置為空表intlistempty(sqlistL){if(0==L.length)returnTRUE;elsereturnFALSE;}//求當(dāng)前表L是否為空intlistlength(sqlistL){returnL.length;}//求當(dāng)前線性表L的長度intgetelem(sqlistL,inti,int&e){if(i<1||i>L.length)exit(ERROR);e=*(L.elem+i-1);returnOK;}//用e返回L中第i個數(shù)據(jù)元素的值intlocateelem(sqlistL,inte,int(*compare)(intx1,intx2)){inti=1,j=0,*p;p=L.elem;while(i<=L.length&&!j){j=compare(*p++,e);++i;}if(i<=L.length)returni-1;elsereturnFALSE;}//求L中第一個與e滿足關(guān)系compare()的數(shù)據(jù)元素的位序，若不存在則返回0intpriorelem(sqlistL,intcur_e,int&pre_e){inti=2,*p;p=L.elem+1;while(i<=L.length&&(*p++)!=cur_e)i++;if(i>L.length)returnFALSE;else{pre_e=*p-2;returnOK;}}//若cur_e是L的數(shù)據(jù)元素，且不是第一個，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無定義intnextelem(sqlistL,intcur_e,int&next_e){inti=1,*p;p=L.elem;while(i<L.length&&(*p++)!=cur_e)i++;if(i>=L.length)returnFALSE;else{next_e=*p;returnOK;}}//若cur_e是L的數(shù)據(jù)元素，且不是最后一個，則用next_e返回它的后繼，否則操作失敗，next_e無定義intlistinsert(sqlist&L,inti,inte){int*newbase,*p,*q;if((i<1)||(i>L.length+1))returnERROR;if(L.length>=L.listsize){newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));if(!newbase){exit(0);}L.elem=newbase;L.listsize=L.listsize+LISTINCREMENT;}q=L.elem+i-1;for(p=L.elem+L.length-1;p>=q;--p)*(p+1)=*p;*q=e;++L.length;returnOK;}//在線性表L中第i個位置插入元素eintlistdelete(sqlist&L,inti,int&e){int*p,*q;if(i<1||i>L.length)returnERROR;else{p=L.elem+i-1;e=*p;q=L.elem+L.length-1;for(++p;p<=q;++p){*(p-1)=*p;}L.length--;returnOK;}}//將線性表中的第i個元素刪除并返回其值intlisttraverse(sqlistL,void(*visit)(int&p)){inti=1,*p;p=L.elem;while(i<=L.length){visit(*p);p++;i++;}returnOK;}//依次對L中的每一個元素調(diào)用函數(shù)visit(),一旦visit()失敗，則操作失敗voidmain(){sqlistL;inti,j,k,b,n,e,m,a,cur_e,pre_e,next_e;initlist(L);cout<<"初始化后的基值地址:"<<L.elem<<"L.length=:"<<L.length<<"L.listsize=:"<<L.listsize<<endl;cout<<"新建一順序表."<<endl;cout<<"當(dāng)前表是否為空表"<<listempty(L)<<endl;cout<<"定義該線性表長度:"<<endl;cin>>a;cout<<"分別輸入線性表的各個元素,按ENTER"<<endl;for(k=1;k<=a;k++){cin>>j;i=listinsert(L,k,j);}for(b=1;b<=10;b++)cout<<L.elem[b-1]<<endl;listlength(L);cout<<"當(dāng)前表長:"<<L.length<<endl;cout<<"輸入要取的數(shù)的位置n(n<=10)"<<endl;cin>>n;getelem(L,n,e);cout<<L.elem[n-1]<<endl;cout<<"與該數(shù)相等的的一個數(shù)的位序?yàn)?"<<locateelem(L,e,compare)<<endl;cout<<"輸入要取前驅(qū)的數(shù)的位置m(<=10)"<<endl;cin>>m;getelem(L,m,cur_e);if(priorelem(L,cur_e,pre_e))cout<<"cur_e的前驅(qū)為:"<<pre_e<<endl;elsecout<<"該元素沒前驅(qū)"<<endl;nextelem(L,cur_e,next_e);if(nextelem(L,cur_e,next_e))cout<<"cur_e的后繼為:"<<next_e<<endl;elsecout<<"該元素沒后繼"<<endl;cout<<"輸入要刪元素的位序m(<=10)"<<endl;cin>>m;listdelete(L,m,e);cout<<"被刪的元素為:"<<e<<endl;cout<<"刪除元素后表長為"<<L.length<<endl;listtraverse(L,visit);cout<<"置為空表"<<clearlist(L)<<endl;cout<<"銷毀線性表"<<destroylist(L)<<endl;}四、實(shí)驗(yàn)內(nèi)容分析、理解程序。調(diào)試程序，并設(shè)計(jì)輸入數(shù)據(jù)。修改程序：將順序表的ai元素刪除（i為３的倍數(shù)）。判斷該順序表中元素是否對稱,對稱返回1,否則返回0。實(shí)現(xiàn)把該表中所有奇數(shù)排在偶數(shù)之前,即表的前面為奇數(shù),后面為偶數(shù)。試著將程序改為無指針的順序表實(shí)現(xiàn)。五、實(shí)驗(yàn)報告要求基本要求見第一頁內(nèi)容。寫出實(shí)驗(yàn)結(jié)果，并畫出所建順序表的示意圖。六、附加實(shí)驗(yàn)內(nèi)容（詳細(xì)內(nèi)容略，請同學(xué)們自行找相關(guān)書籍進(jìn)行練習(xí)）ＶＣ程序調(diào)試方法明確ＶＣ中調(diào)試程序的基本方法，必須掌握工程設(shè)置，變量查看，單步執(zhí)行，插樁調(diào)試等這些最為基本的程序調(diào)試手段。

實(shí)驗(yàn)二單鏈表的插入和刪除一、目的：了解和掌握線性表的邏輯結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，掌握單鏈表的基本算法及相關(guān)的時間性能分析。二、要求：建立一個數(shù)據(jù)域定義為字符串的單鏈表，在鏈表中不允許有重復(fù)的字符串；根據(jù)輸入的字符串，先找到相應(yīng)的結(jié)點(diǎn)，后刪除之。三、示例程序：#include"stdio.h"#include"string.h"#include"stdlib.h"#include"ctype.h"typedefstructnode//定義結(jié)點(diǎn){ chardata[10];//結(jié)點(diǎn)的數(shù)據(jù)域?yàn)樽址?structnode*next;//結(jié)點(diǎn)的指針域}ListNode;typedefListNode*LinkList;//自定義LinkList單鏈表類型LinkListCreatListR1();//函數(shù)，用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表ListNode*LocateNode();//函數(shù)，按值查找結(jié)點(diǎn)voidDeleteList();//函數(shù)，刪除指定值的結(jié)點(diǎn)voidprintlist();//函數(shù)，打印鏈表中的所有值voidDeleteAll();//函數(shù)，刪除所有結(jié)點(diǎn)，釋放內(nèi)存//==========主函數(shù)==============voidmain(){char*ch,*num;LinkListhead;head=CreatListR1();//用尾插入法建立單鏈表，返回頭指針printlist(head);//遍歷鏈表輸出其值printf("Deletenode(y/n):");//輸入“y”或“n”去選擇是否刪除結(jié)點(diǎn)scanf("%s",num);if(strcmp(num,"y")==0||strcmp(num,"Y")==0){printf("PleaseinputDelete_data:"); scanf("%s",ch); //輸入要刪除的字符串DeleteList(head,ch); printlist(head);}DeleteAll(head);//刪除所有結(jié)點(diǎn)，釋放內(nèi)存}//==========用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表===========LinkListCreatListR1(void){char*ch;LinkListhead=(LinkList)malloc(sizeof(ListNode));//生成頭結(jié)點(diǎn)ListNode*s,*r,*pp;r=head;r->next=NULL;printf("Input#toend");//輸入“#”代表輸入結(jié)束printf("PleaseinputNode_data:");scanf("%s",ch);//輸入各結(jié)點(diǎn)的字符串while(strcmp(ch,"#")!=0){pp=LocateNode(head,ch);//按值查找結(jié)點(diǎn)，返回結(jié)點(diǎn)指針 if(pp==NULL){//沒有重復(fù)的字符串，插入到鏈表中 s=(ListNode*)malloc(sizeof(ListNode)); strcpy(s->data,ch); r->next=s; r=s; r->next=NULL;} printf("Input#toend"); printf("PleaseinputNode_data:"); scanf("%s",ch);}returnhead;//返回頭指針}//==========按值查找結(jié)點(diǎn)，找到則返回該結(jié)點(diǎn)的位置，否則返回NULL==========ListNode*LocateNode(LinkListhead,char*key){ListNode*p=head->next;//從開始結(jié)點(diǎn)比較while(strcmp(p->data,key)!=0&&p)//直到p為NULL或p-> data為key止 p=p->next;//掃描下一個結(jié)點(diǎn)returnp;//若p=NULL則查找失敗，否則p指向找到的值為key的結(jié)點(diǎn)}//==========刪除帶頭結(jié)點(diǎn)的單鏈表中的指定結(jié)點(diǎn)=======voidDeleteList(LinkListhead,char*key){ListNode*p,*r,*q=head;p=LocateNode(head,key);//按key值查找結(jié)點(diǎn)的if(p==NULL){//若沒有找到結(jié)點(diǎn)，退出 printf("positionerror"); exit(0);}while(q->next!=p)//p為要刪除的結(jié)點(diǎn)，q為p的前結(jié)點(diǎn) q=q->next;r=q->next;q->next=r->next;free(r);//釋放結(jié)點(diǎn)}//===========打印鏈表=======voidprintlist(LinkListhead){ListNode*p=head->next;//從開始結(jié)點(diǎn)打印while(p){ printf("%s,",p->data); p=p->next;}printf("\n");}//==========刪除所有結(jié)點(diǎn)，釋放空間===========voidDeleteAll(LinkListhead){ListNode*p=head,*r;while(p->next){ r=p->next; free(p); p=r;}free(p);}四、實(shí)驗(yàn)內(nèi)容分析、理解程序。調(diào)試程序，并設(shè)計(jì)輸入數(shù)據(jù)（如：bat，cat，eat，fat，hat，jat，lat，mat，#），測試程序的如下功能：不允許重復(fù)字符串的插入；根據(jù)輸入的字符串，找到相應(yīng)的結(jié)點(diǎn)并刪除。修改程序：(1)增加插入結(jié)點(diǎn)的功能。將建立鏈表的方法改為頭插入法。五、實(shí)驗(yàn)報告要求基本要求見第一頁內(nèi)容。寫出實(shí)驗(yàn)結(jié)果，并畫出所建鏈表的示意圖。六、附加實(shí)驗(yàn)內(nèi)容（詳細(xì)內(nèi)容略，請同學(xué)們自行找相關(guān)書籍進(jìn)行練習(xí)）線性表操作掌握線性表的幾種存儲結(jié)構(gòu)，掌握每種結(jié)構(gòu)的相應(yīng)算法。

實(shí)驗(yàn)三棧的實(shí)現(xiàn)一、目的：掌握棧的表示，實(shí)現(xiàn)及其針對棧的各種操作。二、要求：建立一個順序棧，用以實(shí)現(xiàn)任意數(shù)據(jù)的轉(zhuǎn)換。三、示例程序：下述程序演示了將數(shù)轉(zhuǎn)換成８進(jìn)制。使用了一個順序棧，實(shí)現(xiàn)了棧常用的基本操作。棧的應(yīng)用基本上基于這些方法實(shí)現(xiàn)的，此外，還有鏈棧，關(guān)于鏈棧的操作請同學(xué)們對應(yīng)寫出一個演示程序吧。#include"iostream.h"http://這里還要加入我們默認(rèn)的常量頭文件#include"head.h"#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefintSElemType;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;StatusInitStack(SqStack&S){S.base=newSElemType[STACK_INIT_SIZE];if(!S.base)returnOVERFLOW;S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}StatusDestroyStack(SqStack&S){S.top=NULL;S.base=NULL;delete[]S.base;S.stacksize=0;returnOK;}intStackEmpty(SqStacks){if(s.top==s.base)return1;elsereturn0;}StatusGetTop(SqStack&s,SElemType&e){if(s.top==s.base)returnERROR;e=*(s.top-1);returnOK;}intStackLength(SqStacks){returns.top-s.base;}StatusClearStack(SqStack&S){S.top=S.base;returnOK;}StatusPush(SqStack&s,SElemTypee){if(s.top-s.base>=s.stacksize)returnOVERFLOW;*s.top++=e;returnOK;}StatusPop(SqStack&s,SElemType&e){if(s.top==s.base)returnERROR;e=*--s.top;returnOK;}StatusStackTraverse(SqStacks,Status(*visit)(SElemTypec))//這個函數(shù)最好不要用，因?yàn)樗呀?jīng)破壞了棧的特性{while(s.top>s.base)visit(*s.base++);cout<<endl;returnOK;}Statusvisit(SElemTypec){cout<<c<<"";returnOK;}voidmain()//為進(jìn)制轉(zhuǎn)換的函數(shù){SqStackS;SElemTypeN;SElemTypee;InitStack(S);cout<<"inputthenumber:";cin>>N;while(N){Push(S,N%8);N=N/8;轉(zhuǎn)換為八進(jìn)制的數(shù)}while(!StackEmpty(S)){Pop(S,e);cout<<e;}cout<<endl;四、實(shí)驗(yàn)內(nèi)容分析、理解程序。編寫程序：完成對任意進(jìn)制的轉(zhuǎn)換完成檢查表達(dá)式括號匹配的算法五、實(shí)驗(yàn)報告要求基本要求見第一頁內(nèi)容。寫出實(shí)驗(yàn)結(jié)果，并畫出所建鏈表的示意圖。六、附加實(shí)驗(yàn)內(nèi)容（詳細(xì)內(nèi)容略，請同學(xué)們自行找相關(guān)書籍進(jìn)行練習(xí)）鏈棧的操作實(shí)現(xiàn)鏈棧的相應(yīng)操作算法。

實(shí)驗(yàn)四二叉樹操作實(shí)現(xiàn)一、目的：掌握二叉樹的定義、性質(zhì)及存儲方式，各種遍歷算法。二、要求：采用二叉樹鏈表作為存儲結(jié)構(gòu)，完成二叉樹的建立，先序、中序和后序以及按層次遍歷的操作，求所有葉子及結(jié)點(diǎn)總數(shù)的操作。三、示例程序：#include"stdio.h"#include"string.h"#defineMax20//結(jié)點(diǎn)的最大個數(shù)typedefstructnode{chardata;structnode*lchild,*rchild;}BinTNode;//自定義二叉樹的結(jié)點(diǎn)類型typedefBinTNode*BinTree;//定義二叉樹的指針intNodeNum,leaf;//NodeNum為結(jié)點(diǎn)數(shù)，leaf為葉子數(shù)//==========基于先序遍歷算法創(chuàng)建二叉樹==============//=====要求輸入先序序列，其中加入虛結(jié)點(diǎn)“#”以示空指針的位置==========BinTreeCreatBinTree(void){BinTreeT;charch;if((ch=getchar())=='#') return(NULL);//讀入#，返回空指針else{ T=(BinTNode*)malloc(sizeof(BinTNode));生成結(jié)點(diǎn) T->data=ch; T->lchild=CreatBinTree();//構(gòu)造左子樹 T->rchild=CreatBinTree();//構(gòu)造右子樹 return(T);}}//========NLR先序遍歷=============voidPreorder(BinTreeT){if(T){ printf("%c",T->data);//訪問結(jié)點(diǎn) Preorder(T->lchild);//先序遍歷左子樹 Preorder(T->rchild);//先序遍歷右子樹}}//========LNR中序遍歷===============voidInorder(BinTreeT){if(T){ Inorder(T->lchild);//中序遍歷左子樹 printf("%c",T->data);//訪問結(jié)點(diǎn) Inorder(T->rchild);//中序遍歷右子樹}}//==========LRN后序遍歷============voidPostorder(BinTreeT){if(T){ Postorder(T->lchild);//后序遍歷左子樹 Postorder(T->rchild);//后序遍歷右子樹 printf("%c",T->data);//訪問結(jié)點(diǎn)}}//=====采用后序遍歷求二叉樹的深度、結(jié)點(diǎn)數(shù)及葉子數(shù)的遞歸算法========intTreeDepth(BinTreeT){inthl,hr,max;if(T){ hl=TreeDepth(T->lchild); //求左深度 hr=TreeDepth(T->rchild);//求右深度 max=hl>hr?hl:hr;//取左右深度的最大值 NodeNum=NodeNum+1;//求結(jié)點(diǎn)數(shù) if(hl==0&&hr==0)leaf=leaf+1;//若左右深度為0，即為葉子。 return(max+1);}elsereturn(0);}//====利用“先進(jìn)先出”（FIFO）隊(duì)列，按層次遍歷二叉樹==========voidLevelorder(BinTreeT){intfront=0,rear=1;BinTNode*cq[Max],*p;//定義結(jié)點(diǎn)的指針數(shù)組cqcq[1]=T;//根入隊(duì)while(front!=rear){ front=(front+1)%NodeNum; p=cq[front];//出隊(duì) printf("%c",p->data);//出隊(duì)，輸出結(jié)點(diǎn)的值 if(p->lchild!=NULL){ rear=(rear+1)%NodeNum; cq[rear]=p->lchild;//左子樹入隊(duì) } if(p->rchild!=NULL){ rear=(rear+1)%NodeNum; cq[rear]=p->rchild;//右子樹入隊(duì) }}}//==========主函數(shù)=================voidmain(){BinTreeroot;inti,depth;printf("\n");printf("CreatBin_Tree；Inputpreorder:");//輸入完全二叉樹的先序序列，//用#代表虛結(jié)點(diǎn)，如ABD###CE##F##root=CreatBinTree();//創(chuàng)建二叉樹，返回根結(jié)點(diǎn)do{//從菜單中選擇遍歷方式，輸入序號。 printf("\t**********select************\n"); printf("\t1:PreorderTraversal\n"); printf("\t2:IorderTraversal\n"); printf("\t3:Postordertraversal\n"); printf("\t4:PostTreeDepth,Nodenumber,Leafnumber\n"); printf("\t5:LevelDepth\n");//按層次遍歷之前，先選擇4，求出該樹的結(jié)點(diǎn)數(shù)。 printf("\t0:Exit\n"); printf("\t*******************************\n"); scanf("%d",&i);//輸入菜單序號（0-5） switch(i){ case1:printf("PrintBin_treePreorder:"); Preorder(root);//先序遍歷 break; case2:printf("PrintBin_TreeInorder:"); Inorder(root);//中序遍歷 break; case3:printf("PrintBin_TreePostorder:"); Postorder(root);//后序遍歷 break; case4:depth=TreeDepth(root);//求樹的深度及葉子數(shù) printf("BinTreeDepth=%dBinTreeNodenumber=%d",depth,NodeNum); printf("BinTreeLeafnumber=%d",leaf); break; case5:printf("LevePrintBin_Tree:"); Levelorder(root);//按層次遍歷 break; default:exit(1); } printf("\n");}while(i!=0);}四、實(shí)驗(yàn)內(nèi)容分析、理解程序。調(diào)試程序，設(shè)計(jì)一棵二叉樹，輸入完全二叉樹的先序序列，用#代表虛結(jié)點(diǎn)（空指針），如ABD###CE##F##，建立二叉樹，求出先序、中序和后序以及按層次遍歷序列，求所有葉子及結(jié)點(diǎn)總數(shù)。五、實(shí)驗(yàn)報告要求基本要求見第一頁。畫出所設(shè)計(jì)的二叉樹，以后序遍歷算法為例，畫出執(zhí)行蹤跡示意圖。給出實(shí)驗(yàn)結(jié)果。

實(shí)驗(yàn)五哈夫曼樹的建立與編碼實(shí)現(xiàn)一、目的：掌握哈夫曼樹的表示，實(shí)現(xiàn)及其在編碼上的應(yīng)用。二、要求：建立一正文文件(本程序中建立的文件名文test.txt)，向其中輸入字符。通過哈夫曼算法求出文件中字符的相應(yīng)編碼。建立一與正文文件(test.txt)對應(yīng)的編碼文件（bainma.txt）三、示例程序：#include<stdio.h>#include<alloc.h>#include<conio.h>#include<stdlib.h>#include<string.h>/*聲明兩種鏈表結(jié)構(gòu)start*/structnode_a{/*鏈表1作用：用來統(tǒng)計(jì)文件中字符的個數(shù)和種類（通過count）*/chardata;intcount;structnode_a*next;};typedefstructnode_anode,*list;listhead=NULL;structnodeb{/*鏈表2作用：用來建立用相應(yīng)的編碼代替字符的新文件*/chardata;structnodeb*next;};typedefstructnodebnode_b,*list_b;/*jiangbianmaxieruwenjian*/list_bhead_b=NULL;/*聲明兩種鏈表結(jié)構(gòu)end*//*哈夫曼算法種相關(guān)的3種結(jié)構(gòu)的聲明start*/structforest{floatweight;introot;};structalphabet{charsymbol;floatprobability;intleaf;char*bianma;};structtree{intlchild;intrchild;intparent;};typedefstructtree*tree_ptr,tree_node;typedefstructforest*forest_ptr,forest_node;typedefstructalphabet*alphabet_ptr,alphabet_node;tree_ptrtree1;forest_ptrforest1;alphabet_ptralphabet1;intlasttree,lastnode;intleast,second;/*哈夫曼算法種相關(guān)的3種結(jié)構(gòu)的聲明end*//**************stackdifinationstart****************/structstacknode{char*bian_ma;structstacknode*next;};typedefstructstacknodestack_node;typedefstack_node*link;linktop=NULL;voidpush(char*item){linkp;if(top!=NULL){p=(link)malloc(sizeof(stack_node));if(p==NULL){printf("Memoryallocationerror!");return;}p->bian_ma=item;p->next=top;top=p;}else{top=(link)malloc(sizeof(stack_node));if(!top){printf("Memoryallocationerror!");return;}top->bian_ma=item;top->next=NULL;}}voidpop(void){linkp;p=top;top=top->next;free(p);}voidmakenull(void){while(top!=NULL)pop();}intempty(){if(top==NULL)return1;elsereturn0;}char*tops(void){return(top->bian_ma);}voiddisplay_stack(links){/*顯示棧重的內(nèi)容*/linkptr;ptr=s;while(ptr!=NULL){printf("%s",ptr->bian_ma);ptr=ptr->next;}}/***************stack__difinationisend**************/voiddisplay(listh){/*顯示鏈表1*/listptr;inti=1;ptr=h->next;while(ptr!=NULL){printf("%d,%c,%d\n",i,ptr->data,ptr->count);i++;ptr=ptr->next;}}voiddisplay_b(list_bh){/*顯示鏈表2*/list_bptr;inti=1;ptr=h->next;while(ptr!=NULL){printf("%d,%c\n",i,ptr->data);i++;ptr=ptr->next;}}voidinsert(charitem){/*用于插入元素以建立鏈表1*/listtemp,ptr;intflag;ptr=head->next;if(ptr==NULL){head->next=(list)malloc(sizeof(node));head->next->data=item;head->next->count=1;head->next->next=NULL;}else{while(ptr!=NULL){if(ptr->data==item){ptr->count=ptr->count+1;flag=1;}ptr=ptr->next;}ptr=head;if(flag==1)return;else{temp=ptr->next;ptr->next=(list)malloc(sizeof(node));ptr->next->data=item;ptr->next->count=1;ptr->next->next=temp;}}}voidinsert_b(charitem){/*插入元素以建立鏈表2*/list_bptr_b,temp_b;ptr_b=head_b;if(ptr_b->next==NULL){head_b->next=(list_b)malloc(sizeof(node_b));head_b->next->data=item;head_b->next->next=NULL;}else{while(ptr_b->next!=NULL){ptr_b=ptr_b->next;}ptr_b->next=(list_b)malloc(sizeof(node_b));ptr_b->next->data=item;ptr_b->next->next=NULL;}}voidsearch(void){/*搜索文件并將文件中的數(shù)據(jù)分別存入作用不同的鏈表中*/FILE*fp;listptr;charch;if((fp=fopen("test.txt","r"))==NULL)printf("Readingerror!\n");while(!feof(fp)){ch=getc(fp);if(ferror(fp)){printf("error!\n");break;}if(ch==EOF)break;insert(ch);/*插入元素進(jìn)鏈表1*/insert_b(ch);/*插入元素進(jìn)鏈表2*/}printf("\n");fclose(fp);}voiddisplay_struct(intn){/*顯示哈夫曼算法中的3個結(jié)構(gòu)樹組*/inti=0;printf("\n\n=======================================\n\n");printf("FOREST_STRUCT_ARRY:\n\n\n");for(i=0;i<=n;i++){printf("%f,%d\n",forest1[i].weight,forest1[i].root);}getch();printf("\n\nALPHABET_STRUCT_ARRY:\n\n\n");for(i=0;i<=n;i++){printf("%f,%d,%c\n",alphabet1[i].probability,alphabet1[i].leaf,alphabet1[i].symbol);}getch();printf("\n\nTREE_STRUCT_ARRY:\n\n\n");for(i=0;i<=2*n-1;i++)printf("%d,%d,%d\n",tree1[i].lchild,tree1[i].rchild,tree1[i].parent);printf("\n\n======================================\n\n");getch();}intinit_struct(void){/*初始化哈夫曼算法中3種結(jié)構(gòu)數(shù)組*/listptr;floatcount=.0;inti=1,n=0;ptr=head->next;while(ptr!=NULL){count=ptr->count+count;n++;ptr=ptr->next;}ptr=head->next;forest1=(forest_ptr)malloc(sizeof(forest_node)*n+sizeof(forest_node));alphabet1=(alphabet_ptr)malloc(sizeof(alphabet_node)*n+sizeof(alphabet_node));tree1=(tree_ptr)malloc(sizeof(tree_node)*n*2-sizeof(tree_node));forest1[0].weight=alphabet1[0].probability=0.0;forest1[0].root=alphabet1[0].leaf=0;alphabet1[0].symbol='0';while(ptr!=NULL){forest1[i].weight=alphabet1[i].probability=ptr->count/count;forest1[i].root=alphabet1[i].leaf=i;alphabet1[i].symbol=ptr->data;i++;ptr=ptr->next;}for(i=0;i<=2*n-1;i++){tree1[i].lchild=0;tree1[i].rchild=0;tree1[i].parent=0;}returnn;}voidcreat(void){/*創(chuàng)建正文文件test.txt*/FILE*fp,*out;charch;if((fp=fopen("test.txt","w+t"))==NULL)printf("Createrror!\n");printf("Inputthedata:\n");ch=getch();putch(ch);while(ch!='#'){putc(ch,fp);ch=getch();putch(ch);}fclose(fp);}voidcreat_bianma(intnumber){/*根據(jù)哈夫曼算法建立文件中各種字符對應(yīng)的編碼*/inti,j,n;intp;char*bm=malloc(sizeof(char)*number);for(n=1;n<=number;n++){j=i=n;makenull();p=tree1[i].parent;while(tree1[p].parent!=0){if(tree1[p].lchild==i)push("0");elsepush("1");i=p;p=tree1[p].parent;}if(tree1[p].lchild==i)push("0");elsepush("1");strcpy(bm,"");/*目的：使創(chuàng)建編碼文件中的各編碼中間存在間隔*/while(!empty()){strcat(bm,tops());pop();}alphabet1[j].bianma=malloc(sizeof(char)*number);strcpy(alphabet1[j].bianma,bm);printf("\n%c:%s",alphabet1[j].symbol,alphabet1[j].bianma);/*打印出相應(yīng)的編碼*/getch();}}voidwrite_new_file(intnumber){/*根據(jù)相應(yīng)的編碼重新建立編碼文件*/FILE*fp;list_bptr;inti;char*ch=malloc(sizeof(char)*number);ptr=head_b->next;if((fp=fopen("bianma.txt","w"))==NULL)printf("Writeinanewfileerror!");else{while(ptr!=NULL){for(i=1;i<=number;i++){if(ptr->data==alphabet1[i].symbol){strcpy(ch,alphabet1[i].bianma);fputs(ch,fp);}}ptr=ptr->next;}}fclose(fp);}voidmain(void){inti,num;charch;voidhuffman(void);voidlightones();head=(list)malloc(sizeof(node));head->next=NULL;head->data='';head->count=0;head_b=(list_b)malloc(sizeof(node_b));head_b->data='';head_b->next=NULL;do{system("cls");creat();search();printf("\nlianbiao1:\n");display(head);/*顯示鏈表1*/getch();printf("\nlianbiao2:\n");display_b(head_b);getch();num=init_struct();printf("\n");printf("The3init_structofhuffman?\n");display_struct(num);/*顯示初始化的哈夫曼書的相關(guān)3個結(jié)構(gòu)數(shù)組*/lastnode=num;lasttree=num;huffman();printf("Nowthe3structthroughhuffmanshuanfa\n");display_struct(num);/*顯示哈夫曼樹中相關(guān)的3種結(jié)構(gòu)（經(jīng)過哈夫曼算法處理）*/printf("\nThebian_mais:\n");creat_bianma(num);write_new_file(num);printf("\nDoyouwanttore_try(y/n)?");ch=getchar();}while(ch=='y');}/*哈夫曼算法defination_start*/voidlightones(void){inti;if(forest1[1].weight<=forest1[2].weight){least=1;second=2;}else{least=2;second=1;}for(i=3;i<=lasttree;i++)if(forest1[i].weight<forest1[least].weight){second=least;least=i;}elseif(forest1[i].weight<forest1[second].weight)second=i;}intcreat_tree(intlefttree,intrighttree){lastnode=lastnode+1;tree1[lastnode].lchild=forest1[lefttree].root;tree1[lastnode].rchild=forest1[righttree].root;tree1[lastnode].parent=0;tree1[forest1[lefttree].root].parent=lastnode;tree1[forest1[righttree].root].parent=lastnode;return(lastnode);}voidhuffman(void){inti,j;intnewroot;while(lasttree>1){lightones();i=least;j=second;newroot=creat_tree(i,j);forest1[i].weight=forest1[i].weight+forest1[j].weight;forest1[i].root=newroot;forest1[j]=forest1[lasttree];lasttree=lasttree-1;}}/*哈夫曼算法definationend*/四、實(shí)驗(yàn)內(nèi)容理解程序。編寫相應(yīng)的譯碼程序。五、實(shí)驗(yàn)報告要求略

實(shí)驗(yàn)六圖的遍歷操作一、目的：掌握有向圖和無向圖的概念；掌握鄰接矩陣和鄰接鏈表建立圖的存儲結(jié)構(gòu)；掌握DFS及BFS對圖的遍歷操作；二、要求：采用鄰接矩陣和鄰接鏈表作為圖的存儲結(jié)構(gòu)，完成有向圖和無向圖的DFS和BFS操作。三、示例程序：DFS和BFS的基本思想：深度優(yōu)先搜索法DFS的基本思想：從圖G中某個頂點(diǎn)Vo出發(fā)，首先訪問Vo，然后選擇一個與Vo相鄰且沒被訪問過的頂點(diǎn)Vi訪問，再從Vi出發(fā)選擇一個與Vi相鄰且沒被訪問過的頂點(diǎn)Vj訪問，……依次繼續(xù)。如果當(dāng)前被訪問過的頂點(diǎn)的所有鄰接頂點(diǎn)都已被訪問，則回退到已被訪問的頂點(diǎn)序列中最后一個擁有未被訪問的相鄰頂點(diǎn)的頂點(diǎn)W，從W出發(fā)按同樣方法向前遍歷。直到圖中所有的頂點(diǎn)都被訪問。廣度優(yōu)先算法BFS的基本思想：從圖G中某個頂點(diǎn)Vo出發(fā)，首先訪問Vo，然后訪問與Vo相鄰的所有未被訪問過的頂點(diǎn)V1，V2，……，Vt；再依次訪問與V1，V2，……，Vt相鄰的起且未被訪問過的的所有頂點(diǎn)。如此繼續(xù)，直到訪問完圖中的所有頂點(diǎn)。示例程序：鄰接矩陣作為存儲結(jié)構(gòu)的程序示例#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum100//定義最大頂點(diǎn)數(shù)typedefstruct{charvexs[MaxVertexNum];//頂點(diǎn)表intedges[MaxVertexNum][MaxVertexNum];//鄰接矩陣，可看作邊表intn,e;//圖中的頂點(diǎn)數(shù)n和邊數(shù)e}MGraph;//用鄰接矩陣表示的圖的類型//=========建立鄰接矩陣=======voidCreatMGraph(MGraph*G){inti,j,k;chara;printf("InputVertexNum(n)andEdgesNum(e):");scanf("%d,%d",&G->n,&G->e);//輸入頂點(diǎn)數(shù)和邊數(shù)scanf("%c",&a);printf("InputVertexstring:");for(i=0;i<G->n;i++){ scanf("%c",&a); G->vexs[i]=a;//讀入頂點(diǎn)信息，建立頂點(diǎn)表}for(i=0;i<G->n;i++) for(j=0;j<G->n;j++) G->edges[i][j]=0;//初始化鄰接矩陣printf("Inputedges,CreatAdjacencyMatrix\n");for(k=0;k<G->e;k++){//讀入e條邊，建立鄰接矩陣 scanf("%d%d",&i,&j);//輸入邊（Vi，Vj）的頂點(diǎn)序號 G->edges[i][j]=1; G->edges[j][i]=1;//若為無向圖，矩陣為對稱矩陣；若建立有向圖，去掉該條語句}}//=========定義標(biāo)志向量，為全局變量=======typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS：深度優(yōu)先遍歷的遞歸算法======voidDFSM(MGraph*G,inti){//以Vi為出發(fā)點(diǎn)對鄰接矩陣表示的圖G進(jìn)行DFS搜索，鄰接矩陣是0，1矩陣intj;printf("%c",G->vexs[i]);//訪問頂點(diǎn)Vivisited[i]=TRUE;//置已訪問標(biāo)志for(j=0;j<G->n;j++)//依次搜索Vi的鄰接點(diǎn) if(G->edges[i][j]==1&&!visited[j]) DFSM(G,j);//（Vi，Vj）∈E，且Vj未訪問過，故Vj為新出發(fā)點(diǎn)}voidDFS(MGraph*G){inti;for(i=0;i<G->n;i++) visited[i]=FALSE;//標(biāo)志向量初始化for(i=0;i<G->n;i++) if(!visited[i])//Vi未訪問過 DFSM(G,i);//以Vi為源點(diǎn)開始DFS搜索}//===========BFS：廣度優(yōu)先遍歷=======voidBFS(MGraph*G,intk){//以Vk為源點(diǎn)對用鄰接矩陣表示的圖G進(jìn)行廣度優(yōu)先搜索inti,j,f=0,r=0;intcq[MaxVertexNum];//定義隊(duì)列for(i=0;i<G->n;i++) visited[i]=FALSE; //標(biāo)志向量初始化for(i=0;i<G->n;i++) cq[i]=-1;//隊(duì)列初始化printf("%c",G->vexs[k]);//訪問源點(diǎn)Vkvisited[k]=TRUE;cq[r]=k;//Vk已訪問，將其入隊(duì)。注意，實(shí)際上是將其序號入隊(duì)while(cq[f]!=-1){//隊(duì)非空則執(zhí)行 i=cq[f];f=f+1;//Vf出隊(duì) for(j=0;j<G->n;j++)//依次Vi的鄰接點(diǎn)Vj if(G->edges[i][j]==1&&!visited[j]){//Vj未訪問 printf("%c",G->vexs[j]);//訪問Vj visited[j]=TRUE;

r=r+1;cq[r]=j;//訪問過Vj入隊(duì) }}}//==========main====