




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、實(shí)驗(yàn)二 棧和隊(duì)列1、實(shí)驗(yàn)?zāi)康模海?) 熟悉棧的特點(diǎn)(先進(jìn)后出)及棧的基本操作,如入棧、出棧等,掌握棧的基本操作在棧的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn);(2) 熟悉隊(duì)列的特點(diǎn)(先進(jìn)先出)及隊(duì)列的基本操作,如入隊(duì)、出隊(duì)等,掌握隊(duì)列的基本操作在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。2、實(shí)驗(yàn)要求:(1) 復(fù)習(xí)課本中有關(guān)棧和隊(duì)列的知識(shí);(2) 用C語言完成算法和程序設(shè)計(jì)并上機(jī)調(diào)試通過;(3) 撰寫實(shí)驗(yàn)報(bào)告,給出算法思路或流程圖和具體實(shí)現(xiàn)(源程序)、算法分析結(jié)果(包括時(shí)間復(fù)雜度、空間復(fù)雜度以及算法優(yōu)化設(shè)想)、輸入數(shù)據(jù)及程序運(yùn)行結(jié)果(必要時(shí)給出多種可能的輸入數(shù)據(jù)和運(yùn)行結(jié)果)。3、實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)1 棧的順
2、序表示和實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容與要求:編寫一個(gè)程序?qū)崿F(xiàn)順序棧的各種基本運(yùn)算,并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序,完成如下功能:(1)初始化順序棧(2)插入元素(3)刪除棧頂元素(4)取棧頂元素(5)遍歷順序棧(6)置空順序棧分析:棧的順序存儲(chǔ)結(jié)構(gòu)簡稱為順序棧,它是運(yùn)算受限的順序表。對(duì)于順序棧,入棧時(shí),首先判斷棧是否為滿,棧滿的條件為:p->top= =MAXNUM-1,棧滿時(shí),不能入棧; 否則出現(xiàn)空間溢出,引起錯(cuò)誤,這種現(xiàn)象稱為上溢。出棧和讀棧頂元素操作,先判棧是否為空,為空時(shí)不能操作,否則產(chǎn)生錯(cuò)誤。通常??兆鳛橐环N控制轉(zhuǎn)移的條件。注意:(1)順序棧中元素用向量存放(2)棧底位置是固定不變的,可設(shè)置在向量
3、兩端的任意一個(gè)端點(diǎn)(3)棧頂位置是隨著進(jìn)棧和退棧操作而變化的,用一個(gè)整型量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 structSElemType *base;SElemType *top;i
4、nt stacksize;SqStack;/初始化棧Status InitStack(SqStack *s)s->base = (SElemType *)malloc(INIT_SIZE * sizeof(SElemType);if(!s->base)puts("存儲(chǔ)空間分配失??!");return Error;s->top = s->base;s->stacksize = INIT_SIZE;return Ok;/清空棧Status ClearStack(SqStack *s) s->top = s->base; return O
5、k; /棧是否為空Status StackEmpty(SqStack *s) if(s->top = s->base) return True; else return 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)s->base = (SElemType *)realloc(s->base, (s->stacksize + STACKINCREMENT) * sizeof(SElemType);if(!s->base)puts("存儲(chǔ)空間分配失??!");return Error;s->top = s->base + s-
7、>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-&g
8、t;top; 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("請(qǐng)輸入要進(jìn)棧的個(gè)數(shù):");scanf("%d", &n);while(n-)int m;scanf("%d",
9、&m);Push(s, m);StackTraverse(s, visit);puts("");Pop(s, &e);printf("%dn", e);printf("%dn", *s->top);Destroy(s);return 0;實(shí)驗(yàn)2 棧的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)實(shí)驗(yàn)內(nèi)容與要求:編寫一個(gè)程序?qū)崿F(xiàn)鏈棧的各種基本運(yùn)算,并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序,完成如下功能:(1)初始化鏈棧(2)鏈棧置空(3)入棧(4)出棧(5)取棧頂元素(6)遍歷鏈棧分析:鏈棧是沒有附加頭結(jié)點(diǎn)的運(yùn)算受限的單鏈表。棧頂指針就是鏈表的頭指針。注意:(
10、1)LinkStack結(jié)構(gòu)類型的定義可以方便地在函數(shù)體中修改top指針本身(2)若要記錄棧中元素個(gè)數(shù),可將元素個(gè)數(shù)屬性放在LinkStack類型中定義。(3)鏈棧中的結(jié)點(diǎn)是動(dòng)態(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 nodeElemType data;struct node *next;St
11、ackNode;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,
12、 ElemType 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("??? 不能進(jìn)行彈棧操作!");return ERROR;s->top = p->next;e = p->data
13、;free(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("請(qǐng)輸入鏈棧長度:n");scanf("%d", &n);puts("請(qǐng)輸入要錄入的數(shù)據(jù):&qu
14、ot;);while(n-)int x;scanf("%d", &x);Push(&s, x);PrintStack(&s);SetEmpty(&s);return 0; 實(shí)驗(yàn)3 隊(duì)列的順序表示和實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容與要求編寫一個(gè)程序?qū)崿F(xiàn)順序隊(duì)列的各種基本運(yùn)算,并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序,完成如下功能:(1)初始化隊(duì)列(2)建立順序隊(duì)列(3)入隊(duì)(4)出隊(duì)(5)判斷隊(duì)列是否為空(6)取隊(duì)頭元素(7)遍歷隊(duì)列分析:隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列,順序隊(duì)列實(shí)際上是運(yùn)算受限的順序表。入隊(duì)時(shí),將新元素插入rear所指的位置,然后將rear加1。出隊(duì)
15、時(shí),刪去front所指的元素,然后將front加1并返回被刪元素。順序隊(duì)列中的溢出現(xiàn)象:(1) "下溢"現(xiàn)象。當(dāng)隊(duì)列為空時(shí),做出隊(duì)運(yùn)算產(chǎn)生的溢出現(xiàn)象?!跋乱纭笔钦,F(xiàn)象,常用作程序控制轉(zhuǎn)移的條件。(2) "真上溢"現(xiàn)象。當(dāng)隊(duì)列滿時(shí),做進(jìn)棧運(yùn)算產(chǎn)生空間溢出的現(xiàn)象?!罢嫔弦纭笔且环N出錯(cuò)狀態(tài),應(yīng)設(shè)法避免。(3) "假上溢"現(xiàn)象。由于入隊(duì)和出隊(duì)操作中,頭尾指針只增加不減小,致使被刪元素的空間永遠(yuǎn)無法重新利用。當(dāng)隊(duì)列中實(shí)際的元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于向量空間的規(guī)模時(shí),也可能由于尾指針已超越向量空間的上界而不能做入隊(duì)操作。該現(xiàn)象稱為"假上溢&qu
16、ot;現(xiàn)象。注意:(1)當(dāng)頭尾指針相等時(shí),隊(duì)列為空。(2)在非空隊(duì)列里,隊(duì)頭指針始終指向隊(duì)頭元素,尾指針始終指向隊(duì)尾元素的下一位置。#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 structQElemType *base;int front, rear;SqQu
17、eue;/初始化循環(huán)隊(duì)列int InitQueue(SqQueue &Q)Q.base = (QElemType*)malloc(MaxQSize*sizeof(QElemType);if (Q.base = NULL)puts("分配內(nèi)存空間失?。?quot;); exit(OVERFLOW);Q.front = Q.rear = 0;return 0;/將循環(huán)隊(duì)列清空int ClearQueue(SqQueue &Q)Q.front = Q.rear = 0;/求隊(duì)列元素的個(gè)數(shù)int QueueLength(SqQueue Q)return (Q.rear - Q
18、.front + MaxQSize) % MaxQSize;/插入元素到循環(huán)隊(duì)列int EnSqQueue(SqQueue &Q, QElemType e)if (Q.rear + 1) % MaxQSize = Q.front)return ERROR; /隊(duì)列滿Q.baseQ.rear = e; /元素e入隊(duì)Q.rear = (Q.rear + 1) % MaxQSize; /修改隊(duì)尾指針return OK;/從循環(huán)隊(duì)列中刪除元素int DeSqQueue(SqQueue &Q, QElemType &e)if (Q.front = Q.rear)return ER
19、ROR;e = Q.baseQ.front; /取隊(duì)頭元素至eQ.front = (Q.front + 1) % MaxQSize; /修改隊(duì)頭指針,如果超內(nèi)存,循環(huán) return OK;/判斷一個(gè)循環(huán)隊(duì)列是否為空隊(duì)列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個(gè)數(shù)據(jù)進(jìn)隊(duì)列EnSqQueue(Q, i);i = Queue
20、Length(Q);printf("隊(duì)列里的元素有%d個(gè)n", i);for (i=0; i<3; i+)DeSqQueue(Q, e);printf("%d ", e);printf("n");i = QueueLength(Q);printf("隊(duì)列里的元素有%d個(gè)n", i);for (i=10; i<12; i+)EnSqQueue(Q, i);i = QueueLength(Q);printf("隊(duì)列里的元素有%d個(gè)n", i);ClearQueue(Q);i = Queu
21、eLength(Q);printf("隊(duì)列里的元素有%d個(gè)n", i);return 0;實(shí)驗(yàn)4 隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)實(shí)驗(yàn)內(nèi)容與要求:編寫一個(gè)程序?qū)崿F(xiàn)鏈隊(duì)列的各種基本運(yùn)算,并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序,完成如下功能:(1)初始化并建立鏈隊(duì)列(2)入鏈隊(duì)列(3)出鏈隊(duì)列(4)遍歷鏈隊(duì)列分析:隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡稱為鏈隊(duì)列。它是限制僅在表頭刪除和表尾插入的單鏈表。注意:(1)和鏈棧類似,無須考慮判隊(duì)滿的運(yùn)算及上溢。(2)在出隊(duì)算法中,一般只需修改隊(duì)頭指針。但當(dāng)原隊(duì)中只有一個(gè)結(jié)點(diǎn)時(shí),該結(jié)點(diǎn)既是隊(duì)頭也是隊(duì)尾,故刪去此結(jié)點(diǎn)時(shí)亦需修改尾指針,且刪去此結(jié)點(diǎn)后隊(duì)列變空。(3)和單鏈表類似,為
22、了簡化邊界條件的處理,在隊(duì)頭結(jié)點(diǎn)前可附加一個(gè)頭結(jié)點(diǎn)。#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 InitQueue(LinkQueue
23、 *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("隊(duì)列已銷毀!"); return OK;bool isEmpty(LinkQueue *q) if(q->front =NULL && q->rear = NULL) return
24、TRUE; return FALSE;/isEmptyStatus Push(LinkQueue *q, ElemType e)Node *p = (Node*)malloc(sizeof(Node);if(!p)puts("存儲(chǔ)空間分配失敗!");return ERROR;p->data = e;p->next = NULL;/防止出現(xiàn)野指針if(isEmpty(q)/如果是空隊(duì)列,則front指向p(第一個(gè)元素) q->front = p;else q->rear->next = p; q->rear = p;/q->rear指向隊(duì)尾return OK;/PushStatus Pop(LinkQueue *q, ElemType *e) Node *p = q->front; if(isEmpty(q) puts(&qu
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 眉山中學(xué)面試題及答案
- 計(jì)算機(jī)二級(jí)考試題庫及答案
- 開發(fā)崗位面試題及答案
- 社團(tuán)司儀面試題及答案
- 適用于船舶含油廢水處理的生物質(zhì)基濾膜制備及性能研究
- 2025年高考真題-語文(全國二卷) 含解析
- 綠色建筑屋頂花園行業(yè)深度調(diào)研及發(fā)展項(xiàng)目商業(yè)計(jì)劃書
- 曲藝音樂保護(hù)AI應(yīng)用行業(yè)深度調(diào)研及發(fā)展項(xiàng)目商業(yè)計(jì)劃書
- 中國傳統(tǒng)節(jié)日元宵節(jié)習(xí)俗民俗簡介介紹主題班會(huì)0
- 2.2.2 城鎮(zhèn)化過程中出現(xiàn)的問題(42張內(nèi)嵌視頻)
- IgG4相關(guān)性疾病課件
- 腰椎ODI評(píng)分完整版
- 實(shí)驗(yàn)五探索淀粉酶對(duì)淀粉和蔗糖水解的作用
- DB51-T 3041-2023佯黃竹豐產(chǎn)栽培技術(shù)規(guī)程
- GB/T 3091-2015低壓流體輸送用焊接鋼管
- GB/T 17530.5-1998工業(yè)丙烯酸及酯中阻聚劑的測定
- 廣東省東莞市《財(cái)務(wù)會(huì)計(jì)知識(shí)》事業(yè)單位國考真題
- 前道設(shè)備簡介及設(shè)計(jì)方法
- 交通指揮疏導(dǎo)技戰(zhàn)術(shù)培訓(xùn)課件交警培訓(xùn)專用
- 圖解通信施工安全隱患
- 實(shí)際控制人股東會(huì)決議
評(píng)論
0/150
提交評(píng)論