棧和隊列的基本操作

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

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

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

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

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

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

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

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

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

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

11、lloc(STACK_INIT_SIZE *sizeof(int);/*動態(tài)分配內(nèi)存*/ if(!s->base) /*存儲分配失敗*/ return 0; s->top=s->base; s->stacksize=STACK_INIT_SIZE; /*初始化存儲空間*/ 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) /*比較棧中元素所占空間與已分配存儲空間*/ s->base=(int *)realloc(s->base,(s->stacksize+STACKINCEREMENT)*sizeof(int); /*棧滿，追加存儲空間*/ if(!s->base) /*若存儲失敗則返回0*/ return 0; s->top=s->base+s->stacksize; s->stacksize+=STACKINCEREMENT; /*存儲空間不夠，

13、添加增量*/ *(s->top+)=x;/*逐個輸入數(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; /*進制轉(zhuǎn)換函數(shù)*/int conversion(SqStack *s) /*將所輸入的任意一個非負的十進制數(shù)轉(zhuǎn)換為R進制的數(shù)*/ int n,x=0,R=0; printf("輸入要轉(zhuǎn)化的十進制數(shù)：n");

14、 scanf("%d",&n); printf("要轉(zhuǎn)化為幾進制：n輸入2代表二進制n輸入8代表八進制n輸入16代表十六進制n"); scanf("%d",&R); printf("將十進制數(shù)%d 轉(zhuǎn)化為%d 進制是：n",n,R); while(n) Push(s,n%R);/*運用求余運算改變進制數(shù)*/ n=n/R; while(!stackempty(s) x=Pop(s,x); switch(x) /*十六進制的輸出方式*/ 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/*定義隊列*/ int dataMAXSIZE; int front; /*隊頭指針*/ int rear; /*隊尾指針*/ SeqQueue; /*建立空隊列函數(shù)*/SeqQueue *InitQueue() /*構(gòu)造一個空隊

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

18、IZE; /*出隊函數(shù)*/int DeQueue(SeqQueue *q)/*若隊列不空則刪除隊頭元素，并返回其值*/ int x; if(q->front=q->rear) printf("n順序隊列是空的！不能做刪除操作！"); return 0; x=q->dataq->front; /*用x返回出隊的值*/ q->front=(q->front+1)%MAXSIZE; return x; /*求隊列長度函數(shù)*/ int QueueEmpty(SeqQueue *q) /*求隊列的長度*/ return(q->front-q->rear); /*返回隊頭函數(shù)*/int GetHead(SeqQueue *q)/*用e返回隊頭元素*/ int e; if(q->front=q->rear) /*隊列為空*/ 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(