數(shù)據(jù)結構個人筆記總結

1、_- 數(shù)據(jù)結構個人筆記總結王小龍Good luck Believe yourselfJust go 數(shù)據(jù)結構部分一、數(shù)據(jù)結構的基本概念1.邏輯結構1)集合結構(集)：結構中的元素除了同屬一個集之外，沒有任何聯(lián)系。2)線性結構(表)：結構中的元素具有一對一的前后關系。3)樹型結構(樹)：結構中的元素具有一對多的父子關系。4)網(wǎng)狀結構(圖)：結構中的元素具有多對多的交叉映射關系。2.物理結構1)順序結構(數(shù)組)：結構中的元素存放在一段連續(xù)的地址空間中。隨機訪問方便，空間利用率低，插入刪除不便。2)鏈式結構(鏈式)：結構中的元素存放在彼此獨立的地址空間中，每個獨立的地址空間被稱為節(jié)點，節(jié)點除了保存數(shù)

2、據(jù)以外，還保存另外一個或幾個相關節(jié)點的地址。空間利用率高，插入刪除方便，隨機訪問不便。3.邏輯結構和物理結構的關系 表 樹 圖順序 數(shù)組 順序樹 復 鏈式 鏈表 鏈式樹 合二、數(shù)據(jù)結構的基本運算1.創(chuàng)建與銷毀2.插入與刪除3.獲取與修改4.排序與查找三、堆棧1.基本特征：后進先出2.基本操作：壓入(push)，彈出(pop)3.實現(xiàn)要點：初始化空間，棧頂指針，判空判滿。12341*93+2*92+3*91+4*90 - 4123 - 312 - 21 - 1例子1：基于順序表的堆棧#include using namespace std;/ 基于順序表的堆棧class Stack public

3、:/ 構造過程中分配內(nèi)存Stack (size_t size = 10) :m_array (new intsize), m_size (size),m_top (0) / 析構過程中釋放內(nèi)存Stack (void) if (m_array) delete m_array;m_array = 0;/ 壓入 要判斷是否滿了void push (int data) if (full () /如果返回為真，則滿了throw OverFlow (); /拋出異常m_arraym_top+ = data; /壓入元素，用后+，因為先在棧頂?shù)奈恢脡喝朐兀趯ｍ斏弦?，等待新的元素壓? 彈出 要判斷是否

