西南科技大學(xué)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告棧的基本操作

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

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

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

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

5、nt i,q;stack *p; /首先要建立一個(gè)結(jié)點(diǎn)p=new stack;/為該結(jié)點(diǎn)開(kāi)辟空間p->data=ch;/該結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閷⑦M(jìn)棧的元素p->next=s->next;/將p結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向s結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，為了實(shí)現(xiàn)插入操作的對(duì)接s->next=p;/將s的下一個(gè)結(jié)點(diǎn)指向p，這樣就把p指向的數(shù)據(jù)插入到了s的后面int lengthstack(stack *s)/該函數(shù)實(shí)現(xiàn)了計(jì)算鏈棧的長(zhǎng)度stack *p=s->next;/因?yàn)殒湕有頭結(jié)點(diǎn)，所以定義p指向s的下一個(gè)，因?yàn)閟的下一個(gè)才有數(shù)據(jù)int n=0;while(p!=NULL)/通過(guò)棧中元素

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

7、q=s;if(q->next=NULL)return ;while(p!=NULL)cout<<p->data;q->next=p->next;/q指針跳過(guò)P指向的數(shù)據(jù)，直接指向p的下一個(gè)free(p);/釋放空間p=q->next;cout<<endl;void destroystack(stack *s)/該函數(shù)實(shí)現(xiàn)了對(duì)棧的銷(xiāo)毀，釋放棧的存儲(chǔ)空間stack *p=s,*q=s->next;while(q)/挨個(gè)對(duì)空間進(jìn)行釋放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();/下面實(shí)現(xiàn)界面的友好cout<<"1:輸入進(jìn)棧元素"<<endl<<"2:判斷棧S是否為空"<<endl<<"3:輸出鏈棧S長(zhǎng)度"<<endl<<"4:輸出從棧頂?shù)綏５自?quot;<<endl<<"5:輸出出鏈棧序列"<<endl<<"6:釋放鏈棧"<<endl;while

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