數(shù)據(jù)結(jié)構(gòu)實驗報告：循環(huán)隊列的應(yīng)用及串的匹配操作

1、.-工業(yè)學院計算機工程系?數(shù)據(jù)結(jié)構(gòu)?實驗報告實驗名稱實驗三、循環(huán)隊列的應(yīng)用與串的匹配操作實驗時間學生班級學號指導教師批閱教師成績實驗目的：1掌握循環(huán)隊列和串的基本原理 2掌握循環(huán)隊列和串的存儲結(jié)構(gòu) 3掌握循環(huán)隊列的入隊、出隊、判斷隊空的實現(xiàn)方法和串的匹配方法 4掌握循環(huán)隊列和串的基本應(yīng)用和實現(xiàn)方法實驗設(shè)備與要求：PC機一臺，安裝有Windows操作系統(tǒng)以及VC6.0及以上版本1熟悉C+語言編程 2熟練使用C+語言實現(xiàn)循環(huán)隊列的入隊、出隊、判斷?？盏炔僮?，串的匹配操作 3熟練使用循環(huán)隊列的入隊、出隊算法，串的BF算法。實驗容：1、舞伴配對問題：假設(shè)在周末舞會上，男士們和女士們進入舞廳時，各自排成

2、一隊。跳舞開始時，依次從男隊和女隊的隊頭上各出一人配成舞伴。假設(shè)兩隊初始人數(shù)不相同，那么較長的那一隊中未配對者，等待下一輪舞曲?，F(xiàn)要求寫一算法模擬上述舞伴配對問題。 2、用BF算法實現(xiàn)串S=abbacdbaafcefg,T=cdbaaf的匹配操作。實驗步驟及實驗結(jié)果記錄：算法分析： 1、舞伴配對問題：假設(shè)在周末舞會上，男士們和女士們進入舞廳時，各自排成一隊。跳舞開始時，依次從男隊和女隊的隊頭上各出一人配成舞伴。假設(shè)兩隊初始人數(shù)不相同，那么較長的那一隊中未配對者，等待下一輪舞曲?，F(xiàn)要求寫一算法模擬上述舞伴配對問題。 2、用BF算法實現(xiàn)串S=abbacdbaafcefg,T=cdbaaf的匹配操作

3、。問題分析：先入隊的男士或女士亦先出隊配成舞伴。因此該問題具體有典型的先進先出特性，可用隊列作為算法的數(shù)據(jù)結(jié)構(gòu)。在算法中，假設(shè)男士和女士的記錄存放在一個數(shù)組中作為輸入，然后依次掃描該數(shù)組的各元素，并根據(jù)性別來決定是進入男隊還是女隊。當這兩個隊列構(gòu)造完成之后，依次將兩隊當前的隊頭元素出隊來配成舞伴，直至某隊列變空為止。此時，假設(shè)某隊仍有等待配對者，算法輸出此隊列中等待者的人數(shù)及排在隊頭的等待者的名字，他或她將是下一輪舞曲開始時第一個可獲得舞伴的人。偽代碼：輸入兩個隊列兩個隊列進行入隊操作判斷隊列長度兩個隊列進行匹配出隊操作短隊列出對完成，長隊列等待下一隊列的到來設(shè)Man對為ABCDEFGH，設(shè)W

4、oman隊為IJKLMN。當Man隊列和Woman隊列都入隊完成之后，開始配對：IJKLMN此時Man隊列就還有兩個人沒有舞伴，等待下一輪Woman的隊列參照教材所列BF算法實現(xiàn)，串S和T的匹配操作。1、在串S和串T中設(shè)比較的起始下標i和j；2、循環(huán)直到S中所剩字符個數(shù)小于T的長度或T的所有字符均比較完 2.1 如果Si=Tj，繼續(xù)比較S和T的下一個字符；否那么將i和j回溯，準備下一趟比較；3、如果T中所有字符均比較完，那么匹配成功，返回匹配的起始比較下標； 否那么，匹配失敗，返回0； 4、S=abbacdbaafcefg,T=cdbaaf程序代碼1、舞伴配對問題：頭文件：LinkQueue.

