数据结构个人笔记总结

《数据结构个人笔记总结》由会员分享，可在线阅读，更多相关《数据结构个人笔记总结（62页珍藏版）》请在装配图网上搜索。

1、精品文档，仅供学习与交流，如有侵权请联系网站删除_- 数据结构个人笔记总结王小龙Good luck Believe yourselfJust go【精品文档】第 61 页 数据结构部分一、数据结构的基本概念1.逻辑结构1)集合结构(集)：结构中的元素除了同属一个集之外，没有任何联系。2)线性结构(表)：结构中的元素具有一对一的前后关系。3)树型结构(树)：结构中的元素具有一对多的父子关系。4)网状结构(图)：结构中的元素具有多对多的交叉映射关系。2.物理结构1)顺序结构(数组)：结构中的元素存放在一段连续的地址空间中。随机访问方便，空间利用率低，插入删除不便。2)链式结构(链式)：结构中的元素

2、存放在彼此独立的地址空间中，每个独立的地址空间被称为节点，节点除了保存数据以外，还保存另外一个或几个相关节点的地址。空间利用率高，插入删除方便，随机访问不便。3.逻辑结构和物理结构的关系 表 树 图顺序 数组 顺序树 复 链式 链表 链式树 合二、数据结构的基本运算1.创建与销毁2.插入与删除3.获取与修改4.排序与查找三、堆栈1.基本特征：后进先出2.基本操作：压入(push)，弹出(pop)3.实现要点：初始化空间，栈顶指针，判空判满。12341*93+2*92+3*91+4*90 - 4123 - 312 - 21 - 1例子1：基于顺序表的堆栈#include using namesp

