北科大_ 數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)報(bào)告

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

2、實(shí)現(xiàn)、結(jié)果有效性分析的能力。2 實(shí)驗(yàn)要求（1）由于在有限的實(shí)驗(yàn)課內(nèi)學(xué)時(shí)難以較好完成所有實(shí)驗(yàn)內(nèi)容，因此要求在實(shí)驗(yàn)課前自主完成部分實(shí)驗(yàn)或?qū)嶒?yàn)的部分內(nèi)容；（2）對(duì)于每個(gè)實(shí)驗(yàn)都要針對(duì)問題進(jìn)行分析，設(shè)計(jì)出有效的數(shù)據(jù)結(jié)構(gòu)、算法和程序，對(duì)實(shí)現(xiàn)結(jié)果的正確性進(jìn)行測試，給出測試用例和結(jié)果，分析算法的時(shí)間復(fù)雜度、空間復(fù)雜度、有效性和不足，在算法設(shè)計(jì)和實(shí)現(xiàn)過程中體現(xiàn)創(chuàng)新意識(shí)，并能綜合考慮時(shí)空權(quán)衡、用戶的友好性、程序的模塊化和擴(kuò)展性等；（3）完成的每個(gè)實(shí)驗(yàn)需要在實(shí)驗(yàn)課內(nèi)經(jīng)指導(dǎo)教師現(xiàn)場檢查、查看程序代碼，回答指導(dǎo)教師提出的問題，以確認(rèn)實(shí)驗(yàn)實(shí)際完成的質(zhì)量；（4）在實(shí)驗(yàn)報(bào)告中體現(xiàn)問題分析、算法思路、算法描述、程序?qū)崿F(xiàn)和驗(yàn)證、

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

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

5、knode); /建立頭節(jié)點(diǎn) r=H;scanf(“%d”,&a); /輸入一個(gè)數(shù)據(jù)while(a!=0) P=(Link)malloc(sizeof(Linknode);/申請(qǐng)新節(jié)點(diǎn) P->data=a; /存入數(shù)據(jù) r->next=P; /新節(jié)點(diǎn)鏈入表尾 r=P; scanf(“%d”,&a); /輸入下一個(gè)數(shù)據(jù)r->next=NULL; /將尾節(jié)點(diǎn)的指針域置空 return(H); /返回已創(chuàng)建的頭節(jié)點(diǎn) Link Adjmax(Link H) /求鏈表中相鄰兩節(jié)點(diǎn)data值之和為最大的第一節(jié)點(diǎn)的指針的算法 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時(shí)返回 i=p->data+q->data; /相鄰兩節(jié)點(diǎn)data值之和 while(q->next)p=q;q=q->next; /取下一對(duì)相鄰節(jié)點(diǎn)的指針 j=p->data+q->data;if(j>i)p1=p;i=j; /取和為最大的第一節(jié)點(diǎn)指針 return (p1);1.2.3 程序?qū)崿F(xiàn)#include<stdio.h>#include<stdlib.h>

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

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

