回文串實(shí)驗(yàn)報(bào)告

1、回文串實(shí)驗(yàn)報(bào)告課程名稱： 數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)名稱： 單鏈表 學(xué)生姓名： 杜克強(qiáng) 學(xué)生學(xué)號(hào)： 201207092427 11實(shí)驗(yàn)一 回文串的基本操作及其應(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)。二、實(shí)驗(yàn)內(nèi)容和要求問(wèn)題描述對(duì)于一個(gè)從鍵盤(pán)輸入的字符串，判斷其是否為回文?；匚募凑葱蛳嗤Ｈ纭癮bba”是回文，而“abab”不是回文?；疽螅?）數(shù)據(jù)從鍵盤(pán)讀入；（2）輸出要判斷的字符串； （3）利用棧的基本操作對(duì)

2、給定的字符串判斷其是否是回文，若是則輸出“Yes”，否則輸出“No”。 測(cè)試數(shù)據(jù)由學(xué)生任意指定。三、實(shí)驗(yàn)步驟1需求分析本演示程序用C語(yǔ)言編寫(xiě)，完成對(duì)一個(gè)字符串是否是回文字符串的判斷 輸入一個(gè)任意的字符串； 對(duì)輸入的字符串進(jìn)行判斷是否為回文串； 輸出判斷結(jié)果； 測(cè)試數(shù)據(jù)： A 依次輸入“abccba”，“asddas”等數(shù)據(jù)；B 輸出判斷結(jié)果“Yes”，“No”等4、 算法設(shè)計(jì)1、 算法思想：把字符串中的字符逐個(gè)分別存儲(chǔ)到隊(duì)列和堆棧中，然后逐個(gè)出隊(duì)和出棧并比較出隊(duì)列的數(shù)據(jù)元素和退棧的數(shù)據(jù)元素是否相等，若相等則是會(huì)文，否則不是。2、 模塊設(shè)計(jì)（1） int Palindrome_Test()判斷字

3、符序列是否為回文串；（2） Status main()主函數(shù)；（3） Status CreatStack(SqStack &S)創(chuàng)建一個(gè)棧；（4） Status Push(SqStack &S,SElemType e)入棧；（5） Status Pop(SqStack &S ,SElemType &e)出棧；（6） Status CreatQueue(LinkQueue &Q)創(chuàng)建一個(gè)隊(duì)列；（7） Status EnQueue(LinkQueue &Q,QElemType e)入隊(duì)；（8） Status DeQueue(LinkQueue &am

4、p;Q,QElemType &e)出隊(duì)；3、 模塊之間關(guān)系及其相互調(diào)用的圖示 4、數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)圖五、調(diào)試分析一、實(shí)驗(yàn)結(jié)果圖2 實(shí)驗(yàn)結(jié)果2、 總結(jié)通過(guò)做回文串實(shí)驗(yàn)讓我同時(shí)用到了棧和隊(duì)列兩種結(jié)構(gòu)，讓我對(duì)這兩種結(jié)構(gòu)有了一個(gè)比較深入的了解和應(yīng)用，對(duì)我以后的編程產(chǎn)生了比較深遠(yuǎn)的影響。源程序（帶注釋）/創(chuàng)建棧Status CreatStack(SqStack &S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksiz

5、e=STACK_INIT_SIZE;return OK;/創(chuàng)建隊(duì)列tatus CreatQueue(LinkQueue &Q)/建立一個(gè)空的鏈?zhǔn)綏.front=Q.rear=(QNodePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);Q.front->next=NULL;return OK;/入棧Status Push(SqStack &S,SElemType e)if(S.top-S.base>=S.stacksize)/棧滿，追加存儲(chǔ)空間S.base=(SElemType*)realloc(S.base,

6、(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base)exit (OVERFLOW);/存儲(chǔ)空間分配失敗S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;/入隊(duì)Status EnQueue(LinkQueue &Q,QElemType e) QNodePtr p;p=(QNodePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);p->data=e;p->next=NULL;Q.

7、rear->next=p;Q.rear=p;return OK;/出棧Status Pop(SqStack &S ,SElemType &e)if(S.top=S.base) return ERROR;e=*-S.top;return OK;/出隊(duì)Status DeQueue(LinkQueue &Q,QElemType &e)QNodePtr p;if(Q.front=Q.rear) return ERROR;p=Q.front->next; e=p->data;Q.front->next=p->next;if(Q.rear=p) Q.rear=Q.front;free(p);return OK;/判斷是否為回文串int Palindrome_Test()/判別輸入的字符串是否回文序列,是則返回1,否則返回0SqStack S;LinkQueue Q;CreatStack(S);CreatQueue(Q); char c; SElemType a,b;while(c=getchar()!=