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

數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)報(bào)告所在院系：班號(hào)：學(xué)號(hào)：專(zhuān)業(yè)：姓名：指導(dǎo)老師：二零一三年六月目錄1一元多項(xiàng)式計(jì)算 21.1基本算法： 21.1.1輸入輸出 21.1.2多項(xiàng)式的加法 21.1.3多項(xiàng)式的減法 31.2程序： 41.3運(yùn)行結(jié)果： 82設(shè)計(jì)一個(gè)模擬計(jì)算器的程序 82.1設(shè)計(jì)思路 82.2功能模塊： 92.3程序： 92.4測(cè)試結(jié)果： 163學(xué)生成績(jī)查詢(xún)系統(tǒng) 163.1設(shè)計(jì)思路 163.2系統(tǒng)流程圖： 173.3程序： 173.4測(cè)試結(jié)果： 204構(gòu)造n個(gè)城市連接的最小生成樹(shù) 204.1設(shè)計(jì)思路 214.2數(shù)據(jù)結(jié)構(gòu)定義 214.3系統(tǒng)功能模塊 224.4運(yùn)行結(jié)果： 225哈夫曼編碼的應(yīng)用 235.1問(wèn)題分析哈夫曼樹(shù)的定義 235.2功能模塊圖 245.3程序： 245.4測(cè)試結(jié)果： 306實(shí)習(xí)總結(jié)： 301一元多項(xiàng)式計(jì)算