9、din),scanf("%f",&b); /判斷輸入的是否是整數(shù) a=(int)b; if(c!=1|a!=b|a<-32768|a>32767) printf("非法輸入!請(qǐng)重新輸入!n"); while(c!=1|a!=b|a<-32768|a>32767); r->next=NULL; /將尾節(jié)點(diǎn)的指針域置空 return(H); /返回已創(chuàng)建的頭節(jié)點(diǎn) Link Adjmax(Link H) /求鏈表中相鄰兩節(jié)點(diǎn)data值之和為最大的第一節(jié)點(diǎn)的指針的算法 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時(shí)返回 i=p->data+q->data; /相鄰兩節(jié)點(diǎn)data值之和 while(q->next)p=q;q=q->next; /取下一對(duì)相鄰節(jié)點(diǎn)的指針 j=p->data+q->data;if(j>i)p1=p;i=j; /取和為最大的第一節(jié)點(diǎn)指針 return (p1);void main() /主函數(shù) Link A,B,p,q;int a,b;doprintf("請(qǐng)輸入一組整數(shù)

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

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

13、：算法正確，算法易讀、易編碼和易于調(diào)試不足：每個(gè)數(shù)據(jù)輸入之間只能用回車區(qū)分。2 實(shí)驗(yàn)2：棧的應(yīng)用2.1 實(shí)驗(yàn)內(nèi)容設(shè)操作數(shù)：0，1，2，8，9（可擴(kuò)充）；運(yùn)算符：+，-，*，/，（，），#（#號(hào)為結(jié)束）。輸入中綴表達(dá)式，將其轉(zhuǎn)換成后綴表達(dá)式，然后計(jì)算，輸出結(jié)果。例如：輸入中綴表達(dá)式5+(4-2)*3 #，將其轉(zhuǎn)換成后綴表達(dá)式：542-3*+#，然后計(jì)算，本例結(jié)果為11。2.2 主要步驟2.2.1 問題分析與算法思路利用棧來寫程序。首先要獲得中綴表達(dá)式，再利用一個(gè)調(diào)用函數(shù)是中綴表達(dá)式變?yōu)楹缶Y表達(dá)式。再用一個(gè)函數(shù)求后綴表達(dá)式的值。利用一個(gè)調(diào)用函數(shù)取判斷中綴表達(dá)式的合法性。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進(jìn)棧slink p;p=(slink)malloc(sizeof(snode); /生成進(jìn)棧p節(jié)點(diǎn) p->data=x; /存入新元素 p->next=*s; /p節(jié)點(diǎn)作為新的棧頂鏈入 *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) /中綴表達(dá)式B到后綴表達(dá)式E的轉(zhuǎn)換 int i=0,j=0;char x; int a;slink s=NULL; /置空棧 Clearstack(s);Push(&s,'#'); /結(jié)束符入棧 dox=Bi+; /掃描當(dāng)前表達(dá)式分量x switch(x) case ' ':break; case '#':while(!Emptystack(s) Ej+=' &

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

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

20、#') /掃描每一個(gè)字符是送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í)行相應(yīng)運(yùn)算結(jié)果進(jìn)棧 default: g=0;g1=0; /獲取操作數(shù) while(Ei!=' ') g1=Ei-'0' g=g*10+g1; i+; Push1(&s,g); /操作數(shù)進(jìn)棧 i+;if(!Emptystack1(s) return(Getstop1(s); /返回結(jié)果 Clearstack1(s);2.2.3 程序?qū)崿F(xiàn)#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進(jìn)棧slink p;p=(slink)malloc(sizeof(snode); /生成進(jìn)棧p節(jié)點(diǎn) p->data=x; /存入新元素 p->next=*s; /p節(jié)點(diǎn)作為新的棧頂鏈入 *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進(jìn)棧slink1 p;p=(slink1)malloc(sizeof(snode1); /生成進(jìn)棧p節(jié)點(diǎn) p->data=x; /存入新元素 p->next=*s; /p節(jié)點(diǎn)作為新的棧頂鏈入 *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) /中綴表達(dá)式B到后綴

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

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

29、break; default:Ej+=x; /操作數(shù)直接輸出 while(x!='#'); Ej='0'Clearstack(s);int Ecount(char E) /后綴表達(dá)式求值 int i=0,g=0,k=0,d=0,d1,g1;char x;int z,a,b;slink1 s=NULL; /置?？?while(Ei!='#') /掃描每一個(gè)字符是送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í)行相應(yīng)運(yùn)算結(jié)果進(jìn)棧 default: g=0;g1=0; /獲取操作數(shù) while(Ei!=' &

31、#39;) g1=Ei-'0' g=g*10+g1; i+; Push1(&s,g); /操作數(shù)進(jìn)棧 i+;if(!Emptystack1(s) return(Getstop1(s); /返回結(jié)果 Clearstack1(s);int pd(char B) /判斷輸入錯(cuò)誤 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; /一個(gè)操作數(shù)之間不能有空格 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("非法輸入!請(qǐng)重新輸入!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("非法輸入!請(qǐng)重新輸入!n");return(0);break; k=i+1; while(Bk=' ') k+; switch(Bk) /'+',

35、9;-'，'*'，'/'左邊不能有 '+'，'-'，'*'，'/'，')','#'case '+':case '-':case '*':case '/':case ')':case '#':printf("非法輸入!請(qǐng)重新輸入!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("非法輸入!請(qǐng)重新輸入!n");return(0);break; k=i+1; while(Bk=' ') k+; switch(Bk) /'('右邊不能有 '+','-','*','/','#'case '+':case '-':case '*':case '/':case '#':printf("非法輸入!請(qǐng)重新輸入!n");return

38、(0);break; break;case ')': /')'左邊不能有'(' j=i-1; while(Bj=' ') j-; switch(Bj) case '(':printf("非法輸入!請(qǐng)重新輸入!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("非法輸入!請(qǐng)重新輸入!n");return(0);break; break; case '0':break; default:printf("8非法輸入!請(qǐng)重新輸入!n");return(0); i+; if(B0='#') printf

40、("表達(dá)式為空!請(qǐng)重新輸入!n");return(0); else if (Bc-1!='#') printf("9非法輸入!請(qǐng)重新輸入!n");return(0); void main() int a,b,c,d;char B100,E100;dodo printf("請(qǐng)輸入中綴表達(dá)式: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("后綴表達(dá)式為:n"); printf("%sn",E); a=Ecount(E); printf("結(jié)果=%dn",a); printf("是否繼續(xù)?是:1否:0n"); scanf("%d",&c); while(c=1); 2.3 結(jié)果分析輸入的中綴表達(dá)式為：5+(4-2)*3，輸出的后綴表達(dá)式為：5 4 2 -3 * +，后綴表達(dá)式求值結(jié)果為：11。結(jié)果是正確的。輸入的中綴表達(dá)式為：123+45*2-56，輸出的后綴表達(dá)式為：123

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

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

44、=NULL;q->rear=q->front;void Creatqueue(linkqueue *q) /創(chuàng)建隊(duì)列 q->front=(Qlink)malloc(sizeof(Qnode);q->front->next=NULL;q->rear=q->front;int Emptyqueue(linkqueue *q) /判斷隊(duì)列是否為空if(q->front=q->rear) return (1);else return (0);void Enqueue(linkqueue *q,char e) /元素進(jìn)隊(duì)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) /元素出隊(duì)Qlink p;if(Emptyqueue(q) return;elsep=q->front;q->front=p->next;free(p);return(q->front->data);3.2.3 程序?qū)崿F(xiàn)#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) /清空隊(duì)列q->front->next=NULL;q->rear=q->front;void Creatqueue(linkqueue *q) /創(chuàng)建隊(duì)列 q->front=(Qlink)malloc(sizeof(Qnode);q->front->next=NULL;q->rear=q->front;int Emptyqueue(linkqueue *q) /判斷隊(duì)列是否為空if(q->front=q->rear) return (1);else return (0);void Enqueue(linkqueue *q,char e) /元素進(jìn)隊(duì)Qlink p;p=(Qlink)malloc(sizeof(Qnode);p->data=e;p->next=NULL;q->rear->next=p;q->rear=p;char Dequeue(linkqueue *q