世紀高等院校規(guī)劃教材數(shù)據(jù)結(jié)構(gòu)c語言版-資料下載頁
2025-07-18 00:59本頁面
【正文】 022/8/15 26 為解決理解與執(zhí)行的矛盾 ， 常使用一種稱為偽碼 （ 類 ） 語言的描述方法來進行算法描述 。 類語言介于高級程序設(shè)計語言和自然語言之間 ， 它忽略高級程序設(shè)計語言中一些嚴格的語法規(guī)則與描述細節(jié) ， 因此它比程序設(shè)計語言更容易描述和被人理解 ， 而且比自然語言更接近程序設(shè)計語言 。它雖然不能直接執(zhí)行但很容易被轉(zhuǎn)換成高級語言 。 2022/8/15 27 算法設(shè)計的要求 要設(shè)計一個好的算法通常要考慮以下要求 。 ⑴ 正確 性 (Correctness)： 算法的執(zhí)行結(jié)果應(yīng)當滿足預(yù)先規(guī)定的功能和性能要求 。 ⑵可讀 性 (Readability)： 算法應(yīng)當思路清晰、層次分明、簡單明了、易讀 易懂。 以有利于閱讀者對程序的理解。 ⑶ 健壯性 (Robustness)： 算法應(yīng)具有容錯處理 。 當輸入非法數(shù)據(jù)時 ， 算法應(yīng)對其作出反應(yīng)并適當處理 ， 不至引起嚴重后果 。 ⑷高效性和存儲量需求：效率指算法執(zhí)行的時間。對于解決同一問題的多個算法，執(zhí)行時間短的算法效率高。存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。 算法分析與評價 2022/8/15 28 算法效率的度量 1．時間復(fù)雜度 （ Time plexity） 一個算法的時間復(fù)雜度是指算法運行從開始到結(jié)束所需要的時間。 通常是所處理問題規(guī)模的一個函數(shù) T(n) ，常采用數(shù)量級的形式表示。記作： T(n)=O(f(n)) 稱 T(n)為算法的 (漸近 )時間復(fù)雜度。 2022/8/15 29 2． 空間復(fù)雜度 （ Space plexity） 一個算法的空間復(fù)雜度是指算法運行從開始到結(jié)束所需的存儲量 。 算法的存儲量指的是算法執(zhí)行過程中所需的最大存儲空間 。 算法執(zhí)行期間所需要的存儲量應(yīng)該包括以下三部分： (1) 輸入數(shù)據(jù)所占空間； (2) 程序本身所占空間； (3) 輔 助變量所占空間 。 類似于算法的時間復(fù)雜度 ， 通常以算法的空間復(fù)雜度作為算法所需存儲空間的量度 。 定義： S(n)=O(g(n)) 稱 S(n)為算法的空間復(fù)雜度 。 2022/8/15 30 1． 數(shù)據(jù)結(jié)構(gòu)研究的是數(shù)據(jù)的表示和數(shù)據(jù)之間的關(guān)系 。 從邏輯上講 ， 數(shù)據(jù)有集合 、 線性 、 樹和圖四種結(jié)構(gòu) 。 從存儲結(jié)構(gòu)上講 ，數(shù)據(jù)有順序結(jié)構(gòu) 、 鏈接結(jié)構(gòu) 、 索引結(jié)構(gòu)和散列結(jié)構(gòu)四種 。 理論上 ， 任一種數(shù)據(jù)邏輯結(jié)構(gòu)都可以用任一種存儲結(jié)構(gòu)來實現(xiàn) 。 2． 在集合結(jié)構(gòu)中 ， 數(shù)據(jù)處于無序的 、 各自獨立的狀態(tài)；在線性結(jié)構(gòu)中 ， 數(shù)據(jù)之間是 1對 1的關(guān)系；在樹結(jié)構(gòu)中 ， 數(shù)據(jù)之間是 1對多的關(guān)系；在圖結(jié)構(gòu)中 ， 數(shù)據(jù)之間是多對多的關(guān)系 。 3． 就存儲結(jié)構(gòu)而言 ， 一個數(shù)組占有一片連續(xù)的存儲空間 ， 每個元素的物理存儲單元是按下標位置從 0開始連續(xù)編號的 ， 相鄰元素之間其存儲位置也相鄰 。 對于任一種數(shù)據(jù)的邏輯結(jié)構(gòu) ， 若能夠把元素之間的邏輯關(guān)系對應(yīng)地轉(zhuǎn)換為數(shù)組下標位置之間的物理關(guān)系 ， 則就能夠利用數(shù)組來實現(xiàn)其順序存儲結(jié)構(gòu) 。 本章小結(jié) 2022/8/15 31 4． 抽象數(shù)據(jù)類型是數(shù)據(jù)和對數(shù)據(jù)進行各種操作的集合體 。 這里所說的數(shù)據(jù)是廣義的 ， 是帶有結(jié)構(gòu)的數(shù)據(jù) ， 它可以具有任何邏輯結(jié)構(gòu)和存儲結(jié)構(gòu) 。 5． 算法的評價指標主要為正確性 、 健壯性 、 可讀性和有效性四個方面 。 有效性又包括時間復(fù)雜度 (性 )和空間復(fù)雜度 (性 )兩個方面 。 一個算法的時間和空間復(fù)雜度越好 ， 就越節(jié)省時間和空間 ， 則表明該算法越有效 。 6． 算法的時間復(fù)雜度和空間復(fù)雜度通常用數(shù)量級的形式表示出來。數(shù)量級的形式可分為常量級，對數(shù)級、線性級、平方級、立方級等多個級別。當數(shù)據(jù)處理量較大時，處于前面級別的算法比處于后面級別的算法更有效。
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1