大話數據結構之一（緒論、算法） - liyunhua－IT工程師數位筆記本

文章出處

數據結構緒論

數據結構是相互之間存在一種或多種特定關系的數據元素的集合

程序設計=數據結構+算法

數據結構事實上就是一門研究非數值計算的程序設計問題的操作對象，以及它們之間的關系和操作等相關問題的學科。

數據是描述客觀事件的符號，是計算機中可以操作的對象，是能被計算機識別，并輸入能計算機處理的符號集合，也就是說數據必須具備兩個前提：

可以輸入到計算機中
能被計算機程序處理

數據

數據元素是組成數據的、有一定意義的基本單位，在計算機中通常作為整體處理，也被稱為記錄

數據項：一個數據元素可以由若干個數據項組成

數據項是數據不可分割的最小單位

數據對象：是性質相同的數據元素的集合，是數據的子集

不同數據元素之間不是獨立的，而是存在特定的關系，我們將這些關系稱為結構

數據結構：是相互之間存在一種或多種特定關系的數據元素的集合

邏輯結構：是指數據對象中數據元素之間的相互關系。

集合結構:集合結構中的數據元素除了同屬于一個集合外，它們之間沒有其它關系
線性結構：線性結構中的數據元素之間是一對一的關系
樹性結構：樹性結構中的數據元素之間是一對多的層次關系
圖形結構：圖形結構中的數據元素是多對多的關系

物理結構：是指數據的邏輯結構在計算機中的存儲結構。

順序存儲結構：是把數據元素存儲在地址連續的存儲單元里，其數據間的邏輯關系和物理關系是一致的
鏈式存儲結構：是把數據元素存儲在任意的存儲單元里，這組存儲單元可以是連續的，也可是不連續的。

數據類型：是指一組性質相同的值的集合及定義在此集合上的一些操作的總稱。

原子類型：是不可再分解的基本類型
結構類型：由若干個類型組合而成，是可以再分解的。

抽象是指抽取出事物具有的普遍性的本質。（抽取的意義在于數據類型的數學抽象特性）

抽象數據類型（Abstract Data Type ADT）：是指一個數據模型及定義在該模型上的一組操作。

抽象數據類型體現了程序設計中問題分解、抽象和信息隱藏的特征。

算法

算法：是解決特定問題求解步驟的描述，在計算機中表現為指令的有限序列，并且每條指令表示一個或多個操作。

算法的特性

輸入：具有零個或多個輸入
輸出：至少有一個或多個輸出
有窮性：在執行有限的步驟之后，自動結束而不會出現無限循環，并且每一個步驟在可接受的時間內完成
確定性：算法的每一個步驟都具有確定的含義，不會出現二義性
可行性：算法的每一步都必須是可行的，也就是說，每一步都能夠通過執行有限的次數完成

算法的設計要求

正確性：至少應該具有輸入、輸出和加工處理無歧義性、能正確反映問題的需求、能夠得到問題的正確答案
可讀性：算法設計的另一個目的是為了全球閱讀、理解和交流
健壯性：當輸入數據不合法時，算法也能夠做出相關處理，而不是產生異常或莫名其妙的結果
時間效率高和存儲量低：設計算法應該在盡量滿足時間效率高和存儲量低的需求

算法效率的度量方法

事后統計方法：通過設計好的測試程序和數據，利用計算機計時器對不同算法編制的程序的運行時間進行比較，從而確定算法效率的高低（不科學、不準確）
事前分析估算方法：在計算機程序編制前，依據統計方法對算法進行估算

程序在計算機運行的時間取決于以下因素：

算法采用的策略、方法
編譯產生的代碼質量
問題的輸入規模
機器執行指令的速度

也就是說一個程序的運行時間依賴于算法的好壞和問題的輸入規模，最終在分析程序的運行時間時，最重要的是把程序看成是獨立于程序設計語言的算法或一系列的步驟

算法時間復雜度

在判斷一個算法的效率時，函數中的常數和其他次要項常常可以忽略，而更應該關注主項的階數

如何分析一個算法的時間復雜度呢？方法就是：

常用時間復雜度分析

單純的分支結構（不包含在循環結構中），其時間復雜度都是O(1)

分析算法的復雜度，關鍵是要分析循環結構的運行情況

純性階

            int i;
            for (i = 0; i < n; i++)//時間復雜度為O(n)
            { }

對數階

            int count = 1;
            while (count<n)//由于count乘2之后，就距離n更近了一步，也就是2的x次方等于2 x=log2的n
                //所以時間復雜度為O(logn)
            {
                count = count * 2;
            }

平方階

            int i, j;
            for (i = 0; i < n; i++)//時間復雜度為O(n的平方)
            {
                for (j = 0; j < n; j++)
                {
                    /*這里面的代碼為時間復雜度為O(1)的程序步驟序列*/
                }
            }

分析一個相對復雜一點兒的......

        void fuc(int cout)//這個函數的時間復雜度為O(n)
        {
            for (int j = 0; j < n; j++)
            {
                /*這里面的代碼為時間復雜度為O(1)的程序步驟序列*/
            }
        }
            n++;//執行次數為1
            fuc(n);//執行次數為n
            for (i = 0; i < n; i++)
            {
                fuc(i);//整個的執行次數為n2
            }
            for (i = 0; i < n; i++)
            {
                for (j = 0; j < n; j++)//當i=0，內循環執行n 當i=1內循環執行n-1次...
                    //所以總的執行次數為n+(n-1)+(n-2)+....+1=(n+1)n/2
                {
                    /*這里面的代碼為時間復雜度為O(1)的程序步驟序列*/
                }
            }