3、ace std;/ 基于顺序表的堆栈class Stack public:/ 构造过程中分配内存Stack (size_t size = 10) :m_array (new intsize), m_size (size),m_top (0) / 析构过程中释放内存Stack (void) if (m_array) delete m_array;m_array = 0;/ 压入 要判断是否满了void push (int data) if (full () /如果返回为真，则满了throw OverFlow (); /抛出异常m_arraym_top+ = data; /压入元素，用后+，因为先

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 excep

5、tion /内部类，继承标准异常const char* what (void) const throw () /给what提供一个覆盖return 堆栈上溢！;/ 下溢异常class UnderFlow : public exception /内部类，继承标准异常const char* what (void) const throw () return 堆栈下溢！;int* m_array; / 数组size_t m_size; / 容量size_t m_top; / 栈顶void printb (unsigned int numb, int base) /堆栈的产生与使用的顺序是相反的。 S

6、tack stack (256);do stack.push (numb % base); /进行求余得到没以为的数字，不过顺序相反while (numb /= base); /while (! stack.empty () /将栈中的内容拿出。因为堆栈是后进先出，所以顺序再次颠倒，刚好恢复顺序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 (vo

7、id) try Stack stack;for (int i = 0; ! stack.full (); +i) /压入元素，直到栈满stack.push (i);/stack.push (0); /这时栈满，抛出OverFlowwhile (! stack.empty () /判断是否为空，不空则打印出cout stack.pop () endl;/stack.pop (); /这时栈空，抛出UnderFlowcatch (exception& ex) cout ex.what () endl; /调用的是相对应exception类的子类中的what的覆盖版本return -1;cout 输

8、入一个整数： numb;cout 您想看几进制： base;cout 结果：;printb (numb, base);return 0;例子2： 基于链式表的堆栈#include using namespace std;/ 基于链式表的堆栈class Stack public:/ 构造过程中初始化为空堆栈Stack (void) : m_top (NULL) / 析构过程中销毁剩余的节点Stack (void) for (Node* next; m_top; m_top = next) next = m_top-m_next;delete m_top;/ 压入void push (int da

9、ta) 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) if (empty () /如果为空，则抛出异常throw UnderFlow ();int data = m_top-m_data; /保存弹出的节点的值Node* next = m_top-m_next; /保存弹出的节点后指针指向的地址（也就是保存弹出节点的后一个节点的地址）delete m_top;

10、m_top = next; /将栈顶指针移动到弹出节点的后指针指向的那个节点（也就是将栈顶指针指向弹出节点的后一个节点的地址）return data; /返回弹出的元素值/ 判空bool empty (void) const return ! m_top;private:/ 下溢异常/链表实现的堆栈不会存在满的情况。class UnderFlow : public exception /继承标准异常const char* what (void) const throw () return 堆栈下溢！;/ 节点class Node public:Node (int data = 0, Node*

11、 next = NULL) :m_data (data), m_next (next) int m_data; / 数据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.基本特征

12、：先进先出，FIFO2.基本操作：压入(push)、弹出(pop)3.实现要点：初始化空间，从前端(front)弹出，从后端(rear)压入，循环使用，判空判满思考：用堆栈实现队列。例子1：基于顺序表的队列#include using namespace std;/ 基于顺序表的队列class Queue public:/ 构造过程中分配内存Queue (size_t size = 5) :m_array (new intsize), m_size (size),m_rear (0), m_front (0), m_count (0) / 析构过程中释放内存Queue (void) if (m

13、_array) delete m_array;m_array = NULL;/ 压入void push (int data) if (full () /判断是否，满了throw OverFlow ();if (m_rear = m_size) m_rear = 0; /如果后端指针指向的位置超过数组的大小，则循环利用，从最初的数组起始位置开始压入，不用担心0处是否会有元素，因为前面已经判断是否为满，既然能执行到这，没有抛出异常，就说明没有满，可以在0处压入+m_count; /压入一个元素，计数则加一m_arraym_rear+ = data; /用后+，向数组中后端指针指向的位置压入元素，在

14、将后端指针移动到下一个位置/ 弹出int pop (void) if (empty () /判断是否为空throw UnderFlow ();if (m_front = m_size) /如果前段指针指向的位置超过数组大小，则循环利用，从数组的起始位置0处开始弹出m_front = 0; /不用担心0处是否有元素可弹出，因为前面已经判断过是否为空，既然执行到这，说明不为空，没有抛出异常，则0出异一定有元素可弹出-m_count; /弹出一个元素，技术则减一return m_arraym_front+; /用后+，返回弹出的元素，在将前段指针移动到下一个要弹出的位置/ 判空bool empty

15、(void) const return ! m_count; /如果计数为0则为空，返回真说明空了/ 判满bool full (void) const return m_count = m_size; /如果计数与数组大小相等，则说明满了private:/ 上溢异常class OverFlow : public exception const char* what (void) const throw () return 队列上溢！;/ 下溢异常class UnderFlow : public exception const char* what (void) const throw () r

16、eturn 队列下溢！;int* m_array; / 数组size_t m_size; / 容量size_t m_rear; / 后端size_t m_front; / 前端size_t m_count; / 计数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)

17、; /循环利用，前面已经将0处的10弹出，则会将60压入到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

18、弹出1处/queue.pop (); /会显示队列下溢catch (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) / 在析构过程中销毁剩余的节点Queue (void) for (Node* next; m_front; m_front = next) next = m_fro

19、nt-m_next; /将m_front中的后指针指向的下个节点的地址保存，以备释放delete m_front; /释放当前m_front指向的节点/ 压入 不需要判断是否为满void push (int data) Node* node = new Node (data); /创建一个新的节点，并初始化，node保存的是新创建的节点的地址if (m_rear) /如果m_rear不为空m_rear-m_next = node; /则将当前m_rear指向的节点（原来最后创建的节点）的后指针指向新建的节点elsem_front = node; /如果rear为空，说明这是第一个节点，则让前前

20、端front指针指向它m_rear = node; /让rear指针指向新建的节点/ 弹出int pop (void) if (empty () /判断是否为空throw UnderFlow ();int data = m_front-m_data; /保存要弹出的节点的数据Node* next = m_front-m_next; /保存要弹出的节点的后指针指向的下个节点地址delete m_front; /释放当前front指针指向的节点if (! (m_front = next) /将front指针指向下一个节点，如果为空，则将rear也置为空m_rear = NULL;return da

21、ta; /返回弹出节点中保存的数据/ 判空bool empty (void) const return ! m_front & ! m_rear;private:/ 下溢异常class UnderFlow : public exception const char* what (void) const throw () return 队列下溢！;/ 节点class Node public:Node (int data = 0, Node* next = NULL) :m_data (data), m_next (next) int m_data; / 数据Node* m_next; / 后指针

22、Node* m_rear; / 后端Node* m_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 s

23、td;/ 基于链式表的堆栈class Stack public:/ 构造过程中初始化为空堆栈Stack (void) : m_top (NULL) / 析构过程中销毁剩余的节点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_t

24、op);/ 弹出int pop (void) 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 堆栈下溢！;/ 节点class Node

25、 public:Node (int data = 0, Node* next = NULL) :m_data (data), m_next (next) int m_data; / 数据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中

26、弹出元素的顺序相反，但是压入元素到m_i的顺序和从m_o中弹出元素的顺序相同，两个栈可以实现队列，符合队列先进先出的特点。class Queue public:/ 压入void push (int data) m_i.push (data);/直接调用堆栈的压入，/ 弹出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里弹出，然后将弹

27、出的再压入m_o里return m_o.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.po

28、p () endl; / 2cout 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.基本特征：内存中不连续的节点序列，彼此之间通过指针相互关联，前指针(prev)指向前节点，后指针(next)指向后节点。2.基本操作：追加、

29、插入、删除、遍历3.实现要点：void 讲故事 (void) 从前有座山; 山里有个庙; 庙里有个老和尚; if (老和尚圆寂了) return; 讲故事 ();例子：双向链表#include #include using namespace std;/ 双向线性链表class List public:/ 构造过程中初始化为空链表List (void) : m_head (NULL), m_tail (NULL) / 析构过程中销毁剩余的节点List (void) for (Node* next; m_head; m_head = next) next = m_head-m_next;dele

30、te m_head;/ 追加void append (int data) m_tail = new Node (data, m_tail); /将新加的节点的前指针指向原来的尾节点，后节点指向空（因为是插在最后位置）。并将链表的尾指针指向现在新加的节点。if (m_tail-m_prev) /如过链表的尾指针指向的节点的前面有节点m_tail-m_prev-m_next = m_tail; /则尾指针指向的节点的前一个节点的后指针指向尾指针指向的节点。elsem_head = m_tail; /如果为空，说明新建节点是第一个节点，则让链表的头指针指向该新建节点/ 插入void insert (

31、size_t pos, int data) for (Node* find = m_head; find;find = find-m_next)if (pos- = 0) /要插到find节点的前方Node* node = new Node (data,find-m_prev, find); /新建一个节点，新建节点的前指针指向find节点的前一个节点，新建节点的后指针指向find节点if (node-m_prev) /判断新建的节点的前指针指向是否为空node-m_prev-m_next = node; /如果不为空，则新建节点的前指针指向的节点的后指针指向新建节点。elsem_head =

32、 node; /如果为空，说明新建节点是第一个节点，则将头指针指向新建节点node-m_next-m_prev = node; /将新建节点后指针指向的节点的前节点指向新建节点return;throw out_of_range (链表越界！); /执行到这，说明没有找到find，说明给的位置越界了/ 删除void erase (size_t pos) for (Node* find = m_head; find;find = find-m_next)if (pos- = 0) if (find-m_prev) /判断要删除的节点的前面是否有节点find-m_prev-m_next = find

33、-m_next; /如果有，要删除的节点的前一个节点的后指针指向要删除的节点的后一个节点elsem_head = find-m_next; /如果没有，说明要删除的节点是第一个节点，则将链表的头指针指向要删除的节点的后一个节点if (find-m_next) /判断要删除的节点的后面是否有节点find-m_next-m_prev =find-m_prev; /如果有，则将要删除的节点的后一个节点的前指针指向要删除的节点的前一个节点elsem_tail = find-m_prev; /如果没有，说明要删除的是最后一个节点，则将链表的尾指针指向要删除的节点的前一个节点delete find;ret

34、urn;throw out_of_range (链表越界！); /执行到这，说明没有找到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变为0return find-m_data;throw out_of_range (链表越界！);cons

35、t int& operator (size_t index) const return const_cast (*this) index;private:/ 节点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; / 数据Node* m_prev; / 前指针Node* m_next; / 后指针Node* m_head; / 头指针，指向链表第一个节点Node* m_tail; /

36、尾指针，指向链表最后一个节点int 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

37、; i 5; +i)+listi;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)树型结构的最简模型，每个节点最多有两个子节点。 2)单根。除根节点外每个节点有且仅有一个父节点，整棵树只有一个根节点。 3)递归结构，用递归处理二叉树问题可以简化算法。2.基本操作 1)生成 2)遍历D-L-R：前序遍历L-D-R：中序遍历L-R-D：后序遍历有