能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式；能夠完成兩個(gè)多項(xiàng)式的相加、相減和相乘，并將結(jié)果輸出。1.1基本算法：1.1.1輸入輸出（1）功能：將要進(jìn)行運(yùn)算的多項(xiàng)式輸入輸出。（2）數(shù)據(jù)流入：要輸入的多項(xiàng)式的系數(shù)與指數(shù)。（3）數(shù)據(jù)流出：合并同類(lèi)項(xiàng)后的多項(xiàng)式。（4）程序流程圖：多項(xiàng)式輸入流程圖如圖1所示。（5）測(cè)試要點(diǎn)：輸入的多項(xiàng)式是否正確，若輸入錯(cuò)誤則重新輸入流程圖：1.1.2多項(xiàng)式的加法（1）功能：將兩多項(xiàng)式相加。（2）數(shù)據(jù)流入：輸入函數(shù)。（3）數(shù)據(jù)流出：多項(xiàng)式相加后的結(jié)果。（4）程序流程圖：多項(xiàng)式的加法流程圖如圖2所示。（5）測(cè)試要點(diǎn)：兩多項(xiàng)式是否為空，為空則提示重新輸入，否則，進(jìn)行運(yùn)算。流程圖：1.1.3多項(xiàng)式的減法（1）功能：將兩多項(xiàng)式相減。（2）數(shù)據(jù)流入：調(diào)用輸入函數(shù)。（3）數(shù)據(jù)流出：多項(xiàng)式相減后的結(jié)果。（4）程序流程圖：多項(xiàng)式的減法流程圖如圖3所示。（5）測(cè)試要點(diǎn)：兩多項(xiàng)式是否為空，為空則提示重新輸入，否則，進(jìn)行運(yùn)算。流程圖：1.2程序：#include"stdafx.h"#include<stdio.h>#include<malloc.h>typedefstructPolynomial{floatcoef;intexpn;structPolynomial*next;}*Polyn,Polynomial;//Polyn為結(jié)點(diǎn)指針類(lèi)型voidInsert(Polynp,Polynh){if(p->coef==0)free(p);//系數(shù)為0的話釋放結(jié)點(diǎn)else{Polynq1,q2;q1=h;q2=h->next;while(q2&&p->expn<q2->expn){//查找插入位置q1=q2;q2=q2->next;}if(q2&&p->expn==q2->expn){//將指數(shù)相同相合并q2->coef+=p->coef;free(p);if(!q2->coef){//系數(shù)為0的話釋放結(jié)點(diǎn)q1->next=q2->next;free(q2);}}else{//指數(shù)為新時(shí)將結(jié)點(diǎn)插入p->next=q2;q1->next=p;}}}//InsertPolynCreatePolyn(Polynhead,intm){//建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial));head->next=NULL;for(i=0;i<m;i++){p=(Polyn)malloc(sizeof(structPolynomial));//建立新結(jié)點(diǎn)以接收數(shù)據(jù)printf("請(qǐng)輸入第%d項(xiàng)的系數(shù)與指數(shù):",i+1);scanf("%f%d",&p->coef,&p->expn);Insert(p,head);//調(diào)用Insert函數(shù)插入結(jié)點(diǎn)}returnhead;}//CreatePolynvoidDestroyPolyn(Polynp){//銷(xiāo)毀多項(xiàng)式pPolynq1,q2;q1=p->next;q2=q1->next;while(q1->next){free(q1);q1=q2;//指針后移q2=q2->next;}}voidPrintPolyn(PolynP){Polynq=P->next;intflag=1;//項(xiàng)數(shù)計(jì)數(shù)器if(!q){//若多項(xiàng)式為空，輸出0putchar('0');printf("\n");return;}while(q){if(q->coef>0&&flag!=1)putchar('+');//系數(shù)大于0且不是第一項(xiàng)if(q->coef!=1&&q->coef!=-1){//系數(shù)非1或-1的普通情況printf("%g",q->coef);if(q->expn==1)putchar('X');elseif(q->expn)printf("X^%d",q->expn);}else{if(q->coef==1){if(!q->expn)putchar('1');elseif(q->expn==1)putchar('X');elseprintf("X^%d",q->expn);}if(q->coef==-1){if(!q->expn)printf("-1");elseif(q->expn==1)printf("-X");elseprintf("-X^%d",q->expn);}}q=q->next;flag++;}//whileprintf("\n");}//PrintPolynintcompare(Polyna,Polynb){if(a&&b){if(!b||a->expn>b->expn)return1;elseif(!a||a->expn<b->expn)return-1;elsereturn0;}elseif(!a&&b)return-1;//a多項(xiàng)式已空，但b多項(xiàng)式非空elsereturn1;//b多項(xiàng)式已空，但a多項(xiàng)式非空}//comparePolynAddPolyn(Polynpa,Polynpb){//求解并建立多項(xiàng)式a+b，返回其頭指針Polynqa=pa->next;Polynqb=pb->next;Polynheadc,hc,qc;hc=(Polyn)malloc(sizeof(structPolynomial));//建立頭結(jié)點(diǎn)hc->next=NULL;headc=hc;while(qa||qb){qc=(Polyn)malloc(sizeof(structPolynomial));switch(compare(qa,qb)){case1:{qc->coef=qa->coef;qc->expn=qa->expn;qa=qa->next;break;}case0:{qc->coef=qa->coef+qb->coef;qc->expn=qa->expn;qa=qa->next;qb=qb->next;break;}case-1:{qc->coef=qb->coef;qc->expn=qb->expn;qb=qb->next;break;}}//switchif(qc->coef!=0){qc->next=hc->next;hc->next=qc;hc=qc;}elsefree(qc);//當(dāng)相加系數(shù)為0時(shí)，釋放該結(jié)點(diǎn)}//whilereturnheadc;}//AddPolynPolynSubtractPolyn(Polynpa,Polynpb){//求解并建立多項(xiàng)式a+b，返回其頭指針Polynh=pb;Polynp=pb->next;Polynpd;while(p){//將pb的系數(shù)取反p->coef*=-1;p=p->next;}pd=AddPolyn(pa,h);for(p=h->next;p;p=p->next)//恢復(fù)pb的系數(shù)p->coef*=-1;returnpd;}//SubtractPolynintmain(){intm,n,flag=0;floatx;Polynpa=0,pb=0,pc,pd,pe,pf;//定義各式的頭指針，pa與pb在使用前付初值NULLprintf("請(qǐng)輸入a的項(xiàng)數(shù):");scanf("%d",&m);pa=CreatePolyn(pa,m);//建立多項(xiàng)式aprintf("請(qǐng)輸入b的項(xiàng)數(shù):");scanf("%d",&n);pb=CreatePolyn(pb,n);//建立多項(xiàng)式a//輸出菜單printf("**********************************************\n");printf("操作提示：\n\t1.輸出多項(xiàng)式a和b\n\t2.建立多項(xiàng)式a+b\n\t3.建立多項(xiàng)式a-b\n");printf("\t4.退出\n**********************************************\n");for(;;flag=0){printf("執(zhí)行操作：");scanf("%d",&flag);if(flag==1){printf("多項(xiàng)式a：");PrintPolyn(pa);printf("多項(xiàng)式b：");PrintPolyn(pb);continue;}if(flag==2){pc=AddPolyn(pa,pb);printf("多項(xiàng)式a+b：");PrintPolyn(pc);DestroyPolyn(pc);continue;}if(flag==3){pd=SubtractPolyn(pa,pb);printf("多項(xiàng)式a-b：");PrintPolyn(pd);DestroyPolyn(pd);continue;}if(flag==4)break;if(flag<1||flag>4)printf("Error!!!\n");continue;}//forDestroyPolyn(pa);DestroyPolyn(pb);return0;}1.3運(yùn)行結(jié)果：2設(shè)計(jì)一個(gè)模擬計(jì)算器的程序

