數(shù)據(jù)結(jié)構(gòu)課程設計--文章編輯集合運算.docx

此文檔收集于網(wǎng)絡，如有侵權(quán)，請聯(lián)系網(wǎng)站刪除學 號 成都理工大學計算機科學與技術(shù)系數(shù)據(jù)結(jié)構(gòu)課程設計設計說明書題目文章編輯 集合運算起止日期： 學生姓名班級成績指導教師(簽字) 計算機科學與技術(shù)系 目錄文章編輯2一、需求分析21.問題描述22.基本要求23.需求分析24.開發(fā)環(huán)境3二、概要設計31.流程圖32.結(jié)構(gòu)體構(gòu)造43.設計思想4三、詳細設計41.結(jié)構(gòu)體構(gòu)造42.函數(shù)構(gòu)造53.重點函數(shù)分析6四、調(diào)試與測試6五、執(zhí)行結(jié)果7六、源代碼8集合運算18一、需求分析181.問題描述182.基本要求183.需求分析184.開發(fā)環(huán)境18二、概要設計191.流程圖192.結(jié)構(gòu)體構(gòu)造193.設計思想19三、詳細設計191.結(jié)構(gòu)體構(gòu)造192.函數(shù)構(gòu)造203.重點函數(shù)分析21四、調(diào)試與測試22五、關(guān)鍵源程序清單和執(zhí)行結(jié)果22六、源代碼23文章編輯一、 需求分析1. 問題描述輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。2. 基本要求靜態(tài)存儲一頁文章，每行最多不超過80個字符，共N行，要求：（1）分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字數(shù)；（2）統(tǒng)計某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。存儲結(jié)構(gòu)使用線性表，分別用幾個子函數(shù)實現(xiàn)相應的功能。輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標點符號。輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出全部字母數(shù)、數(shù)字個數(shù)、空格個數(shù)、文章總字數(shù)（3）輸出刪除某一字符串后的文章；3. 需求分析（1）將文本轉(zhuǎn)換為鏈表儲存。（2）統(tǒng)計各個字符數(shù)量。（3）能夠?qū)⒃撴湵泶蛴〕鰜?，并且?zhí)行刪除某一節(jié)點的操作。（4）查找并匹配字符串，并得到對應的位置。4. 開發(fā)環(huán)境系統(tǒng)環(huán)境：Microsoft Windows10 專業(yè)版開發(fā)環(huán)境：Microsoft Visual Studio 2015開發(fā)平臺：Win64開發(fā)語言：C+編譯器：Intel Parallel Studio XE 2013硬件環(huán)境：（1） CPU：Intel Core i7-4710MQ（2） 內(nèi)存：16GB（3） 顯示卡：NVIDIA GeForce GTX960M二、 概要設計1. 流程圖2. 結(jié)構(gòu)體構(gòu)造本程序采用的數(shù)據(jù)結(jié)構(gòu)是單鏈表形式，在每個節(jié)點中存儲一個字符，用指針的方式連接，形成鏈表，通過遍歷的方式來打印和搜尋所需的字符。3. 設計思想本程序旨在處理文字，重點即是先將文本轉(zhuǎn)化為鏈表存儲，然后用對應的函數(shù)遍歷鏈表，得出字符的數(shù)值。使用KMP算法查找對應的字符串，并使用刪除節(jié)點的方式完成字符串的刪除操作。三、 詳細設計1. 結(jié)構(gòu)體構(gòu)造/ 構(gòu)造存儲字符的結(jié)構(gòu)體 typedef struct listNodechar word;struct listNode *next; wordList, *list;/ 構(gòu)造儲存字符數(shù)量的結(jié)構(gòu)體typedef struct int alpha;int digit;int blank;int sum; numStruct, *numNode;/ 構(gòu)造儲存字符位置的結(jié)構(gòu)體typedef struct posNodeint pos;struct posNode *next; posStruct, *posList;2. 函數(shù)構(gòu)造/ 線性鏈表初始化函數(shù)：鏈表頭指針int wordList_init( list *res);/ 存儲結(jié)構(gòu)初始化函數(shù)：結(jié)構(gòu)指針int numNode_init( numNode *num);/ 字符位置鏈表初始化函數(shù)：結(jié)構(gòu)指針int posNode_init( posList *posP);/ 字符位置鏈表增加與儲存函數(shù)：頭指針，插入字符int posNode_add( posList *posP, int posNum);/ 鏈表增加與儲存函數(shù)：頭指針，插入字符int wordList_add( list *res, char letter);/ 文本轉(zhuǎn)換鏈表函數(shù)，同時計算文本中的字符類別和數(shù)量：鏈表頭指針，結(jié)構(gòu)體指針int text_transform( list *res, numNode *num);/ 刪除鏈表的某一節(jié)點：該節(jié)點的前一個節(jié)點的指針int wordList_delete( list *now);/ 鏈表打印：頭指針void wordList_print( list *res);/ 計算next數(shù)組的值：void nextArray_make( char strFind, int next);/ KMP算法：int KMP( char strRes, char strFind, int next);/ KMP統(tǒng)計出現(xiàn)次數(shù)int stringRepeat_count( char strRes, char strFind, posList *posL);/ 字符串查詢：鏈表頭指針，結(jié)構(gòu)void string_search( list *res, numNode *num);/ 字符串刪除函數(shù)：鏈表頭指針，結(jié)構(gòu)void string_delete( list *res, numNode *num);/ 菜單函數(shù)void menu();3. 重點函數(shù)分析在這個程序當中，個人認為最重要的部分就是KMP算法的實現(xiàn)，這個算法的搜索速度極其快速，但是因為不太容易理解，所以實現(xiàn)上有些困難。KMP算法相對于普通的搜索算法，最大的優(yōu)勢就是使用了一個next數(shù)組來幫助算法程序跳轉(zhuǎn)，通過減少比對時間來優(yōu)化效率。這個算法的核心也就是是next數(shù)組的求法。Next數(shù)組保證每一次比對完成以后向后跳轉(zhuǎn)的具體位置。而KMP算法的核心即是計算字符串string，每一個位置之前的字符串的前面部分和后部分的公共部分的最大長度（不包括字符串本身，否則最大長度始終是字符串本身）。這樣構(gòu)造的算法可以在最大程度上向后跳轉(zhuǎn)節(jié)約時間。四、 調(diào)試與測試在調(diào)試本程序時，為了保證輸入輸出的值的正確，基本思路是在每個函數(shù)寫好以后對該函數(shù)的效果進行測試，保證該函數(shù)能正常運行并得出對應正確的結(jié)果，并且對可能會影響到的指針的值進行處理，保證程序的健壯性。如果程序出現(xiàn)了致命的錯誤，我就會打開斷點調(diào)試功能篩查是哪個地方出了問題，然后進行修改。五、 執(zhí)行結(jié)果本程序所需要的文章以文本形式放在程序同目錄下的input_text.txt內(nèi)。打開程序時會自動加載轉(zhuǎn)換本文本，并且不會對原文本進行更改。以下是演示圖片。六、 源代碼#include #include #include / 構(gòu)造存儲字符的結(jié)構(gòu)體 typedef struct listNodechar word;struct listNode *next; wordList, *list;/ 構(gòu)造儲存字符數(shù)量的結(jié)構(gòu)體typedef struct int alpha;int digit;int blank;int sum; numStruct, *numNode;/ 構(gòu)造儲存字符位置的結(jié)構(gòu)體typedef struct posNodeint pos;struct posNode *next; posStruct, *posList;/ 線性鏈表初始化函數(shù)：鏈表頭指針int wordList_init( list *res);/ 存儲結(jié)構(gòu)初始化函數(shù)：結(jié)構(gòu)指針int numNode_init( numNode *num);/ 字符位置鏈表初始化函數(shù)：結(jié)構(gòu)指針int posNode_init( posList *posP);/ 字符位置鏈表增加與儲存函數(shù)：頭指針，插入字符int posNode_add( posList *posP, int posNum);/ 鏈表增加與儲存函數(shù)：頭指針，插入字符int wordList_add( list *res, char letter);/ 文本轉(zhuǎn)換鏈表函數(shù)，同時計算文本中的字符類別和數(shù)量：鏈表頭指針，結(jié)構(gòu)體指針int text_transform( list *res, numNode *num);/ 刪除鏈表的某一節(jié)點：該節(jié)點的前一個節(jié)點的指針int wordList_delete( list *now);/ 鏈表打?。侯^指針void wordList_print( list *res);/ 計算next數(shù)組的值：void nextArray_make( char strFind, int next);/ KMP算法：int KMP( char strRes, char strFind, int next);/ KMP統(tǒng)計出現(xiàn)次數(shù)int stringRepeat_count( char strRes, char strFind, posList *posL);/ 字符串查詢：鏈表頭指針，結(jié)構(gòu)void string_search( list *res, numNode *num);/ 字符串刪除函數(shù)：鏈表頭指針，結(jié)構(gòu)void string_delete( list *res, numNode *num);/ 菜單函數(shù)void menu();/ 主函數(shù)int main (void)menu();return 0;/ 線性鏈表初始化函數(shù)：鏈表頭指針int wordList_init( list *res)(*res) = (list)malloc(sizeof(wordList);if( (*res) )(*res)-next = NULL;(*res)-word = ;return 1;elseprintf(空間分配失敗，請重試。n);return 0;/ 存儲結(jié)構(gòu)初始化函數(shù)：結(jié)構(gòu)指針int numNode_init( numNode *num)(*num) = (numNode)malloc(sizeof(numStruct);if( (*num) )(*num)-alpha = 0;(*num)-digit = 0;(*num)-blank = 0;(*num)-sum = 0;return 1;elseprintf(空間分配失敗，請重試。n);return 0;/ 字符位置鏈表初始化函數(shù)：結(jié)構(gòu)指針int posNode_init( posList *posP)(*posP) = (posList)malloc(sizeof(posStruct);if (*posP)(*posP)-next = NULL;(*posP)-pos = 0;elsereturn 0;/ 字符位置鏈表增加與儲存函數(shù)：頭指針，插入字符int posNode_add( posList *posP, int posNum)while (*posP)-next)(*posP) = (*posP)-next;/ 分配空間(*posP)-next = (posList)malloc(sizeof(posStruct);if (*posP)-next)(*posP) = (*posP)-next;(*posP)-next = NULL;(*posP)-pos = posNum;return 1;elseprintf(空間分配失敗，請重試。n);return 0;/ 鏈表增加與儲存函數(shù)：頭指針，插入字符int wordList_add( list *res, char letter)while (*res)-next)(*res) = (*res)-next;/ 分配空間(*res)-next = (list)malloc(sizeof(wordList);if (*res)-next)(*res) = (*res)-next;(*res)-next = NULL;(*res)-word = letter;return 1;elseprintf(空間分配失敗，請重試。n);return 0;/ 文本轉(zhuǎn)換鏈表函數(shù)，同時計算文本中的字符類別和數(shù)量：鏈表頭指針，結(jié)構(gòu)體指針int text_transform( list *res, numNode *num)/ 文件操作，打開文件FILE *fp;fp = fopen( input_text.txt, r);char letter;/ 初始化鏈表wordList_init( &(*res);numNode_init( &(*num);/ 重新聲明變量，操作resNow來構(gòu)建鏈表list resNow = (*res);/ 循環(huán)將文本讀入線性表中while( (letter = getc(fp) != EOF)wordList_add( &resNow, letter);if( isalpha( letter) )(*num)-alpha+; /求字母數(shù)else if( isdigit( letter)(*num)-digit+; /求數(shù)字個數(shù)else if( letter = )(*num)-blank+; /求空格數(shù)(*num)-sum+;/ 關(guān)閉文件fclose(fp);/ 刪除鏈表的某一節(jié)點：該節(jié)點的前一個節(jié)點的指針int wordList_delete( list *now)list temp = (*now)-next;(*now)-next = temp-next;free(temp);return 1;/ 鏈表打?。侯^指針void wordList_print( list *res)list temp = (*res);while( temp-next )temp = temp-next;printf(%c,temp-word);/ 計算next數(shù)組的值：void nextArray_make( char strFind, int next)int i,j;int len = strlen(strFind); next0 = -1;/next0放上-1 i = 0;/指向字符串每個字符的指針 j = -1; while( i len )/沒有到達結(jié)尾的話 if( j = -1 | strFindi = strFindj)/如果是第一個字符或遇到相同的字符 i+;j+;nexti = j; else j = nextj; / for( i = 0; i len; i+)/輸出next值 / printf(%d,nexti); / / KMP算法：int KMP( char strRes, char strFind, int next) int i, j; i = j = 0;int lenRes = strlen(strRes);int lenFind = strlen(strFind); while( i lenRes & j lenFind )int nextlenTemp;nextArray_make( strFind, next);int pos = KMP( strTemp, strFind, next);if(pos = -1)break;elsestrTemp = &(strTemppos+lenFind);lenTemp = strlen(strTemp);repeatCount+;posCount += (pos + lenFind);printf(n第 %d 在第 %d 個位置出現(xiàn)。n, repeatCount, posCount);posNode_add( &tempPOS, posCount);return repeatCount;/ 字符串查詢：鏈表頭指針，結(jié)構(gòu)void string_search( list *res, numNode *num)printf(n請輸入您想要查找的字符串：n);/ 獲得最大長度為文本文件大小的字符串數(shù)組char strFind(*num)-sum;scanf(%s,&strFind);/ 將鏈表轉(zhuǎn)換為數(shù)組處理char strRes(*num)-sum;list temp = (*res);int i = 0;while( temp-next )temp = temp-next;strResi = temp-word;i+;posList pos;posNode_init( &pos);int repeatCount = stringRepeat_count( strRes, strFind, &pos);if ( repeatCount)printf(n該字符串“ %s ”在本文本中出現(xiàn)了 %d 次。, strFind, repeatCount);else printf(沒有搜索到該文本。);/ 字符串刪除函數(shù)：鏈表頭指針，結(jié)構(gòu)void string_delete( list *res, numNode *num)printf(n請輸入您想要刪除的字符串：n);/ 獲得最大長度為文本文件大小的字符串數(shù)組char strFind(*num)-sum;scanf(%s,&strFind);/ 將鏈表轉(zhuǎn)換為數(shù)組處理char strRes(*num)-sum;list temp = (*res);int i = 0;while( temp-next )temp = temp-next;strResi = temp-word;i+;posList pos;posNode_init( &pos);int repeatCount = stringRepeat_count( strRes, strFind, &pos);if ( !repeatCount)printf(沒有搜索到該文本。);return;printf(n該字符串“ %s ”在本文本中出現(xiàn)了 %d 次。n, strFind, repeatCount);printf(n您確認刪除這個字符串嗎？nn回復數(shù)字 1 來確認此操作。n);i = 0;scanf(%d,&i);if ( i = 1)int count = 0;list temp = (*res);pos = pos-next;while( temp-next & pos)int lenDelete = strlen(strFind);count+;if ( count = pos-pos)count += lenDelete;while ( lenDelete)wordList_delete( &temp);lenDelete-;pos = pos-next;temp = temp-next;printf(nn刪除成功，現(xiàn)文本如下：nn);wordList_print( &(*res);return;/ 菜單函數(shù)void menu()/ 聲明鏈表頭指針list res;/ 聲明數(shù)量結(jié)構(gòu)體numNode num;/ 將文本轉(zhuǎn)換為鏈表保存并統(tǒng)計字符數(shù)量text_transform( &res, &num);int funChoose;while (1)printf(n請輸入序號來選擇您需要的功能：nn);printf(1.顯示文本nn2.顯示字符統(tǒng)計情況。nn3.查詢字符串nn4.刪除字符串nn);scanf(%d, &funChoose);system(cls);if ( funChoose = 1)wordList_print( &res); else if ( funChoose = 2)printf(n字母數(shù)：%dnn數(shù)字數(shù)：%dnn空格數(shù)：%dnn字符總數(shù)：%dn, num-alpha, num-digit, num-blank, num-sum); else if ( funChoose = 3)string_search( &res, &num); else if ( funChoose = 4)string_delete( &res, &num);elseprintf(n請輸入正確的選擇數(shù)字。);printf(nnn);system(pause);system(cls);集合運算一、 需求分析1. 問題描述使用鏈表來表示集合，完成集合的合并，求交集等操作。2. 基本要求（1）用鏈表表示兩個集合（2）對兩個集合分別從小到大排序（3）兩個集合合并成另一個新集合，如數(shù)值相同，合并為一個數(shù)據(jù)項（4）求出兩個集合的交集建立一個新的集合。3. 需求分析（1）將該集合轉(zhuǎn)換為鏈表儲存。（2）分別對兩個集合進行排序操作。（3）合并兩個集合，排序并合并相同數(shù)據(jù)項。（4）打印出交集。4. 開發(fā)環(huán)境系統(tǒng)環(huán)境：Microsoft Windows10 專業(yè)版開發(fā)環(huán)境：Microsoft Visual Studio 2015開發(fā)平臺：Win64開發(fā)語言：C+編譯器：Intel Parallel Studio XE 2013硬件環(huán)境：（1） CPU：Intel Core i7-4710MQ（2） 內(nèi)存：16GB（3） 顯示卡：NVIDIA GeForce GTX960M二、 概要設計1. 流程圖2. 結(jié)構(gòu)體構(gòu)造本程序采用的數(shù)據(jù)結(jié)構(gòu)是單鏈表形式，在每個節(jié)點中存儲集合中的一個元素，用指針的方式連接，形成鏈表，通過遍歷的方式來排序和打印元素。3. 設計思想本程序旨在集合運算，所以一開始便構(gòu)造兩個鏈表分別存儲兩個集合，并進行分別排序。最后使用總處理函數(shù)得到交集和并集，具體設計在第三節(jié)的重點函數(shù)分析中。三、 詳細設計1. 結(jié)構(gòu)體構(gòu)造/ 構(gòu)造結(jié)構(gòu)體儲存數(shù)據(jù)typedef struct nodeint num; struct node *next; groupList, *list;2. 函數(shù)構(gòu)造/ 鏈表初始化函數(shù)：鏈表頭指針int group_init( list *res);/ 鏈表增加函數(shù)：鏈表頭指針，值int group_add( list *res, int num);/ 刪除該節(jié)點的下個節(jié)點：頭指針void group_delete( list *res);/ 鏈表打印函數(shù)：頭指針void group_print( list *res);/ 獲取集合：頭指針，集合元素總數(shù)void group_get( list *res, int numSum);/ 鏈表的冒泡排序：頭指針void group_BubbleSort( list *res);/ 鏈表的總處理：四個頭指針/ 在這個函數(shù)中調(diào)用了冒泡排序函數(shù)和刪除節(jié)點函數(shù)void group_process( list *groupA, list *groupB, list *groupUnion, list *groupInter);/ 菜單函數(shù)void menu ();3. 重點函數(shù)分析本程序的重點在于鏈表的總處理函數(shù)，在此附上代碼和說明。因為本程序較為簡單，所以沒有特意重新構(gòu)造一個鏈表來分別保存并集和交集。這個函數(shù)的基本思路是講這兩個鏈表合在一起進行排序，然后遍歷這個總鏈表。當遍歷到兩次出現(xiàn)同一個值時，證明這個值在兩個鏈表中均出現(xiàn)過。則將其放到新構(gòu)造的交集鏈表中。而當出現(xiàn)了三次時，則刪除。由此得到的遍歷后的鏈表即為并集的集合。/ 鏈表的總處理：四個頭指針void group_process( list *groupA, list *groupB, list *groupUnion, list *groupInter) list a, b, c, temp; c = (*groupInter); / 將AB鏈表合在一起 temp = (*groupA); while (temp-next) temp = temp-next; temp-next = (*groupB)-next; temp = (*groupA); / 排序總鏈表 group_BubbleSort( &temp); / 總鏈表中的重復數(shù)據(jù)計入交集鏈表中 while (temp-next) b = temp; temp = temp-next; if (a = temp-next) if ( a-num = temp-num ) if ( !(*groupInter)-next ) group_add( &c, a-num); if ( a-num != c-num) group_add( &c, a-num); / 刪除重復數(shù)據(jù) group_delete(&temp); temp = b; / 剩下的即是合集 (*groupUnion) = (*groupA);四、 調(diào)試與測試在調(diào)試本程序時，為了保證輸入輸出的值的正確，基本思路是在每個函數(shù)寫好以后對該函數(shù)的效果進行測試，保證該函數(shù)能正常運行并得出對應正確的結(jié)果，并且對可能會影響到的指針的值進行處理，保證程序的健壯性。如果程序出現(xiàn)了致命的錯誤，我就會打開斷點調(diào)試功能篩查是哪個地方出了問題，然后進行修改。五、 關(guān)鍵源程序清單和執(zhí)行結(jié)果六、 源代碼#include #include / 構(gòu)造結(jié)構(gòu)體儲存數(shù)據(jù)typedef struct nodeint num; struct node *next; groupList, *list;/ 鏈表初始化函數(shù)：鏈表頭指針int group_init( list *res);/ 鏈表增加函數(shù)：鏈表頭指針，值int group_add( list *res, int num);/ 刪除該節(jié)點的下個節(jié)點：頭指針void group_delete( list *res);/ 鏈表打印函數(shù)：頭指針void group_print( list *res);/ 獲取集合：頭指針，集合元素總數(shù)void group_get( list *res, int numSum);/ 鏈表的冒泡排序：頭指針void group_BubbleSort( list *res);/ 鏈表的總處理：四個頭指針void group_process( list *groupA, list *groupB, list *groupUnion, list *groupInter);/ 菜單函數(shù)void menu ();int main (void)menu(); return 0;/ 鏈表初始化函數(shù)：鏈表頭指針int group_init( list *res) / 分配空間 (*res) = (list)malloc(sizeof(groupList); if (*res) (*res)-next = NULL; (*res)-num = 0; return 1; else return 0; / 鏈表增加函數(shù)：鏈表頭指針，值int group_add( list *res, int num) / 判斷當前指針是否指向最后一個節(jié)點 while(*res)-next) (*res) = (*res)-next; printf(指針有誤。); / 分配空間 (*res)-next = (list)malloc(sizeof(groupList); if (*res)-next) (*res) = (*res)-next; (*res)-next = NULL; (*res)-num = num; return 1; else return 0; / 刪除該節(jié)點的下個節(jié)點：頭指針void group_delete( list *res) list temp = (*res)-next; if (temp-next) (*res)-next = temp-next; free(temp); / 鏈表打印函數(shù)：頭指針void group_print( list *res) / 循環(huán)打印項 list temp = (*res); while ( temp-next ) temp = temp-next; printf(%d , temp-num); / 獲取集合：頭指針，集合元素總數(shù)void group_get( list *res, int numSum) int i = 1; list temp = (*res); int tempNum; while ( inext;n = (*res)-next;for ( m = (*res)-next; m; m = m-next ) for ( n = m-next; n; n = n-next ) if ( (m-num) (n-num) ) int temp = m-num;m-num = n-num;n-num = temp; / 鏈表的總處理：四個頭指針void group_process( list *groupA, list *groupB, list *groupUnion, list *groupInter) list a, b, c, temp; c = (*groupInter); / 將AB鏈表合在一起 temp = (*groupA); while (temp-next) temp = temp-next; temp-next = (*groupB)-next; temp = (*groupA); / 排序總鏈表 group_BubbleSort( &temp); / 總鏈表中的重復數(shù)據(jù)計入交集鏈表中 while (temp-next) b = temp; temp = temp-next; if (a = temp-next) if ( a-num =