棧和隊列的基本操作的實現(xiàn)

封面：安徽大學(xué)網(wǎng)絡(luò)工程棧和隊列的根本操作的實現(xiàn)______2010\4\12【實驗?zāi)康摹坷斫獠⒄莆諚：完犃械倪壿嫿Y(jié)構(gòu)和存儲結(jié)構(gòu)；理解棧和隊列的相關(guān)根本運算；編程對相關(guān)算法進行驗證?！緦嶒瀮?nèi)容】〔一〕分別在順序和鏈式存儲結(jié)構(gòu)上實現(xiàn)棧的以下操作〔含初始化，入棧，出棧，取棧頂元素等〕：構(gòu)造一個棧S，將構(gòu)造好的棧輸出；在第1步所構(gòu)造的棧S中將元素e入棧，并將更新后的棧S輸出；在第2步更新后所得到的棧S中將棧頂元素出棧，用變量e返回該元素，并將更新后的棧S輸出?！捕撤謩e在鏈隊列和循環(huán)隊列上實現(xiàn)以下操作〔初始化，入隊，出隊，取隊頭元素等〕：1.構(gòu)造一個隊列Q，將構(gòu)造好的隊列輸出；2.在第1步所構(gòu)造的隊列Q中將元素e入隊，并將更新后的隊列Q輸出；3.在第2步更新后所得到的隊列Q中將隊頭元素出隊，用變量e返回該元素，并將更新后的隊列Q輸出?！疽蟆織：完犃兄械脑匾獜慕K端輸入；具體的輸入和輸出格式不限；算法要具有較好的健壯性，對運行過程中的錯誤操作要做適當處理。三、實驗步驟1．本實驗用到的數(shù)據(jù)結(jié)構(gòu)(1)邏輯結(jié)構(gòu)：線性結(jié)構(gòu)(2)存儲結(jié)構(gòu)：程序一、四〔順序存儲結(jié)構(gòu)〕；程序二、三〔鏈式存儲結(jié)構(gòu)〕；2．各程序的功能和算法設(shè)計思想程序一：順序棧#include<stdio.h>#include<malloc.h>#include<process.h>#defineSTACKINITISIZE100#defineSTACKINCREMENT10#defineOK1#defineERROR0#defineOVERFLOW-2typedefintSElemtype;typedefintstatus;typedefstruct{SElemtype*base;SElemtype*top;intstacksize;}sqstack;voidInitstack(sqstack*s){(*s).base=(SElemtype*)malloc(STACKINITISIZE*sizeof(SElemtype));if(!(*s).base)exit(OVERFLOW);(*s).top=(*s).base;(*s).stacksize=STACKINITISIZE;}voidpush(sqstack*s,SElemtypee){if((*s).top-(*s).base>=(*s).stacksize){(*s).base=(SElemtype*)realloc((*s).base,((*s).stacksize+STACKINCREMENT)*sizeof(SElemtype));if(!(*s).base)exit(OVERFLOW);(*s).top=(*s).base+(*s).stacksize;(*s).stacksize+=STACKINCREMENT;}*(*s).top++=e;}statusGettop(sqstacks){inte;if(s.top==s.base)returnERROR;e=*(s.top-1);printf("棧頂元素是%d\n",e);returnOK;}statuspop(sqstack*s){intf;if((*s).top==(*s).base)returnERROR;f=*(--(*s).top);printf("出棧元素是%d\n",f);returnOK;}voidstackTraverse(sqstacks){ SElemtype*p=s.base;while(s.top>p) printf("%d",*p++);printf("\n");}voidmain(){ inth,k,e,i; sqstackla; printf("構(gòu)建一個空棧\n");Initstack(&la); printf("請輸入棧內(nèi)元素的個數(shù)\n"); scanf("%d",&k);printf("請輸入%d個元素\n",k); for(i=0;i<k;i++){ scanf("%d",&e); push(&la,e); } printf("\n"); printf("輸出棧內(nèi)所有元素\n");stackTraverse(la); fflush(stdin);printf("查找棧頂元素\n");Gettop(la); printf("刪除棧頂元素\n"); pop(&la); printf("輸出棧內(nèi)所有元素\n");stackTraverse(la); fflush(stdin); printf("\n"); printf("插入一個元素\n"); printf("請輸入插入的元素值\n"); scanf("%d",&h); push(&la,h); printf("輸出棧內(nèi)所有元素\n");stackTraverse(la); printf("\n");}功能：實現(xiàn)順序棧的各種功能，如能建立空棧，實現(xiàn)棧的初始化，插入，刪除棧頂元素等操作。算法設(shè)計思想：首先建立一個空棧，再實現(xiàn)棧的初始化，用一個主函數(shù)包涵棧的各種操作。程序調(diào)式如下：程序二：鏈棧//shuju3.cpp:定義控制臺應(yīng)用程序的入口點。#include"stdafx.h"#include<malloc.h>#include<stdio.h>#include<process.h>#defineOK1#defineERROR0typedefintstatus;typedefstructSNode{intdata;structSNode*next;}SNode,*Sqstack;voidCreatesqstack(Sqstack*l,intn){inti; Sqstacks; *l=(Sqstack)malloc(sizeof(SNode)); (*l)->next=NULL; printf("請輸入%d個元素\n",n);for(i=n;i>0;--i){ s=(Sqstack)malloc(sizeof(SNode)); scanf("%d",&(s->data));s->next=(*l)->next; (*l)->next=s; }}statusGetelem(Sqstack*l,int*e){ Sqstacks; s=(*l)->next; *e=s->data; printf("頭元素是%d\n",*e);returnOK;}statusinsertsqtack(Sqstackl,inte,intn){ Sqstackp,s;inti; p=l;for(i=0;i<n;i++){ p=p->next; }s=(Sqstack)malloc(sizeof(SNode)); s->data=e; p->next=s; s->next=NULL;returnOK;}statusDeletesqstack(Sqstackl){inth; Sqstackp,q; p=l;q=p->next;p->next=q->next;h=q->data;printf("刪除的元素是%d",h);free(q);returnOK;}voidsqstackTraverse(Sqstackl){Sqstackp; p=l->next;while(p){ printf("%d",p->data); p=p->next; }}voidmain(){inti,j,n,k,e;Sqstackla; printf("請輸入鏈棧的長度\n"); scanf("%d",&n);printf("建立一個鏈棧\n"); Createsqstack(&la,n); printf("輸出各元素\n"); printf("la=");sqstackTraverse(la); fflush(stdin); printf("\n"); printf("查找棧頂元素\n"); Getelem(&la,&e); fflush(stdin);printf("\n"); printf("插入新的棧頂元素\n"); scanf("%d",&e);insertsqtack(la,e,n); printf("輸出各元素\n"); printf("la=");sqstackTraverse(la); fflush(stdin);printf("\n"); printf("刪除棧頂元素\n");Deletesqstack(la);printf("輸出各元素\n"); printf("la=");sqstackTraverse(la); printf("\n");}功能：實現(xiàn)鏈棧的根本功能，如初始化，刪除，插入，查找棧頂元素等。算法設(shè)計思想：利用單鏈表的形式建立一個鏈棧，定義一個結(jié)構(gòu)體，利用指針指向，建立鏈棧的具有不同功能的函數(shù)〔刪除、插入、查找等〕，利用主函數(shù)合理安排順序?qū)崿F(xiàn)鏈棧操作。調(diào)試情況如下：程序三:鏈隊列//SHUJU.cpp:定義控制臺應(yīng)用程序的入口點。\\鏈隊列的建立#include"stdafx.h"#include<stdio.h>#include<malloc.h>#include<process.h>#defineOK1#defineERROR0#defineOVERFLOW-2typedefintQElemtype;typedefintstatus;typedefstructQNode{ QElemtypedata;structQNode*next;}QNode,*Queueptr;typedefstruct{ Queueptrfront; Queueptrrear;}LinkQueue;statusInitQueue(LinkQueue&Q){ Q.front=(Queueptr)malloc(sizeof(QNode));Q.rear=Q.front;if(!Q.front) exit(OVERFLOW); Q.front->next=NULL;returnOK;}statusDestoryQueue(LinkQueue&Q){while(Q.front){ Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; }returnOK;}statusEnQueue(LinkQueue&Q,QElemtypee){ Queueptrp; p=(Queueptr)malloc(sizeof(QNode));if(!p) exit(OVERFLOW); p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p;returnOK;}statusDeQueue(LinkQueue&Q,QElemtype&e){ Queueptrp;if(Q.front==Q.rear)returnERROR; p=Q.front->next; e=p->data; Q.front->next=p->next;if(Q.rear==p) Q.rear=Q.front; free(p);returnOK;}statusGethead(LinkQueue&Q){ Queueptrp; QElemtypee;if(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data; printf("頭元素是%d",e); printf("\n");returnOK;}statusQueueqTraverse(LinkQueueQ){Queueptrp; p=Q.front->next;while(p){ printf("%d",p->data); p=p->next; } printf("\n");returnOK;}voidmain(){ LinkQueuela; QElemtypee,k;inth,i; printf("構(gòu)建一個空隊列\(zhòng)n");InitQueue(la); printf("請輸入元素個數(shù)\n");scanf("%d",&h); printf("請輸入%d個元素\n",h);for(i=0;i<h;i++){ scanf("%d",&e);EnQueue(la,e); }printf("輸出隊列內(nèi)的元素\n");QueueqTraverse(la);fflush(stdin); printf("\n"); printf("獲得對列的頭元素\n");Gethead(la);printf("輸出隊列內(nèi)的元素\n");QueueqTraverse(la);fflush(stdin); printf("\n");printf("開始插入一元素\n"); printf("請輸入插入元素\n"); scanf("%d",&k);EnQueue(la,k);printf("輸出隊列內(nèi)的元素\n");QueueqTraverse(la);fflush(stdin); printf("\n"); printf("刪除對頭的元素\n");DeQueue(la,e); printf("刪除的元素是%d\n",e);printf("輸出隊列內(nèi)的元素\n");QueueqTraverse(la);fflush(stdin); printf("\n"); printf("摧毀隊列\(zhòng)n");DestoryQueue(la);printf("輸出隊列內(nèi)的元素\n");QueueqTraverse(la);}功能：實現(xiàn)鏈隊列的各種不同的操作，如隊列的初始化，隊列的插入，刪除，查詢以及摧毀隊列等。算法設(shè)計思想：構(gòu)建兩個不同的結(jié)構(gòu)體，如下：typedefstructQNode{ QElemtypedata;structQNode*next;}QNode,*Queueptr;typedefstruct{ Queueptrfront; Queueptrrear;}LinkQueue;其中有指向頭和尾的front和rear指針，利用它們構(gòu)建鏈隊列。調(diào)試情況如下：程序四：循環(huán)隊列//shujiu4.cpp:定義控制臺應(yīng)用程序的入口點。#include"stdafx.h"#include<stdio.h>#include<malloc.h>#include<process.h>#defineMAXSIZE10#defineOK1#defineERROR0#defineOVERFLOW-2typedefintQElemtype;typedefintstatus;typedefstruct{ QElemtype*base;intfront;intrear;}sqQueue;statusInitQueue(sqQueue&Q){ Q.base=(QElemtype*)malloc(MAXSIZE*sizeof(QElemtype));if(!Q.base) exit(OVERFLOW); Q.front=Q.rear=0;returnOK;}statusQueueLength(sqQueueQ){QElemtypex; x=(Q.rear-Q.front+MAXSIZE)%MAXSIZE;printf("隊列的元素個數(shù)是%d",x);returnOK;}statusEnQueue(sqQueue&Q,QElemtypee){if((Q.rear+1)%MAXSIZE==Q.front)returnERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXSIZE;returnOK;}statusDeQueue(sqQueue&Q){QElemtypee;if(Q.front==Q.rear)returnERROR; e=Q.base[Q.front]; printf("刪除的元素是%d",e); Q.front=(Q.front+1)%MAXSIZE;returnOK;}statusGetQueue(sqQueue&Q){ QElemtypee; e=Q.base[Q.front]; printf("頭元素是%d",e); printf("\n");returnOK;}statusQueueTraverse(sqQueue&Q,intk){ QElemtypeh,i; i=Q.front;for(;k>0;k--){ h=Q.base[Q.front]; printf("%d