4、為空int pop (void) /if (empty () /如果返回為真，則為空throw UnderFlow (); /拋出異常return m_array-m_top; /用前-，因為要先將棧頂下降一，在彈出/ 判滿bool full (void) const return m_top = m_size; /如果滿了，返回真/ 判空bool empty (void) const return ! m_top; /如果位空，返回為真private:/ 上溢異常class OverFlow : public exception /內(nèi)部類，繼承標準異常const char* what (vo

5、id) const throw () /給what提供一個覆蓋return 堆棧上溢！;/ 下溢異常class UnderFlow : public exception /內(nèi)部類，繼承標準異常const char* what (void) const throw () return 堆棧下溢！;int* m_array; / 數(shù)組size_t m_size; / 容量size_t m_top; / 棧頂;void printb (unsigned int numb, int base) /堆棧的產(chǎn)生與使用的順序是相反的。 Stack stack (256);do stack.push (num

6、b % base); /進行求余得到?jīng)]以為的數(shù)字，不過順序相反while (numb /= base); /while (! stack.empty () /將棧中的內(nèi)容拿出。因為堆棧是后進先出，所以順序再次顛倒，剛好恢復順序int digit = stack.pop ();if (digit 10)cout digit;elsecout char (digit - 10 + A); /強制轉換成char型，小于十的直接用上一行的代碼打印，大于十的轉換位a，b，c，d，e，f 打印cout endl;int main (void) try Stack stack;for (int i = 0;

7、 ! stack.full (); +i) /壓入元素，直到棧滿stack.push (i);/stack.push (0); /這時棧滿，拋出OverFlowwhile (! stack.empty () /判斷是否為空，不空則打印出cout stack.pop () endl;/stack.pop (); /這時?？眨瑨伋鯱nderFlowcatch (exception& ex) cout ex.what () endl; /調(diào)用的是相對應exception類的子類中的what的覆蓋版本return -1;cout 輸入一個整數(shù)： numb;cout 您想看幾進制： base;cout

8、結果：;printb (numb, base);return 0;-例子2： 基于鏈式表的堆棧#include using namespace std;/ 基于鏈式表的堆棧class Stack public:/ 構造過程中初始化為空堆棧Stack (void) : m_top (NULL) / 析構過程中銷毀剩余的節(jié)點Stack (void) for (Node* next; m_top; m_top = next) next = m_top-m_next;delete m_top;/ 壓入void push (int data) /*Node* node = new Node;node-m

9、_data = data;node-m_next = m_top;m_top = node; */m_top = new Node (data, m_top); /和上面的四行實現(xiàn)的是一樣的/ 彈出int pop (void) if (empty () /如果為空，則拋出異常throw UnderFlow ();int data = m_top-m_data; /保存彈出的節(jié)點的值Node* next = m_top-m_next; /保存彈出的節(jié)點后指針指向的地址（也就是保存彈出節(jié)點的后一個節(jié)點的地址）delete m_top;m_top = next; /將棧頂指針移動到彈出節(jié)點的后指針指

10、向的那個節(jié)點（也就是將棧頂指針指向彈出節(jié)點的后一個節(jié)點的地址）return data; /返回彈出的元素值/ 判空bool empty (void) const return ! m_top;private:/ 下溢異常/鏈表實現(xiàn)的堆棧不會存在滿的情況。class UnderFlow : public exception /繼承標準異常const char* what (void) const throw () return 堆棧下溢！;/ 節(jié)點class Node public:Node (int data = 0, Node* next = NULL) :m_data (data), m_

11、next (next) int m_data; / 數(shù)據(jù)Node* m_next; / 后指針;Node* m_top; / 棧頂;int main (void) try Stack stack;for (int i = 0; i 10; +i)stack.push (i);while (! stack.empty ()cout stack.pop () endl;/stack.pop ();catch (exception& ex) cout ex.what () endl;return -1;return 0;-四、隊列1.基本特征：先進先出，F(xiàn)IFO2.基本操作：壓入(push)、彈出(

12、pop)3.實現(xiàn)要點：初始化空間，從前端(front)彈出，從后端(rear)壓入，循環(huán)使用，判空判滿思考：用堆棧實現(xiàn)隊列。例子1：基于順序表的隊列#include using namespace std;/ 基于順序表的隊列class Queue public:/ 構造過程中分配內(nèi)存Queue (size_t size = 5) :m_array (new intsize), m_size (size),m_rear (0), m_front (0), m_count (0) / 析構過程中釋放內(nèi)存Queue (void) if (m_array) delete m_array;m_arra

13、y = NULL;/ 壓入void push (int data) if (full () /判斷是否，滿了throw OverFlow ();if (m_rear = m_size) m_rear = 0; /如果后端指針指向的位置超過數(shù)組的大小，則循環(huán)利用，從最初的數(shù)組起始位置開始壓入，不用擔心0處是否會有元素，因為前面已經(jīng)判斷是否為滿，既然能執(zhí)行到這，沒有拋出異常，就說明沒有滿，可以在0處壓入+m_count; /壓入一個元素，計數(shù)則加一m_arraym_rear+ = data; /用后+，向數(shù)組中后端指針指向的位置壓入元素，在將后端指針移動到下一個位置/ 彈出int pop (voi

14、d) if (empty () /判斷是否為空throw UnderFlow ();if (m_front = m_size) /如果前段指針指向的位置超過數(shù)組大小，則循環(huán)利用，從數(shù)組的起始位置0處開始彈出m_front = 0; /不用擔心0處是否有元素可彈出，因為前面已經(jīng)判斷過是否為空，既然執(zhí)行到這，說明不為空，沒有拋出異常，則0出異一定有元素可彈出-m_count; /彈出一個元素，技術則減一return m_arraym_front+; /用后+，返回彈出的元素，在將前段指針移動到下一個要彈出的位置/ 判空bool empty (void) const return ! m_count

15、; /如果計數(shù)為0則為空，返回真說明空了/ 判滿bool full (void) const return m_count = m_size; /如果計數(shù)與數(shù)組大小相等，則說明滿了private:/ 上溢異常class OverFlow : public exception const char* what (void) const throw () return 隊列上溢！;/ 下溢異常class UnderFlow : public exception const char* what (void) const throw () return 隊列下溢！;int* m_array; / 數(shù)

16、組size_t m_size; / 容量size_t m_rear; / 后端size_t m_front; / 前端size_t m_count; / 計數(shù);int main (void) try Queue queue;queue.push (10);queue.push (20);queue.push (30);queue.push (40);queue.push (50); /queue.push (60); /會顯示隊列上溢cout queue.pop () endl; / 10 彈出0處 先進先出queue.push (60); /循環(huán)利用，前面已經(jīng)將0處的10彈出，則會將60壓入

17、到0這里cout queue.pop () endl; / 20 彈出1處queue.push (70); / /選還利用，前面將1處的20彈出，則會將70壓入到1這里 /queue.push (80); /會顯示隊列上溢cout queue.pop () endl; / 30 彈出2處cout queue.pop () endl; / 40 彈出3處cout queue.pop () endl; / 50 彈出4處cout queue.pop () endl; / 60 彈出0處cout queue.pop () endl; / 70 彈出1處/queue.pop (); /會顯示隊列下溢c

18、atch (exception& ex) cout ex.what () endl;return -1;return 0;-例子2：基于鏈表的隊列#include using namespace std;/ 基于鏈式表的隊列class Queue public:/ 在構造過程中初始化為空隊列Queue (void) : m_rear (NULL), m_front (NULL) / 在析構過程中銷毀剩余的節(jié)點Queue (void) for (Node* next; m_front; m_front = next) next = m_front-m_next; /將m_front中的后指針指向

19、的下個節(jié)點的地址保存，以備釋放delete m_front; /釋放當前m_front指向的節(jié)點/ 壓入 不需要判斷是否為滿void push (int data) Node* node = new Node (data); /創(chuàng)建一個新的節(jié)點，并初始化，node保存的是新創(chuàng)建的節(jié)點的地址if (m_rear) /如果m_rear不為空m_rear-m_next = node; /則將當前m_rear指向的節(jié)點（原來最后創(chuàng)建的節(jié)點）的后指針指向新建的節(jié)點elsem_front = node; /如果rear為空，說明這是第一個節(jié)點，則讓前前端front指針指向它m_rear = node; /

20、讓rear指針指向新建的節(jié)點/ 彈出int pop (void) if (empty () /判斷是否為空throw UnderFlow ();int data = m_front-m_data; /保存要彈出的節(jié)點的數(shù)據(jù)Node* next = m_front-m_next; /保存要彈出的節(jié)點的后指針指向的下個節(jié)點地址delete m_front; /釋放當前front指針指向的節(jié)點if (! (m_front = next) /將front指針指向下一個節(jié)點，如果為空，則將rear也置為空m_rear = NULL;return data; /返回彈出節(jié)點中保存的數(shù)據(jù)/ 判空bool e

21、mpty (void) const return ! m_front & ! m_rear;private:/ 下溢異常class UnderFlow : public exception const char* what (void) const throw () return 隊列下溢！;/ 節(jié)點class Node public:Node (int data = 0, Node* next = NULL) :m_data (data), m_next (next) int m_data; / 數(shù)據(jù)Node* m_next; / 后指針;Node* m_rear; / 后端Node* m_

22、front; / 前端;int main (void) try Queue queue;for (int i = 0; i 10; +i)queue.push (i);while (! queue.empty ()cout queue.pop () endl; /Node* catch (exception& ex) cout ex.what () endl;return -1;return 0;-例子3：基于堆棧的隊列頭文件：#ifndef _LSTACK_H#define _LSTACK_H#include using namespace std;/ 基于鏈式表的堆棧class Stack

23、 public:/ 構造過程中初始化為空堆棧Stack (void) : m_top (NULL) / 析構過程中銷毀剩余的節(jié)點Stack (void) for (Node* next; m_top; m_top = next) next = m_top-m_next;delete m_top;/ 壓入void push (int data) /*Node* node = new Node;node-m_data = data;node-m_next = m_top;m_top = node;*/m_top = new Node (data, m_top);/ 彈出int pop (void)

24、 if (empty ()throw UnderFlow ();int data = m_top-m_data;Node* next = m_top-m_next;delete m_top;m_top = next;return data;/ 判空bool empty (void) const return ! m_top;private:/ 下溢異常class UnderFlow : public exception const char* what (void) const throw () return 堆棧下溢！;/ 節(jié)點class Node public:Node (int data

25、 = 0, Node* next = NULL) :m_data (data), m_next (next) int m_data; / 數(shù)據(jù)Node* m_next; / 后指針;Node* m_top; / 棧頂;#endif / _LSTACK_H-源文件：#include #include lstack.husing namespace std;/ 基于堆棧的隊列 / 想將元素壓入到m_i棧中，再將元素彈出，此時壓入元素到m_i中與從m_i中彈出元素順序相反，先進后出，在將彈出的元素壓入m_o棧中，再彈出元素，此時也是壓入元素到m_o中與從m_o中彈出元素的順序相反，但是壓入元素到m_

26、i的順序和從m_o中彈出元素的順序相同，兩個?？梢詫崿F(xiàn)隊列，符合隊列先進先出的特點。class Queue public:/ 壓入void push (int data) m_i.push (data);/直接調(diào)用堆棧的壓入，/ 彈出int pop (void) if (m_o.empty () /判斷m_o是否為空if (m_i.empty () /判斷m_i是否為空throw underflow_error(隊列下溢！);while (! m_i.empty () /直到輸入棧為空m_o.push (m_i.pop (); /先從m_i里彈出，然后將彈出的再壓入m_o里return m_o

27、.pop (); /彈出m_o棧中的元素，彈出的順序和m_i壓入元素的順序相同/ 判空bool empty (void) const return m_i.empty () & m_o.empty ();private:Stack m_i; / 輸入棧Stack m_o; / 輸出棧;int main (void) try Queue queue;for (int i = 0; i 10; +i)queue.push (i);cout queue.pop () endl; / 0cout queue.pop () endl; / 1cout queue.pop () endl; / 2cout

28、 queue.pop () endl; / 3cout queue.pop () endl; / 4queue.push (10);queue.push (11);queue.push (12);while (! queue.empty ()cout queue.pop () endl;catch (exception& ex) cout ex.what () endl;return -1;return 0;-五、鏈表1.基本特征：內(nèi)存中不連續(xù)的節(jié)點序列，彼此之間通過指針相互關聯(lián)，前指針(prev)指向前節(jié)點，后指針(next)指向后節(jié)點。2.基本操作：追加、插入、刪除、遍歷3.實現(xiàn)要點：vo

29、id 講故事 (void) 從前有座山; 山里有個廟; 廟里有個老和尚; if (老和尚圓寂了) return; 講故事 ();例子：雙向鏈表#include #include using namespace std;/ 雙向線性鏈表class List public:/ 構造過程中初始化為空鏈表List (void) : m_head (NULL), m_tail (NULL) / 析構過程中銷毀剩余的節(jié)點List (void) for (Node* next; m_head; m_head = next) next = m_head-m_next;delete m_head;/ 追加voi

30、d append (int data) m_tail = new Node (data, m_tail); /將新加的節(jié)點的前指針指向原來的尾節(jié)點，后節(jié)點指向空（因為是插在最后位置）。并將鏈表的尾指針指向現(xiàn)在新加的節(jié)點。if (m_tail-m_prev) /如過鏈表的尾指針指向的節(jié)點的前面有節(jié)點m_tail-m_prev-m_next = m_tail; /則尾指針指向的節(jié)點的前一個節(jié)點的后指針指向尾指針指向的節(jié)點。elsem_head = m_tail; /如果為空，說明新建節(jié)點是第一個節(jié)點，則讓鏈表的頭指針指向該新建節(jié)點/ 插入void insert (size_t pos, int d

31、ata) for (Node* find = m_head; find;find = find-m_next)if (pos- = 0) /要插到find節(jié)點的前方Node* node = new Node (data,find-m_prev, find); /新建一個節(jié)點，新建節(jié)點的前指針指向find節(jié)點的前一個節(jié)點，新建節(jié)點的后指針指向find節(jié)點if (node-m_prev) /判斷新建的節(jié)點的前指針指向是否為空node-m_prev-m_next = node; /如果不為空，則新建節(jié)點的前指針指向的節(jié)點的后指針指向新建節(jié)點。elsem_head = node; /如果為空，說明新建

32、節(jié)點是第一個節(jié)點，則將頭指針指向新建節(jié)點node-m_next-m_prev = node; /將新建節(jié)點后指針指向的節(jié)點的前節(jié)點指向新建節(jié)點return;throw out_of_range (鏈表越界！); /執(zhí)行到這，說明沒有找到find，說明給的位置越界了/ 刪除void erase (size_t pos) for (Node* find = m_head; find;find = find-m_next)if (pos- = 0) if (find-m_prev) /判斷要刪除的節(jié)點的前面是否有節(jié)點find-m_prev-m_next = find-m_next; /如果有，要刪除

33、的節(jié)點的前一個節(jié)點的后指針指向要刪除的節(jié)點的后一個節(jié)點elsem_head = find-m_next; /如果沒有，說明要刪除的節(jié)點是第一個節(jié)點，則將鏈表的頭指針指向要刪除的節(jié)點的后一個節(jié)點if (find-m_next) /判斷要刪除的節(jié)點的后面是否有節(jié)點find-m_next-m_prev =find-m_prev; /如果有，則將要刪除的節(jié)點的后一個節(jié)點的前指針指向要刪除的節(jié)點的前一個節(jié)點elsem_tail = find-m_prev; /如果沒有，說明要刪除的是最后一個節(jié)點，則將鏈表的尾指針指向要刪除的節(jié)點的前一個節(jié)點delete find;return;throw out_of_

34、range (鏈表越界！); /執(zhí)行到這，說明沒有找到find，說明給的位置越界了/ 正向遍歷void forward (void) const for (Node* node = m_head; node;node = node-m_next) /從頭到尾掃一遍cout m_data ;cout m_prev) /從尾到頭掃一遍cout m_data ;cout m_next)if (index- = 0) /前-，先返回，再做減，挨個找，知道index變?yōu)?return find-m_data;throw out_of_range (鏈表越界！);const int& operator (

35、size_t index) const return const_cast (*this) index;private:/ 節(jié)點class Node public:Node (int data = 0, Node* prev = NULL,Node* next = NULL) : m_data (data),m_prev (prev), m_next (next) int m_data; / 數(shù)據(jù)Node* m_prev; / 前指針Node* m_next; / 后指針;Node* m_head; / 頭指針，指向鏈表第一個節(jié)點Node* m_tail; / 尾指針，指向鏈表最后一個節(jié)點;i

36、nt main (void) try List list;list.append (10);list.append (30);list.append (50);list.append (60);list.append (80);list.insert (1, 20);list.insert (3, 40);list.insert (6, 70);list.forward ();list.backward ();list.erase (5);list.erase (5);list.erase (5);list.forward ();for (size_t i = 0; i 5; +i)+list

37、i;const List& cr = list;for (size_t i = 0; i 5; +i)cout /*+*/cri ;cout endl;catch (exception& ex) cout ex.what () endl;return -1; return 0; 六、二叉樹1.基本特征 1)樹型結構的最簡模型，每個節(jié)點最多有兩個子節(jié)點。 2)單根。除根節(jié)點外每個節(jié)點有且僅有一個父節(jié)點，整棵樹只有一個根節(jié)點。 3)遞歸結構，用遞歸處理二叉樹問題可以簡化算法。2.基本操作 1)生成 2)遍歷D-L-R：前序遍歷L-D-R：中序遍歷L-R-D：后序遍歷有序二叉樹(二叉搜索樹)L=D=

38、R50 70 20 60 40 30 10 90 80 50 / /- - 20| 70 / / 10 40 60 90 / / 30 80 / 10中序遍歷：10 20 30 40 50 60 70 80 90例子：#include using namespace std;/ 有序二叉樹(二叉搜索樹)class Tree public:/ 構造過程中初始化為空樹Tree (void) : m_root (NULL), m_size (0) / 析構過程中銷毀剩余節(jié)點Tree (void) clear ();/ 插入數(shù)據(jù)void insert (int data) insert (new No

39、de(data), m_root);/把新建的節(jié)點插入以m_root為樹根的樹中+m_size;/ 刪除第一個匹配數(shù)據(jù)，不存在返回falsebool erase (int data) Node*& node = find (data, m_root);/找到這個節(jié)點，并保存該地址if (node) / 左插右insert (node-m_left, node-m_right);/將要刪除的節(jié)點的左子樹插入到他的右子樹Node* temp = node;/保存要刪除的節(jié)點的地址/ 右提升node = node-m_right;/將要刪除的節(jié)點node的右子樹移動到node的位置delete te

40、mp;/將該節(jié)點刪除，釋放-m_size;/刪除一個則總數(shù)減一return true;/如果找到要刪除的數(shù)據(jù)，則返回truereturn false;/如果沒有找到要刪除的數(shù)據(jù)/ 刪除所有匹配數(shù)據(jù)void remove (int data) while (erase (data); /因為找不到要刪除的數(shù)據(jù)erase會返回false，所以會執(zhí)行到?jīng)]有該數(shù)據(jù)為止/ 清空樹void clear (void) clear (m_root);/m_size = 0;/大小清零/ 將所有的_old替換為_newvoid update (int _old, int _new) while (erase (

41、_old) /成功刪除一個old的同時插入一個new，知道沒有old，erase會返回false跳出while。insert (_new);/ 判斷data是否存在bool find (int data) return find (data, m_root) != NULL;/如果有該數(shù)據(jù)，則它的指向不為空，可以以此作為判斷/ 中序遍歷void travel (void) travel (m_root);cout m_data m_data)/如果這個新建的節(jié)點的數(shù)據(jù)比樹根的數(shù)據(jù)小，則插在樹根的左面，否則插在右面insert (node, tree-m_left);/一直插入，直到左面沒有比他

42、大的數(shù)據(jù)elseinsert (node, tree-m_right);/一直插入，直到右面沒有比他小的數(shù)據(jù)/ 返回子樹tree中值與data相匹配的節(jié)點的父節(jié)點中/ 指向該節(jié)點的成員變量的別名Node*& find (int data, Node*& tree) /在tree中查找dataif (! tree)return tree;/如果該樹為空。則返回NULLelseif (data = tree-m_data)/如果該節(jié)點的數(shù)據(jù)與要找的數(shù)據(jù)匹配return tree;/執(zhí)行到這時，該函數(shù)的參數(shù)是tree-left或者tree-ringht,則返回指向這個父節(jié)點的別名treeelseif (data m_data)return find (data, tree-m_left);/如果該節(jié)點大于查找數(shù)據(jù)，則繼續(xù)在這個樹根的左子樹中繼續(xù)查找elsereturn find (data, tree-m_right);/如果該節(jié)點小于查找數(shù)據(jù)，則繼續(xù)在這個樹根的右子樹中繼續(xù)查找void clear (Node*& tree) if (tree)