线性表

同种数据类型的集合，静态列表例如：数组（array），动态列表例如：链表（linked list）

链表

与数组

区别：数组更强调于整块大小固定的、连续的内存空间，并且不可以随意的插入数据，而链表则可以分段并且可以随意改变大小，随意插入数据，更好地利用了内存空间。

对于链表来讲，我们只需要知道第一个节点的地址，便可以环环相扣得到链表上所有的数据。

	数组	链表
内存空间	连续且大小固定	不连续且大小不固定
访问方式（时间复杂度）	直接（低）	遍历链表（高）
内存空间利用	不充分	充分
总结	更容易实现	易出错

单链表

定义节点

struct Node
{
    int data;
    struct Node* link;//c++中直接写Node *
};// 定义节点

创建

Node * A;//头指针 永远
A = NULL;
Node* temp = malloc(sizeof(Node));    //创建节点  对于c++首选new
(*temp).data = 2;    //temp->data=2;
(*temp).link = NULL;    //temp->link=NULL;
A = temp;
temp = new Node();
temp->data=4;
temp->link=NULL;

遍历

 //用循环遍历链表
    Node* temp1=A;
    while(temp1->link!=NULL)
{
    temp1=temp1->link;
}
 //末尾添加节点
  temp = new Node();
  temp->data=4;
  temp->link=NULL;
  temp1->link = temp;

增加节点

头部

struct Node{
  int data;
  struct Node* next;  
};
struct Node* head;
struct Node* Insert(struct Node* head,int x)
{
    Node* temp = (Node*)malloc(sizeof(struct Node));
    temp->data = x;
    temp->next=NULL;
    if(head!=NULL) temp->next = head;
    head = temp;
    return head;
}
int main()
{
    head=Insert(head,2);
    return 0;
}

任意节点

//head=NULL or head!=NULL
//假定链表目前为 2——>4——>6
//要将其变成    2——>4——>8——>6

struct Node{
  int data;
  struct Node* next;  
};
struct Node* head;
void Print(){...}
void Insert(int data,int n)
{
    Node* temp1 = new Node();
    temp1->data = data;
    temp1->next = NULL;
    if(n == 1)//如果插入头部
{
    temp1->next = head;
    head = temp1;
    return ;
}
    Node* temp2 = head;
    for(int i=0;i<n-2;i++)
{
    temp2 = temp2->next;
}
    temp1->next=temp2->next;
    temp2->next = temp1;
}
int main()
{
    head = NULL;
    Insert(2,1);// 2
    Insert(3,2);// 2 3
    Insert(4,1);// 4 2 3
    Insert(5,2);// 4 5 2 3
    Print();
}

删除节点

任意节点

struct Node {
    int data;
    struct Node* next;
};
struct Node* head;
void Insert(int data);
void Print();
void Delete(int n)
{
    struct Node* temp1 = head;
    if (n == 1) {
        head = temp1->next;
        free(temp1);
    }
    else//（前面有节点后面也有 OR 前面有节点后面没有）
    {
        for (int i = 0; i < n - 1; i++)
        {
            temp1 = temp1->next;
        }
        struct Node* temp2 = temp1->next;
        temp1->next = temp2->next;
        free(temp2);//delete temp2;
    }
    return;
}
int main(void)
{
    head = NULL;
    Insert(2);
    Insert(4);
    Insert(6);
    Insert(5);
    int n;
    printf("Enter a position \n");
    scanf("%d", &n);
    Delete(n);
    Print();
    return 0;
}

反转链表

方法一：

遍历，一个节点一个节点的反转

代码：

##include<stdio.h>
##include<malloc.h>
struct Node {
	int data;
	struct Node* next;
};
void Print(struct Node* head)
{
	struct Node* temp = head;
	while (temp->next != NULL)
	{
		printf("%d ", temp->data);
		temp = temp->next;
	}
	printf("%d\n", temp->data);
	return;
}
struct Node* Insert(struct Node* head, int x)
{
	struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
	temp->data = x;
	temp->next = NULL;
	if (head != NULL) temp->next = head;
	head = temp;
	return head;
}
struct Node* Reverse(struct Node* head)
{
	struct Node* current,*prev,*next;
	current = head;
	prev = NULL;
	while (current != NULL)
	{
		next = current->next;
		current->next = prev;
		prev = current;
		current = next;
	}
	head = prev;
	return head;
}
int main(void)
{
	struct Node* head = NULL;
	head=Insert(head, 2);
	head=Insert(head, 4);
	head=Insert(head, 6);
	head=Insert(head, 8);
	Print(head);
	head = Reverse(head);
	Print(head);
	return 0;
}

方法二：

递归

void Reverse(struct Node* p)
{
    if(p->next==NULL)
{
    head = p;
    return;
}
Reverse(p->next);
struct Node* q=p->next;
q->next = p;
p->next = NULL;
}

利用嵌套关系来代替前指针的作用

双向链表

特点

节点有两个指针

struct Node{
  int data;
  struct Node* next; //指向
  struct Node* prev;//指向前节点
};

优点：可以反向查询

缺点：增加了额外内存，对于一样的操作相对于单项链表需要更多的步骤

实现

##include<stdio.h>
##include<stdlib.h>

struct Node {
	int data;
	struct Node* next;
	struct Node* prev;
};
struct Node* head = NULL;
struct Node* GetNewNode(int x)
{
	struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
	temp->data = x;
	temp->next = NULL;
	temp->prev = NULL;
	return temp;
}
void InsertAtHead(int x)//在链首添加
{
	struct Node* newnode = GetNewNode(x);
	if (head == NULL)
	{
		head = newnode;
		head->next = NULL;
		head->prev = NULL;
	}
	else
	{
		head->prev = newnode;
		newnode->next = head;
		newnode->prev = NULL;
		head = newnode;
	}
	return;
}
void InsertAtTail(int x)//在末尾添加
{
	struct Node* newnode = GetNewNode(x);
	struct Node* temp = head;
	if (head == NULL)
	{
		head = newnode;
		head->next = NULL;
		head->prev = NULL;
	}
	else
	{
		while (temp->next != NULL)
		{
			temp = temp->next;
		}
		temp->next = newnode;
		newnode->prev = temp;
		newnode->next = NULL;
	}
}
void Print(void)//打印链表
{
	struct Node* temp = head;
	if (head == NULL)
	{
		printf("NULL\n");
		return;
	}
	while (temp->next != NULL)
	{
		printf("%d ", temp->data);
		temp = temp->next;
	}
	printf("%d\n", temp->data);
	return;
}
void ReversePrint() //逆转链表
{
	struct Node* temp = head;
	if (head == NULL || head->next == NULL)
	{
		printf("Reverse:%d\n", temp->data);
		return;//当链表只有一个或没有节点时
	}
	while (temp->next != NULL)
	{
		temp = temp->next;
	}
	printf("Reverse: ");
	while (temp->prev != NULL)
	{
		printf("%d ", temp->data);
		temp = temp->prev;
	}
	printf("%d\n",temp->data);
	return;
}
int main() {

	head = NULL; 
	InsertAtTail(2); Print(); ReversePrint();
	InsertAtTail(4); Print(); ReversePrint();
	InsertAtHead(6); Print(); ReversePrint();
	InsertAtTail(8); Print(); ReversePrint();
	return 0;
}

循环链表

栈（stack）

特点：封闭性好，使用方便

顺序存储

以存储数字为例，利用数组实现

class sstack
{
private:
	int top;
	char* array;
	int size;
public:
	sstack(int k)
	{
		top = -1;
		size = k;
		array = new char[k]();
	}
	~sstack()
	{
		delete[]array;
	}
	int pop(char& item)
	{
		if (top == -1) return 0;
		item = array[top];
		top--;
		return 1;
	}
	int push(const char item)
	{
		if (top == size - 1) return 0;
		top++;
		array[top] = item;

		return 1;
	}
	int peek(char& item) const
	{
		if (top == -1) return 0;
		item = array[top];
		return 1;
	}
	int isempty(void) const
	{
		if (top == -1) return 1;
		else
			return 0;
	}
	int isfull(void)const
	{
		if (top == size - 1) return 1;
		else
			return 0;
	}
	void clear(void)
	{
		top = -1;
	}
};

链式存储

使用单链表实现

template<class T>
struct SLNode// 节点
{
public:
	T date;
	SLNode<T>* next;
	SLNode() { next = NULL; }
};


template<class T>
class sstack
{
private:
	struct SLNode <T>* top; // 栈顶指针指向表头
public:
	sstack() { top = NULL; } // 构造函数

	~sstack() { clear(); } // 析构函数
	int push(const T item)
	{
		struct SLNode<T>* tmp = new SLNode<T>();
		tmp->date = item;
		tmp->next = top;
		top = tmp;
		return 1;
	}
	int pop(T& item)
	{
		if (top == NULL) return 0;
		else
		{
			item = top->date;
			struct SLNode<T>* tmp = top;
			top = top->next;
			delete tmp;
			return 1;
		}
	}

	int peek(T& item) const
	{
		if (top == NULL) return 0;
		else
		{
			item = top->date;
			return 1;
		}
	}
	int isempty(void) const
	{
		if (top == NULL) return 1;
		else
			return 0;
	}
	void clear(void)
	{
		struct SLNode<T>* p;
		while (top != NULL)
		{
			p = top->next;
			delete top;
			top = p;
		}
		return;
	}
};

比较

在空间复杂性上，顺序栈必须初始就申请固定的空间，当栈不满时，必然造成空间的浪费；链式栈所需空间是根据需要随时申请的，其代价是为每个元素提供空间以存储其next指针域。
在时间复杂性上，对于针对栈顶的基本操作（压入、弹出和栈顶元素存取），顺序栈和链式栈的时间复杂性均为O(1) .

*双栈

template<class T>
class sstack
{
private:
	T* left;
	T* right;
	int size;
	int lefttop;
	int righttop;
public:
	sstack(int k)
	{
		size = k;
		left = new T[k]();
		right = left;
		lefttop = -1;
		righttop = size;
	}
	~sstack() { delete[]left; }
	int push(const T& item, int num)//num选择的栈
	{
		if (righttop == lefttop + 1)
		{
			cout << "full";
			return 0;//栈已经满
		}
		else
		{
			if (num == 0)
			{
				lefttop++;
				left[lefttop] = item;
			}
			else if (num == 1)
			{
				righttop--;
				right[righttop] = item;
			}
			return 1;
		}
	}
	int pop(T& item, int num)
	{
		if (righttop == size && lefttop == -1)
		{
			cout << "双栈为空无法出栈" << endl;
			item = -1;
			return 0;
		}
		else
		{
			if (num == 0)
			{
				if (lefttop == -1)
				{
					cout << "左栈为空无法出栈" << endl;
					item = -1;
					return 0;
				}
				else
				{
					item = left[lefttop];
					lefttop--;
					return 1;
				}
			}
			if (num == 1)
			{
				if (righttop == size)
				{
					cout << "右栈为空无法出栈" << endl;
					item = -1;
					return 0;
				}
				else
				{
					item = right[righttop];
					righttop++;
					return 1;
				}
			}
		}
	}
	int peek(T& item, int num)
	{
		if (num == 0)
		{
			if (lefttop == -1)
			{
				item = -1;
				return 0;
			}
			else
			{
				item = left[lefttop];
				return 1;
			}
		}
		else
		{
			if (righttop == size) { item = -1; return 0; }
			item = right[righttop];
			return 1;
		}
	}
	void clear(int num)
	{
		if (num == 0) lefttop = -1;
		else
			righttop = size;
	}
	int isempty(int num)
	{
		if (num == 0 && lefttop == -1)
		{
			return 1;
		}
		if (num == 1 && righttop == size)
		{
			return 1;
		}
		return 0;
	}
	int isfull(void)
	{
		if (lefttop + 1 == righttop)
		{
			return 1;
		}
		else
			return 0;
	}
};

