數(shù)據(jù)實(shí)驗(yàn)報(bào)告書_回文測(cè)試

1、.數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告書實(shí)驗(yàn)內(nèi)容：棧和隊(duì)列的基本操作及其應(yīng)用計(jì)算機(jī)學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)計(jì)科：*前言計(jì)算機(jī)編程中加工處理的對(duì)象是數(shù)據(jù)，而數(shù)據(jù)具有一定的組織結(jié)構(gòu)，所以學(xué)習(xí)計(jì)算機(jī)編程僅僅了解計(jì)算機(jī)語(yǔ)言是不夠的，還必須掌握數(shù)據(jù)的組織、存儲(chǔ)和運(yùn)算的一般方法，這便是數(shù)據(jù)結(jié)構(gòu)課程中所研究的內(nèi)容，也是我們編寫計(jì)算機(jī)程序的重要基礎(chǔ)，由于它對(duì)計(jì)算機(jī)學(xué)科起到承前啟后的作用，因此本課程被列為計(jì)算機(jī)等相關(guān)專業(yè)最重要的專業(yè)基礎(chǔ)課；同時(shí)數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)教學(xué)的一門核心課程。計(jì)算機(jī)各領(lǐng)域都要用到各種數(shù)據(jù)結(jié)構(gòu)，而且要從事計(jì)算機(jī)科學(xué)與技術(shù)工作，尤其是計(jì)算機(jī)領(lǐng)域的軟件開發(fā)工作，必須具備較強(qiáng)的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容豐富、學(xué)習(xí)

2、量大，實(shí)踐性強(qiáng)；隱含在各部分內(nèi)容中的方法和技術(shù)多；算法設(shè)計(jì)具有動(dòng)態(tài)性和抽象性等特點(diǎn)，看懂聽明白與掌握會(huì)應(yīng)用之間有相當(dāng)大的一段距離。所以學(xué)生必須多實(shí)踐才能進(jìn)一步加深對(duì)課程的理解，理解和掌握算法設(shè)計(jì)所需的方法和技術(shù)，為整個(gè)專業(yè)學(xué)習(xí)打下良好的基礎(chǔ)。棧和隊(duì)列的基本操作及其應(yīng)用回文判斷一、實(shí)驗(yàn)?zāi)康?、掌握棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，以便在實(shí)際中靈活應(yīng)用。2、掌握棧和隊(duì)列的特點(diǎn)，即后進(jìn)先出和先進(jìn)先出的原則。3、掌握棧和隊(duì)列的基本運(yùn)算，如：入棧與出棧，入隊(duì)與出隊(duì)等運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。 問題描述對(duì)于一個(gè)從鍵盤輸入的字符串，判斷其是否為回文?；匚募凑葱蛳嗤?。如“abba”是回文

3、，而“abab”不是回文?；疽螅?）數(shù)據(jù)從鍵盤讀入；（2）輸出要判斷的字符串；（3）利用棧的基本操作對(duì)給定的字符串判斷其是否是回文，若是則輸出“Yes”，否則輸出“No”。測(cè)試數(shù)據(jù)由學(xué)生任意指定。算法設(shè)計(jì)：首先，先建立兩個(gè)空棧。分別命名為S、L?，F(xiàn)將輸入的字符串，儲(chǔ)存于S棧中。然后，編寫代碼。使得S棧中的字符依出棧，并保存于L棧中。這樣可以使得S棧與L棧中的字符完全相同，但順序顛倒。然后依次比較L棧與S棧中的字符是否相同。如果相同，則說(shuō)明，所輸入的字符。顛倒順序后與原字符依然相同。所以可判斷為回文。否則，就不是回文。在本代碼中，棧的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)了三個(gè)指針。base指向棧底，top指向棧頂，

4、sel也指向棧頂。sel的作用是用于將棧S中的元素，依次傳給棧L。從而避免了，在傳元素的過程中，棧S的top指針回到base指針上。導(dǎo)致棧S變?yōu)榭諚?。最后說(shuō)明一下。字符串的輸入是一“#”字符為結(jié)束標(biāo)志的。但這個(gè)符號(hào)本身不算字符串的一部分。建立堆棧的數(shù)據(jù)結(jié)構(gòu):typedef struct Stick ele *base; ele *top; ele *sel; int stacksize;Sqstack;當(dāng)然此處定義：typedef char ele;初始化所有可能用到的數(shù)據(jù)：#define NULL 0 #define SIZE 100#define OVER 100堆棧的建立算法：int I

