大數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告材料-棧和隊(duì)列

1、實(shí)用標(biāo)準(zhǔn)文案實(shí)驗(yàn)三棧和隊(duì)列【實(shí)驗(yàn)?zāi)康摹?、掌握棧的結(jié)構(gòu)特性及其入棧，出棧操作；2、掌握隊(duì)列的結(jié)構(gòu)特性及其入隊(duì)、出隊(duì)的操作，掌握循環(huán)隊(duì)列的特點(diǎn)及其操作。3、理解掌握遞歸調(diào)用程序設(shè)計(jì)思想?！緦?shí)驗(yàn)學(xué)時(shí)】4 學(xué)時(shí)【實(shí)驗(yàn)預(yù)習(xí)】回答以下問題：1、棧的順序存儲(chǔ)表示2、單鏈隊(duì)列的存儲(chǔ)表示3、循環(huán)隊(duì)列的順序存儲(chǔ)表示【實(shí)驗(yàn)內(nèi)容和要求】1、按照要求完成程序exp3_1.c ，實(shí)現(xiàn)順序棧的相關(guān)操作。以下具有返回值的函數(shù)，若文檔大全實(shí)用標(biāo)準(zhǔn)文案操作完成，返回OK ，操作失敗返回ERROR 。函數(shù)需返回的其他數(shù)據(jù)，使用函數(shù)參數(shù)返回。調(diào)試及測(cè)試數(shù)據(jù)并給出結(jié)果：初始化棧；連續(xù)進(jìn)棧3 ，5，7，9，13 ；獲取當(dāng)前棧頂元素；返

2、回當(dāng)前棧長(zhǎng)度；判斷當(dāng)前棧是否為空；棧內(nèi)元素依次出棧；判斷當(dāng)前棧是否為空；清空棧；利用棧實(shí)現(xiàn)數(shù)制轉(zhuǎn)換，測(cè)試整數(shù)8和255；判斷表達(dá)式括號(hào)是否匹配，測(cè)試以下三個(gè)表達(dá)式：表達(dá)式 1 ：1*(2+3)/4；表達(dá)式 2 ：(3+4)*7-(8-9)；表達(dá)式 3 ：(1+2)*(3+4)-(5+6)*3)exp3_1.c部分代碼如下：#include<stdio.h>#include<malloc.h>#include<string.h>#define ERROR 0文檔大全實(shí)用標(biāo)準(zhǔn)文案#define OK 1#define STACK_INT_SIZE 10/* 存儲(chǔ)

3、空間初始分配量*/#define STACKINCREMENT 5/* 存儲(chǔ)空間分配增量*/typedefint ElemType; /*定義元素的類型*/* （ 1） - 補(bǔ)充棧的順序存儲(chǔ)分配表示，采用定長(zhǎng)和可變長(zhǎng)度存儲(chǔ)均可*/typedef structElemType *base;ElemType *top;int stacksize;SqStack;int InitStack(SqStack *S);/* 構(gòu)造空棧 */int Push(SqStack *S,ElemType e);/* 入棧 */int Pop(SqStack *S,ElemType *e);/* 出棧 */int

4、PopSq(SqStack *S);int GetTop(SqStack *S,ElemType *e); /*獲取棧頂元素 */int ClearStack(SqStack *S);/* 清空棧 */int StackEmpty(SqStack *S);/* 判斷棧是否為空*/int StackLength(SqStack *S);/* 求棧的長(zhǎng)度 */void conversion();/* 十進(jìn)制轉(zhuǎn)換為二進(jìn)制*/void Correct();/* 判斷表達(dá)式括號(hào)是否匹配*/文檔大全實(shí)用標(biāo)準(zhǔn)文案/* （ 2） - 初始化棧函數(shù)*/int InitStack(SqStack *S)S->

