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

1.數(shù)據(jù)結(jié)構(gòu)與算法相關(guān)術(shù)語(yǔ)

• 數(shù)據(jù): 程序的操作對(duì)象,用于描述客觀事物。

  • 可以輸入到計(jì)算機(jī)
  • 可以被計(jì)算機(jī)處理

• 數(shù)據(jù)項(xiàng): 一個(gè)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)組成。

//聲明一個(gè)結(jié)構(gòu)體類(lèi)型
struct Doctor {     //一種數(shù)據(jù)結(jié)構(gòu)
    char *name;     //數(shù)據(jù)項(xiàng)--名字
    char *title;    //數(shù)據(jù)項(xiàng)--職稱
    int  age;       //數(shù)據(jù)項(xiàng)--年齡
};

struct Doctor t1;     //數(shù)據(jù)元素;
struct Doctor tArray[10]; //數(shù)據(jù)對(duì)象;

• 數(shù)據(jù)元素: 組成數(shù)據(jù)的對(duì)象的基本單位。
• 數(shù)據(jù)對(duì)象: 性質(zhì)相同的數(shù)據(jù)元素的集合(類(lèi)似于數(shù)組)。
• 結(jié)構(gòu): 數(shù)據(jù)元素之間不是獨(dú)立的,存在特定的關(guān)系.這些關(guān)系即是結(jié)構(gòu)。
• 數(shù)據(jù)結(jié)構(gòu):指的數(shù)據(jù)對(duì)象中的數(shù)據(jù)元素之間的關(guān)系。

2.數(shù)據(jù)結(jié)構(gòu)分類(lèi)

• 邏輯結(jié)構(gòu)
  • 集合結(jié)構(gòu)
    集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一個(gè)集合外，它們之間沒(méi)有其他關(guān)系。各個(gè)數(shù)據(jù)元素是"平等"的。
  • 線性結(jié)構(gòu)
    線性結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對(duì)一的關(guān)系。
    常用的線性結(jié)構(gòu)有：線性表、棧、隊(duì)列、雙隊(duì)列、數(shù)組、串。
  • 樹(shù)形結(jié)構(gòu)
    樹(shù)型結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一種一對(duì)多的層次關(guān)系。
    常見(jiàn)的樹(shù)形結(jié)構(gòu)：二叉樹(shù)、B樹(shù)、哈夫曼樹(shù)、紅黑樹(shù)等。
  • 圖形結(jié)構(gòu)
    圖形結(jié)構(gòu)的數(shù)據(jù)元素是多對(duì)多的關(guān)系。
    常見(jiàn)的圖形結(jié)構(gòu)：鄰近矩陣、鄰接表。
• 物理結(jié)構(gòu)
  
  物理結(jié)構(gòu)：又稱“存儲(chǔ)結(jié)構(gòu)”，指的是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)的存儲(chǔ)形式。
  
  數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)應(yīng)該正確反映數(shù)據(jù)元素之間的邏輯關(guān)系。如何存儲(chǔ)數(shù)據(jù)元素之間的邏輯關(guān)系，是實(shí)現(xiàn)物理結(jié)構(gòu)的重點(diǎn)和難點(diǎn)。
  • 順序存儲(chǔ)結(jié)構(gòu)
    把數(shù)據(jù)元素放在地址連續(xù)的存儲(chǔ)單元里，其數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系是一致的。
  • 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
    把數(shù)據(jù)元素放在任意的存儲(chǔ)單元里，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。

數(shù)據(jù)元素的存儲(chǔ)關(guān)系并不能直接反映邏輯關(guān)系，因此需要用一個(gè)指針存放數(shù)據(jù)元素的地址，通過(guò)地址找到相關(guān)關(guān)聯(lián)數(shù)據(jù)元素的位置。

算法

• 算法: 解決特定問(wèn)題求解步驟的描述,在計(jì)算機(jī)中表現(xiàn)為指令的有限序列,并且每條指令表示一個(gè)或多個(gè)操作。
• 算法特性
  • 輸?輸出: 輸入提供已知條件，輸出產(chǎn)生結(jié)果。
  • 有窮性: 執(zhí)行有限的步驟之后，會(huì)自動(dòng)結(jié)束。不會(huì)死循環(huán)。
  • 確定性: 相同輸入執(zhí)行后，只有對(duì)應(yīng)唯一的結(jié)果，不能有二義性。
  • 可?性: 每一步都是可行的。每一步都能通過(guò)有限次數(shù)完成。
• 算法設(shè)計(jì)要求
  • 正確性: 能夠得到正確答案。錯(cuò)誤答案對(duì)于解決問(wèn)題是沒(méi)有意義的。
  • 可讀性: 能夠在有限的時(shí)間內(nèi)讓人看出算法邏輯。
  • 健壯性: 能對(duì)輸入數(shù)據(jù)的不合法的情況做出合適的處理。
  • 時(shí)間效率高和存儲(chǔ)量低: 花最少的時(shí)間，用最少的存儲(chǔ)空間，得到相同的結(jié)果。
• 復(fù)雜度
  • 時(shí)間復(fù)雜度: 算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定性描述該算法的運(yùn)行時(shí)間。這是一個(gè)代表算法輸入值的字符串的長(zhǎng)度的函數(shù)。時(shí)間復(fù)雜度常用大O符號(hào)表述，不包括這個(gè)函數(shù)的低階項(xiàng)和首項(xiàng)系數(shù)。使用這種方式時(shí)，時(shí)間復(fù)雜度可被稱為是漸近的，亦即考察輸入值大小趨近無(wú)窮時(shí)的情況。

復(fù)雜度排序

O(1) < O(log n) < O(n) < O(nlog n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

• 空間復(fù)雜度: 通過(guò)計(jì)算算法所需的存儲(chǔ)空間實(shí)現(xiàn)，算法空間復(fù)雜度的計(jì)算公式記做：，其中，為問(wèn)題的規(guī)模，為語(yǔ)句關(guān)于所占存儲(chǔ)空間的函數(shù)。

除了需要寄存本身所用的指令、常數(shù)、變量和輸入數(shù)據(jù)外，還需要一些對(duì)數(shù)據(jù)進(jìn)行操作的輔助存儲(chǔ)空間。
考量空間復(fù)雜度是，主要考慮算法執(zhí)行時(shí)所需要的輔助空間。