中國礦業(yè)大學計算機科學與技術系試驗報告課程名稱________數據結構_______試驗名稱____棧、隊列算法設計_________________班級____信息平安08-1_____姓名___________學號___________儀器組號_______實驗日期___09-11-18___實驗報告要求：1.實驗目的2.實驗內容3.實驗步驟4.程序清單5.運行結果6.流程圖7.實驗體會一實驗目的1熟悉棧、隊列這種特殊線性結構的特性；2熟練掌握棧、隊列在順序存儲結構和鏈表存儲結構下的根本操作。二、實驗要求：1實驗之前認真準備，編寫好源程序。2實驗中認真調試程序，對運行結果進行分析，注意程序的正確性和健壯性的驗證。3不斷積累程序的調試方法。三、實驗內容基此題〔必做〕：1分別就棧的順序存儲結構和鏈式存儲結構實現棧的各種根本操作。2假設以帶頭結點的循環(huán)鏈表表示隊列，并且只設一個指針指向對尾結點，不設頭指針，試設計相應的置隊空、入隊和出隊的程序。加強題：3設線性表A中有n個字符，試設計程序判斷字符串是否中心對稱，例如xyzyx和xyzzyx都是中心對稱的字符串。四、程序清單基此題:1.#include<iostream.h>#include<conio.h>#include<stdlib.h>constSTACK_INIT_SIZE=100; //存儲空間初始分配量constSTACKINCREMENT=10; //存儲空間分配增量typedefstruct{ int*base; //在構造之前和銷毀之后，base的值為NULL int*top; //棧頂指針 intstacksize; //當前已分配的存儲空間，以元素為單位}SqStack;voidInitStack(SqStack&S){ //構造一個空棧S S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int)); if(!S.base) exit(0); //存儲分配失敗 S.top=S.base; S.stacksize=STACK_INIT_SIZE; //cout<<"初始化完畢"<<endl;}//InitStackvoidGetTop(SqStackS,int&e){ //假設棧不空，那么用e返回S的棧頂元素，并返回OK；否那么返回ERROR if(S.top==S.base) { cout<<"此棧為空!!!"<<endl; exit(0); } e=*(S.top-1); cout<<e<<endl;// cout<<"取值結束"<<endl;}//GetTopvoidPush(SqStack&S,inte){ //插入元素e為新的棧頂元素 if(S.top-S.base>S.stacksize){//棧滿，追加存儲空間 S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int)); if(!S.base) { cout<<"新分配空間失?。。?！"<<endl; exit(0); } S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e;// cout<<"插入元素成功"<<endl;}//PushvoidPop(SqStack&S,int&e){ //假設棧不空，那么刪除S的棧頂元素，用e返回其值，并返回OK；否那么返回ERROR if(S.base==S.top) { cout<<"此棧為空棧，無法刪除?。?！"<<endl; exit(0); } e=*--S.top;// cout<<"刪除成功?。?！"<<endl;}//PopvoidClearStack(SqStack&S){ //把S置為空棧 if(S.base==S.top) cout<<"此棧已經為空!!!"<<endl; S.top=S.base;}//ClearStackvoidmain(){ SqStackStack; intm,n,x,y,z,i=0; InitStack(Stack); cout<<"請輸入您要建立的棧的大?。?<<endl; cin>>n; Stack.stacksize=n; do{ cout<<"請選擇操作："<<endl; cout<<""<<"1，進棧2，出棧3，查看棧頂值4，清空棧5，退出"<<endl; cin>>m; switch(m){ case1: cout<<"請輸入進棧值："<<endl; cin>>z; if(i==Stack.stacksize) { cout<<"Sorry!!!"<<endl<<"棧溢出!!"<<endl<<"此程序將退出!!!"<<endl; exit(0); } Push(Stack,z); i++; break; case2: Pop(Stack,x); cout<<x<<"出棧"<<endl; break; case3: cout<<"棧頂值為："<<endl; GetTop(Stack,y); break; case4: ClearStack(Stack); break; case5: cout<<"Exit!!"<<endl; break; default: cout<<"輸入錯誤?。?！此程序將退出！?。?<<endl; exit(0); }//switch }while(m!=5); getch();}2.#include<iostream.h>#include<conio.h>#include<stdlib.h>#include<iomanip.h>//鏈式棧typedefstructStack{ Stack*next; intdata;}Stack,*SLink;typedefstruct{ SLinktop; intlength;}SqStack;voidInitStack(SqStack&S){ //構造一個空棧 S.top=NULL; //設棧頂指針的初值為"空" S.length=0; //空棧中元素個數為}//InitStackvoidPush(SqStack&S,int&e){ //在棧頂之上插入元素e為新的棧頂元素 SLinkp; p=newStack; //建新的結點 p->data=e; p->next=S.top; S.top=p; ++S.length;}//PushvoidPop(SqStack&S,int&e){ //假設棧不空，那么刪除S的棧頂元素，用e返回其值 if(!S.top) { cout<<"此棧為空棧！??！"<<endl; exit(0); } e=S.top->data; S.top=S.top->next;}//PopvoidGetTop(SqStack&S,int&e){ //假設棧不空，取棧頂元素，用e返回其值 if(!S.top) { cout<<"此棧為空棧!!!"<<endl; exit(0); } e=S.top->data; cout<<e<<endl;}//GetTopvoidClearStack(SqStack&S){ // if(!S.top) cout<<"此棧已經為空!!!"<<endl; S.top=NULL;}//ClearStackvoidmain(){ SqStackStack; InitStack(Stack); intm,n,x,y,z,i=0; cout<<"請輸入您要建立的棧的大?。?<<endl; cin>>n; //需改正!!! do{ cout<<"請選擇操作："<<endl; cout<<""<<"1，進棧2，出棧3，查看棧頂值4，清空棧5，退出"<<endl; cin>>m; switch(m){ case1: cout<<"請輸入進棧值："<<endl; cin>>z; if(i==n) { cout<<"Sorry!!!"<<endl<<"棧溢出!!"<<endl<<"此程序將退出!!!"<<endl; exit(0); } Push(Stack,z); i++; break; case2: Pop(Stack,x); cout<<x<<"出棧"<<endl; break; case3: cout<<"棧頂值為："<<endl; GetTop(Stack,y); break; case4: ClearStack(Stack); break; case5: cout<<"Exit!!"<<endl; break; default: cout<<"輸入錯誤?。?！此程序將退出！??！"<<endl; exit(0); }//switch }while(m!=5); getch(); getch();}#include<iostream.h>#include<conio.h>#include<stdlib.h>//隊空、入隊和出隊intn=0;typedefstructQ{ intdata; Q*next;}Q,*QLink;voidInitQ(QLink&q){ //構造一個隊列 q->next=q;}//InitQvoidPush(QLink&q,int&e){ //入隊 QLinkp; p=newQ; p->data=e; p->next=q->next; q->next=p; n++;}//PushvoidOutQ(QLink&q,int&e){ //出隊 QLinkp; QLinkt; p=newQ; t=newQ; p=q; inti; for(i=0;i<=n;i++){ if(p->next->data==e) { t=p->next; p->next=t->next; deletet; break; }//if p=p->next; }//for if(i==(n+1)){ cout<<"您所輸入的值不存在！此程序將退出??！"<<endl; exit(0); }}//OutQvoidClearQ(QLink&q){ //置隊空 q=q->next;}//ClearQvoidcheckQ(QLink&q,int&e){ //查看隊尾元素 if(q->next==q){ cout<<"此隊列為空??！程序將退出??！"<<endl; exit(0); } e=q->next->data;}//checkvoidmain(){ intm,x,n,y; QLinkQu; Qu=newQ; InitQ(Qu); do{ cout<<"請選擇操作："<<endl; cout<<" 1,入隊2，出隊3，查看隊尾元素4，清空隊列5，退出"<<endl; cin>>x; switch(x){ case1: cout<<"請輸入您想插入的值："<<"\t"; cin>>m; Push(Qu,m); break; case2: cout<<"請輸入您想出隊的值："<<"\t"; cin>>n; OutQ(Qu,n); cout<<n<<"出隊"<<endl; break; case3: checkQ(Qu,y); cout<<"隊尾元素為："<<y<<endl; break; }//switch }while(x!=5);getch();}加強題：#include<iostream>#include<string>usingnamespacestd;boolcomp(charx,chary){ if(x==y) returntrue; else returnfalse;}//compvoidmain(){ charstr[100]; cout<<"請輸入字符串："<<endl; cin>>str; inti=0,m; while(str[i]){ i++; } m=i%2; if(m){ intp=i-1,q=0; intj; for(j=0;j<(i-1)/2;j++){ if(!comp(str[q++],str[p--])) break; }//for if(j==(i-1)/2) cout<<"此字符串對稱?。?！"<<endl; else cout<<"此字符串不對稱?。?！"<<endl; }//if else{ intp=i-1,q=0; intj; for(j=0;j<(i/2);j+