北科大_ 數據結構上機實驗報告

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

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

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

4、之，則s=b。利用if語句和while語句實現。每當輸入一個數據，程序會判斷輸入的時候輸入的數據是否是整數，如果不是整數，要求重新輸入。1.2.2 算法描述typedef int datatype; /設當前數據元素為整型 typedef struct node /節(jié)點類型 datatype data; /節(jié)點的數據域 struct node *next; /節(jié)點的后繼指針域 Linknode,*Link; Link Createlist() /創(chuàng)建單鏈表的算法 int a;Link H,P,r; /H,P,r分別為表頭，新節(jié)點和表尾節(jié)點指針 H=(Link)malloc(sizeof(Lin

5、knode); /建立頭節(jié)點 r=H;scanf(“%d”,&a); /輸入一個數據while(a!=0) P=(Link)malloc(sizeof(Linknode);/申請新節(jié)點 P->data=a; /存入數據 r->next=P; /新節(jié)點鏈入表尾 r=P; scanf(“%d”,&a); /輸入下一個數據r->next=NULL; /將尾節(jié)點的指針域置空 return(H); /返回已創(chuàng)建的頭節(jié)點 Link Adjmax(Link H) /求鏈表中相鄰兩節(jié)點data值之和為最大的第一節(jié)點的指針的算法 Link p,p1,q;int i,j;p=p1

6、=H->next;if(p1=NULL) return(p1); /表空返回 q=p->next;if(q=NULL) return(p1); /表長=1時返回 i=p->data+q->data; /相鄰兩節(jié)點data值之和 while(q->next)p=q;q=q->next; /取下一對相鄰節(jié)點的指針 j=p->data+q->data;if(j>i)p1=p;i=j; /取和為最大的第一節(jié)點指針 return (p1);1.2.3 程序實現#include<stdio.h>#include<stdlib.h>

7、;typedef int datatype; /設當前數據元素為整型 typedef struct node /節(jié)點類型 datatype data; /節(jié)點的數據域 struct node *next; /節(jié)點的后繼指針域 Linknode,*Link; /linknode為節(jié)點說明符，link為節(jié)點指針說明符 Link Createlist() /創(chuàng)建單鏈表的算法 int a,c;float b;Link H,P,r; /H,P,r分別為表頭，新節(jié)點和表尾節(jié)點指針 H=(Link)malloc(sizeof(Linknode); /建立頭節(jié)點 r=H;doc=(fflush(stdin),

8、scanf("%f",&b);/printf("%d",c); /判斷輸入的是否是整數a=(int)b;if(c!=1|a!=b|a<-32768|a>32767) printf("非法輸入!請重新輸入!n");while(c!=1|a!=b|a<-32768|a>32767);while(a!=0) P=(Link)malloc(sizeof(Linknode);/申請新節(jié)點 P->data=a; /存入數據 r->next=P; /新節(jié)點鏈入表尾 r=P; do c=(fflush(st

9、din),scanf("%f",&b); /判斷輸入的是否是整數 a=(int)b; if(c!=1|a!=b|a<-32768|a>32767) printf("非法輸入!請重新輸入!n"); while(c!=1|a!=b|a<-32768|a>32767); r->next=NULL; /將尾節(jié)點的指針域置空 return(H); /返回已創(chuàng)建的頭節(jié)點 Link Adjmax(Link H) /求鏈表中相鄰兩節(jié)點data值之和為最大的第一節(jié)點的指針的算法 Link p,p1,q;int i,j;p=p1=H-&

10、gt;next;if(p1=NULL) return(p1); /表空返回 q=p->next;if(q=NULL) return(p1); /表長=1時返回 i=p->data+q->data; /相鄰兩節(jié)點data值之和 while(q->next)p=q;q=q->next; /取下一對相鄰節(jié)點的指針 j=p->data+q->data;if(j>i)p1=p;i=j; /取和為最大的第一節(jié)點指針 return (p1);void main() /主函數 Link A,B,p,q;int a,b;doprintf("請輸入一組整數

11、(以0為結束符，數之間回車):n");p=A=Createlist(); /創(chuàng)建新鏈表 B=Adjmax(A); /求鏈表中相鄰兩節(jié)點data值之和為最大的第一節(jié)點的指針 a=(int)(B->data); /取第一節(jié)點的data值 printf("第一節(jié)點的data值為:%dn",a); while(p->next) /釋放鏈表空間 q=p; p=p->next; free(q); free(p); printf("是否繼續(xù)輸入下一組整數:是:1,否:0n"); scanf("%d",&b); w

12、hile(b); 1.3 結果分析輸入的數組為：2 6 4 7 3，輸出結果：第一節(jié)點為4。結果是正確的。輸入的數組為：45 21 456 4 214 54 230，輸出結果：第一節(jié)點為21。結果是正確的。輸入的數組為：45 7 23 564 70 1224 12 145 24，輸出結果：第一節(jié)點為70。結果是正確的。1.3.1 測試如圖所示，只要輸入的數據不是整數（字符或小數），或者輸入的整數不在32768,32767這個范圍，程序會用"非法輸入!請重新輸入!"提示用戶，直到用戶輸入正確的數據。1.3.2 算法和結果的有效性分析時間復雜度：O(n)空間復雜度：不復雜有效性

13、：算法正確，算法易讀、易編碼和易于調試不足：每個數據輸入之間只能用回車區(qū)分。2 實驗2：棧的應用2.1 實驗內容設操作數：0，1，2，8，9（可擴充）；運算符：+，-，*，/，（，），#（#號為結束）。輸入中綴表達式，將其轉換成后綴表達式，然后計算，輸出結果。例如：輸入中綴表達式5+(4-2)*3 #，將其轉換成后綴表達式：542-3*+#，然后計算，本例結果為11。2.2 主要步驟2.2.1 問題分析與算法思路利用棧來寫程序。首先要獲得中綴表達式，再利用一個調用函數是中綴表達式變?yōu)楹缶Y表達式。再用一個函數求后綴表達式的值。利用一個調用函數取判斷中綴表達式的合法性。2.2.2 算法描述type

14、def struct node char data;struct node *next;snode,*slink;typedef struct node1 int data;struct node1 *next;snode1,*slink1;void Clearstack(slink s) /置?？?s=NULL;int Emptystack(slink s) /判斷棧是否為空if(s=NULL) return(1); /?？辗祷?else return(0); /棧非空返回0 char Getstop(slink s) /取棧頂元素if(s!=NULL) return (s->data

15、); return (0); void Push(slink*s,char x) /元素x進棧slink p;p=(slink)malloc(sizeof(snode); /生成進棧p節(jié)點 p->data=x; /存入新元素 p->next=*s; /p節(jié)點作為新的棧頂鏈入 *s=p;char Pop(slink*s) /出棧char x;slink p;if(Emptystack(*s) return (-1); /?？眨祷?1 elsex=(*s)->data;p=*s;*s=(*s)->next;free(p);return (x); /成功 int Prece

16、de(char x,char y) /比較x是否"大于"y int a,b;switch(x)case '#':case '(':a=0;break;case '+': case '-':a=1;break; case '*': case '/':a=2;break; switch(y)case '+':case '-':b=1;break;case '*':case '/':b=2;break;case '

17、(':b=3;break;if(a>=b) return (1);else return (0); void Mid_post(char E,char B) /中綴表達式B到后綴表達式E的轉換 int i=0,j=0;char x; int a;slink s=NULL; /置空棧 Clearstack(s);Push(&s,'#'); /結束符入棧 dox=Bi+; /掃描當前表達式分量x switch(x) case ' ':break; case '#':while(!Emptystack(s) Ej+=' &

18、#39; /棧非空時 Ej+=Pop(&s);break; case ')':while(Getstop(s)!='(') Ej+=' ' Ej+=Pop(&s); /反復出棧直到遇到'(' Pop(&s); /退掉'(' break;case '+':case '-':case '*':case '/':case '(':while(Precede(Getstop(s),x) /棧頂運算符（Q1）與x比較 Ej

19、+=' ' Ej+=Pop(&s); /Q1>=x時，輸出棧頂符兵退棧 /Ej+=' 'Push(&s,x); /Q1<x時，x進棧Ej+=' ' break; default:Ej+=x; /操作數直接輸出 while(x!='#'); Ej='0'Clearstack(s);int Ecount(char E) /后綴表達式求值 int i=0,g=0,k=0,d=0,d1,g1;char x;int z,a,b;slink1 s=NULL; /置?？?while(Ei!='

20、#') /掃描每一個字符是送x x=Ei;switch(x)case ' ':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;case '/':b

21、=Pop1(&s);a=Pop1(&s);z=a/b;Push1(&s,z);break;/執(zhí)行相應運算結果進棧 default: g=0;g1=0; /獲取操作數 while(Ei!=' ') g1=Ei-'0' g=g*10+g1; i+; Push1(&s,g); /操作數進棧 i+;if(!Emptystack1(s) return(Getstop1(s); /返回結果 Clearstack1(s);2.2.3 程序實現#include<stdio.h>#include<stdlib.h>#incl

22、ude<string.h>typedef struct node char data;struct node *next;snode,*slink;typedef struct node1 int data;struct node1 *next;snode1,*slink1;void Clearstack(slink s) /置?？?s=NULL;int Emptystack(slink s) /判斷棧是否為空if(s=NULL) return(1); /?？辗祷?else return(0); /棧非空返回0 char Getstop(slink s) /取棧頂元素if(s!=N

23、ULL) return (s->data); return (0); void Push(slink*s,char x) /元素x進棧slink p;p=(slink)malloc(sizeof(snode); /生成進棧p節(jié)點 p->data=x; /存入新元素 p->next=*s; /p節(jié)點作為新的棧頂鏈入 *s=p;char Pop(slink*s) /出棧char x;slink p;if(Emptystack(*s) return (-1); /?？?，返回-1 elsex=(*s)->data;p=*s;*s=(*s)->next;free(p);re

24、turn (x); /成功 void Push1(slink1*s,int x) /元素x進棧slink1 p;p=(slink1)malloc(sizeof(snode1); /生成進棧p節(jié)點 p->data=x; /存入新元素 p->next=*s; /p節(jié)點作為新的棧頂鏈入 *s=p;int Pop1(slink1*s) /出棧int x;slink1 p;if(Emptystack1(*s) return (-1); /?？?，返回-1 elsex=(*s)->data;p=*s;*s=(*s)->next;free(p);return (x); /成功 int

25、Emptystack1(slink1 s) /判斷棧是否為空if(s=NULL) return(1); /?？辗祷?else return(0); /棧非空返回0 void Clearstack1(slink1 s) /置?？?s=NULL;int Getstop1(slink1 s) /取棧頂元素if(s!=NULL) return (s->data); return (0); int Precede(char x,char y) /比較x是否"大于"y int a,b;switch(x)case '#':case '(':a=0;b

26、reak;case '+': case '-':a=1;break; case '*': case '/':a=2;break; switch(y)case '+':case '-':b=1;break;case '*':case '/':b=2;break;case '(':b=3;break;if(a>=b) return (1);else return (0); void Mid_post(char E,char B) /中綴表達式B到后綴

27、表達式E的轉換 int i=0,j=0;char x; int a;slink s=NULL; /置空棧 Clearstack(s);Push(&s,'#'); /結束符入棧 dox=Bi+; /掃描當前表達式分量x switch(x) case ' ':break; case '#':while(!Emptystack(s) Ej+=' ' /棧非空時 Ej+=Pop(&s);break; case ')':while(Getstop(s)!='(') Ej+=' '

28、; Ej+=Pop(&s); /反復出棧直到遇到'(' Pop(&s); /退掉'(' break;case '+':case '-':case '*':case '/':case '(':while(Precede(Getstop(s),x) /棧頂運算符（Q1）與x比較 Ej+=' ' Ej+=Pop(&s); /Q1>=x時，輸出棧頂符兵退棧 Push(&s,x); /Q1<x時，x進棧Ej+=' '

29、break; default:Ej+=x; /操作數直接輸出 while(x!='#'); Ej='0'Clearstack(s);int Ecount(char E) /后綴表達式求值 int i=0,g=0,k=0,d=0,d1,g1;char x;int z,a,b;slink1 s=NULL; /置?？?while(Ei!='#') /掃描每一個字符是送x x=Ei;switch(x)case ' ':break;case '+':b=Pop1(&s);a=Pop1(&s);z=a+b;Pu

30、sh1(&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;/執(zhí)行相應運算結果進棧 default: g=0;g1=0; /獲取操作數 while(Ei!=' &

31、#39;) g1=Ei-'0' g=g*10+g1; i+; Push1(&s,g); /操作數進棧 i+;if(!Emptystack1(s) return(Getstop1(s); /返回結果 Clearstack1(s);int pd(char B) /判斷輸入錯誤 int i=0,c,j,k; c=strlen(B); /獲取B的長度 while(Bi!='#') switch(Bi) /檢查有無非法字符 case ' ':break; case '0': case '1': case '2

32、': case '3': case '4': case '5': case '6': case '7': case '8': case '9': j=i+1; /一個操作數之間不能有空格 if(Bj=' ') while(Bj=' ') j+; switch(Bj) case '0': case '1': case '2': case '3': case '4':

33、case '5': case '6': case '7': case '8': case '9':printf("非法輸入!請重新輸入!n");return(0);break; break; case '+': case '-': case '*': case '/': j=i-1; while(Bj=' ') j-;switch(Bj) /'+'，'-'，'*'，&#

34、39;/'左邊不能有 '+'，'-'，'*'，'/'，'(','#' case '+':case '-': case '*':case '/':case '(':case '#':printf("非法輸入!請重新輸入!n");return(0);break; k=i+1; while(Bk=' ') k+; switch(Bk) /'+',

35、9;-'，'*'，'/'左邊不能有 '+'，'-'，'*'，'/'，')','#'case '+':case '-':case '*':case '/':case ')':case '#':printf("非法輸入!請重新輸入!n");return(0);break; break;case '(': /'('左邊不

36、能有 '0''9','#',')' j=i-1; while(Bj=' ') j-;switch(Bj)case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':case '#':case ')&

37、#39;:printf("非法輸入!請重新輸入!n");return(0);break; k=i+1; while(Bk=' ') k+; switch(Bk) /'('右邊不能有 '+','-','*','/','#'case '+':case '-':case '*':case '/':case '#':printf("非法輸入!請重新輸入!n");return

38、(0);break; break;case ')': /')'左邊不能有'(' j=i-1; while(Bj=' ') j-; switch(Bj) case '(':printf("非法輸入!請重新輸入!n");return(0);break; k=i+1; while(Bk=' ') k+; /')'右邊不能有'0''9' switch(Bk)case '0': case '1': case &

39、#39;2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':printf("非法輸入!請重新輸入!n");return(0);break; break; case '0':break; default:printf("8非法輸入!請重新輸入!n");return(0); i+; if(B0='#') printf

40、("表達式為空!請重新輸入!n");return(0); else if (Bc-1!='#') printf("9非法輸入!請重新輸入!n");return(0); void main() int a,b,c,d;char B100,E100;dodo printf("請輸入中綴表達式:n");B100=fflush(stdin); gets(B); /輸入B while(B0='0') B100=fflush(stdin); gets(B); b=pd(B); /判斷B是否合法 while(b=0)

41、; Mid_post(E,B); printf("后綴表達式為:n"); printf("%sn",E); a=Ecount(E); printf("結果=%dn",a); printf("是否繼續(xù)?是:1否:0n"); scanf("%d",&c); while(c=1); 2.3 結果分析輸入的中綴表達式為：5+(4-2)*3，輸出的后綴表達式為：5 4 2 -3 * +，后綴表達式求值結果為：11。結果是正確的。輸入的中綴表達式為：123+45*2-56，輸出的后綴表達式為：123

42、 45 2 * + 56 -，后綴表達式求值結果為：157。結果是正確的。輸入的中綴表達式為：7856-56*5+(78-55)，輸出的后綴表達式為：7856 56 5 * - 78 55 - +，后綴表達式求值結果為：7599。結果是正確的。2.3.1 測試輸入各種不合法表達式，例如45 56 - 56#、 56 + 55#等，這時會有提示語句：非法輸入!請重新輸入! 又如，如果直接輸入#，那么中綴表達式為空，這時會有提示語句：表達式為空!請重新輸入!2.3.2 算法和結果的有效性分析時間復雜度：O(n) 空間復雜度：不復雜有效性：算法正確、算法易讀、易編碼和易于調試不足：代碼不夠簡潔3 實

43、驗3：隊列的應用3.1 實驗內容從鍵盤輸入字符x，若x='0'，則進行出隊操作；若x=''，則輸出當前隊列的元素，結束；否則，將x入隊。3.2 主要步驟3.2.1 問題分析與算法思路采用隊列結果當隊列為空時，輸入0或要有相應的結果。3.2.2 算法描述typedef struct nodechar data;struct node *next;Qnode,*Qlink;typedef structQnode *front,*rear;linkqueue;void Clearqueue(linkqueue *q) /清空隊列q->front->next

44、=NULL;q->rear=q->front;void Creatqueue(linkqueue *q) /創(chuàng)建隊列 q->front=(Qlink)malloc(sizeof(Qnode);q->front->next=NULL;q->rear=q->front;int Emptyqueue(linkqueue *q) /判斷隊列是否為空if(q->front=q->rear) return (1);else return (0);void Enqueue(linkqueue *q,char e) /元素進隊Qlink p;p=(Qlin

45、k)malloc(sizeof(Qnode);p->data=e;p->next=NULL;q->rear->next=p;q->rear=p;char Dequeue(linkqueue *q) /元素出隊Qlink p;if(Emptyqueue(q) return;elsep=q->front;q->front=p->next;free(p);return(q->front->data);3.2.3 程序實現#include <stdio.h>#include <string.h>#include<

46、stdlib.h>typedef struct nodechar data;struct node *next;Qnode,*Qlink;typedef structQnode *front,*rear;linkqueue;void Clearqueue(linkqueue *q) /清空隊列q->front->next=NULL;q->rear=q->front;void Creatqueue(linkqueue *q) /創(chuàng)建隊列 q->front=(Qlink)malloc(sizeof(Qnode);q->front->next=NULL;q->rear=q->front;int Emptyqueue(linkqueue *q) /判斷隊列是否為空if(q->front=q->rear) return (1);else return (0);void Enqueue(linkqueue *q,char e) /元素進隊Qlink p;p=(Qlink)malloc(sizeof(Qnode);p->data=e;p->next=NULL;q->rear->next=p;q->rear=p;char Dequeue(linkqueue *q