//测试
int main(void)
{
	int num;
	int x, chose;
	sstack<int> stac(10);
	while (1)
	{
		cout << "选项：push pop peek clear isempty isfull" << endl;
		cin >> num;
		switch (num)
		{
		case(1): cout << "push item  chose:" << endl; cin >> x; cin >> chose; stac.push(x, chose); break;
		case(2):cout << "pop chose:" << endl;  cin >> chose; stac.pop(x, chose); cout << "x=" << x << endl; break;
		case(3):cout << "peek chose:" << endl; cin >> chose; stac.peek(x, chose); cout << "x=" << x << endl; break;
		case(4):cout << "clear chose:" << endl; cin >> chose; stac.clear(chose); break;
		case(5):cout << "empty chose:" << endl; cin >> chose; cout << stac.isempty(chose) << endl; break;
		case(6):cout << "full:" << endl; cout << stac.isfull() << endl; break;
		case(7):return 0;
		}
	}
	return 0;
}

应用

括号匹配

题目一：

有效的括号

存在三种情况：

左括号多于右括号

右括号多于左括号

括号不匹配（左右括号对不上）。

题目二：

移除括号使其有效

##include<iostream>
##include<stack>
##include<string>
using namespace std;

class Solution {
private:
	stack<char*> p1;
public:
	Solution() {}
	string minRemoveToMakeValid(string s)
	{
		char* x;

		for (int i = 0; i <= s.size() - 1; i++)
		{
			if (s[i] == '(')
			{
				p1.push(&s[i]);
			}
			else if (s[i] == ')')
			{
				if (!p1.empty())
				{
					p1.pop();
				}
				else
				{
					s[i] = '#';
				}
			}
		}

		while (p1.empty() == false)
		{
			x = p1.top();
			*x = '#';
			p1.pop();
		}
		string ss;
		for (string::iterator it = s.begin(); it != s.end(); it++)
		{
			if (*it != '#')
				ss.push_back(*it);
		}
		
		return ss;
	}
};

数制转换

数制转换

中缀表达式求值

已知中缀表达式，求值

方法一：中后缀转换，后缀表达式求值

对于高于1位的数字无法处理。

中后缀转换：

如果检测到数字，则直接加入到后缀表达式中

如果检测到运算符时：

若为‘（’，入栈

若为‘）’，则依次将栈中的运算符加入后缀表达式，直到出现‘（’，并从栈中删除‘（’

若为‘+’，‘-’，‘*’，‘/’

栈空，入栈

栈顶元素为‘（’,入栈

高于栈顶元素优先级，入栈

否则，依次弹出栈顶运算符，直到一个优先级比它低的运算符或‘（’为止

遍历完成，若栈非空，依次弹出栈中所有元素

方法二：利用两个栈进行计算

初始化一个操作数栈和一个运算符栈。

从左到右读入中缀表达式，若读到的是操作数，则将其压入操作数栈中。

若读到的是运算符，则和运算符栈栈顶的操作符进行比较：如果优先级比栈顶运算符高，则入栈；如果优先级比栈顶运算符低或者等于，则弹出栈顶运算符，再从操作数栈中弹出 2 个操作数，对其进行运算，将结果压入操作数栈中,重复，直到当前读到的运算符优先级高于运算符栈的栈顶运算符。

若读到的是左括号，则直接入栈；若读到的是右括号，则弹出栈中第一个左括号前所有的运算符，每次同时弹出 2 个操作数进行运算，并将结果压入操作数栈中，最后将左括号弹出。

重复以上过程直到遇到结束符，若此时操作数栈不为空，则将所有操作符弹出，进行和上面相同的运算操作，最终栈顶元素即为计算结果。

long long qpow(long long a, long long n)
{
    long long ans = 1;
    while(n){
        if(n&1)        //如果n的当前末位为1
            ans *= a;  //ans乘上当前的a
        a *= a;        //a自乘
        n >>= 1;       //n往右移一位
    }
    return ans;

class midop
{
private:

	stack<char> ssop;
	stack<long long> ssnum;
	bool tag;
public:
	void littlecalu(long long lh, long long rh, char ch)
	{
		switch (ch)
		{
		case('+'):
		{
			ssnum.push(lh + rh);
			break;
		}
		case('-'):
		{
			ssnum.push(lh - rh);
			break;
		}
		case('*'):
		{
			ssnum.push(lh * rh);
			break;
		}
		case('/'):
		{
			if (rh != 0)
			{
				ssnum.push(lh / rh);
			}
			else
			{
				cout << "INVALID";
				tag = 0;
				return;
			}
			break;
		}
		case('^'):
		{
		long long res = qpow(lh, rh);
			ssnum.push(res);
		}
		}
	}
	bool op_compare(char a, char b)//优先级计算
	{
		long long aa = 0, bb = 0;
		if (a == '+' || a == '-')
		{
			aa = 1;
		}
		if (b == '+' || b == '-')
		{
			bb = 1;
		}
		if (a == '*' || a == '/')
		{
			aa = 2;
		}
		if (b == '*' || b == '/')
		{
			bb = 2;
		}
		if (a == '^')
		{
			aa = 3;
		}
		if (b == '^')
		{
			bb = 3;
		}
		return aa > bb ? true : false
	}
	void caclulate(string str)
	{
		long long i = 0;
		tag = 1;
		long long len = str.size()-1;
		while (i <= len)
		{
			char ch = str[i];
			if (ch >= '0' && ch <= '9')
			{
				ssnum.push(ch - '0');
				i++;
				while (str[i] <= '9' && str[i] >= '0' && i <= len)
				{
					long long tmp = ssnum.top();
					ssnum.pop();
					tmp = tmp * 10 + (str[i] - '0');
					ssnum.push(tmp);
					i++;
				}
			}
			else if (ch == '(')
			{
				ssop.push('(');
				i++;
			}
			else if (ch == ')')
			{
				while (ssop.empty() != true && ssop.top() != '(')
				{
					char ch1 = ssop.top();
					ssop.pop();
					long long lh, rh;
					rh = ssnum.top();
					ssnum.pop();
					lh = ssnum.top();
					ssnum.pop();
					littlecalu(lh, rh, ch1);
					if (!tag) return;//无效则结束计算
				}
				ssop.pop();
				i++;
			}
			else
			{
				if (ssop.empty() != true && ssop.top() != '(' && ssop.top() != ')')
				{
					if (op_compare(ch, ssop.top())) //ch>top
					{
						ssop.push(ch);
						i++;
					}
					else
					{
						while (ssop.empty() != true && !op_compare(ch, ssop.top()))
						{
							char ch1 = ssop.top();
							ssop.pop();
							long long rh = ssnum.top();
							ssnum.pop();
							long long lh = ssnum.top();
							ssnum.pop();
							littlecalu(lh, rh, ch1);
							if (!tag) return;
						}
					}
				}
				else
				{
					ssop.push(ch);
					i++;
				}
			}
		}
		while (!ssop.empty())
		{
			char ch1 = ssop.top();
			ssop.pop();
			long long rh = ssnum.top();
			ssnum.pop();
			long long lh = ssnum.top();
			ssnum.pop();
			littlecalu(lh, rh, ch1);
			if (!tag) return;
		}
		cout << ssnum.top();
	}
};

递归

有些情况下，若采用迭代算法或递归算法的非递归实现，将大大提高效率

八皇后

汉诺塔

BS找最大最小元素

队列（queue）

特点：先进先出，队首删除，队尾插入,与栈类似，队列的封闭性也非常好，使用起来很安全

顺序存储

实现: 使用数组实现队列

初始状态，rear和front均为0

1.删除队首元素

**方法一：**front=front +1

问题：会存在无法利用的空间

方法二：元素向前移动，front始终不变在数组的头部。

问题：效率低下

方法三：循环队列

很好地解决了方法一二的问题。

但要设置参数count计数器判断队列是否满和空

front指向队首位置，删除一个元素就将front顺时针移动一位；front初识化为0
rear指向元素要插入的位置，插入一个元素就将rear顺时针移动一位； rear初始化为0，若指向队尾的元素初始化为-1
count存放队列中元素的个数，当count等于Size时，不可再向队列中插入元素。当count=0时队列为空

class MyCircularQueue {
private:
    int count;//计数器
    int front;
    int rear;//指向队尾的元素初始化为-1
    int size;
    int* array;
public:
    MyCircularQueue(int k) 
    {
        array = new int[k]();
        size = k;
        count = 0;
        front = 0; ////
        rear = -1;////
    }

    bool enQueue(int value)
    {
        if (count == size) return false;
        count++;
        rear = (rear + 1) % size;
        array[rear] = value;
        return true;
    }

    bool deQueue()//删除队首元素
{
	if (count == 0) return false;
	else
	{
		front = (front + 1) % size;
		count--;
		return true;
	}
}

    int Front() 
    {
        if (count == 0) return -1;
        return array[front];
    }

    int Rear() {
        if (count == 0) return -1;
        return array[rear];
    }

    bool isEmpty() {
        if (count == 0) return true;
        else
            return false;
    }

    bool isFull() {
        if (count == size) return true;
        else
            return false;
    }
};

链式存储

实现：使用链表实现

##include<iostream>
struct Node
{
	int date;
	struct Node* next;
};
class Myqueue
{
	struct Node* front;
	struct Node* rear;
	
public:
	
	Myqueue()
	{
		front = NULL;
		rear = NULL;
		
	}

	void push(int item)
	{
        struct Node* tmp = new struct Node;
        tmp->date = item;
		if (rear != NULL)
		{
			rear->next = tmp;
			rear = rear->next;
		}
		else
		{
            front=tmp；
		}
        rear=tmp;
		return;
	}
	int pop(void)
	{
		if (front == NULL)
			return -1;
		int x = front->date;
        struct Node* tmp;
		tmp = front;
		front = front->next;
		delete tmp;
        if(front==NULL) rear=NULL;
		return x;
	}
	int top()
	{
		if (front == NULL) return -1;
		return front->date;
	}
	int empty()
	{
		if (front == NULL) return 1;
		else
			return 0;
	}
};

顺序存储和链式存储

扩展

优先队列

定义与声明

在C++中，priority_queue是一个用于管理具有优先级的队列的容器适配器。它基于堆（通常是最大堆）实现，其中元素按照优先级排列，优先级高的元素在前，支持高效的插入和删除操作。

基本功能和特性

最大堆：默认情况下，priority_queue是一个最大堆，即元素按降序排列。堆顶（top()）是队列中最大或最优先的元素。
接口：
- push()：将元素插入到优先队列中。
- pop()：移除堆顶元素（即最大优先级元素）。
- top()：返回堆顶元素的引用。
- empty()：判断优先队列是否为空。
- size()：返回优先队列中元素的数量。

使用示例

默认情况下，priority_queue使用 std::less<T> 作为比较函数，从而构成最大堆。例如：

#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int> pq;
    
    pq.push(5);
    pq.push(1);
    pq.push(10);
    
    std::cout << "Priority Queue Top: " << pq.top() << std::endl;  // 输出10，因为它是最大值
    
    pq.pop();
    std::cout << "Priority Queue Top after pop: " << pq.top() << std::endl;  // 输出5
    
    return 0;
}