要求對(duì)包含加、減、乘、除、括號(hào)運(yùn)算符的任意整型表達(dá)式進(jìn)行求解。2.1設(shè)計(jì)思路表達(dá)式：任何表達(dá)式都是由操作數(shù)、運(yùn)算符和界限符組成的有意義的式子。 表達(dá)式求值時(shí)一般有后綴表示、中綴表示、前綴表示。操作數(shù)：可以是常數(shù)、變量、常量。運(yùn)算符：從運(yùn)算對(duì)象上分有單目運(yùn)算符、雙目運(yùn)算符、三目運(yùn)算符。界限符：左右括號(hào)和表達(dá)式結(jié)束符。思路：我們平時(shí)用到的表達(dá)式即為我們所輸入的表達(dá)式（以‘#’結(jié)束），此表達(dá)式為中綴表達(dá)式，只要將此表達(dá)式利用棧來(lái)進(jìn)出運(yùn)算的符號(hào)轉(zhuǎn)換為后綴表達(dá)式，之后利用棧來(lái)進(jìn)出運(yùn)算的數(shù)字將后綴表達(dá)式的值求出即可。2.2功能模塊：判斷字符是否為操作數(shù)函數(shù)intisnum(char)

當(dāng)輸入表達(dá)式時(shí)要利用棧對(duì)表達(dá)式中的數(shù)字和符號(hào)進(jìn)行進(jìn)棧出棧，因此要判斷表達(dá)式中的內(nèi)容是操作數(shù)、運(yùn)算符還是界限符，給出相關(guān)信息。求運(yùn)算符優(yōu)先級(jí)函數(shù)intpriority(char)

對(duì)輸入的表達(dá)式中的內(nèi)容，若為運(yùn)算符和界限符則要判斷其優(yōu)先級(jí)已完成其計(jì)算的先后順序。中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式函數(shù)intinfix_exp_value(char*,char*)

我們平時(shí)使用的為中綴表達(dá)式，但若利用棧則利用后綴表達(dá)式比較容易計(jì)算，因此要將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，具體算法步驟如下：

<1>count=0，初始化運(yùn)算符棧s，將結(jié)束符‘#’加入運(yùn)算符棧s中。

<2>讀表達(dá)式字符=>w。

<3>當(dāng)棧頂為‘#’并且w也是‘#’時(shí)結(jié)束；否則循環(huán)做下列步驟：

<3.1>如果w是操作數(shù)判斷若count==0直接輸出,讀下一個(gè)字符=>w;轉(zhuǎn)<3>。若count!=0追加字符’@’,讀下一個(gè)字符=>w,轉(zhuǎn)<3>。

<3.2>w若是運(yùn)算符，則：count=1;

<3.2.1>如果棧頂為‘（’并且w為‘）’則‘（’出棧不輸出，讀下一個(gè)字

符=>w，轉(zhuǎn)<3>。

<3.2.1>如果棧頂為‘（’或者棧頂優(yōu)先級(jí)小于w優(yōu)先級(jí)，則w入棧，讀下

一個(gè)字符=>w，轉(zhuǎn)<3>。否則：從運(yùn)算符棧中出棧并輸出，轉(zhuǎn)<3>后綴表達(dá)式的求值函數(shù)doublepostfix_exp(char*)

使用一個(gè)操作數(shù)棧，當(dāng)從左到右掃描表達(dá)式時(shí)，每遇到一個(gè)操作數(shù)就送入棧中保存，

