數(shù)據(jù)結(jié)構(gòu)（C語言版）——緒論-創(chuàng)新互聯(lián)

學習目錄：

程序=數(shù)據(jù)結(jié)構(gòu)+算法

創(chuàng)新互聯(lián)從2013年開始，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項目成都做網(wǎng)站、網(wǎng)站設(shè)計網(wǎng)站策劃，項目實施與項目整合能力。我們以讓每一個夢想脫穎而出為使命，1280元廈門做網(wǎng)站,已為上家服務(wù),為廈門各地企業(yè)和個人服務(wù),聯(lián)系電話:13518219792

1.數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項和數(shù)據(jù)對象

2.數(shù)據(jù)結(jié)構(gòu)

3.數(shù)據(jù)類型和抽象數(shù)據(jù)類型

4.算法及算法分析

---

學習內(nèi)容： 程序=數(shù)據(jù)結(jié)構(gòu)+算法

數(shù)據(jù)結(jié)構(gòu)：如何用數(shù)據(jù)正確地描述現(xiàn)實世界的問題，并存入計算機

算法：如何高效地處理這些數(shù)據(jù)，以解決實際問題

1.數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項和數(shù)據(jù)對象

（1）數(shù)據(jù)（Data）：是客觀事物的符號表示，是所有能輸入計算機中并能夠被計算機程序處理的符號的總稱。如：整數(shù)、實數(shù)、字符、字符串及多媒體程序處理的圖形、圖像、聲音及動畫等通過特殊編碼定義后的數(shù)據(jù)。

（2）數(shù)據(jù)元素（Data Element）：是數(shù)據(jù)的基本單位，數(shù)據(jù)元素用于完整地描述一個對象，如圖中的一個頂點，樹中棋盤的一個狀態(tài)。

（3）數(shù)據(jù)項（Data Item）：是組成數(shù)據(jù)元素的、有獨立含義的、不可分割的最小單位。如：學生表中的學生姓名，學號等都是數(shù)據(jù)項。

（4）數(shù)據(jù)對象（Data Object）：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。如：C={‘A’,‘B’,‘C’,‘a(chǎn)’,‘b’,‘c’}。

2.數(shù)據(jù)結(jié)構(gòu)

含義：數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。換句話說，數(shù)據(jù)結(jié)構(gòu)是帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合，“結(jié)構(gòu)”指數(shù)據(jù)元素之間存在的關(guān)系。數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。

（1）邏輯結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)有兩個要素：一是數(shù)據(jù)元素；二是關(guān)系，關(guān)系是指數(shù)據(jù)元素間的邏輯關(guān)系。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，數(shù)據(jù)的邏輯結(jié)構(gòu)通常有：

下面4種結(jié)構(gòu)中所舉的示例是以某班級學生作為數(shù)據(jù)對象（數(shù)據(jù)元素是學生的學籍檔案記錄），來分別考察數(shù)據(jù)元素之間的關(guān)系。

• 集合結(jié)構(gòu)：數(shù)據(jù)元素之間除了“屬于同一集合”的關(guān)系外，別無其他關(guān)系。例如：確定一名學生是否為班級成員，只需將班級看作一個集合結(jié)構(gòu)。
• 線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對一的關(guān)系。例如：將學生信息數(shù)據(jù)按照其入學報到的時間先后順序進行排列，將組成一個線性結(jié)構(gòu)。
• 樹結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對多的關(guān)系。例如：在班級的管理體系中，班長管理多個組長，每位組長管理多名組員，從而構(gòu)成樹結(jié)構(gòu)。
• 圖結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)之間存在多對多的關(guān)系。例如：多位同學之間的朋友關(guān)系，任何兩位同學都可以是朋友，從而構(gòu)成圖結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。

其中，集合結(jié)構(gòu)、樹結(jié)構(gòu)、圖結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)都屬于非線性結(jié)構(gòu)。

線性結(jié)構(gòu)：線性表、棧和隊列、字符串、數(shù)組、廣義表；

非線性結(jié)構(gòu)：樹結(jié)構(gòu)（樹和二叉樹），圖結(jié)構(gòu)（無向圖和有向圖），集合結(jié)構(gòu)。