自定义优先级（最小堆）

默认是最大堆，要实现最小堆可以通过std::greater<T>或自定义比较函数：

#include <iostream>
#include <queue>
#include <vector>

int main() {
    // 使用std::greater<int>来实现最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    
    minHeap.push(5);
    minHeap.push(1);
    minHeap.push(10);
    
    std::cout << "Min Heap Top: " << minHeap.top() << std::endl;  // 输出1，因为它是最小值
    
    return 0;
}

自定义结构体和比较规则

如果要对自定义类型（如结构体）使用priority_queue，可以定义一个比较规则：

#include <iostream>
#include <queue>
#include <vector>

struct Task {
    int priority;
    std::string name;
    
    // 定义比较规则
    bool operator<(const Task& other) const {
        return priority < other.priority;  // 按优先级从大到小排序
    }
};

int main() {
    std::priority_queue<Task> tasks;
    
    tasks.push({3, "Low Priority Task"});
    tasks.push({10, "High Priority Task"});
    tasks.push({5, "Medium Priority Task"});
    
    std::cout << "Top Task: " << tasks.top().name << std::endl;  // 输出"High Priority Task"
    
    return 0;
}

总结

默认最大堆：priority_queue默认使用std::less<T>，即最大堆。
自定义堆类型：可以使用std::greater<T>或自定义比较规则实现最小堆。
效率：push()和pop()操作的时间复杂度为O(log n)，适用于需要频繁插入和获取最优先元素的情况。

字符串

模式匹配问题

「朴素模式匹配法」

int BFstringMatching(const string str,const string pattern)
{
    int i=0;
    while(i<=str.size()-pattern.size())
    {
        int j=0;
        while(str[i]==pattern[j]&&j<pattern.size())
        {
            ++i;
            ++j;
		}
        if(j==pattern.size())
        {
            return i-pattern.size();
		}
        return -1;
	}
}

算法分析

「快速模式匹配算法」

b站课程kmp1

b站课程kmp2

对于BF算法的改进，BF算法的效率不高是因为进行了重复的字符比较

算法思想：

是指针i 只前进不后退，避免重复比较，让模式串向后滑动的距离最大化。

失败函数的确定：
求模式串的子串的最大相等子串,即计算前缀后缀相等表——next，next数组只和模式串有关系

next数组表示，当匹配失败的时候应该将j移动到哪个坐标。

void nextfun(string pattern, vector<int>& next)
{
	//生成前缀表
	int len = 0, size = pattern.size(), i = 1;
	next[0] = 0;
	while (i < size)
	{
		if (pattern[i] == pattern[len])
		{
			len++;
			next[i] = len;
			i++;
		}
		else
		{
			if (len > 0)
				len = next[len - 1];
			else
			{
				next[i] = 0;
				i++;
			}
		}
	}
	//前缀表向右移一位，生成next数组
	for (int i = size - 1; i > 0; i--)
	{
		next[i] = next[i - 1];
	}
	next[0] = -1;
}
void kmp_search(string text, string pattern)
{
	int pat_size = pattern.size();
	int text_size = text.size();
	vector<int> next(pat_size);
	nextfun(pattern, next);
	int i = 0, j = 0;//text[i],pattern[j]
	while (i < text_size)
	{
		if (j == pat_size - 1 && text[i] == pattern[j])
		{
			printf("%d\n", i - j);
			//return (i - j);//只找一个匹配的话
			j = next[j];
		}
		if (text[i] == pattern[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
			if (j == -1)
			{
				i++;
				j++;
			}
		}
	}
}

对于next数组的求值，仍存在改进之处：当匹配失败的时候，当前 j 指向的字符和 next[ j ] 指向的字符相等时，会重复比较

因此，可以基于next生成一个nextval数组：

如果位置k的元素与位置next[k]元素相同时，nextval[k]=nextval[next[k]]

如果位置k的元素与位置next[k]元素不同时，nextval[k]= next[k]

void nextfun(string pattern, vector<int>& nextval)
{
	//生成前缀表
	vector<int>next(nextval.size());
	int len = 0, size = pattern.size(), i = 1;
	next[0] = 0;
	while (i < size)
	{
		if (pattern[i] == pattern[len])
		{
			len++;
			next[i] = len;
			i++;
		}
		else
		{
			if (len > 0)
				len = next[len - 1];
			else
			{
				next[i] = 0;
				i++;
			}
		}
	}
	//前缀表向右移一位
	for (int i = size - 1; i > 0; i--)
	{
		next[i] = next[i - 1];
	}
       //基于next生成nextval数组
	nextval[0] = -1;
	for (int i = 1; i < size; i++)
	{
		if (pattern[i] == pattern[next[i]])
			nextval[i] = next[next[i]];
		else
			nextval[i] = next[i];
	}
}

练习：

力扣——找出字符串中第一个匹配项的下标

树

基本操作

1、判树空：TREEEMPTY(T)

2、求根结点：ROOT(T)

3、求树的深度：TREEDEPTH(T)

4、求结点的兄弟节点：同一双亲的孩子互称

5、求结点的双亲：PARENT(T, e)

6、求结点的孩子：CHILD(T, e, i)

7、建立树：CREATE_TREE(T, T1 , T2 , … , Tm )

8、遍历树：TRAVERSAL(T)

二叉树

树与二叉树

二叉树每个结点最多有 2 个子结点，树则无此限制；
二叉树中结点的子树分成左子树和右子树，即使某结点只有一棵子树，也要指明该子树是左子树，还是右子树，就是说二叉树是有序的。

基本性质

二叉树中层数为 i 的结点至多有2^i个，i≥0。

高度为k的二叉树中至多有2^{k+1}-1 (k≥0)个结点。

设T是由n个结点构成的二叉树，其中，叶结点个数为n_0， 度为2的结点个数为n_2，则有:n_0＝n_2+1

满二叉树:一棵非空高度为k ( k >= 0 )的满二叉树，是有2^{k+1} – 1个结点的二叉树

满二叉树的特点是：
① 叶结点都在第k层上；
② 每个分支结点都有两个子结点；
③ 叶结点的个数等于非叶结点个数加1。

一棵有 n 个结点、高为 k 的二叉树 T，一棵高为 k 的满二叉树 T* ，用正整数按层次顺序分别编号 T 和 T* 的所有结点，如果T 之所有结点恰好对应于T*的前 n 个结点，则称 T 为完全二叉树。

存储结构

顺序存储

链式存储

基本操作

中根遍历

力扣： https://leetcode.cn/problems/binary-tree-inorder-traversal/description/?envType=study-plan-v2&envId=top-100-liked

递归算法：


struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
  void inorder(TreeNode* root)
  {
       if (!root) {
           return;
       }
       inorder(root->left);
       cout<<root->val; 
       inorder(root->right);
   }

迭代算法

 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };
stack<TreeNode*> sstack;
void inorderTraversal(TreeNode* root)
{
    while (root != NULL||(!sstack.empty()))
    {
        while (root != NULL)
        {
            sstack.push(root);
            root = root->left;
        }
        TreeNode* p = sstack.top();
        cout<<p->val;
        sstack.pop();
        root = p->right;
    }
    return order;
}

先根遍历

力扣：https://leetcode.cn/problems/binary-tree-preorder-traversal/submissions/478115880/

算法基本等同于中根遍历，只是改了输出顺序，先输出根节点再遍历左右子树。

递归：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
  void preorder(TreeNode* root)
  {
       if (!root) {
           return;
       }
       cout<<root->val; 
       preorder(root->left);
       preorder(root->right);
   }

非递归算法：

 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };
void preorderTraversal(TreeNode* root)
{
    while (root != NULL||(!sstack.empty()))
    {
        while (root != NULL)
        {
            cout<<root->val;
            sstack.push(root);
            root = root->left;
        }
        TreeNode* p = sstack.top();
        sstack.pop();
        root = p->right;
    }
    return ;
}

后根遍历

力扣：https://leetcode.cn/problems/binary-tree-postorder-traversal/submissions/478118154/

递归：与先根中根类似

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
  void postorder(TreeNode* root)
  {
       if (!root) {
           return;
       }
       inorder(root->left);
       inorder(root->right);
       cout<<root->val; 
   }

非递归：

先/中根的非递归算法，一个结点只进出栈一次。结点进栈，表示遍历开始；结点出栈，表示左子树遍历完毕；输出语句的位置为进/出栈时。
后根遍历，输出结点需在遍历完右子树之后；若每个结点还是进出栈一次，无法完成，需多次进出栈。

准备工作栈：

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

struct node
{
	TreeNode* p;
	int num;
	node(TreeNode* root, int num) :p(root), num(num) {}
};


void postorderTraversal(TreeNode* root)
{
    stack<node> sstack;
	if (root == NULL) return ;
	sstack.push(node(root, 0));
	while (!sstack.empty())
	{
		struct node* tmp;
		tmp = &(sstack.top());
		sstack.pop();
		switch (tmp->num)
		{
		case (0):

		{
			tmp->num = 1;
			sstack.push(*tmp);
			if (tmp->p->left != NULL)
			{
				sstack.push(node(tmp->p->left, 0));
			}
			break;
		}

		case(1):
		{
			tmp->num = 2;
			sstack.push(*tmp);
			if (tmp->p->right != NULL)
			{
				sstack.push(node(tmp->p->right, 0));
			}
			break;
		}
		case (2):
		{
			cout << tmp->p->val;
			break;
		}
		}
	}
	return ;
}

或者

力扣官方题解

