棧和隊(duì)列的基本操作

1、數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)報(bào)告專業(yè)班級(jí)姓名學(xué)號(hào)實(shí)驗(yàn)項(xiàng)目 實(shí)驗(yàn)二 棧和隊(duì)列的基本操作。實(shí)驗(yàn)?zāi)康?、掌握棧的基本操作：初始化棧、判棧為空、出棧、入棧等運(yùn)算。2、掌握隊(duì)列的基本操作：初始化隊(duì)列、判隊(duì)列為空、出隊(duì)列、入隊(duì)列等運(yùn)算。實(shí)驗(yàn)內(nèi)容題目1：進(jìn)制轉(zhuǎn)換。利用棧的基本操作實(shí)現(xiàn)將任意一個(gè)十進(jìn)制整數(shù)轉(zhuǎn)化為R進(jìn)制整數(shù)算法提示：1、定義棧的順序存取結(jié)構(gòu)2、分別定義棧的基本操作（初始化棧、判棧為空、出棧、入棧等）3、定義一個(gè)函數(shù)用來(lái)實(shí)現(xiàn)上面問(wèn)題：十進(jìn)制整數(shù)X和R作為形參初始化棧只要X不為0重復(fù)做下列動(dòng)作 將X%R入棧 X=X/R只要棧不為空重復(fù)做下列動(dòng)作 棧頂出棧 輸出棧頂元素題目2：利用隊(duì)列的方式實(shí)現(xiàn)楊輝三角的輸出。

2、算法設(shè)計(jì)分析（一）數(shù)據(jù)結(jié)構(gòu)的定義1、棧的應(yīng)用 實(shí)現(xiàn)十進(jìn)制到其他進(jìn)制的轉(zhuǎn)換，該計(jì)算過(guò)程是從低位到高位順序產(chǎn)生R進(jìn)制數(shù)的各個(gè)位數(shù)，而打印輸出一般從高位到低位進(jìn)行，恰好與計(jì)算過(guò)程相反。因此，運(yùn)用棧先進(jìn)后出的性質(zhì)，即可完成進(jìn)制轉(zhuǎn)換。棧抽象數(shù)據(jù)結(jié)構(gòu)描述typedef struct SqStack /*定義順序棧*/ int *base; /*棧底指針*/ int *top; /*棧頂指針*/ int stacksize; /*當(dāng)前已分配存儲(chǔ)空間*/ SqStack; 2、隊(duì)列的應(yīng)用由于是要打印一個(gè)數(shù)列，并且由于隊(duì)列先進(jìn)先出的性質(zhì)，肯定要利用已經(jīng)進(jìn)隊(duì)的元素在其出隊(duì)之前完成楊輝三角的遞歸性。即，利用要出隊(duì)的

3、元素來(lái)不斷地構(gòu)造新的進(jìn)隊(duì)的元素，即在第N行出隊(duì)的同時(shí)，來(lái)構(gòu)造楊輝三角的第N+1行，從而實(shí)現(xiàn)打印楊輝三角的目的。隊(duì)列抽象數(shù)據(jù)結(jié)構(gòu)描述typedef struct SeqQueue int dataMAXSIZE; int front; /*隊(duì)頭指針*/ int rear; /*隊(duì)尾指針*/ SeqQueue; （二）總體設(shè)計(jì)1、棧（1）主函數(shù)：統(tǒng)籌調(diào)用各個(gè)函數(shù)以實(shí)現(xiàn)相應(yīng)功能 int main()（2）空棧建立函數(shù)：對(duì)棧進(jìn)行初始化。 int StackInit(SqStack *s)（3）判斷棧空函數(shù)：對(duì)棧進(jìn)行判斷，若棧中有元素則返回1，若棧為空，則返回0。int stackempty(SqSta

4、ck *s)（4）入棧函數(shù)：將元素逐個(gè)輸入棧中。int Push(SqStack *s,int x)（5）出棧函數(shù)：若棧不空，則刪除棧頂元素，并用x返回其值。int Pop(SqStack *s,int x)（6）進(jìn)制轉(zhuǎn)換函數(shù)：將十進(jìn)制數(shù)轉(zhuǎn)換為R進(jìn)制數(shù)int conversion(SqStack *s)2、隊(duì)列（1）主函數(shù)：統(tǒng)籌調(diào)用各個(gè)函數(shù)以實(shí)現(xiàn)相應(yīng)功能 void main()（2）空隊(duì)列建立函數(shù)：對(duì)隊(duì)列進(jìn)行初始化。 SeqQueue *InitQueue()（3）返回隊(duì)頭函數(shù)： 判斷隊(duì)是否為空，若不為空則返回隊(duì)頭元素。int QueueEmpty(SeqQueue *q)（4）入隊(duì)函數(shù)：將元

