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

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

2、，完成鍵盤緩沖區(qū)的功能。四、實驗重點、難點1. 進棧、出棧棧頂指針都要改變。2. 隊空、隊滿的條件及入隊、出隊時指針的變更。五、操作內(nèi)容與要求1.任務(wù)一（1）：完成下列程序，該程序?qū)崿F(xiàn)棧的順序存儲結(jié)構(gòu)，構(gòu)建順序棧（棧中的元素依次為R，S，Y，F(xiàn)，C，T），依次進行進棧和出棧操作，判斷?？蘸蜅M操作，返回棧頂元素操作。要求生成順序棧時，從鍵盤上讀取數(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;/* 順序棧的存儲類型 */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("存儲空間分配失敗!n"

6、;);return (ERROR);S->top = S->base + S->stacksize;S->stacksize += STACKINCREMENT;fflush(stdin);/清除輸入緩沖區(qū)，否則原來的輸入會默認送給變量xprintf("請輸入要入棧的元素的值:");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("輸入有誤，請重新輸入(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）運行結(jié)果（3） 結(jié)果分析 順序表通過設(shè)置棧頂運用線性結(jié)構(gòu)實現(xiàn)先進先出功能。2.任務(wù)一（2）：完成下列程序，該程序?qū)崿F(xiàn)棧的鏈式存儲結(jié)構(gòu)，構(gòu)建鏈棧（棧中的元素依次為China，Japan，F(xiàn)rance，India，Australia），依次進行

11、進棧和出棧操作，判斷?？蘸蜅M操作，返回棧頂元素操作。要求生成鏈棧時，從鍵盤上讀取數(shù)據(jù)元素。（1）源代碼：#include<stdio.h>#include<stdlib.h>#include<string.h># define OK 1# define ERROR 0typedef char DataType;/* 鏈式棧的存儲類型 */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"); /*取鏈式棧頂元素*/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 /* 將元素壓入鏈式棧*/int Push_L(LinkStack *top) /Push_L() sub-function SNode *q;DataType e20; q=(LinkStack)malloc(sizeof(SNode); if(!q) printf("存儲空間分配失敗! n"); return (ERROR); fflush(stdin);/清除輸入緩沖區(qū)，否則原來的輸入會默認送給變量eprintf("n請輸入要入棧的元素的值:");gets(e);strcpy(q->data,e)

14、; q->next=top->next; top->next=q; return (OK); /Push_L() end /*將元素彈出鏈式棧*/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("輸入有誤，請重新輸入(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） 運行結(jié)果 （3） 結(jié)果分析 鏈表通過設(shè)置棧頂運用指針實現(xiàn)先進先出功能3.任務(wù)二：完成下列程序，該程序?qū)崿F(xiàn)循環(huán)隊列的存儲和基本操作，構(gòu)建循環(huán)隊列，完成鍵盤緩沖區(qū)的功能，每輸入一個字符，鏈入緩沖區(qū)隊列中；每輸出一個字符，將該字符從緩沖區(qū)中刪除。（1）源代碼：#include<std

19、io.h>#include<stdlib.h># define MAXQSIZE 100# define OK 1# define ERROR 0 /* 定義QElemType為int或別的自定義類型 */typedef char QElemType; /* 順序隊列的存儲類型 */typedef struct SqQueue /define structure SqQueue QElemType *base; int front; int rear;SqQueue; /* 構(gòu)造空順序隊列*/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("隊列初始化成功! n"); return (OK); /InitQueue() end /* 求順序隊列長度*/int QueueLength(SqQueue *Q) /QueueLength() sub-function return (Q->

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

22、nt DeQueue(SqQueue *Q,QElemType e) /DeQueue() sub-function if(Q->front=Q->rear) printf("隊列為空!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("隊列為空!n");int i=Q->front;while(i+1)%MAXQSIZE!=Q-