棧-隊列的順序-鏈?zhǔn)絻Υ娼Y(jié)構(gòu)(數(shù)據(jù)結(jié)構(gòu)試驗報告

1、.數(shù)據(jù)結(jié)構(gòu)實驗報告班 級： 計 學(xué) 號：姓 名：設(shè)計日期： 西安計算機(jī)學(xué)院實驗題目 1)棧的順序存儲結(jié)構(gòu) 2)棧的鏈?zhǔn)酱鎯Y(jié)構(gòu) 3)隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu) 4)隊列的循環(huán)存儲結(jié)構(gòu)2. 需求分析 本演示程序用C語言編寫，完成棧和列的初始化，入棧、出棧、輸出操作。1） 對于順序棧，入棧時要先判斷棧是否滿了，棧滿不能入棧，否則出現(xiàn)空間溢出；在進(jìn)棧出棧和讀取棧頂時先判棧是否為空，為空時不能操作。2） 在一個鏈隊表中需設(shè)定兩個指針分別指向隊列的頭和尾。3） 隊列的存儲結(jié)構(gòu)：注意要判斷隊滿和隊空。4） 程序所能達(dá)到的功能：完成棧的初始化，入棧，出棧和輸出操作；完成隊列的初始化，入隊列，出隊列和輸出操作。3.

2、概要設(shè)計 本程序包含1、棧的順序存儲結(jié)構(gòu)包含的函數(shù)：1） 主函數(shù)main（）2） 入棧函數(shù)Push（）3） 出棧函數(shù)Pop（）2、棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)包含的函數(shù)：1） 主函數(shù)main（）2） 入棧函數(shù)PushStack（）3） 退棧函數(shù)PopStack（）4） 取棧頂元素函數(shù)Getstack top（）3、隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)所包含的函數(shù)：1） 主函數(shù)main（）2） 入隊函數(shù)EnQueue（）3） 出隊函數(shù)DeQueue（）4 隊列的循環(huán)所包含的函數(shù)：1） 主函數(shù)main（）2） 初始化循環(huán)函數(shù)CircSeqQueue（）3） 入隊函數(shù)EnQueue（）4） 出隊函數(shù)DeQueue（）5） 取隊首

3、元素函數(shù)GetFront（）4. 詳細(xì)設(shè)計 1）棧的順序存儲結(jié)構(gòu)*include<stdio.h>*include<stdlib.h>*include<conio.h>*define MAXSIZE 20typedef int datatype;typedef struct datatype elemMAXSIZE; int top;SeqStack;int init(SeqStack *s) s->top=-1; return 1;void print(SeqStack *s)char ch; int i;if(s->top=-1)printf

4、("n 棧已空.");elsei=s->top;while(i!=-1)printf("n data=%d",s->elemi); i-;printf("n 按回車?yán)^續(xù)");ch=getch();void push(SeqStack *s,datatype x)if(s->top=MAXSIZE-1) printf("n 棧已滿！");else s->elem+s->top=x;datatype pop(SeqStack*s)datatype x;if(s->top=-1)pri

5、ntf("n 棧已空! "); x=-1;elsex=s->elems->top-;return(x);void main()SeqStack s; int k; datatype x;if(init(&s)do printf("nnn"); printf("n*"); printf("nn 1. x進(jìn)棧"); printf("nn 2.出棧返回其值"); printf("nn 3 結(jié)束"); printf("n*"); printf(

6、"n 請選擇(123)"); scanf("%d",&k); switch(k) case 1:printf("n 請輸入進(jìn)棧整數(shù) X=");scanf("%d",&x); push(&s,x);print(&s); break; case 2: x=pop(&s); printf("n 出棧元素:%d",x); print(&s); break; case 3:exit(0); printf("n-");while(k>

7、=1 &&k<3);printf("n 按回車返回");getch();else printf("n 初始化失敗！n");2) .棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)*include<stdio.h>*include<stdlib.h>typedef struct SNodeint data;struct SNode*next;SNode,*LinkStack;LinkStack top;LinkStack PushStack(LinkStack top,int x)/入棧LinkStack s;s=(LinkStack)mal