38、序二叉树(二叉搜索树)L=D=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) / 析构过程中销毁剩余节点Tree (void) clear ();/ 插入数据void insert (int data) insert (new Node

39、(data), m_root);/把新建的节点插入以m_root为树根的树中+m_size;/ 删除第一个匹配数据，不存在返回falsebool erase (int data) Node*& node = find (data, m_root);/找到这个节点，并保存该地址if (node) / 左插右insert (node-m_left, node-m_right);/将要删除的节点的左子树插入到他的右子树Node* temp = node;/保存要删除的节点的地址/ 右提升node = node-m_right;/将要删除的节点node的右子树移动到node的位置delete temp

40、;/将该节点删除，释放-m_size;/删除一个则总数减一return true;/如果找到要删除的数据，则返回truereturn false;/如果没有找到要删除的数据/ 删除所有匹配数据void remove (int data) while (erase (data); /因为找不到要删除的数据erase会返回false，所以会执行到没有该数据为止/ 清空树void clear (void) clear (m_root);/m_size = 0;/大小清零/ 将所有的_old替换为_newvoid update (int _old, int _new) while (erase (_o

41、ld) /成功删除一个old的同时插入一个new，知道没有old，erase会返回false跳出while。insert (_new);/ 判断data是否存在bool find (int data) return find (data, m_root) != NULL;/如果有该数据，则它的指向不为空，可以以此作为判断/ 中序遍历void travel (void) travel (m_root);cout m_data m_data)/如果这个新建的节点的数据比树根的数据小，则插在树根的左面，否则插在右面insert (node, tree-m_left);/一直插入，直到左面没有比他大的

42、数据elseinsert (node, tree-m_right);/一直插入，直到右面没有比他小的数据/ 返回子树tree中值与data相匹配的节点的父节点中/ 指向该节点的成员变量的别名Node*& find (int data, Node*& tree) /在tree中查找dataif (! tree)return tree;/如果该树为空。则返回NULLelseif (data = tree-m_data)/如果该节点的数据与要找的数据匹配return tree;/执行到这时，该函数的参数是tree-left或者tree-ringht,则返回指向这个父节点的别名treeelseif (

43、data m_data)return find (data, tree-m_left);/如果该节点大于查找数据，则继续在这个树根的左子树中继续查找elsereturn find (data, tree-m_right);/如果该节点小于查找数据，则继续在这个树根的右子树中继续查找void clear (Node*& tree) if (tree) /判断是否为空clear (tree-m_left);/删除他的左子树，会一直递归到最左面，然后再层层返回clear (tree-m_right);/删除他的右子树，会一直递归到最右面，然后在层层返回delete tree;/删除该节点，递归到最后

44、，从这里层层开始往回删除tree = NULL;void travel (Node* tree) if (tree) /直到执行到叶子节点，例子：tree-left=null的话tree的left就是叶子节点travel (tree-m_left);/遍历他的左子树，会一直递归到最后，开始层层递归，输出数据，再递归遍历当前右子树，右子树递归到坐后，在开始执行第二次往回层层返回cout m_data m_right);/遍历他的右子树size_t height (Node* tree) if (tree) size_t lh = height (tree-m_left);size_t rh =

