集合類的設(shè)計(jì)與實(shí)現(xiàn)

1、1成績(jī)?cè)u(píng)定表成績(jī)?cè)u(píng)定表學(xué)生姓名鐘城班級(jí)學(xué)號(hào)1503060334專 業(yè)通信工程課程設(shè)計(jì)題目集合類的設(shè)計(jì)與設(shè)計(jì)評(píng)語(yǔ)組長(zhǎng)簽字：成績(jī)?nèi)掌?20 年 月 日2課程設(shè)計(jì)任務(wù)書(shū)課程設(shè)計(jì)任務(wù)書(shū)學(xué) 院信息科學(xué)與工程學(xué)院專 業(yè)通信工程學(xué)生姓名鐘城班級(jí)學(xué)號(hào)1503060334課程設(shè)計(jì)題目集合類的設(shè)計(jì)與實(shí)現(xiàn)實(shí)踐教學(xué)要求與任務(wù)實(shí)踐教學(xué)要求與任務(wù)本課程設(shè)計(jì)主要是集合的交、并和差運(yùn)算的研究與實(shí)現(xiàn)，用有序單鏈表表示集合，實(shí)現(xiàn)集合的交、并和差運(yùn)算。研究表明，采用有序存儲(chǔ)的運(yùn)算簡(jiǎn)單、方便。通過(guò)類與對(duì)象的設(shè)計(jì)，編制一個(gè)能演示執(zhí)行集合的并、交和差運(yùn)算的程序，要求如下：（1）集合的元素限定為小寫字母字符a,z。（2）演示程序以用戶和計(jì)

2、算機(jī)的對(duì)話方式執(zhí)行。（3）以有序鏈表表示集合。(4）可進(jìn)一步實(shí)現(xiàn)集合的元素判定和子集判定運(yùn)算。工作計(jì)劃與進(jìn)度安排工作計(jì)劃與進(jìn)度安排第 2 周：分析題目，查閱課題相關(guān)資料，進(jìn)行類設(shè)計(jì)、算法設(shè)計(jì)；第 3 周：程序的設(shè)計(jì)、調(diào)試與實(shí)現(xiàn)；第 4 周：程序測(cè)試與分析，撰寫課程設(shè)計(jì)報(bào)告，進(jìn)行答辯驗(yàn)收。指導(dǎo)教師： 201 年 月 日專業(yè)負(fù)責(zé)人：201 年 月 日學(xué)院教學(xué)副院長(zhǎng)：201 年 月 日沈陽(yáng)理工大學(xué)課程設(shè)計(jì)專用紙 3摘 要現(xiàn)實(shí)生活中許多數(shù)據(jù)的處理依賴于哈希表的應(yīng)用，通過(guò)應(yīng)用哈希表使復(fù)雜問(wèn)題更加簡(jiǎn)單化。通過(guò)實(shí)用類模板，使用開(kāi)放地址法和除留余數(shù)法來(lái)實(shí)現(xiàn)對(duì)哈希表的建立、插入、刪除等功能，采用 Visual

3、C+ 6.0 的控制臺(tái)工程和 MFC 工程分別實(shí)現(xiàn)了哈希表的應(yīng)用。關(guān)鍵詞：除留余數(shù)法；哈希表；開(kāi)放地址法；MFC 工程沈陽(yáng)理工大學(xué)課程設(shè)計(jì)專用紙 4目 錄1需求分析.-1-2算法基本原理.-1-3類設(shè)計(jì).-3-3.1 類的概述.-3-3.2 類的設(shè)計(jì)和實(shí)現(xiàn).-3-4基于控制臺(tái)的應(yīng)用程序.-9-4.1 主函數(shù)設(shè)計(jì).-9-4.2 運(yùn)行結(jié)果及分析.-10-5基于 MFC 的應(yīng)用程序 .-12-5.1 圖形界面設(shè)計(jì).-12-5.2 程序代碼設(shè)計(jì).-15-5.3 運(yùn)行結(jié)果及分析.-16-結(jié) 論.-20-參考文獻(xiàn).-21-沈陽(yáng)理工大學(xué)課程設(shè)計(jì)專用紙 01 需求分析 （1）本演示程序中，集合的元素限定為小寫

4、字母字符a.z，集合的大小 n27。集合輸入的形式為一個(gè)以“#”為結(jié)束標(biāo)志的字符串，串中字符順序不限，且允許出現(xiàn)重復(fù)字符及非法字符，程序應(yīng)能自動(dòng)濾去。輸出的運(yùn)行結(jié)果字符串將不含重復(fù)字符及非法字符。（2）演示程序以用戶和計(jì)算機(jī)的對(duì)話方式執(zhí)行，即在計(jì)算機(jī)終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運(yùn)算命令；相應(yīng)的輸入數(shù)據(jù)（濾去輸入中的非法字符）和運(yùn)算結(jié)果顯示在其后。 (1)（3）程序執(zhí)行的命令包括： 1).構(gòu)造集合 1；2).構(gòu)造集合 2；3).求并集；4).求交集；5).求差集；6).結(jié)束。 “構(gòu)造集合 1”和“構(gòu)造集合 2”時(shí)，需以字符串的形式鍵入集合元素。（4）測(cè)試數(shù)據(jù) 1

5、).head1=”merry”,head2=”Christmas”,head1head2=”acehimrsty”,head1head2=”mr”,head1-head2=”ey” ； 2).head1=”012abcde”,head2=”123cdefg”,head1head2=”abcdefg”,head1head2=”cde”,head1-head2=”ab” 。2 算法基本原理 本課題采用數(shù)據(jù)抽象的程序設(shè)計(jì)方法，將程序劃分為四個(gè)層次結(jié)構(gòu)：元素節(jié)點(diǎn)，有序鏈表，有序集和主控模塊，使得設(shè)計(jì)時(shí)思路清晰，實(shí)現(xiàn)時(shí)調(diào)試順利，各模塊具有較好的可重用性，確實(shí)得到了一次良好的程序設(shè)計(jì)訓(xùn)練。建立集合類，在類