如果操作數(shù)不止一位，則保存在operand中，遇到下一個(gè)操作數(shù)時(shí)，執(zhí)行operand=operand*10+(ch-'0')，便可將操作數(shù)轉(zhuǎn)化為數(shù)字。每遇到一個(gè)運(yùn)算符就從棧中取出兩個(gè)操作數(shù)進(jìn)行當(dāng)前的計(jì)算，然后把結(jié)果在入棧，直到整個(gè)表達(dá)式結(jié)束，這時(shí)送入棧頂?shù)闹稻褪墙Y(jié)果。2.3程序：#include"stdafx.h"#include<stdio.h>#include<malloc.h>#include<conio.h>#definemaxsize100typedefdoubledatatype1;typedefchardatatype2;typedefstructstack1{datatype1data1[maxsize];inttop1; /*棧頂元素*/}seqstack1,*pseqstack1;/*順序棧*/typedefstructstack2{datatype2data2[maxsize];inttop2; /*棧頂元素*/}seqstack2,*pseqstack2;/*順序棧*//*棧的初始化*/pseqstack1init_seqstack1(void){pseqstack1S;S=(pseqstack1)malloc(sizeof(pseqstack1));if(S)S->top1=-1;returnS;}pseqstack2init_seqstack2(void){pseqstack2S;S=(pseqstack2)malloc(sizeof(pseqstack2));if(S)S->top2=-1;returnS;}/*判斷?？?/intempty_seqstack1(pseqstack1S){if(S->top1==-1)return1;elsereturn0;}intempty_seqstack2(pseqstack2S){if(S->top2==-1)return1;elsereturn0;}/*X入棧*/intpush_seqstack1(pseqstack1S,datatype1X){if(S->top1==maxsize-1){printf("棧滿，無(wú)法入棧！\n");return0;}else{S->top1++;S->data1[S->top1]=X;return1; }}intpush_seqstack2(pseqstack2S,datatype2X){if(S->top2==maxsize-1){printf("棧滿，無(wú)法入棧！\n");return0;}else{S->top2++;S->data2[S->top2]=X;return1; }}/*X出棧*/intpop_seqstack1(pseqstack1S,datatype1*X){if(empty_seqstack1(S))return0;else{*X=S->data1[S->top1];S->top1--;return1; }}intpop_seqstack2(pseqstack2S,datatype2*X){if(empty_seqstack2(S))return0;else{*X=S->data2[S->top2];S->top2--;return1; }}/*求棧頂元素*/intgettop_seqstack1(pseqstack1S,datatype1*X){if(empty_seqstack1(S))return0;else*X=S->data1[S->top1];return1; }intgettop_seqstack2(pseqstack2S,datatype2*X){if(empty_seqstack2(S))return0;else*X=S->data2[S->top2];return1; }/*判斷字符是否為操作數(shù)。若是返回1，否則返回0*/intisnum(charc){if(c>='0'&&c<='9')return1;elsereturn0;}/*求后綴表達(dá)式的值*/doublepostfix_exp(char*A){pseqstack1S; /*定義棧S*/ doubleoperand=0;doubleresult; /*存放棧頂元素*/ doublea; /*運(yùn)算符ch前的操作數(shù)出棧存入a*/ doubleb; /*運(yùn)算符ch后的操作數(shù)出棧存入b*/ doublec; /*c==achb*/charch; /*存放讀取到的表達(dá)式(A)的字符*/ch=*A++; /*讀表達(dá)式字符=>A*/S=init_seqstack1(); /*初始化棧*/while(ch!='#')/*遇到元素!='#'時(shí)*/{if(isnum(ch))/*判斷ch是否為數(shù)字字符,計(jì)算出操作數(shù)*/operand=operand*10+(ch-'0');else /*否則*/ { if(operand) { push_seqstack1(S,operand);/*當(dāng)前字符不是數(shù)字,操作數(shù)結(jié)束,要入棧*/ operand=0; } if(ch!='@'&&ch!='') { pop_seqstack1(S,&b); /*運(yùn)算符ch后的操作數(shù)出棧存入b*/ pop_seqstack1(S,&a); /*運(yùn)算符ch前的操作數(shù)出棧存入a*/ switch(ch) /*求achb==?,將結(jié)果賦給c*/ { case'+': c=a+b; break; case'-': c=a-b; break; case'*': c=a*b; break; case'/': if(b!=0) c=a/b; else printf("分母為零!"); } push_seqstack1(S,c); /*將c壓入棧中*/ } }ch=*A++; /*指針向下移動(dòng)一位*/}/*遇到'#'循環(huán)結(jié)束*/gettop_seqstack1(S,&result);/*此時(shí)棧頂元素即為計(jì)算結(jié)果result*/returnresult;}/*優(yōu)先級(jí)判斷函數(shù)*/intpriority(charop){ switch(op) { case'#':return1; case')':return2; case'+': case'-':return3; case'*': case'/':return4; case'(':return5; default:return0; } }/*將指針infixexp指向的中綴表達(dá)式轉(zhuǎn)換為指針postfixexp指向的后綴表達(dá)式*/intinfix_exp_value(char*infixexp,char*postfixexp){ pseqstack2S; /*定義棧S*/ intcount=0; charw; /*存放讀取到的表達(dá)式(infixexp)的字符*/ charc; /*存放棧頂元素*/ chartopelement;/*存出棧元素*/ S=init_seqstack2(); /*初始化棧*/ if(!S) /*棧的初始化判斷*/ { printf("棧初始化失敗!"); return0; } push_seqstack2(S,'#'); /*將結(jié)束符'#'加入運(yùn)算符棧S中*/ w=*infixexp; /*讀表達(dá)式字符=>w*/ while((gettop_seqstack2(S,&c),c)!='#'||w!='#')/*<3>棧頂元素不等于'#'或w不等于'#'時(shí)循環(huán)*/ { if(isnum(w))/*判斷w是否為操作數(shù),若是直接輸出,讀下一個(gè)字符=>w,轉(zhuǎn)<3>*/ { if(count) { *postfixexp='@'; postfixexp++; count=0; } *postfixexp=w; postfixexp++; w=*(++infixexp); } else /*w若是運(yùn)算符分類(lèi)如下*/ { count=1; if((gettop_seqstack2(S,&c),c)=='('&&w==')') {/*如果棧頂為'('并且w為')'則'('出棧不輸出,讀下一個(gè)字符=>w,轉(zhuǎn)<3>*/ pop_seqstack2(S,&topelement);/*將'('出棧存入topelement*/ w=*(++infixexp); } else if((gettop_seqstack2(S,&c),c)=='('||priority((gettop_seqstack2(S,&c),c))<priority(w)) {/*如果棧頂為'('或者棧頂優(yōu)先級(jí)小于w優(yōu)先級(jí),則w入棧,讀下一個(gè)字符=>w，轉(zhuǎn)<3>*/ push_seqstack2(S,w); w=*(++infixexp); } else/*否則*/ {/*從運(yùn)算符棧中出棧并輸出,轉(zhuǎn)<3>*/ pop_seqstack2(S,&topelement); *postfixexp=topelement; postfixexp++; } } } *postfixexp='#';/*在指針postfixexp指向的后綴表達(dá)式結(jié)尾追加字符'#'*/ *(++postfixexp)='\0';/*在指針postfixexp指向的后綴表達(dá)式最后追加結(jié)束符'\0'*/ return1;}/*主函數(shù)*/intmain(){ inti=0; charA[maxsize]; charB[maxsize]; printf("請(qǐng)輸入表達(dá)式,如:45+36#,必須以#號(hào)結(jié)尾!\n"); A[i]=getchar(); while(A[i++]!='#') { A[i]=getchar(); } A[i]='\0'; infix_exp_value(A,B); printf("A==%s\n",A); printf("B==%s\n",B); printf("上式的結(jié)果為:"); printf("%g\n",postfix_exp(B)); return0;getch();}2.4測(cè)試結(jié)果：1）輸入11+（9-3）*（8/2）#2)輸入3+(1/8)*(16-7)#3學(xué)生成績(jī)查詢(xún)系統(tǒng)