5、素逐個(gè)輸入隊(duì)列中。void EnQueue(SeqQueue *q,int x)（5）出隊(duì)函數(shù)：若隊(duì)列不空，則刪除隊(duì)列元素，并用x返回其值。int DeQueue(SeqQueue *q)（6）計(jì)算隊(duì)長(zhǎng)函數(shù)：計(jì)算隊(duì)列的長(zhǎng)度。int QueueEmpty(SeqQueue *q)（7）輸出楊輝三角函數(shù)：按一定格式輸出楊輝三角。 void YangHui(int n)（三）各函數(shù)的詳細(xì)設(shè)計(jì)：1、棧（1）int main()主函數(shù) 定義s為棧類型 調(diào)用函數(shù)建立空棧 調(diào)用進(jìn)制轉(zhuǎn)換函數(shù) 返回0值（2）int StackInit(SqStack *s) 空棧建立函數(shù) 動(dòng)態(tài)分配內(nèi)存 判斷分配成功并返回相應(yīng)的

6、值 若成功，初始化存儲(chǔ)空間（3）int stackempty(SqStack *s) 判斷?？蘸瘮?shù) 若棧為空，返回0，否則返回1（4）int Push(SqStack *s,int x) 入棧函數(shù) 比較棧中元素所占空間與已分配存儲(chǔ)空間 若棧滿，追加存儲(chǔ)空間 若存儲(chǔ)失敗則返回0 存儲(chǔ)空間不夠，添加增量 逐個(gè)輸入數(shù)據(jù)元素 返回x的值（5）int Pop(SqStack *s,int x) 出棧函數(shù) 如果棧為空，則返回0 若棧不空，則刪除棧頂元素，用x返回其值（6）：int conversion(SqStack *s) 進(jìn)制轉(zhuǎn)換函數(shù) 輸入要轉(zhuǎn)化的十進(jìn)制數(shù) 輸入要轉(zhuǎn)化為幾進(jìn)制 運(yùn)用求余運(yùn)算改變進(jìn)制數(shù)

7、運(yùn)用選擇結(jié)構(gòu)控制十六進(jìn)制的輸出方式2、隊(duì)列（1）void main()主函數(shù)輸入楊輝三角的行數(shù)調(diào)用楊輝三角輸出函數(shù)輸出楊輝三角（2）SeqQueue *InitQueue()空隊(duì)列建立函數(shù) 動(dòng)態(tài)分配內(nèi)存 建立隊(duì)列并返還該隊(duì)列（3）int QueueEmpty(SeqQueue *q) 返回隊(duì)頭函數(shù) 判斷隊(duì)列為空，返回0若不空返回隊(duì)頭元素（4）void EnQueue(SeqQueue *q,int x) 入隊(duì)函數(shù) 判斷隊(duì)滿 若不滿，逐個(gè)添加元素（5）int DeQueue(SeqQueue *q) 出隊(duì)函數(shù) 若頭指針等于尾指針，順序隊(duì)列是空的不能做刪除操作 否則，刪除隊(duì)列 用x返回出隊(duì)的值（6

