數(shù)據(jù)結(jié)構(gòu)概要
數(shù)據(jù)結(jié)構(gòu)
1 基本概念
數(shù)據(jù)：描述客觀事物的符號(hào)；能輸入到計(jì)算機(jī)中，能被計(jì)算機(jī)程序處理；比如聲音，圖像，視頻...
數(shù)據(jù)元素：是組成數(shù)據(jù)的有一定意義的基本單位；也被稱為記錄；（比如學(xué)生，老師）
數(shù)據(jù)項(xiàng)：一個(gè)數(shù)據(jù)元素可以有若干個(gè)數(shù)據(jù)項(xiàng)組成；是數(shù)據(jù)項(xiàng)不可分割的最小單位；（比如學(xué)生的姓名，學(xué)號(hào),性別...）
數(shù)據(jù)對(duì)象：數(shù)據(jù)元素具有相同數(shù)量和類型的數(shù)據(jù)項(xiàng)；（比如學(xué)生有姓名，學(xué)號(hào)，性別等相同的數(shù)據(jù)項(xiàng)）
數(shù)據(jù)結(jié)構(gòu)：相互之間存在一種或者多種特定關(guān)系的數(shù)據(jù)元素集合。
數(shù)據(jù)結(jié)構(gòu)按照視點(diǎn)不同可分為：邏輯結(jié)構(gòu)和物理結(jié)構(gòu)
1.1 邏輯結(jié)構(gòu)
邏輯結(jié)構(gòu)是指數(shù)據(jù)對(duì)象中數(shù)據(jù)元素之間的關(guān)系，具體分為以下幾類：
集合結(jié)構(gòu)：數(shù)據(jù)元素除了同屬于一個(gè)集合外，沒有其他關(guān)系
線性結(jié)構(gòu)：數(shù)據(jù)元素之間一對(duì)一關(guān)系
樹形結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對(duì)一或一對(duì)多的層級(jí)關(guān)系
圖形結(jié)構(gòu)：數(shù)據(jù)元素之間是多對(duì)多的關(guān)系
沒有關(guān)系
1.2 物理結(jié)構(gòu)
物理結(jié)構(gòu)(存儲(chǔ)結(jié)構(gòu))是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)形式。
集合結(jié)構(gòu)：數(shù)據(jù)元素除了同屬于一個(gè)集合外，沒有其他關(guān)系（數(shù)據(jù)元素隨機(jī)存放在內(nèi)存里）
順序結(jié)構(gòu)：把數(shù)據(jù)元素存放在地址連續(xù)的存儲(chǔ)單元里；（數(shù)組）（或者說按內(nèi)存編號(hào)順序存放）
鏈?zhǔn)浇Y(jié)構(gòu)：把數(shù)據(jù)元素存放在任意的存儲(chǔ)單元里，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的
邏輯結(jié)構(gòu)是面向問題的，物理結(jié)構(gòu)是面向計(jì)算機(jī)的；我們應(yīng)該注重的就是物理結(jié)構(gòu)，將數(shù)據(jù)及其邏輯關(guān)系存儲(chǔ)到計(jì)算機(jī)內(nèi)存中去 線性,樹形,圖形,鏈?zhǔn)绞菙?shù)據(jù)結(jié)構(gòu)的重點(diǎn)和難點(diǎn)。
數(shù)據(jù)結(jié)構(gòu)解決的是如何高效的將面向問題的邏輯結(jié)構(gòu)存儲(chǔ)在計(jì)算機(jī)中，同時(shí)在需要用到這些邏輯關(guān)系時(shí)將其高效的轉(zhuǎn)換回來。
數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)只有兩種，線性存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，因而數(shù)組也好，鏈表，樹，圖也罷，最終都要轉(zhuǎn)換為線性存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)。另外值得注意的是，數(shù)組天生就是線性存儲(chǔ)，鏈表天生就是鏈?zhǔn)酱鎯?chǔ)。因而問題更進(jìn)一步，就是將樹與圖轉(zhuǎn)換為數(shù)組或者鏈表的存儲(chǔ)方式存儲(chǔ)。
而數(shù)組和鏈表天生與內(nèi)存掛鉤。內(nèi)存呢從本質(zhì)上來說就是一個(gè)數(shù)組，連續(xù)的內(nèi)存單元編號(hào)，內(nèi)存單元直接和數(shù)組對(duì)應(yīng)。所以更進(jìn)一步，就轉(zhuǎn)換為鏈表如何存儲(chǔ)在數(shù)組里。
數(shù)組是這樣的一個(gè)東西，它由兩部分組成：編號(hào)，和編號(hào)對(duì)應(yīng)的空間（可以放東西，可以放東西這一性質(zhì)最神奇的地方在于你可以把一個(gè)編號(hào)放進(jìn)去，這就形成了鏈表）。
現(xiàn)在假設(shè)有一個(gè)編號(hào)為0-14的數(shù)組，需要放進(jìn)去1,2,3,4,5個(gè)數(shù)，請(qǐng)問怎么放？
1,2,3,4,5
(5,1),(3,2),(1,3)(2,4)
放進(jìn)去好放，關(guān)鍵是怎么讀出來，即放進(jìn)去一定要有規(guī)則，而且這個(gè)規(guī)則還要可逆，這樣才能講數(shù)據(jù)完整的讀出來。
2 線性表
線性表是一種線性結(jié)構(gòu)，它是具有相同類型的n(n≥0)個(gè)數(shù)據(jù)元素組成的有限序列。具體分為：
數(shù)組
單向鏈表
雙向鏈表
2.1 數(shù)組
數(shù)組從邏輯上來說是 相同變量的有序集合。
數(shù)組從物理結(jié)構(gòu)上來說是 一片連續(xù)內(nèi)存空間中的存儲(chǔ)元素。
數(shù)組有上界和下界，數(shù)組的元素在上下界內(nèi)是連續(xù)的。
數(shù)組的特點(diǎn)是：數(shù)據(jù)是連續(xù)的；隨機(jī)訪問速度快。
數(shù)組中稍微復(fù)雜一點(diǎn)的是多維數(shù)組和動(dòng)態(tài)數(shù)組。對(duì)于C語言而言，多維數(shù)組本質(zhì)上也是通過一維數(shù)組實(shí)現(xiàn)的。 在C語言中，對(duì)于數(shù)組名與數(shù)組地址，以int a[5]為例，有如下關(guān)系：
數(shù)組名a代表數(shù)組首元素的地址(即 &a[0] == a)
數(shù)組的地址需要取地址符&才能得到(即數(shù)組的地址為 &a)
數(shù)組首元素的地址與數(shù)組地址值相同，但是表示的概念不同(即a與&a在數(shù)值上相同，但是a代表a[0]的地址，但是&a代表數(shù)組在內(nèi)存中的地址
對(duì)于數(shù)組的使用，需要注意如下幾點(diǎn)：
數(shù)組名可以看做一個(gè)常量指針，即決定了在表達(dá)式中數(shù)組名只能作為右值使用
數(shù)組名 "指向" 的是內(nèi)存中數(shù)組首元素的起始地址
數(shù)組名不包含數(shù)組的長(zhǎng)度信息
數(shù)組名作為 sizeof 操作符的參數(shù)(sizeof(array)得到的是整個(gè)數(shù)組在內(nèi)存中占用的空間
數(shù)組名作為 & 運(yùn)算符的參數(shù)得到時(shí)數(shù)組在內(nèi)存中的地址，得到的是一個(gè)數(shù)組指針
2.2 linux內(nèi)核中鏈表的實(shí)現(xiàn)
2.2.1 offsetof
//獲得結(jié)構(gòu)體（TYPE）的變量成員（MEMBER）在此結(jié)構(gòu)體中的偏移量
#define offsetof(TYPE,MEMBER) ((size_t)&((TYPE*)0)->MEMER)
//( (TYPE *)0 )將零轉(zhuǎn)型為TYPE類型指針，即TYPE類型的指針的地址是0
//((TYPE *)0)->MEMBER訪問結(jié)構(gòu)中的數(shù)據(jù)成員
//&( ( (TYPE *)0 )->MEMBER )取出數(shù)據(jù)成員的地址
//由于TYPE的地址是0，這里獲取到的地址就是相對(duì)MEMBER在TYPE中的偏移
// (size_t)(&(((TYPE*)0)->MEMBER))結(jié)果轉(zhuǎn)換類型
//對(duì)于32位系統(tǒng)而言，size_t是unsigned int類型
//對(duì)于64位系統(tǒng)而言，size_t是unsigned long類型
2.2.2 container_of
//根據(jù)"結(jié)構(gòu)體(type)變量"中的"域成員變量(member)的指針(ptr)"來獲取指向整個(gè)結(jié)構(gòu)體變量的指針
#define container_of(ptr, type, member) ({ ? ? ? ? ?\
? ?const typeof( ((type *)0)->member ) *__mptr = (ptr); ? ?\
? ?(type *)( (char *)__mptr - offsetof(type,member) );})
//typeof( ( (type *)0)->member )取出member成員的變量類型。
//const typeof( ((type *)0)->member ) *__mptr = (ptr)定義變量__mptr指針,并將ptr賦值給__mptr
//經(jīng)過這一步，__mptr為member數(shù)據(jù)類型的常量指針，其指向ptr所指向的地址
//(char *)__mptr 將__mptr轉(zhuǎn)換為字符型指針
//offsetof(type,member))就是獲取"member成員"在"結(jié)構(gòu)體type"中的位置偏移
//(char *)__mptr - offsetof(type,member))就是用來獲取"結(jié)構(gòu)體type"的指針的起始地址（為char *型指針）
//(type *)( (char *)__mptr - offsetof(type,member) )
//就是將"char *類型的結(jié)構(gòu)體type的指針"轉(zhuǎn)換為"type *類型的結(jié)構(gòu)體type的指針
2.2.3 鏈表實(shí)現(xiàn)
將雙向鏈表節(jié)點(diǎn)嵌套在其它的結(jié)構(gòu)體中；在遍歷鏈表的時(shí)候，根據(jù)雙鏈表節(jié)點(diǎn)的指針獲取"它所在結(jié)構(gòu)體的指針"，從而再獲取數(shù)據(jù)。
//鏈表結(jié)構(gòu)
struct list_head{
? ?struct list_head *next,*prev;
};
//初始化鏈表
//設(shè)置name節(jié)點(diǎn)的前繼節(jié)點(diǎn)和后繼節(jié)點(diǎn)都是指向name本身
#define LIST_HEAD_INIT(name) {&(name),&(name)}
//新建雙向鏈表表頭name，并設(shè)置name的前繼節(jié)點(diǎn)和后繼節(jié)點(diǎn)都是指向name本身
#define LIST_HEAD(name) struct list_head name=LIST_HEAD_INIT(name)
//將list節(jié)點(diǎn)的前繼節(jié)點(diǎn)和后繼節(jié)點(diǎn)都是指向list本身
static inline void INIT_LIST_HEAD(struct list_head *list){
? ?list->next=list;
? ?list->pre=list;
}
添加節(jié)點(diǎn)
//將new插入到prev和next之間
//以"__"開頭的函數(shù)意味著是內(nèi)核的內(nèi)部接口，外部不應(yīng)該調(diào)用該接口
static inline void __list_add(struct list_head *new,
? ? ? ? ? ? ? ? ?struct list_head *prev,
? ? ? ? ? ? ? ? ?struct list_head *next)
{
? ?next->prev = new;
? ?new->next = next;
? ?new->prev = prev;
? ?prev->next = new;
}
//將new添加到head之后，是new稱為head的后繼節(jié)點(diǎn)(尾插法)
static inline void list_add(struct list_head *new, struct list_head *head)
{
? ?__list_add(new, head, head->next);
}
//將new添加到head之前，即將new添加到雙鏈表的末尾（頭插法）
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
? ?__list_add(new, head->prev, head);
}
刪除節(jié)點(diǎn)
//從雙鏈表中刪除prev和next之間的節(jié)點(diǎn)
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
? ?next->prev = prev;
? ?prev->next = next;
}
//從雙鏈表中刪除entry節(jié)點(diǎn)
static inline void list_del(struct list_head *entry)
{
? ?__list_del(entry->prev, entry->next);
}
//從雙鏈表中刪除entry節(jié)點(diǎn)
static inline void __list_del_entry(struct list_head *entry)
{
? ?__list_del(entry->prev, entry->next);
}
//從雙鏈表中刪除entry節(jié)點(diǎn)，并將entry節(jié)點(diǎn)的前繼節(jié)點(diǎn)和后繼節(jié)點(diǎn)都指向entry本身
static inline void list_del_init(struct list_head *entry)
{
? ?__list_del_entry(entry);
? ?INIT_LIST_HEAD(entry);
}
替換節(jié)點(diǎn)
//用new節(jié)點(diǎn)替換old節(jié)點(diǎn)
static inline void list_replace(struct list_head *old,
? ? ? ? ? ? ? ?struct list_head *new)
{
? ?new->next = old->next;
? ?new->next->prev = new;
? ?new->prev = old->prev;
? ?new->prev->next = new;
}
判斷鏈表是否為空
//通過區(qū)分"表頭的后繼節(jié)點(diǎn)"是不是"表頭本身"來進(jìn)行判斷
static inline int list_empty(const struct list_head *head)
{
? ?return head->next == head;
}
獲取節(jié)點(diǎn)
//獲取指向節(jié)點(diǎn)的指針
#define list_entry(ptr, type, member) \
? ?container_of(ptr, type, member)
遍歷節(jié)點(diǎn)
//通常用于獲取節(jié)點(diǎn)，而不能用到刪除節(jié)點(diǎn)的場(chǎng)景
#define list_for_each(pos, head) \
? ?for (pos = (head)->next; pos != (head); pos = pos->next)
//通常用于刪除節(jié)點(diǎn)的場(chǎng)景
#define list_for_each_safe(pos, n, head) \
? ?for (pos = (head)->next, n = pos->next; pos != (head); \
? ? ? ?pos = n, n = pos->next)
3 二叉樹
3.1 基本概念
樹是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。
結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹的數(shù)目
葉子：度為零的結(jié)點(diǎn)
分支結(jié)點(diǎn)：度不為零的結(jié)點(diǎn)
樹的度：樹中結(jié)點(diǎn)的最大的度
層次：根結(jié)點(diǎn)的層次為1，其余結(jié)點(diǎn)的層次等于該結(jié)點(diǎn)的雙親結(jié)點(diǎn)的層次加1
樹的高度：樹中結(jié)點(diǎn)的最大層次
無序樹：如果樹中結(jié)點(diǎn)的各子樹之間的次序是不重要的，可以交換位置
有序樹：如果樹中結(jié)點(diǎn)的各子樹之間的次序是重要的, 不可以交換位置
森林：0個(gè)或多個(gè)不相交的樹組成。對(duì)森林加上一個(gè)根，森林即成為樹；刪去根，樹即成為森林
一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹，一共有2n個(gè)指針域，其中只有n-1個(gè)用來指向節(jié)點(diǎn)的左右孩子，其余的n+1個(gè)指針為空。二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。它有五種基本形態(tài)：
空集
根和空的左右子樹
根和左子樹
根和右子樹
根和左右子樹
3.2 二叉樹的性質(zhì)
第i層上的節(jié)點(diǎn)數(shù)目最多為2^i-1(i>0)
深度為k的二叉樹至多有2^k-1個(gè)節(jié)點(diǎn)
包含n個(gè)結(jié)點(diǎn)的二叉樹的高度至少為log2 (n+1)
在任意一棵二叉樹中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1