6、的成員函數(shù)中，通過(guò)尾插法生成一個(gè)有 N 個(gè)結(jié)點(diǎn)的單鏈表。單鏈表是集合存儲(chǔ)的基礎(chǔ)，單鏈表建立算法需要一個(gè)計(jì)數(shù)循環(huán)語(yǔ)句，為每個(gè)元素建立一個(gè)結(jié)點(diǎn)，插入頭結(jié)點(diǎn)之后。算法流程圖如下 2-1 所示。沈陽(yáng)理工大學(xué)課程設(shè)計(jì)專用紙 1 否是圖 2-1 單鏈表流程圖集合運(yùn)算系統(tǒng)，是將兩單鏈表進(jìn)行交、并和差的集合運(yùn)算，其流程圖如圖 2-2 所示。開(kāi)始初始化一個(gè)單鏈表輸入字符為#建立一個(gè)插入頭結(jié)點(diǎn)后的結(jié)點(diǎn)結(jié)束開(kāi)始輸入提示任意輸入兩組字符串并集運(yùn)算交集運(yùn)算差集運(yùn)算y/Y 繼續(xù)其他 退出輸出運(yùn)行結(jié)果結(jié)束沈陽(yáng)理工大學(xué)課程設(shè)計(jì)專用紙 2圖 2-2 集合運(yùn)算系統(tǒng)流程圖 3 類設(shè)計(jì)3.1 類的概述 從上面的算法分析可以看到，本設(shè)

