数据结构 王道2026学习笔记 第一章 绪论 1.1 数据结构的基本概念 概念和术语
数据 数据是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。
数据元素 数据元素是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
数据项 一个数据元素可以由若干个数据项组成，数据项是数据不可分割的最小单位。
数据对象 数据对象是性质相同的数据元素的集合，是数据的子集。
数据类型 数据类型是一个值的集合和定义在此集合上的一组操作的总称。
原子类型：其值不可再分的类型，如整型、浮点型、字符型等。
结构类型：其值可以再分的类型，如整形数组、浮点型数组、结构体、链表、栈、队列等。
抽象数据类型（Abstract Data Type, ADT）：抽象数据类型是指一个数学模型及定义在该模型上的一组操作。
数据结构三要素 1.逻辑结构：数据元素之间的逻辑关系。
2.存储结构：数据元素及其关系在计算机存储器中的表示。
3.数据运算：针对某种逻辑结构在相应存储结构上的操作。
逻辑结构
存储结构
顺序存储: 用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。
链式存储: 用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。
索引存储: 在存储数据元素的同时，还建立附加的索引表，索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）。
散列存储: 散列存储是根据元素的关键字直接计算出该元素的存储地址，因此散列存储不需要建立索引表。
数据运算
包括运算的定义和运算的实现两个部分。
数据运算的定义是针对逻辑的，指出运算的功能
数据运算的实现是针对存储的，指出运算的具体实现方法
1.2 算法 算法的概念 算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
算法具有以下五个特性(了解)：
有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得到相同的输出。
可行性：算法的每一步操作都是可行的，即每一步都能够通过执行有限次数完成。
输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。
算法达到的目标(了解)：
正确性：算法对于合法的输入，能够产生满足要求的输出，对非法输入能够做出相应处理。
可读性：算法应具有良好的可读性，以帮助人们理解。
健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。
高效性：算法应尽量简短，算法的执行时间应尽可能短，算法所需的存储空间应尽量小。
算法效率的度量！！！ 时间复杂度：算法的时间复杂度是指算法执行时间随问题规模n的变化而变化的函数，记作：T(n)=O(f(n))。其中f(n)是问题规模n的某个函数，O是数量级符号。
空间复杂度：算法的空间复杂度是指算法在计算机内执行时所需存储空间的度量，记作：S(n)=O(g(n))。其中g(n)是问题规模n的某个函数，O是数量级符号。
第二章 线性表 2.1 线性表的定义和基本操作 线性表的定义 线性表是具有相同数据类型的n个数据元素的有限序列，其中n(0≤n≤∞)为线性表的长度，当n=0时，线性表是一个空表。a1是表头元素，an是表尾元素。
线性表的特点：
表中元素个数有限。
表中元素具有逻辑上的顺序性，表中元素有其先后次序。
表中元素具有相同的数据类型，每个元素占有相同的存储空间。
表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素本身的特性。
线性表的基本操作
InitList(&L)：初始化表。构造一个空的线性表L，分配内存空间。
Length(L)：求表长。返回线性表L中数据元素的个数。
LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。
GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。
ListInsert(&L,i,e)：插入操作。在表L中的第i个位置插入指定元素e。
ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回其值。
PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。
Empty(L)：判空操作。若L为空表，则返回true，否则返回false。
DestroyList(&L)：销毁操作。销毁线性表，释放线性表L所占用的内存空间。
2.2 线性表的顺序表示和实现 顺序表的定义 线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的数据元素，这种存储方式称为顺序存储或顺序表。
顺序表上基本操作的实现 #include <iostream> #define MaxSize 100 using namespace std;enum error_code {success,overflow,underflow}; template <typename T>class SqList {private : int count; T data[MaxSize]; public : SqList (){ count = 0 ; } error_code listInsert (int i,T x) { if (i<0 ||i>count){ return overflow; } if (count==MaxSize){ return overflow; } for (int j=count; j>i; j--){ data[j] = data[j-1 ]; } data[i] = x; count++; return success; } error_code listDelete (int i,T &x) { if (i<0 ||i>=count){ return underflow; } x = data[i]; for (int j=i;j <count-1 ;j++){ data[j] = data[j+1 ]; } count--; } int listSearch (T x) for (int i=0 ;i<count;i++){ if (data[i]==x){ return i; } } return -1 ; } int listLength () return count; } bool listEmpty () return count==0 ; } void listPrint () for (int i=0 ;i<count;i++){ cout<<data[i]<<" " ; } cout<<endl; } T getElem (int i) { return data[i]; } };
2.3 线性表的链式表示和实现 单链表的定义 单链表是一种线性表的链式存储结构。它由一系列结点（链表中的数据元素）组成，每个结点都由数据域和指针域两部分组成。
单链表的实现 #include <iostream> using namespace std;enum error_code {success,overflow,underflow}; template <typename T>struct Node { T data; Node<T> * next; }; template <typename T>class LinkList {private : Node<T> * head; int listSize; public : LinkList (){ head = new Node<T>; head->next = nullptr ; listSize = 0 ; } int length () return listSize; } Node<T> * getElem (int i) { if (i<0 ||i>listSize-1 ){ return nullptr ; } Node<T> * temp = head->next; for (int j=0 ;j<i;j++){ temp = temp->next; } return temp; } Node<T> * locateElem (T e) { Node<T> * temp = head->next; while (temp!=nullptr &&temp->data!=e){ temp = temp->next; } return temp; } error_code insertElem (int i,T e) { if (i<0 ||i>listSize){ return overflow; } Node<T> * newNode = new Node<T>; newNode->data = e; Node<T> * temp = head; for (int j=0 ;j<i;j++){ temp = temp->next; } newNode->next = temp->next; temp->next = newNode; listSize++; return success; } error_code deleteElem (int i) { if (i<0 ||i>listSize-1 ){ return underflow; } Node<T> * temp = head; for (int j=0 ;j<i;j++){ temp = temp->next; } Node<T> * delNode = temp->next; temp->next = delNode->next; delete delNode; listSize--; return success; } void printList () Node<T> * temp = head->next; while (temp!=nullptr ){ cout<<temp->data<<" " ; temp = temp->next; } cout<<endl; } ~LinkList () { Node<T>* temp; while (head != nullptr ) { temp = head; head = head->next; delete temp; } } }; int main () LinkList<int > list; list.insertElem (0 , 1 ); list.insertElem (1 , 2 ); list.insertElem (2 , 3 ); list.insertElem (3 , 4 ); list.insertElem (4 , 5 ); list.printList (); list.deleteElem (2 ); list.printList (); cout << list.length () << endl; Node<int >* node = list.getElem (2 ); if (node != nullptr ) cout << node->data << endl; Node<int >* target = list.locateElem (3 ); if (target != nullptr ) cout << target->data << endl; return 0 ; }
双链表 单链表如果要访问某个节点的前驱节点，需要从头节点开始遍历，时间复杂度为O(n)。双链表则可以在O(1)时间内访问到前驱节点。
双链表的实现 #include <iostream> using namespace std;enum error_code {success,overflow,underflow}; template <typename T>struct Node { T data; Node<T> * next; Node<T> * prev; }; template <typename T>class LinkList {private : Node<T> * head; int listSize; public : LinkList (){ head = new Node<T>; head->next = nullptr ; head->prev = nullptr ; listSize = 0 ; } int length () return listSize; } Node<T> * getElem (int i) { if (i<0 ||i>listSize-1 ){ return nullptr ; } Node<T> * temp = head->next; for (int j=0 ;j<i;j++){ temp = temp->next; } return temp; } Node<T> * locateElem (T e) { Node<T> * temp = head->next; while (temp!=nullptr &&temp->data!=e){ temp = temp->next; } return temp; } error_code insertElem (int i,T e) { if (i<0 ||i>listSize){ return overflow; } Node<T> * newNode = new Node<T>; newNode->data = e; newNode->next = nullptr ; newNode->prev = nullptr ; Node<T> * temp = head; for (int j=0 ;j<i;j++){ temp = temp->next; } newNode->next = temp->next; if (temp->next != nullptr ) { temp->next->prev = newNode; } newNode->prev = temp; temp->next = newNode; listSize++; return success; } error_code deleteElem (int i) { if (i<0 ||i>listSize-1 ){ return underflow; } Node<T> * temp = head; for (int j=0 ;j<i;j++){ temp = temp->next; } Node<T> * delNode = temp->next; temp->next = delNode->next; if (delNode->next != nullptr ) { delNode->next->prev = temp; } delete delNode; listSize--; return success; } void printList () Node<T> * temp = head->next; while (temp!=nullptr ){ cout<<temp->data<<" " ; temp = temp->next; } cout<<endl; } ~LinkList () { Node<T>* temp; while (head != nullptr ) { temp = head; head = head->next; delete temp; } } }; int main () LinkList<int > list; list.insertElem (0 , 1 ); list.insertElem (1 , 2 ); list.insertElem (2 , 3 ); list.insertElem (3 , 4 ); list.insertElem (4 , 5 ); list.printList (); list.deleteElem (2 ); list.printList (); cout << list.length () << endl; Node<int >* node = list.getElem (2 ); if (node != nullptr ) cout << node->data << endl; Node<int >* target = list.locateElem (3 ); if (target != nullptr ) cout << target->data << endl; return 0 ; }
循环链表 循环链表是一种特殊的链表，它的最后一个节点的指针指向链表的第一个节点，形成一个环。循环链表可以用来解决一些需要循环遍历的问题，例如约瑟夫环问题。
循环单链表与循环双链表的实现与单链表和双链表类似，只是在链表的末尾添加了一个指向头节点的指针，使得链表形成一个环。
静态链表 静态链表是一种特殊的链表，它的节点存储在数组中，而不是在堆内存中。静态链表的大小在创建时就已经确定，不能动态地增加或减少。
第三章 栈、队列和数组 栈 栈的定义和基本操作 只允许在一端进行插入或删除的线性表
当有n个不同的元素入栈的时候，出栈排列有(1/n+1)/C^n_{2n}种
共享栈
一个数组两个栈用，一个用栈底一个用栈顶（好奇怪）
栈的实现（数组实现比较简单，这里采用链栈实现）
链栈的优点在于不存在上溢问题
#include <iostream> using namespace std;enum operation_code {success,overflow,underflow};template <typename T>struct Node { T data; Node<T>* next; }; template <typename T>class LinkStack {private : Node<T> *top; int stackSize; public : LinkStack (){ top = new Node <T>(); top->next = nullptr ; stackSize = 0 ; }; bool isEmpty () return stackSize==0 ; } operation_code push (T data) { Node<T>* newNode = new Node <T>(); newNode->data = data; newNode->next = top->next; top->next = newNode; stackSize++; return success; } operation_code getTop (T &x) { if (!top->next){ return underflow; } x = top->next->data; return success; } operation_code pop (T &x) { if (!top->next){ return underflow; } Node<T>* popNode = top->next; x = popNode->data; top->next = popNode->next; delete popNode; stackSize--; return success; } ~LinkStack (){ T temp; while (!isEmpty ()){ pop (temp); } delete top; top = nullptr ; } }; int main () LinkStack<int > stack; int x; if (stack.pop (x) == underflow) { cout << "1. 空栈弹出失败测试通过" << endl; } stack.push (10 ); stack.getTop (x); cout << "2. 当前栈顶元素（应为10）: " << x << endl; stack.push (20 ); stack.push (30 ); stack.pop (x); cout << "3. 弹出元素（应为30）: " << x << endl; stack.pop (x); cout << "4. 弹出元素（应为20）: " << x << endl; stack.getTop (x); cout << "5. 当前栈顶元素（应为10）: " << x << endl; stack.pop (x); cout << "6. 弹出元素（应为10）: " << x << endl; if (stack.isEmpty ()) { cout << "7. 栈已空测试通过" << endl; } if (stack.getTop (x) == underflow) { cout << "8. 空栈获取栈顶测试通过" << endl; } return 0 ; }
队列 队列的定义 先进先出的受限线性表
顺序存储 这里有一个假溢出的概念
这个时候如果使用rear == front 判断栈满，就会出现假溢出现象
引入循环队列：
还是无法判断队列满不满（rear == front 可能是空，也可能是满）
牺牲一个存储单元
(rear+1) % maxSize == front 满
rear == front 空
(rear - front + MaxSize) % MaxSize 队内元素
增加size属性
size == 0 空
size == maxSize 满
增加tag
出队的时候 将 tag = 0, 入队的时候 将 tag = 1
tag == 0 && rear == front 空
tag == 1 && rear == front 满
循环队列的实现 #include <iostream> using namespace std;#define MaxSize 100 enum operation_code {success,overflow,underflow};template <typename T>class Queue {private : T data[MaxSize]; int size; int front; int rear; public : Queue (){ front = 0 ; rear = 0 ; size = 0 ; } bool isEmpty () return size==0 ; } bool isFull () return size==MaxSize; } operation_code push (T x) { if (isFull ()){ return overflow; } data[rear]= x; rear = (rear + 1 )%MaxSize; size++; return success; } operation_code pop (T &x) { if (isEmpty ()){ return underflow; } x = data[front]; front = (front + 1 )%MaxSize; size--; return success; } }; int main () Queue<int > q; int x; for (int i = 0 ; i < 100 ; ++i) { if (q.push (i) != success) { cout << "队列已满，无法入队元素 " << i << endl; } } operation_code result = q.push (100 ); cout << "满队列入队结果: " << result << " (1 表示overflow)" << endl; while (q.pop (x) == success) { cout << x << " " ; } cout << "\n队列已清空" << endl; result = q.pop (x); cout << "空队列出队结果: " << result << " (2 表示underflow)" << endl; q.push (10 ); q.push (20 ); q.pop (x); cout << "出队元素: " << x << endl; q.pop (x); cout << "出队元素: " << x << endl; return 0 ; }
链式队列 #include <iostream> using namespace std;enum operation_code {success,overflow,underflow};template <typename T>struct Node { T data; Node<T>* next; }; template <typename T>class Queue {private : Node<T>* front; Node<T>* rear; int size; public : Queue (){ front = new Node <T>(); front->next = nullptr ; rear = front; size = 0 ; } bool isEmpty () return size == 0 ; } operation_code push (T x) { Node<T> * newNode = new Node <T>(); newNode->data = x; newNode->next = nullptr ; rear->next = newNode; rear = newNode; size++; return success; } operation_code pop (T &x) { if (isEmpty ()){ return underflow; } Node<T> *tmp = front->next; x = tmp->data; front->next = tmp->next; if (rear == tmp){ rear = front; } delete tmp; size--; return success; } ~Queue (){ while (front != nullptr ) { Node<T>* tmp = front; front = front->next; delete tmp; } } }; int main () Queue<int > q; int val; cout << "空队列出队结果: " << q.pop (val) << " (应返回2 underflow)" << endl; q.push (10 ); q.push (20 ); q.push (30 ); q.pop (val); cout << "第一次出队元素: " << val << " (应输出10)" << endl; q.pop (val); cout << "第二次出队元素: " << val << " (应输出20)" << endl; q.push (40 ); q.pop (val); cout << "第三次出队元素: " << val << " (应输出30)" << endl; q.pop (val); cout << "第四次出队元素: " << val << " (应输出40)" << endl; cout << "空队列出队结果: " << q.pop (val) << " (应返回2 underflow)" << endl; return 0 ; }
双端队列（了解）
栈和队列的应用 看一看书，队列的遍历非常重要！！！
数组（了解） 第五章 树与二叉树 树的定义 树是由n（n≥0）个节点组成的有限集合。当n=0时，称为空树；当n>0时，树由一个根节点和若干棵子树组成。树中的每一个节点都只有一个父节点，除了根节点没有父节点。
任意一个非空树应当满足：
树的这种定义方式称为递归定义。 具有以下特点：
树的基本术语
祖先、子孙、双亲、孩子、兄弟和堂兄弟
节点的层次、深度和高度
节点的度和树的度
分支节点和叶节点
有序树和无序树
路径和路径长度
森林
树的性质(了解)：
树的节点数等于所有节点的度数加1
度为m的树中第i层上至多有m^(i-1)个节点（i≥1）
高度为h的m叉树至多有(m^h-1)/(m-1)个节点
具有n个节点的m叉树的最小高度为logm(n(m-1)+1)
度为m的树中第i层上至多有m^(i-1)个节点（i≥1）
二叉树 二叉树是一种特殊的树，它的每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树可以是有序的，也可以是无序的。在有序二叉树中，左子树上的节点都小于根节点，右子树上的节点都大于根节点。
二叉树与度为2的树的区别：
度为2的树至少要含有3个节点，而二叉树可以为空
度为2的树种孩子的左右次序是相对的(若是只有一个子树，则左右次序无所谓)，而二叉树中孩子的左右次序是绝对的(若是只有一个子树，则也要分左子树或者是右子树)
几种特殊的二叉树：
满二叉树：一棵高度为h，且含有2^h-1个节点的二叉树
对满二叉树的节点进行编号，若从根节点开始，自上而下，自左至右的顺序进行，则对于编号为i的节点，其左孩子编号为2i，右孩子编号为2i+1
完全二叉树：一棵高度为h，且含有n个节点的二叉树，当且仅当其每一个节点都与高度为h的满二叉树中编号为1~n的节点一一对应
二叉排序树：又称二叉搜索树，左子树上所有节点的值均小于它的根节点的值，右子树上所有节点的值均大于它的根节点的值
平衡二叉树：又称AVL树，任何节点的两个子树的高度差不超过1
二叉树的性质：：
非空二叉树的叶节点数等于其双分支节点(度为2的节点)的个数加1
非空二叉树中第i层上至多有2^(i-1)个节点
高度为h的二叉树至多有2^h-1个节点(满二叉树)
具有n个节点的完全二叉树的高度为log2(n+1)向上取整
二叉树的存储结构 顺序存储结构
二叉树的顺序存储结构使用数组来存储二叉树的节点，数组的下标表示节点的编号，数组的值表示节点的值。
对于完全二叉树，可以使用顺序存储结构来存储，对于非完全二叉树，可以使用顺序存储结构来存储，但是需要浪费一些空间。
链式存储结构
二叉树的链式存储结构使用链表来存储二叉树的节点，每个节点包含一个数据域和两个指针域，分别指向左子节点和右子节点。
二叉树的遍历 二叉树的遍历是指按照某种顺序访问二叉树中的所有节点，使得每个节点被访问一次且仅被访问一次。
二叉树的遍历有四种方式：前序遍历、中序遍历、后序遍历和层序遍历。
(二叉树的遍历算法，后面会有代码实现)
前序遍历：先访问根节点，然后递归地访问左子树和右子树
中序遍历：先递归地访问左子树，然后访问根节点，最后递归地访问右子树
后序遍历：先递归地访问左子树和右子树，然后访问根节点
层序遍历：从根节点开始，逐层访问二叉树的每一层，每一层的节点按照从左到右的顺序访问
由遍历构造的二叉树 四种遍历，任意给一种都不能确定，但是只要若已知 中序遍历 和 其他三种遍历的任意一种就可以确定唯一一棵二叉树
#include <iostream> #include <queue> using namespace std;struct treeNode { char data; treeNode * left; treeNode * right; treeNode (char newData){ data = newData; left = nullptr ; right = nullptr ; } }; class BinaryTree {private : int size; treeNode* root; treeNode * createTree () { char val; cin>>val; if (val=='#' ){ return nullptr ; } treeNode * current = new treeNode (val); current->left = createTree (); current->right = createTree (); size++; return current; } void preOrder_private (treeNode* T) if (T!=nullptr ){ cout<<T->data<<"->" ; preOrder_private (T->left); preOrder_private (T->right); } } void inOrder_private (treeNode* T) if (T!=nullptr ){ inOrder_private (T->left); cout<<T->data<<"->" ; inOrder_private (T->right); } } void postOrder_private (treeNode* T) if (T!=nullptr ){ postOrder_private (T->left); cout<<T->data<<"->" ; postOrder_private (T->right); } } void levelOrder_private (treeNode* T) if (T==nullptr ){ return ; } queue<treeNode*> orderQueue; orderQueue.push (T); while (!orderQueue.empty ()){ treeNode* temp = orderQueue.front (); orderQueue.pop (); cout<<temp->data<<"->" ; if (temp->left){ orderQueue.push (temp->left); } if (temp->right){ orderQueue.push (temp->right); } } } int getHeightRecursion_private (treeNode* T) if (T==nullptr ){ return 0 ; } int leftTreeHeight = getHeightRecursion_private (T->left); int rightTreeHeight = getHeightRecursion_private (T->right); int resultLength = leftTreeHeight>rightTreeHeight?leftTreeHeight+1 :rightTreeHeight+1 ; return resultLength; } int getHeightLevel_private (treeNode* T) if (T==nullptr ){ return 0 ; } int resultHeight = 0 ; queue<treeNode*> orderQueue; orderQueue.push (T); while (!orderQueue.empty ()){ resultHeight++; for (int i=0 ;i<orderQueue.size ();i++){ treeNode* temp = orderQueue.front (); orderQueue.pop (); if (temp->left){ orderQueue.push (temp->left); } if (temp->right){ orderQueue.push (temp->right); } } } return resultHeight; } int getSize_private (treeNode* T) if (T==nullptr ){ return 0 ; } int leftSize = getSize_private (T->left); int rightSize = getSize_private (T->right); return leftSize + rightSize + 1 ; } public : BinaryTree (){ size = 0 ; root = createTree (); } void preOrder () this ->preOrder_private (root); } void inOrder () this ->inOrder_private (root); } void postOrder () this ->postOrder_private (root); } void levelOrder () this ->levelOrder_private (root); } int getHeightRecursion () return this ->getHeightRecursion_private (root); } int getHeightLevel () return this ->getHeightLevel_private (root); } int getSize () return this ->getSize_private (root); } }; int main () cout << "输入二叉树的前序序列（空节点用#表示，例如ABD##E##C#F##）:" << endl; BinaryTree bt; cout << "前序遍历结果: " ; bt.preOrder (); cout << "END" << endl; cout << "中序遍历结果: " ; bt.inOrder (); cout << "END" << endl; cout << "后序遍历结果: " ; bt.postOrder (); cout << "END" << endl; cout << "层序遍历结果: " ; bt.levelOrder (); cout << "END" << endl; cout << "递归计算的高度: " << bt.getHeightRecursion () << endl; cout << "层序计算的高度: " << bt.getHeightLevel () << endl; cout << "节点总数: " << bt.getSize () << endl; return 0 ; }
线索二叉树(看书) 树与森林 树的存储结构
双亲表示法：使用一个一维数组来存储树的节点，每个节点包含一个数据域和一个指向其父节点的指针域。
孩子表示法：使用一个一维数组来存储树的节点，每个节点包含一个数据域和一个指向其孩子节点的指针域。
孩子兄弟表示法：使用一个一维数组来存储树的节点，每个节点包含一个数据域、一个指向其父节点的指针域和一个指向其第一个孩子节点的指针域，以及一个指向其右兄弟节点的指针域。
树和二叉树的相互转化
扩展：
树的遍历
先根遍历：先访问根节点，然后依次访问根节点的孩子节点，再依次访问每个孩子节点的子树。
后根遍历：先依次访问根节点的孩子节点，再访问根节点，最后依次访问每个孩子节点的子树。
森林的遍历
先根遍历：先访问森林中每棵树的根节点，然后依次访问每棵树的根节点的孩子节点，再依次访问每个孩子节点的子树。
中序遍历：先依次访问森林中每棵树的根节点的孩子节点，再访问每棵树的根节点，最后依次访问每个孩子节点的子树。
树与二叉树的应用 哈夫曼树 一些概念
路径：从树中一个节点到另一个节点之间的分支构成这两个节点之间的路径。
权重：在树的节点上赋予的有某种意义的数值。
路径长度：路径上的分支数目称为路径长度。
树的带权路径长度：树的路径长度乘上该路径上的权值。
权重最小的路径：带权路径长度最小的路径。
哈夫曼树的构造：
从给定的节点集合中选出两个权值最小的节点，将它们合并成一个新的节点，新的节点的权值为两个节点的权值之和。
将新的节点重新插入到节点集合中，重复上述步骤，直到节点集合中只剩下一个节点，这个节点就是哈夫曼树的根节点。
哈夫曼编码：
哈夫曼编码是一种无损压缩编码，它根据字符出现的频率来构造编码，使得出现频率高的字符用较短的编码表示，出现频率低的字符用较长的编码表示。
哈夫曼编码的构造过程与哈夫曼树的构造过程类似，只是将节点的权值替换为字符出现的频率。
哈夫曼编码的解码过程与哈夫曼树的遍历过程类似，只是将遍历过程中遇到的叶子节点替换为对应的字符。
第六章 图 图的基本概念 图的定义：图是由顶点的有穷非空集合和顶点之间边的集合组成的数据结构，记作G=(V,E)，其中V是顶点的集合，E是边的集合。
术语(GPT生成的，看书吧)：
有向图:有向图是由顶点的有穷非空集合和顶点之间的有向边组成的图。
无向图:无向图是由顶点的有穷非空集合和顶点之间的无向边组成的图。
带权图:带权图是由顶点的有穷非空集合和顶点之间的带权边组成的图。
简单图:简单图是指没有重复边和重复顶点的图。
多重图:多重图是指有重复边的图。
完全图:完全图是指任意两个顶点之间都有一条边的图。
子图:子图是指由原图的顶点集合和边集合的子集组成的图。
连通图:连通图是指任意两个顶点之间都有一条路径的图。
连通分量:连通分量是指原图的最大连通子图。
入度:入度是指以某个顶点为终点的边的数目。
出度:出度是指以某个顶点为起点的边的数目。
度:度是指某个顶点的入度与出度之和。
路径:路径是指图中顶点序列，其中相邻两个顶点之间有边相连。
环:环是指路径中第一个顶点和最后一个顶点相同，且路径中不重复出现的顶点。
简单路径:简单路径是指路径中不重复出现的顶点。
简单环:简单环是指路径中不重复出现的顶点，且路径中第一个顶点和最后一个顶点相同。
距离:距离是指两个顶点之间的路径长度。
有向无环图:有向无环图是指没有环的有向图。
连通分量:连通分量是指原图的最大连通子图。
强连通图:强连通图是指任意两个顶点之间都有一条有向路径的图。
强连通分量:强连通分量是指原图的最大强连通子图。
生成图:生成图是指由原图的顶点集合和边集合的子集组成的图。
生成树:生成树是指原图的最大连通子图。
最小生成树:最小生成树是指带权图的最小生成树。
最短路径:最短路径是指两个顶点之间的路径长度最小的路径。
图的存储以及基本操作 存储结构主要是邻接矩阵和邻接表，除此之外还有十字链表和邻接多重表。
邻接矩阵 邻接矩阵是一种使用二维数组来表示图的存储结构，其中每个元素表示两个顶点之间是否存在一条边。
邻接表 邻接表是一种使用链表来表示图的存储结构，其中每个顶点都有一个链表，链表中的每个元素表示与该顶点相邻的顶点。
#include <iostream> #include <vector> using namespace std;class GraphMatrix {private : int nodeNum = 5 ; int data[5 ][5 ]; public : GraphMatrix (){ for (int i=0 ;i<nodeNum;i++){ for (int j=0 ;j<nodeNum;j++){ data[i][j] = 0 ; } } data[0 ][1 ] = 1 ; data[0 ][3 ] = 1 ; data[1 ][4 ] = 1 ; data[2 ][4 ] = 1 ; data[3 ][1 ] = 1 ; data[4 ][3 ] = 1 ; } int firstNeighbor (int x) if (x>nodeNum-1 ||x<0 ){ return -1 ; } for (int i = 0 ; i < nodeNum; i++){ if (data[x][i]!=0 ){ return i; } } return -1 ; } int nextNeighbor (int x,int y) if (x>nodeNum-1 ||x<0 ){ return -1 ; } if (y>nodeNum-1 ||y<0 ){ return -1 ; } for (int i = y+1 ; i < nodeNum; i++){ if (data[x][i]!=0 ){ return i; } } return -1 ; } }; class GraphTable {private : const int nodeNum = 5 ; vector<int > data[5 ]; public : GraphTable (){ data[0 ].push_back (1 ); data[0 ].push_back (3 ); data[1 ].push_back (4 ); data[2 ].push_back (4 ); data[3 ].push_back (1 ); data[4 ].push_back (3 ); } int firstNeighbor (int x) if (x < 0 || x >= nodeNum || data[x].empty ()) { return -1 ; } return data[x][0 ]; } int nextNeighbor (int x, int y) if (x < 0 || x >= nodeNum || y < 0 || y >= nodeNum) { return -1 ; } for (int i = 0 ; i < data[x].size (); ++i) { if (data[x][i] == y) { if (i + 1 < data[x].size ()) { return data[x][i + 1 ]; } else { return -1 ; } } } return -1 ; } }; int main () GraphMatrix gm; cout << "Testing GraphMatrix:" << endl; for (int x = 0 ; x < 5 ; x++) { cout << "Node " << x << " neighbors: " ; int current = gm.firstNeighbor (x); if (current == -1 ) { cout << "None" << endl; continue ; } cout << current; while ((current = gm.nextNeighbor (x, current)) != -1 ) { cout << ", " << current; } cout << endl; } GraphTable gt; cout << "\nTesting GraphTable:" << endl; for (int x = 0 ; x < 5 ; x++) { cout << "Node " << x << " neighbors: " ; int current = gt.firstNeighbor (x); if (current == -1 ) { cout << "None" << endl; continue ; } cout << current; while ((current = gt.nextNeighbor (x, current)) != -1 ) { cout << ", " << current; } cout << endl; } return 0 ; }
这个例子有点取巧了，对于临接表法的处理，因为是存储的node是int型的，而且连续的，所以直接使用下标作为顶点表了
图的遍历 广度优先遍历(BFS)和深度优先遍历(DFS)是两种常见的图遍历算法。
#include <iostream> #include <queue> using namespace std;class GraphMatrix {private : int nodeNum = 5 ; int data[5 ][5 ]; bool visited[5 ]; public : GraphMatrix (){ for (int i=0 ;i<nodeNum;i++){ for (int j=0 ;j<nodeNum;j++){ data[i][j] = 0 ; } } data[0 ][1 ] = 1 ; data[0 ][3 ] = 1 ; data[1 ][4 ] = 1 ; data[2 ][4 ] = 1 ; data[3 ][1 ] = 1 ; data[4 ][3 ] = 1 ; } int firstNeighbor (int x) if (x>nodeNum-1 ||x<0 ){ return -1 ; } for (int i = 0 ; i < nodeNum; i++){ if (data[x][i]!=0 ){ return i; } } return -1 ; } int nextNeighbor (int x,int y) if (x>nodeNum-1 ||x<0 ||y>nodeNum-1 ||y<0 ){ return -1 ; } for (int i = y+1 ; i < nodeNum; i++){ if (data[x][i]!=0 ){ return i; } } return -1 ; } void BFSTraverse () for (int i=0 ;i<nodeNum;i++){ visited[i] = false ; }; for (int i=0 ;i<nodeNum;i++){ if (!visited[i]) { BFS (i); } }; } void BFS (int node) queue<int > bfsQueue; bfsQueue.push (node); cout<<node<<" " ; visited[node] = true ; while (!bfsQueue.empty ()){ int temp = bfsQueue.front (); bfsQueue.pop (); for (int i = firstNeighbor (temp); i != -1 ; i = nextNeighbor (temp,i)) { if (!visited[i]){ bfsQueue.push (i); cout<<i<<" " ; visited[i] = true ; } } } } void DFSTraverse () for (int i=0 ;i<nodeNum;i++){ visited[i] = false ; }; for (int i=0 ;i<nodeNum;i++){ if (!visited[i]) { DFS (i); } }; } void DFS (int node) cout<<node<<" " ; visited[node]=true ; for (int i = firstNeighbor (node); i != -1 ; i = nextNeighbor (node,i)){ if (!visited[i]){ DFS (i); } } } }; class GraphTable {private : const int nodeNum = 5 ; vector<int > data[5 ]; bool visited[5 ]; public : GraphTable (){ data[0 ].push_back (1 ); data[0 ].push_back (3 ); data[1 ].push_back (4 ); data[2 ].push_back (4 ); data[3 ].push_back (1 ); data[4 ].push_back (3 ); } int firstNeighbor (int x) if (x < 0 || x >= nodeNum || data[x].empty ()) { return -1 ; } return data[x][0 ]; } int nextNeighbor (int x, int y) if (x < 0 || x >= nodeNum || y < 0 || y >= nodeNum) { return -1 ; } for (int i = 0 ; i < data[x].size (); ++i) { if (data[x][i] == y) { if (i + 1 < data[x].size ()) { return data[x][i + 1 ]; } else { return -1 ; } } } return -1 ; } void BFSTraverse () for (int i=0 ;i<nodeNum;i++){ visited[i] = false ; }; for (int i=0 ;i<nodeNum;i++){ if (!visited[i]) { BFS (i); } }; } void BFS (int node) queue<int > bfsQueue; bfsQueue.push (node); cout<<node<<" " ; visited[node] = true ; while (!bfsQueue.empty ()){ int temp = bfsQueue.front (); bfsQueue.pop (); for (int i = firstNeighbor (temp); i != -1 ; i = nextNeighbor (temp,i)) { if (!visited[i]){ bfsQueue.push (i); cout<<i<<" " ; visited[i] = true ; } } } } void DFSTraverse () for (int i=0 ;i<nodeNum;i++){ visited[i] = false ; }; for (int i=0 ;i<nodeNum;i++){ if (!visited[i]) { DFS (i); } }; } void DFS (int node) cout<<node<<" " ; visited[node]=true ; for (int i = firstNeighbor (node); i != -1 ; i = nextNeighbor (node,i)){ if (!visited[i]){ DFS (i); } } } }; int main () GraphMatrix gm; cout << "Testing GraphMatrix:" << endl; for (int x = 0 ; x < 5 ; x++) { cout << "Node " << x << " neighbors: " ; int current = gm.firstNeighbor (x); if (current == -1 ) { cout << "None" << endl; continue ; } cout << current; while ((current = gm.nextNeighbor (x, current)) != -1 ) { cout << ", " << current; } cout << endl; } cout << "\nTesting GraphMatrix BFS and DFS:" << endl; cout << "BFS starting from 0: " ; gm.BFSTraverse (); cout<<endl; cout << "DFS starting from 0: " ; gm.DFSTraverse (); cout<<endl; GraphTable gt; cout << "\nTesting GraphTable:" << endl; for (int x = 0 ; x < 5 ; x++) { cout << "Node " << x << " neighbors: " ; int current = gt.firstNeighbor (x); if (current == -1 ) { cout << "None" << endl; continue ; } cout << current; while ((current = gt.nextNeighbor (x, current)) != -1 ) { cout << ", " << current; } cout << endl; } cout << "\nTesting GraphTable BFS and DFS:" << endl; cout << "BFS starting from 0: " ; gt.BFSTraverse (); cout<<endl; cout << "DFS starting from 0: " ; gt.DFSTraverse (); cout<<endl; return 0 ; }
基本思路是这样的，这里要注意，不管是邻接表还是邻接矩阵，只要实现了基础的firstNeighbor与nextNeighbor函数，其流程基本上是差不多的，这个可以多看看，注意理解！！！
最小生成树 prim算法与Kruskal算法
prim算法：从任意一个顶点开始，逐步加入新的顶点，每次都选择权重最小的边，直到所有顶点都被加入为止。
Kruskal算法：将所有边按照权重从小到大排序，然后依次选择权重最小的边，如果这条边连接的两个顶点不在同一个连通分量中，则将其加入生成树中，直到所有顶点都在同一个连通分量中为止。
#include <iostream> #include <vector> #include <algorithm> using namespace std;class GraphMatrix {private : int nodeNum = 6 ; int data[6 ][6 ]; public : GraphMatrix (){ for (int i=0 ;i<nodeNum;i++){ for (int j=0 ;j<nodeNum;j++){ data[i][j] = 0 ; } } data[0 ][1 ] = 6 ;data[0 ][2 ] = 1 ;data[0 ][3 ] = 5 ; data[1 ][0 ] = 6 ;data[1 ][2 ] = 5 ;data[1 ][4 ] = 3 ; data[2 ][0 ] = 1 ;data[2 ][1 ] = 5 ;data[2 ][4 ] = 6 ;data[2 ][5 ] = 4 ;data[2 ][3 ] = 5 ; data[3 ][0 ] = 5 ;data[3 ][2 ] = 5 ;data[3 ][5 ] = 2 ; data[4 ][1 ] = 3 ;data[4 ][2 ] = 6 ;data[4 ][5 ] = 6 ; data[5 ][4 ] = 6 ;data[5 ][2 ] = 4 ;data[5 ][3 ] = 2 ; } int firstNeighbor (int x) if (x>nodeNum-1 ||x<0 ){ return -1 ; } for (int i = 0 ; i < nodeNum; i++){ if (data[x][i]!=0 ){ return i; } } return -1 ; } int nextNeighbor (int x,int y) if (x>nodeNum-1 ||x<0 ||y>nodeNum-1 ||y<0 ){ return -1 ; } for (int i = y+1 ; i < nodeNum; i++){ if (data[x][i]!=0 ){ return i; } } return -1 ; } int getWeight (int x,int y) if (x>nodeNum-1 ||x<0 ||y>nodeNum-1 ||y<0 ){ return -1 ; } return data[x][y]; } }; void prim (GraphMatrix &graph) const int n = 6 ; int parent[n]; int key[n]; bool mstSet[n]; for (int i=0 ; i<n; i++) { key[i] = 9999 ; mstSet[i] = false ; } key[0 ] = 0 ; parent[0 ] = -1 ; for (int count=0 ; count < n-1 ; count++) { int u = -1 ; int minKey = 9999 ; for (int i=0 ; i<n; i++) { if (!mstSet[i] && key[i] < minKey) { minKey = key[i]; u = i; } } if (u == -1 ) break ; mstSet[u] = true ; for (int v = graph.firstNeighbor (u);v!=-1 ;v = graph.nextNeighbor (u, v)){ int weight = graph.getWeight (u, v); if (!mstSet[v] && weight < key[v]) { parent[v] = u; key[v] = weight; } } } cout << "Prim's MST:" << endl; int totalWeight = 0 ; for (int i=1 ; i<n; i++) { int w = graph.getWeight (parent[i], i); cout << parent[i] << " - " << i << " \tWeight: " << w << endl; totalWeight += w; } cout << "Total Weight: " << totalWeight << endl << endl; } struct Edge { int u, v, weight; Edge (int u, int v, int w) : u (u), v (v), weight (w) {} bool operator <(const Edge &other) const { return weight < other.weight; } }; class UnionFind {private : vector<int > parent; public : UnionFind (int size) { parent.resize (size); for (int i=0 ; i<size; i++) parent[i] = i; } int find (int x) if (parent[x] != x) parent[x] = find (parent[x]); return parent[x]; } void unite (int x, int y) int rootX = find (x); int rootY = find (y); if (rootX != rootY) parent[rootX] = rootY; } }; void kruskal (GraphMatrix &graph) vector<Edge> edges; for (int u=0 ; u<6 ; u++) { int v = graph.firstNeighbor (u); while (v != -1 ) { if (u < v) { edges.emplace_back (u, v, graph.getWeight (u, v)); } v = graph.nextNeighbor (u, v); } } sort (edges.begin (), edges.end ()); UnionFind uf (6 ) ; vector<Edge> mst; int totalWeight = 0 ; for (Edge &e : edges) { if (uf.find (e.u) != uf.find (e.v)) { uf.unite (e.u, e.v); mst.push_back (e); totalWeight += e.weight; if (mst.size () == 5 ) break ; } } cout << "Kruskal's MST:" << endl; for (Edge &e : mst) { cout << e.u << " - " << e.v << " \tWeight: " << e.weight << endl; } cout << "Total Weight: " << totalWeight << endl; } int main () GraphMatrix graph; prim (graph); kruskal (graph); return 0 ; }
最短路径 dijkstra算法和floyd算法
#include <iostream> #include <vector> #include <algorithm> using namespace std;class GraphMatrix {private : int nodeNum = 5 ; int data[5 ][5 ]; public : GraphMatrix (){ for (int i=0 ;i<nodeNum;i++){ for (int j=0 ;j<nodeNum;j++){ data[i][j] = 0 ; } } data[0 ][1 ] = 10 ;data[0 ][4 ] = 5 ; data[1 ][4 ] = 2 ;data[1 ][2 ] = 1 ; data[2 ][3 ] = 4 ; data[3 ][2 ] = 6 ;data[3 ][0 ] = 7 ; data[4 ][1 ] = 3 ;data[4 ][2 ] = 9 ;data[4 ][3 ] = 2 ; } int firstNeighbor (int x) if (x>nodeNum-1 ||x<0 ){ return -1 ; } for (int i = 0 ; i < nodeNum; i++){ if (data[x][i]!=0 ){ return i; } } return -1 ; } int nextNeighbor (int x,int y) if (x>nodeNum-1 ||x<0 ||y>nodeNum-1 ||y<0 ){ return -1 ; } for (int i = y+1 ; i < nodeNum; i++){ if (data[x][i]!=0 ){ return i; } } return -1 ; } int getWeight (int x,int y) if (x>nodeNum-1 ||x<0 ||y>nodeNum-1 ||y<0 ){ return -1 ; } return data[x][y]; } }; void dijkstra (GraphMatrix &graph) const int nodeNum = 5 ; const int INF = 999999 ; int dist[nodeNum]; bool visited[nodeNum] = {false }; for (int i = 0 ; i < nodeNum; i++){ dist[i] = INF; } dist[0 ] = 0 ; for (int count = 0 ; count < nodeNum; count++) { int u = -1 , minDist = INF; for (int i = 0 ; i < nodeNum; i++) { if (!visited[i] && dist[i] < minDist) { minDist = dist[i]; u = i; } } if (u == -1 ) break ; visited[u] = true ; for (int v = graph.firstNeighbor (u);v!=-1 ;v = graph.nextNeighbor (u, v)){ int weight = graph.getWeight (u, v); if (!visited[v] && dist[u] != INF && dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; } } } cout << "Dijkstra算法（起点0）的最短路径：" << endl; for (int i = 0 ; i < nodeNum; i++) { if (dist[i] != INF) cout << "0->" << i << " 的最短距离: " << dist[i] << endl; else cout << "0->" << i << " 不可达" << endl; } } void floyd (GraphMatrix &graph) const int nodeNum = 5 ; const int INF = 999999 ; int dist[nodeNum][nodeNum]; for (int i = 0 ; i < nodeNum; i++) { for (int j = 0 ; j < nodeNum; j++) { if (i == j) dist[i][j] = 0 ; else { int w = graph.getWeight (i, j); dist[i][j] = (w != 0 ) ? w : INF; } } } for (int k = 0 ; k < nodeNum; k++){ for (int i = 0 ; i < nodeNum; i++){ for (int j = 0 ; j < nodeNum; j++){ if (dist[i][k]!=INF&&dist[k][j]!=INF&&dist[i][j]>dist[i][k]+dist[k][j]) { dist[i][j]=dist[i][k]+dist[k][j]; } } } } cout << "\nFloyd算法的所有顶点对最短路径：" << endl; for (int i = 0 ; i < nodeNum; i++) { for (int j = 0 ; j < nodeNum; j++) { if (dist[i][j] == INF) cout << "INF\t" ; else cout << dist[i][j] << "\t" ; } cout << endl; } } int main () GraphMatrix graph; dijkstra (graph); floyd (graph); return 0 ; }
拓扑排序
#include <iostream> #include <queue> #include <algorithm> #include <vector> using namespace std;class GraphMatrix {private : int nodeNum = 5 ; int data[5 ][5 ]; public : GraphMatrix (){ for (int i=0 ;i<nodeNum;i++){ for (int j=0 ;j<nodeNum;j++){ data[i][j] = 0 ; } } data[0 ][1 ] = 1 ;data[0 ][3 ] = 1 ; data[1 ][3 ] = 1 ;data[1 ][2 ] = 1 ; data[2 ][4 ] = 1 ; data[3 ][2 ] = 1 ;data[3 ][4 ] = 1 ; } int firstNeighbor (int x) if (x>nodeNum-1 ||x<0 ){ return -1 ; } for (int i = 0 ; i < nodeNum; i++){ if (data[x][i]!=0 ){ return i; } } return -1 ; } int nextNeighbor (int x,int y) if (x>nodeNum-1 ||x<0 ||y>nodeNum-1 ||y<0 ){ return -1 ; } for (int i = y+1 ; i < nodeNum; i++){ if (data[x][i]!=0 ){ return i; } } return -1 ; } int getWeight (int x,int y) if (x>nodeNum-1 ||x<0 ||y>nodeNum-1 ||y<0 ){ return -1 ; } return data[x][y]; } int indegree (int x) if (x>nodeNum-1 ||x<0 ){ return -1 ; } int result = 0 ; for (int i = 0 ; i < nodeNum; i++) { if (data[i][x] != 0 ) { result++; } } return result; } }; vector<int > topologicalSort (GraphMatrix &graph) { const int nodeNum = 5 ; vector<int > inDegree (nodeNum) ; for (int i = 0 ; i < nodeNum; ++i) { inDegree[i] = graph.indegree (i); } queue<int > q; for (int i = 0 ; i < nodeNum; ++i) { if (inDegree[i] == 0 ) { q.push (i); } } vector<int > result; while (!q.empty ()){ int u = q.front (); q.pop (); result.push_back (u); for (int v = graph.firstNeighbor (u);v!=-1 ;v = graph.nextNeighbor (u, v)){ if (--inDegree[v] == 0 ) { q.push (v); } } } if (result.size () != nodeNum) { return {}; } return result; } int main () GraphMatrix graph; vector<int > sorted = topologicalSort (graph); if (sorted.empty ()) { cout << "图中存在环，无法进行拓扑排序" << endl; } else { cout << "拓扑排序结果：" ; for (int node : sorted) { cout << node << " " ; } cout << endl; } return 0 ; }
关键路径(看书吧哥，这个好复杂) 第七章 查找 基本概念 顺序查找和折半查找 顺序查找 1.一般顺序查找
很简单，直接遍历
2.有序线性表的顺序查找
也是遍历，但是如果之前的都是小于findKey,突然值大于了findKey,那么就不必再查找了，就直接停止遍历(因为是有序的)
1 3 5 7 9 11 13 15 17 19 21 23 25
findKey = 11 遍历的时候查找到11 成功返回index
findKey = 12 遍历的时候查找到11之前一直小于12,但是到下一个点13就突然大于12,那么就直接返回-1(错误处理的结果)就好，查找不到
折半查找 这个就不过多介绍了
#include <iostream> using namespace std;int main () int data[10 ] = {2 ,5 ,7 ,11 ,13 ,17 ,19 ,23 ,29 ,31 }; int findKey = 11 ; int low=0 ,high=9 ,mid; bool flag = false ; while (low<=high){ mid = (low + high)/2 ; if (data[mid]==findKey){ cout<<"找到了! 位置为：" <<mid<<endl; flag = true ; break ; } if (data[mid]>findKey){ high = mid - 1 ; } if (data[mid]<findKey){ low = mid + 1 ; } } if (!flag){ cout<<"没找到" <<endl; } return 0 ; }
分块查找：
索引表折半，表内顺序
二叉排序树 #include <iostream> using namespace std;struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode (int x):val (x),left (nullptr ),right (nullptr ){}; }; class BST {private : TreeNode* root; TreeNode* insertNode (TreeNode* node,int val) { if (!node){ return new TreeNode (val); } if (val < node->val){ node->left = insertNode (node->left,val); }else if (val > node->val){ node->right = insertNode (node->right,val); } return node; } TreeNode* findMin (TreeNode* node) { while (node && node->left) node = node->left; return node; } TreeNode* deleteNode (TreeNode* node,int val) { if (!node){ return nullptr ; } if (val < node->val){ node->left = deleteNode (node->left,val); }else if (val > node->val){ node->right = deleteNode (node->right,val); }else { if (!node->left){ TreeNode* right = node->right; delete node; return right; } else if (!node->right){ TreeNode* left = node->left; delete node; return left; } else { TreeNode* minRight = findMin (node->right); node->val = minRight->val; node->right = deleteNode (node->right,minRight->val); } } return node; } void inorderTraversal (TreeNode* node) if (!node) return ; inorderTraversal (node->left); cout << node->val << " " ; inorderTraversal (node->right); } void destroyTree (TreeNode* node) if (!node) return ; destroyTree (node->left); destroyTree (node->right); delete node; } public : BST () : root (nullptr ) {} void insert (int val) root = insertNode (root, val); } void remove (int val) root = deleteNode (root,val); } bool search (int val) TreeNode* curr = root; while (curr){ if (curr->val == val){ return true ; }else if (curr->val < val){ curr = curr->right; }else { curr = curr->left; } } return false ; } void printInorder () inorderTraversal (root); cout<<"END" <<endl; } ~BST () { destroyTree (root); } }; int main () BST bst; bst.insert (5 ); bst.insert (3 ); bst.insert (7 ); bst.insert (2 ); bst.insert (4 ); bst.insert (6 ); bst.insert (8 ); cout << "初始中序遍历: " ; bst.printInorder (); cout << "查找 4: " << (bst.search (4 ) ? "存在" : "不存在" ) << endl; cout << "查找 9: " << (bst.search (9 ) ? "存在" : "不存在" ) << endl; bst.remove (3 ); cout << "删除3后的中序遍历: " ; bst.printInorder (); bst.remove (7 ); cout << "删除7后的中序遍历: " ; bst.printInorder (); bst.remove (2 ); cout << "删除2后的中序遍历: " ; bst.printInorder (); return 0 ; }
平衡二叉树 #include <iostream> #include <algorithm> using namespace std;struct AVLNode { int val; int height; AVLNode* left; AVLNode* right; AVLNode (int x):val (x),height (1 ),left (nullptr ),right (nullptr ){}; }; class AVLTree { AVLNode* root; int getHeight (AVLNode* node) return node ? node->height : 0 ; } void updateHeight (AVLNode* node) if (node){ node->height = 1 + max (getHeight (node->left),getHeight (node->right)); } } int getBalanceFactor (AVLNode* node) return getHeight (node->left) - getHeight (node->right); } AVLNode* rightRotate (AVLNode* y) { AVLNode* x = y->left; AVLNode* T3 = x->right; x->right = y; y->left = T3; updateHeight (y); updateHeight (x); return x; } AVLNode* leftRotate (AVLNode* x) { AVLNode* y = x->right; AVLNode* T2 = y->left; y->left = x; x->right = T2; updateHeight (x); updateHeight (y); return y; } AVLNode* insertNode (AVLNode* node, int val) { if (!node){ return new AVLNode (val); } if (val < node->val){ node->left = insertNode (node->left,val); }else if (val > node->val){ node->right = insertNode (node->right,val); }else { return node; } updateHeight (node); int balance = getBalanceFactor (node); if (balance > 1 && val < node->left->val) return rightRotate (node); if (balance < -1 && val > node->right->val) return leftRotate (node); if (balance > 1 && val > node->left->val) { node->left = leftRotate (node->left); return rightRotate (node); } return node; } AVLNode* deleteNode (AVLNode* node, int val) { if (!node) return nullptr ; if (val < node->val){ node->left = deleteNode (node->left, val); }else if (val > node->val){ node->right = deleteNode (node->right, val); }else { if (!node->left||!node->right){ AVLNode* temp = node->left ? node->left : node->right; if (!temp){ temp = node; node = nullptr ; }else { *node = *temp; } delete temp; }else { AVLNode* minRight = node->right; while (minRight->left){ minRight = minRight->left; } node->val = minRight->val; node->right = deleteNode (node->right,minRight->val); } } if (!node) return nullptr ; updateHeight (node); int balance = getBalanceFactor (node); if (balance < -1 && val < node->right->val) { node->right = rightRotate (node->right); return leftRotate (node); } if (balance > 1 && getBalanceFactor (node->left) >= 0 ) return rightRotate (node); if (balance > 1 && getBalanceFactor (node->left) < 0 ) { node->left = leftRotate (node->left); return rightRotate (node); } if (balance < -1 && getBalanceFactor (node->right) <= 0 ) return leftRotate (node); if (balance < -1 && getBalanceFactor (node->right) > 0 ) { node->right = rightRotate (node->right); return leftRotate (node); } return node; } void inorderTraversal (AVLNode* node) if (!node) return ; inorderTraversal (node->left); cout << node->val << " " ; inorderTraversal (node->right); } public : AVLTree () : root (nullptr ) {} void insert (int val) root = insertNode (root, val); } void remove (int val) root = deleteNode (root, val); } bool search (int val) AVLNode* curr = root; while (curr) { if (curr->val == val) return true ; else if (val < curr->val) curr = curr->left; else curr = curr->right; } return false ; } void printInorder () inorderTraversal (root); cout << endl; } }; int main () AVLTree avl; avl.insert (10 ); avl.insert (20 ); avl.insert (30 ); avl.insert (40 ); avl.insert (50 ); avl.insert (25 ); cout << "插入后的中序遍历: " ; avl.printInorder (); cout << "查找25: " << (avl.search (25 ) ? "存在" : "不存在" ) << endl; cout << "查找100: " << (avl.search (100 ) ? "存在" : "不存在" ) << endl; avl.remove (30 ); cout << "删除30后的中序遍历: " ; avl.printInorder (); avl.remove (25 ); cout << "删除25后的中序遍历: " ; avl.printInorder (); return 0 ; }
红黑树 #include <iostream> using namespace std;enum Color { RED, BLACK };struct RBNode { int val; Color color; RBNode *left, *right, *parent; RBNode (int x) : val (x), color (RED), left (nullptr ), right (nullptr ), parent (nullptr ) {} }; class RedBlackTree {private : RBNode* root; RBNode* nil; void leftRotate (RBNode* x) RBNode* y = x->right; x->right = y->left; if (y->left != nil) { y->left->parent = x; } y->parent = x->parent; if (x->parent == nil) { root = y; } else if (x == x->parent->left) { x->parent->left = y; } else { x->parent->right = y; } y->left = x; x->parent = y; } void rightRotate (RBNode* x) RBNode* y = x->left; x->left = y->right; if (y->right != nil) { y->right->parent = x; } y->parent = x->parent; if (x->parent == nil) { root = y; } else if (x == x->parent->right) { x->parent->right = y; } else { x->parent->left = y; } y->right = x; x->parent = y; } void insertFixup (RBNode* z) while (z->parent->color == RED) { if (z->parent == z->parent->parent->left) { RBNode* y = z->parent->parent->right; if (y->color == RED) { z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; } else { if (z == z->parent->right) { z = z->parent; leftRotate (z); } z->parent->color = BLACK; z->parent->parent->color = RED; rightRotate (z->parent->parent); } } else { RBNode* y = z->parent->parent->left; if (y->color == RED) { z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; } else { if (z == z->parent->left) { z = z->parent; rightRotate (z); } z->parent->color = BLACK; z->parent->parent->color = RED; leftRotate (z->parent->parent); } } } root->color = BLACK; } void deleteFixup (RBNode* x) while (x != root && x->color == BLACK) { if (x == x->parent->left) { RBNode* w = x->parent->right; if (w->color == RED) { w->color = BLACK; x->parent->color = RED; leftRotate (x->parent); w = x->parent->right; } if (w->left->color == BLACK && w->right->color == BLACK) { w->color = RED; x = x->parent; } else { if (w->right->color == BLACK) { w->left->color = BLACK; w->color = RED; rightRotate (w); w = x->parent->right; } w->color = x->parent->color; x->parent->color = BLACK; w->right->color = BLACK; leftRotate (x->parent); x = root; } } else { RBNode* w = x->parent->left; if (w->color == RED) { w->color = BLACK; x->parent->color = RED; rightRotate (x->parent); w = x->parent->left; } if (w->right->color == BLACK && w->left->color == BLACK) { w->color = RED; x = x->parent; } else { if (w->left->color == BLACK) { w->right->color = BLACK; w->color = RED; leftRotate (w); w = x->parent->left; } w->color = x->parent->color; x->parent->color = BLACK; w->left->color = BLACK; rightRotate (x->parent); x = root; } } } x->color = BLACK; } RBNode* minimum (RBNode* node) { while (node->left != nil) node = node->left; return node; } void inorderTraversal (RBNode* node) if (node == nil) return ; inorderTraversal (node->left); cout << node->val << (node->color == RED ? "(R) " : "(B) " ); inorderTraversal (node->right); } public : RedBlackTree () { nil = new RBNode (-1 ); nil->color = BLACK; root = nil; } void insert (int val) RBNode* z = new RBNode (val); RBNode* y = nil; RBNode* x = root; while (x != nil) { y = x; if (z->val < x->val) { x = x->left; } else { x = x->right; } } z->parent = y; if (y == nil) { root = z; } else if (z->val < y->val) { y->left = z; } else { y->right = z; } z->left = nil; z->right = nil; insertFixup (z); } void remove (int val) RBNode* z = root; while (z != nil) { if (z->val == val) break ; else if (val < z->val) z = z->left; else z = z->right; } if (z == nil) return ; RBNode* y = z; Color yOriginalColor = y->color; RBNode* x; if (z->left == nil) { x = z->right; transplant (z, z->right); } else if (z->right == nil) { x = z->left; transplant (z, z->left); } else { y = minimum (z->right); yOriginalColor = y->color; x = y->right; if (y->parent == z) { x->parent = y; } else { transplant (y, y->right); y->right = z->right; y->right->parent = y; } transplant (z, y); y->left = z->left; y->left->parent = y; y->color = z->color; } delete z; if (yOriginalColor == BLACK) { deleteFixup (x); } } void transplant (RBNode* u, RBNode* v) if (u->parent == nil) { root = v; } else if (u == u->parent->left) { u->parent->left = v; } else { u->parent->right = v; } v->parent = u->parent; } bool search (int val) RBNode* curr = root; while (curr != nil) { if (curr->val == val) return true ; else if (val < curr->val) curr = curr->left; else curr = curr->right; } return false ; } void printInorder () inorderTraversal (root); cout << endl; } }; int main () RedBlackTree rbt; rbt.insert (10 ); rbt.insert (20 ); rbt.insert (30 ); rbt.insert (40 ); rbt.insert (50 ); rbt.insert (25 ); cout << "插入后的中序遍历: " ; rbt.printInorder (); cout << "查找25: " << (rbt.search (25 ) ? "存在" : "不存在" ) << endl; cout << "查找100: " << (rbt.search (100 ) ? "存在" : "不存在" ) << endl; rbt.remove (30 ); cout << "删除30后的中序遍历: " ; rbt.printInorder (); rbt.remove (25 ); cout << "删除25后的中序遍历: " ; rbt.printInorder (); return 0 ; }
hush表 #include <iostream> #include <string> #include <vector> using namespace std;const int TABLE_SIZE = 10 ; struct HashNode { string key; int value; HashNode* next; HashNode (const string& k,int v):key (k),value (v),next (nullptr ){} }; class HashTable {private : vector<HashNode*> buckets; int hashFunction (const string& key) int hash = 0 ; for (char c:key){ hash += c; } return hash % TABLE_SIZE; } public : HashTable () : buckets (TABLE_SIZE, nullptr ) {} ~HashTable (){ for (int i = 0 ; i < TABLE_SIZE; ++i){ HashNode* entry = buckets[i]; while (entry){ HashNode* prev = entry; entry = entry->next; delete entry; } } } void insert (const string& key, int value) int bucketIndex = hashFunction (key); HashNode* entry = buckets[bucketIndex]; while (entry){ if (entry->key == key) { entry->value = value; return ; } entry = entry->next; } HashNode* newNode = new HashNode (key, value); newNode->next = buckets[bucketIndex]; buckets[bucketIndex] = newNode; } int get (const string& key) int bucketIndex = hashFunction (key); HashNode* entry = buckets[bucketIndex]; while (entry){ if (entry->key == key){ return entry->value; } entry = entry->next; } return -1 ; } void remove (const string& key) int bucketIndex = hashFunction (key); HashNode* entry = buckets[bucketIndex]; HashNode* prev = nullptr ; while (entry){ if (entry->key == key){ if (prev){ prev->next = entry->next; }else { buckets[bucketIndex] = entry->next; } delete entry; } prev = entry; entry = entry->next; } } }; int main () HashTable myHashTable; myHashTable.insert ("Alice" , 30 ); myHashTable.insert ("Bob" , 25 ); myHashTable.insert ("Charlie" , 28 ); cout << "Alice's age: " << myHashTable.get ("Alice" ) << endl; cout << "Unknown key: " << myHashTable.get ("Dave" ) << endl; myHashTable.remove ("Bob" ); cout << "After removal - Bob: " << myHashTable.get ("Bob" ) << endl; return 0 ; }
第八章 查找 8.2 插入排序 直接插入排序 #include <iostream> using namespace std;int main () int data_1[11 ] = {36 ,27 ,20 ,60 ,55 ,7 ,70 ,36 ,44 ,67 ,16 }; for (int i=1 ;i<11 ;i++){ for (int j=i;j>0 ;j--){ if (data_1[j]<data_1[j-1 ]){ int temp = data_1[j-1 ]; data_1[j-1 ] = data_1[j]; data_1[j] = temp; } } } for (int i=0 ;i<11 ;i++){ cout<<data_1[i]<<" " ; } cout<<endl; int data_2[11 ] = {36 ,27 ,20 ,60 ,55 ,7 ,70 ,36 ,44 ,67 ,16 }; for (int i=1 ;i<11 ;i++){ int key = data_2[i]; int j = i; while (j > 0 && key > data_2[j-1 ]){ data_2[j] = data_2[j-1 ]; j--; } data_2[j] = key; } for (int i=0 ;i<11 ;i++){ cout<<data_2[i]<<" " ; } cout<<endl; return 0 ; }
折半插入排序 #include <iostream> using namespace std;int main () int data[11 ] = {36 ,27 ,20 ,60 ,55 ,7 ,70 ,36 ,44 ,67 ,16 }; for (int i=1 ;i<11 ;i++){ int key = data[i]; int low = 0 ,high = i-1 ; while (low <= high){ int mid = (low + high)/2 ; if (key > data[mid]){ high = mid - 1 ; }else { low = mid + 1 ; } } for (int j=i;j>high+1 ;j--){ data[j] = data[j-1 ]; } data[high + 1 ] = key; } for (int i=0 ;i<11 ;i++){ cout<<data[i]<<" " ; } cout<<endl; return 0 ; }
希儿排序 #include <iostream> using namespace std;int main () int n = 11 ; int data[n] = {36 ,27 ,20 ,60 ,55 ,7 ,70 ,36 ,44 ,67 ,16 }; for (int gap = n/2 ; gap > 0 ; gap /= 2 ) { for (int i = gap;i<n;i++){ int tmp = data[i]; int j = i; while (j>0 &&j>=gap&&data[j-gap]>tmp){ data[j] = data[j-gap]; j = j - gap; } data[j] = tmp; } } for (int i=0 ;i<11 ;i++){ cout<<data[i]<<" " ; } cout<<endl; }
8.3 交换排序 冒泡排序 #include <iostream> using namespace std;int main () int n = 11 ; int data[n] = {36 ,27 ,20 ,60 ,55 ,7 ,70 ,36 ,44 ,67 ,16 }; for (int i=0 ;i<n-1 ;i++){ bool flag = false ; for (int j=n-1 ;j>i;j--){ if (data[j]<data[j-1 ]){ int temp = data[j-1 ]; data[j-1 ] = data[j]; data[j] = temp; flag = true ; } } if (!flag){ break ; } } for (int i=0 ;i<11 ;i++){ cout<<data[i]<<" " ; } cout<<endl; return 0 ; }
快速排序 #include <iostream> using namespace std;int partition (int data[],int low,int high) int pivot = data[low]; while (low<high){ while (low<high&&data[high]>=pivot){ high--; } data[low] = data[high]; while (low<high&&data[low]<=pivot){ low++; } data[high] = data[low]; } data[low] = pivot; return low; } void quickSort (int data[],int low,int high) if (low<high){ int pivotpos = partition (data,low,high); quickSort (data,low,pivotpos-1 ); quickSort (data,pivotpos+1 ,high); } } int main () int n = 11 ; int data[n] = {36 ,27 ,20 ,60 ,55 ,7 ,70 ,36 ,44 ,67 ,16 }; quickSort (data,0 ,n-1 ); for (int i=0 ;i<n;i++){ cout<<data[i]<<" " ; } cout<<endl; return 0 ; }
8.4 选择排序 简单选择排序 #include <iostream> using namespace std;int main () int n = 11 ; int data[n] = {36 ,27 ,20 ,60 ,55 ,7 ,70 ,36 ,44 ,67 ,16 }; for (int i=0 ;i<n-1 ;i++){ int minIndex = i; for (int j=i+1 ;j<n;j++){ if (data[minIndex]>data[j]){ minIndex = j; } } if (minIndex!=i){ int temp = data[i]; data[i] = data[minIndex]; data[minIndex] = temp; } } for (int i=0 ;i<n;i++){ cout<<data[i]<<" " ; } cout<<endl; return 0 ; }
快排 #include <iostream> using namespace std;int partition (int data[],int low,int high) int pivot = data[low]; while (low<high){ while (low<high&&data[high]>=pivot){ high--; } data[low] = data[high]; while (low<high&&data[low]<=pivot){ low++; } data[high] = data[low]; } data[low] = pivot; return low; } void quickSort (int data[],int low,int high) if (low<high){ int pivotpos = partition (data,low,high); quickSort (data,low,pivotpos-1 ); quickSort (data,pivotpos+1 ,high); } } int main () int n = 11 ; int data[n] = {36 ,27 ,20 ,60 ,55 ,7 ,70 ,36 ,44 ,67 ,16 }; quickSort (data,0 ,n-1 ); for (int i=0 ;i<n;i++){ cout<<data[i]<<" " ; } cout<<endl; return 0 ; }
8.5 归并与基数 归并排序 #include <iostream> using namespace std;void merge (int data[],int left,int right,int mid) int n1 = mid - left + 1 ; int n2 = right - mid; int leftArr[n1] = {0 }; int rightArr[n2] = {0 }; for (int i=0 ;i<n1;i++){ leftArr[i] = data[i+left]; } for (int j=0 ;j<n2;j++){ rightArr[j] = data[j+mid+1 ]; } int i = 0 ,j=0 ,k=left; while (i<n1&&j<n2){ if (leftArr[i]<=rightArr[j]){ data[k] = leftArr[i]; i++; }else { data[k] = rightArr[j]; j++; } k++; } while (i<n1){ data[k++] = leftArr[i++]; } while (j<n2){ data[k++] = rightArr[j++]; } } void mergeSortRecursive (int data[],int left,int right) if (left<right){ int mid = (left + right) / 2 ; mergeSortRecursive (data,left,mid); mergeSortRecursive (data,mid+1 ,right); merge (data,left,right,mid); } } void mergeSortIterative (int data[], int n) for (int size = 1 ; size < n; size *= 2 ) { for (int left=0 ;left<n;left+=2 *size){ int mid = min (left+size-1 ,n-1 ); int right = min (left+2 *size-1 ,n-1 ); if (mid<right){ merge (data,left,right,mid); } } } } int main () int n = 11 ; int data_1[n] = {36 ,27 ,20 ,60 ,55 ,7 ,70 ,36 ,44 ,67 ,16 }; mergeSortRecursive (data_1, 0 , n - 1 ); cout << "递归结果: " ; for (int i=0 ;i<n;i++){ cout<<data_1[i]<<" " ; } cout<<endl; int data_2[n] = {36 ,27 ,20 ,60 ,55 ,7 ,70 ,36 ,44 ,67 ,16 }; mergeSortIterative (data_2, n); cout << "递归结果: " ; for (int i=0 ;i<n;i++){ cout<<data_2[i]<<" " ; } cout<<endl; return 0 ; }
