四川師范大學(xué)數(shù)學(xué)與軟件科學(xué)學(xué)院實(shí)驗(yàn)報告課程名稱：數(shù)據(jù)結(jié)構(gòu)（C語言版）指導(dǎo)老師：馮山實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)名稱學(xué)時成績實(shí)驗(yàn)一ADT的類C描述向C程序的轉(zhuǎn)換實(shí)驗(yàn)2學(xué)時實(shí)驗(yàn)二線性表及其基本操作實(shí)驗(yàn)2學(xué)時實(shí)驗(yàn)三棧和隊(duì)列實(shí)驗(yàn)6學(xué)時實(shí)驗(yàn)四字符串實(shí)驗(yàn)2學(xué)時實(shí)驗(yàn)五稀疏矩陣的三元組實(shí)現(xiàn)實(shí)驗(yàn)4學(xué)時實(shí)驗(yàn)六二叉樹的基本算法實(shí)驗(yàn)4學(xué)時實(shí)驗(yàn)七Huffman樹與Huffman樹編碼算法實(shí)驗(yàn)4學(xué)時實(shí)驗(yàn)八圖的建立與遍歷算法實(shí)驗(yàn)4學(xué)時實(shí)驗(yàn)九內(nèi)部排序算法實(shí)驗(yàn)4學(xué)時實(shí)驗(yàn)十查找實(shí)驗(yàn)2學(xué)時班級：2009級6班學(xué)號：2009060630姓名：總成績：________實(shí)驗(yàn)一：ADT的類C描述向C程序的轉(zhuǎn)換實(shí)驗(yàn)(2學(xué)時)實(shí)驗(yàn)?zāi)康模?1)復(fù)習(xí)C語言的基本用法；(2)學(xué)會用類C的語言對算法進(jìn)行描述的方法，將類C算法轉(zhuǎn)換成C源程序的方法和過程；(3)抽象數(shù)據(jù)類型的定義和表示、實(shí)現(xiàn)；(4)加深對數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)之間關(guān)系的理解；(5)初步建立起時間復(fù)雜度和空間復(fù)雜度的概念。實(shí)驗(yàn)內(nèi)容：(類C算法的程序?qū)崿F(xiàn))(1)輸入一組數(shù)據(jù)存入數(shù)組中，并將數(shù)據(jù)元素的個數(shù)動態(tài)地由輸入函數(shù)完成。求輸入數(shù)據(jù)的最大值、最小值，并通過函數(shù)參數(shù)返回所求結(jié)果；實(shí)驗(yàn)準(zhǔn)備：1)計算機(jī)設(shè)備；2)程序調(diào)試環(huán)境的準(zhǔn)備，如TC環(huán)境；3)實(shí)驗(yàn)內(nèi)容的算法分析與代碼設(shè)計與分析準(zhǔn)備。實(shí)驗(yàn)步驟：1.安裝TC并設(shè)置好環(huán)境，如果已安裝好，可以跳過此步；2.錄入程序代碼并進(jìn)行調(diào)試和算法分析；對實(shí)驗(yàn)內(nèi)容(1)的操作步驟：1)用類C語言描述算法過程；2)用C語言環(huán)境實(shí)現(xiàn)該算法。對實(shí)驗(yàn)內(nèi)容(2)的操作步驟：1)完成算法的C實(shí)現(xiàn)；2)分析其時間復(fù)雜度和空間復(fù)雜度。3.編寫實(shí)驗(yàn)報告。實(shí)驗(yàn)結(jié)果：//動態(tài)分配數(shù)組空間#include"stdio.h"#include"malloc.h"intsize,i;int*pArray;int*p;voidmalloc_size(){ pArray=(int*)malloc(size*(sizeof(int)));}intinput_size(){ printf("pleaseinputthesize:\n"); printf("size="); scanf("%d",&size); return0;}intinput_data(){ printf("pleaseinputthevalue:\n"); for(i=0;i<size;i++) { printf("pArray[%d]=",i); scanf("%d",&pArray[i]); } return*pArray;}intCompare(){ intx,y,i; x=y=p[0]; for(i=0;i<size;i++) { if(x>=p[i])x=p[i]; if(y<=p[i])y=p[i]; } printf("min=%d\tmax=%d\n",x,y); return0;}intOutput_data(){ p=pArray; printf("beforeofpaixu:\n"); for(i=0;i<size;i++) { printf("%d\t",*pArray); pArray++; } printf("\n"); return*pArray;}voidpaixu(){ intx=0; inti,j; printf("laterofpaixu:\n"); for(i=0;i<size;i++) { for(j=i+1;j<size;j++) { if(p[i]>=p[j]) { x=p[i];p[i]=p[j];p[j]=x; } } printf("%d\t",p[i]); } printf("\n");}voidmain(){ clrscr(); input_size(); malloc_size(); input_data(); Output_data(); Compare(); paixu();}實(shí)驗(yàn)結(jié)果：實(shí)驗(yàn)二線性表及其基本操作實(shí)驗(yàn)(2學(xué)時)實(shí)驗(yàn)?zāi)康模?1)熟練掌握線性表ADT和相關(guān)算法描述、基本程序?qū)崿F(xiàn)結(jié)構(gòu)；(2)以線性表的基本操作為基礎(chǔ)實(shí)現(xiàn)相應(yīng)的程序；(3)掌握線性表的順序存儲結(jié)構(gòu)和動態(tài)存儲結(jié)構(gòu)之區(qū)分。實(shí)驗(yàn)內(nèi)容：(類C算法的程序?qū)崿F(xiàn)，任選其一。具體要求參見教學(xué)實(shí)驗(yàn)大綱)(1)一元多項(xiàng)式運(yùn)算的C語言程序?qū)崿F(xiàn)(加法必做，其它選做)；(2)有序表的合并；(3)集合的并、交、補(bǔ)運(yùn)算；實(shí)驗(yàn)準(zhǔn)備：1)計算機(jī)設(shè)備；2)程序調(diào)試環(huán)境的準(zhǔn)備，如TC環(huán)境；3)實(shí)驗(yàn)內(nèi)容的算法分析與代碼設(shè)計與分析準(zhǔn)備。實(shí)驗(yàn)步驟：1.錄入程序代碼并進(jìn)行調(diào)試和算法分析；2.編寫實(shí)驗(yàn)報告。實(shí)驗(yàn)結(jié)果：//線性鏈表#include"malloc.h"#include"stdio.h"#defineM6typedefstructnode{ intdata;structnode*next;}*Sqlist;voidInitlialize(Sqlist&L){ L=(Sqlist)malloc(sizeof(Sqlist)); L->next=NULL;}intGetlength(SqlistL){ inti=0; Sqlistp=L->next; while(p!=NULL) {i++;p=p->next; }returni;}intGetelem(SqlistL,inti){intj=1,e; Sqlistp=L->next; while(j<i) {p=p->next;j++; }e=p->data; printf("第%d個元素是：%d\n",i,e); return1;}intLocatelem(SqlistL,intx){inti=0; Sqlistp=L->next; while(p!=NULL&&p->data!=x) { p=p->next;i++; } if(p==NULL) return0; else { printf("%d是第%d個元素\n",x,i); returni; }}voidCreatlistF(Sqlist&L,inta[],intn)//頭插法{//從一個空表開始，讀取字符數(shù)組a中字符生成新結(jié)點(diǎn)，將讀取數(shù)據(jù)存放到新結(jié)點(diǎn)數(shù)據(jù)域，//再將新結(jié)點(diǎn)插入當(dāng)前鏈表表頭、直至結(jié)束 Sqlists; inti; L=(Sqlist)malloc(sizeof(Sqlist)); L->next=NULL; for(i=0;i<n;i++) { s=(Sqlist)malloc(sizeof(Sqlist)); s->data=a[i];s->next=L->next; L->next=s; }}voidCreatlistR(Sqlist&L,inta[],intn)//尾插法{//將新結(jié)點(diǎn)插到當(dāng)前鏈表表尾，為此必須新增一個尾指針r,使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)Sqlists,r; inti; L=(Sqlist)malloc(sizeof(Sqlist)); L->next=NULL; r=L; for(i=0;i<n;i++) { s=(Sqlist)malloc(sizeof(Sqlist)); s->data=a[i];s->next=NULL; r->next=s;r=s; }}intInselem(Sqlist&L,inti,intx){//1、將所建新結(jié)點(diǎn)s的next域指向p的下一結(jié)點(diǎn)：s->next=p->next//2、將結(jié)點(diǎn)p的next域指向新結(jié)點(diǎn)s：p->next=s intj=1; Sqlists,p=L->next; s=(Sqlist)malloc(sizeof(Sqlist)); s->data=x;s->next=NULL; if(i<1||i>Getlength(L)) return0; while(j<i-1) { p=p->next; j++; } printf("在第%d個位置插入數(shù)據(jù)：%d\n",i,x); s->next=p->next;p->next=s; return1;}intDelelem(Sqlist&L,inti){intj=1;Sqlistp,q;p=L;if(i<1||i>Getlength(L)) return0;while(j<i){ p=p->next;j++;}q=p->next;p->next=q->next;free(q);return1;}voidDisplist(SqlistL){Sqlistp=L->next; while(p!=NULL) { printf("%d\t",p->data); p=p->next; } printf(“\n”);}voidinput(int*pArray,intn){printf("請輸入數(shù)組數(shù)據(jù)(共含%d個元):\n",n);for(inti=0;i<n;i++)Scanf(“%d”,&pArray[i]);intmain(intargc,char*argv[]){ SqlistL;intArray[M],Select; Initlialize(L); do{ printf("請輸入選擇方法（1表示頭插法，2表示尾插法,0表示結(jié)束）：\n");scanf("%d",&Select);switch(Select) { case1:printf("按頭插法建立線性表:\n");input(Array,M);CreatlistF(L,Array,M);break; case2:printf("按尾插法建立線性表:\n");input(Array,M);CreatlistR(L,Array,M);break; } printf("原線性表數(shù)據(jù)為:\n"); Displist(L); Getelem(L,3);Locatelem(L,2);Inselem(L,5,5);printf("修改后的線性表數(shù)據(jù)為:\n");// Delelem(L,4);Displist(L); }while(Select!=0); return0;}//運(yùn)行結(jié)果:實(shí)驗(yàn)三棧和隊(duì)列實(shí)驗(yàn)(6學(xué)時)實(shí)驗(yàn)?zāi)康模?1)熟練掌握棧和隊(duì)列的抽象數(shù)據(jù)類型及其結(jié)構(gòu)特點(diǎn)；(2)實(shí)現(xiàn)基本的棧和隊(duì)列的基本操作算法程序。實(shí)驗(yàn)內(nèi)容：(類C算法的程序?qū)崿F(xiàn)，任選其一)(1)設(shè)計與實(shí)現(xiàn)基本的堆棧和隊(duì)列結(jié)構(gòu)下的各種操作（如堆棧的PUSH、POP等操作）(必做)；(2)以表達(dá)式計算為例，完成一個可以進(jìn)行算術(shù)表達(dá)式計算功能的算法設(shè)計與實(shí)現(xiàn)（選做）；實(shí)驗(yàn)準(zhǔn)備：1)計算機(jī)設(shè)備；2)程序調(diào)試環(huán)境的準(zhǔn)備，如TC環(huán)境；3)實(shí)驗(yàn)內(nèi)容的算法分析與代碼設(shè)計與分析準(zhǔn)備。實(shí)驗(yàn)步驟：1.錄入程序代碼并進(jìn)行調(diào)試和算法分析；2.編寫實(shí)驗(yàn)報告。實(shí)驗(yàn)結(jié)果：（1）/*隊(duì)列存儲*/#include"stdio.h"typedefintstatus;#defineQueueSize10typedefstructsqqueue{ chardata[QueueSize]; intfront,rear;}SqQueue;voidInitQueue(SqQueue&qu){ qu.front=qu.rear=0;}statusEnQueue(SqQueue&qu,charx){if((qu.rear+1)%QueueSize==qu.front) return0; qu.rear=(qu.rear+1)%QueueSize; qu.data[qu.rear]=x; return1;}statusDeQueue(SqQueue&qu,char&x){ if(qu.rear==qu.front) return0; qu.front=(qu.front+1)%QueueSize; x=qu.data[qu.front]; return1;}statusGetHead(SqQueuequ,char&x){ if(qu.rear==qu.front) return0; x=qu.data[(qu.front+1)%QueueSize]; return1;}statusQueueEmpty(SqQueuequ){ if(qu.rear==qu.front) return1; else return0;}voidmain(){SqQueuequ; chare; InitQueue(qu);printf("Queue%s\n",(QueueEmpty(qu)==1"Empty":"NotEmpty"));printf("insera\n");EnQueue(qu,'a');printf("inserb\n");EnQueue(qu,'b');printf("inserc\n");EnQueue(qu,'c');printf("inserd\n");EnQueue(qu,'d');printf("Queue%s\n",(QueueEmpty(qu)==1"Empty":"NotEmpty"));GetHead(qu,e);printf("Queueoftopelemis:%c\n",e);printf("showofQueue:\n");while(!QueueEmpty(qu)) { DeQueue(qu,e); printf("%c\t",e); }printf("\n");}實(shí)驗(yàn)結(jié)果：（2）/*用棧實(shí)現(xiàn)對表達(dá)式的求值運(yùn)算*/#include"stdio.h"#include"malloc.h"#include"stdlib.h"/*數(shù)據(jù)類型轉(zhuǎn)換庫函數(shù)*/#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2#defineSTACK_INIT_SIZE100/*初始分配量*/#defineSTACKINCREMENT10/*存儲空間的分配增量*/typedefintStatus;typedefcharElemType;typedefElemTypeOperandType;/*操作數(shù)*/typedefcharOperatorType;typedefstruct{ElemType*base;ElemType*top;intstacksize;}SqStack;StatusInitStack(SqStack&S){/*構(gòu)造一個空棧S*/S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)exit(OVERFLOW);/*存儲空間失敗*/S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}/*InitStack*/StatusGetTop(SqStackS){ /*若棧不空，則用e返回S的棧頂元素*/ElemTypee;if(S.top==S.base)returnERROR;e=*(S.top-1);returne;}/*GetTop*/StatusPush(SqStack&S,ElemTypee)/*插入元素e為新的棧頂元素*/{if(S.top-S.base>=S.stacksize){ /*棧滿，追加存儲空間*/S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));if(!S.base)exit(OVERFLOW);/*存儲空間失敗*/S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}/*Push*/StatusPop(SqStack&S,ElemType&e)/*取棧頂元素，用e返回*/{/*若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR*/if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}/*Pop*/charIn(charc,charOP[])/*判斷字符c是否屬于運(yùn)算符*/{if(c>=35&&c<=47)return1; /*常見操作符（如：'#'、'（'、'）'、'+'、'-'、'*'、'\'等）的ASCII碼在35到47之間*/elsereturn0;}charOP[8]={'+','-','*','/','(',')','#','\0'};/*定義有所要用到的操作符構(gòu)成的數(shù)組OP[8]*/intm[7][7]={1,1,2,2,2,1,1,1,1,2,2,2,1,1,1,1,1,1,2,1,1,1,1,1,1,2,1,1,2,2,2,2,2,0,-1,1,1,1,1,-1,1,1,2,2,2,2,2,-1,0};/*各運(yùn)算符間優(yōu)先級別的關(guān)系*//*以上：1表示‘>’；2表示‘<’；0表示‘=’；-1表示‘不存在’*/charPrecede(chari,charj)/*比較數(shù)組OP[]中字符i與數(shù)組OP中字符j的優(yōu)先權(quán)*/{inta,b;char*p;for(p=OP,a=0;*p!='\0';p++,a++)if(*p==i)break;for(p=OP,b=0;*p!='\0';p++,b++)if(*p==j)break;if(m[a][b]==1)return'>';elseif(m[a][b]==2)return'<';elseif(m[a][b]==0)return'=';elsereturn'O';}charOperate(chara,chartheta,charb)/*對運(yùn)算數(shù)a、b按操作符theta進(jìn)行二元運(yùn)算*/{if(a>47)a=atoi(&a);/*將字符數(shù)轉(zhuǎn)化為整型數(shù)*/if(b>47)b=atoi(&b);switch(theta) {case'+':returna+b;break;case'-':returna-b;break;case'*':returna*b;break;case'/':returna/b;break; }return'1';}OperandTypeEvaluateExpression()/*算術(shù)表達(dá)式求值的算符優(yōu)先算法*/{SqStackOPTR,OPND;/*設(shè)OPTR、OPND分別運(yùn)算符棧和運(yùn)算數(shù)棧*/OperandTypea,b,c;OperatorTypetheta;InitStack(OPTR);Push(OPTR,'#');InitStack(OPND);c=getchar();while(c!='#'||GetTop(OPTR)!='#') {if(!In(c,OP)){Push(OPND,c);c=getchar();}elseswitch(Precede(GetTop(OPTR),c)) {case'<':Push(OPTR,c);c=getchar();break;case'=':Pop(OPTR,c);c=getchar();break;case'>':Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a); Push(OPND,Operate(a,theta,b));break; } }returnGetTop(OPND);}intmain(){printf("(請輸入運(yùn)算表達(dá)式：以#為結(jié)束符)\n");inta;a=(int)EvaluateExpression();/*執(zhí)行函數(shù)EvaluateExpression()，將表達(dá)式的最終值強(qiáng)制轉(zhuǎn)換為整型，并用a返回*/printf("%d",a);getchar();return0;}測試結(jié)果為：①表達(dá)式中包含+、-、*的情況；②表達(dá)式中包含（）、+、-、*的情況；③表達(dá)式中包含（）、+、-、*、/的情況；④表達(dá)式中出現(xiàn)負(fù)數(shù)的情況；實(shí)驗(yàn)四字符串實(shí)驗(yàn)(2學(xué)時)實(shí)驗(yàn)?zāi)康模赫莆沼嘘P(guān)字符串的基本操作和存儲結(jié)構(gòu)，并編寫相應(yīng)的基本操作算法。實(shí)驗(yàn)內(nèi)容：(類C算法的程序?qū)崿F(xiàn)，任選其二)(1)求字符串的長度算法(必做)；(2)求字符串的子串算法(選做)；(3)字符串的合并算法(選做)；(4)字符串的置換算法(選做)；(5)字符串的插入算法(選做)。實(shí)驗(yàn)準(zhǔn)備：1)計算機(jī)設(shè)備；2)程序調(diào)試環(huán)境的準(zhǔn)備，如TC環(huán)境；3)實(shí)驗(yàn)內(nèi)容的算法分析與代碼設(shè)計與分析準(zhǔn)備。實(shí)驗(yàn)步驟：1.錄入程序代碼并進(jìn)行調(diào)試和算法分析；2.編寫實(shí)驗(yàn)報告。實(shí)驗(yàn)結(jié)果：#include"malloc.h"#include"stdio.h"typedefintStatus;typedefstructnode{ charch[5];//存放串字符 intlen;//存放串的實(shí)際長度}Sqstring;//順序串類型//串賦值運(yùn)算算法SqstringStrAssign(Sqstring&s,charch[])//將一個字符數(shù)組ch[]賦給串s{inti=0; while(ch[i]!='\0') {s.ch[i]=ch[i]; i++; } s.len=i; returns;}//求串長運(yùn)算算法StatusStrlength(Sqstrings){returns.len;}//判斷算法相等算法StatusStrCompare(Sqstrings,Sqstringt){ if(s.len!=t.len) return0; else for(inti=0;i<s.len;i++) { if(s.ch[i]!=t.ch[i]) { printf("這兩個字符串是不相等的\n"); return0; } else { printf("這兩個字符串是相等的\n"); return1; } }return1;}//串復(fù)制算法StatusStrCopy(Sqstring&s,Sqstringt)//將串t賦給串s{ for(inti=0;i<t.len;i++) { s.ch[i]=t.ch[i]; } s.len=t.len; return0;}//串連接算法SqstringConcat(Sqstring&s,Sqstringt)//將串t連接到串s之后，返回連接后的結(jié)果串{Sqstringr; inti,j; for(i=0;i<s.len;i++)//將s復(fù)制給r r.ch[i]=s.ch[i]; for(j=0;j<t.len;j++)//將t復(fù)制給r r.ch[s.len+j]=t.ch[j]; r.len=i+j; returnr;//返回r}//求字串運(yùn)算算法SqstringSubStr(Sqstrings,inti,intj)//將從串s的第i個位置取的j個字符以字符串形式返回{ Sqstringt;printf("由A中第%d個字符開始的%d個字符構(gòu)成的",i,j); if(i<1||i>s.len||j<1||i+j>s.len+1) t.len=0; else { for(intk=i+-1;k<i+j;k++) t.ch[k-i+1]=s.ch[k]; t.len=j; } returnt;}//查找字串位置運(yùn)算算法intIndex(Sqstring&s,Sqstringt)//返回字串t在主串s中的位置，若不在s中返回0{inti=0,j=0,k; while(i<s.len&&j<t.len) { if(s.ch[i]==t.ch[j])//對應(yīng)字符相同，繼續(xù)比較下一個字符 { i++; j++; } else//否則，從主串開頭從新開始下一次匹配 { i=i-j+1; j=0; } } printf("1：表示能找到相匹配的字符串，0：表示沒有找到相匹配的字符串\n查找結(jié)果為\n"); if(j>=t.len) { k=i-t.len+1;//求出第一個字符的位置 printf("%d\n",k); } else { k=0; printf("%d\n",k); } returnk;}//字串插入運(yùn)算算法intInsStr(Sqstring&s,inti,Sqstringt)//將字串t插入串s中{ intj; printf("在字符串A的第%d個字符處插入字符串B后",i); if(i>s.len+1) return0; else { for(j=s.len;j>i-2;j--)//將s.ch[i-1]--s.ch[s.len-1]后移t.len個位置 s.ch[j+t.len]=s.ch[j]; for(j=0;j<t.len;j++) s.ch[i+j-1]=t.ch[j]; s.len=s.len+t.len;//修改s的長度 return1; }}//字串刪除運(yùn)算算法StatusDelStr(Sqstring&s,inti,intj){ intk; printf("刪出A中第%d個字符開始的%d個字符后構(gòu)成的",i,j); if(i<1||i>s.len||j<1||j>s.len+1) return0; else { for(k=i+j-1;k<s.len;k++)//將s.ch[i+j-1]--s.ch[s.len-1]前移j位 s.ch[k-j]=s.ch[k]; s.len=s.len-j;//修改s的長度 return1; }}//字串替換算法SqstringRepStr(Sqstrings,Sqstrings1,Sqstrings2)//將s中所有出現(xiàn)的字串s1均替換為字串s2{ inti; i=Index(s,s1); while(i>=0) { DelStr(s,i,s1.len);//刪除 InsStr(s,i,s2);//插入 i=Index(s,s1); } returns;}//輸出串運(yùn)算算法voidDispStr(Sqstrings,chara){ inti; printf("字符串%c為：\n",a); for(i=0;i<s.len;i++) printf("%c\t",s.ch[i]); printf("\n");}//主函數(shù)intmain(){ SqstringA,B,C,D,E,F,G; charArray[5]={'a','b','c','d','\0'}; charBrray[5]={'e','f','g','h','\0'}; charCrray[3]={'c','d','\0'};StrAssign(A,Array); DispStr(A,'A'); StrAssign(B,Brray); DispStr(B,'B'); StrAssign(E,Brray); DispStr(E,'E');StrCompare(A,B);//比較兩字符串 printf("將字符串B連接到字符串A后的");F=Concat(A,B);DispStr(F,'F');//將字符串s1連接到s字符串中 printf("將字符串B復(fù)制到字符串A后的");StrCopy(A,B);DispStr(A,'A');//將字符串s1復(fù)制到s字符串中D=SubStr(A,2,3);DispStr(D,'D');Index(A,E);DelStr(A,3,2);DispStr(A,'A'); return0;}測試結(jié)果為：實(shí)驗(yàn)五稀疏矩陣的三元組實(shí)現(xiàn)實(shí)驗(yàn)(4學(xué)時)實(shí)驗(yàn)?zāi)康模赫莆障∈杈仃嚨娜M表示方法、算法實(shí)現(xiàn)。實(shí)驗(yàn)內(nèi)容：(類C算法的程序?qū)崿F(xiàn)，任選其二)(1)基于三元組的稀疏矩陣表示與輸入、輸出方法(必做)；(2)基于三元組的稀疏矩陣加法(選做)；(3)基于三元組表示的稀疏矩陣轉(zhuǎn)置(選做)；實(shí)驗(yàn)準(zhǔn)備：1)計算機(jī)設(shè)備；2)程序調(diào)試環(huán)境的準(zhǔn)備，如TC環(huán)境；3)實(shí)驗(yàn)內(nèi)容的算法分析與代碼設(shè)計與分析準(zhǔn)備。實(shí)驗(yàn)步驟：1.錄入程序代碼并進(jìn)行調(diào)試和算法分析；2.編寫實(shí)驗(yàn)報告。實(shí)驗(yàn)結(jié)果：#include"stdio.h"#defineMaxsize100#defineM6#defineN6typedefstruct{ intr;//行號 intc;//列號 intd;//元素值}TupNode;typedefstruct{ introws;//行數(shù)值intcols;//列數(shù)值 intnums;//非零元素個數(shù) TupNodedata[Maxsize];}TSMatrix;//三元組順序表定義//從一個二維矩陣創(chuàng)建其三元組表示的運(yùn)算算法voidCreatMat(TSMatrix&t,intA[M][N]){ inti,j; t.rows=M; t.cols=N; t.nums=0; for(i=0;i<M;i++) { for(j=0;j<N;j++) { if(A[i][j]!=0)//只存儲非0元 { t.data[t.nums].r=i; t.data[t.nums].c=j; t.data[t.nums].d=A[i][j]; t.nums++; } } }}//三元組元素賦值運(yùn)算算法intValue(TSMatrix&t,intx,intrs,intcs){ inti,k; if(rs>=t.rows||cs>=t.cols) return0; while(k<t.nums&&rs>t.data[k].r)k++;//尋找位置 while(k<t.nums&&cs>t.data[k].c)k++; if(t.data[k].r==rs&&t.data[k].c==cs) t.data[k].d=x;//該元素存在 else//該元素不存在 { for(i=k;i<=t.nums;i++)//將i后面的元素后移 { t.data[i+1].r=t.data[i].r; t.data[i+1].c=t.data[i].c; t.data[i+1].d=t.data[i].d; } t.data[k].r=rs; t.data[k].c=cs; t.data[k].d=x; t.nums++; } return1;}//將指定位置的元素賦給變量的運(yùn)算算法intAssign(TSMatrixt,int&x,intrs,intcs){ intk=0; if(rs>=t.rows||cs>=t.cols) return0; while(k<t.nums&&rs>t.data[k].r)k++; while(k<t.nums&&cs>t.data[k].c)k++; if(t.data[k].r==rs&&t.data[k].c==cs) { x=t.data[k].d; printf("第%d行第%d列的元素為：x=%d\n",rs,cs,x); returnx; } elsereturn0;}//輸出三元組運(yùn)算算法intDispMat(TSMatrixt){ inti; if(t.nums<=0) return0; printf("\t%d\t%d\t%d\n",t.rows,t.cols,t.nums); printf("------------------------------------\n"); for(i=0;i<t.nums;i++) printf("\t%d\t%d\t%d\n",t.data[i].r,t.data[i].c,t.data[i].d); return1;}//矩陣轉(zhuǎn)置算法voidTsanTat(TSMatrixt,TSMatrix&tb){ intp,q=0,v; tb.rows=t.cols;; tb.cols=t.rows; tb.nums=t.nums; if(t.nums!=0) { for(v=0;v<t.cols;v++) { for(p=0;p<t.nums;p++) { if(t.data[p].c==v) { tb.data[q].r=t.data[p].c; tb.data[q].c=t.data[p].r; tb.data[q].d=t.data[p].d; q++; } } } }}//兩矩陣相加運(yùn)算算法intMatAdd(TSMatrixa,TSMatrixb,TSMatrix&c){ inti=0,j=0,k=0; chare; if(a.rows!=b.rows||a.cols!=b.cols) { printf("這兩矩陣不能相加：\n"); return0; } c.rows=a.rows;c.cols=a.cols; while(i<a.nums&&j<b.nums) { if(a.data[i].r==b.data[j].r) { if(a.data[i].c<b.data[j].c) { c.data[k].r=a.data[i].r; c.data[k].c=a.data[i].c; c.data[k].d=a.data[i].d; k++;i++; } elseif(a.data[i].c>b.data[j].c) { c.data[k].r=b.data[j].r; c.data[k].c=b.data[j].c; c.data[k].d=b.data[j].d; k++; j++; } else { e=a.data[i].d+b.data[j].d; if(e!=0) { c.data[k].r=a.data[i].r; c.data[k].c=a.data[i].c; c.data[k].d=e; k++; } i++;j++; } }elseif(a.data[k].r<b.data[j].r) { c.data[k].r=a.data[i].r; c.data[k].c=a.data[i].c; c.data[k].d=a.data[i].d; k++;i++; }else { c.data[k].r=b.data[j].r; c.data[k].c=b.data[j].c; c.data[k].d=b.data[j].d; k++;j++; } c.nums=k; }return1;}intmain()//主函數(shù){ TSMatrixt,tb,tp; inte; intArray[M][N]={0,0,1,0,0,0, 0,2,0,0,0,0, 3,0,0,0,0,0, 0,0,0,5,0,0, 0,0,0,0,6,0, 0,0,0,0,0,7}; CreatMat(t,Array); printf("該稀疏矩陣為：\n"); DispMat(t); Assign(t,e,0,2);//查找元素 TsanTat(t,tb); printf("轉(zhuǎn)置后的矩陣為：\n"); DispMat(tb);MatAdd(t,tb,tp); printf("兩矩陣相加后所得矩陣為：\n");DispMat(tp); return0;}測試結(jié)果：實(shí)驗(yàn)六二叉樹的基本算法實(shí)驗(yàn)(4學(xué)時)實(shí)驗(yàn)?zāi)康模?1)掌握樹和二叉樹的基本概念和順序與鏈?zhǔn)酱鎯Y(jié)構(gòu)；(2)重點(diǎn)掌握二叉樹的生成、遍歷等算法；(3)掌握二叉樹的線索化及基于線索二叉樹的遍歷算法。實(shí)驗(yàn)內(nèi)容：(類C算法的程序?qū)崿F(xiàn))(1)二叉樹的基本算法描述及實(shí)現(xiàn)（二叉樹的建立、輸出、插入等算法）(必做)(2)二叉樹的先序、后序、中序遍歷(必做)實(shí)驗(yàn)準(zhǔn)備：1)計算機(jī)設(shè)備；2)程序調(diào)試環(huán)境的準(zhǔn)備，如TC環(huán)境；3)實(shí)驗(yàn)內(nèi)容的算法分析與代碼設(shè)計與分析準(zhǔn)備。實(shí)驗(yàn)步驟：1.錄入程序代碼并進(jìn)行調(diào)試和算法分析2.編寫實(shí)驗(yàn)報告實(shí)驗(yàn)結(jié)果：#include"stdio.h"#include"malloc.h"#defineMaxSize20typedefstructtnode{ intdata; structtnode*lchild,*rchild;}BTNode;//建立二叉樹運(yùn)算算法voidCreatBTree(BTNode*&bt,char*str){ BTNode*St[MaxSize],*p=NULL; inttop=-1,k,j=0;charch; bt=NULL;//建立的二叉樹初始化時為空 ch=str[0]; while(ch!='\0') { switch(ch) { case'(':top++;St[top]=p;k=1;break;//為左孩子結(jié)點(diǎn) case')':top--;break; case',':k=2;break;//為右孩子結(jié)點(diǎn) default:p=(BTNode*)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL; if(bt==NULL)//p為二叉樹的根結(jié)點(diǎn) bt=p; else//已建立二叉樹根結(jié)點(diǎn) { switch(k) { case1:St[top]->lchild=p;break; case2:St[top]->rchild=p;break; } } } j++;ch=str[j]; }}//求二叉樹高度運(yùn)算算法(遞歸法)intBTHeight(BTNode*bt){ intlchilddep,rchilddep; if(bt==NULL)//空樹高度為0 return0; else { lchilddep=BTHeight(bt->lchild);//求左子樹的高度 rchilddep=BTHeight(bt->rchild);//求右子樹的高度 return(lchilddep>rchilddep)(lchilddep+1):(rchilddep+1); }}//求二叉樹結(jié)點(diǎn)個數(shù)運(yùn)算算法(遞歸法)intNodeCount(BTNode*bt){ intnum1,num2; if(bt==NULL)//空樹結(jié)點(diǎn)個數(shù)為0 return0; else { num1=NodeCount(bt->lchild);//求出左子樹的結(jié)點(diǎn)樹 num2=NodeCount(bt->rchild);//求出右子樹的結(jié)點(diǎn)樹 return(num1+num2+1); }}//求二叉樹葉子結(jié)點(diǎn)個數(shù)運(yùn)算算法(遞歸法)intLeafCount(BTNode*bt){ intnum1,num2; if(bt==NULL) return0;//空樹葉子結(jié)點(diǎn)個數(shù)為0 elseif(bt->lchild==NULL&&bt->rchild==NULL) return1;//若為葉子結(jié)點(diǎn)返回1 else { num1=LeafCount(bt->lchild);//求出左子樹的葉子結(jié)點(diǎn)樹 num2=LeafCount(bt->rchild);//求出右子樹的葉子結(jié)點(diǎn)樹 returnnum1+num2; }}//以括號表示法輸出二叉樹運(yùn)算算法(遞歸法)voidDispBTree(BTNode*bt){ if(bt!=NULL) { printf("%c",bt->data); if(bt->lchild!=NULL||bt->rchild!=NULL) { printf("("); DispBTree(bt->lchild);//以遞歸法處理左子樹 if(bt->rchild!=NULL) printf(","); DispBTree(bt->rchild);//以遞歸法處理右子樹 printf(")"); } }}//先序遍歷voidPreOrder(BTNode*bt){ if(bt!=NULL) { printf("%c",bt->data); PreOrder(bt->lchild);PreOrder(bt->rchild); }}//中序遍歷voidInOrder(BTNode*bt){ if(bt!=NULL) { InOrder(bt->lchild); printf("%c",bt->data);InOrder(bt->rchild); }}//后序遍歷voidPostOrder(BTNode*bt){ if(bt!=NULL) { PostOrder(bt->lchild);PostOrder(bt->rchild); printf("%c",bt->data); }}intmain()//主函數(shù){BTNode*bt; CreatBTree(bt,"A(B(D,E(G,H),C(,F(I)))"); printf("二叉數(shù)bt以括號法顯示為:");DispBTree(bt);printf("\n"); printf("先序發(fā)遍歷二叉數(shù)bt為:");PreOrder(bt); printf("\n"); printf("中序發(fā)遍歷二叉數(shù)bt為:");InOrder(bt); printf("\n"); printf("后序發(fā)遍歷二叉數(shù)bt為:");PostOrder(bt); printf("\n"); printf("二叉數(shù)bt的高度為：%d\n",BTHeight(bt)); printf("二叉數(shù)bt的結(jié)點(diǎn)數(shù)為：%d\n",NodeCount(bt)); printf("二叉數(shù)bt的葉子結(jié)點(diǎn)數(shù)為：%d\n",LeafCount(bt)); printf("\n"); return0;}測試結(jié)果為：實(shí)驗(yàn)七Huffman樹與Huffman樹編碼算法實(shí)驗(yàn)(4學(xué)時)*實(shí)驗(yàn)?zāi)康模赫莆誋uffman樹的編碼方法和算法實(shí)現(xiàn)。實(shí)驗(yàn)內(nèi)容：(類C算法的程序?qū)崿F(xiàn))(1)建立Huffman樹編碼的表示結(jié)構(gòu)，對給定輸入信息集合進(jìn)行Huffman編碼，輸出編碼結(jié)果(必做)(2)利用Huffman編碼算法實(shí)現(xiàn)給定信息串的編碼結(jié)果(必做)實(shí)驗(yàn)準(zhǔn)備：1)計算機(jī)設(shè)備；2)程序調(diào)試環(huán)境的準(zhǔn)備，如TC環(huán)境；3)實(shí)驗(yàn)內(nèi)容的算法分析與代碼設(shè)計與分析準(zhǔn)備。實(shí)驗(yàn)步驟：1.錄入程序代碼并進(jìn)行調(diào)試和算法分析；2.編寫實(shí)驗(yàn)報告。實(shí)驗(yàn)結(jié)果：//HuffmanTree及其編碼#include"malloc.h"#include<iostream>#include"stdio.h"typedefstruct{unsigned intweight;unsigned intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;constintMaxsize=100;intSearch(chardifchar[],intn,chare) //查詢此e字符是否已出現(xiàn){ for(inti=1;i<=n;i++) if(difchar[i]==e) returni; return0;}intstat(chardata[],chardifchar[],intw[])//計算相應(yīng)字符出現(xiàn)的頻率{ intj=0,i,length=strlen(data); inttemp; for(i=0;i<length;i++) { temp=Search(difchar,j,data[i]); if(temp==0) { difchar[++j]=data[i]; w[j]=0; } else w[temp]++; } returnj;}intGetmin(HuffmanTreeT,intn) //返回n個結(jié)點(diǎn)中權(quán)值最小的且沒有父親結(jié)點(diǎn)的結(jié)點(diǎn)序號{ inti=1,flag,j; while(T[i].parent!=0) i++; flag=i,j=T[i].weight;//flag為T中第一個沒有父親結(jié)點(diǎn)的結(jié)點(diǎn)序號 for(i++;i<=n;i++) if(T[i].weight<j&&T[i].parent==0) { j=T[i].weight; flag=i; } T[flag].parent=1; returnflag;}voidSelect(HuffmanTreeT,inti,int&s1,int&s2)//在i個結(jié)點(diǎn)中選擇2個權(quán)值最小的樹的根結(jié)點(diǎn)序號{ intj; s1=Getmin(T,i); s2=Getmin(T,i); if(T[s1].weight>T[s2].weight) { j=s1;s1=s2;s2=j; }}voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){//w存放n個字符的權(quán)值，構(gòu)造Huffman樹HT，并求出n個字符的Huffman編碼HCints1,s2,start,m,i;unsignedintc,f;char*cd;HuffmanTreep;if(n<=1)return;m=2*n-1;//結(jié)點(diǎn)的總數(shù)HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//結(jié)點(diǎn)0空for(p=HT+1,i=1;i<=n;i++,p++,w++){p->weight=*w;(*p).parent=(*p).lchild=(*p).rchild=0;}for(;i<=m;i++,p++)(*p).parent=0;for(i=n+1;i<=m;i++){Select(HT,i-1,s1,s2);//尋找權(quán)值最小的二棵子樹HT[s1].parent=HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-1]='\0';for(i=1;i<=n;i++){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';elsecd[--start]='1';}HC[i]=(char*)malloc((n-start)*sizeof(char));strcpy(HC[i],&cd[start]);}free(cd);}intmain(){ HuffmanTreeHT;HuffmanCodeHC;intn=0,i;//n表示輸入文字中不同字符的個數(shù)chardata[Maxsize];chardifchar[Maxsize],temp;intw[Maxsize];printf("=====-請輸入預(yù)編碼的文字-=====\n");printf("僅限英文字符，輸入#結(jié)束輸入\n"); for(intj=0;j<Maxsize;j++) { scanf("%c",&temp); if(temp!='#') data[j]=temp; else {n=stat(data,difchar,w);HuffmanCoding(HT,HC,w+1,n);printf("=============字符與相應(yīng)編碼為=============\n");for(i=1;i<n;i++)printf("%c:,%s\n",difchar[i],HC[i]); printf("\n===============編碼文字===============\n");for(i=0;i<n-1;i++)printf("%s\t",HC[Search(difchar,n,data[i])]);printf("\n"); }} return0;}實(shí)驗(yàn)結(jié)果：①②實(shí)驗(yàn)八圖的建立與遍歷算法實(shí)驗(yàn)(4學(xué)時)*實(shí)驗(yàn)?zāi)康模?1)熟練掌握圖的鄰接矩陣和鄰接表的存儲方式；(2)實(shí)現(xiàn)一些基本的圖的運(yùn)算算法(如圖的遍歷)；(3)掌握常見算法如最小生成樹、Top排序樹、關(guān)鍵路徑、最短路徑等應(yīng)用算法。實(shí)驗(yàn)內(nèi)容：(類C算法的程序?qū)崿F(xiàn)，任選其二)(1)圖的基本存儲結(jié)構(gòu)和運(yùn)算算法的實(shí)現(xiàn)(必做)；(2)圖的遍歷算法的實(shí)現(xiàn)(選做)；(3)最小生成樹的生成算法實(shí)現(xiàn)(選做)；(4)Top排序樹的算法實(shí)現(xiàn)(選做)；(5)關(guān)鍵路徑算法的實(shí)現(xiàn)(選做)；(6)最短路徑算法的實(shí)現(xiàn)(選做)。實(shí)驗(yàn)準(zhǔn)備：1)計算機(jī)設(shè)備；2)程序調(diào)試環(huán)境的準(zhǔn)備，如TC環(huán)境；3)實(shí)驗(yàn)內(nèi)容的算法分析與代碼設(shè)計與分析準(zhǔn)備。實(shí)驗(yàn)步驟：1.錄入程序代碼并進(jìn)行調(diào)試和算法分析；2.編寫實(shí)驗(yàn)報告。實(shí)驗(yàn)結(jié)果：//圖深度優(yōu)先遍歷算法—鄰接矩陣#include<stdio.h>#include<malloc.h>#defineINFINITY32767#defineMAX_VEX20//最大頂點(diǎn)個數(shù)bool*visited;//訪問標(biāo)志數(shù)組//圖的鄰接矩陣存儲結(jié)構(gòu)typedefstruct{char*vexs;//頂點(diǎn)向量intarcs[MAX_VEX][MAX_VEX];//鄰接矩陣intvexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}Graph;//圖G中查找元素c的位置intLocate(GraphG,charc){for(inti=0;i<G.vexnum;i++)if(G.vexs[i]==c)returni;return-1;}//創(chuàng)建無向網(wǎng)voidCreateUDN(Graph&G){inti,j,w,s1,s2;chara,b,temp;printf("輸入頂點(diǎn)數(shù)和弧數(shù):");scanf("%d%d",&G.vexnum,&G.arcnum);temp=getchar();//接收回車G.vexs=(char*)malloc(G.vexnum*sizeof(char));//分配頂點(diǎn)數(shù)目printf("輸入%d個頂點(diǎn).\n",G.vexnum);for(i=0;i<G.vexnum;i++){//初始化頂點(diǎn)printf("輸入頂點(diǎn)%d:",i);scanf("%c",&G.vexs[i]);temp=getchar();//接收回車}for(i=0;i<G.vexnum;i++)//初始化鄰接矩陣for(j=0;j<G.vexnum;j++)G.arcs[i][j]=INFINITY;printf("輸入%d條弧.\n",G.arcnum);for(i=0;i<G.arcnum;i++){//初始化弧printf("輸入弧%d:",i);scanf("%c%c%d",&a,&b,&w);//輸入一條邊依附的頂點(diǎn)和權(quán)值temp=getchar();//接收回車s1=Locate(G,a);s2=Locate(G,b);G.arcs[s1][s2]=G.arcs[s2][s1]=w;}}//圖G中頂點(diǎn)k的第一個鄰接頂點(diǎn)intFirstVex(GraphG,intk){if(k>=0&&k<G.vexnum){//k合理for(inti=0;i<G.vexnum;i++)if(G.arcs[k][i]!=INFINITY)returni;}return-1;}//圖G中頂點(diǎn)i的第j個鄰接頂點(diǎn)的下一個鄰接頂點(diǎn)intNextVex(GraphG,inti,intj){if(i>=0&&i<G.vexnum&&j>=0&&j<G.vexnum){//i,j合理for(intk=j+1;k<G.vexnum;k++)if(G.arcs[i][k]!=INFINITY)returnk;}return-1;}//深度優(yōu)先遍歷voidDFS(GraphG,intk){inti;if(k==-1){//第一次執(zhí)行DFS時,k為-1for(i=0;i<G.vexnum;i++)if(!visited[i])DFS(G,i);//對尚未訪問的頂點(diǎn)調(diào)用DFS}else{visited[k]=true;printf("%c",G.vexs[k]);//訪問第k個頂點(diǎn)for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))if(!visited[i])DFS(G,i);//對k的尚未訪問的鄰接頂點(diǎn)i遞歸調(diào)用DFS}}//主函數(shù)voidmain(){inti;GraphG;CreateUDN(G);visited=(bool*)malloc(G.vexnum*sizeof(bool));printf("\n深度優(yōu)先遍歷:");for(i=0;i<G.vexnum;i++)visited[i]=false;DFS(G,-1);printf("\n程序結(jié)束.\n");}實(shí)驗(yàn)結(jié)果：//最短路徑：/*用鄰接矩陣表示的圖的Dijkstra算法的源程序*/#include"stdafx.h"#include<stdio.h>#defineMAXVEX100#defineMAX1e+8typedefcharVexType;typedeffloatAdjType;typedefstruct{intn;/*n為圖中頂點(diǎn)個數(shù)*/VexTypevexs[MAXVEX];/*頂點(diǎn)信息*/AdjTypearcs[MAXVEX][MAXVEX];/*邊信息*/}GraphMatrix;typedefstruct{VexTypevertex;/*頂點(diǎn)信息*/AdjTypelength;/*最短路徑長度*/intprevex;/*從v0到達(dá)vi(i=1,2,…n-1)的最短路徑上vi的前趨頂點(diǎn)*/}Path;Pathdist[6];voidinit(GraphMatrix*pgraph,Pathdist[]){inti;dist[0].length=0;dist[0].prevex=0;dist[0].vertex=pgraph->vexs[0];pgraph->arcs[0][0]=1;/*表示頂點(diǎn)v0在集合U中*/for(i=1;i<pgraph->n;i++) {/*初始化集合V-U中頂點(diǎn)的距離值*/dist[i].length=pgraph->arcs[0][i];dist[i].vertex=pgraph->vexs[i];if(dist[i].length!=MAX)dist[i].prevex=0;elsedist[i].prevex=-1;}}voiddijkstra(GraphMatrixgraph,Pathdist[]){inti,j,minvex;AdjTypemin; init(&graph,dist);/*初始化，此時集合U中只有頂點(diǎn)v0*/for(i=1;i<graph.n;i++) {min=MAX; minvex=0;for(j=1;j<graph.n;j++)/*在V-U中選出距離值最小頂點(diǎn)*/if(graph.arcs[j][j]==0&&dist[j].length<min)min=dist[j].length;minvex=j;if(minvex==0)break; /*從v0沒有路徑可以通往集合V-U中的頂點(diǎn)*/graph.arcs[minvex][minvex]=1; /*集合V-U中路徑最小的頂點(diǎn)為minvex*/for(j=1;j<graph.n;j++) { /*調(diào)整集合V-U中的頂點(diǎn)的最短路徑*/if(graph.arcs[j][j]==1)continue;if(dist[j].length>dist[minvex].length+graph.arcs[minvex][j]) {dist[j].length=dist[minvex].length+graph.arcs[minvex][j];dist[j].prevex=minvex;}}}}GraphMatrixgraph;voidinitgraph(){inti,j;graph.n=6;for(i=0;i<graph.n;i++)for(j=0;j<graph.