實(shí)驗(yàn)二棧、隊(duì)列的實(shí)現(xiàn)及應(yīng)用

1、實(shí)驗(yàn)二棧、隊(duì)列的實(shí)現(xiàn)及應(yīng)用實(shí)驗(yàn)課程名：數(shù)據(jù)結(jié)構(gòu)與算法專業(yè)班級(jí)：_ 學(xué)號(hào)： 姓名： _實(shí)驗(yàn)時(shí)間：實(shí)驗(yàn)地點(diǎn)： 指導(dǎo)教師：馮珊 一、實(shí)驗(yàn)?zāi)康?掌握棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，以便在實(shí)際背景下靈活運(yùn)用。2、掌握棧和隊(duì)列的特點(diǎn)，即先進(jìn)后出與先進(jìn)先出的原則。3、掌握棧和隊(duì)列的基本操作實(shí)現(xiàn)方法。二、實(shí)驗(yàn)內(nèi)容一、實(shí)驗(yàn)?zāi)康募耙?、掌握棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，以便在實(shí)際背景下靈活運(yùn)用。2、掌握棧和隊(duì)列的特點(diǎn)，即先進(jìn)后出與先進(jìn)先出的原則。3、掌握棧和隊(duì)列的基本操作實(shí)現(xiàn)方法。二、實(shí)驗(yàn)學(xué)時(shí)2學(xué)時(shí)三、實(shí)驗(yàn)任務(wù)任務(wù)一：（1）實(shí)現(xiàn)棧的順序存儲(chǔ)（2）實(shí)現(xiàn)棧的鏈?zhǔn)酱鎯?chǔ)。任務(wù)二：實(shí)現(xiàn)順序存儲(chǔ)的循環(huán)隊(duì)列，完

2、成鍵盤緩沖區(qū)的功能。四、實(shí)驗(yàn)重點(diǎn)、難點(diǎn)1. 進(jìn)棧、出棧棧頂指針都要改變。2. 隊(duì)空、隊(duì)滿的條件及入隊(duì)、出隊(duì)時(shí)指針的變更。五、操作內(nèi)容與要求1. 任務(wù)一（1）:完成下列程序，該程序?qū)崿F(xiàn)棧的順序存儲(chǔ)結(jié)構(gòu)，構(gòu)建順序棧（棧中的 元素依次為R，S, Y, F, C, T）,依次進(jìn)行進(jìn)棧和出棧操作，判斷棧空和棧滿操作，返回棧 頂元素操作。要求生成順序棧時(shí)，從鍵盤上讀取數(shù)據(jù)元素。(1 )源代碼：#include #include #defi neSTACK INIT SIZE 100#defi neSTACKINCREMENW# defi neOK1# defi neERRORtypedef char SE

