西南科技大學數(shù)據(jù)結構實驗報告棧的基本操作

1、西南科技大學數(shù)據(jù)結構實驗報告實驗名稱： 棧的基本操作 實驗環(huán)境： windows 7 VS2010 實驗類別： 指導教師： 專業(yè)班級： 姓 名： 學 號： 一、 實驗目的1、 掌握棧的鏈式存儲結構2、 學會棧基本運算的實現(xiàn)二、 實驗內(nèi)容我所做的實驗是實驗題3.2，編寫程序3-2.cpp，實現(xiàn)鏈棧的各種基本運算，并在此基礎上設計一個主程序完成如下功能（1）、初始化鏈棧s；（2）、判斷鏈棧s是否非空；（3）、依次進棧元素a,b,c,d,e;（4）、判斷鏈棧s是否非空；（5）、輸出鏈棧長度；（6）、輸出從棧頂?shù)綏５自?；?）、輸出出鏈棧序列；（8）、判斷鏈棧s是否非空；（9）、釋放鏈棧。三、 實驗

2、過程本次實驗我是用C+來完成的，鏈棧也就是采用單鏈表實現(xiàn)，鏈棧的優(yōu)點是不存在棧滿上溢的情況，規(guī)定棧的所有操作都是在單鏈表的表頭進行的，所以實現(xiàn)鏈棧也就是對單鏈表的簡化。下面具體介紹一下本次實驗的實驗過程：1、 初始化鏈棧要建立鏈棧的頭結點，并將其next域置為NULL。2、 鏈棧為空的條件是棧的指針的下一個指向空（s->next=NULL）,也就是單鏈表中沒有數(shù)據(jù)結點。3、 進棧也就是將新數(shù)據(jù)結點插入到頭結點之后。4、 鏈棧的長度也就是從第一個數(shù)據(jù)結點開始掃描單鏈表，從而保存訪問的數(shù)據(jù)結點的個數(shù)，然后將其值返回。5、 從棧頂?shù)綏５自氐妮敵鲆簿褪菑牡谝粋€數(shù)據(jù)結點開始掃描單鏈表嗎，并輸出當

3、前訪問結點的數(shù)據(jù)域值6、 輸出出棧序列是在棧不為空的條件下，將頭結點的指針域所指數(shù)據(jù)結點的數(shù)據(jù)域輸出，然后將其空間釋放，也就是刪除。7、 釋放鏈棧也就是對棧的銷毀，釋放棧占用的全部存儲空間四、 實驗結果本次實驗實現(xiàn)了棧的各種基本運算，并對其進行檢驗，均沒有發(fā)生錯誤，符合實驗要求。五、 實驗心得通過本次實驗，可以說我對單鏈表的操作再一次熟悉了一遍，并且了解到棧在實際應用當中也很廣泛，例如在計算器當中的表達式的求值可以用棧來實現(xiàn)，DFS深度優(yōu)先搜索也可以用棧來實現(xiàn)，從而解決了求解迷宮問題等等。通過學習棧，對大數(shù)據(jù)的處理也提供了遍歷，提高了代碼的可讀性。六、 實驗代碼#include<iost

4、ream>using namespace std;struct stack /定義鏈棧數(shù)據(jù)類型為stack，char data;/數(shù)據(jù)域stack *next;/指針域;stack *init()/該函數(shù)實現(xiàn)初始化鏈棧stack *s;s=new stack;/依然用new函數(shù)開辟空間s->next=NULL;/將其next域置為NULLreturn s;int emptystack(stack *s)/該函數(shù)實現(xiàn)鏈棧的判空操作return (s->next=NULL);/這里返回1為非空，0為空void push(stack *s,char ch)/該函數(shù)實現(xiàn)了進棧的功能i

5、nt i,q;stack *p; /首先要建立一個結點p=new stack;/為該結點開辟空間p->data=ch;/該結點的數(shù)據(jù)域為將進棧的元素p->next=s->next;/將p結點的下一個結點指向s結點的下一個結點，為了實現(xiàn)插入操作的對接s->next=p;/將s的下一個結點指向p，這樣就把p指向的數(shù)據(jù)插入到了s的后面int lengthstack(stack *s)/該函數(shù)實現(xiàn)了計算鏈棧的長度stack *p=s->next;/因為鏈棧s有頭結點，所以定義p指向s的下一個，因為s的下一個才有數(shù)據(jù)int n=0;while(p!=NULL)/通過棧中元素

6、指針指向地址遍歷實現(xiàn)計算鏈棧長度功能n+;/n的累加，返回鏈棧長度p=p->next;return n;void putstack(stack *s)/該函數(shù)實現(xiàn)了從棧頂?shù)綏５自氐妮敵?，其過程與計算鏈棧長度相似，只不過這次是把數(shù)據(jù)域中元素的輸出stack *p=s->next;while(p!=NULL)cout<<p->data;p=p->next;cout<<endl;void pop(stack *s)/該函數(shù)實現(xiàn)對棧中元素的輸出，是出棧功能，與上面的相似，這里就是多一個釋放空間的操作stack *p=s->next;stack *

7、q=s;if(q->next=NULL)return ;while(p!=NULL)cout<<p->data;q->next=p->next;/q指針跳過P指向的數(shù)據(jù)，直接指向p的下一個free(p);/釋放空間p=q->next;cout<<endl;void destroystack(stack *s)/該函數(shù)實現(xiàn)了對棧的銷毀，釋放棧的存儲空間stack *p=s,*q=s->next;while(q)/挨個對空間進行釋放free(p);p=q;q=p->next;free(p);int main()int n,m,p,i

8、,q,flag;char ch,c;stack *S=init();/下面實現(xiàn)界面的友好cout<<"1:輸入進棧元素"<<endl<<"2:判斷棧S是否為空"<<endl<<"3:輸出鏈棧S長度"<<endl<<"4:輸出從棧頂?shù)綏５自?quot;<<endl<<"5:輸出出鏈棧序列"<<endl<<"6:釋放鏈棧"<<endl;while

9、(1)/實現(xiàn)了人性化操作cout<<"請選擇："cin>>flag;if(flag=1)cout<<"請輸入要插入元素的個數(shù):"<<endl; cin>>q; cout<<"請輸入元素"<<endl;for(i=0;i<q;i+)cin>>ch;push(S,ch);if(flag=2)cout<<"判空:"<<emptystack(S)<<endl;if(flag=3)cout<<"鏈棧長度為："<<lengthstack(S)<<endl;if(flag=4)cout