（2）存儲結(jié)構(gòu)：數(shù)據(jù)對象在計算機中的存儲結(jié)構(gòu)表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)，也稱為物理結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)分為：

• 順序存儲結(jié)構(gòu)：是把邏輯上相鄰的結(jié)點存儲在物理上相鄰的存儲單元里，結(jié)點之間的關(guān)系有存儲單元的鄰接關(guān)系來體現(xiàn)。其優(yōu)點是占用最少的存儲空間；其缺點是由于只能使用相鄰的一整塊存儲單元，因此可能產(chǎn)生較多的碎片現(xiàn)象。
• 鏈式存儲結(jié)構(gòu)：將結(jié)點所占的存儲單元分為兩部分，一部分存放結(jié)點本身的信息，即為數(shù)據(jù)項；另一部分存放該結(jié)點的后繼結(jié)點所對應(yīng)的存儲單元的地址，即為指針項。其優(yōu)點是不會出現(xiàn)碎片現(xiàn)象，充分利用所有的存儲單元；其缺點是每個結(jié)點占用較多的存儲空間。
• 索引存儲結(jié)構(gòu)：用結(jié)點的索引號來確定結(jié)點的存儲地址。其優(yōu)點是檢索速度快。其缺點是增加了附加的索引表，會占用較多的存儲空間；另外在增加和刪除數(shù)據(jù)時由于要修改索引表因而會花費較多時間。
• 散列存儲結(jié)構(gòu)：根據(jù)結(jié)點的值確定它的存儲結(jié)構(gòu)。其優(yōu)點是檢索、增加和刪除結(jié)點的操作都很快；其缺點是采用不好的散列函數(shù)時可能會出現(xiàn)結(jié)點存儲單元的沖突，為解決沖突需要附加的時間和空間開銷。

若采用順序存儲結(jié)構(gòu)，則各個元素在物理上必須是連續(xù)的；若采用非順序存儲結(jié)構(gòu)，則各個元素在物理上可是是離散的。

數(shù)據(jù)的存儲結(jié)構(gòu)會影響存儲空間分配的方便程度。

數(shù)據(jù)的存儲結(jié)構(gòu)會影響對數(shù)據(jù)運算的速度。

（3）數(shù)據(jù)運算：施加于數(shù)據(jù)的操作。如對一張表格的查找、增加、修改、刪除記錄的工作。運算不僅僅是加減乘除，還包括算法。算法的實現(xiàn)是與數(shù)據(jù)的存儲結(jié)構(gòu)密切相關(guān)的。

運算的定義是針對邏輯結(jié)構(gòu)的，指出運算的功能；運算的實現(xiàn)是針對存儲結(jié)構(gòu)的，指出運算的具體操作步驟。

3.數(shù)據(jù)類型和抽象數(shù)據(jù)類型

（1）數(shù)據(jù)類型：是一個值的集合和定義在此集合上的一組操作的總稱。

• 原子類型：其值不可再分的數(shù)據(jù)類型。布爾類型：TRUE，F(xiàn)ALSE，可進行操作：與、或、非...；int類型：-2147483648~2147483647，可進行操作：加、減、乘、除、模運算...
• 結(jié)構(gòu)類型：其值可以再分解為若干成分（分量）的數(shù)據(jù)類型。如結(jié)構(gòu)體

（2）抽象數(shù)據(jù)類型（ADT）：一般指用戶定義的、表示應(yīng)用問題的數(shù)學模型，以及定義在這個模型上的一組操作的總稱，具體包括3個部分：數(shù)據(jù)對象、數(shù)據(jù)對象上關(guān)系的集合以及對數(shù)據(jù)對象的基本操作的集合。

定義一個抽象數(shù)據(jù)類型就是在“定義”一種數(shù)據(jù)結(jié)構(gòu)；確定了抽象數(shù)據(jù)類型的存儲結(jié)構(gòu)，才能“實現(xiàn)”這種數(shù)據(jù)結(jié)構(gòu)。

4.算法及算法分析

（1）算法的定義：為解決某類問題而規(guī)定的一個有限長的操作序列。（換一種說法則是對特定問題求解步驟的一種描述）例如：要解決的問題是做番茄炒蛋，食材則是數(shù)據(jù)結(jié)構(gòu)，步驟則為算法。

（2）算法的特性：