按學(xué)號(hào)排序后對(duì)學(xué)號(hào)進(jìn)行折半查找。隨機(jī)輸入以學(xué)號(hào)為關(guān)鍵字的學(xué)生信息并構(gòu)建二叉排序樹(shù)，對(duì)學(xué)號(hào)進(jìn)行二叉排序樹(shù)查找。3.1設(shè)計(jì)思路這個(gè)程序主要是實(shí)現(xiàn)按學(xué)號(hào)對(duì)8名學(xué)生的信息進(jìn)行查找，其中查找方式分為三種：順序查找、折半查找、二叉排序樹(shù)查找。由于順序查找、折半查找很容易實(shí)現(xiàn)，而二叉排序樹(shù)查找需要構(gòu)建二叉排序樹(shù)，再進(jìn)行二叉排序樹(shù)查找，所以在這一步驟上有點(diǎn)難度。學(xué)生信息包括序號(hào)、姓名、成績(jī)，其中學(xué)號(hào)和姓名都是由字符實(shí)現(xiàn)，成績(jī)由整形實(shí)現(xiàn)。在輸入學(xué)生信息時(shí)直接按學(xué)號(hào)順序輸入，這樣便省去了在程序中對(duì)學(xué)生的學(xué)號(hào)從新進(jìn)行排序，在二叉排序樹(shù)的查找過(guò)程中，只能查找那些參與構(gòu)建二叉排序樹(shù)的學(xué)號(hào)，二叉排序樹(shù)是以第一個(gè)輸入的學(xué)生學(xué)號(hào)為根結(jié)點(diǎn)構(gòu)造二叉排序樹(shù)的。3.2系統(tǒng)流程圖：3.3程序：#include"stdafx.h"#include<stdio.h>#include<string.h>#include<stdlib.h>typedefstruct{ charsno[11]; //學(xué)號(hào) charname[16]; //姓名 intscore; //成績(jī)}student;typedefstructBinSTreeNode{ charhao[11]; charming[16]; intfen; structBinSTreeNode*lchild; structBinSTreeNode*rchild;}*BTree;intshun_search(studentstu[],intn,charx[]){ inti,j; for(i=0;i<n;i++) if(strcmp(stu[i].sno,x)==0) { printf("所查找的學(xué)生信息如下：\n學(xué)號(hào)\t姓名\t成績(jī)\n"); printf("%s%s%d",stu[i].sno,stu[i].name,stu[i].score); return0; } }intzhe_search(studentstu[],intn,charx[]){ intlow,mid,high; low=0;high=n-1; while(low<=high) { mid=(low+high)/2; if(strcmp(stu[mid].sno,x)==0) { printf("所查找的學(xué)生信息如下：\n學(xué)號(hào)\t姓名\t成績(jī)\n"); printf("%s%s%d",stu[mid].sno,stu[mid].name,stu[mid].score); return0; } elseif(strcmp(stu[mid].sno,x)>0)high=mid-1; elselow=mid+1; } return0;}voidBSTree(BTree*t,studentk){ BTreer; if(*t==NULL) { r=(BTree)malloc(sizeof(structBinSTreeNode)); strcpy(r->hao,k.sno); strcpy(r->ming,); r->fen=k.score; r->lchild=r->rchild=NULL; *t=r; return; }else if(strcmp(k.sno,((*t)->ming))<=0) BSTree(&((*t)->lchild),k); else BSTree(&((*t)->rchild),k);}BTreeBSTreeSearch(BTreet,charx[]){ if(t==NULL)returnNULL; if(strcmp(t->hao,x)==0)returnt; if(strcmp(t->hao,x)>=0) returnBSTreeSearch(t->lchild,x); else returnBSTreeSearch(t->rchild,x);}main(){ studentstu[40]; inti,j,k,n,b; charx[12]; printf("\n\t學(xué)生成績(jī)查詢(xún)系統(tǒng)\n\n"); printf("請(qǐng)輸入本次統(tǒng)計(jì)的學(xué)生數(shù)："); scanf("%d",&n); printf("\n請(qǐng)輸入這些學(xué)生的信息：\n"); printf("\t學(xué)號(hào)\t姓名成績(jī)\n"); for(i=0;i<n;i++) { printf("學(xué)生%d",i+1); scanf("%s%s%d",&stu[i].sno,&stu[i].name,&stu[i].score); } printf("信息輸入完畢...\n\n"); printf("請(qǐng)輸入你需要查找的學(xué)生號(hào)："); scanf("%s",x); printf("\n下面進(jìn)行順序查找:\n"); shun_search(stu,n,x); printf("\n\n下面進(jìn)行折半查找:\n"); zhe_search(stu,n,x); printf("\n\n下面進(jìn)行二叉排序樹(shù)的查找"); printf("\n輸入構(gòu)造二叉樹(shù)學(xué)號(hào)的個(gè)數(shù)："); scanf("%d",&b); BTreeT; T=(BTree)malloc(sizeof(structBinSTreeNode)); T=NULL; for(i=0;i<b;i++) { printf("輸入你的第%i學(xué)號(hào)：",i+1); scanf("%s",x); for(j=0;j<n;j++) if(strcmp(stu[j].sno,x)==0) k=j; BSTree(&T,stu[k]); } printf("信息輸入完畢...\n"); printf("二叉排序樹(shù)構(gòu)建成功...\n"); printf("\n輸入你想要在此二叉排序樹(shù)中查找的學(xué)號(hào)："); scanf("%s",x); BTrees; s=(BTree)malloc(sizeof(structBinSTreeNode)); s=BSTreeSearch(T,x); printf("所查找的學(xué)生信息如下：\n學(xué)號(hào)\t姓名\t成績(jī)\n"); printf("%s%s%d\n\n",s->hao,s->ming,s->fen); }3.4測(cè)試結(jié)果：4構(gòu)造n個(gè)城市連接的最小生成樹(shù)

