實(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(xiàn)，C，T），依次進(jìn)行進(jìn)棧和出棧操作，判斷棧空和棧滿操作，返回棧頂元素操作。要求生成順序棧時(shí)，從鍵盤上讀取數(shù)據(jù)元素。（1）源代碼：#include<stdio.h>#include<stdlib.h>#define STACK_INIT_SIZE 100#define STACKINCREMENT 10# define OK 1#

3、define ERROR 0typedef char SElemType;/* 順序棧的存儲(chǔ)類型 */typedef struct/define structure SqStack()SElemType *base;SElemType *top;int stacksize;SqStack;/*構(gòu)造空順序棧*/int InitStack(SqStack *S)/InitStack() sub-functionS->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if (!S->base)printf("

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

5、;*e = *(S->top - 1);return (OK); /GetTop() end/*將元素壓入順序棧*/int Push(SqStack *S)/Push() sub-functionSElemType e;if (S->top - S->base>S->stacksize)S->base = (SElemType *)realloc(S->base, (S->stacksize +STACKINCREMENT*sizeof(SElemType);if (!S->base)printf("存儲(chǔ)空間分配失敗!n"

6、;);return (ERROR);S->top = S->base + S->stacksize;S->stacksize += STACKINCREMENT;fflush(stdin);/清除輸入緩沖區(qū)，否則原來(lái)的輸入會(huì)默認(rèn)送給變量xprintf("請(qǐng)輸入要入棧的元素的值:");e = getchar();*S->top+ = e;return (OK); /Push() end/* 將元素彈出順序棧*/int Pop(SqStack *S, SElemType *e)/Pop() sub-functionif (S->top = S

7、->base)printf("棧為空!n");return (ERROR);*e = *-S->top;return (OK); /Pop() endvoid display(SqStack *s)if (s->top = s->base)printf("棧為空!n");elsewhile (s->top != s->base)s->top = s->top - 1;printf("%c->", *(s->top);printf("n");int main

8、()int choice;SElemType e;SqStack s;doprintf("=n");printf(" 0:退出n");printf(" 1:初始化棧n");printf(" 2:入棧n");printf(" 3:出棧n");printf(" 4:讀取棧頂元素n");printf(" 5:顯示棧中元素n");printf("=n");printf("輸入操作選擇代碼(0-5):");scanf(&quo

9、t;%d", &choice);while (choice<0 | choice>5) printf("輸入有誤，請(qǐng)重新輸入(0-5):"); scanf("%d", &choice); switch (choice)case 0:exit(1);case 1:InitStack(&s); break;case 2:printf("2n"); Push(&s); break;case 3:Pop(&s, &e); printf("出棧元素的值是:%cn&q

10、uot;, e); break;case 4:GetTop(&s, &e); printf("棧頂元素的值是:%cn", e); break;case 5: printf("棧中元素的值是為：n"); display(&s); break; while (choice);return 0;（2）運(yùn)行結(jié)果（3） 結(jié)果分析 順序表通過(guò)設(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)行

11、進(jìn)棧和出棧操作，判斷?？蘸蜅M操作，返回棧頂元素操作。要求生成鏈棧時(shí)，從鍵盤上讀取數(shù)據(jù)元素。（1）源代碼：#include<stdio.h>#include<stdlib.h>#include<string.h># define OK 1# define ERROR 0typedef char DataType;/* 鏈?zhǔn)綏５拇鎯?chǔ)類型 */typedef struct SNode /define structure LinkStack DataType data20; struct SNode *next;SNode,*LinkStack; void Ini

12、tStack_L (LinkStack *top)top = (LinkStack)malloc(sizeof(SNode) ; top->next = NULL;printf("nn棧初始化成功！nn"); /*取鏈?zhǔn)綏ｍ斣?/int GetTop_L(LinkStack *top,DataType e) /GetTop_L() sub-function if(!top->next) printf("鏈棧為空!n"); return (ERROR); else strcpy(e,top->next->data); return

13、 (OK); /GetTop_L() end /* 將元素壓入鏈?zhǔn)綏?/int Push_L(LinkStack *top) /Push_L() sub-function SNode *q;DataType e20; q=(LinkStack)malloc(sizeof(SNode); if(!q) printf("存儲(chǔ)空間分配失敗! n"); return (ERROR); fflush(stdin);/清除輸入緩沖區(qū)，否則原來(lái)的輸入會(huì)默認(rèn)送給變量eprintf("n請(qǐng)輸入要入棧的元素的值:");gets(e);strcpy(q->data,e)

14、; q->next=top->next; top->next=q; return (OK); /Push_L() end /*將元素彈出鏈?zhǔn)綏?/int Pop_L(LinkStack *top,DataType e) /Pop_L() sub-function SNode *q; if(!top->next) printf("鏈棧為空! n "); return (ERROR); strcpy(e,top->next->data); q=top->next; top->next=q->next; free(q); re

15、turn (OK); /Pop_L() end void display(LinkStack *top) LinkStack p=top->next; if(!p) printf("棧為空!n"); elsewhile(p) printf("%s->",p->data); p=p->next; printf("n"); int main()char choice;DataType e20=""LinkStack s=NULL;do printf("=n"); printf

16、(" 0:退出n"); printf(" 1:初始化棧n"); printf(" 2:入棧n"); printf(" 3:出棧n"); printf(" 4:讀取棧頂元素n"); printf(" 5:顯示棧中元素n"); printf("=n"); printf("輸入操作選擇代碼(0-5):"); fflush(stdin); scanf("%c",&choice); while(choice<&#

17、39;0'|choice>'5') printf("輸入有誤，請(qǐng)重新輸入(0-5):"); fflush(stdin); scanf("%c",&choice); switch(choice) case '0':exit(1); case '1': InitStack_L(&s);break; case '2': Push_L(&s);break; case '3':Pop_L(&s, e);break; case '4&

18、#39;:GetTop_L(&s, e);printf("棧頂元素的值是:%sn",e);break; case '5': printf("棧中元素的值是: ");display(&s); while(choice);return 0;（2） 運(yùn)行結(jié)果 （3） 結(jié)果分析 鏈表通過(guò)設(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）源代碼：#include<std

19、io.h>#include<stdlib.h># define MAXQSIZE 100# define OK 1# define ERROR 0 /* 定義QElemType為int或別的自定義類型 */typedef char QElemType; /* 順序隊(duì)列的存儲(chǔ)類型 */typedef struct SqQueue /define structure SqQueue QElemType *base; int front; int rear;SqQueue; /* 構(gòu)造空順序隊(duì)列*/int InitQueue(SqQueue *Q) /InitQueue() sub

20、-function Q->base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType); if(!Q->base) printf("分配空間失敗! n"); return (ERROR); Q->front=Q->rear=0;printf("隊(duì)列初始化成功! n"); return (OK); /InitQueue() end /* 求順序隊(duì)列長(zhǎng)度*/int QueueLength(SqQueue *Q) /QueueLength() sub-function return (Q->

21、;rear-Q->front+MAXQSIZE)%MAXQSIZE); /*在順序隊(duì)列尾插入新元素*/int EnQueue(SqQueue *Q,QElemType e) /EnQueue() sub-function if(Q->rear+1)%MAXQSIZE=Q->front) printf("隊(duì)列已滿! n");return (ERROR); Q->baseQ->rear=e;Q->rear=(Q->rear+1)%MAXQSIZE; return (OK); /EnQueue() end /*在順序隊(duì)列頭刪除舊元素*/i

22、nt DeQueue(SqQueue *Q,QElemType e) /DeQueue() sub-function if(Q->front=Q->rear) printf("隊(duì)列為空!n"); return (ERROR); e=Q->baseQ->front; Q->front=(Q->front+1)%MAXQSIZE; return (OK); /DeQueue() end void display(SqQueue *Q)if(Q->front=Q->rear) printf("隊(duì)列為空!n");int i=Q->front;while(i+1)%MAXQSIZE!=Q-