南方醫科大學生物醫學工程學院__電子信息工程_系數據結構實驗報告PAGEPAGE5姓名田媛學號113200880200009專業年級08電子信息工程單元第3章內容棧和隊列的應用日期2010-6-1實驗題目實驗二棧和隊列的應用（綜合性實驗3學時）實驗目的本次實習的目的在于深入了解棧和隊列的特征，以便在實際問題背景下靈活運用它們；同時還將鞏固這兩種結構的構造方法，接觸較復雜問題的遞歸算法設計。實驗內容一、必做題（選做兩題）：二、選做題：1、火車車廂調度問題[問題描述]假設停在鐵路調試站入口處車廂序列的編號依次為：1，2，3，…，n。設計一個程序，求出所有可能由此輸出的長度為n的車廂序列。[基本要求]程序對棧的任何存取（即更改，讀取和狀態判別等操作）必須借助于基本運算進行。[測試數據]分別取n=1，2，3和4。實驗要求及討論（本次實驗的要求是否達到，有何問題，是怎么解決的）抄寫自己所選擇的題目。寫出算法設計思路。編寫代碼，調試運行，實現題目要求（提示：考慮到插入和刪除的位置是否超出范圍等可能出現的異常問題）。

四、寫出算法設計、編程和調試運行的體會。數據結構實驗報告抄寫自己所選擇的題目。1、稱正讀和反讀都相同的字符序列為“回文”，例如，abcddcba、qwerewq是回文，ashgash不是回文。試寫一個算法，判斷讀入的一個以“@”為結束符的字符序列是否為回文。2、假設以數組se[m]存放循環隊列的元素，同時設變量rear和front分別作為隊首、隊尾指針，且隊首指針指向隊首節點前一個位置，寫出這樣設計的循環隊列的入隊、出隊的算法。寫出算法設計思路。先分配一個含80個字符的數組用于存放輸入的字符序列，然后以堆棧的方式將字符序列入棧，接著，出棧并與相應的順序數組依次進行比較，直到出現不相等的情況，就輸出“不是回文”，否則在結束比較后輸出“是回文”。先分配一個用來存放輸入的字符串的數組。然后按照用戶的長度要求將字符串讀入，接著，將此讀入的字符串存入循環隊列中，并計算所存循環隊列的長度，再將字符依次輸出到屏幕。實現字符串的入隊，出隊。編寫代碼，調試運行，實現題目要求（提示：考慮到插入和刪除的位置是否超出范圍等可能出現的異常問題）1./*shiy2.1回文*/typedefcharSElemType;#include"c-head.h"#include"hong.h"#include"shunxz.c"#defineCHECK0main(){SqStacks;charch[80],*p,e;/*變量聲明*/intt,i,k=1;if(InitStack(&s))/*初始化棧成功*/{printf("請輸入以“@”結尾的字符序列:");gets(ch);p=ch;}while(*p)if(*p!=64)Push(&s,*p++);else{t=StackLength(s);printf("您一共輸入了%d個字符。\n\n\n",t);p++;}printf("正在比較中：\n");printf("正讀反讀\n");for(i=0;i<t;i++){Pop(&s,&e);printf("%c-><-%c\n",ch[i],e);if(ch[i]!=e){printf("您輸入的字符序列“不是”回文。\n");if(CHECK)printf("no.");k=0;break;}}if(k)printf("您輸入的字符序列“是”回文。\n");if(CHECK){if(k)printf("yes.");}getch();}/*c-head.h(程序名)*/#include<string.h>#include<ctype.h>#include<malloc.h>/*malloc()等*/#include<limits.h>/*INT_MAX等*/#include<stdio.h>/*EOF(=^Z或F6),NULL*/#include<stdlib.h>/*atoi()*/#include<io.h>/*eof()*/#include<math.h>/*floor(),ceil(),abs()*/#include<process.h>/*exit()*/#include<conio.h>/*函數結果狀態代碼*/#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1/*#defineOVERFLOW-2因為在math.h中已定義OVERFLOW的值為3,故去掉此行*/typedefintStatus;/*Status是函數的類型,其值是函數結果狀態代碼，如OK等*/typedefintBoolean;/*Boolean是布爾類型,其值是TRUE或FALSE*//*hong.h棧的順序存儲表示*/#defineSTACK_INIT_SIZE10/*存儲空間初始分配量*/#defineSTACKINCREMENT2/*存儲空間分配增量*/typedefstructSqStack{SElemType*base;/*在棧構造之前和銷毀之后，base的值為NULL*/SElemType*top;/*棧頂指針*/intstacksize;/*當前已分配的存儲空間，以元素為單位*/}SqStack;/*順序棧*//*shunxz.c順序棧（存儲結構由hong.h定義）的基本操作*/StatusInitStack(SqStack*S){/*構造一個空棧S*/(*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW);/*存儲分配失敗*/(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;returnOK;}intStackLength(SqStackS){/*返回S的元素個數，即棧的長度*/returnS.top-S.base;}StatusPush(SqStack*S,SElemTypee){/*插入元素e為新的棧頂元素*/if((*S).top-(*S).base>=(*S).stacksize)/*棧滿，追加存儲空間*/{(*S).base=(SElemType*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW);/*存儲分配失敗*/(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;}*((*S).top)++=e;returnOK;}StatusPop(SqStack*S,SElemType*e){/*若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR*/if((*S).top==(*S).base)returnERROR;*e=*--(*S).top;returnOK;}2./*“shiy2.2.c”循環列表的入隊與出隊*/typedefcharQElemType;#include"c-head.h"#include"xhdl.h"#include"xhdl.c"main(){SqQueueq;intm,se[80],i,*p,t;chare;if(InitQueue(&q))/*初始化隊列成功*/{printf("PleaseinputthelengthoftheSqQueue:");scanf("%d",&m);}printf("Pleaseinputyourchar:");for(i=0;i<=m;i++)scanf("%c",&se[i]);p=se;printf("Yourcharis:");for(i=0;i<=m;i++)printf("%c",p[i]);while(*p)/*入隊*/EnQueue(&q,*p++);t=QueueLength(q);printf("\nThereare%dcharsintheSqQueue:",t-1);while(t)/*出隊*/{DeQueue(&q,&e);t--;printf("%c",e);}getch();}/*"xunhdl.h"文件——循環隊列*/#defineMAXQSIZE100/*最大隊列長度*/typedefstructSqQueue{QElemType*base;/*初始化的動態分配空間*/intfront;/*頭指針*/intrear;/*尾指針*/}SqQueue;/*定義循環隊列*//*"xhdl.c"——循環隊列基本操作*/StatusInitQueue(SqQueue*Q)/*構造一個空隊列Q*/{(*Q).base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!(*Q).base)exit(OVERFLOW);/*儲存分配失敗*/(*Q).front=(*Q).rear=0;returnOK;}intQueueLength(SqQueueQ)/*返回Q的元素個數，即隊列的長度*/{return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;}StatusEnQueue(SqQueue*Q,QElemTypee){/*插入e為Q的新的隊尾元素*/if(((*Q).rear+1)%MAXQSIZE==(*Q).front)returnERROR;/*隊列滿*/(*Q).base[(*Q).rear]=e;(*Q).rear=((*Q).rear+1)%MAXQSIZE;returnOK;}StatusDeQueue(SqQueue*Q,QElemType*e){/*若隊列不空，則刪除Q的隊頭元素，用e返回其值，并返回OK;否則返回ERROR*/if((*Q).front==(*Q).rear)returnERROR;*e=(*Q).base[(*Q).front];(*Q).front=((*Q).front+1)