二叉查找树 这种数据结构能够将链表插入的灵活性和有序数组查找的高效性结合，大名鼎鼎的二叉查找树，也叫二叉搜索树。下面的代码是一份完整的类实现 class BST { public: class Node { public: int key; //键 int value; //值 Node* left; Node* right; int N;//以该节点为根节点的树的节点总数 public://Node类的构造函数 Node(int key, int value...

在通过第二章的方法将数据排序之后，我们常常需要进行查找操作，本章就来介绍查找的方法。我们会使用符号表这个词来表示一张抽象的表格，其实就可以把它看成键值对，而键值对就是字典，键对应单词，值对应单词的意思，发音等。 我们先列出符号表symbol table的API: 然后我们的工作就是选择适当的数据结构去实现它，你可以看到，不同的数据结构对效率的影响有多大 无序链表实现符号表 一个简单选择是链表，每个节点存储一个键值对，具体实现看代码： class SequentialSearchST{ private: Node first; //链表首节点 class Node{ ...

一：归并操作 在本节中我们所讨论的算法都基于归并这个简单的操作，即将两个有序数组归并成一个： void sort(vector<int> &arr, int start, int mid, int end){ int i=start, j= mid+1; vector<int> arrcopy; for (int k = 0; k <= end; ++k) { arrcopy.push_back(arr[k]); } for (int k = start; k <= end; ++k) ...

一：选择排序 每次选最小的与未排序的最前面那个交换一下： class SelectionSort { public: static void exch(vector<int> &arr, int p, int q) { int temp = arr[p]; arr[p] = arr[q]; arr[q] = temp; } static void sort(vector<int> &arr) { int N = arr.size(); ...

原书目录 动态连通性 我们输入一对一对的整数，每个整数表示一台计算机，整数对表示这两台计算机可以通信，当我们在已有一些整数对的情况下，需要去判断，新进来一个整数对p,q，是否需要在它俩之间架设新的连接才能通信，还是说我们可以在已有的连接上使二者可以通信 我们会一步步地去优化问题的解决方案，你可以在看每个解决方案之前想一想 定义一份API <thead> public class UF 含义 </thead> UF(int N)以整数标识(0-N-1)初始化N台电脑 void union(int p,...

最后一题全排列，把大于号的数写成了n-k+1，刚刚才发现，然而。。。 啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊！

首先互相包涵就有问题，现在我采用的A包涵B，然后在B.h中前置声明class A，但是这样只是声明而已，无法去调用A的函数，请教大侠～

一：递归找链表中的节点最大值 不难，但我觉得对理解递归的思想有用，就把自己写的代码贴上来了： int max(Node first) { if (first.next == NULL){ return first.a; } else{ return first.a > max(*(first.next)) ? first.a : max(*(first.next)); } } 二：约瑟夫问题 N个身陷绝境的人一致同意通过以下方式减少生存人数，直到最后一个人留下来，从第一个人开始报数，报到M的人会被杀死，直到只剩一人，我贴一份以前的代码抛砖引玉（环形链表）： class ...

一：书上原题1.3.9 编写一段程序，从标准输入得到一个缺少左括号的表达式并打印出补全括号之后的中序表达式，例如，给定输入： 1+2)3-4) 5-6))) 你的程序应该输出： ((1+2) ((3-4) (5-6))) 这道题跟前面介绍的很类似我们还是用两个栈分三种情况来处理： 遇到数，入数栈 遇到运算符，入符栈 遇到右括号，弹出两个数（注意顺序），一个符，拼成字符串（加上括号），入数栈``` string left(vector &a) { stack vals, ops; for (int i = 0; i < a.size(); ++i) ...

一：算术表达式求值 这次讲的是简单的算术表达式求值，怎么简单呢？就是每个子表达式都是有括号的，你不用去管它的运算优先级 栈永远是表达式求值的经典应用 我们求的是类似这样的表达式：( 1 + ( (2+3) ( 4 5) )) 空格忽略（我是为了md格式方便显示）我们使用栈的求值策略如下：准备两个栈，分别存放数值和运算符，当我们从左到右扫描表达式时有四种情况，我们来分别处理： 遇到数->直接入数值栈 遇到运算符->直接入运算符栈 遇到左括号->忽略 遇到右括号，弹出一个运算符，弹出俩数，做运算（注意顺序），将结果压入数值栈我们可以看到，非常简单对...

一：辗转相除法求最大公约数 不知道辗转相除法的戳这里 这个简单的程序，涉及到了递归的思想，我们来看一下： int gcd(int p, int q) { if(q==0) return p; //一定有一个触底反弹 int r = p % q; return gcd(q, r); //问题规模越来越小，且子问题与父问题无交集 } 如果你对于递归不是特别了解，我强烈建议你在自己的编译器中去断点调试一下，看看发生了什么 二：二分查找 这是一个非常经典的查找，注意前提一定得是有序列，然后你要注意分界（这里不考虑重复元素）： //在vec中寻找元素等于tar的，返回其下...

算法（第4版）笔记 目录： 第一章：基础-基础编程模型 第一章：基础-背包队列和栈1 第一章：基础-栈在各类表达式中的应用 第一章：基础-链表练习 第一章：union-find算法（临渊羡鱼不如退而结网啊） 第二章：初级排序算法 第二章：归并排序 第三章：查找1 第三章：查找2

C++ Primer 模板与泛型编程 这一章会介绍一个神器-模板，我们可以用它实现泛型编程，我们先来说点大的官方的话： 面向对象编程能处理类型未知的情况，因为它都封装为对象了 泛型编程能处理在编译之前类型不知道的情况 说得这么玄乎，其实我们早就在用泛型编程了，比如我们学过的容器、迭代器和算法都是泛型编程，下面我们就来学习它，看看它到底方便在哪 模板是C++中泛型编程的基础，记住这句话：一个模板就是一个创建类或函数的蓝图 定义模板 我们现在要实现一个功能，很简单，比较两个值的大小，在实际中，我们可能需要写很多歌，因为这两个值可能是int,, double, string等等...

C++ Primer 面向对象程序设计 文本查询程序再探 我们要拓展之前的文本查询程序，用来作为说明继承的最后一个例子。上一版程序中，我们实现的功能时查询在文件中某个指定单词的出现情况。我们将在本节拓展该程序使其支持更多更复杂的查询操作。在后面的例子中，我们将针对下面这个美丽的小故事展开查询： Alice Emma has long flowing red hair. Her Daddy says when the wind blows through her hair, it looks almost alive, like a fiery bird in flight. A beautif...