...13/13XX理工大學《數據結構》課程設計報告黃博學院計算機與通信工程專業計算機科學與技術班級計算機0903班學號200986250311學生姓名黃博指導教師陳倩詒課程成績完成日期20XX7月3日課程設計成績評定學院城南學院專業計算機科技與技術班級計算機科學與技術學號200986250311學生姓名黃博指導教師陳倩詒完成日期20XX7月3日指導教師對學生在課程設計中的評價課程設計中的創造性成果學生掌握課程內容的程度課程設計論文的質量指導教師對課程設計的評定意見綜合成績指導教師簽字2011年7月10日課程設計任務書城南學院計算機科學與技術專業課程名稱數據結構課程設計時間2010～2011學年第2學期18～20周學生姓名黃博指導老師陳倩詒題目串的查找和替換主要內容：問題描述：打開一篇英文文章,在該文章中找出所有給定的單詞,然后對所有給定的單詞替換為另外一個單詞,再存盤要求：〔1通過實際項目的分析、設計、編碼、測試等工作,掌握用C語言來開發和維護軟件?！?按要求編寫課程設計報告書,能正確編寫分析、設計、編碼、測試等技術文檔和用戶使用手冊。應當提交的文件：〔1課程設計學年論文?！?課程設計附件〔主要是源程序。用C++語言解決串的查找和替換問題學生姓名：黃博指導老師：陳倩詒摘要本課程設計主要解決的在一篇英語文章中,在文章中找出所指定的單詞,然后對所指定的單詞進行替換,替換為另一個單詞,再存盤的課程設計。先建立一個文件,然后從文件中讀取字符串保存到數組中。從鍵盤輸入被替換的單詞,然后刪除這個單詞。從鍵盤中輸入替換的單詞,把它插入到被刪除的單詞的位置。然后把該字符串再寫入到文件中。程序通過調試運行,初步實現了設計目標。關鍵詞程序設計；C++；替換；字符串目錄1.引言·······················································12.課程設計目的和要求·······································22.1課程設計目的···············································22.2課程設計要求···············································23.課程設計分析·············································33.1課程設計思路················································33.2課程設計要求函數分析········································33.3課程設計主要流程············································44.課程設計調試···············································65.課程設計總結···············································9參考文獻·······················································10附錄····························································11...1引言數據結構是一門理論性強,思維抽象,難度較大的一門課程。是基礎課專業課之間的橋梁。該課程的先行課時計算機基礎,程序設計語言、離散數學等,后續課程有操作系統、編譯原理、數據庫原理、軟件工程等。通過本門課程的學習,我們應該透徹的理解各種數據的特點,學會數據的組織方法和實現方法,并進一步培養良好的程序設計能力和解決實際問題的能力,而且該課程的研究方法對我們學生在校和離校后學習和工作有著重要的影響。[1]數據結構是計算機科學與技術的一門核心專業基礎課程,在該專業課程中有著承上啟下的作用,學習好數據結構對于提高理論認知水平和實踐操作能力有重要的作用,學習數據結構的最終目的是為了獲得解決求解問題的能力。對于現實世界的問題,應該從中抽象出一個適當的數學模型,該數學模型在計算機的用數構表示出來,然后在設計一個求數學模型的的算法,再進行編程調試,最后獲得問題的解答。數據課程設計著眼培養我們實踐能力,加強編程能力的培養。第1頁2課程設計目的和要求2.1課程設計目的通過課程設計的題目練習,強化對所學知識的掌握及對問題分析和任務定義的理解,對題目做了相應的邏輯分析和數據結構的選擇通過對任務的分析,為操作對象定義相應的數據結構,一過程化程序設計的思想原則劃分各個模塊,定義數據的抽象數據類型。分模塊對題目進行設計,強化對C++語言的掌握和對數據結構選擇及掌握。通過程序的編譯掌握對程序的調試及思想,并且學習一些編程的技巧。養成良好的編程習慣。[2]以及讓學生對書本的上的知識進行實踐。算法和數據結構是計算機科學與技術專業綜合的專業基礎課。它不僅是計算機學科的核心課程,而且成為其他理工專業的熱門選修課。它又是操作系統、編譯原理、數據庫原理、算法分析、人工智能、圖像處理等專業課程的前導課。具有承上啟下的作用。數據結構的研究不僅設計到計算機硬件的研究方面,而且與計算機軟件研究有著密切的關系。計算機科學各領域都要用到數據構,該課程的目的就是介紹一些常用的數據結構,闡明數據結構的內在邏輯關系,討論它們計算機內的儲存表示,并結合各種典型它們在進行各種運算時的動態性質和實際的執行算法。2.2課程設計要求1.問題分析和任務的定義對問題的描述應避免具體的算法和涉及的數據結構,它是對要完成的任務明確的回答,強調是做什么,而不是怎么做。2.詳細的設計及編碼算法的描述與代碼的編寫。3.上機調試源程序的輸入及代碼的調試。第2頁3課程設計分析3.1課程設計思路先建立一個文件,然后從文件中讀取字符串保存到數組中。從鍵盤輸入被替換的單詞,然后刪除這個單詞。從鍵盤中輸入替換的單詞,把它插入到被刪除的單詞的位置。然后把該字符串再寫入到文件中。計算機上的非數值處理的對象基本上上字符串數據,字符串一般簡稱為串。串〔string是由零個或多個字符組成的有限序列,一般記為s=`a1a2…an`<n大于零>。通常稱字符在序列中的序號為該字符在串中的位置,子串在主串中的位置則以子串的第一個字符在主串中的位置來表示。當兩個串的每個字符都相等時〔串值相等,稱這兩個串是相等的。[3]在子串的查找定位過程中,分別利用計數指針j和k指示被替換串和替換串中當前正待比較的字符位置。所用算法的基本思想是：首先利用指針i來完成被替換串和替換串在文本中的遍歷,從被替換串和替換串的第一個字符起進行比較,若相等則繼續逐個比較后續字符；否則完成一次比較,指針i遞增進行下一次的比較。以此類推,直至匹配成功[4]。3.2課程設計主要函數分析本設計所采用的數據結構charString[65535]; //長度要大于輸入文本文件的長度！charfindString[50]; //輸入的要查找的字符charreplaceString[50];//輸入的替換后的string.程序中各部分功能函數：voidInitStr<>/*從文件初始化數組*/；voidInputReplaceChar<>/*輸入要替換的字符串*/；intFindString<>/*查找第一個出現要查找字符的下標*/；voidFindStrings<>/*查看文章中共有多少個要查找的字符*/；voidInsert<charsource[],intindex,chartarget[]>/*從指定的下標開始插入target數組第3頁中的元素*/；voidReplace<>/*將String中要替換的內容替換掉*/；voidSave<>/*保存修改后的文章信息*/；voidMenu<>/*程序主菜單*/。3.3課程設計主要流程首先利用標準庫函數fopen<>打開一個文件,然后從文件中讀取字符串保存到數組中,完成文件的讀入。其次,根據鍵盤輸入的選擇命令〔數字1~4程序調用不同功能模塊來完成相應的操作。[5]程序中用戶選擇命令〔數字1~4設置："1"：文本文件顯示；"2"：子串查找；"3"：子串替換；"4"：退出整個程序。程序設計流程圖如圖3.1所示：圖3.1設計流程圖第4頁程序運行后顯示主菜單,提示用戶根據需要選擇不同的命令操作。程序根據鍵盤輸入的選擇命令〔數字1~4調用不同功能模塊來完成相應的操作。如果用戶輸入的命令是"1",主函數調用InitStr<>函數從文件進行初始化數組,利用標準輸入函數將該數組輸出到標準輸出上；如果用戶輸入的命令是"2",主函數調用FindStrings<>函數查找匹配的字符串并連同匹配的字符串個數一并輸出到標準輸出上；如果用戶輸入的命令是"3",主函數調用Replace<>函數,將String中要替換的內容替換掉；如果用戶輸入的命令是"4",程序自動退出。第5頁4課程設計調試程序的開發與調試均在MicrosoftVisualC++環境下進行。首先程序運行后顯示程序的主菜單,主菜單命令選擇設置"1"：文本文件顯示；"2"：子串查找；"3"：子串替換；"4"：退出整個程序。程序根據用戶輸入的命令〔數字1~4進行相應的操作輸入命令一后程序的運行結果：顯示文本文件的內容。如圖4.1圖4.1程序命令一的運行結果輸入命令二后程序的運行結果：選擇命令二,進行字符串的查找測試。從圖4.3中可以看到查找后的結果。圖中顯示出查找到的字符串getchar的數量為3個,并顯示查找成功等信息。如圖4.2圖4.3第6頁圖4.2程序命令二字符串查找圖4.3程序命令二字符串查找再次輸入命令三后程序的運行結果：選擇命令三,進行字符串的替換測試。從圖4.4中可以看到替換后的結果。圖中顯示出被替換的字符串getchar和替換后的字符串charget,并顯示替換成功等信息第7頁圖4.4程序命令三字符串替換圖4.5程序命令三字符串替換再次輸入命令一查看命令三是否真正替換成功：從圖4.5中可以看到替換后的結果,鼠標箭頭所指的方向看以看到原先文本文件〔對比前面的程序測試圖中最后一行〔當然,先前是查找到三個,這里只以最后一行容易觀察到的來進行說明的getchar<>已經被替換成了charget<>,說明程序替換成功,并將替換后的文本文件進行了保存。第8頁5課程設計總結課程設計是培養學生綜合運用所學知識,發現,提出,分析和解決實際問題,鍛煉實踐能力的重要環節。數據結構是程序設計的基本算法,經過這次數據結構的課程設計對于實際應用數據結構有很大幫助,尤其是對于串的學習上。在數據結構課程的學習及其課程設計中要感謝陳老師的悉心教導,為我細心的指出錯誤。第9頁參考文獻[1]譚浩強.C++程序設計.北京：清華大學出版社.2004[2]王曉東.計算機算法與分析.北京:電子工業出版社.2006[3]徐孝凱.C++語言基礎教程.北京:清華大學出版社.2002[4]9.EsakovJ,WeissT.DataStructures:AnAdvancedApproachUsingC.Prentice-Hall,Inc.,1989年[5]晉良潁.《數據結構》.人民郵電出版社.2002第10頁附錄：源程序：#include<stdio.h>#include<stdlib.h>#include<string.h>FILE*fp;charString[65535]; //長度要大于輸入文本文件的長度！charfindString[50]; //輸入的要查找的字符charreplaceString[50];//輸入的替換后的stringvoidInitStr<>{/*從文件初始化數組*/ inti=0; fp=fopen<"test.txt","r">;//打開文件,文件在當前目錄下r-readonly while<!feof<fp>> { String[i]=fgetc<fp>;//intfgetc<FILE*stream>; i++; //Readacharacterfromastream. } String[--i]='\0';//添加結束標志fclose<fp>;}voidInputReplaceChar<>{/*輸入要替換的字符串*/ printf<"輸入被替換的字符串：">; scanf<"%s",findString>; printf<"輸入要替換的字符串：">; scanf<"%s",replaceString>;}intFindString<>{/*查找第一個出現要查找字符的下標*/ inti,j,k; for<i=0;i<strlen<String>;i++> { j=i;k=0; while<<String[j]==findString[k]>&&<findString[k]!='\0'>&&<String[j]!='\0'>> {//當前比較的兩個字符相等,并且主/模式串都為結束,繼續下一個的比較第11頁j++; k++; } if<findString[k]=='\0'> returni;//返回的是最后的匹配位置 } return-1;}voidFindStrings<>{/*查看文章中共有多少個要查找的字符*/ inti,j,k,all=0; printf<"輸入要查找的字符串：">; scanf<"%s",findString>; for<i=0;i<strlen<String>;i++> { j=i;k=0; while<<String[j]==findString[k]>&&<findString[k]!='\0'>&&<String[j]!='\0'>> {//當前比較的兩個字符相等,并且主/模式串都為結束,繼續下一個的比較 j++; k++; } if<findString[k]=='\0'> all++;//記錄匹配的字符串的個數} printf<"查找成功！\n">;printf<"共查找到%d個%s",all,findString>; printf<"\n按任意鍵返回\n">;}voidInsert<charsource[],intindex,chartarget[]>{/*從指定的下標開始插入target數組中的元素*///Insert<String,pos,replaceString>; inti,j,k,m; j=strlen<target>;//計算串target的長度,存入j k=strlen<source>; source[j+k]='\0';//string串以'\0'結束 i=j+k-1;//減1后為實際長度 m=k-1; while<m>=index>//index為pos,pos是找到的位置 { source[i]=source[m]; i--; m--;}第12頁 i=index;//index為pos,pos是找到的位置 m=0; while<m<j> { source[i]=target[m]; i++; m++; }}voidReplace<>{/*將String中要替換的內容替換掉*/ intpos,b=0; InputReplaceChar<>; do { pos=FindString<>;//FindString<>--returni;返回的是最后的匹配位置 b=pos; //FindString<>未找到時返回的是-1,故判斷b==-1 if<b==-1> { printf<"查找內容不存在！\n">; return; } else { while<String[b+strlen<findString>]!='\0'> { String[b]=String[b+strlen<findString>]; b++; } String[b]='\0';//字符串添加結束符 Insert<String,pos,replaceString>; } pos=FindString<>; }while<pos!=-1>; printf<"替換成功！\n">;printf<"\n按任意鍵返回\n">;getchar<>;}voidSave<>{/*保存修改后的