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

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

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

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

4、oman隊(duì)為IJKLMN。當(dāng)Man隊(duì)列和Woman隊(duì)列都入隊(duì)完成之后，開(kāi)始配對(duì)：IJKLMN此時(shí)Man隊(duì)列就還有兩個(gè)人沒(méi)有舞伴，等待下一輪Woman的隊(duì)列參照教材所列BF算法實(shí)現(xiàn)，串S和T的匹配操作。1、在串S和串T中設(shè)比較的起始下標(biāo)i和j；2、循環(huán)直到S中所剩字符個(gè)數(shù)小于T的長(zhǎng)度或T的所有字符均比較完 2.1 如果Si=Tj，繼續(xù)比較S和T的下一個(gè)字符；否那么將i和j回溯，準(zhǔn)備下一趟比較；3、如果T中所有字符均比較完，那么匹配成功，返回匹配的起始比較下標(biāo)； 否那么，匹配失敗，返回0； 4、S=abbacdbaafcefg,T=cdbaaf程序代碼1、舞伴配對(duì)問(wèn)題：頭文件：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ù)組長(zhǎng)度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ù)組的長(zhǎng)度length2 = strlen(Woman); /獲取Woman數(shù)組的長(zhǎng)度cout 男士人數(shù): length1 女士人數(shù):length2 endl;cout endl;for (int i = 0; i length1; i+) /對(duì)Man數(shù)組進(jìn)行入隊(duì)操作Q1.EnQueue(Mani);for (int i = 0; i length2; i+) /對(duì)Woman進(jìn)行入隊(duì)操作Q2.EnQueue(Womani);if (length1 = lengt

10、h2) /當(dāng)男士人數(shù)小于女士人數(shù)時(shí)，先開(kāi)始男士的配對(duì)，剩余女士進(jìn)行下一組配對(duì)cout 配對(duì)開(kāi)始！男士在前 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) /當(dāng)女士人數(shù)小于男士人數(shù)時(shí)，先開(kāi)始女士的配對(duì)，剩余男士進(jìn)行下一組配對(duì)cout 配對(duì)開(kāi)始！女士在前 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 開(kāi)始匹配！ 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開(kāi)始匹配S位置： i - j + 1 endl;elsecout 匹配失??！ endl;