8、）int QueueEmpty(SeqQueue *q) 計(jì)算隊(duì)長(zhǎng)函數(shù) 頭指針減尾指針，求隊(duì)列長(zhǎng)度（7）void YangHui(int n) 輸出楊輝三角函數(shù) 定義變量 循環(huán)輸出元素1 插入1為隊(duì)列隊(duì)尾元素 使用空格控制輸出格式 逐個(gè)輸出隊(duì)列元素，并構(gòu)建下一行需輸出的隊(duì)列 運(yùn)算結(jié)果插入隊(duì)尾實(shí)驗(yàn)測(cè)試結(jié)果及結(jié)果分析（一）測(cè)試結(jié)果（進(jìn)制轉(zhuǎn)換） （楊輝三角）（二）結(jié)果分析 調(diào)試程序時(shí)，出現(xiàn)了許多錯(cuò)誤。如： 有時(shí)候?qū)懙臎]有出現(xiàn)問(wèn)題，但運(yùn)行的結(jié)果是Press anu key to continue 。程序肯定有錯(cuò)，但為什么會(huì)出現(xiàn)這種問(wèn)題呢。分號(hào)的忘記那還是很經(jīng)常的，要加強(qiáng)注意。在做表達(dá)式的計(jì)算的時(shí)候一定

9、要注意何時(shí)入棧何時(shí)出棧，隊(duì)列也是同樣的。如果如棧與出棧的情況判斷不清楚就無(wú)法得出答案。在寫主函數(shù)時(shí)，如果是用void main的形式，那么可以不用有返回值，如果是int main的話，要有返回值，既末尾要有return語(yǔ)句。實(shí)驗(yàn)總結(jié)1.進(jìn)一步鞏固了C語(yǔ)言的基礎(chǔ)，尤其是指針那部分；2.通過(guò)實(shí)驗(yàn)加深了對(duì)棧和隊(duì)列的操作方面知識(shí)的認(rèn)識(shí)。更深層次了解了棧和隊(duì)列的操作特點(diǎn)及不同之處；3.通過(guò)實(shí)驗(yàn)達(dá)到了理論與實(shí)踐結(jié)合的目的，提高了自己的編程能力；4.程序可能不夠完善需要在學(xué)習(xí)過(guò)程中不斷去完善，這需要平時(shí)的努力。附錄 實(shí)驗(yàn)程序代碼一、進(jìn)制轉(zhuǎn)換#include <stdio.h> #include

10、<stdlib.h> #include <malloc.h> #define STACK_INIT_SIZE 100 /*存儲(chǔ)空間初始分配量*/#define STACKINCEREMENT 10 /*存儲(chǔ)空間分配增量*/typedef struct SqStack /*定義順序棧*/ int *base; /*棧底指針*/ int *top; /*棧頂指針*/ int stacksize; /*當(dāng)前已分配存儲(chǔ)空間*/ SqStack; /*建立空棧函數(shù)*/int StackInit(SqStack *s) /*構(gòu)造一個(gè)空棧*/ s->base=(int *)ma

