1、1成績評定表成績評定表學生姓名鐘城班級學號1503060334專 業通信工程課程設計題目集合類的設計與設計評語組長簽字：成績日期 20 年 月 日2課程設計任務書課程設計任務書學 院信息科學與工程學院專 業通信工程學生姓名鐘城班級學號1503060334課程設計題目集合類的設計與實現實踐教學要求與任務實踐教學要求與任務本課程設計主要是集合的交、并和差運算的研究與實現，用有序單鏈表表示集合，實現集合的交、并和差運算。研究表明，采用有序存儲的運算簡單、方便。通過類與對象的設計，編制一個能演示執行集合的并、交和差運算的程序，要求如下：（1）集合的元素限定為小寫字母字符a,z。（2）演示程序以用戶和計

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

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

4、字母字符a.z，集合的大小 n27。集合輸入的形式為一個以“#”為結束標志的字符串，串中字符順序不限，且允許出現重復字符及非法字符，程序應能自動濾去。輸出的運行結果字符串將不含重復字符及非法字符。（2）演示程序以用戶和計算機的對話方式執行，即在計算機終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規定的運算命令；相應的輸入數據（濾去輸入中的非法字符）和運算結果顯示在其后。 (1)（3）程序執行的命令包括： 1).構造集合 1；2).構造集合 2；3).求并集；4).求交集；5).求差集；6).結束。 “構造集合 1”和“構造集合 2”時，需以字符串的形式鍵入集合元素。（4）測試數據 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 算法基本原理 本課題采用數據抽象的程序設計方法，將程序劃分為四個層次結構：元素節點，有序鏈表，有序集和主控模塊，使得設計時思路清晰，實現時調試順利，各模塊具有較好的可重用性，確實得到了一次良好的程序設計訓練。建立集合類，在類

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

7、計面臨的計算問題的關鍵是集合運算。可以定義一個線性表類 Linklist 作為基類，從問題的需要來看，在線性表類應包括對兩單鏈表的操作的成員函數。在集合的求解過程中，在線性表類 Linklist 的成員函數 initLinklist(LinkList Head)中需要初始化類 Linklist 的數據成員，再利用成員函數 LinkList Merge(LinkList Head1,LinkList Head2)，LinkList Insection(LinkList Head1,LinkList Head2)，LinkList Deprive(LinkList Head1,LinkList H

8、ead2)分別求得兩集合的并，交，差運算結果。整個程序中的集合存儲采用的是動態內存分配方式。由 Linklist 類生成一個對象用來存放集合，然后由此對象調用成員函數，對集合進行各種并，交，差運算。并運算，是生成一個新的單鏈表，然后利用尾插法將兩個集合的元素順序插入到新表的表頭之后。若待插字符串為非小寫字母，則跳過不插。交運算，是生成一個新的單鏈表，然后利用尾插法將兩個集合的相同元素順序插入到新表的表頭之后。若待插字符串為非小寫字母，則跳過不插。差運算，是生成一個新的單鏈表，然后利用尾插法將集合一中不同于集合二的元素順序插入到新表的表頭之后。若待插字符串為非小寫字母，則跳過不插。在主函數中對兩

9、集合進行測試，運算完成后，設置一個循環，若輸入 y/Y 則繼續運算，否則結束程序。3.2 類的設計和實現#include using namespace std; typedef struct Node char data; Node *next; 沈陽理工大學課程設計專用紙 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)沈陽理工大學課程設計專用紙 4 flag=FALSE; return flag; temp=temp-next; return

11、flag; /合并兩個集合 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; 沈陽理工大學課程設計專用紙 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; /兩個集合的差集 沈陽理工大學課程設計專用紙 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; /兩個集合交集 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; 沈陽理工大學課程設計專用紙 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; ;在程序的類聲明部分，先由類的成員函數 initLinklist(LinkList Head)生成單鏈表，然后由各成員函數對其進行集合的并，交，差運算。4 基于控制臺的應用程序4.1 主函數設計int main() char cmd; Linklist List; do cout*n;cout*集合運算系統*n; cout*n;cout輸入兩個集合的元素，輸完一個集合的元素,按#結束n; LinkList head1=(Node*)malloc(SIZE); 沈陽理工大學

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

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

20、示。沈陽理工大學課程設計專用紙 10圖 5-1 程序運行結果測試數據二運行結果如圖 5-2 所示。沈陽理工大學課程設計專用紙 11圖 5-2 程序運行結果5 基于 MFC 的應用程序MFC 的圖形界面程序設計可在上述類設計的基礎上進行改造，MFC 的圖形界面程序與 DOS 界面程序的主要不同點是：MFC 圖形界面程序與 DOS 界面程序的輸入輸出方式不同，DOS 界面程序采用字符交互式實現數據輸入輸出，主要通過 cin，cout 等I/O 流實現，而 MFC 的圖形程序界面采用標準 Windows 窗口和控件實現輸入輸出，因此必須在 MFC 類的框架下加入上面所設計的矩陣和方程組類，并通過圖形

21、界面的輸入輸出改造來完成。5.1 圖形界面設計首先在 VC 中建立 MFC AppWizard（exe）工程，名稱為 MFC，并在向導的 Step1中選擇 Dialog based，即建立基于對話框的應用程序，如下圖 6-1 所示。沈陽理工大學課程設計專用紙 12圖 6-1 建立 MFC AppWizard（exe）工程圖 6-2 建立基于對話框的應用程序將對話框資源中的默認對話框利用工具箱改造成如下界面，如圖 6-3 所示。沈陽理工大學課程設計專用紙 13 圖 6-3 集合運算程序界面設計圖 6-3 所示的界面中包含了 3 個 Static Text 控件，4 個 Button 控件，和 1

22、 個 Edit Box 控件，控件的基本信息列表如下表 1 所示。表 1 控件基本信息控件類別控件 ID控件 Caption說明輸入操作記錄Static TextIDC_STATIC功能IDC_BUTTON_Def確定IDC_BUTTON_Jiao交集IDC_BUTTON_Bing并集BottonIDC_BUTTON_Cha差集Edit BoxIDC_EDIT_A00 IDC_EDIT_A100集合的元素沈陽理工大學課程設計專用紙 145.2 程序代碼設計為了能夠將對話框界面上的控件能夠與代碼聯系起來，需要為 1 個 Edit Box 控件建立 Member Variables，按 Ctrl+

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

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