因为数组默认值为0，因此记录了很多没意义的数据。
当一个数组中大部分元素为0，或者为同一个数值的数组时，可以使用稀疏数组来保存该数据。
- 记录数组一共有几行几列，有多少个不同的值。
- 把具有不同值的元素的行列及值记录在一个小规模的数组中（稀疏数组），从而缩小程序的规模。
二维数组转稀疏数组的思路：
1.遍历原始的二维数组，得到有效数据的个数sum。
2.根据sum就可以创建稀疏数组 int sparseArr[sum+1][3]。
3.将二维数组的有效数据存入到稀疏数组。
稀疏数组转二维数组的思路：
1.先读取稀疏数组第一行，根据第一行数据，创建二维数组，
int chessArr[sparseArr[0][0]][sparseArr[0][1]]。
2.再读取稀疏数组后几行的数据，并赋给二维数组即可。int main()
{
//创建一个原始的二维数组11*11
//0：没有棋子，1：黑子，2：蓝子
int chessArr1[11 ][11]={};
chessArr1[1][2]=1;
chessArr2[2][4]=2;
//将二维数组中转换为稀疏数组
//1.先遍历二维数组，得出非0数据的个数
int sum=0;
for(int i=0;i<11;i++)
{
for(int j=0;j<11;j++)
{
if(chessArr1[i][j]!=0)
{
sum++;
}
}
}
//2.创建对应稀疏数组
int sparseArr[sum+1][3]={};
//2.1给稀疏数组赋值
sparseArr[0][0]=11;
sparseArr[0][1]=11;
sparseArr[0][2]=sum;
//2.2遍历二维数组，将非0的值存到稀疏数组
int count=0;//count用来记录是第几个非0值
for(int i=0;i<11;i++)
{
for(int j=0;j<11;j++)
{
if(chessArr1[i][j]!=0)
{
count++;
sparse[count][0]=i;
sparse[count][1]=j;
sparse[count][2]=chessArr1[i][j];
}
}
}
//将稀疏数组恢复二维数组
//1.先读取稀疏数组第一行，根据第一行数据，创建二维数组
int chessArr2[sparseArr[0][0]][sparseArr[0][1]]={};
// 2.再读取稀疏数组后几行的数据，并赋给二维数组即可
for(int i=1;i<sum+1;i++)
{
chessArr2[sparseArr[i][0]][sparse[i][1]]=sparse[i][2];
}
}- 队列是一个有序列表，可以用数组或是链表来实现
- 遵循先入先出的原则。
//使用数组模拟队列-编写一个ArrayQueue类
class ArrayQueue
{
private:
int maxSize;//数组的最大容量
int front;//队列头
int rear;//队列尾
int arr[];//该数组用于存放数据，模拟队列
public:
//创捷队列构造器
ArrayQueue(int arrMaxSize) {
maxSize = arrMaxSize;
arr[maxSize] = {};
front = -1;//指向队列头部。当还未插入数据时，分析出front是指向队列头的前一个位置，不包含数据。
rear = -1;//指向队列尾，包含数据。
}
//判断队列是否满
bool isFull() {
return rear == maxSize - 1;
}
//判断队列是否为空
bool isEmpty() {
return front == rear;
}
//添加数据到队列
void addQueue(int n) {
//判断队列是否满
if (isFull()) {
cout << "队列满，不能加入数据。" << endl;
return;
}
rear++;//让rear后移
arr[rear] = n;
}
//获取队列的数据，出队列
int getQueue() {
//判断队列是否空
if (isEmpty()) {
//通过抛出异常
throw runtime_error("队列空，不能取数据。");
}
front++;//front后移
return arr[front];
}
//显示队列所有数据
void showQueue() {
if (isEmpty()) {
cout << "队列为空，没有数据。" << endl;
return;
}
for (int i = 0; i < maxSize; i++) {
cout << arr[i] << endl;
}
}
//显示队列的头数据，注意不是取出数据
int headQueue() {
if (isEmpty()) {
throw runtime_error("队列为空，没有数据。");
}
return arr[front + 1];
}
};
int main() {
//测试
ArrayQueue aq(3);
char key = ' ';//接收用户输入
bool loop = true;
cout << "输入s（show）：显示队列" << endl;
cout << "输入e（exit）：退出程序" << endl;
cout << "输入a（add）：添加数据到队列" << endl;
cout << "输入g（get）：从队列取出数据" << endl;
cout << "输入h（head）：查看队列头的数据" << endl;
while (loop) {
cin >> key;
int value = 0;
switch (key) {
case 's':
aq.showQueue();
break;
case 'a':
cout << "输入一个数" << endl;
cin >> value;
aq.addQueue(value);
break;
case'g':
try {
int res = aq.getQueue();
cout << "取出的数据是" << res << endl;
}
catch (exception e) {
cout << e.what() << endl;
}
break;
case'h':
try {
int res = aq.headQueue();
cout << "队列头的数据是" << res << endl;
}
catch (exception e) {
cout << e.what() << endl;
}
break;
case'e':
loop = false;
break;
default:
break;
}
}
cout << "程序退出。" << endl;
system("pause");
return 0;
}
缺点：虽然取出数据，但却无法再添加数据，数组用了一次之后就不能用了。思路：
1.front变量的含义做一个调整：front就指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素。
front的初始值=0。
2.rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置，因为希望空出一个位置作为约定。
rear的初始值=0。
3.队列满时，条件是：(rear+1)%maxSize==front。
4.队列空时，条件是：rear==front。
5.当我们这样分析，队列中有效的数据的个数（rear+maxSize-front）%maxSize。
6.我们就可以在原来的队列上修改得到环形队列
class CircleArray {
private:
int maxSize;//数组的最大容量
int front;//指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素
int rear;//rear指向队列的最后一个元素的后一个位置，因为希望空出一个位置作为约定
int arr[];//该数组用于存放数据，模拟队列
public:
CircleArray(int arrMaxSize) {
maxSize = arrMaxSize;
arr[maxSize] = {};
front = 0;
rear = 0;
}
//判断队列是否满
bool isFull() {
return (rear + 1) % maxSize == front;
}
//判断队列是否为空
bool isEmpty() {
return front == rear;
}
//添加数据到队列
void addQueue(int n) {
//判断队列是否满
if (isFull()) {
cout << "队列满，不能加入数据。" << endl;
return;
}
//直接将数据加入
arr[rear] = n;
//将rear后移，这里必须考虑取模
rear = (rear + 1) % maxSize;
}
//获取队列的数据，出队列
int getQueue() {
//判断队列是否空
if (isEmpty()) {
//通过抛出异常
throw runtime_error("队列空，不能取数据。");
}
//这里需要分析出front是指向队列的第一个元素
//1.先把front对应的值保留到一个临时变量
//2.将front后移
//3.将临时保存的变量返回
int value = arr[front];
front = (front + 1) % maxSize;
return value;
}
//显示队列所有数据
void showQueue() {
if (isEmpty()) {
cout << "队列为空，没有数据。" << endl;
return;
}
//思路：从front开始遍历，遍历多少个元素
for (int i = front; i < front + size(); i++) {
cout << arr[i % maxSize] << endl;//i有可能超过了maxSize,所以要取模
}
}
//求出当前队列的有效数据
int size() {
return (rear + maxSize - front) % maxSize;//取模的原因：因为是环形队列，rear有可能在front的前面，即rear可能比front小
}
//显示队列的头数据，注意不是取出数据
int headQueue() {
if (isEmpty()) {
throw runtime_error("队列为空，没有数据。");
}
return arr[front];
}
};
int main() {
//测试
CircleArray aq(4);//其队列的有效数据最大是3
char key = ' ';//接收用户输入
bool loop = true;
cout << "输入s（show）：显示队列" << endl;
cout << "输入e（exit）：退出程序" << endl;
cout << "输入a（add）：添加数据到队列" << endl;
cout << "输入g（get）：从队列取出数据" << endl;
cout << "输入h（head）：查看队列头的数据" << endl;
while (loop) {
cin >> key;
int value = 0;
switch (key) {
case 's':
aq.showQueue();
break;
case 'a':
cout << "输入一个数" << endl;
cin >> value;
aq.addQueue(value);
break;
case'g':
try {
int res = aq.getQueue();
cout << "取出的数据是" << res << endl;
}
catch (exception e) {
cout << e.what() << endl;
}
break;
case'h':
try {
int res = aq.headQueue();
cout << "队列头的数据是" << res << endl;
}
catch (exception e) {
cout << e.what() << endl;
}
break;
case'e':
cout << "程序退出。" << endl;
loop = false;
break;
default:
break;
}
}
system("pause");
return 0;
}链表是有序的列表，但是它在内存中存储如下
#include<iostream>
using namespace std;
//定义HeroNode，每个Hernode对象就是一个节点
class HeroNode {
public:
int no;
string name;
string nickname;
HeroNode* next;//指向下一个节点
//构造器
HeroNode(int no, string name, string nickname) {
this->no = no;
this->name = name;
this->nickname = nickname;
}
//为了显示方便，我们重写toString
void toString() {
cout << "HeroNode [no=" << no << "，name = " << name << "，nickname = " << nickname << "]" << endl;
}
};
//定义SingleLinkedList管理我们的英雄
class SingleLinkedList {
//先初始化一个头节点，头节点不要动，不存放具体的数据
private:
HeroNode* head = new HeroNode(0, "", "");
public:
//添加节点到单向链表
//第一种方法（直接添加到链表尾部，当不考虑编号顺序时
//1.找到当前链表的最后节点
//2.将最后这个节点的next指向新的节点
void add(HeroNode* heroNode) {
//因为head节点不能动，因此我们需要一个辅助指针遍历temp
HeroNode* temp = head;
//遍历链表，找到最后
while (true) {
//找到链表的最后一个节点
if (temp->next == NULL) {
break;
}
//如果没有找到最后
temp = temp->next;
}
//当退出while循环时，temp就指向了链表的最后一个节点
temp->next = heroNode;
}
//第二种方法（按照编号的顺序添加）
// 1.首先找到新添加的节点的位置，是通过辅助变量（指针），通过遍历来搞定
// 2.新的节点->next = temp->next
// 3.将temp->next = 新的节点
void addByOrder(HeroNode* heroNode) {
//因为头节点不能动，因此我们仍然通过一个辅助指针来帮助找到添加的位置
//因为单链表，我们找的temp是位于添加位置的前一个节点，否则插入不了
HeroNode* temp = head;
bool flag = false;//标志添加的编号是否存在，默认为false
while (true) {
if (temp->next == NULL) {//说明temp已经在链表的最后
break;
}
if (temp->next->no > heroNode->no) {//位置找到，就在temp的后面插入
break;
}
else if (temp->next->no == heroNode->no) {//说明希望添加的heroNode的编号已然存在
flag = true;//说明编号存在
break;
}
temp = temp->next;//后移，遍历当前链表
}
//判断flag的值
if (flag) {//不能添加，说明编号存在
cout << "准备插入的英雄的编号" << heroNode->no << "已经存在了，不能加入" << endl;
}
else {
//插入到链表中，temp的后面
heroNode->next = temp->next;
temp->next = heroNode;
}
}
//修改节点的信息，根据no编号来修改，即no编号不能改
//1.根据 newHeroNode的no来修改即可
void update(HeroNode* newHeroNode) {
//判断是否为空
if (head->next == NULL) {
cout << "链表为空" << endl;
return;
}
//找到需要修改的节点，根据no编号
//定义一个辅助指针
HeroNode* temp = head->next;
bool flag = false;//表示是否找到该节点
while (true) {
if (temp == NULL) {
break;//已经遍历完链表
}
if (temp->no == newHeroNode->no) {
//找到
flag = true;
break;
}
temp = temp->next;
}
//根据flag判断是否找到要修改的节点
if (flag) {
temp->name = newHeroNode->name;
temp->nickname = newHeroNode->nickname;
}
else {//没有找到
cout << "没有找到编号" << newHeroNode->no << "的节点，不能修改。" << endl;
}
}
//从单链表中删除一个节点的思路
//1.我们先找到需要删除的节点的前一个节点temp
//2.temp->next=temp->next->next
//3.被删除的节点，将不会有其他引用指向，会被垃圾回收机制回收
//删除节点
void del(int no) {
HeroNode* temp = head;
bool flag = false;//标志是否找到待删除的节点
while (true) {
if (temp->next == NULL) {
break;
}
if (temp->next->no == no) {
//找到待删除节点的前一个节点
flag = true;
break;
}
temp = temp->next;
}
//判断flag
if (flag) {//找到
temp->next = temp->next->next;
}
else {
cout << "要删除的" <<no << "的节点不存在" << endl;
}
}
//显示链表[遍历]
void list() {
//判断链表是否为空
if (head->next == NULL) {
cout << "链表为空" << endl;
return;
}
//因为头节点不能动，因此我们需要一个辅助指针来遍历
HeroNode* temp = head->next;
while (true) {
//输出节点信息
temp->toString();
//判断是否到链表最后一个结点
if (temp->next == NULL) {
break;
}
//将temp后移，一定小心
temp = temp->next;
}
}
};
int main() {
//进行测试
//先创建节点
HeroNode hero1(1, "宋江", "及时雨");
HeroNode hero2(2, "卢俊义", "玉麒麟");
HeroNode hero3(3, "吴用", "智多星");
HeroNode hero4(4, "林冲", "豹子头");
//创建链表
SingleLinkedList singleLinkedList;
//按照编号的顺序加入
singleLinkedList.addByOrder(&hero1);
singleLinkedList.addByOrder(&hero4);
singleLinkedList.addByOrder(&hero2);
singleLinkedList.addByOrder(&hero3);
singleLinkedList.addByOrder(&hero3);
singleLinkedList.list();
//测试修改节点的代码
HeroNode newHeroNode(2, "小卢", "玉麒麟~~");
singleLinkedList.update(&newHeroNode);
cout << "修改后的链表情况" << endl;
//显示
singleLinkedList.list();
singleLinkedList.del(1);
singleLinkedList.del(4);
singleLinkedList.del(2);
singleLinkedList.del(3);
cout << "删除后的链表情况" << endl;
singleLinkedList.list();
}
//1.获取到单链表的节点的个数（如果是带头节点的链表，需求是不统计头节点）
//head 链表的头节点
//return 返回的就是有效节点的个数
int getLength(HeroNode* head) {
if (head->next == NULL) {//空链表
return 0;
}
int length = 0;
//定义一个辅助变量,这里我们没有统计头节点
HeroNode* cur = head->next;
while (cur != NULL) {
length++;
cur = cur->next;//遍历
}
return length;
}
新浪面试题：
//2.查找单链表中的倒数第k个节点
//（1）编写一个方法，接收head节点，同时接收一个index
//（2）index表示是倒数第index个节点
//（3）先把链表从头到尾遍历，得到链表的总长度getLength()
//（4）得到size后，我们从链表的第一个开始遍历（size-index）个，就可以得到倒数第index个节点
HeroNode* findLastIndexNode(HeroNode* head, int index) {
//判断如果链表为空，返回NULL
if (head->next == NULL) {
return NULL;
}
//第一次遍历得到链表的长度（节点个数）
int size = getLength(head);
//第二次遍历size-index位置，就是我们倒数的第index个节点
//先做一个index的校验
if (index <= 0 || index > size) {
return NULL;
}
//定义一个辅助变量,for循环定位到倒数的index节点
HeroNode* cur = head->next;
for (int i = 0; i < size - index; i++) {
cur = cur->next;
}
return cur;
}
腾讯面试题：
//3.单链表反转
//（1）先定义一个节点HeroNode* reverseHead=new HeroNode()
//（2）从头到尾遍历原来的链表，每遍历一个节点，就将其摘下，并放在新的链表的最前端
//（3）原来的链表的head->next=reverseHead->next
void reverseList(HeroNode* head) {
//如果当前链表为空，或者只有一个节点，无需反转，直接返回
if (head->next == NULL || head->next->next == NULL) {
return;
}
//定义一个辅助指针，帮助我们遍历原来的链表
HeroNode* cur = head->next;
HeroNode* next = NULL;//指向当前节点的下一个节点
HeroNode* reverseHead = new HeroNode(0, "", "");
//遍历原来的链表，每遍历一个节点，就将其摘下，并放在新的链表的最前端
while (cur != NULL) {
next = cur->next;//先暂时保留当前节点的下一个节点，因为后面需要使用，不中断
cur->next = reverseHead->next;//将cur的下一个节点指向新的链表的最前端
reverseHead->next = cur;//将cur连接到新的链表上
cur = next;//让cur后移
}
//将head->next指向reverseHead->next，实现单链表的反转
head->next = reverseHead->next;
}
相当于不断在reverseHead节点和reverseHead的下一个节点之间插入在原链表中遍历的节点，同时还要保证不丢失对原来链表的追踪，保证遍历成功。
百度面试题：
//4.从尾到头打印单链表
//（1）逆序打印单链表
//（2）方式1：先将单链表进行反转操作，然后再遍历即可，这样做的问题是会破坏原来的单链表的结构，不建议
//（3）方式2：可以利用栈，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果
//使用方式2逆序打印单链表
void reversePrint(HeroNode* head) {
if (head->next == NULL) {
return;//空链表，不能打印
}
//创建栈，将各个节点压入栈
stack<HeroNode*>stk;
HeroNode* cur = head->next;
//将链表的所有节点压入栈
while (cur != NULL) {
stk.push(cur);
cur = cur->next;//cur后移，这样就可以压入下一个节点
}
//将栈中的节点进行打印
while (stk.size() > 0) {
stk.top()->toString();
stk.pop();
}
}
双向链表增删改查
1.遍历：和单链表一样，只是可以向前，也可以向后查找
2.添加：（默认添加到双向链表的最后）
（1）先找到双向链表的最后这个节点
（2）temp->next=newHeroNode;
（3）newHeroNode->pre=temp;
3.修改：和单链表一样
4.删除：
（1）因为是双向链表，因此，我们可以自我实现删除某个节点
（2）直接找到要删除的这个节点，比如temp
（3）temp->pre->next=temp->next;
（4）temp->next->pre=temp->pre;
//创建一个双向链表的类
class DoubleLinkedList {
//先初始化一个头节点，头节点不要动，不存放具体的数据
private:
HeroNode* head = new HeroNode(0, "", "");
public:
//返回头节点
HeroNode* getHead() {
return head;
}
//遍历双向链表的方法
//显示链表[遍历]
void list() {
//判断链表是否为空
if (head->next == NULL) {
cout << "链表为空" << endl;
return;
}
//因为头节点不能动，因此我们需要一个辅助指针来遍历
HeroNode* temp = head->next;
while (true) {
//输出节点信息
temp->toString();
//判断是否到链表最后一个结点
if (temp->next == NULL) {
break;
}
//将temp后移，一定小心
temp = temp->next;
}
}
//添加一个节点到双向链表的最后
void add(HeroNode* heroNode) {
//因为head节点不能动，因此我们需要一个辅助指针遍历temp
HeroNode* temp = head;
//遍历链表，找到最后
while (true) {
//找到链表的最后一个节点
if (temp->next == NULL) {
break;
}
//如果没有找到最后
temp = temp->next;
}
//当退出while循环时，temp就指向了链表的最后一个节点
//形成一个双向链表
temp->next = heroNode;
heroNode->pre = temp;
}
//修改一个节点的内容
void update(HeroNode* newHeroNode) {
//判断是否为空,可以看到双向链表的节点内容修改和单向链表一样
if (head->next == NULL) {
cout << "链表为空" << endl;
return;
}
//找到需要修改的节点，根据no编号
//定义一个辅助指针
HeroNode* temp = head->next;
bool flag = false;//表示是否找到该节点
while (true) {
if (temp == NULL) {
break;//已经遍历完链表
}
if (temp->no == newHeroNode->no) {
//找到
flag = true;
break;
}
temp = temp->next;
}
//根据flag判断是否找到要修改的节点
if (flag) {
temp->name = newHeroNode->name;
temp->nickname = newHeroNode->nickname;
}
else {//没有找到
cout << "没有找到编号" << newHeroNode->no << "的节点，不能修改。" << endl;
}
}
//从双向链表中删除一个节点
//1.对于双向链表，我们可以直接找到要删除的节点
//2.找到后自我删除即可
void del(int no) {
//判断当前链表是否为空
if (head->next == NULL) {
cout << "链表为空，无法删除" << endl;
return;
}
HeroNode* temp = head->next;//辅助指针
bool flag = false;//标志是否找到待删除的节点
while (true) {
if (temp == NULL) {//已经到链表的最后
break;
}
if (temp->no == no) {
//找到待删除节点的前一个节点
flag = true;
break;
}
temp = temp->next;//temp后移，遍历
}
//判断flag
if (flag) {//找到
temp->pre->next = temp->next;
//如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
if (temp->next != NULL) {
temp->next->pre = temp->pre;
}
}
else {
cout << "要删除的" << no << "的节点不存在" << endl;
}
}
};
//定义HeroNode，每个Hernode对象就是一个节点
class HeroNode {
public:
int no;
string name;
string nickname;
HeroNode* next;//指向下一个节点，默认为NULL
HeroNode* pre;//指向前一个结点，默认为NULL
//构造器
HeroNode(int no, string name, string nickname) {
this->no = no;
this->name = name;
this->nickname = nickname;
this->next = NULL;
this->pre = NULL;
}
//为了显示方便，我们重写toString
void toString() {
cout << "HeroNode [no=" << no << "，name = " << name << "，nickname = " << nickname << "]" << endl;
}
};
Josephu 问题：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
构建一个单向环形链表
1.先创建第一个节点，让first指向该节点，并形成环形
2.后面当我们每创建一个新的节点，就把该节点加入到已有的环形链表中即可
遍历环形链表
1.先让一个辅助指针指向first节点
2.然后通过一个while循环遍历该环形链表即可，curBoy->next==first时结束
//创建一个Boy类，表示一个节点
class Boy {
private:
int no;//编号
Boy* next;//指向下一个节点，默认NULL
public:
Boy(int no) {
this->no = no;
next = NULL;
}
void setNext(Boy* nextBoy) {
this->next = nextBoy;
}
int getNo()const {
return this->no;
}
Boy* getNext() const{
return this->next;
}
};
//创建一个环形的单向链表
class CircleSingleLinkedList {
private:
//创建一个first节点，当前没有编号
Boy* first = new Boy(-1);
public:
//添加小孩节点，构建成一个环形的链表
void addBoy(int nums) {
//nums 做一个数据校验
if (nums < 1) {
cout << "nums的值不正确" << endl;
return;
}
Boy* curBoy = NULL;//辅助指针，帮助构建环形链表
//使用for循环创建环形链表
for (int i = 1; i <=nums; i++) {
//根据编号创建小孩节点
Boy* boy = new Boy(i);
//如果是第一个小孩
if (i == 1) {
first = boy;
first->setNext(first);//构成环
curBoy = first;//让curBoy指向第一个小孩
}
else {
curBoy->setNext(boy);
boy->setNext(first);
curBoy = boy;
}
}
}
//遍历当前的环形链表
void showBoy(){
//判断链表是否为空
if (first == NULL) {
cout << "没有任何小孩~~" << endl;
}
//因为first不能动，因此我们仍然使用一个辅助指针完成遍历
Boy* curBoy = first;
while (true) {
cout << "小孩的编号：" << curBoy->getNo() << endl;
if (curBoy->getNext() == first) {//说明已经遍历完毕
break;
}
curBoy = curBoy->getNext();
}
}
// n=5，有5个人
// k=1，从编号为1的那个人开始报数
// m=2，每数两次走一人
//1.需要创建一个辅助指针helper，事先应该指向环形链表的最后一个节点
// 报数前，先让first和helper移动k-1次
//2.当小孩报数时，让first和helper指针同时移动m-1次,helper总比first落后一个节点
//3.这时可以将first指向的小孩节点出圈
// first=first->next
// helper->next=first;
// 原来first指向的节点就没有任何引用，就会被回收
//根据用户的输入，生成一个小孩的出圈的顺序
void countBoy(int startNo, int countNum, int nums) {//startNo：从第几个小孩开始数；countNum：数几下；nums：最初有几个小孩
//先对数据进行校验
if (first == NULL || startNo<1 || startNo>nums) {
cout << "参数输入有误，请重新输入" << endl;
return;
}
//创建辅助指针，帮助小孩出圈
Boy* helper = first;
//需要创建一个辅助指针helper，事先应该指向环形链表的最后一个节点
while (true) {
if (helper->getNext() == first) {//说明helper指向最后一个小孩节点
break;
}
helper = helper->getNext();
}
//报数前，先让first和helper移动k - 1次
for (int j = 0; j < startNo - 1; j++) {
first = first->getNext();
helper = helper->getNext();
}
//当小孩报数时，让first和helper指针同时移动m - 1次, helper总比first落后一个节点
//这里是一个循环的操作，直到圈中只有一个节点
while (true) {
if (helper == first) {//说明圈中只有一个节点
break;
}
//让first和helper同时移动countNum-1次
for (int j = 0; j < countNum - 1; j++) {
first = first->getNext();
helper = helper->getNext();
}
//这时first指向的节点，就是要出圈的小孩节点
cout << "小孩" << first->getNo() << "出圈" << endl;
//这时将first指向的小孩节点出圈
first = first->getNext();
helper->setNext(first);
}
cout << "最后留在圈中的小孩编号：" << helper->getNo() << endl;
}
};
int main() {
//测试
CircleSingleLinkedList* cs = new CircleSingleLinkedList();
cs->addBoy(5);
cs->showBoy();
//测试小孩出圈
cs->countBoy(2, 2, 126);//2->4->1->5->3
}
实现栈：
1.使用数组来模拟栈
2.定义一个top来表示栈顶，初始化为-1
3.入栈操作，当有数据加入到栈时，top++;stack[top]=data;
4.出栈的操作，int value=stack[top];top--;return value;
//定义一个ArrayStack表示栈
class ArrayStack {
private:
int maxSize;//栈的大小
int top = -1;//top表示栈顶，初始化为-1
int stack[];//数组，数组模拟栈
public:
//构造器
ArrayStack(int max_Size) {
maxSize = max_Size;
stack[maxSize] = {};
}
//栈满
bool isFull() {
return top == maxSize - 1;
}
//栈空
bool isEmpty() {
return top == -1;
}
//入栈-push
void push(int value) {
//先判断栈是否满
if (isFull()) {
cout << "栈满" << endl;
return;
}
top++;
stack[top] = value;
}
//出栈-pop
void pop() {
if (isEmpty) {
cout << "栈空" << endl;
return;
}
top--;
}
//栈顶-top
int top() {
if (isEmpty()) {
throw new runtime_error("栈空，没有数据");
return;
}
int value = stack[top];
top--;
return value;
}
//遍历栈
void list() {
if (isEmpty()) {
cout << "栈空，没有数据" << endl;
return;
}
for (int i = top; i >= 0; i--) {
cout << stack[i] << endl;
}
}
};栈实现综合计算器：
1.数栈numStack：存放数
2.符号栈operStack：存放运算符
3.通过一个index值（索引），来遍历表达式
4.如果我们发现是一个数字，就直接如数栈
5.如果发现扫描到的是一个符号，就分如下情况
5.1如果发现当前符号栈为空，就直接入栈
5.2如果符号站有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中的操作符，这时就需要从数 栈中top出两个数，再从符号栈中top出一个符号，进行运算，将得到的结果入数栈，然后将当前的操作符入符 号栈
6.当表达式扫描完毕，就顺序地从数栈和符号栈中top出相应的数和符号，并运算
7.最后在数栈只有一个数字，就是表达式的结果
当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数
在处理数，需要向expression给地表达式地index地后再看一位，如果是数就进行扫描，如果是符号才入栈
因此我们需要定义一个字符串变量用于拼接
//将一个逆波兰表达式，依次将数据和运算符放入到ArrayList中
list<char>getListChar(string suffixExpression) {
//将suffixExpression分割
list<char>list;
for (int i = 0; i < suffixExpression.size(); i++) {
list.push_back(suffixExpression[i]);
}
return list;
}
//完成对逆波兰表达式的运算
int calculate(list<char>ls) {
//创建栈，只需要一个栈即可
stack<char>stack;
//遍历ls
for (char item : ls) {
//使用正则表达式来取出数
if (item == '+' || item == '-' || item == '*' || item == '/') {
int num2 = (int)stack.top();
stack.pop();
int num1 = (int)stack.top();
stack.pop();
int res = 0;
if (item == '+') {
res = num1 + num2;
}
else if(item=='-') {
res = num1 - num2;
}
else if (item == '*') {
res = num1 * num2;
}
else if (item == '/') {
res = num1 / num2;
}
//把res入栈
stack.push((char)res);
}
else if(item=='0'|| item == '1' || item == '2' || item == '3' || item == '4' || item == '5' || item == '6' || item == '7' || item == '8' || item == '9' ) {
stack.push(item);
}
else {
throw new runtime_error("运算符有误");
}
}
//最后留在stack中的数据是运算结果
return (int)stack.top();
}
int main() {
//先定义逆波兰表达式
string suffixExpression = "34+5*6-";
//1.先将suffixExpression放到ArrayList中
//2.将ArrayList传递给一个方法，配合栈完成计算
list<char>rpnList = getListChar(suffixExpression);
cout << "rpnList=";
for (auto it = rpnList.begin(); it != rpnList.end(); it++) {
cout << *it;
}
cout << " = " << calculate(rpnList);//29
}
完成将中缀表达式转成后缀表达式
1.“1+((2+3)×4)-5”=>“123+4*+5-”
2.因为直接对字符串进行操作不方便，因此先将字符串转成中缀的list
3.将得到的中缀表达式对应的list转成后缀表达式对应的list
递归调用规则：
1.当程序执行到一个方法时，就会开辟一个独立的空间（栈）
2.每个空间的数据（局部变量）是独立的
1.打印问题
void test(int n){
if(n>2){
test(n-1);//调用自己，形成递归
}
cout<<"n="<<n<<endl;
}
int main() {
test(4);
}
2.阶乘问题
int factorial(int n){
if(n==1){
return 1;
}
else{
return factorial(n-1)*n;
}
}
- 1.执行一个方法时，就创建一个新的受保护的独立空间（栈空间）
- 2.方法的局部变量是独立的，不会相互影响，比如变量
- 3.如果方法中使用的是引用类型变量，就会共享该引用类型的数据
- 4.递归必须向退出递归的条件逼近，否则无限递归
- 5.当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕
回溯：该层走不通，回到上一层栈
//使用递归回溯来给小球找路
//如果小球能到map[6][5]位置，则说明通路找到
//约定：当map[i][j]为0表示该点没有走过；当为1表示墙；为2表示通路可以走；3表示该点已经走过，但是走不通
//在走迷宫时，需要确定一个策略（方法）下->右->上->左，如果该点走不通，再回溯
bool setWay(int map[8][7], int i, int j) {//map表示地图；i、j表示从哪个位置开始；如果找到通路就返回true，否则返回false
if (map[6][5] == 2) {//通路已经找到
return true;
}
else {
if (map[i][j] == 0) {//如果当前这个点还没有走过
//按照下->右->上->左 走
map[i][j] = 2;//假定该点是可以走通的
if (setWay(map, i+1, j)) {//向下走，
return true;
}
else if(setWay(map,i,j+1)) {//向右走
return true;
}
else if (setWay(map, i - 1, j)) {//向上走
return true;
}
else if (setWay(map, i, j - 1)) {//向左走
return true;
}
else {
//说明该点是走不通的，是死路
map[i][j] = 3;
return false;
}
}
else {//如果map[i][j]不等于0，可能是1，2，3；1、3好理解，2也返回false的原因是此时的小球又回到 原先走过的地方，回溯了
return false;
}
}
}
int main() {
//先创建一个二维数组，模拟迷宫
//地图
int map[8][7] = {};
//使用1表示墙
//上下全部置为1
for (int i = 0; i < 7; i++) {
map[0][i] = 1;
map[7][i] = 1;
}
//左右全部置为1
for (int i = 1; i < 7; i++) {
map[i][0] = 1;
map[i][6] = 1;
}
//设置挡板，1表示
map[3][1] = 1;
map[3][2] = 1;
map[1][2] = 1;
map[2][2] = 1;
//输出地图
cout << "地图的情况" << endl;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
cout << map[i][j] << " ";
}
cout << endl;
}
//使用递归回溯给小球找路
setWay(map, 1, 1);
//输出新的地图，小球走过，并标识过的递归
cout << "小球走过，并标识过的地图的情况" << endl;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
cout << map[i][j] << " ";
}
cout << endl;
}
/*1 1 1 1 1 1 1
1 2 0 0 0 0 1
1 2 2 2 0 0 1
1 1 1 2 0 0 1
1 0 0 2 0 0 1
1 0 0 2 0 0 1
1 0 0 2 2 2 1
1 1 1 1 1 1 1*/
}
其实就是小球重新回到走过的地方小球的路径，和程序员设置的找路策略有关。
最短路径：每一步都在往终点靠近
//修改找路策略，改成上->右->下->左
bool setWay2(int map[8][7], int i, int j) {//map表示地图；i、j表示从哪个位置开始；如果找到通路就返回true，否则返回false
if (map[6][5] == 2) {//通路已经找到
return true;
}
else {
if (map[i][j] == 0) {//如果当前这个点还没有走过
//按照下->右->上->左 走
map[i][j] = 2;//假定该点是可以走通的
if (setWay2(map, i - 1, j)) {//向上走，
return true;
}
else if (setWay2(map, i, j + 1)) {//向右走
return true;
}
else if (setWay2(map, i +1, j)) {//向下走
return true;
}
else if (setWay2(map, i, j - 1)) {//向左走
return true;
}
else {
//说明该点是走不通的，是死路
map[i][j] = 3;
return false;
}
}
else {//如果map[i][j]不等于0，可能是1，2，3
return false;
}
}
}
int main() {
//先创建一个二维数组，模拟迷宫
//地图
int map[8][7] = {};
//使用1表示墙
//上下全部置为1
for (int i = 0; i < 7; i++) {
map[0][i] = 1;
map[7][i] = 1;
}
//左右全部置为1
for (int i = 1; i < 7; i++) {
map[i][0] = 1;
map[i][6] = 1;
}
//设置挡板，1表示
map[3][1] = 1;
map[3][2] = 1;
//输出地图
cout << "地图的情况" << endl;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
cout << map[i][j] << " ";
}
cout << endl;
}
//使用递归回溯给小球找路
setWay2(map, 1, 1);
//输出新的地图，小球走过，并标识过的递归
cout << "小球走过，并标识过的地图的情况" << endl;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
cout << map[i][j] << " ";
}
cout << endl;
}
/*1 1 1 1 1 1 1
1 2 2 2 2 2 1
1 0 0 0 0 2 1
1 1 1 0 0 2 1
1 0 0 0 0 2 1
1 0 0 0 0 2 1
1 0 0 0 0 2 1
1 1 1 1 1 1 1*/
}
#include<iostream>
using namespace std;
class Queue8 {
private:
//定义一个max表示共有多少个皇后
int max = 8;
//定义数组arr，保存皇后位置
int arr[8] = {};
public:
static int count;
//编写一个方法，放置第n个皇后
//特别注意：check是每一次递归时，进入到check中都有一次for循环，因此会有回溯
void check(int n) {
if (n == max) {//n=8，其实8个皇后已经放好，因为n从0开始
print();
return;
}
//依次放入皇后，并判断是否冲突
for (int i = 0; i < max; i++) {
//先把当前的皇后n，放入该行的第1列
arr[n] = i;
//判断当放置第n个皇后到i列时，是否冲突
if (judge(n)) {//不冲突
//接着放n+1个皇后，即开始递归
check(n + 1);//回溯：第一次回溯是在n=5的时候，调用check(5)，发现前面5个皇后如果按照 原来的摆法，那么第6个皇后在8列中都没有安身之处，所以check(5)就不继续 递归，因为无法通过judge(5)的判定条件，所以无法调用check(6)，所以退回 上一层栈，此时第一次回溯。所以这就是为什么每次回溯都先调整上一个皇后的 位置
}
//如果冲突，就继续执行for循环；即将第n个皇后放置在本行的后移的一个位置
}
}
//查看当我们放置第n个皇后，就去检测该皇后是否和前面已经摆放的皇后冲突
//n表示第n个皇后
bool judge(int n) {
for (int i = 0; i < n; i++) {
//1.arr[i]==arr[n]表示判断第n个皇后是否和前面的n-1个皇后在同一列
//2.abs(n - i) == abs(arr[n] - arr[i])表示判断第n个皇后是否和前面的n-1个皇后在同一斜线
//3.没必要判断在同一行，因为n在递增
if (arr[i] == arr[n] || abs(n - i) == abs(arr[n] - arr[i])) {
return false;
}
}
return true;
}
//写一个方法，可以将皇后的位置输出
void print() {
count++;
for (int i = 0; i < 8; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
};
int Queue8::count = 0;
int main() {
Queue8 queue8;
queue8.check(0);
cout << "解法数" << queue8.count << endl;
}
void BubbleSort(int arr[], int length) {
int temp = 0;
for (int i = 0; i < length-1; i++) {
for (int j = 0; j < length - i-1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
每经历一层外层for循环，都有一个“最大的数”放置到“最后一个位置”，所以也就可以少比较一个位置（最后）
优化：如果我们发现在某一趟排序中，没有发生一次交换，可以提前结束冒泡排序
void BubbleSort(int arr[], int length) {
int temp = 0;
bool flag = false;//标识变量，表示是否进行过交换
for (int i = 0; i < length-1; i++) {
for (int j = 0; j < length - 1-i; j++) {
if (arr[j] > arr[j + 1]) {
flag = true;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
if (!flag) {
break;
}
else {
flag = false;//重置flag，进行下次判断
}
}
}
void selectSort(int arr[], int length) {
for (int i = 0; i < length-1; i++) {
int minIndex = i;
int min = arr[i];
for (int j = i + 1; j < length; j++) {
if (min > arr[j]) {
min = arr[j];
minIndex = j;
}
}
if (minIndex != i) {
arr[minIndex] = arr[i];
arr[i] = min;
}
}
}
void insertSort(int arr[],int length) {
for (int i = 1; i < length; i++) {
//定义待插入的数
int insertVal = arr[i];
int insertIndex = i - 1;//取arr[i]的前面一个数的下标
//给insertVal找到插入的位置
//1.insertIndex>=0保证在给insertVal找位置时不越界
//2.insertVal<arr[insertIndex]，找插入位置的条件
//3.因为需要将insetVal插入到前面有序的空间中，所以需要空出来一个位置
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];//空出一个位置给insertVal
insertIndex--;
}
//判断是否需要赋值
if (insertIndex + 1 ！= i) {
arr[insertIndex+1] = insertVal;//退出while循环时，arr[inserIndex]<insertVal,而 arr[insertIndex+1]是大于insertVal的，所以需要插 入二者之间，由于 arr[insertIndex+2]=arr[insertIndex+1]，所以直 接赋值即可
}
}
}
//希尔排序（交换式）
void shellSort(int arr[], int length) {
int temp = 0;
for (int gap = length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < length; i++) {
//遍历各组中所有的元素，步长为gap
for (int j = i - gap; j >= 0; j -= gap) {
//如果当前元素大于加上步长后的那个元素，说明交换
if (arr[j] > arr[j + gap]) {
temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
}
}
//对交换式的希尔排序进行优化->移位法
void shellSort2(int arr[], int length) {
//增量gap，并逐步缩小增量
for (int gap = length / 2; gap > 0; gap /= 2) {
//从第gap个元素，逐个对其所在的组进行直接插入排序
for (int i = gap; i < length; i++) {
int j = i;
int temp = arr[j];
if (arr[j] < arr[j - gap]) {
while (j - gap >= 0 && temp < arr[j - gap]) {
//移动
arr[j] = arr[j - gap];
j -= gap;
}
//当退出while后，就给temp找到插入的位置
arr[j] = temp;
}
}
}
}
void quickSort(int arr[], int length, int left, int right) {
int l = left;//左下彪
int r = right;//右下标
int pivot = arr[(left + right) / 2];//中轴值
int temp = 0;//临时变量，用于交换
//while循环的目的是让比pivot值小的放到左边
//比pivot值大的放到右边
while (l < r) {
//在pivot左边一直找，找到大于等于pivot值，才退出
while (arr[l] < pivot) {
l += 1;
}
//在pivot右边一直找，找到小于等于pivot值，才退出
while (arr[r] > pivot) {
r -= 1;
}
if (l >= r) {//说明pivot的左右两边的值，已经按照左边全部是小于等于pivot，而右边全部大于等于 pivot
break;
}
//交换
temp = arr[l];
arr[l] = arr[r];
arr[r] = arr[temp];
//如果交换完后，发现arr[l]=pivot，r--，前移，往中间靠
if (arr[l] == pivot) {
r -= 1;
}
//如果交换完后，发现arr[r]=pivot，l++，后移，往中间靠
if (arr[r] == pivot) {
l += 1;
}
}
//如果l==r，必须l++，r--，否则会出现栈溢出
if (l == r) {
l += 1;
r -= 1;
}
//向左递归
if (left < r) {
quickSort(arr, r - left, left, r);
}
//向右递归
if (right > l) {
quickSort(arr, right - l, l, right);
}
}
void merge(int arr[], int length, int left, int mid, int right, int temp[]) {
int l = left;//左边有序序列的索引
int r = mid + 1;//右边有序序列的索引
int tempIndex = 0;//指向temp数组的当前索引
//（一）
//先把左右两边（有序）的数据按照规则填充到temp数组
//直到左右两边的有序序列的其中一边处理完毕为止
while (l <= mid && r <= right) {
//谁小就先把谁放入临时数组temp
if (arr[l] <= arr[r]) {
temp[tempIndex] = arr[l];
tempIndex++;
l++;
}
else {
temp[tempIndex] = arr[r];
tempIndex++;
r++;
}
}
//（二）
//把有剩余数据的地方依次全部填充到temp
if (l <= mid) {
while (l <= mid) {
temp[tempIndex] = arr[l];
tempIndex++;
l++;
}
}
if (r <= right) {
while (r <= mid) {
temp[tempIndex] = arr[r];
tempIndex++;
r++;
}
}
//（三）
//把temp数组的数据拷入arr
int tempLeft = left;
tempIndex = 0;
while (tempLeft <= right) {
arr[tempLeft] = temp[tempIndex];
tempLeft++;
tempIndex++;
}
}
void mergeSort(int arr[], int length, int left, int right, int temp[]) {
if (left < right) {
int mid = (left + right) / 2;//中间索引
//向左递归进行分解
mergeSort(arr, length, left, mid, temp);
//向右递归进行分解
mergeSort(arr, length, mid+1, right, temp);
//合并
merge(arr, length, left, mid, right, temp);
}
}
int main() {
int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
cout << "归并排序前：" << endl;
for (int i = 0; i < 10; i++) {
cout << arr[i] << " ";
}
cout << endl;
int temp[10] = {};
mergeSort(arr, 10, 0, 9, temp);
cout << "归并排序后：" << endl;
for (int j = 0; j < 10; j++) {
cout << arr[j] << " ";
}
}
稳定性：两个相等的数排序前后相对位置不变
//桶排序是经典的空间换时间的算法
注意事项：一般不用基数排序处理有负数的数组
void radixSort(int arr[], int length) {
int bucket[10][10] = {};//二维数组--桶，每个桶就是一个一维数组
int bucketElementCounts[10] = { 0 };//每个桶里的数据容量
int max = 0;//待排序数组的最大值
for (int i = 0; i < length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
int m_digit = 0;//待排序数组的最大位数
while (max > 0) {
m_digit++;
max /= 10;
}
for (int j = 0,n=1; j < m_digit; j++,n*=10) {
for (int k = 0; k < length; k++) {
//取出每个元素对应位的值
int digit = (arr[k] / n) % 10;
//放入到对应桶中
bucket[digit][bucketElementCounts[digit]] = arr[k];
bucketElementCounts[digit]++;
}
//按照桶的顺序（一维数组的下标）一次取出数据放回原数组中
int index = 0;
for (int l = 0; l < 10; l++) {
//如果桶中有数据才放入数组
if (bucketElementCounts[l] != 0) {
for(int m=0;m<bucketElementCounts[l];m++){
arr[index] = bucket[l][m];
index++;
}
}
//为了模拟桶的数据被取出，我们需要将桶中的数据容量清空
bucketElementCounts[l] = 0;
}
}
}
int main() {
int arr[6] = { 9,78,0,23,567,70 };
cout << "排序前：" << endl;
for (int j = 0; j < 6; j++) {
cout << arr[j] << " ";
}
cout << endl;
int temp[6] = {};
radixSort(arr, 6);
cout << "排序后：" << endl;
for (int j = 0; j < 6; j++) {
cout << arr[j] << " ";
}
}| 排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | In-place | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | In-place | 不稳定 |
| 插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | In-place | 稳定 |
| 希尔排序 | O(nlogn) | O(n(logn)^2) | O(n(logn)^2) | O(1) | In-place | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | Out-place | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn) | In-place | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | In-place | 不稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | Out-place | 稳定 |
| 桶排序 | O(n+k) | O(n+k) | O(n^2) | O(n+k) | Out-place | 稳定 |
| 基数排序 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | Out-place | 稳定 |
int seqSearch(int arr[], int length, int value) {
//线性查找是找逐一比对，找到相同的值就返回下标
for (int i = 0; i < length; i++) {
if (arr[i] == value) {
return i;
}
}
return -1;
}二分查找思路分析：
1.确定数组的中间坐标(mid=left+(right-left)>>1)
2.让findVal与arr[mid]比较
2.1findVal<arr[mid],向左递归
2.2findVal>arr[mid]，向右递归
2.3findVa=arr[mid]，返回mid
3.结束递归条件：
3.1找到：直接返回
3.2未找到：(left>right)时，就需要退出了
使用二分查找的前提：数组必须先排好序
从小到大：
int binarySearch(int arr[], int left, int right, int findVal) {
if (left > right) {//未找到
return -1;
}
int mid = left + (right - left) >> 1;
if (findVal > arr[mid]) {
binarySearch(arr, mid+1, right, findVal);//向右递归
}
else if(findVal<arr[mid]) {
binarySearch(arr, left, mid - 1, findVal);//向左递归
}
else {
return mid;
}
}
完善功能：能够返回多个相同值的下标
思路分析：
1.找到mid时，先不要返回
2.向mid左右两边扫描，将满足findVal的下标放入链表
else{
int temp = mid - 1;
vector<int>resIndexVec;
while (true) {//向左扫描
if (temp < 0 || arr[temp] != findVal) {
break;
}
resIndexVec.push_back(temp);
temp -= 1;
}
resIndexVec.push_back(mid);
temp = mid + 1;
while (true) {//向右扫描
if (temp > length || arr[temp] != findVal) {
break;
}
resIndexVec.push_back(temp);
temp += 1;
}
return resIndexVec;
}
插值查找(二分查找(适应版))
插值查找也只适用于排列好的数组
int insertValueSearch(int arr[], int left, int right, int findVal) {
if (left > right || findVal<arr[0] || findVal>arr[right]) {//mid可能会越界
return -1;
}
int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
if (findVal < arr[mid]) {
return insertValueSearch(arr, left, mid - 1,findVal);
}
else if (findVal > arr[mid]) {
return insertValueSearch(arr, mid + 1, right, findVal);
}
else {
return mid;
}
}
数组需先排好序
注意：每切分成两段，都要从下一段的上半段开始
#include<iostream>
using namespace std;
#include<vector>
const int fibonacciSize = 20;
void fibonacci(vector<int>& F) {
F.push_back(1);
F.push_back(1);
for (int i = 2; i < fibonacciSize; i++) {
F.push_back(F[i - 1] + F[i - 2]);
}
}
int fibonacciSearch(vector<int>numbers, int key) {
int low = 0;
int mid = 0;
int high = numbers.size() - 1;
int k = 0;
vector<int>F;
fibonacci(F);
while (numbers.size() > F[k] - 1) {
k++;
}
vector<int>temp(F[k] - 1);
for (int i = 0; i < temp.size(); i++) {
if (i >= high) {
temp[i] = numbers[high];
}
else {
temp[i] = numbers[i];
}
}
while (low <= high) {
mid = low + F[k - 1] - 1;
if (key < temp[mid]) {
high = mid - 1;
//该条件下，mid要到左段的黄金切割点,由于F[k-1]=F[k-2]+F[k-3]，所以该段的长度为F[k-2]
//下一次，mid=low+F[k-2]-1，所以k-=1。
k -= 1;
}
else if (key > temp[mid]) {
low = mid + 1;
//该条件下，mid要到右段的黄金切割点，由于左半段的长度是F[k-1],右半段的长度自然就是F[k-2]
//F[k-2]=F[k-3]+F[k-4]
//下一次，mid=low+F[k-3]-1,所以k-=2。
k -= 2;
}
else {
return mid < high ? mid : high;
}
}
return -1;
}
int main() {
vector<int>vec = { 1,3,5,7,9,11 };
cout << fibonacciSearch(vec,11) << endl;
} 
图解：
由点到线再到面
//创建雇员
class Emp {
public:
int id;
string name;
Emp* next = NULL;
Emp(int id, string name) {
this->id = id;
this->name = name;
}
};
//创建EmpLinkedList，表示链表
class EmpLinkedList {
private:
Emp* head =new Emp(0,"");//头指针直接指向第一个emp，每个链表的头节点不能为NULL，不然无法添加了
public:
void add(Emp* emp) {
Emp* curEmp = head;
while (curEmp->next) {
curEmp = curEmp->next;
}
curEmp->next = emp;
}
//遍历雇员信息
void list(int no) {
if (!head) {
cout << "链表为空" << endl;
return;
}
cout << "第" << no + 1 << "条链表的信息为：" << endl;
Emp* curEmp = head->next;
while (curEmp) {
cout << "ID：" << curEmp->id << " 姓名：" << curEmp->name << endl;
curEmp = curEmp->next;
}
}
//根据ID查找雇员
Emp* findEmpById(int id) {
if (!head) {
cout << "链表为空" << endl;
return NULL;
}
Emp* curEmp = head;
while (curEmp) {
if (curEmp->id == id) {
return curEmp;
}
curEmp = curEmp->next;
}
return NULL;
}
};
//创建HashTab管理多条链表
class HashTab {
private:
EmpLinkedList empLinkedListArray[100];
public:
//添加雇员
void add(Emp* emp) {
int empLinkedListNo = hashFun(emp->id);
empLinkedListArray[empLinkedListNo].add(emp);
}
//遍历hashTab，遍历所有链表
void list() {
for (int i = 0; i < 100; i++) {
empLinkedListArray[i].list(i);
}
}
//根据id找雇员
void findEmpById(int id) {
int empLinkedListNo = hashFun(id);
Emp* emp = empLinkedListArray[empLinkedListNo].findEmpById(id);
if (!emp) {
cout << "在第" << empLinkedListNo + 1 << "条链表中找到雇员id：" << id << endl;
}
else {
cout << "在哈希表中，没有找到该雇员~" << endl;
}
}
//散列函数
int hashFun(int id) {
return id % 100;
}
};
数组：
- 优点：搜索速度快。
- 缺点：插入值会使整体数组移动，效率低
链表：
- 优点：插入效率高
- 缺点：搜素速度慢
满二叉树：
- 所有叶子节点都在最后一层
- 总结点树为2^n-1(n为层数)
完全二叉树：
- 叶子节点在最后一层或者倒数第二层
- 最后一层叶子节点从左到右不中断
- 倒数第二层叶子节点从右到左不中断
按父节点的输出顺序判断
分析二叉树的前序，中序，后序的遍历步骤
1.创建一棵二叉树
2.前序遍历
2.1先输出当前节点(初始的时候是root节点)
2.2如果左子节点不为空，则递归继续前序遍历
2.3如果右子节点不为空，则递归继续前序遍历
3.中序遍历
3.1如果当前节点的左子节点不为空，则递归中序遍历
3.2输出当前节点
3.3如果当前节点的右子节点不为空，则递归中序遍历
4.后序遍历
4.1如果当前节点的左子节点不为空，则递归后序遍历
4.2如果当前节点的右子节点不为空，则递归后序遍历
4.3输出当前节点
//先创建HeroNode节点
class HeroNode {
private:
int no;
string name;
HeroNode* left=NULL;
HeroNode* right = NULL;
public:
HeroNode(int no, string name) {
this->no = no;
this->name = name;
}
int getNo() {
return no;
}
void setNo(int no) {
this->no = no;
}
string getName() {
return name;
}
void setName(string name) {
this->name = name;
}
HeroNode* getLeft() {
return left;
}
void setLeft(HeroNode* left) {
this->left = left;
}
HeroNode* getRight() {
return right;
}
void setRight(HeroNode*right) {
this->right = right;
}
void toString() {
cout << "no=" << no << " name=" << name << endl;
}
//前序遍历
void preOrder() {
this->toString();//先输出父节点
//递归向左子树前序遍历
if (this->left != NULL) {
this->left->preOrder();
}
//上面递归完成后，栈回收，又回到开始递归的那个节点
//递归向右子树前序遍历
if (this->right != NULL) {
this->right->preOrder();
}
}
//中序遍历
void infixOrder() {
//递归向左子树中序遍历
if (this->left != NULL) {
this->left->infixOrder();
}
//输出父节点
this->toString();
//递归向右子树中序遍历
if (this->right != NULL) {
this->right->infixOrder();
}
}
//后序遍历
void postOrder() {
if (this->left != NULL) {
this->left->postOrder();
}
if (this->right != NULL) {
this->right->postOrder();
}
this->toString();
}
};
//定义BinaryTree 二叉树
class BinaryTree {
private:
HeroNode* root = NULL;
public:
void setRoot(HeroNode* root) {
this->root = root;
}
//前序遍历
void preOrder() {
if (this->root != NULL) {
this->root->preOrder();
}
else {
cout << "二叉树为空，无法遍历" << endl;
}
}
//中序遍历
void infixOrder() {
if (this->root != NULL) {
this->root->infixOrder();
}
else {
cout << "二叉树为空，无法遍历" << endl;
}
}
//后序遍历
void postOrder() {
if (this->root != NULL) {
this->root->postOrder();
}
else {
cout << "二叉树为空，无法遍历" << endl;
}
}
};思路：
前序查找：
1.判断当前节点的no是否等于要查找的
2.如果左子节点不为空，向左递归前序查找
3.如果右子节点不为空，向右递归前序查找
中序查找：
1.如果左子节点不为空，向左递归中序查找
2.判断当前节点的no是否等于要查找的
3.如果右子节点不为空，向右递归中序查找
后序查找：
1.如果左子节点不为空，向左递归中序查找
2.如果右子节点不为空，向右递归中序查找
3.判断当前节点的no是否等于要查找的
//前序查找
HeroNode* preOrderSearch(int no) {
//1.判断当前节点的no是否等于要查找的
//进入前序查找
if (this->no == no) {
return this;
}
//2.如果左子节点不为空，向左递归前序查找,但是要在当前栈创建一个变量接收递归的
HeroNode* resNode = NULL;
if (this->left != NULL) {
resNode = this->left->preOrderSearch(no);
}
if (resNode != NULL) {
return resNode;
}
//3.如果右子节点不为空，向右递归前序查找
if (this->right != NULL) {
resNode = this->right->preOrderSearch(no);
}
//无论找到与否，直接返回resNode即可
return resNode;
}
//中序查找
HeroNode* infixOrderSearch(int no) {
//1.如果左子节点不为空，向左递归中序查找
HeroNode* resNode = NULL;
if (this->left != NULL) {
resNode = this->left->infixOrderSearch(no);
}
if (resNode != NULL) {
return resNode;
}
//2.判断当前节点的no是否等于要查找的
//进入中序查找
if (this->no == no) {
return this;
}
//.如果右子节点不为空，向右递归中序查找
if (this->right != NULL) {
resNode = this->right->infixOrderSearch(no);
}
return resNode;
}
//后序查找
HeroNode* postOrderSearch(int no) {
//1.如果左子节点不为空，向左递归中序查找
HeroNode* resNode = NULL;
if (this->left != NULL) {
resNode = this->left->postOrderSearch(no);
}
if (resNode != NULL) {
return resNode;
}
//2.如果右子节点不为空，向右递归中序查找
if (this->right != NULL) {
resNode = this->right->postOrderSearch(no);
}
if (resNode != NULL) {
return resNode;
}
//3.判断当前节点的no是否等于要查找的
//进入后序查找
if (this->no == no) {
return this;
}
return resNode;
}- 如果删除的是叶子节点，直接删除即可
- 如果删除的节点是非叶子节点，则删除该子树
思路：
首先处理：
如果二叉树是空树，不处理；
如果二叉树只有一个root节点，等价于将二叉树置空
1.因为二叉树是单向的，所以我们是判断当前节点的子节点是否需要删除，而不能判断当前节点是否为需要删除的节点，因为如果当前节点不需要删除，但是已经无法回到父节点了
2.如果当前节点的左子节点不为空，并且左子节点就是要删除的节点，就将this->left=NULL;返回(结束递归)
3.如果当前节点的右子节点不为空，并且右子节点就是要删除的节点，就将this->right=NULL;返回(结束递归)
4.如果第2步和第3步没有删除节点，就向左子树也进行递归删除
5.如果第4步也没有删除节点，就向右子树进行递归删除
类HeroNode中：
void delNode(int no){
//2.如果当前节点的左子节点不为空，并且左子节点就是要删除的节点，就将this->left=NULL;返回(结束 递归)
if(this->left!=NULL&&this->left->no==no){
this->left=NULL;
return;
}
//3.如果当前节点的右子节点不为空，并且右子节点就是要删除的节点，就将this->right=NULL;返回(结束 递归)
if(this->right!=NULL&&this->right->no==no){
this->right=NULL;
return;
}
//4.如果第2步和第3步没有删除节点，就向左子树也进行递归删除
if(this->left!=NULL){
this->left->delNode(no);//先不写return，因为向左子树移动时可能还未删除节点
}
//5.如果第4步也没有删除节点，就向右子树进行递归删除
if(this->right!=NULL){
this->right->delNode(no);
}
}
类BinaryTree中：
void delNode(int no){
if(root!=NULL){
if(root.getNo()==no){
root=NULL;
}else{
//递归删除
root->delNode(no);
}
}else{
cout<<"空树"<<endl;
}
}
class VectorBinaryTree {
private:
vector<int>vec;
public:
VectorBinaryTree(vector<int>vec) {
this->vec = vec;
}
//前序遍历
void preOrder(int index) {
cout << vec[index] << endl;
if ((index * 2 + 1) < vec.size()) {
preOrder(index * 2 + 1);
}
if ((index * 2 + 2) < vec.size()) {
preOrder(index * 2 + 2);
}
}
void preOrder() {
this->preOrder(0);
}
//中序遍历
void infixOrder(int index) {
if ((index * 2 + 1) < vec.size()) {
infixOrder(index * 2 + 1);
}
cout << vec[index] << endl;
if ((index * 2 + 2) < vec.size()) {
infixOrder(index * 2 + 2);
}
}
void infixOrder() {
this->infixOrder(0);
}
//后序遍历
void postOrder(int index) {
if ((index * 2 + 1) < vec.size()) {
postOrder(index * 2 + 1);
}
if ((index * 2 + 2) < vec.size()) {
postOrder(index * 2 + 2);
}
cout << vec[index] << endl;
}
void postOrder() {
this->postOrder(0);
}
};
前序线索二叉树：
按前序遍历的顺序，将拥有空指针的节点的左指针指向前驱节点(即前序遍历数组中该节点的前一个节点)，右指针指向后继节点(即前序遍历数组中该节点的下一个节点)
计算空指针域：
//线索化的目的是让二叉树变成链式结构，本质上就是利用空指针域达到链式的效果，前中后序的数组对应前中后序的线索化二叉树使pre指针能够完美地符合预期一个一个往后移动，太优雅了，目前的我能够理解，但是可能不全面而且费劲
class HeroNode {
private:
int no;
string name;
HeroNode* left = NULL;
HeroNode* right = NULL;
//说明
//1.如果leftType=0，说明表示指向的是左子树，如果是1,则表示指向前驱节点
//2.如果rightType=0，表示指向的是右子树，如果是1，表示指向后继节点
int leftType=0;
int rightType=0;
public:
HeroNode(int no, string name) {
this->no = no;
this->name = name;
}
int getNo() {
return no;
}
void setNo(int no) {
this->no = no;
}
string getName() {
return name;
}
void setName(string name) {
this->name = name;
}
HeroNode* getLeft() {
return left;
}
void setLeft(HeroNode* left) {
this->left = left;
}
HeroNode* getRight() {
return right;
}
void setRight(HeroNode* right) {
this->right = right;
}
int getLeftType() {
return leftType;
}
int getRightType() {
return leftType;
}
void setLeftType(int leftType) {
this->leftType = leftType;
}
void setRightType(int rightType) {
this->rightType = rightType;
}
void toString() {
cout << "no=" << no << " name=" << name << endl;
}
};
//定义ThreadedBinaryTree实现了线索化功能的二叉树
class ThreadedBinaryTree {
private:
HeroNode* root = NULL;
//为了实现线索化，需要创建指向当前节点的前驱节点指针
//在递归进行线索化时，pre总是保留该节点的前驱节点
HeroNode* pre = NULL;
public:
void setRoot(HeroNode* root) {
this->root = root;
}
//前序线索化二叉树
void preThreadedNodes(HeroNode* node) {
if (node == NULL) {
return;
}
if (node->getLeft() == NULL) {
node->setLeft(pre);
node->setLeftType(1);
}
if (pre != NULL && pre->getRight() == NULL) {
pre->setRight(node);
pre->setRightType(1);
}
pre = node;
if (node->getLeftType() == 0) {
preThreadedNodes(node->getLeft());
//注意：这里是preThreadedNodes(node->getLeft());，而不是node->getLeft()->preThreadedNodes()，所以pre指针一直都是root节点的pre指针，所以不会丢失
}
if (node->getRightType() == 0) {
preThreadedNodes(node->getRight());
//注意：这里是preThreadedNodes(node->getRight());，而不是node->getRight()->preThreadedNodes()，所以pre指针一直都是root节点的pre指针，所以不会丢失
}
}
//中序线索化二叉树
void infixThreadedNodes(HeroNode* node) {
//如果node为空，不能线索化
if (node == NULL) {
return;
}
//（一）先线索化左子树
infixThreadedNodes(node->getLeft());
//注意：这里是preThreadedNodes(node->getLeft());，而不是node->getLeft()->preThreadedNodes()，所以pre指针一直都是root节点的pre指针，所以不会丢失
//（二）线索化当前节点
//线索化当前节点的前驱节点
if (node->getLeft() == NULL) {
//让当前节点指向前驱节点
node->setLeft(pre);
//修改当前节点的左指针类型，指向前驱节点
node->setLeftType(1);
}
//处理后继节点
if (pre != NULL && pre->getRight() == NULL) {
//让前驱节点的右指针指向当前节点
pre->setRight(node);
//修改前驱节点的右指针类型
pre->setRightType(1);
}
//！！！ 每处理一个节点后，让当前节点成为下一个节点的前驱节点
pre = node;
//（三）线索化右子树
infixThreadedNodes(node->getRight());
//注意：这里是preThreadedNodes(node->getRight());，而不是node->getRight()->preThreadedNodes()，所以pre指针一直都是root节点的pre指针，所以不会丢失
}
//前序遍历线索化二叉树
void preList() {
HeroNode* node = root;
while (node != NULL) {
node->toString();
while (node->getLeftType() == 0) {
node = node->getLeft();
node->toString();
}
while (node->getRightType() == 1) {
node = node->getRight();
node->toString();
}
node = node->getRight();
}
}
//中序遍历线索化二叉树
void infixList() {
HeroNode* node = root;
while (node != NULL) {
while (node->getLeftType() == 0) {
node = node->getLeft();
}
node->toString();
while (node->getRightType()==1) {
node = node->getRight();
node->toString();
}
node = node->getRight();
}
}
};
大顶堆：把最大的值放到根节点（局部）
小顶堆：把最小的值放到根节点（局部）
先有数组再有树，所以树的结构应该是从上到下，从左到右
个人理解：堆排序有点类似于冒泡排序，每一轮循环都将最大值“沉”到数组最后。
相当于是把数组转换成树，然后通过把树转换成大顶堆（循环adjustSort）的方式把最大值放到根节点，由于 底下的树已经都是大顶堆了，所以只需不断的adjustSort即可
//功能：完成将i对应的非叶子节点的树调整成大顶堆，相当于将以该节点为父节点的树调整成大顶堆
//将一个数组（二叉树）调整成一个大顶堆
//vec：待调整数组
//i：非叶子节点在数组中的索引
//length：待调整元素个数，length在逐渐减少
//因为是为了把最大值放到i节点，所以temp值可以不变，只要有比temp值大的直接交换上来即可，又因为是从下到上的，所以不用担心会错过
void adjustSort(vector<int>& vec, int i, int length) {
int temp = vec[i];//先取出当前元素值，保存在临时变量
for (int k = i * 2 + 1; k < length;k=k*2+1) {//k是i节点的左子节点
if (k+1<length&&vec[k] < vec[k + 1]) {
k++;//左子节点的值小于右子节点的值，让k成为右子节点在数组中的索引
}
if (vec[k] > temp) {
vec[i] = vec[k];//如果子节点的值大于父节点的值，那么就让他们的值互换
i = k;//！！！非常重要
}
else {
break;//因为调整的时候是从左至右、从下到上的，所以下面的都是调整过的，因此直接break即可
}
}
//当for循环结束后，我们已经将以i为父节点的树的最大值放在了最顶（局部）
vec[i] = temp;//将temp值放到调整后的位置
}
void heapSort(vector<int>&vec) {
int temp = 0;
cout << "堆排序！！" << endl;
//将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
for (int i = vec.size() / 2 - 1; i >= 0; i--) {//从左至右，从下至上，之字形从底走到顶
adjustSort(vec, i, vec.size());
}
//将堆顶元素与末尾元素交换，将最大元素“沉”到数组末端
//重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序
for (int j = vec.size() - 1; j > 0; j--) {
temp = vec[0];
vec[0] = vec[j];
vec[j] = temp;
adjustSort(vec, 0, j);
}
for (int i = 0; i < vec.size(); i++) {
cout << vec[i] << " ";
}
}
思路：
1.从小到大进行排序，每个数据都是一个节点，每个节点可以看成是一棵最简单的二叉树
2.取出根节点权值最小的两棵二叉树
3，组成一棵新的二叉树，该新的二叉树的根节点的权值是前面两课二叉树根节点权值的和
4.再将这两棵新的二叉树，以根节点的权值大小再次排序，不断重复 1-2-3-4 的步骤，直到所有数据都被处理，就 得到一棵赫夫曼树
class Node {
public:
int value;
Node* left = NULL;
Node* right = NULL;
Node(int value) {
this->value = value;
}
void toString() {
cout << "value=" << this->value << " ";
}
};
bool myCompare(Node*& node1, Node*& node2) {
return node1->value < node2->value;
}
//创建赫夫曼树的方法
Node* createHuffmanTree(vector<int>& vec) {
//第一步，为了操作方便
//1.遍历vec数组
//2.将vec的每个元素构成一个Node
//3.将Node放入另一个容器中
vector<Node*>nodes;
for (int value : vec) {
nodes.push_back(new Node(value));
}
while (nodes.size() > 1) {
//处理过程是一个循环过程
//排序 从小到大
sort(nodes.begin(), nodes.end(), myCompare);
//取出根节点权值最小的两棵二叉树
//（1）取出权值最小的节点（二叉树）
Node* leftNode = nodes[0];
//（2）取出权值第二小的节点（二叉树）
Node* rightNode = nodes[1];
//（3）构建一棵新的二叉树
Node* parent = new Node(leftNode->value + rightNode->value);
parent->left = leftNode;
parent->right = rightNode;
//（4）从Nodes中删除处理过的二叉树
nodes.erase(nodes.begin());
nodes.erase(nodes.begin());
//（5）将parent加入到nodes
nodes.push_back(parent);
sort(nodes.begin(), nodes.end(), myCompare);
}
//返回赫夫曼树节点
return nodes[0];
}
-
定长编码
-
变长编码
-
赫夫曼编码
思路：
1.创建赫夫曼树
2.根据赫夫曼树，给各个字符规定编码(前缀编码)，向左的路径为0，向右的路径为1
eg.
o:1000，u:10010
由于每个字母的路径必定不同，所以必定是前缀编码(每个字符的编码前缀一定不包含其他字符的编码)
#include<iostream>
using namespace std;
#include<string>
#include<list>
#include<map>
#include<vector>
#include <bitset>
map<int, string>huffmanCodes;
string stringBuilder;
//创建Node，存放数据和权值
class Node {
public:
int data;//存放数据（字符）本身
int weight;//权重
Node* left = NULL;
Node* right = NULL;
Node(char c, int weight) {
this->data = c;
this->weight = weight;
}
void toString() {
cout << "c=" << this->data << " " << "weight=" << this->weight << endl;
}
//前序遍历
void preOrder() {
this->toString();
if (this->left)this->left->preOrder();
if (this->right)this->right->preOrder();
}
};
bool myCompare(Node* node1, Node* node2) {
return node1->weight < node2->weight;
}
list<Node*>getNodes(string str) {
//1.创建一个list
list<Node*>nodes;
//2.存储每个char出现得次数->map[key,value]
multimap<char, int>counts;
for (char& c : str) {
size_t count = counts.count(c);
if (count == 0) {//Map还没有这个字符数据，第一次
counts.insert(pair<char, int>(c, 1));
}
else {
counts.find(c)->second += 1;
}
}
//把每个键值对转成一个Node对象，并加入到nodes集合
for (auto it = counts.begin(); it != counts.end(); it++) {
nodes.push_back(new Node(it->first, it->second));
}
return nodes;
}
Node* createHuffmanTree(list<Node*>nodes) {
while (nodes.size() > 1) {
nodes.sort(myCompare);
Node* leftNode = nodes.front();
nodes.pop_front();
Node* rightNode = nodes.front();
nodes.pop_front();
Node* parent = new Node(NULL, leftNode->weight + rightNode->weight);
parent->left = leftNode;
parent->right = rightNode;
nodes.push_back(parent);
nodes.sort(myCompare);
}
return nodes.front();
}
//生成赫夫曼树对应的赫夫曼编码
//思路：
//1.将赫夫曼编码表存放在map<char,string>，形式：97=100 100=11000
//2.在生成赫夫曼编码表时，需要不停地拼接路径，定义一个StringBuilder存储某个叶子节点的路径
//将传入的node节点的所有叶子节点的赫夫曼编码得到，并放入huffmanCodes集合
//node 传入节点（根节点）
//code 路径：左子节点是0，右子节点是1
void getCodes(Node* node, string code, string str) {//将传入的node节点的所有叶子节点的赫夫曼编码得到，并放入huffmanCodes集合
//将code加入到stringBuilder2
str.append(code);
if (node != NULL) {//如果node==NULL不处理
//判断当前node是叶子节点还是非叶子节点
if (node->data == 0) {
//递归处理
//向左递归
getCodes(node->left, "0", str);
//向右递归
getCodes(node->right, "1", str);
}
else {
huffmanCodes.insert(pair<int, string>(node->data, str));
}
}
}
vector<int> zip(vector<int>vec, map<int, string>huffmanCodes) {
string str1;
string str2;
for (auto& n : vec) {
str1 = huffmanCodes[n];
str1.erase(0,1);
str2 += str1;
}
size_t len = (str2.length() + 7) / 8;
vector<int>huffmanCodeBytes(len);
int index = 0;
for (int i = 0; i < str2.length(); i += 8) {
string strByte;
if (i + 8 > str2.length()) {
strByte = str2.substr(i);
}
else {
strByte = str2.substr(i, i + 8);
}
huffmanCodeBytes[index++] = stoi(strByte, nullptr, 2);
}
return huffmanCodeBytes;
}
string intToString(bool flag, int n) {//flagb标识是否需要补高位
if(flag){
n |= 256;
}
char str[100];
_itoa_s(n, str, 2);
string str2 = str;
if (flag) {
return str2.substr(str2.length() - 8);
}
else {
return str2;
}
}
//赫夫曼编码解压，将数组转换成对应的二进制字符串，如果是最后一个数，则无需补高位
vector<int>decode(map<int, string>huffmanCodes, vector<int>huffmanBytes) {
string str;
for (int i = 0;i<huffmanBytes.size();i++) {
bool flag = (i == huffmanBytes.size() - 1);
str.append(intToString(!flag, huffmanBytes[i]));
}
//把字符串安装指定的赫夫曼编码进行解码
map<string, int>r_map;
for (auto& temp : huffmanCodes) {
r_map.insert(pair<string, int>(temp.second, temp.first));
}
vector<int>resVec;
for (int i = 0; i < str.length();) {
int count = 1;//计数器
bool flag = true;
int b = 0;
while (flag) {
//递增取出key
string key = str.substr(i, i + count);//i不动，让count移动，直到匹配到一个字符
b = r_map[key];
if (b == 0) {
count++;
}
else {
flag = false;
}
}
resVec.push_back(b);
i += count;
}
return resVec;
}
void huffmanZip(string str) {
list<Node*>nodes = getNodes(str);
vector<int>vec;
for (auto& c : str) {
vec.push_back(c);
}
//根据nodes创建赫夫曼树
Node* huffmanTreeRoot = createHuffmanTree(nodes);
//对应的赫夫曼编码
getCodes(huffmanTreeRoot, " ", stringBuilder);
//根据生成的赫夫曼编码，得到压缩后的赫夫曼编码数组
vector<int>huffmanCodeBytes = zip(vec, huffmanCodes);
vector<int>decodeBytes = decode(huffmanCodes, huffmanCodeBytes);
vector<char>str;
for (auto& n : decodeBytes) {
str.push_back(n);
}
}
int main() {
string str = "i like like like java do you like a java";
huffmanZip(str);
system("pause");
return 0;
}
//创建节点
class Node {
public:
int value;
Node* left = NULL;
Node* right = NULL;
Node(int value) {
this->value = value;
}
void toString() {
cout << this->value << endl;
}
//添加节点
//递归的形式添加节点，主义需要满足二叉排序树的要求
void add(Node* node) {
if (!node) return;
//判断传入的节点的值和当前节点值得关系
if (node->value < this->value) {
//如果当前节点的左子节点为空
if (this->left == NULL) {
this->left = node;
}
else {
//递归向左子树添加
this->left->add(node);
}
}
else {//添加的节点的值大于当前节点的值
if (this->right == NULL) {
this->right = node;
}
else {
//递归向右子树添加
this->right->add(node);
}
}
}
//中序遍历
void infixOrder() {
if (this->left != NULL) {
this->left->infixOrder();
}
this->toString();
if (this->right != NULL) {
this->right->infixOrder();
}
}
};
//创建二叉排序树
class BinarySortTree {
private:
Node* root = NULL;
public:
//添加节点的方法
void add(Node* node) {
if (root == NULL) {
root = node;
}
else {
root->add(node);
}
}
//中序遍历
void infixOrder() {
if (root) {
root->infixOrder();
}
else {
cout << "二叉排序树为空" << endl;
}
}
};思路：
1.第一种情况：删除叶子节点
1.1需要先去找到要删除的节点，targetNode
1.2找到targetNode的父节点，parent
1.3确定targetNode是parent的左子节点，还是右子节点
1.4根据前面情况对应删除：
1.4.1如果是左子节点parent->left=NULL;
1.4.2如果是右子节点parent->right=NULL;
2.第二种情况：删除只有一棵子树的节点
2.1需要先去找到要删除的节点，targetNode
2.2找到targetNode的父节点，parent
2.3确定targetNode是左子节点还是右子节点
2.4targetNode是parent的左子节点还是右子节点
2.4.1如果targetNode是parent的左子节点：
2.4.1.1targetNode的子节点是左子节点：parent->left=targetNode->left
2.4.1.2targetNode的子节点是右子节点：parent->left=targetNode->right
2.4.2如果targetNode是parent的右子节点：
2.4.2.1targetNode的子节点是左子节点：parent->right=targetNode->left
2.4.2.2targetNode的子节点是右子节点：parent->right=targetNode->right
3.第三种情况：删除有两棵子树的节点
3.1需要先去找到要删除的节点，targetNode
3.2找到targetNode的父节点，parent
3.3从targetNode的右子树找到值最小的节点，因为要找一个比targetNode左子节点的值大且比targetNode 右子节点的值小的节点来取代targetNode的位置
3.4用一个临时变量temp，将最小节点的值保存
3.5删除该最小节点，targetNode->right=NULL;
3.6targetNode->value=temp;
//创建节点
class Node {
public:
int value;
Node* left = NULL;
Node* right = NULL;
Node(int value) {
this->value = value;
}
//查找要删除的节点
Node* research(int value) {
if (value == this->value) {//就是该节点
return this;
}
else if (value < this->value) {//如果查找的值小于当前节点，向左子树递归
if (this->left == NULL)return NULL;
return this->left->research(value);
}
else {
if (this->right == NULL)return NULL;
return this->right->research(value);
}
}
//查找要删除节点的父节点
Node* searchParent(int value) {
if ((this->left != NULL && this->left->value == value) ||
(this->right != NULL && this->right->value == value)) {
return this;
}
else {
//如果查找的值小于当前节点的值，并且当前节点的左子节点不为空
if (value < this->value && this->left != NULL) {
return this->searchParent(value);//向左子树递归查找
}
else if (value >= this->value && this->right != NULL) {
return this->right->searchParent(value);
}
else {
return NULL;//没有父节点
}
}
}
void toString() {
cout << this->value << " ";
}
//添加节点
//递归的形式添加节点，主义需要满足二叉排序树的要求
void add(Node* node) {
if (!node) return;
//判断传入的节点的值和当前节点值得关系
if (node->value < this->value) {
//如果当前节点的左子节点为空
if (this->left == NULL) {
this->left = node;
}
else {
//递归向左子树添加
this->left->add(node);
}
}
else {//添加的节点的值大于当前节点的值
if (this->right == NULL) {
this->right = node;
}
else {
//递归向右子树添加
this->right->add(node);
}
}
}
//中序遍历
void infixOrder() {
if (this->left != NULL) {
this->left->infixOrder();
}
this->toString();
if (this->right != NULL) {
this->right->infixOrder();
}
}
};
//创建二叉排序树
class BinarySortTree {
private:
Node* root = NULL;
public:
//查找要删除的节点
Node* search(int value) {
if (root == NULL) {
return NULL;
}
else {
return root->searchParent(value);
}
}
//查找父节点
Node* searchParent(int value) {
if (root == NULL) {
return NULL;
}
else {
return root->searchParent(value);
}
}
//1.返回以node为根节点的二叉排序树的最小节点的值
//2.删除以node为根节点的二叉排序树的最小节点
int delRightTreeMin(Node* node) {//node当作一棵二叉排序树的根节点，返回以node为根节点的二叉排序树的最小节点的值
Node* target = node;
//循环查找左节点，就会找到最小值
while (target->left != NULL) {
target = target->left;
}
//这时target就指向了最小节点
//删除最小节点
delNode(target->value);
return target->value;
}
//删除节点
void delNode(int value) {
if (root == NULL)return;
//1.需要先去找到要删除的节点targetNode
Node* targetNode = search(value);
//2.如果没有找到要删除的节点
if (targetNode == NULL) {
cout << "该节点不存在" << endl;
return;
}
//如果该树只有一个节点
if (root->left == NULL && root->right == NULL) {
root = NULL;
return;
}
//寻找targetNode的父节点
Node* parent = searchParent(value);
//删除叶子节点
if (targetNode->left == NULL && targetNode->right == NULL) {
//判断targetNode是父节点的左子节点。还是右子节点
if (parent->left != NULL && parent->left->value == value) {
parent->left = NULL;
}
else if (parent->right != NULL && parent->right->value == value) {
parent->value = NULL;
}
}
else if (targetNode->left!=NULL&&targetNode->right!=NULL) {//删除有两棵子树的节点
int minVal = delRightTreeMin(targetNode->right);
targetNode->value = minVal;
}
else {//删除只有一棵子树的节点，关键：当二叉排序树只剩两个节点时，要注意父节点可能为空
//如果要删除的节点有左子节点
if (targetNode->left != NULL) {
if (parent != NULL) {
//如果targetNode是parent的左子节点
if (parent->left->value == value) {
parent->left = targetNode->left;
}
else {//targetNode是parent的右子节点
parent->right = targetNode->left;
}
}
else {
root = targetNode->left;
}
}
else {
if (parent != NULL) {
//如果targetNode是parent的左子节点
if (parent->left->value == value) {
parent->left = targetNode->right;
}
else {//targetNode是parent的右子节点
parent->right = targetNode->right;
}
}
else {
root = targetNode->right;
}
}
}
}
//添加节点的方法
void add(Node* node) {
if (root == NULL) {
root = node;
}
else {
root->add(node);
}
}
//中序遍历
void infixOrder() {
if (root) {
root->infixOrder();
}
else {
cout << "二叉排序树为空" << endl;
}
}
};
每添加一个节点都要判断一次左右子树的高度差然后相应地进行左右旋转
当右子树高度大于左子树高度时，且高度差大于1：
左旋转：(本质：让一个更适中的数作根节点使得两边的节点数差不多，以此达到平衡)
1.创建一个新的节点，值等于当前根节点的值：Node*newNode=new Node(root->value);
2.把新节点的左子树设置为当前节点的左子树：newNode->left=left;
3.把新节点的右子树设置为当前节点的右子树的左子树：newNode->right=right->left;
4.把当前节点的值换为右子节点的值：value=right->value;
5.把当前节点的右子树设置成右子树的右子树：right=right->right;
6.把当前节点的左子树设置为新节点：left=newNode;
当左子树高度大于左子树高度时，且高度差大于1：
右旋转：
1.创建一个新的节点，值等于当前根节点的值：Node*newNode=new Node(root->value);
2.把新节点的右子树设置为当前节点的右子树：newNode->rihgt=right;
3.把新节点的左子树设置为当前节点的左子树的右子树：newNode->left=left->right;
4.把当前节点的值换为左子节点的值：value=left->value;
5.把当前节点的左子树设置成左子树的左子树：left=left->left;
6.把当前节点的左子树设置为新节点 right=newNode;
问题分析：
1.符合右旋转条件
2.如果当前节点的左子树的右子树高度大于它的左子树的左子树的高度
3.先对当前节点的左节点进行左旋转
4.再对当前节点进行右旋转
//创建节点
class Node {
public:
int value;
Node* left = NULL;
Node* right = NULL;
Node(int value) {
this->value = value;
}
//返回左子树高度
int leftheight() {
if (left == NULL) {
return 0;
}
return left->height();
}
//返回右子树高度
int rightheight() {
if (right == NULL) {
return 0;
}
return right->height();
}
//返回以该节点为根节点的树的高度
int height() {
return max(left ? left->height() : 0, right ? right->height() : 0)+1 ;
}
//左旋转方法
void leftRotate() {
//创建新的节点，以当前根节点的值
Node* newNode = new Node(value);
//把新节点的左子树设置为当前节点的左子树
newNode->left = left;
//把新的节点的右子树设置为当前节点的右子树的左子树
newNode->right = right->left;
//把当前节点的值替换成右子节点的值
value = right->value;
//把当前节点的右子树设置成右子树的右子树
right = right->right;
//把当前节点的左子树设置成新的节点
left = newNode;
}
void rightRotate() {
Node* newNode = new Node(value);
newNode->right = right;
newNode->left = left->right;
value = left->value;
left = left->left;
right = newNode;
}
//查找要删除的节点
Node* research(int value) {
if (value == this->value) {//就是该节点
return this;
}
else if (value < this->value) {//如果查找的值小于当前节点，向左子树递归
if (this->left == NULL)return NULL;
return this->left->research(value);
}
else {
if (this->right == NULL)return NULL;
return this->right->research(value);
}
}
//查找要删除节点的父节点
Node* searchParent(int value) {
if ((this->left != NULL && this->left->value == value) ||
(this->right != NULL && this->right->value == value)) {
return this;
}
else {
//如果查找的值小于当前节点的值，并且当前节点的左子节点不为空
if (value < this->value && this->left != NULL) {
return this->searchParent(value);//向左子树递归查找
}
else if (value >= this->value && this->right != NULL) {
return this->right->searchParent(value);
}
else {
return NULL;//没有父节点
}
}
}
void toString() {
cout << this->value << " ";
}
//添加节点
//递归的形式添加节点，主义需要满足二叉排序树的要求
void add(Node* node) {
if (!node) return;
//判断传入的节点的值和当前节点值得关系
if (node->value < this->value) {
//如果当前节点的左子节点为空
if (this->left == NULL) {
this->left = node;
}
else {
//递归向左子树添加
this->left->add(node);
}
}
else {//添加的节点的值大于当前节点的值
if (this->right == NULL) {
this->right = node;
}
else {
//递归向右子树添加
this->right->add(node);
}
}
//当添加完一个节点后，如果：（右子树的高度-左子树高度）>1，左旋转
if (rightheight() - leftheight() > 1) {
//如果它的右子树的左子树高度大于它的右子树的右子树的高度
if (right != NULL && right->leftheight() > right->rightheight()) {
right->rightRotate();
}
leftRotate();
return;//直接return，不然还要接下去做判断，以免引起不必要的bug
}
//当添加完一个节点，如果（左子树的高度-右子树的高度）>1，右旋转
if (leftheight() - rightheight() > 1) {
//如果它的左子树的右子树高度大于它的左子树的左子树的高度
if (left != NULL && left->rightheight() > left->leftheight()) {
//先对当前这个节点的左节点进行左旋转
left->leftRotate();
}
rightRotate();
return;
}
}
//中序遍历
void infixOrder() {
if (this->left != NULL) {
this->left->infixOrder();
}
this->toString();
if (this->right != NULL) {
this->right->infixOrder();
}
}
};
节点度：该节点的子节点的数量称作节点度
树的度：所有节点中，节点度最大的就是树的度
插入规则： 1.2-3树的所有叶子节点都在同一层（只要是B树都满足这个条件） 2.有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点；三节点同理 3.当按照规则插入一个数到某个节点是，不能满足上面三个要求时，就需要拆，先向上拆，如果上层满，则拆本层， 拆后仍然需要满足上面3个条件 4.对于三节点的子树的值大小仍然遵守（BST二叉排序树）的规则： 4.1三节点的左子节点大小小于三节点中最小的值 4.2三节点的中子节点大小介于三节点中两个值之间 4.3三节点的右子节点大小大于三节点中最大的值
思路：
1.存储顶点用vector<char>
2.保存矩阵用vector<vector<int>>edges，表示边的关系
class Graph {
private:
vector<char>vertex;//存储顶点集合
vector<vector<int>>edges;//存储图对应的领接矩阵
int numOfEdges;//边的数目
public:
//构造器
Graph(int n) {
//初始化矩阵和vertexList
for (int i = 0; i < n; i++) {
edges.push_back(vector<int>(n));
}
numOfEdges = 0;
}
//图中常用的方法
//返回节点个数
int getNumOfVertex() {
return vertex.size();
}
//得到边的数目
int getNumOfEdges() {
return numOfEdges;
}
//返回节点i（下标）对应的数据
char getValueByIndex(int i) {
return vertex[i];
}
//返回[x][y]的权值
int getWeight(int x, int y) {
return edges[x][y];
}
//显示图对应的矩阵
void showGraph() {
for (auto& link : edges) {
cout << "[" << " ";
for (auto& n : link) {
cout << n << " ";
}
cout <<"]"<< endl;
}
}
//插入节点
void insertVertex(char vertex2) {
vertex.push_back(vertex2);
}
//添加边
void insertEdge(int x, int y, int weight) {
edges[x][y] = weight;
edges[x][y] = weight;
numOfEdges++;
}
};
int main() {
int n = 5;//节点的个数
string VertexValue = "ABCDE";
//创建图对象
Graph graph(n);
//循环添加顶点
for (char& c : VertexValue) {
graph.insertVertex(c);
}
//添加边
//A-B A-C B-C B-D B-E
graph.insertEdge(0, 1, 1);
graph.insertEdge(0, 2, 1);
graph.insertEdge(1, 2, 1);
graph.insertEdge(1, 3, 1);
graph.insertEdge(1, 4, 1);
graph.showGraph();
}
思路：
1.vector<list<char>>来存放edges
思路：
1.访问初始节点v，并标记节点v为已访问
2.查找节点v的第一个邻接节点w
3.若w存在，则继续执行4，如果w不存在，则回到第一步，将从v的下一个节点继续
4.若w未被访问，对w进行深度优先遍历递归（即把w当作另一个v，然后进行步骤123）
5.若w已被访问，查找节点v的w邻接节点的下一个邻接节点，转到步骤3
//得到第一个邻接节点的下标w，如果存在就返回对应的下标，否则返回-1
int getFirstNeighbor(int index) {
for (int j = 0; j < vertex.size(); j++) {
if (edges[index][j] > 0) {
return j;
}
}
return -1;
}
//根据前一个邻接节点的下标来获取下一个邻接节点
int getNextNeighbor(int v1, int v2) {
for (int j = v2 + 1; j < vertex.size(); j++) {
if (edges[v1][j] > 0) {
return j;
}
}
return -1;
}
//深度优先遍历算法
//i第一次就是0
void dfs(vector<bool>&isvisited,int i) {
//首先访问该节点，输出
cout << getValueByIndex(i) << "->";
//将该节点设置成已访问
isvisited[i] = true;
//查找i节点的第一个邻接节点
int w = getFirstNeighbor(i);
while (w != -1) {
if (!isvisited[w]) {
dfs(isvisited, w);
}
w = getNextNeighbor(i, w);
}
}
//重载dfs
void dfs() {
for (int i = 0; i < vertex.size(); i++) {
if (!isVisited[i]) {
dfs(isVisited, i);
}
}
}
//对一个节点进行广度优先遍历的方法
void bfs(vector<bool>& isvisited, int i) {
int u=0;//表示队列头的对应下标
int w = 0;//邻接节点w
//队列，记录节点访问的顺序
queue<int>qu;
//能调用该函数，说明该节点可访问，输出节点信息
cout << getValueByIndex(i) << "=>";
//标记为已访问
isvisited[i] = true;
//将节点加入队列
qu.push(i);
while (!qu.empty()) {
//取出队列的头节点下标
u = qu.front();
qu.pop();
//得到第一个邻接节点的下标
w = getFirstNeighbor(u);
while (w != -1) {//找到
//判断w节点是否被访问过
if (!isvisited[w]) {//未被访问过
//输出节点信息
cout << getValueByIndex(w) << "=>";
//标记已被访问
isvisited[w] = true;
//入队
qu.push(w);
}
//如果w已被访问过，那么就以u为前驱节点，找w后面的邻接节点
w = getNextNeighbor(u, w);//体现出广度优先
}
}
}
//重载bfs，遍历所有节点都进行广度优先搜索
void bfs() {
for (int i = 0; i < vertex.size(); i++) {
if (!isVisited[i]) {
bfs(isVisited, i);
}
}
}
int binarySearch(vector<int>& vec, int target) {
int left = 0;
int right = vec.size() - 1;
int mid = 0;
while (left <= right) {
mid = left + (right - left) >> 1;
if (target == vec[mid]) {
return mid;
}
else if(target<vec[mid]) {
right = mid - 1;//因为mid已经和target比较过了，所以下一次比较时不需要再把mid位算上
}
else {
left = mid + 1;
}
}
return -1;
}
思路：
1.如果只有一个盘，A->C
2.如果n>=2，可以看作只有两个盘：最下面的盘…&上面的所有盘
3.移动：
3.1先把最上面的盘A->B
3.2把最下面的盘A->C
3.3把B塔的所有盘从B->C
//汉诺塔的移动方法
//使用分支算法
void hanoiTower(int num, char a, char b, char c) {
if (num == 1) {
cout << a << "->" << c << endl;
}
else {
//如果n >= 2，可以看作只有两个盘：最下面的盘… & 最上面的盘
//先把最上面的所有盘A->B，借助C塔
hanoiTower(num - 1, a,c, b);
//把最下面的盘A->C
cout <<a << "->" << c << endl;
//把B塔的所有盘移动到C，借助A塔
hanoiTower(num - 1, b, a, c);
}
}
思路：
w[i]:weight
v[i]:value
table[i][j]:表示在前i个物品中能够装入容量为j的背包中的最大价值
1.table[i][0]=table[0][j]=0;//表示填入表的第一行和第一列都是0
2.当w[i]>j时:table[i][j]=table[i-1][j]
//当准备加入新增的商品的容量大于当前背包的容量时，就直接使用上一个单元格的装入策略
3.当w[i]<=j时:table[i][j]=table{v[i-1][j],table[i-1][j-w[i]]+v[i]}
//当准备加入的商品的容量小于等于当前背包的容量
装入的方式：
table[i-1][j]:就是上一个单元格装入的最大值
v[i]:表示当前商品的价值
v[i-1][j-w[i]]:装入i-1商品，到剩余空间[j-w[i]]的最大值
int main() {
vector<int>w = { 1,4,3 };//物品的重量
vector<int>v = { 1500,3000,2000 };//物品的价值
int m = 4;//背包的容量
int n = v.size();//物品的个数
//创建二维数组，表
vector<vector<int>>table;
vector<int>temp(m+1);
for (int i = 0; i <= n; i++) {
table.push_back(temp);
}
vector<vector<int>>path = table;//记录商品存放情况
//动态规划处理
for (int i = 1; i < table.size(); i++) {//不处理第一行
for (int j = 1; j < table[0].size(); j++) {//不处理第一列
//公式
if (w[i - 1] > j) {//由于i和j都是从1开始的，所以对应的weight和value会对应的下一个物品，因此，w和v数组对应的i和j都要减1
table[i][j] = table[i - 1][j];
}
else {
if (table[i - 1][j] < v[i - 1] + table[i - 1][j - w[i - 1]]) {
table[i][j] = v[i - 1] + table[i - 1][j - w[i - 1]];
//把当前的情况记录到path
path[i][j] = 1;
}
else {
table[i][j] = table[i - 1][j];
}
}
}
}
for (int i = 0; i < table.size(); i++) {
for (int j = 0; j < table[i].size(); j++) {
cout << table[i][j] << " ";
}
cout << endl;
}
//输出最后放入的是哪些物品
int i=path.size()-1;//行的最大小标
int j=path[0].size()-1;//列的最大下标
while(i>0&&j>0){//从path的最后开始找
if(path[i][j]==1){
cout<<"第"<<i<<"个商品放入到背包"<<endl;
j-=w[i-1];//因为每次往背包加入物品都是建立在前一次放入物品的基础之上，所以要减去当前物品的 重量
}
i--;
}
}
int violenceMatch(string& str1, string& str2) {
int i = 0;
int j = 0;
while (i < str1.length() && j < str2.length()) {
if (str1[i] == str2[j]) {
i++;
j++;
}
else {//回溯，并让j回到初始位
i -= j - 1;
j = 0;
}
}
if (j == str2.length()) {
return i - j;
}
else {
return -1;
}
}
-
字符串的前缀、后缀
eg.bread
- 前缀：b,br,bre,brea
- 后缀：read,ead,ad,d
-
部分匹配值
“前缀”和“后缀”的最长的共有元素的长度
思路：
1.先得到子串的部分匹配表
2.使用部分匹配表完成KMP匹配
//获取一个字符串（子串）的部分匹配值表
vector<int>kmpNext(string dest) {
//创建一个next 数组保存部分匹配值
vector<int>next(dest.length());//如果字符串长度是1，部分匹配值就是0，所以我们可以直接从1开始
for (int i = 1, j = 0; i < dest.length(); i++) {
//当dest[i[!=dest[j]，我们需要从next[j-1]获取新的j
//直到我们发现有dest[i]==dest[j]成立才退出
//这时kmp算法的核心点
while (j > 0 && dest[i] != dest[j]) {
j = next[j - 1];
}
//当dest[i] == dest[j]满足时，部分匹配值+1
if (dest[i] == dest[j]) {
j++;
}
next[i] = j;
}
return next;
}
//写出kmp搜索算法
//str1 源字符串
//str2 子串
//next 子串的部分匹配表
int kmpSearch(string& str1, string& str2, vector<int>& next) {
//遍历
for (int i = 0, j = 0; i < str1.length(); i++) {
//需要处理不相等的情况
//kmp算法核心点
while (j > 0 && str1[i] != str2[j]) {
j = next[j - 1];//此时j位的字符并不和str1匹配，因此真正要处理是j前的子串，不断的让j回到最 大公共前后缀的前缀最后一位，刚好等于j前子串的最后一位，于是就可以直接开 始匹配，无需回溯。也可以理解成将str2往后拉去匹配
}
if (str1[i] == str2[j]) {
j++;
}
if (j == str2.length()) {
return i - j + 1;
}
}
return -1;
}
思路：
1.遍历所有的广播电台，找到一个覆盖了最多“未覆盖的地区“的电台（此电台可能包含一些已覆盖的地区）
2.将这个电台加入到一个集合中，想办法把该电台覆盖的地区在下次比较时去掉
3.重复第一步直到覆盖了全部地区
vector<string>same(vector<string>& vec1, vector<string>& vec2) {//求交集
vector<string>resVec;
for (auto it1 : vec1) {
for (auto it2 : vec2) {
if (it1 == it2) {
resVec.push_back(it2);
}
}
}
return resVec;
}
vector<string>differ(vector<string>& vec1, vector<string>& vec2) {//求交集
vector<string>resVec;
for (auto it1 : vec1) {
for (auto it2 : vec2) {
if (it1 != it2) {
resVec.push_back(it2);
}
}
}
return resVec;
}
int main() {
//创建广播电台，放入map
map<string, vector<string>>broadcasts;
//将各个电台放入到broadcasts
vector<string>vec1{ "北京" ,"上海" ,"天津" };
vector<string>vec2{ "广州", "北京" ,"深圳" };
vector<string>vec3{ "成都" ,"上海" ,"杭州" };
vector<string>vec4{ "上海" ,"天津" };
vector<string>vec5{ "杭州" ,"大连" };
//加入到map
broadcasts.insert(pair<string,vector<string>>("K1", vec1));
broadcasts.insert(pair<string, vector<string>>("K2", vec2));
broadcasts.insert(pair<string, vector<string>>("K3", vec3));
broadcasts.insert(pair<string, vector<string>>("K4", vec4));
broadcasts.insert(pair<string, vector<string>>("K5", vec5));
vector<string>allAreas{ "北京","上海","天津","广州","深圳","成都","杭州","大连" };
//创建vector存放选择的电台集合
vector<string>selects;
//定义临时集合，存放遍历的过程中的电台覆盖的地区和当前还没覆盖的地区的交集
vector<string>temp1;
//定义maxKey，保存在一次遍历过程中，能够覆盖最多未覆盖地区对应的电台key
string maxKey;
while (allAreas.size()>0) {//如果allAreas不为空，则还未覆盖到所有地区
//每进行一次循环，需要置空maxKey和temp1
maxKey = "";
temp1.clear();
//遍历broadcasts，取出对应key
for (auto it : broadcasts) {
string key = it.first;
vector<string>temp2;
//当前能够覆盖的地区
vector<string>areas = broadcasts[key];
temp1 = areas;
temp2 = same(allAreas, areas);//areas和allAreas的交集
//如果当前这个集合包含的未覆盖地区的数量比maxKey指向的集合包含的未覆盖的地区还多
//体现出贪心算法的核心，每次都选择最优的
if (temp2.size() > 0 && (maxKey.length() == 0 || temp2.size() > same(broadcasts[maxKey], allAreas).size())) {
maxKey = key;
}
}
//maxKey不为空的情况下，就应该将maxKey加入selects
if (maxKey.length() > 0) {
selects.push_back(maxKey);
//将maxKey指向的广播电台覆盖的地区从allAreas去掉
allAreas = differ(broadcasts[maxKey], allAreas);
}
}
for (auto it : selects) {
cout << it << " ";
}
}
修路问题的本质就是最小生成树问题
思路：
本质：贪心算法
1.从A顶点（任意顶点开始都行）开始处理，此时顶点集合中只有A点<A>
2.分析A到它连通的各顶点权重为多少：A->c[7],A->G[2],A-B[5]
3.选择权重最小的路径，将对应的另一顶点放入顶点集合中,加入的时候可以记录连接，此时顶点集合中有<A,G>
4.<A,G>开始，将A、G顶点和他们相邻的还没有访问的顶点进行处理
5.A->C[7],A->B[5],G->E[4],G->F[6],G->B[3]
6.此时顶点集合<A,G,B>
7.<A,G,B>开始，将A,G,B和他们相邻的还没有访问的顶点进行处理
8.A->C[7],G-E[4],G->F[6],B->D[9]
9.<A,G,B,E>
......
代码实现：
class MGraph {
public:
int verxs;//表示图的节点个数
string data;//存放节点数据
vector<vector<int>>weight;//存放边，邻接矩阵
MGraph(int verxs) {//构造函数
this->verxs = verxs;
for (int i = 0; i < verxs; i++) {
data.append(" ");
weight.push_back(vector<int>(verxs));
}
}
};
//创建最小生成树->村庄的图
class MinTree {
//创建图的邻接矩阵
public:
void createGraph(MGraph& graph, int verxs, string data, vector<vector<int>>& weight) {
for (int i = 0; i < verxs; i++) {//顶点
graph.data[i] = data[i];
for (int j = 0; j < verxs; j++) {
graph.weight[i][j] = weight[i][j];
}
}
}
void showGraph(MGraph&graph) {
for (auto& it0 : graph.weight) {
for (auto& it1 : it0) {
cout << it1 << " ";
}
cout << endl;
}
}
//编写prim算法，得到最小生成树
void prim(MGraph&graph,int v) {//v表示从图的第几个顶点开始
//visited标记顶点是否被访问过
vector<int>visited(graph.verxs);
//把当前顶点标记为已访问
visited[v] = 1;
//h1和h2记录两个顶点的下标
int h1 = -1;
int h2 = -1;
int minWeight = 10000;//将minWeight初始成一个大数，在遍历过程中会被替换
//因为不是单纯的一次性遍历图，而是需要回溯，每次都要重新从第一个已访问的顶点去分析与各个相邻点的权重
for (int k = 1; k < graph.verxs; k++) {//因为有graph.verxs个顶点，所以有graph.verx-1条边
//确定每一次生成的子图和那个顶点的距离最近
for (int i = 0; i < graph.verxs; i++) {//i表示已访问过的顶点
if (visited[i] == 1) {
for (int j = 0; j < graph.verxs; j++) {//j表示还未访问过的顶点
if (visited[j] == 0 && graph.weight[i][j] < minWeight) {
minWeight = graph.weight[i][j];
h1 = i;
h2 = j;
}
}
}
}
cout << "边<" << graph.data[h1] << "," << graph.data[h2] << ">" << "权值：" << minWeight << endl;
//将h2设置为已访问
visited[h2] = 1;
//重新设置minWeight
minWeight = 10000;
}
}
};
int main() {
string data = "ABCDEFG";
int verxs = data.length();
//邻接矩阵，10000表示两个点不连通
vector<vector<int>>weight = {
{10000,5,7,10000,10000,10000,2},
{5,1000,10000,9,10000,10000,3},
{7,10000,10000,10000,8,10000,10000},
{10000,9,10000,10000,10000,4,10000},
{10000,10000,8,10000,10000,5,4},
{10000,10000,10000,4,5,10000,6},
{2,3,10000,10000,4,6,10000}
};
//创建MGraph对象
MGraph graph(verxs);
////创建一个MinTree对象
MinTree minTree;
minTree.createGraph(graph, verxs, data, weight);
minTree.showGraph(graph);
minTree.prim(graph, 1);
}
终点：
- 就是将所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是“与它连通的最大顶点”
- 因此，接下来，虽然<C,E>是权值最小的边。但是C和E的终点都是F，即它们的终点相同，因此，将<C,E>加入最小生成树的话，会形成回路。这就是判断回路的方式。也就是说，我们加入的边的两个顶点不能都指向同一个终点，否则将构成回路。
//使用INT_MAX表示两个顶点不连通
int INF = INT_MAX;
//创建一个类EData，它的对象实例就表示一条边
class EData {
public:
char start;//边的一个点
char end;//边的另外一个点
int weight;//边的权值
EData()
:start(' '), end(' '), weight(0){}
EData(char start, char end, int weight) {
this->start = start;
this->end = end;
this->weight = weight;
}
void toString() {
cout << "start: " << this->start << " end: " << this->end << " weight: " << this->weight << endl;
}
};
class KruskalCase {
private:
int edgeNum=0;//边的个数
string vertexs;//顶点数组
vector<vector<int>>matrix;//邻接矩阵
public:
KruskalCase(string vertexs, vector<vector<int>>& matrix) {
size_t vlen = vertexs.length();
this->vertexs.append(vertexs);
for (size_t i = 0; i < vlen; i++) {
this->matrix.push_back(vector<int>(vlen));
}
for (size_t i = 0; i < vlen; i++) {
for (size_t j = i+1; j < vlen; j++) {
this->matrix[i][j] = matrix[i][j];
}
}
//统计边
for (size_t i = 0; i < vlen; i++) {
for (size_t j = i+1; j < vlen; j++) {
if (this->matrix[i][j] != INF) {
edgeNum++;
}
}
}
}
vector<EData>& kruskal() {
int index = 0;//表示最后结果数组的索引
vector<int>ends(this->edgeNum);//用于保存“已有最小生成树”中的每个顶点在最小生成树中的终点
//创建结果数组，保存最后的最生成树
vector<EData>rets;
//获取图中所有边的集合，一共有12条边
vector<EData>edges = getEdges();
//按照边的权值大小进行排序（从小到大）
sortEdges(edges);
//遍历edges数组，将边添加到最小生成树中时，判断准备加入的边是否形成了回路，如果没有，就加入rets，否则不能加入
for (int i = 0; i < edgeNum; i++) {
//获取到第i条边的第一个顶点（起点）
int p1 = getPosition(edges[i].start);
//获取到第i条边的第二个顶点
int p2 = getPosition(edges[i].end);
//获取p1这个顶点在已有最小生成树中的终点
int m = getEnd(ends, p1);
//获取p2这个顶点在已有最小生成树中的终点
int n = getEnd(ends, p2);
if (m != n) {//不构成回路
ends[m] = n;//设置m 在“已有最小生成树”中的终点
rets.push_back(edges[i]);//有一条边加入到rets数组
}
}
for (int i = 0; i < rets.size(); i++) {
rets[i].toString();
}
return rets;
}
//打印邻接矩阵
void print() {
cout << "邻接矩阵为：" << endl;
for (int i = 0; i < vertexs.length(); i++) {
for (int j = 0; j < vertexs.length(); j++) {
cout << matrix[i][j] << "\t";
}
cout << endl;
}
}
//对边进行排序处理，冒泡排序
void sortEdges(vector<EData>&edges) {
for (int i = 0; i < edges.size() ; i++) {
for (int j = 0; j < edges.size() - i; j++) {
if (edges[j].weight < edges[j + 1].weight) {
EData temp = edges[j];
edges[j] = edges[j + 1];
edges[j + 1] = temp;
}
}
}
}
int getPosition(char ch) {
for (int i = 0; i < vertexs.length(); i++) {
if (vertexs[i] == ch) {
return i;
}
}
//找不到，返回-1
return -1;
}
//获取图中边，放到EData数组中，后面我们需要遍历该数组
vector<EData>& getEdges() {
vector<EData>edges;
for (int i = 0; i < vertexs.length(); i++) {
for (int j = i + 1; j < vertexs.length(); j++) {
if (matrix[i][j] != INF) {
edges.push_back(EData(vertexs[i], vertexs[j], matrix[i][j]));
}
}
}
return edges;
}
//获取下标为i的顶点的终点,，用于判断两个顶点的终点是否相同
//ends数组记录了各个顶点对应的终点，ends数组实在遍历过程中，逐步形成
int getEnd(vector<int>& ends, int i) {
while (ends[i] != 0) {
i = ends[i];
}
return i;
}
};
int main() {
string vertexs = "ABCDEFG";
vector<vector<int>>matrix = {
{0,12,INF,INF,INF,16,14},
{12,0,10,INF,INF,7,INF},
{INF,10,0,3,5,6,INF},
{INF,INF,3,0,4,INF,INF},
{INF,INF,5,4,0,2,8},
{16,7,6,INF,2,0,9},
{14,INF,INF,INF,8,9,0}
};
//创建KruskalCase对象实例
KruskalCase kruskalCase(vertexs, matrix);
//输出构建的
kruskalCase.print();
kruskalCase.kruskal();
}
广度优先搜索思想
思路：
1.already_arr:记录已访问顶点
2.dis:记录出发顶点到其他顶点的距离
3.pre_visited:记录该顶点的前驱顶点
上述3个集合都会动态更新
class VisitedVertex {
public:
vector<int>already_arr;//记录各个顶点是否访问过 1-访问过，0-未访问过，会动态更新
vector<int>pre_visited;//每个下标对应的值为前一个顶点的下标，会动态更新
vector<int>dis;//记录出发顶点到其他所有顶点的距离，比如G为出发顶点，就会记录F到其他顶点的距离，会动态更新，求的最短距离就会存放到dis
VisitedVertex(){}
VisitedVertex(int length, int index) {//length：顶点个数 index:：起始顶点下标
already_arr = vector<int>(length);
pre_visited = vector<int>(length);
dis = vector<int>(length);
this->already_arr[index] = 1;//设置出发顶点被访问
//初始化dis数组
for (int i = 0; i < dis.size() - 1; i++) {
this->dis[i] = 65535;
}
}
//判断index顶点是否被访问过
bool in(int index) {
return already_arr[index] == 1;
}
//更新出发顶点到index顶点的距离
void updateDis(int index, int len) {
this->dis[index] = len;
}
//更新pre顶点的前驱顶点为index顶点
void updatePre(int pre, int index) {
this->pre_visited[pre] = index;
}
//返回出发顶点到index顶点的距离
int getDis(int index) {
return this->dis[index];
}
//继续访问未访问过的顶点
int updateArr() {
int min = 65535, index = 0;
for (int i = 0; i < already_arr.size(); i++) {
if (already_arr[i] == 0 && dis[i] < min) {
min = dis[i];
index = i;
}
}
//更新index顶点被访问过
already_arr[index] = 1;
return index;
}
//显示最后的结果
//即将三个数组的情况输出
void show() {
for (auto& it0 : already_arr) {
cout << it0 << "\t";
}
cout << endl;
for (auto& it1 : pre_visited) {
cout << it1 << "\t";
}
cout << endl;
for (auto& it2 : dis) {
cout << it2 << "\t";
}
cout << endl;
}
};
class Graph {
private:
string vertrx;//顶点数组
vector<vector<int>>matrix;//邻接矩阵
VisitedVertex vv;//已经访问的顶点的集合
public:
Graph(string vertrx, vector<vector<int>>& matrix) {
this->vertrx = vertrx;
this->matrix = matrix;
}
//显示图
void showGraph() {
for (auto& it0 : matrix) {
for (auto& it1 : it0) {
cout << it1 << "\t";
}
cout << endl;
}
}
//Dijstra算法实现
void dsj(int index) {//index：出发顶点
vv=VisitedVertex(this->vertrx.length(), index);
update(index);
for (int j = 0; j < vertrx.length()-1; j++) {//因为出发顶点已经处理过了，所以处理的顶点数为总顶点数-1
index = vv.updateArr();
update(index);
}
}
//更新index顶点到周围顶点的距离和周围顶点的前驱顶点
void update(int index) {
int len = 0;
//根据遍历邻接矩阵的matrix[index]行
for (int j = 0; j < matrix[index].size(); j++) {
//len：出发顶点到index顶点的距离+从index顶点到j顶点的距离
len = vv.getDis(index) + matrix[index][j];
//如果j顶点没被访问过，并且len小于出发顶点到j顶点的距离，就需要更新
if (!vv.in(j) && len < vv.getDis(j)) {
vv.updatePre(j, index);//更新j顶点的前驱顶点为index顶点
vv.updateDis(j, len);//更新出发顶点到j顶点的距离
}
}
}
void showDijstra() {
vv.show();
}
};
int main() {
string vertrx = "ABCDEFG";
int N = 65535;//表示不连通
//邻接矩阵
vector<vector<int>>matrix = {
{N,5,7,N,N,N,2},
{5,N,N,9,N,N,3},
{7,N,N,N,8,N,N},
{N,9,N,N,N,4,N},
{N,N,8,N,N,5,4},
{N,N,N,4,5,N,6},
{2,3,N,N,4,6,N}
};
Graph graph(vertrx, matrix);
graph.dsj(6);
graph.showDijstra();
}
思路：
1.把各个顶点当作中间顶点后（即过渡点），然后更新表
2.三个for循环
class Graph {
private:
string vertex;//存放顶点
vector<vector<int>>dis;//存放从各个顶点出发到其他顶点的距离
vector<vector<int>>pre;//保存到达目标顶点的前驱顶点
public:
Graph(int length, vector<vector<int>>matrix, string vertex) {
this->vertex = vertex;
this->dis = matrix;
for (int i = 0; i < length; i++) {
this->pre.push_back(vector<int>(length));
}
//对pre数组初始化，注意存放的是前驱顶点的下标
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
pre[i][j] = i;
}
}
}
//显示pre和dis
void show() {
//为了显示便于阅读，优化输出
string vertex = "ABCDEFG";
for (int k = 0; k < dis.size(); k++) {
//先将pre输出
for (int i = 0; i < dis.size(); i++) {
cout << vertex[pre[k][i]] << "\t";
}
cout << endl;
for (int i = 0; i < dis.size(); i++) {
cout << "(" << vertex[k] << "到" << vertex[i] << "的最短路径：" << dis[k][i] << ")";
}
cout << endl;
cout << endl;
}
}
//弗洛伊德算法
void floyd() {
int len = 0;//变量保存距离
//对中间顶点遍历，k就是中间顶点的下标
for (int k = 0; k < dis.size(); k++) {
//从i顶点开始出发
for (int i = 0; i < dis.size(); i++) {
//在j顶点结束
for (int j = 0; j < dis.size(); j++) {
len = dis[i][k] + dis[k][j];
if (len < dis[i][j]) {
dis[i][j] = len;//更新距离
pre[i][j] = pre[k][j];//更新前驱节点
}
}
}
}
}
};
int main() {
string vertex = "ABCDEFG";
int N = 65535;
vector<vector<int>>matrix = {
{0,5,7,N,N,N,2},
{5,0,N,9,N,N,3},
{7,N,0,N,8,N,N},
{N,9,N,0,N,4,N},
{N,N,8,N,0,5,4},
{N,N,N,4,5,0,6},
{2,3,N,N,4,6,0}
};
Graph graph(vertex.length(), matrix, vertex);
graph.floyd();
graph.show();
}
思路：
1.创建棋盘chessBoard，是一个二维数组
2.将当前位置设置为已经访问，然后根据当前位置，计算马还能走哪些位置，并放入到一个集合中，最多有8个位置， 每走一步，step++
3.遍历集合中的所有位置，看看哪个可以走通，如果走通就继续，走不通就回溯
4.判断马是否完成了骑士周游任务（判断条件:将step和应走的步数比较
注意：马儿不同的走法（策略），会得到不同的结果，效率也会被影响（优化）
class Point {
public:
int X;
int Y;
Point()
:X(0),Y(0) {}
Point(int x, int y) {
this->X = x;
this->Y = y;
}
};
class HorseChessboard {
private:
int X;//棋盘的列数
int Y;//棋盘的行数
//创建一个数组，标记棋盘各个位置是否被访问过
vector<bool>visited;
//使用一个属性，标记棋盘的所有位置都被访问
bool finished = false;
public:
HorseChessboard(int x, int y) {
this->X = x;
this->Y = y;
for (int i = 0; i < X * Y; i++) {
visited.push_back(false);
}
}
//hessboard：棋盘
// row:马当前的位置的行，从0开始
// column：马当前位置的列：从0开始
//step：第几步，从1开始
void traversalChessboard(vector<vector<int>>& chessboard, int row, int column, int step) {
chessboard[row][column] = step;
visited[row * X + column] = true;//标记该位置已经访问
//获取当前位置可以走的下一步位置集合
vector<Point>ps;
Point curPoint(column, row);
//判断马能否走以下各个位置
if ((curPoint.X = curPoint.X - 2) >= 0 && (curPoint.Y = curPoint.Y - 1) >= 0) {
ps.push_back(curPoint);
}
if ((curPoint.X = curPoint.X - 1) >= 0 && (curPoint.Y = curPoint.Y - 2) >= 0) {
ps.push_back(curPoint);
}
if ((curPoint.X = curPoint.X + 1) < X && (curPoint.Y = curPoint.Y - 2) >= 0) {
ps.push_back(curPoint);
}
if ((curPoint.X = curPoint.X + 2) < X && (curPoint.Y = curPoint.Y - 1) >= 0) {
ps.push_back(curPoint);
}
if ((curPoint.X = curPoint.X + 2) < X && (curPoint.Y = curPoint.Y + 1) < Y) {
ps.push_back(curPoint);
}
if ((curPoint.X = curPoint.X + 1) < X && (curPoint.Y = curPoint.Y + 2) < Y) {
ps.push_back(curPoint);
}
if ((curPoint.X = curPoint.X - 1) >= 0 && (curPoint.Y = curPoint.Y + 2) < Y) {
ps.push_back(curPoint);
}
if ((curPoint.X = curPoint.X - 2) >= 0 && (curPoint.Y = curPoint.Y + 1) < Y) {
ps.push_back(curPoint);
}
//遍历ps
while (!ps.empty()) {
int x = (*ps.begin()).X;
int y = (*ps.begin()).Y;
Point p(x, y);
ps.erase(ps.begin());
//判断该点是否已经访问
if (p.Y * X + p.X < visited.size()) {
if(!visited[p.Y * X + p.X]) {
traversalChessboard(chessboard, p.Y, p.X, step + 1);
}
}
}
//step<X*Y成立的情况有两种
//1.棋盘到目前位置还没走完
//2.棋盘处于一个回溯过程
if (step < X * Y&&!finished) {//说明这一步不是预期要的，因此回溯的时候应该把这一步的历史记录清掉
chessboard[row][column] = 0;
visited[row * X + column] = false;
}
else {
finished = true;
}
}
};