7、計(jì)面臨的計(jì)算問(wèn)題的關(guān)鍵是集合運(yùn)算?？梢远x一個(gè)線性表類 Linklist 作為基類，從問(wèn)題的需要來(lái)看，在線性表類應(yīng)包括對(duì)兩單鏈表的操作的成員函數(shù)。在集合的求解過(guò)程中，在線性表類 Linklist 的成員函數(shù) initLinklist(LinkList Head)中需要初始化類 Linklist 的數(shù)據(jù)成員，再利用成員函數(shù) LinkList Merge(LinkList Head1,LinkList Head2)，LinkList Insection(LinkList Head1,LinkList Head2)，LinkList Deprive(LinkList Head1,LinkList H

8、ead2)分別求得兩集合的并，交，差運(yùn)算結(jié)果。整個(gè)程序中的集合存儲(chǔ)采用的是動(dòng)態(tài)內(nèi)存分配方式。由 Linklist 類生成一個(gè)對(duì)象用來(lái)存放集合，然后由此對(duì)象調(diào)用成員函數(shù)，對(duì)集合進(jìn)行各種并，交，差運(yùn)算。并運(yùn)算，是生成一個(gè)新的單鏈表，然后利用尾插法將兩個(gè)集合的元素順序插入到新表的表頭之后。若待插字符串為非小寫字母，則跳過(guò)不插。交運(yùn)算，是生成一個(gè)新的單鏈表，然后利用尾插法將兩個(gè)集合的相同元素順序插入到新表的表頭之后。若待插字符串為非小寫字母，則跳過(guò)不插。差運(yùn)算，是生成一個(gè)新的單鏈表，然后利用尾插法將集合一中不同于集合二的元素順序插入到新表的表頭之后。若待插字符串為非小寫字母，則跳過(guò)不插。在主函數(shù)中對(duì)兩

9、集合進(jìn)行測(cè)試，運(yùn)算完成后，設(shè)置一個(gè)循環(huán)，若輸入 y/Y 則繼續(xù)運(yùn)算，否則結(jié)束程序。3.2 類的設(shè)計(jì)和實(shí)現(xiàn)#include using namespace std; typedef struct Node char data; Node *next; 沈陽(yáng)理工大學(xué)課程設(shè)計(jì)專用紙 3Node,*LinkList; #define SIZE sizeof(Node) #define FALSE 0 #define TRUE 1 class Linklistpublic:initLinklist(LinkList Head) char ch; Node *p=Head; Head-next=NULL;