没有用标识区别是哪一个状态。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        stack<TreeNode *> stk;
        TreeNode *prev = nullptr;              ///用来记录前一个访问的节点
        while (root != nullptr || !stk.empty()) {
            while (root != nullptr) {
                stk.emplace(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            ///////////////////////////////////////////////////
            //到此为止完全和中序遍历完全相同
            ///////////////////////////////////////////////////
           if (root->right == nullptr || root->right == prev)////判断右子树是否访问过或存不存在
           {
                res.emplace_back(root->val);
                prev = root;
                root = nullptr;
            } else {
                stk.emplace(root);
                root = root->right;
            }
        }
        return res;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/binary-tree-postorder-traversal/submissions/478118154/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

层次遍历

力扣：

https://leetcode.cn/problems/binary-tree-level-order-traversal/submissions/480155496/

用队列辅助实现，和广度优先算法有点像，但经过优化，一次性移除一层的节点

我们可以用一种巧妙的方法修改广度优先搜索：
首先根元素入队
当队列不为空的时候
    求当前队列的长度 sis_isi
    依次从队列中取 sis_isi 个元素进行拓展，然后进入下一次迭代
它和普通广度优先搜索的区别在于，普通广度优先搜索每次只取一个元素拓展，而这里每次取 sis_isi 个元素。在上述过程中的第 iii 次迭代就得到了二叉树的第 iii 层的 sis_isi 个元素。

为什么这么做是对的呢？我们观察这个算法，可以归纳出这样的循环不变式：第 iii 次迭代前，队列中的所有元素就是第 iii 层的所有元素，并且按照从左向右的顺序排列。证明它的三条性质（你也可以把它理解成数学归纳法）：
初始化：i=1i = 1i=1 的时候，队列里面只有 root，是唯一的层数为 111 的元素，因为只有一个元素，所以也显然满足「从左向右排列」；
保持：如果 i=ki = ki=k 时性质成立，即第 kkk 轮中出队 sks_ksk 的元素是第 kkk 层的所有元素，并且顺序从左到右。因为对树进行广度优先搜索的时候由低 kkk 层的点拓展出的点一定也只能是 k+1k + 1k+1 层的点，并且 k+1k + 1k+1 层的点只能由第 kkk 层的点拓展到，所以由这 sks_ksk 个点能拓展到下一层所有的 sk+1s_{k+1}sk+1 个点。又因为队列的先进先出（FIFO）特性，既然第 kkk 层的点的出队顺序是从左向右，那么第 k+1k + 1k+1 层也一定是从左向右。至此，我们已经可以通过数学归纳法证明循环不变式的正确性。
终止：因为该循环不变式是正确的，所以按照这个方法迭代之后每次迭代得到的也就是当前层的层次遍历结果。至此，我们证明了算法是正确的。
作者：力扣官方题解

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector <vector <int>> ret;
        if (!root) {
            return ret;
        }

        queue <TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int currentLevelSize = q.size();
            ret.push_back(vector <int> ());
            for (int i = 1; i <= currentLevelSize; ++i)  {//移除处理本层所有节点
                auto node = q.front(); q.pop();
                ret.back().push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        
        return ret;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

创建二叉树

先根序列和中根序列可以确定
后根序列和中根序列可以确定
先根序列和后根序列不能确定

已知含空指针的先根序列

递归实现，规定所给的先序序列如果有空指针则用 ”#“ 标识

class solution
{
private:
	struct TreeNode* root;
	char* arry;
	int size;
	int point;//读到字符串的第几个了
public:
	solution(char* arr, int si) :arry(arr), size(si)
	{
		root = NULL;
		point = 0;
	}
	struct TreeNode* creatBinTree(void)
	{
		if (arry[point] == '#' || point > size - 1)
		{
			point++;
			return NULL;
		}
		else
		{
			struct TreeNode* tmp = new struct TreeNode;
			tmp->val = arry[point];
			if (point == 0) root = tmp;
			point++;
			tmp->left = creatBinTree();
			tmp->right = creatBinTree();

			return tmp;
		}
	}
};

已知中根和后根序列

pta：

给定非空二叉树的中根序列和后根序列，请编写程序创建该二叉树，计算其高度和先根序列；如给定的中根和后根序列不合法，则亦能识别。

合法性

长度要相同，可以都为0

任一字母的中序序列和后序序列左右元素相同，顺序可以不一致，通过递归实现

已知先根和中根序列

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

复制二叉树

用遍历的方式进行复制

以后序遍历为例子

**复制过程：**先复制子结点，再复制父结点，然后将父结点与子结点链接起来。

struct TreeNode* copy(struct TreeNode* tmp, struct TreeNode* tmp1)
	{
		tmp1 = new struct TreeNode;
		if (tmp == NULL) return NULL;
		if (tmp->left != NULL) 	tmp1->left = copy(tmp->left, tmp1->left);
		if (tmp->right != NULL)    tmp1->right = copy(tmp->right, tmp1->right);

		tmp1->val = tmp->val;
		return tmp1;
	}

计算树的高度

注意根节点是第0层还是第1层

int high(struct Node* root)//根所在的是第一层
{
	int h1, h2;
	if (root)
	{
		h1 = high(root->left);
		h2 = high(root->right);
		return h1 > h2 ? h1 + 1 : h2 + 1;
	}
	else return 0;
}

计算树的路径

练习

112. 路径总和 - 力扣（LeetCode）

//递归
class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root == nullptr) {
            return false;
        }
        if (root->left == nullptr && root->right == nullptr) {
            return sum == root->val;
        }
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/path-sum/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

//非递归  广度优先搜索
class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root == nullptr) {
            return false;
        }
        queue<TreeNode *> que_node;
        queue<int> que_val;
        que_node.push(root);
        que_val.push(root->val);
        while (!que_node.empty()) {
            TreeNode *now = que_node.front();
            int temp = que_val.front();
            que_node.pop();
            que_val.pop();
            if (now->left == nullptr && now->right == nullptr) {
                if (temp == sum) {
                    return true;
                }
                continue;
            }
            if (now->left != nullptr) {
                que_node.push(now->left);
                que_val.push(now->left->val + temp);
            }
            if (now->right != nullptr) {
                que_node.push(now->right);
                que_val.push(now->right->val + temp);
            }
        }
        return false;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/path-sum/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

113. 路径总和 II - 力扣（LeetCode）

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;

    void dfs(TreeNode* root, int targetSum) {
        if (root == nullptr) {
            return;
        }
        path.emplace_back(root->val);
        targetSum -= root->val;
        if (root->left == nullptr && root->right == nullptr && targetSum == 0) {
            ret.emplace_back(path);
        }
        dfs(root->left, targetSum);
        dfs(root->right, targetSum);
        path.pop_back();
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        dfs(root, targetSum);
        return ret;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/path-sum-ii/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处

437. 路径总和 III - 力扣（LeetCode）

我的思路：暴利破解，遍历每个节点之后递归搜索有无路径满足

改进算法：

前缀和，

PTA：

编写程序找出二叉树中和最大的路径，二叉树结点为不等于0的整数。本题的“路径”限定为以根结点为起点，以叶结点为终点的路径。路径的和，即该路径所包含的所有结点的数据值之和。

输入格式:

输入为一组用空格间隔的整数，个数不超过100个，表示带空指针信息的二叉树先根序列。

输出格式:

输出为两行，第一行为该二叉树路径和的最大值，第二行为一组整数，每个整数后一个空格，即该最大路径包含的结点值（按从根的叶的顺序），如果存在多条满足条件路径，则输出最左边一条。

输入样例1:

1	1 2 0 0 3 0 0

输出样例1:

1
2

4
1 3

输入样例2:

1	-1 2 0 0 3 0 0

输出样例2:

1
2

2
-1 3

查找给定结点的父结点

遍历的同时进行比较

struct TreeNode* Father(struct TreeNode* root,int value)
{
    if (!root || (root->left == NULL && root->right == NULL)) {
        return NULL;
    }
    if (root->left != NULL)
    {
        if (value == root->left->val) return root;
    }
    if (root->right != NULL)
    {
        if (value == root->right->val) return root;
    }
    struct TreeNode* res = Father(root->left, value);
    struct TreeNode* res1 = Father(root->right, value);
    if (res != NULL) return res;
    else return res1;
}

查找符合数据域条件的结点

遍历的同时进行比较

例如：采用递归前序遍历进行查找

struct TreeNode* Find(struct TreeNode*root,int value)
{
	if (!root){return NULL; }
	if (value == root->val) return root;
	findpreorder(root->left, value);
	findpreorder(root->right, value);
}

释放二叉树

遍历的同时进行释放

如：采用层次遍历

void deleteTree(struct TreeNode* root)
{
    queue<struct TreeNode*> list;
    if (root == NULL) return;
    list.push(root);
    struct TreeNode* tmp;
    while (!list.empty())
    {
        tmp = list.front();
        list.pop();
        if (tmp->left != NULL) list.push(tmp->left);
        if (tmp->right != NULL) list.push(tmp->right);
        delete tmp;
    }
    return;
}

插入结点

在二叉树中插入结点，要确定待插入结点与插入位置结点的父子关系。
设p为指向待插入结点的指针，简称结点 p；s为指向插入位置结点的指针，简称结点s. 即要确定 p 作为 s 的左儿子还是右儿子，以及如何维护 s 原来的父子关系。

指定为左儿子：

void insert(struct TreeNode* s,struct TreeNode* p)
{
    if(s==NULL||p==NULL) return ;
    p->left=s->left;
    p->right=NULL;
    s->left=p;
    return ;
}

删除给定结点及其左右子树

相较于释放二叉树，我们还需要改变父节点的内容。

void deleteNode(struct TreeNode* root,struct TreeNode* p)
{
    if(root==NULL||p==NULL) return ;
    if(root==p) {deleteTree(root); return ;}
    struct TreeNode* father=Father(p);//查找p的父节点
    if(father->left==q) father->left=NULL;
    else				 father->right=NULL;
    deleteTree(p);
    return ;
}

表达式树

概念

表达式有一个内在二叉树结构，即表达式(a+b) * (c−d)−e对应的二叉树，二叉树中叶结点是表达式中的变量或常数（如：a，b），非叶结点是操作符。

后缀表达式构造对应的表达式树

实现

struct TreeNode* creatBinTree(char* array, int size)
{
	struct TreeNode* tmp = NULL;
	int point = 0;
	while (point <= size - 1)
	{
		if (array[point] == '+' || array[point] == '-' || array[point] == '*' || array[point] == '/')
		{
			tmp = new struct TreeNode(array[point]);
			tmp->left = ss.top();
			ss.pop();
			tmp->right = ss.top();
			ss.pop();
			ss.push(tmp);
		}
		else
		{
			tmp = new struct TreeNode(array[point]);
			ss.push(tmp);
		}
		point++;
	}
	return ss.top();
}

已知表达式树，计算其对应的值

将表达式树转换为后缀表达式，再利用栈计算后缀表达式的值。

stack<double> cacu;
struct TreeNode* root;
vector<char> v;
void Tree2array(struct TreeNode* tmp)
{
    if (tmp == NULL) return;
    if (tmp->left != NULL) Tree2array(tmp->left);
    if (tmp->right != NULL) Tree2array(tmp->right);
    v.push_back(tmp->val);
    return;
}
double Treecaculate()
{
    double lh = 0, rh = 0;
    Tree2array(root);
    for (vector<char>::iterator it = v.begin(); it < v.end(); it++)
    {
        if (*it == '+' || *it == '-' || *it == '*' || *it == '/')
        {
            switch (*it)
            {
                case('+'):
                    {rh = cacu.top();
                     cacu.pop();
                     lh = cacu.top();
                     cacu.pop();
                     cacu.push(lh + rh);
                     break;
                    }
                case('-'):
                    {rh = cacu.top();
                     cacu.pop(); 
                     lh = cacu.top(); 
                     cacu.pop(); 
                     cacu.push(lh - rh); 
                     break; }
                case('*'): 
                    {rh = cacu.top(); 
                     cacu.pop(); 
                     lh = cacu.top();
                     cacu.pop(); 
                     cacu.push(lh * rh);
                     break; }
                case('/'): 
                    {rh = cacu.top();
                     cacu.pop(); 
                     lh = cacu.top();
                     cacu.pop();
                     cacu.push(lh / rh);
                     break; }
            }
        }
        else
        {
            cacu.push(*it - '0');
        }
    }
    return (cacu.top());
}

*线索化二叉树

概念

通过遍历二叉树可得到结点的一个线性序列，在线性序列中，除第一个结点外，每个结点有且仅有一个前驱，除最后一个结点外，每个结点有且仅有一个后继。但在二叉树中只能找到结点的左孩子、右孩子，结点在线性序列中的前驱和后继只有在遍历过程中才能得到

为了与结点在二叉树中所具有的前驱（即父结点）和后继即子结点）区别开来，通常把某种序列中结点的前驱或后继冠以某种遍历的名称，如把中根序列中结点的前驱称作中根前驱，结点的后继称作中根后继。

节点变化：

[目的]

在中序线索二叉树中不需要对二叉树进行遍历就可以方便地找到给定结点的中序前驱和中序后继结点，并且不需要太多额外的空间。

线索二叉树中一个结点是叶结点的充要条件为：左、右标识(LThread、RThread)均为1。

哈夫曼树

预备知识

「定义5.6」 扩充二叉树的外通路长度定义为从根到每个外结点的路径长度之和，内通路长度定义为从根到每个内结点的路径长度之和。

「定义5.7」

给扩充二叉树的 n 个外结点分别赋上一个实数权。扩充二叉树的加权外通路长度定义为:
$WPL=\sum\limits_{i=1}^{n}w_iL_i$
其中 n 表示外结点的个数，wi 和 Li 分别表示外结点 ki的权值和根到 ki的路径长度。

「定义5.8」

在外结点权值分别为 w1 , w2 , … , wn的所有扩充二叉树中，加权外通路长度最小的扩充二叉树称为最优二叉树

构造哈夫曼树

「算法思想」

在外结点权值分别为w1 ,w2 ,…,wn的扩充二叉树中，由哈夫曼算法构造出的哈夫曼树的带权路径长度最小，因此哈夫曼树为最优二叉树。

由观察可知，字符集中的字符所在的结点均是哈夫曼树中的外结点。哈夫曼树中没有度为 1 的结点

在构造哈夫曼树的过程中，没有一片树叶是其他树叶的祖先，所以**每个叶结点对应的编码不可能是其他叶结点对应的编码的前缀，**由此可知哈夫曼编码是二进制的前缀码。

「代码实现」

假设给定m个实数（代表权值）对应结点的地址存于一维数组H[1: m+1]中，该数组已按结点的Weight域排序，即：

Weight(H[1])\leq..\leq Weight(H[m])\leq Weightleq\leq +\infty

struct HuffmanTreeNode
{
	struct HuffmanTreeNode* Llink;
	int weight;
	//也可以加一个info字段代表是什么字符
	struct HuffmanTreeNode* Rlink;
};
struct HuffmanTreeNode* createHuffmanTree(int* arr, int size)
{
	int root;
	struct HuffmanTreeNode* H = new struct HuffmanTreeNode[10];

	for (int i = 0; i <= size - 1; i++)
	{
		H[i].Llink = NULL;
		H[i].Rlink = NULL;
		H[i].weight = arr[i];
		
	}
	for (int i = 0; i <= size - 1; i++)
	{
		struct HuffmanTreeNode tmp;
		tmp.weight = H[i].weight + H[i + 1].weight;
		tmp.Llink = &H[i];
		tmp.Rlink = &H[i + 1];
		//插入排序，将tmp插入原来的序列并保持有序
		root = i + 2;
		while (tmp.weight > H[root].weight)
		{
			H[root - 1] = H[root];
			root++;
		}
		H[root - 1] = tmp;
	}
	return &H[root];
}

PTA

编写一个哈夫曼编码译码程序。针对一段文本，根据文本中字符出现频率构造哈夫曼树，给出每个字符的哈夫曼编码，并进行译码，计算编码前后文本大小。
为确保构建的哈夫曼树唯一，本题做如下限定：

选择根结点权值最小的两棵二叉树时，选取权值较小者作为左子树。

若多棵二叉树根结点权值相等，则先生成的作为左子树，后生成的作为右子树，具体来说：i) 对于单结点二叉树，优先选择根结点对应字母在文本中最先出现者，如文本为cba，三个字母均出现1次，但c在文本中最先出现，b第二出现，故则选择c作为左子树，b作为右子树。ii) 对于非单结点二叉树，先生成的二叉树作为左子树，后生成的二叉树作为右子树。iii. 若单结点和非单结点二叉树根结点权值相等，优先选择单结点二叉树。

