實驗二棧和隊列(基本操作)

1、實驗二棧和隊列1、實驗?zāi)康模?1) 熟悉棧的特點(先進(jìn)后出)及棧的基本操作，如入棧、出棧等，掌握棧的基本操作 在棧的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)上的實現(xiàn)；(2) 熟悉隊列的特點(先進(jìn)先出)及隊列的基本操作，如入隊、出隊等，掌握隊列的基 本操作在隊列的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)上的實現(xiàn)。2、實驗要求：(1) 復(fù)習(xí)課本中有關(guān)棧和隊列的知識；(2) 用C語言完成算法和程序設(shè)計并上機(jī)調(diào)試通過；(3) 撰寫實驗報告，給出算法思路或流程圖和具體實現(xiàn)(源程序)、算法分析結(jié)果(包括時間復(fù)雜度、空間復(fù)雜度以及算法優(yōu)化設(shè)想)、輸入數(shù)據(jù)及程序運(yùn)行結(jié)果(必要時給 出多種可能的輸入數(shù)據(jù)和運(yùn)行結(jié)果)。3、實驗內(nèi)容實驗1棧的

2、順序表示和實現(xiàn) 實驗內(nèi)容與要求：編寫一個程序?qū)崿F(xiàn)順序棧的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計一個主程序，完成如下功能：(1)初始化順序棧(2)插入元素(3)刪除棧頂元素(4)取棧頂元素(5)遍歷順序棧(6)置空順序棧分析：棧的順序存儲結(jié)構(gòu)簡稱為順序棧，它是運(yùn)算受限的順序表。對于順序棧，入棧時，首先判斷棧是否為滿，棧滿的條件為：p->top= =MAXNUM-1棧滿時,不能入棧；否則出現(xiàn)空間溢出，引起錯誤，這種現(xiàn)象稱為上溢。出棧和讀棧頂元素操作，先判棧是否為空，為空時不能操作，否則產(chǎn)生錯誤。通常?？兆鳛橐环N控制轉(zhuǎn)移的條件。注意：(1)順序棧中元素用向量存放(2)棧底位置是固定不變的，可設(shè)置在向量