10、 Head-data=0; cinch; while(ch!=#) Node *newNode=(Node*)malloc(SIZE); newNode-data=ch; p-next=newNode; p=p-next; cinch; p-next=NULL; int Check(char ch,LinkList Head) Node *temp=Head-next; int flag=TRUE; while(temp!=NULL) if(temp-data=ch)沈陽(yáng)理工大學(xué)課程設(shè)計(jì)專用紙 4 flag=FALSE; return flag; temp=temp-next; return

11、flag; /合并兩個(gè)集合 LinkList Merge(LinkList Head1,LinkList Head2) LinkList Head=(Node*)malloc(SIZE); Head-data=0;Head-next=NULL; Node *p1=Head1-next; Node *p2=Head2-next; Node *p=Head; while(p1!=NULL&p2!=NULL) if(p1-data=p2-data) if(Check(p1-data,Head)=TRUE)&(p1-data=97&p1-datadata=p1-data; p-next=newNode

12、; p=newNode; p-next=NULL; else if(Check(p1-data,Head)=TRUE)&(p1-data=97&p1-datadata=p1-data; 沈陽(yáng)理工大學(xué)課程設(shè)計(jì)專用紙 5 p-next=newNode; p=newNode; p-next=NULL; if(Check(p2-data,Head)=TRUE)&(p2-data=97&p2-datadata=p2-data; p-next=newNode; p=newNode; p-next=NULL; p1=p1-next; p2=p2-next; while(p1!=NULL) if(Check(

13、p1-data,Head)=TRUE)&(p1-data=97&p1-datadata=p1-data; p-next=newNode; p=newNode; p-next=NULL; p1=p1-next; while(p2!=NULL) if(Check(p2-data,Head)=TRUE)&(p2-data=97&p2-datadata=p2-data; p-next=newNode; p=newNode; p-next=NULL; p2=p2-next; return Head; /集合 A 中的元素，B 中是否存在 int IsExist(char data,LinkList He

14、ad) Node *p=Head-next; int flag=FALSE; while(p!=NULL) if(p-data=data) return flag=TRUE; p=p-next; return flag; int IsExist2(char data,LinkList Head) Node *p=Head-next; int flag=FALSE; while(p!=NULL) if(p-data=data) return flag; p=p-next; return flag=TRUE; /兩個(gè)集合的差集 沈陽(yáng)理工大學(xué)課程設(shè)計(jì)專用紙 7 LinkList Deprive(Li

15、nkList Head1,LinkList Head2) LinkList Head=(Node*)malloc(SIZE); Node *p=Head; Node *p1=Head1-next; while(p1!=NULL) if(IsExist2(p1-data,Head2)=1)&(p1-data=97&p1-datadata=p1-data; p-next=newNode; p=newNode; p-next=NULL; p1=p1-next; return Head; /兩個(gè)集合交集 LinkList Insection(LinkList Head1,LinkList Head2)

16、 Node *p1=Head1-next; LinkList Head=(Node*)malloc(SIZE); Head-data=0; Head-next=NULL; Node *p=Head; while(p1!=NULL) if(IsExist(p1-data,Head2)=1)&(p1-data=97&p1-datadata=p1-data; p-next=newNode; 沈陽(yáng)理工大學(xué)課程設(shè)計(jì)專用紙 8 p=newNode; p-next=NULL; p1=p1-next; return Head; /打印集合元素 void PrintLinkList(LinkList Head)

17、 Node *p=Head-next; while(p!=NULL) coutdata; p=p-next; coutn; ;在程序的類聲明部分，先由類的成員函數(shù) initLinklist(LinkList Head)生成單鏈表，然后由各成員函數(shù)對(duì)其進(jìn)行集合的并，交，差運(yùn)算。4 基于控制臺(tái)的應(yīng)用程序4.1 主函數(shù)設(shè)計(jì)int main() char cmd; Linklist List; do cout*n;cout*集合運(yùn)算系統(tǒng)*n; cout*n;cout輸入兩個(gè)集合的元素，輸完一個(gè)集合的元素,按#結(jié)束n; LinkList head1=(Node*)malloc(SIZE); 沈陽(yáng)理工大學(xué)

18、課程設(shè)計(jì)專用紙 9 LinkList head2=(Node*)malloc(SIZE); List.initLinklist(head1);List.initLinklist(head2); Node *Head1=List.Merge(head1,head2); cout兩個(gè)集合并集為n; List.PrintLinkList(Head1); Node *Head2=List.Insection(head1,head2); cout兩個(gè)集合交集為n; List.PrintLinkList(Head2); Node *Head3=List.Deprive(head1,head2); cout

19、兩個(gè)集合差集為n; List.PrintLinkList(Head3); coutcmd; while(cmd=y|cmd=Y); return 0; 在程序的主函數(shù)部分，先由類生成一個(gè)對(duì)象，再由此對(duì)象調(diào)用類的各成員函數(shù)，求出集合的并，交，差運(yùn)算結(jié)果并輸出。 整個(gè)程序分為兩個(gè)獨(dú)立的文檔，Linklist.cpp 包含了單鏈表的定義和對(duì)兩集合運(yùn)算的成員函數(shù)；main.cpp 文件包括程序的主函數(shù)，主函數(shù)中定義了一個(gè)類 Linklist 的對(duì)象，通過(guò)這個(gè)對(duì)象求解兩集合的交，并，差運(yùn)算結(jié)果。4.2 程序運(yùn)行結(jié)果及分析 通過(guò)下圖可以看出求解兩集合的交，并，差運(yùn)算結(jié)果。測(cè)試數(shù)據(jù)一運(yùn)行結(jié)果如圖 5-1 所

20、示。沈陽(yáng)理工大學(xué)課程設(shè)計(jì)專用紙 10圖 5-1 程序運(yùn)行結(jié)果測(cè)試數(shù)據(jù)二運(yùn)行結(jié)果如圖 5-2 所示。沈陽(yáng)理工大學(xué)課程設(shè)計(jì)專用紙 11圖 5-2 程序運(yùn)行結(jié)果5 基于 MFC 的應(yīng)用程序MFC 的圖形界面程序設(shè)計(jì)可在上述類設(shè)計(jì)的基礎(chǔ)上進(jìn)行改造，MFC 的圖形界面程序與 DOS 界面程序的主要不同點(diǎn)是：MFC 圖形界面程序與 DOS 界面程序的輸入輸出方式不同，DOS 界面程序采用字符交互式實(shí)現(xiàn)數(shù)據(jù)輸入輸出，主要通過(guò) cin，cout 等I/O 流實(shí)現(xiàn)，而 MFC 的圖形程序界面采用標(biāo)準(zhǔn) Windows 窗口和控件實(shí)現(xiàn)輸入輸出，因此必須在 MFC 類的框架下加入上面所設(shè)計(jì)的矩陣和方程組類，并通過(guò)圖形

21、界面的輸入輸出改造來(lái)完成。5.1 圖形界面設(shè)計(jì)首先在 VC 中建立 MFC AppWizard（exe）工程，名稱為 MFC，并在向?qū)У?Step1中選擇 Dialog based，即建立基于對(duì)話框的應(yīng)用程序，如下圖 6-1 所示。沈陽(yáng)理工大學(xué)課程設(shè)計(jì)專用紙 12圖 6-1 建立 MFC AppWizard（exe）工程圖 6-2 建立基于對(duì)話框的應(yīng)用程序?qū)?duì)話框資源中的默認(rèn)對(duì)話框利用工具箱改造成如下界面，如圖 6-3 所示。沈陽(yáng)理工大學(xué)課程設(shè)計(jì)專用紙 13 圖 6-3 集合運(yùn)算程序界面設(shè)計(jì)圖 6-3 所示的界面中包含了 3 個(gè) Static Text 控件，4 個(gè) Button 控件，和 1

22、 個(gè) Edit Box 控件，控件的基本信息列表如下表 1 所示。表 1 控件基本信息控件類別控件 ID控件 Caption說(shuō)明輸入操作記錄Static TextIDC_STATIC功能IDC_BUTTON_Def確定IDC_BUTTON_Jiao交集IDC_BUTTON_Bing并集BottonIDC_BUTTON_Cha差集Edit BoxIDC_EDIT_A00 IDC_EDIT_A100集合的元素沈陽(yáng)理工大學(xué)課程設(shè)計(jì)專用紙 145.2 程序代碼設(shè)計(jì)為了能夠?qū)?duì)話框界面上的控件能夠與代碼聯(lián)系起來(lái)，需要為 1 個(gè) Edit Box 控件建立 Member Variables，按 Ctrl+

23、w 鍵進(jìn)入 MFC ClassWizard 界面，選擇 Member Variables 選項(xiàng)卡，可顯示成員變量設(shè)置界面，如圖 6-4 所示。圖 6-4 成員變量設(shè)置界面通過(guò)該界面設(shè)置與 1 個(gè) Edit Box 控件對(duì)應(yīng)的成員變量，具體如表 2 所示。表 2 控件基本信息控件 ID成員變量類型成員變量名稱IDC_EDIT_A00 IDC_EDIT_A100charm_A00m_A100下面是編寫代碼的重要階段，可以借鑒在設(shè)計(jì)基于 DOS 界面的控制臺(tái)應(yīng)用程序的代碼，并將其作必要的改寫，具體改寫的步驟與內(nèi)容如下。將 Linklist.h 文件和 Linklist.cpp 文件合并成一個(gè)文件，重

24、新命名為 Linklist.h，并將其加入 MFC 工程。修改 Linklist.h 文件。在對(duì)話框類的實(shí)現(xiàn)文件 MFCDlg.cpp 中加入#include ，以實(shí)現(xiàn)在該文件中可使用 Linklist 類。在 MFCDlg.cpp 文件中加入全局變量的定義，以實(shí)現(xiàn) MFCDlg 類和 Linklist 類之間的通信。沈陽(yáng)理工大學(xué)課程設(shè)計(jì)專用紙 15編寫讀入元素按鈕的消息處理函數(shù)，實(shí)現(xiàn)將集合的元素刷新到界面上。編寫集合交，并，差及確定按鈕的消息處理函數(shù)，5.3 運(yùn)行結(jié)果及分析運(yùn)行程序后，首先出現(xiàn)的界面如圖 6-5 所示。圖 6-5 程序初始運(yùn)行界面沈陽(yáng)理工大學(xué)課程設(shè)計(jì)專用紙 16輸入集合一的元素后單擊確定按鈕后，可將集合一的元素在界面上顯示出來(lái)，同理，可現(xiàn)示集合二的元素，如圖 6-6 所示。圖 6-6 輸入集合元素后的界面沈陽(yáng)理工大學(xué)課程設(shè)計(jì)專用