生成哈夫曼编码时，哈夫曼树左分支标记为0，右分支标记为1。

输入格式:

输入为3行。第1行为一个字符串，包含不超过5000个字符，至少包含两个不同的字符，每个字符为a-z的小写字母。第2、3行为两个由0、1组成的字符串，表示待译码的哈夫曼编码。

输出格式:

输出第一行为用空格间隔的2个整数，分别为压缩前后文本大小，以字节为单位，一个字符占1字节，8个二进制位占1字节，若压缩后文本不足8位，则按1字节算。输出从第二行开始，每行为1个字符的哈夫曼编码，按各字符在文本中出现次数递增顺序输出，若多个字符出现次数相同，则按其在文本出现先后排列。每行格式为“字母:编码”。最后两行为两行字符串，表示译码结果，若译码失败，则输出INVALID。

输入样例:
1
2
3
cbaxyyzz
0100
011
输出样例:
1
2
3
4
5
6
7
8
9
8 3
c:100
b:101
a:110
x:111
y:00
z:01
zy
INVALID

扩展:k进制编码

荷马史诗

#include<iostream>
#include<queue>

using namespace std;

typedef long long LL;
typedef pair<LL,int> PLI;//权值 所在的深度
priority_queue<PLI,vector<PLI>,greater<PLI>> heap;
const int N = 100010;
const int K = 9;

int n,k;
int main()
{

    scanf("%d%d",&n,&k);
     for(int i=0;i<n;i++)
    {
        LL w;
        scanf("%lld",&w);
        heap.push({w,0});

    }
    while((n-1)%(k-1)!=0)
    {
        heap.push({0,0});
        n++;
    }
    LL res=0;
    while(heap.size()>1)
    {
        LL s=0;
        int depth=0;
        for(int i=0;i<k;i++)//取出前k个
        {
            PLI tmp=heap.top();
            heap.pop();
            s+=tmp.first;
            depth=max(depth,tmp.second);
        }
        res+=s;//合并就会导致节点加一层
        heap.push({s,depth+1});
    }

   cout<<res<<"\n"<<heap.top().second<<endl;

    return 0;
}

树的存储与操作

略

待更新

等价类与并查集

学习途径：并查集——Pecco 知乎详解

##include<iostream>
##include<vector>
##include<stack>
using namespace std;
struct Node
{
	int val;
	struct Node* left;
	struct Node* right;
};
class DSU
{
private:
	std::vector<int> parent;//一开始，我们先将它们的父节点设为自己
	std::vector<int> rank; //每个节点对应的树的高度，初值为1
public:
	DSU(int size)
	{
		parent.resize(size + 1);
		rank.resize(size + 1);
		for (int i = 0; i < size + 1; i++)
		{
			parent[i] = i;
			rank[i] = 1;
		}
	}
	int find(int x)// 寻找x所在的树的根节点
	{
		if (parent[x] == x)//自己就是父节点即找到了根节点则返回
			return x;
		else
		{
			parent[x] = find(parent[x]);//找父亲的父节点
			return parent[x];
		}
	}
	void merge(int i, int j)
	{
		int x = find(i), y = find(j);
		if (rank[x] <= rank[y]) //x高度低于y或相等时，把i挂在j的树上
		{
			parent[x] = y;//i所在树的根节点x 的父节点是j所在树的根节点
		}
		else
		{
			parent[y] = x;//j所在树的根节点的父节点是i所在树的根节点
		}
		if (rank[x] == rank[y] && x != y) //如果高度相等并且 i和j所在的树不相同 则j的树高度要加一
		{
			rank[y]++;
		}
	}
};

图

存储结构

邻接矩阵

无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图所需存储空间为n(n+1)/2；

有向图的邻接矩阵不一定对称；有n个顶点的有向图所需存储空间为n²

邻接表

边链表里VerAdj是与顶点相连的节点编号，cost是权值，link指向下一个与顶点相连的节点

VerName是顶点名字，adjacent指向与其相连的节点链表

对于边很多的图（也称稠密图），适于用邻接矩阵存储，因为占用的空间少。

而对于顶点多而边少的图（也称稀疏图），若用邻接矩阵存储，对应的邻接矩阵将是一个稀疏矩阵，存储利用率很低。因此，顶点多而边少的图适于用邻接表存储

其他存储结构

图的遍历

图的遍历洛谷

深度优先遍历

递归算法

struct edge
{
	int VerAdj;
	struct edge* link;
};
struct Node
{
	int name;
	struct edge* adjacent;
};

void DepthFirstSearch(struct Node* head,int v,int* visit,int size)
{
	cout << head[v].name<<" ";
	visit[v] = 1;
	struct edge* p = head[v].adjacent;
	while (p != NULL)
	{
		if (visit[p->VerAdj] != 1)
		{
			DepthFirstSearch(head, p->VerAdj, visit, size);
		}
		p = p->link;
	}
}
void DFS(struct Node* head,int size)
{
	int* visited=new int[size];
	for (int i = 0; i <= size-1; i++) visited[i] = 0;
	for (int i = 0; i <= size-1; i++)
	{
		if (visited[i] != 0)
			DepthFirstSearch(head, i, visited, 10);
	}
}

迭代算法

利用栈进行访问

struct edge
{
    int VerAdj;
    struct edge* link;
};
struct Node
{
    int name;
    struct edge* adjacent;
};
void DFS(struct Node* head, int size,int v)
{
    int* visited = new int[size];
    stack<int> ss;
    ss.push(v);
    while (!ss.empty())
    {
        struct Node p = head[ss.top()];
        if (visited[p.name] != 1)
        {
            cout << p.name << " ";
            visited[p.name] = 1;
            ss.pop();
            struct edge* q = p.adjacent;
            while (q != NULL)
            {
                if (visited[q->VerAdj] != 1)
                {
                    ss.push(q->VerAdj);

                }
                q = q->link;
            }
        }
    }

}

广度优先遍历

使用队列实现

struct edge
{
    int VerAdj;
    struct edge* link;
};
struct Node
{
    int name;
    struct edge* adjacent;
};
void BFS(struct Node* head, int size, int v)
{
    int* visited = new int[size + 1];
    for (int i = 0; i <= size; i++)  visited[i] = 0;
    queue<int> list;
    cout << v << " ";
    list.push(v);
    visited[v] = 1;
    while (!list.empty())
    {
        struct edge* p = head[list.front()].adjacent;
        list.pop();
        while (p != NULL)
        {
            if (visited[p->VerAdj] != 1)
            {
                cout << p->VerAdj << " ";
                visited[p->VerAdj] = 1;
                list.push(p->VerAdj);
            }
            p = p->link;
        }
    }
}