3、IemType/*順序棧的存儲(chǔ)類型*/typedef struct/define structure SqStack()SEIemType*base;SEIemType*top;int stacksize; SqStack;/*構(gòu)造空順序棧*/int InitStack(SqStack * S) lnitStack() sub-functionSbase = ( SEIemType*)malloc( STACK_INIT_SIZE*sizeof (SEIemTyp)； if (! S-base)printf(分配空間失敗!n);return ( ERRORStop = S-base;Sstac

4、ksize =STACK_INIT_SIZEprintf(棧初始化成功！ n);return ( OK; /InitStack() end /*取順序棧頂元素*/int GetTop( SqStack * S, SEIemType* e)GetTop() sub-functionif ( Stop = Sbase)printf(棧為空!n ); /if empty SqStackreturn ( ERROR*e = *( S-top - 1);return ( OK； /GetTop() end /*將元素壓入順序棧*/int Push( SqStack * S)Push() sub-func

5、tionSEIemTypee;if ( Stop -S-base Sstacksize)Sbase = ( SEIemType*)reaIIoc( S-base, ( S-stacksize + STACKINCREMENZeof (SEIemType)；if (! S-base)I Iprintf(存儲(chǔ)空間分配失敗!n);return ( ERROR| IStop = Sbase + Sstacksize;Sstacksize += STACKINCREMENTffIush( stdin ); /清除輸入緩沖區(qū)，否則原來的輸入會(huì)默認(rèn)送給變量x printf(請輸入要入棧的元素的值：); e

6、= getchar();*Stop+ = e;return ( OK); Push() end /*將元素彈出順序棧*廠|int Pop( SqStack * S, SEIemType* e)Pop() sub-functionif ( Stop = Sbase)printf(棧為空!n);return ( ERROR*e = *- Stop; return ( OK); Pop() endvoid display( SqStack * s)if ( s-top = s-base) printf(棧為空!n);else while ( s-top != s-base)printf( n);nt

7、 main()int choice;SEIemType e;SqStack s;doprintf( =n);printf( 0:退岀 n);printf(1:初始化棧n）;printf(2:入棧n);printf( 3:岀棧 n);printf（ 4:讀取棧頂元素n）;printf（ 5:顯示棧中元素n”）;printf( =printf(-輸入操作選擇代碼(0-5):);seanf( %d, &choice);while (choice5) printf(輸入有誤，請重新輸入(0-5): ); seanf( %d,&ehoiee); case 1:1 nitStack(&s);break ;

8、case 2:printf( 2n ); Push(&s);break;case 3:Pop(&s, &e); printf(岀棧元素的值是:%cn , e); break;case 4:GetTop(&s, &e); pri ntf(棧頂元素的值是：cn , e); break ;case 5: printf(棧中元素的值是為：n ); display(&s);break ; while (choice); return 0;(2)運(yùn)行結(jié)果操作選擇代碼(0-5):2 入妾入棧的元素的值:c棧 甯 匕 戎戲 岀一黑 :、次邃區(qū) 012345人燥作選扌郛弋碼(0-5) : 1F刀始化成功1桟 習(xí)

9、 匕 戎戎 嗨、次囁虛 0 12 3 4 5素素 元元 棧 ? 岀g黑 :次曙濕 0 12 3 4 5D!SWConsoleApplication1DebugConsoleApplication1 .exe詹輸入要入棧的元素的值:h素素 桟 ? 化 岀：取示 腿、次:遙 0:1:2:3:4:5:師入操作選擇代碼(0-5): 2 n矗輸入要入棧的元素的值:i素素 元元 ?化岀：取示:1次進(jìn)虛0:1:2:3:4:5:rrpi: fi 4J / 選的 操兀 入棧 厶即E元元S.戔戔 yF 出：取示 退艮岀讀顯 0:1:2:3:4:5:D；Sji5lConscleApplication1DebugCo

10、nsaleAp plicationl .ese-|Aag|(0-5)：4?；瘜缛∈?退岀讀顯 !$ !*0 12 3 4 51 遠(yuǎn)兀 S. M戈元： 岀取示 退、巽岀讀顯 I-V- _K ! 012345由入操作選擇代碼(0占：(3)結(jié)果分析順序表通過設(shè)置棧頂運(yùn)用線性結(jié)構(gòu)實(shí)現(xiàn)先進(jìn)先出功能。2. 任務(wù)一(2):完成下列程序，該程序?qū)崿F(xiàn)棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，構(gòu)建鏈棧(棧中的元 素依次為China，Japan，F(xiàn)rance , India ，Australia )，依次進(jìn)行進(jìn)棧和出棧操作，判斷棧 空和棧滿操作，返回棧頂元素操作。要求生成鏈棧時(shí)，從鍵盤上讀取數(shù)據(jù)元素。(1)源代碼：#in clude#in

11、 clude#in clude# define OK 1# define ERROR 0typedef char DataType;/*鏈?zhǔn)綏５拇鎯?chǔ)類型 */typedef struct SNode/defi ne structure Lin kStack DataType data20;struct SNode *n ext;SNode,*Li nkStack;void In itStack_L (Li nkStack *top)top = (Li nkStack)malloc(sizeof(SNode);top- next = NULL;prin tf(nn棧初始化成功！nn);I*取鏈?zhǔn)?/p>

12、棧頂元素*/int GetTop_L(L in kStack *top,DataType e) GetTop_L() sub-fu nctio n if(!top- next) printf(鏈棧為空！n);return (ERROR);else strcpy(e,top-n ext-data);return (OK); /GetTop_L() end/*將元素壓入鏈?zhǔn)綏?/int Push_L(Li nkStack *top) Push_L() sub-fu nction SNode *q;DataType e20;q=(Li nkStack)malloc(sizeof(SNode);if(

13、!q) prin tf(存儲(chǔ)空間分配失??！ n ”)；return (ERROR);fflush(stdi n);清除輸入緩沖區(qū)，否則原來的輸入會(huì)默認(rèn)送給變量eprin tf(n請輸入要入棧的元素的值:);gets(e);strcpy(q-data,e);q-n ext=top-n ext;top-n ext=q;return (OK); Push_L() end/*將元素彈出鏈?zhǔn)綏?/int Pop_L(Li nkStack *top,DataType e) Pop_L() sub-fu nction SNode *q;if(!top-n ext) printf(鏈棧為空！ n );retu

14、rn (ERROR);strcpy(e,top-n ext-data);q=top-n ext;top-n ext=q-n ext;free(q);return (OK); Pop L() endvoid display(Li nkStack *top)Lin kStack p=top-n ext; if(!p) printf(棧為空!n);elsewhile(p)prin tf(%s-,p-data); p=p-n ext;prin tf(An);int mai n()char choice;DataType e20=;Lin kStack s=NULL;doprintf(”=:一一npri

15、ntf(”0:退出n);printf(”1:初始化棧n);printf(”2:入棧n);printf(”3:出棧n);printf(”4:讀取棧頂兀素n);prin tf(5:顯示棧中兀素n););prin tf(=n); prin tf(輸入操作選擇代碼(0-5):);fflush(stdi n);scan f(%c,&choice);while(choice5)prin tf(輸入有誤，請重新輸入(0-5):);fflush(stdi n);sca nf(%c, &choice); switch(choice)case 0:exit(1);case 1: In itStack_L( &s)

16、;break;case 2: Push L( &s);break;case 3:Pop_L(&s, e);break;case 4:GetTop_L(&s, e);printf(棧頂元素的值是:%sn,e);break;case 5: printf(棧中元素的值是：”);display(&s);while(choice);return 0;(2)運(yùn)行結(jié)果0：退岀iir頂元恚J -R你 4:5；料入操作選擇代碼（0-5）: 1 b戔初始化咸功！元元 桟 甯 化 S 出g取示 退艮蛍顯 * !-m K!H* H 0 12 3 4 5輸入操作選擇代碼（。-5） ;2請輸入要入棧的元素的值:chin0

17、;退岀1鷲化棧38 _4 :讀能棧頂匹湊請輸入要入棧的元素的值:big素素元棧 岀：g取示 退艮岀讀顯0 12 3 4 5輸入操作選擇代碼(05):2 請輸入要入桟的元素的值：ad素素亓元 棧 岀黑 嗨、次進(jìn)濕 012345si.輸入操作選擇代碼(0-5): 30:退出1:和韓化棧2:入棧3:岀枝5：縣不桟中兀薰繭入操作選擇代碼(0-5) :3元元 桟 岀取示 0 12 3 4 5棧 s, 匕 確戎 出o 1 2 2 4* 50-5);5.,i 呂一Khi 朗一岀始菲BT1 :ig啜:s 0 12 3t-SSwwf5:顯示棧中元素輸人操作選擇代碼(。-5):(3)結(jié)果分析鏈表通過設(shè)置棧頂運(yùn)用指

18、針實(shí)現(xiàn)先進(jìn)先出功能3. 任務(wù)二：完成下列程序，該程序?qū)崿F(xiàn)循環(huán)隊(duì)列的存儲(chǔ)和基本操作，構(gòu)建循環(huán)隊(duì)列，完 成鍵盤緩沖區(qū)的功能，每輸入一個(gè)字符，鏈入緩沖區(qū)隊(duì)列中；每輸出一個(gè)字符，將該字符從緩沖區(qū)中刪除。(1)源代碼：#in clude#in clude# define MAXQSIZE 100# define OK 1# define ERROR 0/*定義QEIemType為int或別的自定義類型 */typedef char QEIemType;/*順序隊(duì)列的存儲(chǔ)類型*/typedef struct SqQueue /defi ne structure SqQueue QEIemType *bas

19、e;int front;int rear;SqQueue;/*構(gòu)造空順序隊(duì)列*/int In itQueue(SqQueue *Q) /In itQueue() sub-fu nction Q-base=(QEIemType *)malloc(MAXQSIZE*sizeof(QEIemType);if(!Q-base) printf(分配空間失?。?n);return (ERROR);Q_fron t=Q_rear=0;printf(隊(duì)列初始化成功! n);return (OK); /I ni tQueue() end/*求順序隊(duì)列長度*/int QueueLe ngth(SqQueue *Q

20、) /QueueLe ngth() sub-fu ncti on return (Q-rear-Q-fro nt+MAXQSIZE)%MAXQSIZE);/*在順序隊(duì)列尾插入新元素*/int En Queue(SqQueue *Q,QEIemType e) En Queue() sub-fu nction if(Q-rear+1)%MAXQSIZE=Q-fro nt) printf(隊(duì)列已滿！ n);return (ERROR);Q-baseQ-rear=e;Q-rear=(Q-rear+1)%MAXQSIZE;return (OK); /E nQueue() end/*在順序隊(duì)列頭刪除舊元素*/ int DeQueue(SqQueue *Q,QEIemType e) DeQueue() sub-fu nction if(Q-fro nt=Q-rear) printf(隊(duì)列為空！n);return (ERROR);e=Q-baseQ-fro nt;Q-fro nt=(Q-fro nt