3、兩端的任意一個端點(3)棧頂位置是隨著進(jìn)棧和退棧操作而變化的，用一個整型量top (通常稱top為棧頂指 針）來指示當(dāng)前棧頂位置#include <stdio.h>#include <malloc.h> typedef int SElemType;typedef int Status;#define INIT_SIZE 100#define STACKINCREMENT 10#define Ok 1#define Error 0#define True 1#define False 0typedef struct SElemType *base;SElemType *t

4、op;int stacksize;SqStack;/初始化棧Status InitStack(SqStack *s) s->base = (SElemType *)malloc(INIT_SIZE * sizeof(SElemType); if(!s->base) puts("存儲空間分配失?。?quot;)；return Error;s->top = s->base;s->stacksize = INIT_SIZE;return Ok;/清空棧Status ClearStack(SqStack *s) s->top = s->base;re

5、turn Ok;/棧是否為空Status StackEmpty(SqStack *s) if(s->top = s->base)return True;elsereturn False;/銷毀棧Status Destroy(SqStack *s)free(s->base);s->base = NULL;s->top = NULL;s->stacksize=0;return Ok;/獲得棧頂元素Status GetTop(SqStack *s, SElemType &e)if(s->top = s->base) return Error;e

6、 = *(s->top - 1);return Ok;/壓棧Status Push(SqStack *s, SElemType e)if(s->top - s->base >= s->stacksize)+ STACKINCREMENT)s->base = (SElemType *)realloc(s->base, (s->stacksize sizeof(SElemType);if(!s->base)puts("存儲空間分配失??！")；return Error;s->top = s->base + s-&g

7、t;stacksize;s->stacksize += STACKINCREMENT;*s->top+ = e;return Ok;/彈棧Status Pop(SqStack *s, SElemType *e)if(s->top = s->base) return Error;-s->top;*e = *(s->top);return Ok;/遍歷棧Status StackTraverse(SqStack *s,Status(*visit)(SElemType) SElemType *b = s->base;SElemType *t = s->t

8、op;while(t > b)visit(*b+);printf("n");return Ok;Status visit(SElemType c)printf("%d ",c);return Ok; int main()SqStack a;SqStack *s = &a;SElemType e;InitStack(s);int n;puts("請輸入要進(jìn)棧的個數(shù)：");scanf("%d", &n);while(n-)int m;scanf("%d", &m);Pu

9、sh(s, m);StackTraverse(s, visit);puts("");Pop(s, &e);printf("%dn", e);printf("%dn", *s->top);Destroy(s);return 0;實驗2棧的鏈?zhǔn)奖硎竞蛯崿F(xiàn)實驗內(nèi)容與要求：編寫一個程序?qū)崿F(xiàn)鏈棧的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計一個主程序，完成如下功能: (1)初始化鏈棧(2)鏈棧置空(3)入棧(4)出棧(5)取棧頂元素(6)遍歷鏈棧分析：鏈棧是沒有附加頭結(jié)點的運(yùn)算受限的單鏈表。棧頂指針就是鏈表的頭指針。注意：(1) LinkSta

10、ck結(jié)構(gòu)類型的定義可以方便地在函數(shù)體中修改top指針本身(2)若要記錄棧中元素個數(shù)，可將元素個數(shù)屬性放在LinkStack類型中定義。(3)鏈棧中的結(jié)點是動態(tài)分配的，所以可以不考慮上溢。#include <stdio.h>#include <malloc.h>#define ERROR 0#define OK 1#define TRUE 1#define FALSE 0typedef int ElemType;typedef int Status;typedef struct node ElemType data;struct node *next;StackNode;

11、typedef structStackNode *top;LinkStack;/初始化void InitStack(LinkStack *s)s->top = NULL;puts("鏈棧初始化完成！");/將鏈棧置空Status SetEmpty(LinkStack *s)StackNode *p = s->top;while(p) s->top = p->next;free(p);p = s->top;puts("鏈棧已置空！");return OK;/壓棧Status Push(LinkStack *s, ElemTyp

12、e e)StackNode *p;p = (StackNode *)malloc(sizeof(StackNode);p->data = e;p->next = s->top;s->top = p;return OK;/彈棧Status Pop(LinkStack *s, ElemType &e)StackNode *p = s->top;if(s->top = NULL) puts("?？眨荒苓M(jìn)行弓t棧操作！")； return ERROR;s->top = p->next;e = p->data;free(

13、p);return OK;/打印棧Status PrintStack(LinkStack *s)StackNode *p;p = s->top;while(p) printf("%d ", p->data);p = p->next;puts("");return OK;int main()LinkStack s;InitStack(&s);int n;printf("請輸入鏈棧長度:n");scanf("%d", &n);puts("請輸入要錄入的數(shù)據(jù):");w

14、hile(n-)int x;scanf("%d", &x); Push(&s, x);PrintStack(&s);SetEmpty(&s);return 0;實驗3隊列的順序表示和實現(xiàn)實驗內(nèi)容與要求完成如下功能:編寫一個程序?qū)崿F(xiàn)順序隊列的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計一個主程序,(1)初始化隊列(2)建立順序隊列(3)入隊(4)出隊(5)判斷隊列是否為空(6)取隊頭元素(7)遍歷隊列分析：隊列的順序存儲結(jié)構(gòu)稱為順序隊列，順序隊列實際上是運(yùn)算受限的順序表。入隊時，將新元素插入 rear所指的位置，然后將rear加1。出隊時，刪去front所指

15、的元 素，然后將front加1并返回被刪元素。順序隊列中的溢出現(xiàn)象：(1)"下溢"現(xiàn)象。當(dāng)隊列為空時，做出隊運(yùn)算產(chǎn)生的溢出現(xiàn)象?！跋乱纭笔钦，F(xiàn)象，常 用作程序控制轉(zhuǎn)移的條件。(2)"真上溢"現(xiàn)象。當(dāng)隊列滿時，做進(jìn)棧運(yùn)算產(chǎn)生空間溢出的現(xiàn)象?！罢嫔弦纭笔且环N出錯狀態(tài)，應(yīng)設(shè)法避免。(3)"假上溢"現(xiàn)象。由于入隊和出隊操作中，頭尾指針只增加不減小，致使被刪元素的空間永遠(yuǎn)無法重新利用。當(dāng)隊列中實際的元素個數(shù)遠(yuǎn)遠(yuǎn)小于向量空間的規(guī)模時，也可能由于尾指針已超越向量空間的上界而不能做入隊操作。該現(xiàn)象稱為"假上溢"現(xiàn)象。注意：(1)

16、當(dāng)頭尾指針相等時，隊列為空。(2)在非空隊列里，隊頭指針始終指向隊頭元素，尾指針始終指向隊尾元素的下一位置。#include <stdio.h>#include <malloc.h>typedef int QElemType;typedef int Status;#define MaxQSize 10#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define OVERFLOW -1typedef struct QElemType *base; int front, rear;SqQueue;/初始化循環(huán)

17、隊列int InitQueue(SqQueue &Q)Q.base = (QElemType*)malloc(MaxQSize*sizeof(QElemType);if (Q.base = NULL)puts("分配內(nèi)存空間失敗！”)； exit(OVERFLOW);Q.front = Q.rear = 0;return 0;/將循環(huán)隊列清空int ClearQueue(SqQueue &Q) Q.front = Q.rear = 0;/求隊列元素的個數(shù)int QueueLength(SqQueue Q) return (Q.rear - Q.front + MaxQ

18、Size) % MaxQSize;/插入元素到循環(huán)隊列int EnSqQueue(SqQueue &Q, QElemType e)if (Q.rear + 1) % MaxQSize = Q.front)return ERROR; 隊列滿Q.baseQ.rear = e; / 元素e入隊Q.rear = (Q.rear + 1) % MaxQSize; 修改隊尾指針return OK;/從循環(huán)隊列中刪除元素int DeSqQueue(SqQueue &Q, QElemType &e)if (Q.front = Q.rear)return ERROR;e = Q.base

19、Q.front; 取隊頭元素至 eQ.front = (Q.front + 1) % MaxQSize; /修改隊頭指針，如果超內(nèi)存，循環(huán)return OK;/判斷一個循環(huán)隊列是否為空隊列int isQueueEmpty(SqQueue Q) if (Q.front = Q.rear)return TRUE;elsereturn FALSE;int main() int i, e;SqQueue Q;InitQueue(Q);for (i=0; i<MaxQSize-1; i+)/ 只有 MaxQSize 個數(shù)據(jù)進(jìn)隊列EnSqQueue(Q, i);i = QueueLength(Q);

20、printf("隊列里的元素有%d4"n", i);for (i=0; i<3; i+)DeSqQueue(Q, e);printf("%d ", e);printf("n");i = QueueLength(Q);printf("隊列里的元素有%d4"n", i);for (i=10; i<12; i+) EnSqQueue(Q, i);i = QueueLength(Q);printf("隊列里的元素有%d4"n", i);ClearQueue(Q)

21、;i = QueueLength(Q);printf("隊列里的元素有%d4"n", i);return 0;實驗4隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)實驗內(nèi)容與要求：編寫一個程序?qū)崿F(xiàn)鏈隊列的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計一個主程序，完成如下功能： (1)初始化并建立鏈隊列(2)入鏈隊列(3)出鏈隊列(4)遍歷鏈隊列分析：隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈隊列。它是限制僅在表頭刪除和表尾插入的單鏈表。注意：(1)和鏈棧類似，無須考慮判隊滿的運(yùn)算及上溢。(2)在出隊算法中，一般只需修改隊頭指針。但當(dāng)原隊中只有一個結(jié)點時，該結(jié)點既是隊 頭也是隊尾，故刪去此結(jié)點時亦需修改尾指針，且刪去此結(jié)點后

22、隊列變空。(3)和單鏈表類似，為了簡化邊界條件的處理，在隊頭結(jié)點前可附加一個頭結(jié)點。#include <stdio.h>#include <malloc.h>typedef int ElemType;typedef int Status;#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef struct NodeElemType data;struct Node *next;Node;typedef structNode *front;Node *rear;LinkQueue;Status Ini

23、tQueue(LinkQueue *q)q->front = NULL;q->rear = NULL;return OK;InitQueueStatus DestroyQueue(LinkQueue *q)Node *p = q->front;while(p)q->front = p->next;free(p);p = q->front;puts("隊列已銷毀！”)；return OK;bool isEmpty(LinkQueue *q)if(q->front =NULL && q->rear = NULL) retur

24、n TRUE;return FALSE;isEmptyStatus Push(LinkQueue *q, ElemType e)Node *p = (Node*)malloc(sizeof(Node); if(!p)puts（"存儲空間分配失??！"）;return ERROR;p->data = e;p->next = NULL;/ 防止出現(xiàn)野指針if(isEmpty(q) 如果是空隊列，則front指向p (第一個元素)q->front = p;elseq->rear->next = p;q->rear = p;/q->rear指向隊尾return OK;PushStatus Pop(LinkQueue *q, ElemType *e)Node *p =