拓扑排序

AOV网：在有向图中，用顶点表示活动，用有向边表示活动之间的先后关系，称这样的有向图为AOV网(Activity On Vertex Network)。重点在于研究结点Verterx

在AOV网络中，如果活动Vi 必须在活动Vj 之前进行，则存在有向边，**AOV网络中不能出现有向回路，**即有向环。在AOV网络中如果出现了有向环，则意味着某项活动应以自己作为先决条件。因此，对给定的AOV网络，应判断它是否存在有向环

如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV网络中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的

「算法思想」

从网中选择一个入度为0的顶点并将其输出。
从网中删除该顶点及其所有出边。
执行1 、2 ，直至所有顶点都已输出，或者网中剩余顶点的度均不为0（说明网中存在回路，无法继续拓扑排序）。

注意：对于任何无回路的AOV网，其顶点均可排成拓扑序列，但其拓扑序列未必唯一

入栈时：count[i]记录当前的栈顶，top赋值为新的栈顶

出栈时：top即为栈顶的编号，count[top]为栈顶下面的元素编号

实现

void TopoOrder(struct Node* Head,int n)
{
	int* count = new int[n];
	for (int i = 0; i <= n-1; i++)//初始化count数组
	{
		count[n] = 0;
	}
	for (int i = 0; i <= n - 1; i++)//初始化count数组
	{
		struct edge* p = Head[i].adjacent;
		while (p != NULL)
		{
			count[p->VerAdj]++;
			p = p->link;
		}
	}
	int top = -1; // 将数组变成虚拟栈
	for (int i = 0; i <= n - 1; i++)
	{
		if (count[i] == 0)
		{
			count[i] = top;
			top=i;
		}
	}
	for (int i = 0; i <= n - 1; i++)//已经无 有向环 的前提下
	{
		if (top == -1) return ;//无度为0的结点
		else
		{
			int temp = -1;
			temp = top;
			top = count[top];
			std::cout << temp<<" ";
			struct edge* p = Head[temp].adjacent;
			while (p != NULL)//更新count数组和虚拟栈
			{
				count[p->VerAdj]--;
				if (count[p->VerAdj] == 0)
				{
					count[p->VerAdj] = top;
					top = p->VerAdj;
					
				}
                p = p->link;
			}
		}
	}
}

练习一：

课程表

要注意判断是否有有向环

官方题解：

一：深度优先搜索

深度优先搜索，将拓扑排序与深度优先搜索联系在一起，二者都是先完成前一个结点再完成后一个结点

对于图中的任意一个节点，它在搜索的过程中有三种状态，即：

「未搜索」：我们还没有搜索到这个节点；

「搜索中」：我们搜索过这个节点，但还没有回溯到该节点，即该节点还没有入栈，还有相邻的节点没有搜索完成；

「已完成」：我们搜索过并且回溯过这个节点，即该节点已经入栈，并且所有该节点的相邻节点都出现在栈的更底部的位置，满足拓扑排序的要求。

通过上述的三种状态，我们就可以给出使用深度优先搜索得到拓扑排序的算法流程，在每一轮的搜索搜索开始时，我们任取一个「未搜索」的节点开始进行深度优先搜索。

我们将当前搜索的节点 u 标记为「搜索中」，遍历该节点的每一个相邻节点 v：

如果 v为「未搜索」，那么我们开始搜索 v，待搜索完成回溯到 u；

如果 v为「搜索中」，那么我们就找到了图中的一个环，因此是不存在拓扑排序的；

如果 v为「已完成」，那么说明 v已经在栈中了，而 u还不在栈中，因此 u 无论何时入栈都不会影响到 (u,v) 之前的拓扑关系，以及不用进行任何操作。

当 u 的所有相邻节点都为「已完成」时，我们将 u 放入栈中，并将其标记为「已完成」。

在整个深度优先搜索的过程结束后，如果我们没有找到图中的环，那么栈中存储这所有的 n个节点，从栈顶到栈底的顺序即为一种拓扑排序。

优化

由于我们只需要判断是否存在一种拓扑排序，而栈的作用仅仅是存放最终的拓扑排序结果，因此我们可以只记录每个节点的状态，而省去对应的栈。

class Solution {
private:
    vector<vector<int>> edges;
    vector<int> visited;
    bool valid = true;

public:
    void dfs(int u) {
        visited[u] = 1;//将本结点标记为搜索中
        for (int v: edges[u]) {
            if (visited[v] == 0)
            {//如果邻接结点未搜索，则开始搜索
                dfs(v);
                if (!valid) {//搜索完V发现有环，结束,上面几层均是结束
                    return;
                }
            }
            else if (visited[v] == 1) {//如果结点在搜索中存在环，记录并返回
                valid = false;//记录
                return;
            }
        }//不存在环则邻接结点完全搜索完，将本结点标记
        visited[u] = 2;
    }

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);//初始化边结点的数目
        visited.resize(numCourses);//初始化访问标记的数目
        for (const auto& info: prerequisites) {
            edges[info[1]].push_back(info[0]);
        }
        for (int i = 0; i < numCourses && valid; ++i) {
            if (!visited[i]) {//结点状态为0则开始搜索
                dfs(i);
            }
        }
        return valid;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/course-schedule/description/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

二：广度优先搜索

这个方法类似与课本上的解法，只不过是用队列进行实现。

重点是判断能否产生拓扑序列

class Solution {
private:
    vector<vector<int>> edges;
    vector<int> indeg;//入度记录

public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        indeg.resize(numCourses);
        for (const auto& info: prerequisites) {
            edges[info[1]].push_back(info[0]);
            ++indeg[info[0]];//更新入度表
        }

        queue<int> q;//建立度为0的队列
        for (int i = 0; i < numCourses; ++i) {
            if (indeg[i] == 0) {
                q.push(i);
            }
        }

        int visited = 0;
        while (!q.empty()) {//计算可以去掉的结点有多少个
            ++visited;
            int u = q.front();
            q.pop();
            for (int v: edges[u]) {
                --indeg[v];
                if (indeg[v] == 0) {
                    q.push(v);
                }
            }
        }