• 有窮性：一個算法必須總是在執(zhí)行有窮步驟后結(jié)束，且每一步都必須在有窮時間內(nèi)執(zhí)行。注：算法必須是有窮的，而程序可以是無窮的。
• 確定性：算法中每條指令必須有確切的含義，對于相同的輸入只能得出相同的輸出。
• 可行性：算法中的所有操作都可以通過將已經(jīng)實現(xiàn)的基本操作運算執(zhí)行有限次來實現(xiàn)。
• 輸入：一個算法有0個或多個輸入。當用函數(shù)描述算法時，輸入往往是通過形參表示的，在它們被調(diào)用時，從主函數(shù)獲得輸入值。
• 輸出：一個算法有1個或多個輸入。當用函數(shù)描述算法時，輸出多用返回值或引用類型的形參表示。

算法可以沒有輸入但一定要有輸出。

（3）“好”算法的特性：

• 正確性：在有限的運行時間內(nèi)得到正確的結(jié)果。
• 可讀性：便于人們理解，如注釋。
• 健壯性：當輸入非法數(shù)據(jù)時，算法能適當?shù)淖龀龇磻?yīng)或進行處理，而不會產(chǎn)生莫名其妙的輸出結(jié)果。
• 高效性：高效率（花的時間少，時間復雜度低）與低存儲量需求（不費內(nèi)存，空間復雜度低）

（4）時間復雜度O(f(n))

衡量算法效率的方法有事后統(tǒng)計法和事前分析估算法（常用）

問題規(guī)模：不考慮計算機的軟硬件等環(huán)境因素，影響算法時間代價的最主要因素是問題的規(guī)模。

語句頻度：一條語句重復執(zhí)行的次數(shù)

一個算法的執(zhí)行時間大致上等于其所有語句執(zhí)行時間的總和，而語句的執(zhí)行時間則為該條語句的重復執(zhí)行次數(shù)和執(zhí)行一次所需時間的乘積。

常見的時間復雜度按數(shù)量級遞增排隊一次為：

如何計算步驟：

• 找到一個基本操作(最深層循環(huán))
• 分析該基本操作的執(zhí)行次數(shù) x 與問題規(guī)模 n 的關(guān)系 x=f(n)
• x的數(shù)量級 O(x)就是算法時間復雜度 T(n)

例:1：常量階示例

{
   x++;
   s=0;
}

兩條語句頻度均為 1，算法的執(zhí)行時間是一個與問題規(guī)模 n 無關(guān)的常數(shù)，所以算法的時間復雜度為T(n)= O(1)，稱為常量階。

實際上，如果算法的執(zhí)行時間不隨問題規(guī)模n的增長而增長，算法中語句頻度就是某個常數(shù)。即使這個常數(shù)再大，算法的時間復雜度都是O(1)。例如，對上面的程序進行如下改動:

for(i=0;i<10000;i++)
{
   x++;
   s=0;
}

算法的時間復雜度仍然為O(1)。

例2：線性階示例

for(i=0;i

循環(huán)體內(nèi)兩條基本語句的頻度均為n)=n，所以算法的時間復雜度為T)= O)，稱為線性階

例3：平方階示例

x=0；y=0；
for(k=1;k<=n;k++)
x++;
for(i=l;i<=n;i++)
for(j=1;j<=n;j++)
y++;

對循環(huán)語句只需考慮循環(huán)體中語句的執(zhí)行次數(shù)，以上程序段中頻度大的語句是(6)，其頻度為(n)=n^2，所以該算法的時間復雜度為T(n)= O(n^2)，稱為平方階。
例4：立方階示例

x=1;
for(i=l;i<=n;i++)
  for(j=l;j<=i;j++)
    for(k=1;k<=j;k++)
      x++;

則該算法的時間復雜度為T(n)= 0(n^3)，稱為立方階

例5：對數(shù)階示例

for（i=1;i<=n;i=i*2）
{
  x++;
  s=0;
}

算法的時間復雜度為T(n)= O(log2^n)，稱為對數(shù)階。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧


網(wǎng)頁標題：數(shù)據(jù)結(jié)構(gòu)（C語言版）——緒論-創(chuàng)新互聯(lián)
網(wǎng)頁網(wǎng)址：http://m.jiaotiyi.com/article/hegss.html