實(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 <stdio.h>#include <stdlib.h>#defi neSTACK INIT SIZE 100#defi neSTACKINCREMENW# defi neOK

3、1# defi neERRORtypedef char SEIemType/*順序棧的存儲(chǔ)類型*/typedef struct/define structure SqStack()SEIemType*base;SEIemType*top;int stacksize; SqStack;/*構(gòu)造空順序棧*/int InitStack(SqStack * S) lnitStack() sub-functionS>base = ( SEIemType*)malloc( STACK_INIT_SIZE*sizeof (SEIemTyp©)； if (! S->base)printf

4、("分配空間失敗!n");return ( ERRORS>top = S->base;S>stacksize =STACK_INIT_SIZEprintf("棧初始化成功！ n");return ( OK; /InitStack() end /*取順序棧頂元素*/int GetTop( SqStack * S, SEIemType* e)GetTop() sub-functionif ( S>top = S>base)printf("棧為空!n" ); /if empty SqStackreturn (

5、ERROR*e = *( S->top - 1);return ( OK； /GetTop() end /*將元素壓入順序棧*/int Push( SqStack * S)Push() sub-functionSEIemTypee;if ( S>top -S->base> S>stacksize)S>base = ( SEIemType*)reaIIoc( S->base, ( S->stacksize + STACKINCREMENZeof (SEIemType)；if (! S->base)I Iprintf("存儲(chǔ)空間分配失

6、敗!n");return ( ERROR| IS>top = S>base + S>stacksize;S>stacksize += STACKINCREMENTffIush( stdin ); /清除輸入緩沖區(qū)，否則原來的輸入會(huì)默認(rèn)送給變量x printf("請(qǐng)輸入要入棧的元素的值："); e = getchar();*S>top+ = e;return ( OK); Push() end /*將元素彈出順序棧*廠|int Pop( SqStack * S, SEIemType* e)Pop() sub-functionif ( S

7、>top = S>base)printf("棧為空!n");return ( ERROR*e = *- S>top; return ( OK); Pop() endvoid display( SqStack * s)if ( s->top = s->base) printf("棧為空!n");else while ( s->top != s->base)printf( "n");nt main()int choice;SEIemType e;SqStack s;doprintf( "

8、=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 (choice<0 | choice>5) printf(&

9、quot;輸入有誤，請(qǐng)重新輸入(0-5):" ); seanf( "%d",&ehoiee); case 1:1 nitStack(&s);break ;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 ;ca

10、se 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í) 匕 戎戎 嗨、次囁虛 0 12 3 4 5素素 元元 棧 ? 岀g黑 :®次曙濕 0 12 3 4 5D!SWConsoleApplication1DebugConsoleApplication1 .exe詹輸入要入棧的元素的值:h

11、素素 桟 ? 化 岀：取示 腿、次:±遙 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；Sji5lConscleApplication1DebugConsaleAp plicationl .ese-|Aag|(0-5)：4?；瘜缛∈?退岀讀顯 »!$ !*0 12 3 4 51 遠(yuǎn)兀 S. M戈元：£ 岀取示 退、巽岀讀顯 I-V- _K 

12、7;! 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<stdio.h>#in clude<stdlib.h>#in clude<stri ng.h># define OK 1# define ERROR 0

13、typedef 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)綏ｍ斣?/int GetTop_L(L in kSta

14、ck *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(!q)

15、prin tf("存儲(chǔ)空間分配失?。?n ”)；return (ERROR);fflush(stdi n);清除輸入緩沖區(qū)，否則原來的輸入會(huì)默認(rèn)送給變量eprin tf("n請(qǐng)輸入要入棧的元素的值:");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(!to

16、p->n ext) printf("鏈棧為空！ n ");return (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->

17、data); p=p->n ext;prin tf("An");int mai n()char choice;DataType e20=""Lin kStack s=NULL;doprintf(”=:一一nprintf(”0:退出n");printf(”1:初始化棧n");printf(”2:入棧n");printf(”3:出棧n");printf(”4:讀取棧頂兀素n");prin tf("5:顯示棧中兀素n");");prin tf("=n");

18、 prin tf("輸入操作選擇代碼(0-5):");fflush(stdi n);scan f("%c",&choice);while(choice<'0'|choice>'5')prin tf("輸入有誤，請(qǐng)重新輸入(0-5):");fflush(stdi n);sca nf("%c", &choice); switch(choice)case '0':exit(1);case '1': In itStack_L( &a

19、mp;s);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戔初始化咸功！元元

20、 桟 甯 化 S 出g取示 退艮蛍顯 * !-m K!H* » H 0 12 3 4 5輸入操作選擇代碼（。-5） ;2請(qǐng)輸入要入棧的元素的值:chin0;退岀1鷲化棧38 » _4 :讀能棧頂匹湊請(qǐng)輸入要入棧的元素的值:big素素元棧 岀：g取示 退艮岀讀顯0 12 3 4 5輸入操作選擇代碼(05):2 請(qǐng)輸入要入桟的元素的值：ad素素亓元 棧 £ 岀黑 嗨、次進(jìn)濕 012345si.輸入操作選擇代碼(0-5): 30:退出1:和韓化棧2:入棧3:岀枝5：縣不桟中兀薰繭入操作選擇代碼(0-5) :3元元 桟 岀取示 0 12 3 4 5棧 s, 匕 確戎 出o

21、 1 2 2 4* 50-5);5.,i 呂一Khi 朗一岀始菲BT1 :ig啜:s 0 12 3t-SSwwf5:顯示棧中元素輸人操作選擇代碼(。-5):(3) 結(jié)果分析鏈表通過設(shè)置棧頂運(yùn)用指針實(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<stdio.h>#in clude<stdlib.h># define MAXQSIZE 100# define OK 1# define ERROR 0/*

22、定義QEIemType為int或別的自定義類型 */typedef char QEIemType;/*順序隊(duì)列的存儲(chǔ)類型*/typedef struct SqQueue /defi ne structure SqQueue QEIemType *base;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) print

23、f("分配空間失??！ n");return (ERROR);Q_>fron t=Q_>rear=0;printf("隊(duì)列初始化成功! n");return (OK); /I ni tQueue() end/*求順序隊(duì)列長(zhǎng)度*/int QueueLe ngth(SqQueue *Q) /QueueLe ngth() sub-fu ncti on return (Q->rear-Q->fro nt+MAXQSIZE)%MAXQSIZE);/*在順序隊(duì)列尾插入新元素*/int En Queue(SqQueue *Q,QEIemType

24、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+1)%MAXQSIZE;return (OK); /DeQueue() endvoid display(SqQueue *Q)if(Q->fr on t=Q->rear)printf("隊(duì)列為空!n");int i=Q->fr ont;while(i+1)%MAXQSIZ