一個(gè)地區(qū)的n個(gè)城市間的距離網(wǎng)，用Prim算法或Kruskal算法建立最小生成樹(shù)，并計(jì)算得到的最小生成樹(shù)的代價(jià)。基本要求：

1)城市間的距離網(wǎng)采用鄰接矩陣表示，鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義采用課本中給出的定義，若兩個(gè)城市之間不存在道路，則將相應(yīng)邊的權(quán)值設(shè)為自己定義的無(wú)窮大值。要求在屏幕上顯示得到的最小生成樹(shù)中包括了哪些城市間的道路，并顯示得到的最小生成樹(shù)的代價(jià)。2)表示城市間距離網(wǎng)的鄰接矩陣(要求至少6個(gè)城市，10條邊)4.1設(shè)計(jì)思路本程序需要實(shí)現(xiàn)在一個(gè)具有權(quán)值的n個(gè)城市間的有向距離網(wǎng)中，通過(guò)調(diào)用函數(shù)建立最小生成樹(shù)，并通過(guò)計(jì)算求得各個(gè)城市之間最小的權(quán)值。在設(shè)計(jì)程序時(shí)通過(guò)gnodevalue數(shù)組直接對(duì)各個(gè)城市之間的信息進(jìn)行設(shè)置，而不是手動(dòng)輸入。城市的個(gè)數(shù)也默認(rèn)設(shè)置為6個(gè)，路的個(gè)數(shù)也只設(shè)置成十個(gè)，所以在程序運(yùn)行時(shí)不需要輸入城市的相關(guān)信息。由于能力不足，在最后打印兩個(gè)城市之間最短路徑時(shí)，只顯示路徑所經(jīng)過(guò)的頂點(diǎn)，而不是一次經(jīng)過(guò)的頂點(diǎn)。4.2數(shù)據(jù)結(jié)構(gòu)定義本程序的主要內(nèi)容是通過(guò)函數(shù)調(diào)用構(gòu)建最小生成樹(shù)，實(shí)現(xiàn)求的兩個(gè)城市之間的最短路徑，并通過(guò)函數(shù)調(diào)用打印出來(lái)最短路徑所經(jīng)過(guò)的頂點(diǎn)，所有本程序便定義了三個(gè)結(jié)構(gòu)體，每個(gè)結(jié)構(gòu)體的作用如下所示。以及這六個(gè)城市和十條邊的圖也在下面顯示出來(lái)：typedefcharvertextype[7];typedefcharinfoptr;typedefintvrtype;typedefenum{DG,DN,UG,UN}graphkind;typedefstruct{ vrtypeadj; //對(duì)于無(wú)權(quán)圖，用1表示相鄰，0表示不相鄰，對(duì)于帶權(quán)圖，存儲(chǔ)權(quán)值 infoptr*info; //與弧或邊的相關(guān)信息}arcnode,adjmatrix[max][max];typedefstruct //圖的類(lèi)型定義{ vertextypevex[max]; //用于存儲(chǔ)頂點(diǎn) adjmatrixarc; //鄰接矩陣、存儲(chǔ)邊或弧的信息 intvexnum,arcnum; //頂點(diǎn)數(shù)和邊（弧）的數(shù)目 graphkindkind; //圖的類(lèi)型}mgraph;typedefstruct{ //添加一個(gè)存儲(chǔ)網(wǎng)的行、列和權(quán)值的類(lèi)型定義 introw; intcol; intweight;}gnode;4.3系統(tǒng)功能模塊4.4運(yùn)行結(jié)果：5哈夫曼編碼的應(yīng)用（1）哈夫曼樹(shù)的建立哈夫曼編碼的生成編碼文件的譯碼5.1問(wèn)題分析哈夫曼樹(shù)的定義1.哈夫曼樹(shù)節(jié)點(diǎn)的數(shù)據(jù)類(lèi)型定義為：typedefstruct{//赫夫曼樹(shù)的結(jié)構(gòu)體 charch; intweight;//權(quán)值 intparent,lchild,rchild;}htnode,*hfmtree;2）所實(shí)現(xiàn)的功能函數(shù)如下1、voidhfmcoding(hfmtree&HT,hfmcode&HC,intn)初始化哈夫曼樹(shù)，處理InputHuffman(HuffmanHfm)函數(shù)得到的數(shù)據(jù)，按照哈夫曼規(guī)則建立2叉樹(shù)。此函數(shù)塊調(diào)用了Select（）函數(shù)。voidSelect(hfmtree&HT,inta,int*p1,int*p2)//Select函數(shù)，選出HT樹(shù)到a為止，權(quán)值最小且parent為0的2個(gè)節(jié)點(diǎn)2、intmain()主函數(shù)：利用已建好的哈夫曼樹(shù)（如不在內(nèi)存，則從文件hfmtree.txt中讀入）對(duì)文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile.txt中。如果正文中沒(méi)有要編碼的字符，則鍵盤(pán)讀入并存儲(chǔ)到ToBeTran文件中。讀入ToBeTran中將要編碼的內(nèi)容，將編碼好的哈夫曼編碼存儲(chǔ)到CodeFile中。3、Encoding編碼功能：對(duì)輸入字符進(jìn)行編碼4、Decoding譯碼功能：利用已建好的哈夫曼樹(shù)將文件codefile.txt中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile.dat中。Print()打印功能函數(shù)：輸出哈夫曼樹(shù)，字符，權(quán)值，以及它對(duì)應(yīng)的編碼。5.主函數(shù)的簡(jiǎn)要說(shuō)明，主函數(shù)主要設(shè)計(jì)的是一個(gè)分支語(yǔ)句，讓用戶挑選所實(shí)現(xiàn)的功能。使用鏈樹(shù)存儲(chǔ)，然后分別調(diào)用統(tǒng)計(jì)頻數(shù)函數(shù)，排序函數(shù)，建立哈夫曼函數(shù)，編碼函數(shù)，譯碼函數(shù)來(lái)實(shí)現(xiàn)功能。5.2功能模塊圖5.3程序：#include"stdafx.h"#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<fstream.h>typedefstruct{//赫夫曼樹(shù)的結(jié)構(gòu)體 charch; intweight;//權(quán)值 intparent,lchild,rchild;}htnode,*hfmtree;typedefchar**hfmcode;voidSelect(hfmtree&HT,inta,int*p1,int*p2)//Select函數(shù)，選出HT樹(shù)到a為止，權(quán)值最小且parent為0的2個(gè)節(jié)點(diǎn){ inti,j,x,y; for(j=1;j<=a;++j){ if(HT[j].parent==0){ x=j; break; } } for(i=j+1;i<=a;++i){ if(HT[i].weight<HT[x].weight&&HT[i].parent==0){ x=i;//選出最小的節(jié)點(diǎn) } } for(j=1;j<=a;++j) { if(HT[j].parent==0&&x!=j) { y=j; break; } } for(i=j+1;i<=a;++i) { if(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i) { y=i;//選出次小的節(jié)點(diǎn) } } if(x>y){ *p1=y; *p2=x; } else { *p1=x; *p2=y; }}voidhfmcoding(hfmtree&HT,hfmcode&HC,intn)//構(gòu)建赫夫曼樹(shù)HT，并求出n個(gè)字符的赫夫曼編碼HC{ inti,start,c,f,m,w; intp1,p2; char*cd,z; if(n<=1){ return; } m=2*n-1; HT=(hfmtree)malloc((m+1)*sizeof(htnode)); for(i=1;i<=n;++i)//初始化n個(gè)葉子結(jié)點(diǎn) { printf("請(qǐng)輸入第%d字符信息和權(quán)值：",i); scanf("%c%d",&z,&w); while(getchar()!='\n') { continue; } HT[i].ch=z; HT[i].weight=w; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for(;i<=m;++i)//初始化其余的結(jié)點(diǎn) { HT[i].ch='0'; HT[i].weight=0; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for(i=n+1;i<=m;++i)//建立赫夫曼樹(shù) { Select(HT,i-1,&p1,&p2); HT[p1].parent=i;HT[p2].parent=i; HT[i].lchild=p1;HT[i].rchild=p2; HT[i].weight=HT[p1].weight+HT[p2].weight; } HC=(hfmcode)malloc((n+1)*sizeof(char*)); cd=(char*)malloc(n*sizeof(char)); cd[n-1]='\0'; for(i=1;i<=n;++i)//給n個(gè)字符編碼 { start=n-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) { if(HT[f].lchild==c) { cd[--start]='0'; } else { cd[--start]='1'; } } HC[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); } free(cd);}intmain(){ charcode[100],h[100],hl[100]; intn,i,j,k,l; ifstreaminput_file;//文件輸入輸出流 ofstreamoutput_file; charchoice,str[100]; hfmtreeHT; hfmcodeHC; cout<<"\n"; cout<<""<<""<<""<<""<<""<<"\n"; while(choice!='Q'&&choice!='q')//當(dāng)choice的值不為q且不為Q時(shí)循環(huán) { cout<<""<<"*************************赫夫曼編碼/譯碼器*************************\n"; cout<<""<<"I.Init"<<""<<"E.Encoding"<<""<<"D.Decoding"<<""<<"Q.Exit\n"; cout<<"請(qǐng)輸入您要操作的步驟："; cin>>choice; if(choice=='I'||choice=='i')//初始化赫夫曼樹(shù) { cout<<"請(qǐng)輸入字符個(gè)數(shù)："; cin>>n; hfmcoding(HT,HC,n); for(i=1;i<=n;++i) { cout<<HT[i].ch<<":"<<HC[i]<<endl; } output_file.open("hfmTree.txt"); if(!output_file){ cout<<"can'toenfile!"<<endl; return1; } for(i=1;i<=n;i++) { output_file<<"("<<HT[i].ch<<HC[i]<<")"; } output_file.close(); cout<<"赫夫曼樹(shù)已經(jīng)創(chuàng)建完畢