45、height (tree-m_right);return (lh rh ? lh : rh) + 1;return 0;Node* m_root; / 树根 类似链表的头节点。size_t m_size; / 大小int main (void) Tree tree;tree.insert (50);tree.insert (70);tree.insert (20);tree.insert (60);tree.insert (40);tree.insert (30);tree.insert (10);tree.insert (90);tree.insert (80);tree.travel ()

46、;cout tree.size () tree.height () endl;tree.erase (70);tree.travel ();tree.insert (70);tree.insert (70);tree.insert (70);tree.travel ();tree.remove (70);tree.travel ();tree.insert (40);tree.insert (40);tree.travel ();tree.update (40, 69);tree.travel ();cout boolalpha tree.find (50) endl;cout tree.fi

47、nd (55) endl;tree.clear ();tree.travel ();return 0;算法部分程序设计=数据结构+算法+设计方法学数值算法：微积分、方程组、有限元分析等工程计算。非数值算法：查找、排序、决策、调度系统编程。一、冒泡排序1.算法1)比较相邻的元素，如果第一个比第二个大，就交换它们俩；2)对每一对相邻的元素做同样的工作，从开始的第一对到结尾的最后一对，使最后的元素为最大值；3)针对的所有的元素重复以上步骤，除了最后一个；4)持续每次对越来越少的元素重复以上步骤，直到没有元素需要交换为止。2.评价平均时间复杂度：O(N2)稳定对数据的有序性非常敏感例子：/ 冒泡排序v

