1、湖南科技學院課程設計報告課程名稱：數據結構課程設計課程設計題目：02、回文問題系：專 業：年級、班：姓 名：學 號：指導教師：職 稱：2011年12月目錄1. 問題描述-32. 具體要求-33. 測試數據-34. 算法思想-35. 模塊劃分6. 數 據 結 47. 源 程 78. 測 試 情149. 設 計 總1410. 參 考 文問題描述利用棧跟隊列找出一個TXT文檔中所有的回文單詞并輸出。回文單詞就是單詞中字母從前往后拼與從后往前拼得出的單詞是一樣的，如：AaA、121、1221、d、did 等，從數據結構角度看，棧和隊列是特殊的線性表，其特殊性在于棧和 隊列的基本操作是線性表操作的子集，

2、 它們是操作受限的線性表， 而棧是一種限 定僅在表尾進行插入或刪除的線性表， 棧的修改是按先進后出的順序進行的， 隊 列是一種先進先出的線性表， 它只允許在表的一端進行插入， 而在另一端進行刪 除，因此可利用棧和隊列的這兩個性質對一個單詞是否為回文單詞進行檢測， 如 果是則輸出這個單詞即可。 一句話里可能既包含字母、 數字還可能包含標點符號， 回文單詞的判斷是不包含標點符號的 ，但文件輸入流讀取的時候標點也被一起 讀取進來了，因此要刪除緊跟單詞后中的標點符號，單獨對各個單詞進行判斷。二、具體要求 此課程設計要求編寫程序以實現檢測出文檔中的回文單詞并將其輸出的功 能，首先要將每一個單詞從文檔讀取

3、出來， 其次對每一個單詞進行回文判斷， 主 程序用棧和隊列實現， 以進一步鞏固、 理解和熟練掌握棧和隊列的基本操作； 同 時對文本文件進行讀取數據要利用到文件輸入流的知識。三、測試數據用文本文檔 data.txt, 進行測試，輸出回文數，及個數。文本文檔中除英文字母，數字，常見標點符號外無其他字符，并且編碼采用常見的ANSI編碼。四、算法思路1、初始化棧和隊列，讀入TXT文本文檔，若文檔不能正常讀入，則輸出文 檔讀入錯誤，若正常讀入，文檔非空則將文檔中的單詞逐個讀入到字符串中。2、因為標點符號都是緊跟單詞后的，故對每個字符串首先得判斷最后一個 字符c，若c既不是字母也不是數字，字符串的長度減一

4、，即以標點符號結束的 字符串最后一個字符不壓入棧跟隊列，不參與回文單詞的判斷。3、調用出棧與出隊列函數， 逐個比較出棧與出隊列字符是否一樣， 用 count 記錄棧中出來的與隊列出來的相同字符的個數，若 count=str .length() 則說 明該字符串從棧中出來跟從隊列出來完全一樣， 即字符串完全對稱， 為回文單詞， 輸出，回文單詞加一個，否則什么也不做。4、讀取至文本文檔最后時，程序結束，關閉文本文檔，同時銷毀隊列。5、假設文本文檔中除英文字母，數字，常見標點符號外無其他字符，并且 編碼采用常見的 ANSI 編碼。五、模塊劃分函數功能 :void initStack(SqStack&

5、amp; s);/ 構造一個空棧 svoid clearStack(SqStack& s);/ 清空棧bool isEmpty(SqStack& s);/ 判斷棧是否為空bool isFull(SqStack& s);/ 判斷棧是否滿void push(SqStack& s,const char& e);/插入元素 e 為 s 的新的棧頂元素(進棧)char pop(SqStack& s);/ 若棧不空，則刪除 s 的棧頂元素(出棧)void initQueue(LinkQueue& q);/ 構造一個空隊列 qbool isEmpty(

6、LinkQueue q);/ 判斷隊列是否為空void destroyQueue(LinkQueue& q);/ 銷毀隊列void insertElem(LinkQueue& q,char e);/插入元素 e 為 q 的新的隊尾元素(進隊列)char deleteElem(LinkQueue& q);/ 若隊列不空，則刪除 q 的對頭元素(出隊 列)六、數據結構定義棧：struct SqStack / 定義棧char baseMAXSIZE;int top;定義隊列：struct QNode / 定義隊列結點char data;QNode* next;；Kt runt

7、進棧；struct Lin kQueue/定義隊列QNode* front;QNode* rear;I丨1向丨丨抽象數據類型棧定義如下ADT stack數據對象:D= ai | ai ElenSet, i=1,2, ,n,n 0數據關系:R仁< ai i, ai>| ai 1, ai D,i=2,n；約定 an 端為棧頂， a1 端為棧底基本操作 :InitStack(&s) 操作結果：構造一個空棧clearStack(&s)初始條件：棧 s 存在 操作結果：將棧 s 清空為空棧isEmpty(&s) 初始條件：棧 s 存在 操作結果：判斷棧是否為空，為空返

8、回 true, 否則返回 false;isFull(&s) 初始條件：棧 s 存在 操作結果：判斷棧是否滿，滿返回 true, 否則返回 false;push(&s,e) 初始條件：棧 s 存在 操作結果 : 插入元素 e 作為新的棧頂元素pop (&s,&e) 初始條件：棧 s 存在 操作結果:刪除棧s的棧頂元素，并用e返回其值ADT stack數據對象 :D= ai| ai ElenSet, i=1,2 , ,n,n 0數據關系:R仁< ai i, ai>| ai 1, ai D,i=2,n；約定an端為隊列尾，ai端為隊列頭基本操作 :init