        return visited == numCourses;//如果全可以去掉则不存在有向环则可以产生拓扑序列
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/course-schedule/description/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

练习二：

课程表二

关键路径

如果在有向无环的带权图中：

用有向边表示一个工程中的各项活动(Activity) •

用边上的权值表示活动的持续时间(Duration)

用顶点表示事件(Event)

则这样的有向图叫做用边表示活动的网络，简称AOE (Activity On Edges)网络。

● 源点：表示整个工程的开始（入度为零）。

● 汇点：表示整个工程的结束（出度为零）

在AOE网络中, 有些活动必须顺序进行，有些活动可以并行进行。

从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上的所有活动都完成了，整个工程才算完成。

因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即路径上所有活动的持续时间之和。路径长度最长的路径被称为关键路径(Critical Path)。

事件——结点

最早事件发生时间 ve(i) 源点到i点的最长路径长度，即前一个邻接结点的ve加上路径权值最大的那一个

最晚事件发生时间 vl(i) 即后一个邻接结点的vl减去路径权值取最小的那一个，即减去了时间最长的活动（“关键活动”）的时长

活动——边

最早活动开始时间 e(i)

最晚活动开始时间 e(i)

「算法」

判断是否存在有向环，通过拓扑排序进行判断，如果有有向环则中止算法，如果没有，则按照拓扑排序的顺序求出各个事件的最早发生时间ve
按照拓扑排序的逆序列求出每个事件的最晚发生事件vl
根据ve和vl确定活动的最早开始时间e(i)和最晚开始时间l(i)，如果二者相等则为关键活动

「实现」

struct Node
{
    int name;
    struct edge* link;
};
struct edge
{
    int Veradj;
    int cost;
    struct edge* next;
};

class AOE
{
private:
    struct Node* Head;//经过拓扑排序后的结点序列
    int num;
    vector<struct edge> critical;
public:
    void criticalPath(struct Node* Head, int num)
    {//求关键路径之前先判断是否存在有向环，不存在则将结点按拓扑排序排好送入Head
        vector<int> ve(num), vl(num);
        for (int i = 0; i <= num - 1; i++)
        {
            ve[i] = 0;
        }
        for (int i = 0; i < num - 1; i++)//汇点不在范围内,因为没有出边
        {//按拓扑序列进行计算
            struct edge* p = Head[i].link;
            int k = Head[i].name;
            while (p != NULL)//求事件最早happen时间
            {
                if (p->cost + ve[k] > ve[p->Veradj])
                {
                    ve[p->Veradj] = p->cost + ve[i];
                }
                p = p->next;
            }
        }
        for (int i = 0; i <= num - 1; i++)
        {
            vl[i] = ve[i];
        }
        for (int i = num - 2; i >= 0; i--)
        {//求事件最晚发生时间
            struct edge* p = Head[i].link;
            int k = p->Veradj;
            while (p)
            {
                if (vl[k] - p->cost < vl[Head[i].name])
                {
                    vl[Head[i].name] = vl[k] - p->cost;
                }
                p = p->next;
            }
        }
        for (int i = 0; i <= num - 1; i++)
        {//求活动的最晚最早开始事件
            struct edge* p = Head[i].link;
            int l = 0, e = 0;
            while (p != NULL)
            {
                int k = p->Veradj;
                e = ve[Head->name];
                l = vl[k] - p->cost;
                if (e == l)//相等即为关键活动
                {
                    critical.push_back(*p);
                }
                p=p->next;
            }
        }
        return;
    }
};

「时间复杂度」

定理 6.3 任意的非空AOE网至少存在一条关键路径。

推论 6.1 假设<Ti,Tj>边属于AOE网，则有
$vl[j]-ve[i]\geq weight(<Ti,Tj>)$
如果属于关键路径则：
$vl[j]-ve[i]= weight(<Ti,Tj>)$

最短路径问题

洛谷最短路径问题题单

单源最短路径

单源：即只有一个出发点

1.无权最短路径

无权：即每条边的权值都为1

源点到各顶点的路径所经历的边的数目就是路径的长度

相对于源点由近及远依次求各顶点的最短路径

「算法思想」

Di 为源点S到顶点 i 的最短路径长度;初始：Ds =0 ∀i ≠ S，Di = -1

访问初始顶点S，对S的所有邻接顶点w, 若Dw = -1，则Dw =Ds+1

v是当前被访问的顶点，对于v的所有邻接顶点w, 若Dw = -1，则 Dw =Dv +1

处理完v的所有邻接顶点后，访问另一个满足Du =Dv的顶点u，若不存在这样的顶点，则访问满足Du =Dv +1的顶点u，若仍不存在，算法结束.

图的广度优先遍历。

「实现」

class noValueMap
{
private:
	vector<struct Node>Head;//邻接表的首节点
	queue<int> list;
public:
	void ShortestPath(int v)//v是起点
	{
		vector<int> path(Head.size());
		vector<int> dist(Head.size());
		for (int i = 0; i <= Head.size() - 1; i++)
		{
			path[i] = -1;
			dist[i] = -1;
		}
		dist[v] = 0;
		list.push(v);
		while (!list.empty())
		{
			int tmp = list.front();
			list.pop();
			struct edge* p = Head[tmp].adjacent;
			while (p != NULL)
			{
				int k = p->VerAdj;
				if (dist[k] == -1)//没被访问过
				{
					dist[k] = dist[tmp]+1;
					list.push(k);
					path[k] = tmp;
				}
				p = p->link;
			}
		}
		
		return;
	}
};

「复杂度」

2.正权最短路径

「前提」

每条边的权值为正数

迪杰斯特拉算法

「算法思想」

把图中所有顶点分成两个集合，

第一个集合包含已确定最短路径的顶点，

第二个集合包含尚未确定最短路径的顶点。

按照最短路径长度递增的顺序逐个把第二个集合的顶点加到第一个集合中去，直至从源点出发可以到达的所有顶点都包含到第一个集合中

步骤：

初始时( S为初始顶点） D[s] =0 (起点的距离为0)且∀ i ≠ S 有D[ i ] =MAX(无穷，根据题目换成权值的最大值+1)。

在未访问的顶点中选择D值最小的顶点v，访问v，令 S[v]=1（表示已被访问）。

依次考察v的邻接顶点w，若 D[ v ]+weight(<v，w>) < Dw ，则改变Dw的值，使Dw = Dv + weight(<v，w>) 。

重复 2、3，直至所有顶点皆被访问（找到源点到该顶点的最短路径）

「实现」


struct edge
{
	int VerAdj;
	int cost;
	struct edge* link;
};
struct Node
{
	int name;
	struct edge* adjacent;
};
class PositiveValuePath
{
private:
	vector<struct Node> Head;
	vector<int> dist;
	vector<int> path;
    const int Max = 1000;//取决于题目权值的约束条件，一定要比最大值大
public:
	void DshortsPath(int start)
	{
		dist.resize(Head.size());
		path.resize(Head.size());
		vector<int> visited(Head.size());
		for (int i = 0; i <= Head.size() - 1; i++)
		{
			dist[i] = Max;
			path[i] = -1;
			visited[i] = 0;
		}
		dist[start] = 0;
		int next = start;
		visited[next] = 1;
		for (int i = 0; i <= Head.size() - 1; i++)
		{
			struct edge* p = Head[next].adjacent;
			while (p != NULL)
			{
				int k = p->VerAdj;
				if (visited[k] == 0 && dist[next] + p->cost < dist[k])
				{
					dist[k] = dist[next] + p->cost;
					path[k] = next;//在源点到k点的最短路中，k的上一个节点是next
				}
				p = p->link;
			}
			int min = Max;
			for (int i = 0; i <= Head.size() - 1; i++)//更新next，在未访问节点中选取距离最近的节点
			{
				if (dist[i] < min && visited[i] == 0)
				{
					next = i;
					min = dist[i];
				}
			}
			visited[next] = 1;
		}
	}
};

算法结束时，dist[x]将包括所有最短路径的长度。

「练习」

网络延迟时间

对于稀疏图，即边的个数远小于点的个数时，时间效率不高，可以采用优先队列进行改进。

优先队列相关内容见线性表。

void DshortsPath(int start)
{
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> plist;
       //优先队列，按照piar的第一个数据升序排列
	dist[start] = 0;
	plist.push({ 0,start });//<距离，节点号>
	int node_size = date.size();
	while (plist.size())
	{
		auto t = plist.top();
		plist.pop();
		int tindex = t.second, distance = t.first;
		if (visited[tindex])
			continue;
		visited[tindex] = 1;
		struct EDGE* p = date[tindex].next;
		while (p != NULL)
		{
			int index = p->adj_index;
			if (!visited[index] && dist[tindex] + p->val < dist[index])
			{
				dist[index] = dist[tindex] + p->val;
				plist.push({ dist[index],index });//将求过距离的节点放入优先队列中排序，以便生成下次访问的节点
			}
			p = p->next;
		}
	}
	for (int i = 1; i < node_size; i++)
	{
		if (dist[i] != Max)//可以到达
		{
			printf("%d ", dist[i]);
		}
	}
	return;
}

每对顶点之间的最短路径

Floyd算法

「基本思想」

「实现」

class myMap
{
    private:
    vector<vector<int>> edge;
    vector<vector<int>> path;
    vector<vector<int>> dist;
    static int MAX ;
    public:
    void AllLength()
    {
        vector<vector<int>> A(edge.size());
        for (int i = 0; i <=edge.size()-1 ; i++)
        {
            for (int j = 0; j <= edge.size() - 1; j++)
            {
                A[i][j] = edge[i][j];
                if (edge[i][j] < MAX && i != j) path[i][j] = i;//i到j的路上前一个节点是i
                else
                    path[i][j] = -1;//无路可走
            }
        }
        for (int k = 0; k <= edge.size() - 1; k++)//不断添加经过的范围
        {
            for (int i = 0; i <= edge.size() - 1; i++)
            {
                if (i != k)
                {
                    for (int j = 0; j<= edge.size() - 1; j++)
                    {
                        if (j != k && j != i && A[i][k] < MAX && A[k][j] < MAX && A[i][k] + A[k][j] < A[i][j])
                            //i到k可及，k到j可及
                        {
                            A[i][j] = A[i][k] + A[k][j];
                            path[i][j] = path[k][j];//i经由k到j的路上前一个节点是 k到j上的前一个节点
                        }
                    }
                }
            }
        }

    }
};
int myMap::MAX = 100;

「复杂度」

「练习」

力扣除法求值

*满足约束的最短路径

「算法思路」

最小支撑树

对于一个无向网络——无向加权连通图N=(V, E, C)（C表示该图为权图），其顶点个数为|V|=n，图中边的个数为|E|，可以从它的|E|条边中选出n-1条边，使之满足：

(1) 这n-1条边和图的n个顶点构成一个连通图。

(2) 该连通图的代价（n-1条边上的权值之和）是所有满足条件(1)的连通图的代价的最小值。

这样的连通图被称为网络的最小支撑树

Prim算法

「算法思路」

「实现」

假定编号从1开始

struct EDGE
{
	int head;
	int tail;
	int cost;
};
class myMap
{
private:
	static int MAX;
	vector<vector<int>> adjcent;//邻接矩阵
	vector<struct EDGE> TE;//最小支撑树边的集合
public:
	void Prim(void)
	{
		TE.resize(adjcent.size());
		vector<pair<int, int>> closedge(adjcent.size());//lowcost vex 权值和U中的顶点
		for (int i = 1; i <= adjcent.size(); i++)
		{
			closedge[i].first = adjcent[1][i];// 初始状态U中只有起点1
			closedge[i].second = 1;
		}
		closedge[1].second = -1;
		int count = 1;
		for (int j = 2; j <= adjcent.size(); j++)//有n个点，n-1条边加入TE
		{
			int v = 0, min = MAX;
			for (int i = 1; i <= adjcent.size(); i++)//找最短的
			{
				if (closedge[i].second != -1 && closedge[i].first < min)
				{
					v = i;
					min = closedge[i].first;
				}
			}
			if (v != 0)//找到了
			{
				TE[count].head = closedge[v].second;
				TE[count].tail = v;
				TE[count].cost = closedge[v].first;
				count++;
				closedge[v].first = 0;//v is putted in group U
				closedge[v].second = -1;
				for (int k = 1; k <= adjcent.size(); k++)//更新closedge数组
				{
					if (closedge[k].second != -1 && adjcent[v][k] < closedge[k].first)
					{
						closedge[k].first = adjcent[v][k];
						closedge[k].second = v;
					}
				}
			}
			else//图不连通
			{
				cout << "NOT CONNECTED";
				return;
			}
		}
		return;

	}
};
int myMap::MAX = 100;/////

注意MAX的值一定要大于边界条件

「练习」

力扣连接所有点的最小费用

Kruskal算法

「算法思路」

~~Prim是重点在于已知一个点在U中找与其相邻的最小权值边，而Kruskal算法在于已知所有点在不同的连通分量里找权值最小的边~~

「实现」

依旧要借用辅助数组TE来记录支撑树的边,还要由数组E保存图中的边

struct EDGE
{
	int head;
	int tail;
	int cost;
};
class myMap
{
private:
	int T;//连通分量，初识也是点的个数
	vector<EDGE> E;//图中所有边集合
	vector<struct EDGE> TE;//最小支撑树边的集合

public:
	bool cmp(EDGE a, EDGE b)
	{
		return a.cost <= b.cost;
	}
	int kruskal()
	{
		TE.resize(E.size());
		std::sort(E.begin(), E.end(),cmp);
		int j = 0, count = 0;
		while (T > 1)
		{
			int v1 = E[j].head;
			int v2 = E[j].tail;
			int cost = E[j].cost;
			if (Find(v1) != Find(v2))//不在一个连通分支中
			{
				TE[count].head = v1;
				TE[count].tail = v2;
				TE[count].cost = cost;
				count++;
				merge(v1, v2);
				T--;
			}
			j++;
		}
	}
};

图的应用

可及性与传递闭包

warshall算法

「基本概念」

沃尔肖（Warshall）算法：
求有向图G可及矩阵的算法，递推公式如下：
$WSM^{(K)}[i][j]=WSM^{(k-1)}[i][j]\quad OR\quad(WSM^{(k-1)}[i][k]\quad AND\quad WSM^{(K-1)}[k][j])\\ \qquad \qquad 1\leq k \leq n$
其中
$WSM^0 = A\quad (加上主对角线元素1) \quad A是有向图G的邻接矩阵\\WSM^{(k)}[i][j]表示定点i只经过顶点1,2,...,k到达j的可及性$

「实现」

class myMAP
{
private:
	vector<vector<int>> A;
	
public:
	vector<vector<bool>> Warshall()
	{
		vector<vector<bool>> wsm = A;
		for (int k = 0; k <= A.size() - 1; k++)
		{
			for (int i = 0; i <= A.size() - 1; i++)
			{
				if (wsm[i][k] = 1)
				{
					for (int j = 0; j <= A.size() - 1; j++)
					{
						wsm[i][j] = wsm[i][j] + wsm[k][j];
					}
				}
			}
		}
        return wsm;
	}
};

拓扑逆序算法

「算法思想」

「实现」

class myMAP
{
private:
	vector<Node> head;//图的邻接表已经按照拓扑序列排列过
	
public:
	void Tranclo()
	{
		vector<vector<int>> REACH;
		vector<int > Breach;
		Breach.resize(head.size());
		REACH.resize(head.size());
		for (int i = 0; i <= head.size() - 1; i++)
		{
			Breach[i] = 0;
		}
		for (int i = head.size() - 1; i >= 0; i--)
		{
			Breach[i] = 1;
			REACH[i].push_back(i);
			struct EDGE* p = head[i].link;
			while (p != NULL)
			{
				int j = p->num;
				if (Breach[j] == 0)
				{
					for (int k = 0; k <= REACH[j].size() - 1; k++)
					{
						if (Breach[k] ==0)
						{
							REACH[i].push_back(k);
							Breach[k] = 1;
						}
					}
					
				}
				p = p->next;
			}
			for (int i = 0; i <= head.size() - 1; i++)
			{
				Breach[i] = 0;
			}
		}
	}
		
};

连通分量

「算法思想」

在求出可及性的基础上进行计算，wsm[ i ] [ j ] =1&&wsm[ j ] [ i ]=1 成立即i和j在一个连通分量里。

排序

基本概念和指标

关键字域（key）：排序依据

主关键词：如果在数据表中各个对象的关键词互不相同，这种关键词即主关键词。按照主关键词进行排序，排序的结果是唯一的。

次关键词：数据表中有些对象的关键词可能相同，这种关键词称为次关键词。按照次关键词进行排序，排序的结果不一定唯一

稳定性：对于一开始表中主关键词域相同的对象，排序前后相对顺序不变

排序的时间开销：即排序算法的时间复杂度，是衡量算法好坏的最重要的标志，可用算法执行过程中关键词的比较次数与记录的移动次数来衡量。

有些排序算法的时间复杂度受记录关键词序列初始排列及记录个数影响较大，此时，按最好情况、最坏情况及平均情况，分别估算比较次数和移动次数。

算法执行时所需的附加存储空间，是评价排序算法好坏的另外一个指标

插入排序

直接插入排序

「算法思想」

将一个记录插入到已经排好序的有序表中，从而获得一个新的、记录数增加1的有序表。

「实现」

「分析」

「稳定性」

具有稳定性。

「改进」

将顺序查找改为二分查找，构造二分/对半插入排序算法

也是个稳定的排序方法

希尔排序

对直接插入排序的改进

「算法思想」

「实现」

「增量的取法」

「复杂度」

「稳定性」

不稳定

交换排序

冒泡排序

「算法思想」

从左到右/从上到下比较相邻记录的关键词，交换存在逆序的记录

经过一次冒泡排序可以把最大关键词的记录移动到最后

经过n-1次，就可以对所有记录排序

发生一次记录交换，反序对少一个

「实现」

「改进」

某趟扫描没有任何记录交换的时候就算法终止

「复杂度」

「稳定性」

稳定

快速排序(分划交换排序)

「算法思想」

「实现」

「复杂度」

改进：

「稳定性」

不稳定

选择排序

直接选择排序

「算法思想」

「实现」

「复杂度」

改进：

选择排序的关键是找最大或者最小记录，利用树形保存前面的比较结果，下一次选择时直接利用，可以大大减少比较次数

相关概念

比赛树：每次两两比较的结果把关键词大者作为优胜者上升到父结点，，称这种树为比赛树
外结点：位于最底层的叶结点内结点：非叶结点

「稳定性」

不稳定

堆排序

堆：：完全二叉树中的任意结点的关键词大于等于它的两个子结点的关键词，把这样的数据结构称为堆（大根堆 ）

大根堆中根结点的关键词最大，小根堆中根结点的关键词最小。

「算法思想」

过程：

建堆
交换再重建堆

「实现」

堆存储于顺序线性表（数组）中

「复杂度」

「稳定性」

不稳定

合并排序

合并/归并：把两个或多个有序文件组成一个单一的有序文件。

基于合并操作完成排序。

当 i 和 j 分别在两个表内变化时，通过比较A[i]与B[j]的关键词大小，依次把 关键词小的对象放到新表X[k]中；

当 i与 j中有一个超出表长时，将另一个表中的剩余部分照抄到新表X中

「实现」

改进：

分析合并排序算法，不难发现它的两个缺点：

当数据集非常小时，比如只有2个元素，仍然采用分治策略，影响效率。

Merge算法基于元素移动，当元素比较大时，移动操作比较费时

➢针对这两个问题的解决办法：

对于小数据集以及前几趟合并操作，调用直接插入排序算法。

将数组存储改为链表存储，这样记录移动变为指针移动

「复杂度」

「稳定性」

稳定

基于关键词比较的排序算法分析

分治排序的一般方法

快速排序、合并排序，应用了分治策略

分布排序

「复杂度」

时间复杂度可以达到线性阶。

基数分布排序

基于基数分布的排序（基数排序）

最高次序位法：先按高位分桶，然后桶内进行排序如：英文单词，扑克牌

最低次序位法：先按最低位排序，然后按下一个次低位排序，…，最后按最高位排序。

「实现」

值分布排序

「实现」

例如：堆三元组表存储的稀疏矩阵，求转置矩阵，可以利用值排序

查找

线性表的查找

顺序查找

「无序表顺序查找」

查找失败的查找长度：n+1

分析：

改进：自组织表

「有序表的顺序查找」

但如果只对表查找一次，则顺序查找要比排序快；如果要在同一个文件中不断查找，将表按序排列再查找是个很好的方法

对半查找

算法思想

算法分析

一致对半查找

斐波那契查找

插值查找

算法思想

树形结构的查找

字典树（trie树）

常用来解决根据前缀查询字符串的问题

struct TrieNode
{
	struct TrieNode* next[36]={0};
     bool end=false;
	char word[30]="";
};

二叉查找树（BST）

一棵二叉查找树是一棵可能为空的二叉树形，并且关键词各不相同。二叉查找树中的任一结点P，它的左子树中结点的关键词都小于KEY§，而右子树中结点的关键词都大于KEY§

二叉查找树（或称二叉搜索树、排序树）是一棵可能为空的二叉树形，一棵非空的二叉查找树中的所有结点在中根次序下按其关键词由小到大排序，并且关键词各不相同

查找

走过每层

实现：

struct BSTNode
{
    struct BSTnode* left;
    struct BSTnode* right;
    int data;
    int key;
};

//递归版本
BSTnode* Search(BSTnode* root,int k)
{
	if(root == NULL||root->key==k) return root;
    if(k<root->key) return Search(root->left,k);
    else
        return Search(root->right,k);

}
//迭代版本****时间复杂度O(h)  h为树的高度******
BSTnode* Search(BSTnode* root,int k)
{
    BSTnode* p =root;
    while(p!=NULL)
    {
        if(k<p->key) p=p->left;
        else if(k>p->key) p=p->right;
        else return p;
	}
    return NULL;
}

插入

实现：

void Insert(BSTnode* &root,int k )    //返回值为空，采用引用的方法进行修改根节点
{
	if(root==NULL) root = new BSTnode(k);
    else if(k<root->key) Insert(root->left,k);
    else if(k>root->key) Insert(root->right,k);
}
BSTnode* Insert(BSTnode* root,int k)  //返回值为指针，采用值传递的方法更改
{
	if(root==NULL) root = new BSTnode(k);
    else if(k<root->key) root->left = Insert(root->left,k);
    else if(k>root->key)root->right = Insert(root->right,k);
    return root;
}

删除

其实只用分成三类

没有孩子：不做操作

有一个孩子：子承父业

有两个孩子：右子树的中序顺序的第一个（即右子树的最小的一个或者说是k的中序后继）换到k的位置

算法分析

最优二叉查找树

高度平衡树（AVL）

上述所介绍的二叉查找树各个操作的时间复杂度由树的高度决定的，因此我们希望树的高度越低越好，即树矮胖是好的，效率是高的，但达到完全二叉树或者是满二叉树条件较为苛刻，所以我们引入了高度平衡树：

高度的粗略计算

实现：

struct AVLnode
{
	int key;
    int height;
    AVLnode* left,*right;
    AVLnode(int k) {key=k;height=0;left=right=NULL}
};

int Height(AVLnode* t ){return (t==NULL)? -1:t->height;}
int max(int a,int b) {return (a>b)?  a:b;}
void UpdateHeight(ALVnode* t)
{
    t->height = 1+max(Height(t->left),Height(t->right));
}

查找

与普通的二叉查找树一致

插入

为了保持树仍是高度平衡树会有以下四种插入情况

LL型(R旋转): 新结点P插到A的左子树的左子树上

RR型(L旋转): 新结点P插入到A的右子树的右子树上

LR型(LR旋转): 结点P 插入到A的左子树的右子树上

RL型(RL旋转): 结点P插入到A的右子树的左子树上

实现

void LL(AVLndoe* &A)
{
	AVLnode*B = A->left;
    A->left = B->right;
    UpdateHeight(A);
    UpdateHright(B);
    A=B;
}

实现：

void RR(AVLnode* &A)
{
	ALVnode*B = A->right;
    A->right=B->left;
    B->left = A;
    UpdateHeight(A);
    UpdateHeight(B);
    A=B;
}

实现：

通过上述四种操作，在插入前后数的高度和平衡性不受影响

删除

先采用二叉查找树的删除算法删除，再调整平衡性

红黑树

插入

1.原本为空树，插入后将根涂成黑色，不用做其他操作

2.插入节点的父节点是黑色，插入节点染成红色，不影响红黑树的性质，不用做任何操作

3.当父节点为红色，插入节点也为红色，为满足性质2，在不同的前提条件下要做不同的修改：

如果当前节点的叔叔节点是红色，则父节点和叔叔节点都变为黑色，祖父染成红色
如果当前节点的叔叔节点是黑色或者叔叔节点不存在：则按照路径进行RL LR LL RR 旋转，最后根染成黑色，子节点染成红色。

删除：

1.删除含有两个孩子的节点，可以归结为删除一个孩子的节点或者删除叶子节点（用中根后继的值替换被删除的节点的值，再删除中根后继）。

2**.删除一个孩子的节点或者是叶子节点**：

x为红色，则一定是叶子节点，直接删除
x为黑色，替换的节点为红色，用r替换x，并将r染成黑色
x为黑色，r为黑色，即双黑缺陷，又可以分为三种情况

B树及其变形树

外查找

B树

插入

删除

B+树

数字查找

散列

前面所介绍的查找方法有两种，一种是基于表中关键词与给定变元K的比较, 另一种是进行数字的匹配。这两种方法，在找到以给定K为关键词的记录之前都要检查若干数目的关键词。

但散列方法却几乎完全免去了对表的搜索。以给定变元K为自变量，通过某种函数h(K) 直接计算出函数值，此值被解释为存放以 K为关键词的记录的地址。查找时，用相同方法计算出与给定变元K对应之记录的存储地址A，进而到A所指的存储单元中取出要查的记录

冲突调节

拉链法

线性表

链表

单链表

创建

遍历

增加节点

删除节点

反转链表

双向链表

循环链表

栈（stack）

顺序存储

链式存储

比较

*双栈

应用

队列（queue）

顺序存储

链式存储

顺序存储和链式存储

扩展

优先队列

基本功能和特性

使用示例

自定义优先级（最小堆）

自定义结构体和比较规则

总结

字符串

模式匹配问题

树

基本操作

二叉树

基本性质

存储结构

基本操作

中根遍历

先根遍历

后根遍历

层次遍历

创建二叉树

复制二叉树

计算树的高度

计算树的路径

查找给定结点的父结点

查找符合数据域条件的结点

释放二叉树

插入结点

删除给定结点及其左右子树

表达式树

*线索化二叉树

相关操作

哈夫曼树

树的存储与操作

等价类与并查集

图

存储结构

邻接矩阵

邻接表

其他存储结构

图的遍历

深度优先遍历

广度优先遍历

拓扑排序

关键路径

最短路径问题

单源最短路径

每对顶点之间的最短路径

*满足约束的最短路径

最小支撑树

Prim算法

Kruskal算法

图的应用

可及性与传递闭包

连通分量

排序

基本概念和指标

插入排序

直接插入排序

希尔排序

交换排序