48、oid bubbleSort (int data, size_t size) for (size_t i = 0; i size - 1; +i) /控制循环多少次bool ordered = true;for (size_t j = 0; j size - 1 - i; +j)if (dataj+1 dataj) int temp = dataj+1;dataj+1 = dataj;dataj = temp;ordered = false;if (ordered)break;二、插入排序1.算法1)从第一个元素开始，该元素可以认为已经有序；2)取出下一个元素，在已经有序的序列中从后向前扫描；

49、3)若该元素大于新元素，则将该元素移到下一个位置；4)若该元素小于等于新元素，则将新元素放在该元素之后；5)重复步骤2)，直到处理完所有元素。2.评价平均时间复杂度：O(N2)稳定对数据的有序性非常敏感因为没有交换，所以赋值的次数比冒泡少，速度比冒泡略快。例子：/ 插入排序void insertSort (int data, size_t size) for (size_t i = 1; i 0 & temp dataj-1; -j)dataj = dataj-1;if (j != i)dataj = temp;三、选择排序1.算法首先在未排序序列中找到最小元素，与该序列的首元素交换，再从剩余

50、未排序元素中继续寻找最小元素，放到有序序列的末尾。以此类推，直到所有元素均排序完毕。2.评价平均时间复杂度：O(N2)稳定对数据的有序性不敏感因为交换的次数少，所有速度比冒泡略快。例子： / 选择排序void selectSort (int data, size_t size) for (size_t i = 0; i size - 1; +i) size_t min = i;for (size_t j = i + 1; j size; +j)if (dataj datamin)min = j;if (min != i) int temp = datai;datai = datamindatamin = temp;四、快速排序1.算法1)从序列中选出一个元素作为基准；2)重排序列，所有比基准小的元素位于基准左侧，比基准大的元素位于基准右侧，和基准相等的元素位于任意一侧，此过程称为分组；3)以递归的方式对小于基准的分组和大于基准的分组分别进行排序。2.评价平均时间复杂度：O(NlogN)不稳定如果每次能够均匀分组速度将是最快的。例子