11、lloc(STACK_INIT_SIZE *sizeof(int);/*動(dòng)態(tài)分配內(nèi)存*/ if(!s->base) /*存儲(chǔ)分配失敗*/ return 0; s->top=s->base; s->stacksize=STACK_INIT_SIZE; /*初始化存儲(chǔ)空間*/ return 1; /*判斷?？蘸瘮?shù)*/int stackempty(SqStack *s) /*判斷棧是否為空*/ if(s->top=s->base) return 1; else return 0; /*入棧函數(shù) */ int Push(SqStack *s,int x) /*入棧，

12、插入x為新的棧頂元素*/ if(s->top-s->base>=s->stacksize) /*比較棧中元素所占空間與已分配存儲(chǔ)空間*/ s->base=(int *)realloc(s->base,(s->stacksize+STACKINCEREMENT)*sizeof(int); /*棧滿，追加存儲(chǔ)空間*/ if(!s->base) /*若存儲(chǔ)失敗則返回0*/ return 0; s->top=s->base+s->stacksize; s->stacksize+=STACKINCEREMENT; /*存儲(chǔ)空間不夠，

13、添加增量*/ *(s->top+)=x;/*逐個(gè)輸入數(shù)據(jù)元素*/ return x; /*出棧函數(shù)*/int Pop(SqStack *s,int x)/*出棧操作*/ if(s->top=s->base) /*如果棧為空，則返回0*/ return 0; x=*-s->top;/*若棧不空，則刪除棧頂元素，用x返回其值*/ return x; /*進(jìn)制轉(zhuǎn)換函數(shù)*/int conversion(SqStack *s) /*將所輸入的任意一個(gè)非負(fù)的十進(jìn)制數(shù)轉(zhuǎn)換為R進(jìn)制的數(shù)*/ int n,x=0,R=0; printf("輸入要轉(zhuǎn)化的十進(jìn)制數(shù)：n");

14、 scanf("%d",&n); printf("要轉(zhuǎn)化為幾進(jìn)制：n輸入2代表二進(jìn)制n輸入8代表八進(jìn)制n輸入16代表十六進(jìn)制n"); scanf("%d",&R); printf("將十進(jìn)制數(shù)%d 轉(zhuǎn)化為%d 進(jìn)制是：n",n,R); while(n) Push(s,n%R);/*運(yùn)用求余運(yùn)算改變進(jìn)制數(shù)*/ n=n/R; while(!stackempty(s) x=Pop(s,x); switch(x) /*十六進(jìn)制的輸出方式*/ case 10: printf("A"); b

15、reak; case 11: printf("B"); break; case 12: printf("C"); break; case 13: printf("D"); break; case 14: printf("E"); break; case 15: printf("F"); break; default: printf("%d",x); printf("n");return 0; /*主函數(shù)*/ int main() SqStack s; /*

16、定義s為棧類型*/StackInit(&s); conversion(&s); return 0; 二、輸出楊輝三角#include <stdio.h>#include <stdlib.h> #include <malloc.h> #define MAXSIZE 10 typedef struct SeqQueue/*定義隊(duì)列*/ int dataMAXSIZE; int front; /*隊(duì)頭指針*/ int rear; /*隊(duì)尾指針*/ SeqQueue; /*建立空隊(duì)列函數(shù)*/SeqQueue *InitQueue() /*構(gòu)造一個(gè)空隊(duì)

17、列*/ SeqQueue *q; q=(SeqQueue*)malloc(sizeof(SeqQueue);/*動(dòng)態(tài)分配內(nèi)存*/ q->front=q->rear=0; return q; /*入隊(duì)函數(shù)*/ void EnQueue(SeqQueue *q,int x)/*插入元素x為隊(duì)列的新的隊(duì)尾元素*/ if(q->rear+1)%MAXSIZE=q->front) /*判斷隊(duì)滿*/ printf("n順序循環(huán)隊(duì)列是滿的！"); else q->dataq->rear=x; q->rear=(q->rear+1)%MAXS

18、IZE; /*出隊(duì)函數(shù)*/int DeQueue(SeqQueue *q)/*若隊(duì)列不空則刪除隊(duì)頭元素，并返回其值*/ int x; if(q->front=q->rear) printf("n順序隊(duì)列是空的！不能做刪除操作！"); return 0; x=q->dataq->front; /*用x返回出隊(duì)的值*/ q->front=(q->front+1)%MAXSIZE; return x; /*求隊(duì)列長(zhǎng)度函數(shù)*/ int QueueEmpty(SeqQueue *q) /*求隊(duì)列的長(zhǎng)度*/ return(q->front-q->rear); /*返回隊(duì)頭函數(shù)*/int GetHead(SeqQueue *q)/*用e返回隊(duì)頭元素*/ int e; if(q->front=q->rear) /*隊(duì)列為空*/ e=0; else e=q->dataq->front; return e; /*輸出楊輝三角函數(shù)*/void YangHui(int n)/*輸出楊輝三角*/ SeqQueue *q; int i,j,a,b; for(i=1;i<n;i+) printf(