1、北京科技大學計算機與通信工程學院實驗報告實驗名稱：數據結構上機實驗學生姓名：專業：計算機科學與技術班級：學號：指導教師：實驗成績：實驗地點：實驗時間：2021年_6_月一、實驗目的與實驗要求1 實驗目的(1)加深對常用數據結構和算法設計根本思路、思考方法及其適用場合的理解,并能運用于解決實際問題；(2)能根據特定問題需求,分析建立計算模型(包括邏輯結構和物理結構)、 設計算法和程序,并在設計中綜合考慮多種因素,對結果的有效性進行分析；(3)練習分析問題、解決問題的水平以及自主學習與程序設計實踐水平；(4)形成將非數值型問題抽象為計算模型到算法設計、程序實現、結果有效性分析的水平.2 實驗要求(

2、1)由于在有限的實驗課內學時難以較好完成所有實驗內容,因此要求在實驗課前自主完成局部實驗或實驗的局部內容；(2)對于每個實驗都要針對問題進行分析,設計出有效的數據結構、 算法和程序,對實現結果的正確性進行測試,給出測試用例和結果,分析算法的時間復雜度、空間復雜度、有效性和缺乏,在算法設計和實現過程中表達創新意識,并能綜合考慮時空權衡、用戶的友好性、程序的模塊化和擴展性等；(3)完成的每個實驗需要在實驗課內經指導教師現場檢查、查看程序代碼,答復指導教師提出的問題,以確認實驗實際完成的質量；(4)在實驗報告中表達問題分析、算法思路、算法描述、程序實現和驗證、算法和結果的有效性分析.二、實驗設備(環

3、境)及要求Win7、C 語言、Dev-C+三、實驗內容、步驟與結果分析1 實驗 1:鏈表的應用1.1 實驗內容輸入數據(設為整型)建立單鏈表,并求相鄰兩節點 data 值之和為最大的第一節點.1.2 主要步驟1.2.1 問題分析與算法思路采用單鏈表結構.新建鏈表：每輸入一個整數數據,建立一個新節點.循環操作直到輸入結束符結束輸入.利用一個調用函數求兩節點 data 值之和為最大的第一節點：假設,設一個 int 類型的變量 s=0,讀取鏈表中第一個節點的數據以及它的第二個節點的數據,并計算它們之和 a,再計算第二個節點數據和第三個節點數據之和 b,如果 ab,那么 s=a;反之,那么 s=bo

