一资料结构导论

《一资料结构导论》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一﹑資料結構導論1前言2模組化程式設計從問題到程式程式設計的標準由上而下的設計概念3資料與結構4資料結構與演算法何謂演算法演算法的評估1前言進階的程式設計課程程式設計→資料結構→演算法→離算數學→計算理論實務與理論2從問題到程式程式設計的五個階段需求分析階段：問題﹑輸入﹑輸出﹑設備﹑工具設計階段：演算法﹑資料結構﹑程式模組程式撰寫階段驗證階段：測試﹑偵錯維護階段：文件相關課程系統分析﹑程式設計﹑資料結構﹑演算法﹑軟體工程3程式設計的標準簡明性：簡單﹑易懂﹑明瞭可靠性：將錯誤減到最低可修改性：容易擴展﹑功能增加可移植性：跨平台程式

2、設計4由上而下的設計概念模組化：divideandconquer主程式子程式專案(Project)模組(Module)程式(Program)函數(Function)敘述(Statement)範例：Editor五大模組鍵盤處理：keoard.c螢幕處理：screen.c資料儲存：data.c命令列處理：command_line.c檔案處理：file.c個別編譯：SeparateCompile範例：Editor（續）鍵盤處理模組一般資料輸入控制鍵游標區塊字元﹑行﹑列之增加與刪除範例：Editor（續）鍵盤處理模組：游標處理上移一行︰

3、↑下移一行︰↓標右移一列︰→左移一列︰←移到行首︰Home移到行末︰End上捲一頁︰PageUp下捲一頁︰PageDown2資料與結構資料－data所有可以輸入到計算機中，並且計算機程式處理的符號的總稱，包括數值資料﹑字串資料﹑影像﹑聲音﹑視訊等等資料形態：資料的值域和其基本運算整數值域－-32768~32767運算：＋－＊／％字元值域－0~127運算－大小寫轉換2資料與結構資料結構(datastructure)：資料的結構(thestructureofdata)有結構性的資料(structureddata)結構：資料之間的關聯

4、性集合關係：無順序性的資料關係線性關係：陣列﹑串列﹑堆疊﹑佇列一對多關係：樹狀結構多對多關係：圖形結構四種基本資料結構圖ａ集合關係ｂ線性關係ｃ樹狀關係ｄ圖形關係2資料與結構研究資料結構的目的節省資料儲存所需的空間節省資料處理所需的時間邏輯資料結構－Logical資料與資料之間的關聯性和其計算實體資料結構－Physical資料如何儲存﹑程式如何實作3資料結構與演算法演算法：資料處理程式執行的步驟演算法的特性有限性：在有限的步驟內結束確定性：針對資料的特性，每一個執行步驟都是明確的輸入／輸出：可行性：與程式語言無關：ＣorVB，do

5、n’tcare整數n是否為質數－演算法1令i的值等於22如果i可以整除n，則n不是質數，迴圈結束3將i的值加14如果i的值小於n，回到步驟25n是質數整數n是否為質數－SPARK1fori=2ton-12ifnmodi=0then3n不是質數4Endloop5endif6nextI7n是質數整數n是否為質數－流程圖輸入n，令i=2i

6、6for(j=2;j

7、，使得p

8、n∵p

9、n＝﹥存在整數q=n/p∵p>√n∴q<√n→←找出小於n的質數﹙三）1prime3(intn)2{3inti,j,p,v;4printf(“%dt”,2);5for(i=3;i

10、等時間複雜度執行程式所需的時間，包括編譯﹑連結﹑執行所需的時間，其中又以後者最為重要1.3.2演算法的評估（續）局部性80／20定理：百分之八十的時間是在執行百分之二十的程式敘述時間局部性空間局部性大Ｏ記號f(n)=n2+100n→O(n2)NF(n)n2100