8、loc(sizeof(SNode);s->data=x;s->next=top;top=s;return top;LinkStack PopStack(LinkStack top) /退棧LinkStack p;if(top!=NULL)p=top;top=top->next;free(p);printf("退棧已完成n");return top;elseprintf("棧是空的，無法退棧！n");return 0;int GetStackTop(LinkStack top) /取棧頂元素return top->data;bool

9、 IsEmpty()return top=NULL"true:false;void Print()SNode*p;p=top;if(IsEmpty()printf("The stack is empty!n");return;while(p)printf("%d",p->data);p=p->next;printf("n");void main()int x,a,b;char m;do printf("n"); printf(" 鏈棧的基本操作 n"); printf(&q

10、uot; n"); printf(" 1.置空棧 n"); printf(" 2.進(jìn)棧 n"); printf(" 3.退棧 n"); printf(" 4.取棧頂元素 n"); printf(" 5.退出程序 n"); printf("n 請選擇一個數(shù)字（1 2 3 4 5）："); scanf("%c",&m);switch(m)case '1': top=NULL; printf("n棧已置空!"

11、); break;case '2': printf("請輸入要進(jìn)棧的元素個數(shù)是："); scanf("%d",&a); printf("n請輸入要進(jìn)棧的%d個元素:",a); for(b=0;b<a;b+) scanf("%d",&x); top=PushStack(top,x); printf("進(jìn)棧已完成！n"); printf("n輸出棧為:"); Print(); break;case '3': printf(&q

12、uot;n操作之前的輸出棧為:"); Print(); top=PopStack(top); printf("n操作過后的輸出棧為:"); Print(); break;case '4': printf("n輸出棧為:"); Print(); if(top!=NULL) printf("n棧頂元素是：%dn",GetStackTop(top); else printf("n棧是空的，沒有元素！"); break;case '5':break;default:printf(&

13、quot;n輸入的字符不對，請重新輸入!");break;getchar();while(m!='5');運(yùn)算結(jié)果:3） 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)*include<stdio.h>*include<stdlib.h>*include<conio.h>*include<stdio.h>*include<stdlib.h>*include<math.h>typedef int dataType;typedef struct node dataType data; struct node *next;QNod

14、e;typedef structQNode *front,*rear;LQueue;/*初始化*/int init(LQueue *q)if(q->front=(QNode *)malloc(sizeof(QNode)=NULL)return 0;q->rear=q->front;q->front->next=NULL;return 1;/*出隊*/void print(LQueue Q) QNode *p; char ch; p=Q.front->next; while(p!=NULL)printf("n%d",p->data);

15、 p=p->next; printf("n 按回車鍵繼續(xù)。"); ch=getch();/*入隊*/int EnQueue(LQueue *q,dataType x) QNode *p; if(p=(QNode*)malloc(sizeof(QNode)=NULL) return 0; p->data=x; p->next=NULL; q->rear->next=p; q->rear=p; return 1;/*出隊*/dataType DeQueue(LQueue *q)QNode *p;dataType x;if(q->fron

16、t=q->rear)printf("n 隊列空"); x=-1;elsep=q->front->next;q->front->next=p->next;x=p->data;free(p);if(q->front->next=NULL) q->rear=q->front;return(x);void main()int k;dataType e,x;char ch;LQueue Q;init(&Q);doprintf("nnn");printf("n*");pri

17、ntf("nn1.元素入隊列");printf("nn2.出隊列返回");printf("nn3.結(jié)束");printf("n*");printf("n請選擇(1,2,3)");scanf("%d",&k);switch(k)case 1:printf("n 進(jìn)隊 e=");scanf("%d",&e);EnQueue(&Q,e);print(Q);break;case 2:x=DeQueue(&Q);p

18、rintf("n 出隊元素:%d",x);print(Q); break;case 3:exit(0);printf("n-");while(k>=1&&k<3);printf("n按回車鍵，返回。");ch=getch();4） 隊列的循環(huán)存儲*include<stdio.h> *include<process.h> *include<iostream.h> *include<stdlib.h> *define MaxSize 100 typedef int

19、 ElemType; typedef struct ElemType dataMaxSize; int front; int rear; CircSeqQueue; /順序循環(huán)隊列的初始化 void QueueInitial(CircSeqQueue *pQ) /創(chuàng)建一個又指針pQ所指向的空順序循環(huán)隊列 pQ->front=pQ->rear=0; /順序循環(huán)隊列判空 int IsEmpty(CircSeqQueue *pQ) /順序循環(huán)隊列為空時返回1，否則返回0 return pQ->front=pQ->rear; /順序循環(huán)隊列判滿 int IsFull(CircS

20、eqQueue *pQ) /循環(huán)隊列為滿時返回1，否則返回0 return (pQ->rear+1)%MaxSize=pQ->front; /元素進(jìn)隊 void EnQueue(CircSeqQueue *pQ, ElemType e) /若隊列不滿，則元素e進(jìn)隊 if(IsFull(pQ)/隊列已滿，退出 printf("隊列溢出！n"); exit(1); pQ->rear=(pQ->rear+1)%MaxSize;/隊尾指針后移 pQ->datapQ->rear=e; /元素出隊 ElemType DeQueue(CircSeqQu

21、eue *pQ) /若循環(huán)隊列不為空，則刪除隊頭元素，并返回它的值 if(IsEmpty(pQ)/隊列為空，退出 printf("空隊列!n"); exit(1); pQ->front=(pQ->front+1)%MaxSize;/隊頭指針后移 return pQ->datapQ->front; /取隊頭元素 ElemType GetFront(CircSeqQueue *pQ) /若隊列不為空，則返回隊頭元素的值 if(IsEmpty(pQ) printf("空隊列!n"); exit(1); return pQ->dat

22、a(pQ->front+1)%MaxSize; /循環(huán)隊列置空 void MakeEmpty(CircSeqQueue *pQ) /將由指針pQ所指向的隊列變?yōu)榭钻?pQ->front=pQ->rear=0; void main() int k,m=1,n,i; CircSeqQueue *pQ; ElemType e; pQ=new CircSeqQueue; QueueInitial(pQ); while(k) printf("n*n");printf(" 1.元素進(jìn)隊 n");printf(" 2.元素出隊返回 n");printf(&quo