1、數據結構實驗報告班級：計學號：姓名：設計日期：西安計算機學院實驗題目1)棧的順序存儲結構2)棧的鏈式存儲結構3)隊列的鏈式存儲結構4)隊列的循環存儲結構2.需求分析本演示程序用c 語言編寫，完成棧和列的初始化，入棧、出棧、輸出操作。1）對于順序棧，入棧時要先判斷棧是否滿了，棧滿不能入棧，否則出現空間溢出； 在進棧出棧和讀取棧頂時先判棧是否為空，為空時不能操作。2）在一個鏈隊表中需設定兩個指針分別指向隊列的頭和尾。3）隊列的存儲結構：注意要判斷隊滿和隊空。4）程序所能達到的功能： 完成棧的初始化，入棧，出棧和輸出操作；完成隊列的初始化，入隊列，出隊列和輸出操作。3.概要設計本程序包含1、棧的順序

2、存儲結構包含的函數：1）主函數 main（）2）入棧函數 push（）3）出棧函數 pop（）2、棧的鏈式存儲結構包含的函數：1）主函數 main（）2）入棧函數 pushstack （）3）退棧函數 popstack （）4）取棧頂元素函數getstack top （）3、隊列的鏈式存儲結構所包含的函數：1）主函數 main（）2）入隊函數 enqueue （）3）出隊函數 dequeue （）4 隊列的循環所包含的函數：1）主函數 main（）2）初始化循環函數circseqqueue （）3）入隊函數 enqueue （）4）出隊函數 dequeue （）5）取隊首元素函數getfron

3、t（）4.詳細設計1）棧的順序存儲結構#include #include #include #define maxsize 20 typedef 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(n 棧已空 .); elsei=s-top; while(i!=-1)printf(n data=%d,s-el

4、emi); i-; printf(n 按回車繼續 );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)printf(n 棧已空 ! ); x=-1; elsex=s-elems-top-; return(x); void main() seqstack s; int k; datatype x; if(init(&s) do pri

5、ntf(nnn); printf(n*); printf(nn 1. x 進棧 ); printf(nn 2.出棧返回其值 ); printf(nn 3 結束); printf(n*); printf(n 請選擇 (123); scanf(%d,&k); switch(k) case 1:printf(n 請輸入進棧整數x=?);scanf(%d,&x); push(&s,x);print(&s); break; case 2: x=pop(&s); printf(n 出棧元素 :%d,x); print(&s); break; case 3:e

6、xit(0); printf(n-); while(k=1 &k3); printf(n 按回車返回 ); getch(); else printf(n 初始化失敗！ n); 2).棧的鏈式存儲結構#include #include typedef struct snode int data; struct snode*next; snode,*linkstack; linkstack top; linkstack pushstack(linkstack top,int x)/入棧 linkstack s; s=(linkstack)malloc(sizeof(snode); s-da

7、ta=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; else printf( 棧是空的，無法退棧！n); return 0; int getstacktop(linkstack top) /取棧頂元素 return top-data; bool isempty() return top=null?true:false; voi

8、d 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( n); printf( 1.置空棧n); printf( 2.進棧n); printf( 3.退棧n); printf( 4.取棧頂元素n); printf( 5.退出程序n); printf(n 請選

9、擇一個數字（1 2 3 4 5） ：); scanf(%c,&m); switch(m) case 1: top=null; printf(n 棧已置空 !); break; case 2: printf( 請輸入要進棧的元素個數是：); scanf(%d,&a); printf(n 請輸入要進棧的%d 個元素 :,a); for(b=0;ba;b+) scanf(%d,&x); top=pushstack(top,x); printf( 進棧已完成！ n); printf(n 輸出棧為 :); print(); break; case 3: printf(n 操作之前

10、的輸出棧為:); 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(n 輸入的字符不對，請重新輸入!); break; getchar(); while(m!=5); 運算結果 : 3）隊列的鏈式存儲結構#inclu

11、de #include #include #include #include #include typedef int datatype; typedef struct node datatype data; struct node *next; qnode; typedef struct qnode *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

12、 1; /*出隊 */ void print(lqueue q) qnode *p; char ch; p=q.front-next; while(p!=null)printf(n%d,p-data); p=p-next; printf(n 按回車鍵繼續。); 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

13、1; /*出隊 */ datatype dequeue(lqueue *q) qnode *p; datatype x; if(q-front=q-rear) printf(n 隊列空 ); x=-1; else p=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); do printf(nnn); printf

14、(n*); printf(nn 1.元素入隊列 ); printf(nn 2.出隊列返回 ); printf(nn 3.結束 ); printf(n*); printf(n 請選擇 (1,2,3); scanf(%d,&k); switch(k) case 1:printf(n 進隊e=?); scanf(%d,&e); enqueue(&q,e); print(q); break; case 2:x=dequeue(&q); printf(n 出隊元素 :%d,x); print(q); break; case 3:exit(0); printf(n-); w

15、hile(k=1&k3); printf(n 按回車鍵，返回。); ch=getch(); 4）隊列的循環存儲#include #include #include #include #define maxsize 100 typedef int elemtype; typedef struct elemtype datamaxsize; int front; int rear; circseqqueue; /順序循環隊列的初始化void queueinitial(circseqqueue *pq) /創建一個又指針pq 所指向的空順序循環隊列pq-front=pq-rear=0; /順

16、序循環隊列判空int isempty(circseqqueue *pq) / 順序循環隊列為空時返回1，否則返回 0 return pq-front=pq-rear; /順序循環隊列判滿int isfull(circseqqueue *pq) / 循環隊列為滿時返回1，否則返回 0 return (pq-rear+1)%maxsize=pq-front; /元素進隊void enqueue(circseqqueue *pq, elemtype e) / 若隊列不滿，則元素e 進隊if(isfull(pq)/ 隊列已滿，退出 printf( 隊列溢出！ n); exit(1); pq-rear=

17、(pq-rear+1)%maxsize;/ 隊尾指針后移pq-datapq-rear=e; /元素出隊elemtype dequeue(circseqqueue *pq) / 若循環隊列不為空，則刪除隊頭元素，并返回它的值if(isempty(pq)/ 隊列為空，退出 printf( 空隊列 !n); exit(1); pq-front=(pq-front+1)%maxsize;/隊頭指針后移return pq-datapq-front; /取隊頭元素elemtype getfront(circseqqueue *pq) / 若隊列不為空，則返回隊頭元素的值if(isempty(pq) pri

18、ntf( 空隊列 !n); exit(1); return pq-data(pq-front+1)%maxsize; /循環隊列置空void makeempty(circseqqueue *pq) / 將由指針 pq 所指向的隊列變為孔隊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.元素進隊n); printf( 2.元素出隊返回n); printf( 3.取首元素n); printf( 4.隊列置空); printf(n*n); printf( 請選擇 :(1,2,3)n); scanf(%d,&m); switch(m) case 0:return; case 1: printf( 請輸入入隊元素的個數：n); scanf(%d,&n); printf( 輸入元素，入隊n); for(i=0;in;i+) scanf(%d,&e); enqueue(pq,e); bre