棧和隊列的基本操作

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

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

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

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

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

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

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

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

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

11、lloc(STACK_INIT_SIZE *sizeof(int);/*動態(tài)分配內存*/ if(!s->base) /*存儲分配失敗*/ return 0; s->top=s->base; s->stacksize=STACK_INIT_SIZE; /*初始化存儲空間*/ return 1; /*判斷?？蘸瘮?/int stackempty(SqStack *s) /*判斷棧是否為空*/ if(s->top=s->base) return 1; else return 0; /*入棧函數 */ 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;/*逐個輸入數據元素*/ return x; /*出棧函數*/int Pop(SqStack *s,int x)/*出棧操作*/ if(s->top=s->base) /*如果棧為空，則返回0*/ return 0; x=*-s->top;/*若棧不空，則刪除棧頂元素，用x返回其值*/ return x; /*進制轉換函數*/int conversion(SqStack *s) /*將所輸入的任意一個非負的十進制數轉換為R進制的數*/ int n,x=0,R=0; printf("輸入要轉化的十進制數：n");

14、 scanf("%d",&n); printf("要轉化為幾進制：n輸入2代表二進制n輸入8代表八進制n輸入16代表十六進制n"); scanf("%d",&R); printf("將十進制數%d 轉化為%d 進制是：n",n,R); while(n) Push(s,n%R);/*運用求余運算改變進制數*/ 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; /*主函數*/ 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; /*建立空隊列函數*/SeqQueue *InitQueue() /*構造一個空隊

17、列*/ SeqQueue *q; q=(SeqQueue*)malloc(sizeof(SeqQueue);/*動態(tài)分配內存*/ q->front=q->rear=0; return q; /*入隊函數*/ 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; /*出隊函數*/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; /*求隊列長度函數*/ int QueueEmpty(SeqQueue *q) /*求隊列的長度*/ return(q->front-q->rear); /*返回隊頭函數*/int GetHead(SeqQueue *q)/*用e返回隊頭元素*/ int e; if(q->front=q->rear) /*隊列為空*/ e=0; else e=q->dataq->front; return e; /*輸出楊輝三角函數*/void YangHui(int n)/*輸出楊輝三角*/ SeqQueue *q; int i,j,a,b; for(i=1;i<n;i+) printf(