5、nit(Sqstack &S) S.base=(ele *)malloc(SIZE * sizeof(ele); if(!S.base) exit(0); S.top=S.base; S.sel=S.base; S.stacksize=SIZE; return 1;堆棧的建立好以后就可以想法向里面輸入字符，并定義以下算法實(shí)現(xiàn)向堆棧里面輸入字符：int push(Sqstack &S,ele e) if (S.top-S.base=S.stacksize) S.base=(ele *)realloc(S.base,(S.stacksize+OVER)*sizeof(ele); if(!S.bas

6、e) exit(0); S.top=S.base+S.stacksize; S.stacksize=S.stacksize+OVER; *S.top+=e; S.sel=S.top; return 1;此程序是為實(shí)現(xiàn)回文的判斷定義以下實(shí)現(xiàn)函數(shù)comp(Sqstack &S,Sqstack &L):int comp(Sqstack &S,Sqstack &L) /對(duì)兩個(gè)堆棧中的字符串進(jìn)行比較并判斷是否為回文 int n=1; if (L.top-L.base=L.stacksize) L.base=(ele *)realloc(L.base,(L.stacksize+OVER)*sizeof(e

7、le); if(!L.base) exit(0); L.top=L.base+S.stacksize; L.stacksize=L.stacksize+OVER; S.sel=S.sel-1; while(S.sel=S.base) *L.top=*S.sel; S.sel=S.sel-1; L.top =L.top+1; S.top=S.top-2; L.top=L.top-1; while(S.top=S.base)&(L.top=L.base-1) if(*S.top!=*L.top) n=0; S.top-; L.top-; if(n=1) coutYESn; else coutNOn

8、; return OK;此函數(shù)是本程序的核心所以，主要進(jìn)行的操作就是本函數(shù)。主函數(shù)：void main() char j; Sqstack S,L; Init(S); Init(L); coutj; push(S,j); while(j!=#) cinj; push(S,j); coutn; comp(S,L); coutn; system(pause);測(cè)試調(diào)試：本程序開始運(yùn)行后出現(xiàn)以下界面：根據(jù)具體所析：采用以下測(cè)試數(shù)據(jù)，以字母回文、字母非回文、數(shù)字回文、數(shù)字非回文、字母加數(shù)字回文、字母加數(shù)字非回文，進(jìn)行測(cè)試：asdfnmmnfdsa、imksginlkjii、25468986452、23

9、556964、aki56265ika、sdfs5548。所有測(cè)試數(shù)據(jù)以“#”結(jié)尾。測(cè)試一：成功。測(cè)試二：成功。測(cè)試三：成功。測(cè)試四：成功。測(cè)試五：成功。測(cè)試六：成功?？偨Y(jié)：經(jīng)過以上的編碼測(cè)試，可以得出，本實(shí)驗(yàn)程序能對(duì)字符進(jìn)行是否為回文的判斷。并最終以YESor No 的形式把結(jié)果給輸入。能過本次實(shí)驗(yàn)，我算是深入的了解了堆棧的操作及應(yīng)用，雖然此程序很小，但已足以氫棧的思想給表現(xiàn)，并通過本次實(shí)驗(yàn)，熟悉了棧的知識(shí)，并在以后的學(xué)習(xí)當(dāng)中并加以應(yīng)用。最后感謝指導(dǎo)老師：高老師附錄：源代碼：#include#includeusing namespace std;#define NULL 0 /初始化所有可能用

10、到的參數(shù)#define SIZE 100#define OVER 100#define OK 1typedef char ele;typedef struct Stick /建立堆棧的數(shù)據(jù)結(jié)構(gòu) ele *base; ele *top; ele *sel; int stacksize;Sqstack; int Init(Sqstack &S) /建立一個(gè)堆棧 S.base=(ele *)malloc(SIZE * sizeof(ele); if(!S.base) exit(0); S.top=S.base; S.sel=S.base; S.stacksize=SIZE; return OK; i

11、nt push(Sqstack &S,ele e) /向堆棧里輸入字符 if (S.top-S.base=S.stacksize) S.base=(ele *)realloc(S.base,(S.stacksize+OVER)*sizeof(ele); if(!S.base) exit(0); S.top=S.base+S.stacksize; S.stacksize=S.stacksize+OVER; *S.top+=e; S.sel=S.top; return OK; int comp(Sqstack &S,Sqstack &L) /對(duì)兩個(gè)堆棧中的字符串進(jìn)行比較并判斷是否為回文 int n

12、=1; if (L.top-L.base=L.stacksize) L.base=(ele *)realloc(L.base,(L.stacksize+OVER)*sizeof(ele); if(!L.base) exit(0); L.top=L.base+S.stacksize; L.stacksize=L.stacksize+OVER; S.sel=S.sel-1; while(S.sel=S.base) *L.top=*S.sel; S.sel=S.sel-1; L.top =L.top+1; S.top=S.top-2; L.top=L.top-1; while(S.top=S.base)&(L.top=L.base-1) if(*S.top!=*L.top) n=0; S.top