4、利用 if 語句和 while 語句實現.每當輸入一個數據,程序會判斷輸入的時候輸入的數據是否是整數,如果不是整數,要求重新輸入.1.2.2 算法描述inta;LinkH,P,r;/H,P,r 分別為表頭,新節點和表尾節點指針H=(Link)malloc(sizeof(Linknode);建立頭節點r=H;scanf(%d,&a);while(a!=0)(P=(Link)malloc(sizeof(Linknode);/P-data=a;r-next=P;r=P;scanf(%d,&a);r-next=NULL;return(H);LinkAdjmax(LinkH)求鏈表中相鄰

5、兩節點法(Linkp,p1,q;inti,j;p=p1=H-next;if(p1=NULL)return(p1);q=p-next;if(q=NULL)return(p1);i=p-data+q-data;while(q-next)(p=q;q=q-next;取下一對相鄰節點的指針typedefintdatatype;typedefstructnode(datatypedata;structnode*next;Linknode,*Link;LinkCreatelist()(/設當前數據元素為整型節點類型節點的數據域節點的后繼指針域創立單鏈表的算法/輸入一個數據申請新節點存入數據新節點鏈入表尾輸

6、入下一個數據將尾節點的指針域置空返回已創立的頭節點data值之和為最大的第一節點的指針的算表空返回表長=1 時返回相鄰兩節點 data 值之和j=p-data+q-data;if(ji)(p1=p;i=j;/取和為最大的第一節點指針)return(p1);)1.2.3 程序實現#include#includetypedefintdatatype;/設當前數據元素為整型typedefstructnode節點類型(datatypedata;節點的數據域structnode*next;/節點的后繼指針域Linknode,*Link;/linknode 為節點說明符,link 為節點指針說明符Link

7、Createlist()/創立單鏈表的算法(inta,c;floatb;LinkH,P,r;/H,P,r 分別為表頭,新節點和表尾節點指針H=(Link)malloc(sizeof(Linknode);建立頭節點r=H;do(c=(fflush(stdin),scanf(%f,&b);/printf(%d,c);判斷輸入的是否是整數a=(int)b;if(c!=1|a!=b|a32767)printf(非法輸入！請重新輸入！n);while(c!=1|a!=b|a32767);while(a!=0)(P=(Link)malloc(sizeof(Linknode);/申請新節點 P-da

8、ta=a;存入數據r-next=P;新節點鏈入表尾r=P;do(c=(fflush(stdin),scanf(%f,&b);判斷輸入的是否是整數a=(int)b;if(c!=1|a!=b|a32767)printf(非法輸入！請重新輸入！n);while(c!=1|a!=b|a32767);)r-next=NULL;將尾節點的指針域置空return(H);返回已創立的頭節點LinkAdjmax(LinkH)求鏈表中相鄰兩節點 data 值之和為最大的第一節點的指針的算voidmain()主函數LinkA,B,p,q;inta,b;doprintf(請輸入一組整數(以0為結束符,數之間回

9、車):n);p=A=Createlist();/創立新鏈表B=Adjmax(A);求鏈表中相鄰兩節點 data 值之和為最大的第節點的指針a=(int)(B-data);取第一節點的 data 值printf(第一節點的 data 值為:dn,a);while(p-next)/釋放鏈表空間q=p;p=p-next;free(q);free(p);printf(是否繼續輸入下一組整數：是:1,否:0n);Linkp,p1,q;inti,j;p=p1=H-next;if(p1=NULL)return(p1);q=p-next;if(q=NULL)return(p1);i=p-data+q-data

10、;while(q-next)p=q;q=q-next;j=p-data+q-data;if(ji)p1=p;i=j;return(p1);表空返回表長=1 時返回相鄰兩節點 data 值之和取下一對相鄰節點的指針/取和為最大的第一節點指針scanf(%d,&b);while(b);)1.3 結果分析輸入的數組為：26473,輸出結果：第一節點為 4.結果是正確的.輸入的數組為：4521456421454230,輸出結果：第一節點為 21.結果是正確的.輸入的數組為：457235647012241214524,輸出結果：第一節點為 70.結果是正確的.如下圖,只要輸入的數據不是整數(字符

11、或小數),或者輸入的整數不在32768,32767這個范圍,程序會用非法輸入！請重新輸入廠提示用戶,直到用戶輸入正確的數據.1.3.2 算法和結果的有效性分析時間復雜度：O(n)空間復雜度：不復雜有效性：算法正確,算法易讀、易編碼和易于調試缺乏：每個數據輸入之間只能用回車區分.2實驗實驗2:棧的應用2.1實驗內容設操作數：0,1,2,8,9(可擴充)；運算符：+,-,*,/,(,),#(#號為結束).輸入中綴表達式,將其轉換成后綴表達式,然后計算,輸出結果.例如：輸入中綴表達式 5+(4-2)*3#,將其轉換成后綴表達式：542-3*+#,然后計算,本例結果為 11.2.2主要步驟2.2.1

12、問題分析與算法思路利用棧來寫程序.首先要獲得中綴表達式,再利用一個調用函數是中綴表達式變為后綴表達式.再用一個函數求后綴表達式的值.利用一個調用函數取判斷中綴表達式的合法性.2.2.2 算法描述typedefstructnode(chardata;structnode*next;snode,*slink;typedefstructnodel(intdata;structnodel*next;snode1,*slink1;voidClearstack(slinks)置棧空(s=NULL;intEmptystack(slinks)判斷棧是否為空(if(s=NULL)return(1);棧空返回 1

13、elsereturn(0);棧非空返回 0charGetstop(slinks)取棧頂元素(if(s!=NULL)return(s-data);return(0);voidPush(slink*s,charx)元素 x 進棧(slinkp;p=(slink)malloc(sizeof(snode);生成進棧 p 節點p-data=x;/存入新元素p-next=*s;/p 節點作為新的棧頂鏈入*s=p;charPop(slink*s)出棧(charx;slinkp;if(Emptystack(*s)return(-1);棧空,返回-1else(x=(*s)-data;p=*s;*s=(*s)-n

14、ext;free(p);return(x);成功intPrecede(charx,chary)(inta,b;switch(x)(case#:case(:a=0;break;case+:case-:a=1;break;casecase/:a=2;break;switch(y)(case+:case-:b=1;break;case*:case/:b=2;break;case(:b=3;break;if(a=b)return(1);elsereturn(0);voidMid_post(charE,charB 口)中綴表達式 B 到后綴表達式 E 的轉換(inti=0,j=0;charx;inta;

15、slinks=NULL;置空棧 Clearstack(s);Push(&s,#);/結束符入棧do(x=Bi+;掃描當前表達式分量 xswitch(x)(case:break;case#:(while(!Emptystack(s)(Ej+=;Ej+=Pop(&s);break;case):(while(Getstop(s)!=()Ej+=；Ej+=Pop(&s);)反復出棧直到遇到(Pop(&s);/退掉(break;case+:casecase/:case(:(while(Precede(Getstop(s),x)棧頂運算符(Q1)與 x 比擬(Ej+=;Ej

16、+=Pop(&s);/Q1=x 時,輸出棧頂符兵退棧/Ej+=;Push(&s,x);/Q1x 時,x 進棧Ej+=;break;default:Ej+=x;/操作數直接輸出while(x!=#);Ej=0;Clearstack(s);intEcount(charE)后綴表達式求值(inti=0,g=0,k=0,d=0,d1,g1;charx;intz,a,b;slink1s=NULL;/置棧空/比擬 x 是否大于y棧非空時while(Ei!=#)掃描每一個字符是送 x(x=Ei;switch(x)(case:break;case+:b=Pop1(&s);a=Pop1(

17、&s);z=a+b;Push1(&s,z);break;case-:b=Pop1(&s);a=Pop1(&s);z=a-b;Push1(&s,z);break;case*:b=Pop1(&s);a=Pop1(&s);z=a*b;Push1(&s,z);break;case/:b=Pop1(&s);a=Pop1(&s);z=a/b;Push1(&s,z);break; 執行相應運算結果進棧default:(g=0;g1=0;while(Ei!=)(g1=Ei-0;g=g*10+g1;i+；)Push1(&am

18、p;s,g);操作數進棧)i+;)if(!Emptystack1(s)return(Getstop1(s);返回結果Clearstack1(s);)2.2.3 程序實現#include#include#includetypedefstructnode(chardata;structnode*next;snode,*slink;typedefstructnode1(intdata;structnode1*next;snode1,*slink1;voidClearstack(slinks)置棧空(s=NULL;intEmptystack(slinks)判斷棧是否為空(if(s=NULL)retur

19、n(1);棧空返回 1elsereturn(0);棧非空返回 0charGetstop(slinks)/取棧頂元素(if(s!=NULL)return(s-data);return(0);voidPush(slink*s,charx)元素 x 進棧(slinkp;p=(slink)malloc(sizeof(snode);生成進棧 p 節點/獲取操作數/存入新元素/p 節點作為新的棧頂鏈入)charPop(slink*s)/出棧(charx;slinkp;if(Emptystack(*s)return(-1);棧空,返回-1else(x=(*s)-data;p=*s;*s=(*s)-next;

20、free(p);return(x);成功)voidPush1(slink1*s,intx)元素 x 進棧(slink1p;p=(slink1)malloc(sizeof(snode1);生成進棧 p 節點p-data=x;/存入新元素p-next=*s;/p 節點作為新的棧頂鏈入*s=p;)intPop1(slink1*s)/出棧(intx;slink1p;if(Emptystack1(*s)return(-1);棧空,返回-1else(x=(*s)-data;p=*s;*s=(*s)-next;free(p);return(x);成功)intEmptystack1(slink1s)判斷棧是否

21、為空(if(s=NULL)return(1);棧空返回 1elsereturn(0);棧非空返回 0)voidClearstack1(slink1s)/置棧空(s=NULL;p-data=x;p-next=*s;*s=p;)intGetstop1(slink1s)/取棧頂元素(if(s!=NULL)return(s-data);return(0);)intPrecede(charx,chary)/比擬 x 是否大于y(inta,b;switch(x)(case#:case(:a=0;break;case+:case-:a=1;break;casecase/:a=2;break;)switch(

22、y)(case+:case-:b=1;break;casecase/:b=2;break;case(:b=3;break;)if(a=b)return(1);elsereturn(0);)voidMid_post(charE,charB)中綴表達式 B 到后綴表達式 E 的轉換(inti=0,j=0;charx;inta;slinks=NULL;置空棧 Clearstack(s);Push(&s,#);/結束符入棧do(x=Bi+;掃描當前表達式分量 xswitch(x)(case:break;case#:(while(!Emptystack(s)(Ej+=;棧非空時Ej+=Pop(&

23、amp;s);)break;case):(while(Getstop(s)!=()(Ej+=;Ej+=Pop(&s);Pop(&s);break;case+:case-:反復出棧直到遇到(退掉(casecase/:case(:(while(Precede(Getstop(s),x)棧頂運算符(Q1)與 x 比擬(Ej+=;Ej+=Pop(&s);/Q1=x 時,輸出棧頂符兵退棧Push(&s,x);/Q1front-next=NULL;q-rear=q-front;voidCreatqueue(linkqueue*q)/創立隊列(q-front=(Qlink)m

24、alloc(sizeof(Qnode);q-front-next=NULL;q-rear=q-front;intEmptyqueue(linkqueue*q)判斷隊列是否為空(if(q-front=q-rear)return(1);elsereturn(0);voidEnqueue(linkqueue*q,chare)元素進隊(Qlinkp;p=(Qlink)malloc(sizeof(Qnode);p-data=e;p-next=NULL;q-rear-next=p;q-rear=p;charDequeue(linkqueue*q)元素出隊(Qlinkp;if(Emptyqueue(q)re

25、turn;else(p=q-front;q-front=p-next;free(p);return(q-front-data);3.2.3 程序實現#include#include#includetypedefstructnode(chardata;structnode*next;Qnode,*Qlink;typedefstruct(Qnode*front,*rear;linkqueue;voidClearqueue(linkqueue*q)清空隊列(q-front-next=NULL;q-rear=q-front;voidCreatqueue(linkqueue*q)/創立隊列(q-fron

26、t=(Qlink)malloc(sizeof(Qnode);q-front-next=NULL;q-rear=q-front;intEmptyqueue(linkqueue*q)判斷隊列是否為空(if(q-front=q-rear)return(1);elsereturn(0);voidEnqueue(linkqueue*q,chare)元素進隊(Qlinkp;p=(Qlink)malloc(sizeof(Qnode);p-data=e;p-next=NULL;q-rear-next=p;q-rear=p;charDequeue(linkqueue*q)元素出隊(Qlinkp;if(Empty

27、queue(q)return;else(p=q-front;q-front=p-next;free(p);return(q-front-data);voidmain()(chara,b;intc;linkqueueq;Creatqueue(&q);printf(請輸入隊列元素!n);doa=getchar();switch(a)case:break;case0:if(Emptyqueue(&q)printf(隊列為空!n);printf(請繼續輸入!n);c=1;elseb=Dequeue(&q);printf(%c 出隊n,b);printf(請繼續輸入！n);bre

28、ak;case:if(Emptyqueue(&q)printf(隊列為空！n);return;elseprintf(全部元素出隊：n);while(Emptyqueue(&q)!=1)b=Dequeue(&q);printf(%c,b);printf(n);return;break;casen:break;default:Enqueue(&q,a);c=1;break;while(c);3.3結果分析3.3.1 測試當隊列為空時,輸入 0 或,都會有提示語句：隊列為空！并且之后程序停止.3.3.2 算法和結果的有效性分析時間復雜度：O(n)空間復雜度：不復雜有效

29、性：算法正確、算法易讀、易編碼和易于調試當隊列為空時,輸入 0,會有提示語句：隊列為空F：課件課件 數強結構讓機題灼數強結構讓機題灼 aexe青繼續輸入Focessexitedwithreturnualue部元素出隊;anykey 七口 cuntinLis4 實驗 4:Huffman 樹及編碼4.1 實驗內容輸入電文字符集 D 及各字符出現的概率 F,例如：D=a,b,c,d,e,f,g,h(字符數 n=8)F=5,29,7,8,14,23,3,11(%)編寫完成以下功能的程序：構造關于 F 的 Huffman 樹；求出并打印 D 中各字符的 Huffman 編碼.4.2 主要步驟4.2.1

30、問題分析與算法思路先構造一個建立 Huffman 樹的函數后構造一個求 Huffman 編碼的函數4.2.2 算法描述 typedefstruct定義節點intwi;/節點權值chardata;設節點 data 值為字符intparent,Lchild,Rchild;/雙親及左、右指針huffm;/H 樹節點說明符voidHuffman_tree(huffmHT 口,intF,intp,intq)構造 H 樹的算法inti,j,p1,p2;intw,s1,s2;for(i=1;i=q;i+)初始化HTi.wi=0;HTi.parent=0;HTi.Lchild=HTi.Rchild=0;for

31、(i=1;i=p;i+)HTi.wi=Fi-1;/ 存 入 權值for(i=p+1;i=q;i+)p1=p2=0;p1、p2 為所選權值最小的根節點序號s1=s2=max;for(j=1;j=i-1;j+)if(HTj.parent=0)if(HTj.wis1)(s2=s1;以 j 節點為第一個權值最小的根節點s1=HTj.wi;p2=p1;P1=j;elseif(HTj.wis2)(s2=HTj.wi;以 j 節點為第二個權值最小的根節點p2=j;HTp1.parent=HTp2.parent=i;構造新數HTi.Lchild=p1;HTi.Rchild=p2;HTi.wi=HTp1.wi+

32、HTp2.wi;權值相加送新節點typedefstruct(charbitsn+1;intstart;charch;ctype;voidHuffman_code(ctypecode,huffmHT,charD,intF,intp,intq)求 n 個字符的 Huffman 編碼的算法(inti,j,a,s;ctypemd;存放當前編碼的變量for(i=1;i=p;i+)/讀入待編碼的字符(codei.ch=Di-1;HTi.data=codei.ch;for(i=1;i=p;i+)(md.ch=codei.ch;md.start=p+1;s=i;a=HTi.parent;/a 為 s 父節點地

33、址 while(a!=0)/a 存在時(md.start-;if(HTa.Lchild=s)從 HR1HTi-1中選兩個權值最小的根節點md.bitsmd.start=0;/左走一步為0elsemd.bitsmd.start=1;右走一步為1s=a;a=HTa.parent;codei=md;存入第 i 字符的編碼4.2.3 程序實現#include# definen20/最大容量# definem2*n-1/H 樹的節點數# definemax99typedefstruct定義節點(intwi;節點權值chardata;/設節點 data 值為字符intparent,Lchild,Rchil

34、d;/雙親及左、右指針huffm;/H 樹節點說明符voidHuffman_tree(huffmHT,intF,intp,intq)構造 H 樹的算法(inti,j,p1,p2;intw,s1,s2;for(i=1;i=q;i+)初始化(HTi.wi=0;HTi.parent=0;HTi.Lchild=HTi.Rchild=0;for(i=1;i=p;i+)(HTi.wi=Fi-1;存入權值for(i=p+1;i=q;i+)p1=p2=0;s1=s2=max;for(j=1;j=i-1;j+)if(HTj.parent=0)點if(HTj.wis1)(s2=s1;以 j 節點為第一個權值最小的

35、根節點s1=HTj.wi;p2=p1;p1=j;elseif(HTj.wis2)(s2=HTj.wi;以 j 節點為第二個權值最小的根節點p2=j;HTp1.parent=HTp2.parent=i;構造新數HTi.Lchild=p1;HTi.Rchild=p2;HTi.wi=HTp1.wi+HTp2.wi;/權值相加送新節點typedefstruct(charbitsn+1;intstart;charch;ctype;voidHuffman_code(ctypecode,huffmHT,charD,intF 口,intp,intq)求 n 個字符的 Huffman 編碼的算法(inti,j,

36、a,s;ctypemd;存放當前編碼的變量for(i=1;i=p;i+)讀入待編碼的字符(codei.ch=Di-1;HTi.data=codei.ch;for(i=1;i=p;i+)(md.ch=codei.ch;md.start=p+1;s=i;a=HTi.parent;/a 為 s 父節點地址 while(a!=0)/a 存在時md.start-;if(HTa.Lchild=s)md.bitsmd.start=0;左走一步為0elsemd.bitsmd.start=1;右走一步為1s=a;a=HTa.parent;codei=md;/存入第 i 字符的編碼voidmain()intF30

37、;inti,j,k,p0=0,p1=0,q,d,f,p;charD50;dododop0=0;printf(請輸入字符集 D!(最多 20個字符,以#為結束符)n);scanf(%s,&D);for(k=0;kn)printf(超出范圍！n);d=1;D50=fflush(stdin);elsed=0;while(d);printf(請輸入各字符出現的概率集 F!(以-1 為結束符)n);for(i=0;i50;i+)(scanf(%d,&Fi);if(Fi=-1)break;p1=0;for(k=0;k50;k+)if(Fk!=-1)+p1;elsebreak;if(Fp1!

38、=-1)(printf(非法輸入!n);d=1;if(p!=p1)(printf(D 的元素個數與 F 的元素個數不等！n 請重新輸入!n);d=1;while(d);q=2*p-1;huffmHTq+1;Huffman_tree(HT,F,p,q);printf(打印編碼:n);ctypecodep+1;Huffman_code(code,HT,D,F,p,q);/p1、p2 為所選權值最小的根節點序號從 HR1HTi-1中選兩個權值最小的根節printf(%s,D);printf(字符tbitsn);for(i=1;i=p;i+)打印編碼(printf(%ct,codei.ch);for(

39、j=codei.start;jdata.key,p-data.key)=0)/S 節點已存在,返回(free(S);return(T);if(strcmp(S-data.key,p-data.key)Lchild;elsep=p-Rchild;向右找)if(strcmp(S-data.key,q-data.key)Lchild=S;/S 為 q 的左子插入elseq-Rchild=S;/S 為 p 的左子插入return(T);)BSPCreateBst()建立二叉排序樹inti,j,c;BSPT,S;charkey20;T=NULL;置空樹doscanf(%s,&key);if(ke

40、y0=.)printf( 句 子 為 空！請 重 新 輸 入！n);while(key0=.);c=strlen(key);while(keyc-1!=.)S=(BSP)malloc(sizeof(BSN);申請一個 S 節點向左找for(i=0;idata.keyi=keyi;S-data.w=i;elseS-data.keyi=0;break;S-Lchild=S-Rchild=NULL;T=BSTinsert(T,S);scanf(%s,&key);c=strlen(key);if(keyc-1=.)keyc-1=0;S=(BSP)malloc(sizeof(BSN);for(i

41、=0;idata.keyi=keyi;S-data.w=i;)else(S-data.keyi=0;break;)S-Lchild=S-Rchild=NULL;T=BSTinsert(T,S);)return(T);)5.2.3 程序實現#include#include#include#definemax200typedefstructnode(charkey20;intw;Retype;typedefstructBsnode(Retypedata;structBsnode*Lchild,*Rchild;BSN,*BSP; 二叉排序樹節點/節點或記錄數據左右子樹指針節點及指針說明符BSPBST

42、insert(BSPT,BSPS)/二叉排序樹的插入算法(BSPq,p;if(T=NULL)/樹為空日以 S 為根return(S);p=T;/q 為 p 的父節點指針q=NULL;while(p)尋找插入位置(q=p;if(strcmp(S-data.key,p-data.key)=0)/S 節點已存在,返回(free(S);return(T);if(strcmp(S-data.key,p-data.key)Lchild; 向左找elsep=p-Rchild;)if(strcmp(S-data.key,q-data.key)Lchild=S;elseq-Rchild=S;return(T);)BSPCreateBs