9、Queue(&q) ； 操作結果：構造一個空隊列 qisEmpty(q)初始條件：隊列 q 存在 操作結果：判斷隊列是否為空，為空返回 true, 否則返回 false destroyQueue(&q)初始條件：隊列 q 存在操作結果：銷毀隊列 q insertElem(&q,e)初始條件：隊列 q 存在操作結果：插入元素e為q的新的隊尾元素deleteElem(&q)初始條件：隊列 q 存在操作結果 : 若隊列不空，則刪除 q 的對頭元素 新定義數據類型 :MAXSIZE數據類型int七、源程序Sqstack.h#ifndef SQSTACK_H_INCLUD

10、ED#define SQSTACK_H_INCLUDEDconst int MAXSIZE=150;struct SqStack / 定義棧char baseMAXSIZE;int top;void initStack(SqStack& s);/ 構造一個空棧 svoid clearStack(SqStack& s);/ 清空棧bool isEmpty(SqStack& s);/ 判斷棧是否為空bool isFull(SqStack& s);/ 判斷棧是否滿void push(SqStack& s,const char& e);/插入元素 e 為

11、 s 的新的棧頂元素(進棧)char pop(SqStack& s);/ 若棧不空，則刪除 s 的棧頂元素(出棧)#endif / SQSTACK_H_INCLUDEDSqStack.h#include<iostream>#include<cstring>#include<cstdlib> #include"SqStack.h" using namespace std;void initStack(SqStack& s)/ 構造一個空棧 ss.top=0;void clearStack(SqStack& s)s.t

12、op=0;bool isEmpty(SqStack& s)return(s.top=0);bool isFull(SqStack& s)return(s.top=MAXSIZE);插入元素e為s的新的棧頂元素（進void push(SqStack& s,const char& e)/棧)if (s.top=MAXSIZE) cerr<<"Stack overflow!"<<endl;exit(1);s.bases.top=e;+s.top;char pop(SqStack& s)/ 若棧不空，則刪除 s 的棧頂

13、元素(出棧)if (s.top=0)cerr<<"Stack is empty!"<<endl; exit(1);-s.top;char temp=s.bases.top;return temp;LinkQueue.h#ifndef LINKQUEUE_H_INCLUDED#define LINKQUEUE_H_INCLUDEDstruct QNode / 定義隊列結點char data;QNode* next;struct LinkQueue/ 定義隊列QNode* front;QNode* rear;void initQueue(LinkQueu

14、e& q);/ 構造一個空隊列 qbool isEmpty(LinkQueue q);/ 判斷隊列是否為空void destroyQueue(LinkQueue& q);/ 銷毀隊列void insertElem(LinkQueue& q,char e);/ 插入元素 e 為 q 的新的隊尾元素(進 隊列)char deleteElem(LinkQueue& q); 如隊列不空，則刪除q的對頭元素(出隊列)#endif / LINKQUEUE_H_INCLUDEDLinkQueue.cpp#include<iostream>#include<c

15、string>#include<cstdlib>#include"LinkQueue.h"using namespace std;void initQueue(LinkQueue& q) / 構造一個空隊列 qq.front=q.rear=new QNode;if (!q.front)exit(1);q.front->next=NULL;void destroyQueue(LinkQueue& q) while (q.front)q.rear=q.front->next;delete q.front;q.front=q.rear

16、;void insertElem(LinkQueue& q,char e)/ 插入元素 e 為 q 的新的隊尾元素 (進 隊列)QNode* p=new QNode;p->data=e;p->next=NULL;q.rear->next=p;q.rear=p;char deleteElem(LinkQueue& q)/ 如隊列不空，則刪除 q 的對頭元素(出隊列) if (q.front=q.rear)cerr<<"Queue is empty!"<<endl;exit(1);QNode* p=q.front->

17、;next;char e=p->data;q.front->next=p->next;if (q.rear=p) / 若隊列中只剩一個元素針指向頭結點delete p;return e;bool isEmpty(LinkQueue q)return q.front=q.rear;main.cpp#include<iostream>#include<cstring>#include<fstream>#include<cstdlib>#include"SqStack.h" #include"LinkQu

18、eue.h"using namespace std;int main()string str;int i,sum=0;LinkQueue q;SqStack s;initStack(s);if(isEmpty(s)cout<<" 棧初始化成功initQueue(q);!"<<endl;if(isEmpty(q);cout<<" 隊列初始化成功 !"<<endl; ifstream infile("data.txt");if(!infile)cout<<"讀

19、入文本文件發生錯誤 "<<endl;cout<<"*文本文件中回文單詞如下*"<<endl;while (infile.eof()=0)int count=0;infile>>str;i=str.length();char c=stri-1;if (c>='a'|c<='z'|c>='A'|c<='Z');elsei-;for (int j=0; j<i; j+)push(s,strj);insertElem(q,strj)

20、;for (int k=0; k<i; k+)if (pop(s)=deleteElem(q) count+;if (count=i&&infile.eof()=0)for (int n=0; n<i; n+)cout<<strn;cout«"" sum+;in file.close();cout«e ndl;coutvv"此文本文檔中共有回文單詞："vvsumvv'個"<<e ndl;coutvv" * *<<e ndl;clearStack(s);if(isEmpty(s)cout«"棧銷毀成功!"<<endl;destroyQueue(q);if(isEmpty(q);coutvv"隊列銷毀成功!"<<endl;return 0;八、測試情況JC JtJCKJCJCXJCK萍牛中 回戈"甲| 匸 卜 理 員K H 3* W ML W Jt W X W K W JK JU JK