5、h#pragmaoncetemplate structNodeDataType data;Node * next;templateclassLinkQueuepublic:LinkQueue();LinkQueue();void EnQueue(DataType x);DataType DeQueue();DataType GetQueue();int getArrayLen(DataType Array);int Empty();private:Node * front, *rear;源文件：LinkQueue.cpp#includeLinkQueue.htemplateLinkQueue:

6、LinkQueue()Node *s = NULL;s = newNode;s-next = NULL;front = rear = s;templateLinkQueue:LinkQueue()Node *p = NULL;while (front != NULL)p = front-next;delete front;front = p;templatevoidLinkQueue:EnQueue(DataTypex)Node*s = NULL;s = newNode;s-data = x;s-next = NULL;rear-next = s;rear = s;templateDataTy

7、peLinkQueue:DeQueue()Node *p = NULL;int x;if (rear = front) throw下溢;p = front-next;x = p-data;front-next = p-next;if (p-next = NULL)rear = front;delete p;return x;templateDataTypeLinkQueue:GetQueue()if (front != rear)return front-next-data;elsereturnfalse;templateintLinkQueue:Empty()if (front = rear

8、)return 1;elsereturn 0;template /獲取數(shù)組長度intLinkQueue:getArrayLen(DataTypearray)return (sizeof(array) / sizeof(array0)-1);源文件：LinkQueue_main.cpp#include#includeLinkQueue.cppusingnamespace std;/334a6c1d5e27c49d 543b75adbb34afc0int main() LinkQueue Q1;LinkQueue Q2;char Man100;char Woman100;int length1,

9、length2;cout Man;cout Woman;cout endl;length1 = strlen(Man); /獲取Man數(shù)組的長度length2 = strlen(Woman); /獲取Woman數(shù)組的長度cout 男士人數(shù): length1 女士人數(shù):length2 endl;cout endl;for (int i = 0; i length1; i+) /對Man數(shù)組進行入隊操作Q1.EnQueue(Mani);for (int i = 0; i length2; i+) /對Woman進行入隊操作Q2.EnQueue(Womani);if (length1 = lengt

10、h2) /當男士人數(shù)小于女士人數(shù)時，先開始男士的配對，剩余女士進行下一組配對cout 配對開始！男士在前 endl;cout 女士 男士 endl;for (int i = 0; i length1; i+)cout Q1.GetQueue() - Q2.GetQueue() endl;Q1.DeQueue();Q2.DeQueue();if (length1 != length2)cout 還有以下幾位女士等待下一組： endl;for (int i = length1; i length2; i+)cout Q2.GetQueue() ;Q2.DeQueue();cout endl;els

11、eif (length2 = length1) /當女士人數(shù)小于男士人數(shù)時，先開始女士的配對，剩余男士進行下一組配對cout 配對開始！女士在前 endl;cout 女士 男士 endl;for (int i = 0; i length2; i+)cout Q2.GetQueue() - Q1.GetQueue() endl;Q1.DeQueue();Q2.DeQueue();if (length1 != length2)cout 還有以下幾位男士等待下一組： endl;for (int i = length2; i length1; i+)cout Q1.GetQueue() ;Q1.DeQ

12、ueue();cout endl;return 0;程序代碼2、BF算法：#includeusingnamespace std;int main()char S = abbacdbaafcefg;char T = cdbaaf;cout 串S: Sendl;cout 串T: Tendl;cout 開始匹配！ endl;int i = 0, j = 0;while (Si != 0) & (Tj != 0)if (Si = Tj)i+;j+;elsei = i - j + 1;j = 0;if (Tj = 0)cout 匹配成功! endl;cout T開始匹配S位置： i - j + 1 endl;elsecout 匹配失??！ endl;