5、;base=(ElemType *)malloc(STACK_INT_SIZE*sizeof(ElemType);if(!S->base)return ERROR;S->top=S->base;S->stacksize=STACK_INT_SIZE;return OK;/*InitStack*/* （ 3） - 入棧函數(shù) */int Push(SqStack *S,ElemType e)if(S->top-S->base>=S->stacksize)S->base=(ElemType*)realloc(S->base,(S->s

6、tacksize+STACKINCREMENT)*sizeof(ElemType);if(!S->base)文檔大全實(shí)用標(biāo)準(zhǔn)文案return ERROR;S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;*S->top+=e;return OK;/*Push*/* （ 4） - 出棧函數(shù) */int Pop(SqStack *S,ElemType *e)if(S->top=S->base)return ERROR;-S->top;*e=*S->top;return OK;

7、/*Pop*/文檔大全實(shí)用標(biāo)準(zhǔn)文案int PopSq(SqStack *S)if(S->top=S->base)return ERROR;-S->top;return OK;/* （ 5） - 返回棧頂元素函數(shù)*/int GetTop(SqStack *S,ElemType *e)if(S->top=S->base)return ERROR;*e=*(S->top-1);return OK;/*GetTop*/* （ 6） - 清空棧函數(shù) */文檔大全實(shí)用標(biāo)準(zhǔn)文案int ClearStack(SqStack *S)if(InitStack(S)printf(

8、"Init Success!");return OK;elseprintf("Init Fail!");return ERROR;/*ClearStack*/* （ 8） - 判斷棧是否為空*/int StackEmpty(SqStack *S)if(S->base=S->top)return OK;elsereturn ERROR;/*StackEmpty*/文檔大全實(shí)用標(biāo)準(zhǔn)文案/* （ 9） - 返回棧的長(zhǎng)度函數(shù)*/int StackLength(SqStack *S)return S->top-S->base;/*Stack

9、Length*/* （ 10 ） - 十進(jìn)制整數(shù)轉(zhuǎn)換為二進(jìn)制并輸出函數(shù)*/void Conversion()int e;SqStack sq;InitStack(&sq);int count;printf("input count:");scanf("%d",&count);while(count!=0)Push(&sq,count%2);count=count/2;while(Pop(&sq,&e)文檔大全實(shí)用標(biāo)準(zhǔn)文案printf("%d ",e);/*Conversion*/* （ 11 ）

10、 - 判斷表達(dá)式括弧是否匹配（假設(shè)只有一種小括?。┖瘮?shù)*/void Correct()SqStack sqs;InitStack(&sqs);char a100,c;int i=0;printf("input :");while(c=getchar()!='n')ai+=c;for(i=0;i<strlen(a);i+)if(ai='(')Push(&sqs,ai);if(ai=')')文檔大全實(shí)用標(biāo)準(zhǔn)文案PopSq(&sqs);if(StackEmpty(&sqs)printf(&quo

11、t;OK!");elseprintf("error!");/*Correct*/* 定義菜單字符串?dāng)?shù)組*/int menu_select()char *menu= "n*MENU*n"," 1.Init Satckn",/* 初始化順序棧 */" 2.Push Elementn",/* 入棧 */" 3.Get TopElementn",/* 獲得棧頂元素 */" 4.Return StackLengthn",/* 返回棧的長(zhǎng)度 */文檔大全實(shí)用標(biāo)準(zhǔn)文案"

12、 5. Stack IsEmptyn",/* 判斷是否?？?/" 6. Pop Elementn",/* 出棧 */" 7. Clear Stackn",/* 清空棧 */" 8. Conversionn",/* 利用棧進(jìn)行數(shù)制轉(zhuǎn)換*/" 9. Correctn",/* 利用棧進(jìn)行括號(hào)匹配*/" 0. Quitn",/* 退出 */"n*MENU*n"char s3;/* 以字符形式保存選擇號(hào)*/int c,i;/* 定義整形變量 */for (i=0; i<

13、11; i+)/* 輸出主菜單數(shù)組*/printf("%s",menui);doprintf("nEnter you choice(09):");/* 在菜單窗口外顯示提示信息*/scanf("%s",s);/* 輸入選擇項(xiàng) */c=atoi(s);/* 將輸入的字符串轉(zhuǎn)化為整形數(shù)*/while (c<0|c>9);/* 選擇項(xiàng)不在09之間重輸 */return c;/* 返回選擇項(xiàng)，主程序根據(jù)該數(shù)調(diào)用相應(yīng)的函數(shù)*/文檔大全實(shí)用標(biāo)準(zhǔn)文案int main()SqStack ss;int e;InitStack(&ss

14、);for (;)switch (menu_select()case 1:printf("n1-Init Satck:n");if(InitStack(&ss)printf("Init OK!n");elseprintf("Init ERROR!n");break;case 2:printf("n2-Push Element:n");printf("input data(Terminated by inputing a character):");while(scanf("%d

15、",&e)=1)if(Push(&ss,e)文檔大全實(shí)用標(biāo)準(zhǔn)文案printf("Push %d OK!n",e);elseprintf("Push %d ERROR!n",e);printf("input data:(Terminated by inputing a character)");getchar();break;case 3:printf("n3-Get TopElement:n");if(GetTop(&ss,&e)printf("Top is %d

16、",e);elseprintf("Stack is Empty!");break;case 4:printf("n4-Return StackLength:n");printf("StackLength is %d",StackLength(&ss);break;case 5:printf("n5-Stack IsEmpty:n");if(StackEmpty(&ss)文檔大全實(shí)用標(biāo)準(zhǔn)文案printf("Stack is Empty!");elseprintf(&quo

17、t;Stack is not Empty!");break;case 6:printf("n6-Pop Element:n");if(StackEmpty(&ss)printf("Stack is Empty!");elseprintf("All elements of Stack :");while(Pop(&ss,&e)printf("%d ",e);break;文檔大全實(shí)用標(biāo)準(zhǔn)文案case 7:printf("n7-ClearStack:n");Clear

18、Stack(&ss);printf("ClearStack OK!");break;case 8:printf("n8-Conversion:n");Conversion();break;case 9:printf("n9-Correct:n");getchar();Correct();break;case 0:exit(0);return 0;2、按照要求完成程序exp3_2.c ，實(shí)現(xiàn)循環(huán)隊(duì)列的相關(guān)操作。以下具有返回值的函數(shù)，若操作完成，返回OK ，操作失敗返回ERROR 。函數(shù)需返回的其他數(shù)據(jù)，使用函數(shù)參數(shù)返文檔大全實(shí)用

19、標(biāo)準(zhǔn)文案回。調(diào)試及測(cè)試數(shù)據(jù)并給出結(jié)果：初始化隊(duì)列；返回當(dāng)前隊(duì)列長(zhǎng)度；連續(xù)入隊(duì)2， 4， 6，8，10 ；獲取當(dāng)前隊(duì)頭元素；返回當(dāng)前隊(duì)列長(zhǎng)度；判斷當(dāng)前隊(duì)列是否為空；隊(duì)列元素依次出隊(duì)；判斷當(dāng)前隊(duì)列是否為空；exp3_2.c部分代碼如下：#include<stdio.h>#include<malloc.h>#define ERROR 0#define OK 1#define MAXQSIZE 100typedefint QElemType; /*定義元素的類型*/* （ 1） - 循環(huán)隊(duì)列順序存儲(chǔ)表示*/typedef struct文檔大全實(shí)用標(biāo)準(zhǔn)文案QElemType *b

20、ase;int front;int rear;SqQueue;/* （ 2） - 構(gòu)造一個(gè)空循環(huán)隊(duì)列*/int InitQueue(SqQueue *Q)Q->base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType);if(!Q->base)return ERROR;Q->front=Q->rear=0;return OK;/*InitQueue*/* （ 3） - 返回循環(huán)隊(duì)列的長(zhǎng)度*/int QueueLength(SqQueue *Q)return Q->rear - Q->front;/*QueueLen

21、tgh*/文檔大全實(shí)用標(biāo)準(zhǔn)文案/* （ 4） - 入隊(duì)操作 */int EnQueue(SqQueue *Q,QElemType e)if(Q->rear+1)%MAXQSIZE=Q->front)return ERROR;Q->baseQ->rear=e;Q->rear=(Q->rear+1)%MAXQSIZE;return OK;/*EnQuese*/* （ 5） - 出隊(duì)操作 */int DeQueue(SqQueue *Q,QElemType *e)if(Q->front=Q->rear)return ERROR;*e=Q->bas

22、eQ->front;Q->front=(Q->front+1)%MAXQSIZE;文檔大全實(shí)用標(biāo)準(zhǔn)文案return OK;/*DeQueue*/* （ 6） - 判斷隊(duì)列是否為空*/int QueueEmpty(SqQueue *Q)if(Q->rear=Q->front)return OK;elsereturn ERROR;/*QueueEmpty*/* （ 7） - 取隊(duì)頭元素 */int GetHead(SqQueue *Q,QElemType *e)if(Q->rear = Q->front)/ 隊(duì)列空的判斷return ERROR;文檔大全實(shí)

23、用標(biāo)準(zhǔn)文案*e = Q->baseQ->front;/ 將隊(duì)頭元素賦值給eQ->front = (Q->front + 1) % MAXQSIZE;/front指針向后一位置，若到最后，則轉(zhuǎn)到數(shù)組頭部return OK;/*GetHead*/* 銷毀隊(duì)列 */int DestroyQueue(SqQueue *Q)if(Q->base)Q->rear=Q->front=0;free(Q->base);return OK;/*DestroyQueue*/* 定義菜單字符串?dāng)?shù)組*/int menu_select()char *menu= "

24、n*MENU*n",文檔大全實(shí)用標(biāo)準(zhǔn)文案" 1. Init Queuen",/* 初始化循環(huán)隊(duì)列 */" 2. Get QueueLengthn",/* 求隊(duì)列的長(zhǎng)度 */" 3. EnQueuen",/* 入隊(duì)操作 */" 4.Get Headn",/* 取隊(duì)頭元素 */" 5.Queue IsEmptyn",/* 判斷是否隊(duì)空 */" 6.DeQueuen",/* 出隊(duì)操作 */" 0.Quitn",/* 銷毀隊(duì)列并退出 */"n*

25、MENU*n"char s3;int c,i;for (i=0; i<=8; i+)printf("%s",menui);doprintf("nEnter you choice(06):");scanf("%s",s);c=atoi(s);while (c<0|c>6);return c;文檔大全實(shí)用標(biāo)準(zhǔn)文案/* 主函數(shù) */int main()SqQueue qq;int e;InitQueue(&qq);for (;)switch (menu_select()case 1:printf(&quo

26、t;n1-Init Queue:n");if(InitQueue(&qq)printf("Init OK!n");elseprintf("Init ERROR!n");break;case 2:printf("n2-Get QueueLength:n");printf("Queue length is %d",QueueLength(&qq);break;文檔大全實(shí)用標(biāo)準(zhǔn)文案case 3:printf("n3-EnQueue:n");printf("pleas

27、e input data:");scanf("%d",&e);if(EnQueue(&qq,e)printf("%d EnQueue OK!n",e);elseprintf("EnQueue Error!n");break;case 4:printf("n4-Get Head:n");if(GetHead(&qq,&e)printf("Head is %dn",e);elseprintf("Get Head Error!n");bre

28、ak;case 5:printf("n5-QueueEmpty:n");if(QueueEmpty(&qq)printf("Queue is Empty!");elseprintf("Queue is not Empty");文檔大全實(shí)用標(biāo)準(zhǔn)文案break;case 6:printf("n6-DeQueue:n");printf("Queue is :");while(!QueueEmpty(&qq)if(DeQueue(&qq,&e)printf("%d ",e);break;case 0:DestroyQueue(&qq);exit(0);retur