Data structure

数据结构

[TOC]

链表

链表的创建

//链表的创建（带头结点）
typedef struct Node
{
    int x;
    struct Node*next;
}Node,*LinkList;
LinkList p;
p=(LinkList)malloc(sizeof(Node));
p->next=NULL;
//用typedef讲结构体指针和结构体简化

链表的读取

//链表的读取
Status GetElem(LinkList L,int i,Elemtype *e)
{
	int j;
	LinkList p;
	p = L->next;
	j=1;
	while(p&&j<i)
	{
	p =p ->next;
	j++;
	}
	if(!p||j>i)
	return ERROR;
	*e = p->data;
	return OK;
}

头插法

//头插法
void CreateListHead(LinkList*L,int n)
{
    LinkList p;
    int i;
    srand(time(0));
    *L=(LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    for (i=0;i<n;i++)
    {
        p=(LinkList)malloc(sizeof(Node));
        p->data=rand()%100+1;
        p->next=(*L)->next;
        (*L)->next=p;
    }
}

尾插法

//尾插法
void CreateListTail(LinkList*L,int n)
{
    LinkList p,r;
    int i;
    srand(time(0));
    *L=(LinkList)malloc(sizeof(Node));
    r=*L;
    for(i=0;i<n;i++)
    {
        p=(Node*)malloc(sizeof(Node));
        p->data=rand()%100+1;
        r->next=p;
        r=p;
        
    }
    r->next=NULL;
}

双向链表

/* Doubly Linked List implementation */
#include<stdio.h>
#include<stdlib.h>

struct Node  {
	int data;
	struct Node* next;
	struct Node* prev;
};

struct Node* head; // global variable - pointer to head node.

//Creates a new Node and returns pointer to it. 
struct Node* GetNewNode(int x) {
	struct Node* newNode
		= (struct Node*)malloc(sizeof(struct Node));
	newNode->data = x;
	newNode->prev = NULL;
	newNode->next = NULL;
	return newNode;
}

//Inserts a Node at head of doubly linked list
void InsertAtHead(int x) {
	struct Node* newNode = GetNewNode(x);
	if(head == NULL) {
		head = newNode;
		return;
	}
	head->prev = newNode;
	newNode->next = head; 
	head = newNode;
}

//Inserts a Node at tail of Doubly linked list
void InsertAtTail(int x) {
	struct Node* temp = head;
	struct Node* newNode = GetNewNode(x);
	if(head == NULL) {
		head = newNode;
		return;
	}
	while(temp->next != NULL) temp = temp->next; // Go To last Node
	temp->next = newNode;
	newNode->prev = temp;
}

//Prints all the elements in linked list in forward traversal order
void Print() {
	struct Node* temp = head;
	printf("Forward: ");
	while(temp != NULL) {
		printf("%d ",temp->data);
		temp = temp->next;
	}
	printf("\n");
}

//Prints all elements in linked list in reverse traversal order. 
void ReversePrint() {
	struct Node* temp = head;
	if(temp == NULL) return; // empty list, exit
	// Going to last Node
	while(temp->next != NULL) {
		temp = temp->next;
	}
	// Traversing backward using prev pointer
	printf("Reverse: ");
	while(temp != NULL) {
		printf("%d ",temp->data);
		temp = temp->prev;
	}
	printf("\n");
}

int main() {

	/*Driver code to test the implementation*/
	head = NULL; // empty list. set head as NULL. 
	
	// Calling an Insert and printing list both in forward as well as reverse direction. 
	InsertAtTail(2); Print(); ReversePrint();
	InsertAtTail(4); Print(); ReversePrint();
	InsertAtHead(6); Print(); ReversePrint();
	InsertAtTail(8); Print(); ReversePrint();
	
}

链表的全部删除

//链表的全部删除
Status ClearList(LinkList*L)
{
    LinkList p,q;
    p=(*L)->next;
    while(p)
    {
        q=p->next;
        free(p);
        p=q;
    }
    (*L)->next=NULL;
    return OK;
}

栈

用数组实现栈

//用数组实现栈
// Stack - Array based implementation. 
// Creating a stack of integers. 
#include<stdio.h>

#define MAX_SIZE 101

int A[MAX_SIZE]; // integer array to store the stack 
int top = -1;  // variable to mark top of stack in array

// Push operation to insert an element on top of stack. 
void Push(int x) 
{
  if(top == MAX_SIZE -1) { // overflow case. 
		printf("Error: stack overflow\n");
		return;
	}
	A[++top] = x;
}

// Pop operation to remove an element from top of stack.
void Pop() 
{
	if(top == -1) { // If stack is empty, pop should throw error. 
		printf("Error: No element to pop\n");
		return;
	}
	top--;
}

// Top operation to return element at top of stack. 
int Top() 
{
	return A[top];
}

// This function will return 1 (true) if stack is empty, 0 (false) otherwise
int IsEmpty()
{
    if(top == -1) return 1;
    return 0;
}

// This function is just to test the implementation of stack. 
// This will print all the elements in the stack at any stage. 
void Print() {
	int i;
	printf("Stack: ");
	for(i = 0;i<=top;i++)
		printf("%d ",A[i]);
	printf("\n");
}

int main() {	
  // Code to test the implementation. 
  // calling Print() after each push or pop to see the state of stack. 
	Push(2);Print();
	Push(5);Print();
	Push(10);Print();
	Pop();Print();
	Push(12);Print();
}

链表创建栈

//链表创建栈
typedef struct Node
{
	int x;
    struct *Node next;
}*Stack,Node;
Stack s;
s=(Stack)malloc(sizeof(Node));
s->next=NULL;

基本函数

//Push(x);
void Push(int x)
{
    struct Node*temp=(struct Node*)malloc(sizeof(struct Node));
    temp->x=x;
    temp->next=s;
    s=temp;
}

//Pop()
void Pop(){
    struct Node*temp;
    if(s->next==NULL)return;
    temp=s;
    s=s->next;
    free(temp);
}

//Top()
int Top(){
    return s->x;
}

//IsEmpty()
int IsEmpty(){
    if(s->next==NULL){
        return 1;
    }
    return 0;
}

前后中缀表达式

//后缀表达式求值
typedef struct Node {
	float x;
	struct Node *next;
} Node, *Stack;
float EvaluatePostfix(char a[]);
float Perform(char a, char op1, char op2);
Stack s;
int main() {
	char a[10];
	gets(a);
	float ans = EvaluatePostfix(a);
	printf("%f", ans);
	return 0;
}

float EvaluatePostfix(char a[]) {
	s = (Stack)malloc(sizeof(Node));
	s->next = NULL;

	for (int i = 0; i <= strlen(a) - 1 ; i++) {

		if (a[i] >= '0' && a[i] <= '9') {
			Push(a[i] - 48);
		} else if (a[i] == '+' || a[i] == '-' || a[i] == '*' || a[i] == '/') {
			float op2 = Top();
			Pop();
			float op1 = Top();
			Pop();
			float res = 0.0;
			res = Perform(a[i], op1, op2);

			Push(res);

		}
	}

	return Top();
}

float Perform(char a, float op1, float op2) {
	float ans = 0;

	if (a == '+') {
		ans = op1 + op2;
	}

	if (a == '-') {
		ans = op1 - op2;
	}

	if (a == '*') {
		ans = op1 * op2;
	}

	if (a == '/') {

		ans = 1.0 * op1 / op2;
	}

	return ans;
}

//前缀表达式和前缀相比，从后往前便利，先出栈的是op1，后出的为op2，其他类似

//中缀表达式转后缀
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char *InfixToPostfix(char a[]);
int IsOpeningParentheses(char a);
int IsClosingParentheses(char a);
int HasHigherPrec(char b, char c);
char res[100];
int main() {
	char a[100];
	gets(a);
	char *b = InfixToPostfix(a);
	puts(b);
}
char *InfixToPostfix(char a[]) {
	s = (Stack)malloc(sizeof(Node));
	s->next = NULL;
	int j = 0;
	for (int i = 0; i <= strlen(a) - 1; i++)
    {
		if (a[i] >= '0' && a[i] <= '9') 
        {
			res[j] = a[i];
			j++;
		} 
        else if (a[i] == '+' || a[i] == '-' || a[i] == '*' || a[i] == '/')
        {
		 while (!IsEmpty() && !IsOpeningParentheses(Top()) && HasHigherPrec(Top(), a[i]))             {
				res[j] = Top();
				j++;
				Pop();
			}
			Push(a[i]);
		} 
        else if (IsOpeningParentheses(a[i])) 
        {
			Push(a[i]);
		} 
        else if (IsClosingParentheses(a[i])) 
        {
			while (!IsEmpty() && !IsOpeningParentheses(Top())) {
				res[j] = Top();
				j++;
				Pop();
			}
			Pop();
		}
	}
	while (!IsEmpty()) 
    {
		res[j] = Top();
		j++;
		Pop();
	}
	return res;
}
int HasHigherPrec(char b, char c)
{
	if ((b == '+' || b == '-') && (c == '*' || c == '/')) {
		return 0;
	}
	if (IsOpeningParentheses(b) || IsClosingParentheses(b)) {
		return 0;
	}
	return 1;
}
int IsOpeningParentheses(char a)
{
	if (a == '(' || a == '{' || a == '[') 
    {
		return 1;
	}
	return 0;
}
int IsClosingParentheses(char a)
{
	if (a == ')' || a == '}' || a == ']')
    {
		return 1;
	}
	return 0;
}

/*
  Infix to postfix conversion in C++ 
  Input Postfix expression must be in a desired format. 
  Operands and operator, both must be single character.
  Only '+'  ,  '-'  , '*', '/' and '$' (for exponentiation)  operators are expected. 
*/
#include<iostream>
#include<stack>
#include<string>

using namespace std;

// Function to convert Infix expression to postfix 
string InfixToPostfix(string expression);

// Function to verify whether an operator has higher precedence over other
int HasHigherPrecedence(char operator1, char operator2);

// Function to verify whether a character is operator symbol or not. 
bool IsOperator(char C);

// Function to verify whether a character is alphanumeric chanaracter (letter or numeric digit) or not. 
bool IsOperand(char C);

int main() 
{
	string expression; 
	cout<<"Enter Infix Expression \n";
	getline(cin,expression);
	string postfix = InfixToPostfix(expression);
	cout<<"Output = "<<postfix<<"\n";
}

// Function to evaluate Postfix expression and return output
string InfixToPostfix(string expression)
{
	// Declaring a Stack from Standard template library in C++. 
	stack<char> S;
	string postfix = ""; // Initialize postfix as empty string.
	for(int i = 0;i< expression.length();i++) {

		// Scanning each character from left. 
		// If character is a delimitter, move on. 
		if(expression[i] == ' ' || expression[i] == ',') continue; 

		// If character is operator, pop two elements from stack, perform operation and push the result back. 
		else if(IsOperator(expression[i])) 
		{
			while(!S.empty() && S.top() != '(' && HasHigherPrecedence(S.top(),expression[i]))
			{
				postfix+= S.top();
				S.pop();
			}
			S.push(expression[i]);
		}
		// Else if character is an operand
		else if(IsOperand(expression[i]))
		{
			postfix +=expression[i];
		}

		else if (expression[i] == '(') 
		{
			S.push(expression[i]);
		}

		else if(expression[i] == ')') 
		{
			while(!S.empty() && S.top() !=  '(') {
				postfix += S.top();
				S.pop();
			}
			S.pop();
		}
	}

	while(!S.empty()) {
		postfix += S.top();
		S.pop();
	}

	return postfix;
}

// Function to verify whether a character is english letter or numeric digit. 
// We are assuming in this solution that operand will be a single character
bool IsOperand(char C) 
{
	if(C >= '0' && C <= '9') return true;
	if(C >= 'a' && C <= 'z') return true;
	if(C >= 'A' && C <= 'Z') return true;
	return false;
}

// Function to verify whether a character is operator symbol or not. 
bool IsOperator(char C)
{
	if(C == '+' || C == '-' || C == '*' || C == '/' || C== '$')
		return true;

	return false;
}

// Function to verify whether an operator is right associative or not. 
int IsRightAssociative(char op)
{
	if(op == '$') return true;
	return false;
}

// Function to get weight of an operator. An operator with higher weight will have higher precedence. 
int GetOperatorWeight(char op)
{
	int weight = -1; 
	switch(op)
	{
	case '+':
	case '-':
		weight = 1;
	case '*':
	case '/':
		weight = 2;
	case '$':
		weight = 3;
	}
	return weight;
}

// Function to perform an operation and return output. 
int HasHigherPrecedence(char op1, char op2)
{
	int op1Weight = GetOperatorWeight(op1);
	int op2Weight = GetOperatorWeight(op2);

	// If operators have equal precedence, return true if they are left associative. 
	// return false, if right associative. 
	// if operator is left-associative, left one should be given priority. 
	if(op1Weight == op2Weight)
	{
		if(IsRightAssociative(op1)) return false;
		else return true;
	}
	return op1Weight > op2Weight ?  true: false;
}

/*
  Evaluation Of postfix Expression in C++ 
  Input Postfix expression must be in a desired format. 
  Operands must be integers and there should be space in between two operands.
  Only '+'  ,  '-'  , '*' and '/'  operators are expected. 
*/
#include<iostream>
#include<stack>
#include<string>

using namespace std;

// Function to evaluate Postfix expression and return output
int EvaluatePostfix(string expression);

// Function to perform an operation and return output. 
int PerformOperation(char operation, int operand1, int operand2);

// Function to verify whether a character is operator symbol or not. 
bool IsOperator(char C);

// Function to verify whether a character is numeric digit. 
bool IsNumericDigit(char C);

int main() 
{
	string expression; 
	cout<<"Enter Postfix Expression \n";
	getline(cin,expression);
	int result = EvaluatePostfix(expression);
	cout<<"Output = "<<result<<"\n";
}

// Function to evaluate Postfix expression and return output
int EvaluatePostfix(string expression)
{
	// Declaring a Stack from Standard template library in C++. 
	stack<int> S;

	for(int i = 0;i< expression.length();i++) {

		// Scanning each character from left. 
		// If character is a delimitter, move on. 
		if(expression[i] == ' ' || expression[i] == ',') continue; 

		// If character is operator, pop two elements from stack, perform operation and push the result back. 
		else if(IsOperator(expression[i])) {
			// Pop two operands. 
			int operand2 = S.top(); S.pop();
			int operand1 = S.top(); S.pop();
			// Perform operation
			int result = PerformOperation(expression[i], operand1, operand2);
			//Push back result of operation on stack. 
			S.push(result);
		}
		else if(IsNumericDigit(expression[i])){
			// Extract the numeric operand from the string
			// Keep incrementing i as long as you are getting a numeric digit. 
			int operand = 0; 
			while(i<expression.length() && IsNumericDigit(expression[i])) {
				// For a number with more than one digits, as we are scanning from left to right. 
				// Everytime , we get a digit towards right, we can multiply current total in operand by 10 
				// and add the new digit. 
				operand = (operand*10) + (expression[i] - '0'); 
				i++;
			}
			// Finally, you will come out of while loop with i set to a non-numeric character or end of string
			// decrement i because it will be incremented in increment section of loop once again. 
			// We do not want to skip the non-numeric character by incrementing i twice. 
			i--;

			// Push operand on stack. 
			S.push(operand);
		}
	}
	// If expression is in correct format, Stack will finally have one element. This will be the output. 
	return S.top();
}

// Function to verify whether a character is numeric digit. 
bool IsNumericDigit(char C) 
{
	if(C >= '0' && C <= '9') return true;
	return false;
}

// Function to verify whether a character is operator symbol or not. 
bool IsOperator(char C)
{
	if(C == '+' || C == '-' || C == '*' || C == '/')
		return true;

	return false;
}

// Function to perform an operation and return output. 
int PerformOperation(char operation, int operand1, int operand2)
{
	if(operation == '+') return operand1 +operand2;
	else if(operation == '-') return operand1 - operand2;
	else if(operation == '*') return operand1 * operand2;
	else if(operation == '/') return operand1 / operand2;

	else cout<<"Unexpected Error \n";
	return -1; 
}

括号问题

#include <stdio.h>
#include <stdlib.h>
char a[70];
void Push(char t);
void Pop();
char Top();
int IsEmpty();
typedef struct Node {
	char x;
	struct Node *next;
} *Stack;
Stack s;
int main() {
	s = (Stack)malloc(sizeof(struct Node));
	s->next = NULL;
	gets(a);
	int a1 = 0;
	int a2 = 0;
	int a3 = 0;
	for (int i = 0; a[i] != '\0'; i++) {

		if (a[i] != '(' && a[i] != '{' && a[i] != '[' && a[i] != ')' && a[i] != '}' && a[i] != ']') {
			continue;
		}
		if (a[i] == '(' || a[i] == '{' || a[i] == '[') {
			Push(a[i]);
		}
		if (a[i] == ')' || a[i] == '}' || a[i] == ']') {
			char d = Top();
			if (IsEmpty()) {
				if (a[i] == ')')
					a1++;

				if (a[i] == '}')
					a3++;

				if (a[i] == ']')
					a2++;
			}
			else if (a[i] == d + 1 || a[i] == d + 2) {
				Pop();
			} else {
				if (a[i] == ')')
					a1++;

				if (a[i] == '}')
					a3++;

				if (a[i] == ']')
					a2++;

				if (d == '(')
					a1++;

				if (d == '{')
					a3++;

				if (d == '[')
					a2++;
				Pop();
			}
		}
	}
	while (!IsEmpty()) {
		char d = Top();
		//	printf("%c\n", d);

		if (d == '(')
			a1++;

		if (d == '[')
			a2++;

		if (d == '{')
			a3++;
		Pop();
	}

	if (a1 != 0)
		printf("1,");

	if (a2 != 0)
		printf("2,");

	if (a3 != 0)
		printf("3,");

	if (a1 == 0 && a2 == 0 && a3 == 0)
		printf("0");

}

KMP

#include <stdio.h>
#include <string.h>
void GetNext(int *next, char s[]);
int next[100004];

int main() {
	char s1[1000004];
	int n;
	scanf("%s", s1);
	scanf("%d", &n);
	int d1 = strlen(s1);

	for (int x = 1; x <= n; x++) {
		char s2[100004];
		scanf("%s", s2);
		int d2 = strlen(s2);
		GetNext(next, s2);
		int i = 0, j = 0;
		while (i < d1 && j < d2) {
			if (j == -1 || s1[i] == s2[j]) {
				i++;
				j++;
			} else
				j = next[j];
		}

		if (j == d2) {
			char *p;
			p = &s1[i - j];
			printf("%s\n", p);

		} else
			printf("Not Found\n");
	}
}
void GetNext(int *next, char s[]) {
	int j = 0, k = -1;
	next[0] = -1;
	int lens=strlen(s);
	while (j <lens) {
		if (k == -1 || s[j] == s[k]) {
			j++;
			k++;
            next[j] = k;
		} else
			k = next[k];
	}
}

树

二叉树

完美二叉树高度为[log2N];

平衡二叉树 搜索查找删除的效率都是（log2N）

平衡：所有节点，左子树与右子树的差不大于1；

二叉搜索树：左枝<=右枝；左枝<=根结点

二叉树的实现（插入查找）

//二叉树的插入和查找
#include<stdio.h>
typedef struct BstNode
{
    int data;
    BstNode*left;
    BstNode*right;
}BstNode;
BstNode* Insert(BstNode* root,int data);
bool Search(BstNode*root,int x);
int main()
{
    BstNode* root;
    root=Insert(root,15);
    root=Insert(root,10);
    root=Insert(root,20);
    root=Insert(root,25);
    root=Insert(root,8);
    root=Insert(root,12);
    return 0;
}
BstNode* Insert(BstNode* root,int data)
{
    if(root==NULL)
    {
        root=GetNode(data);
    }
    else if(data<=root->data)
    {
        root->left=Insert(root->left,data);
    }
    else
    {
        root->right=Insert(root->right,data);
    }
    return root;
}
bool Search(BstNode*root,int x)
{
    if(root==NULL)return false;
    else if(root->data==x)return true;
    else if(x<=root->data)return Search(root->left,x);
    else return Search(root->right,x);
}

查找最值

//
int FindMin(BstNode*root)
{
    if(root==NULL)
    {
        cout<<"Error:Tree is empty\n";
        return -1
    }
    BstNode*current=root;
    while(current->left!=NULL)
    {
        current=current->left;
    }
    return current->data;
}


//递归实现
int FindMin(BstNode*root)
{
    if(root==NULL)
    {
        cout<<"Error:Tree is empty\n";
        return -1;
    }
    else if(root->left==NULL)
    {
        return root->data;
    }
    return FindMin(root->left);
}

二叉树高度

int FindHeight(BstNode*root)
{
	if(root==NULL)
        return 0;
    int leftHeight=FindHeight(root->left);
    int rightHeight=FindHeight(root->right);
    return max(leftHeight,rightHeight)+1;
}

广度优先（BFS）Breadth First Search

// 
void LevelOrder(Node*root)
{
    if(root==NULL)return;
    queue<Node*>Q;
    Q.push(root);
    while(!Q.empty())
    {
        Node*current=Q.front();
        cout<<current->data<<" ";
        if(current->left!=NULL)Q.push(current->left);
        if(current->right!=NULL)Q.push(current->right);
        Q.pop();
    }
}

深度优先（DFS）Depth First Search

前中后序

//Preorder DLR    Inorder LDR     Postorder  LRD
void Preorder(Node*root)
{
    if(root==NULL)return;
    printf("%c ",root->data);
    Preorder(root->left);
    Preorder(root->right);
}
void Inorder(Node*root)
{
    if(root==NULL)return;
    Inorder(root->left);
    printf("%c ",root->data);
    Inorder(root->right);
}
void Postorder(Node*root)
{
    if(root==NULL)return;
    Postorder(root->left);
    Postorder(root->right);
    printf("%c ",root->data);
}

判断是否为二叉搜索树

bool IsBinarySearch(Node*root)
{
    if(root==NULL)return true;
    if(IsSubtreeLesser(root->left,root->data)&&IsSubtreeGreater(root->right,root->data)&&IsBinarySearch(root->left)&&IsBinarySearch(root->right))
        return true;
    else
        return false;
}
bool IsSubtreeGreater(Node*root,int value)
{
    if(root==NULL)return true;
    if(root->data>value&&IsSubtreeGreater(root->left,value)&&IsSubtreeGreater(root->right,value))
        return true;
    else
        return false;
}
bool IsSubtreeLesser(Node*root,int value)
{
    if(root==NULL)return true;
    if(root->data<=value&&IsSubtreeGreater(root->left,value)&&IsSubtreeGreater(root->right,value))
        return true;
    else
        return false;
}

//效率提高一点
bool IsBstUtil(Node*root,int minValue,int maxValue)
{
    if(root==NULL)return true;
    if(root->data<minValue&&root->data>maxValue&&IsBstUtil(root->left,minValur,root->data)&&IsBstUtil(root->right,root->data,maxValue))
        return true;
    else
        return false;
}
bool IsBinarySearchTree(Node*root)
{
    return IsBstUtil(root,INT_MIN,INT_MAX);
}

取消节点

c

后继节点

#inlcude<iostream>
using namespace std;
struct Node
{
    int data;
    struct Node*left;
    struct Node*right;
};
struct Node*Getsuccessor(struct Node*root,int data)
{
    struct Node*current=Find(root,data);
    if(current==NULL)return NULL;
    if(current->right!=NULL)
    {
        return FindMin(current->right);
    }
    else
    {
        struct Node*successor=NULL;
        struct Node*ancestor=root;
        while(ancestor=!=current)
        {
            if(current->data<ancestor->data)
            {
                successor=ancestor;
                ancestor=ancestor->left;
            }
            else
                ancestor=ancestor->right;
        }
        return successor;
    }
}

普通数的存储结构

typedef struct CSNode
{
    int data;
    struct CSNode*firstchild,*nextsibling;//第一个孩子和又兄弟指针
}CSNode,*CSTree;

数和森林的遍历

普通树的先序遍历

先序遍历与对应二叉树的先序遍历相同

普通树的中序遍历

中序遍历与对应二叉树的后序遍历相同

普通树的层次遍历

用队列实现

1. 若树非空，根节点入队
2. 若队列非空，队元素出队并访问，同时将该元素的孩子依次入队
3. 重复2直到队列为空

平衡二叉树（AVL）

调整最小不平衡子树

1. LL：
2. RR
3. LR
4. RL

avl树的实现（插入与删除）

//LL,LR,RR,RL
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
    int data;
    struct Node*left;
    struct Node*right;
    int height;
}AVLtree;
AVLtree*AVLInsert(AVLtree*root,int data);
void Perorder(AVLtree*root);
int max(int a,int b);
int Height(AVLtree*root);
AVLtree*SingleRotateLL(AVLtree*root);
AVLtree*DoubleRotateLR(AVLtree*root);
AVLtree*SingleRotateRR(AVLtree*root);
AVLtree*DoubleRotateRL(AVLtree*root);
int main()
{
    AVLtree*root=NULL;
    int data;
    while(scanf("%d,",&data)!=EOF)
    {
        root=AVLInsert(root,data);
    }
    Perorder(root);
}
void Perorder(AVLtree*root)
{
    if(root==NULL)return;
    printf("%d,",root->data);
    Perorder(root->left);
    Perorder(root->right);
}
AVLtree*AVLInsert(AVLtree*root,int data)
{
    if(root==NULL)
    {
        root=(AVLtree*)malloc(sizeof(AVLtree));
        root->data=data;
        root->height=0;
        root->left=root->right=NULL;
    }
    else if(data<root->data)
    {
        root->left=AVLInsert(root->left,data);
        if(Height(root->left)-Height(root->right)==2)
        {
            if(data<root->left->data)
            {
                root=SingleRotateLL(root);
            }
            else
            {
                root=DoubleRotateLR(root);
            }
        }
    }
    else if(data>root->data)
    {
        root->right=AVLInsert(root->right,data);
        if(Height(root->left)-Height(root->right)==-2)
        {
            if(data>root->right->data)
            {
                root=SingleRotateRR(root);
            }
            else
            {
                root=DoubleRotateRL(root);
            }
        }
    }
    root->height=max(Height(root->left),Height(root->right))+1;
    return root;
}
int max(int a,int b)
{
    if(a>b)return a;
    else return b;
}
int Height(AVLtree*root)
{
    if(root==NULL)return 0;
    else return max(Height(root->left),Height(root->right))+1;
}
AVLtree*SingleRotateLL(AVLtree*root)
{
    AVLtree*k=NULL;
    k=root->left;
    root->left=k->right;
    k->right=root;
    root->height=max(Height(root->left),Height(root->right))+1;
    k->height=max(Height(k->left),Height(k->right))+1;
    return k;
}
AVLtree*SingleRotateRR(AVLtree*root)
{
    AVLtree*k=NULL;
    k=root->right;
    root->right=k->left;
    k->left=root;
    root->height=max(Height(root->left),Height(root->right))+1;
    k->height=max(Height(k->left),Height(k->right))+1;
    return k;
}
AVLtree*DoubleRotateLR(AVLtree*root)
{
    root->left=SingleRotateRR(root->left);
    return SingleRotateLL(root);
}
AVLtree*DoubleRotateRL(AVLtree*root)
{
    root->right=SingleRotateLL(root->right);
    return SingleRotateRR(root);
}

哈夫曼树

带权路径长度

哈夫曼树的构造

合并n-1次，2n-1个结点，无度为1的结点，不唯一

哈夫曼树的实现

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
class Node
{
public:
    int f;
    char huffman;
    Node*left;
    Node*right;
};
typedef Node* HTtreeNode;
bool cmp(HTtreeNode a,HTtreeNode b)
{
    return a->f<b->f;
}
HTtreeNode merge(HTtreeNode a,HTtreeNode b);
int main()
{
    int num[]={7,19,2,6,32,3,21,10};
    vector<HTtreeNode> v;
    for(int i=0;i<sizeof(num)/sizeof(num[0]);i++)
    {
        HTtreeNode temp=new Node;
        temp->f=num[i];
        temp->huffman='a'+i;
        temp->left=nullptr;
        temp->right=nullptr;
        v.push_back(temp);
    }
    while(v.size()!=1)
    {
        sort(v.begin(),v.end(),cmp);
        HTtreeNode t=merge(v[0],v[1]);
        v.erase(v.begin()+1);
        v[0]=t;
    }
    HTtreeNode Huffmantree=v[0];
    string buf;
    cin>>buf;
    HTtreeNode ptr=Huffmantree;
    for(char c:buf)
    {
        if(c=='1')
        {
            ptr=ptr->right;
        }
        else if(c=='0')
        {
            ptr=ptr->left;
        }
        if(ptr->huffman!='\0')
        {
            cout<<ptr->huffman;
            ptr=Huffmantree;
        }
    }
    return 0;
}
HTtreeNode merge(HTtreeNode a,HTtreeNode b)
{
    HTtreeNode temp=new Node;
    temp->left=a;
    temp->right=b;
    temp->huffman='\0';
    temp->f=a->f+b->f;
    return temp;
}

哈夫曼编码

图

图的一些基本性质

无向图，有向图；有向边，无向边；

顶点的度：

入度出度：

路径

回路（环）

简单路径

路径长度

点到点的距离

连通

强连通

连通图

强连通图

子图

极大连通子图

生成树

带权图

带权路径长度

图的表示（邻接矩阵）

图的表示（邻接表）

typedef struct ArcNode
{
    int adjvex;
    struct ArcNode*next;
    //IndoType info;
}ArcNode;
typedef struct VNode
{
    VertexType data;
    ArcNode*first;
}VNode,AdjList[MaxVertexNum];
typedef struct
{
    AdjList vertices;
    int vexnum,arcnum;
}ALGraph;

十字链表 邻接多重表

BFS广度搜索

bool visited[MAX_VERTEX_NUM];
void BFSTraverse(Graph G)
{
    for(int i=0;i<G.vexnum;i++)
        visited[i]=FALSE;
    InitQueue(Q);
    for(int i=0;i<G.vexnum;i++)
        if(!visited[i])
            BFS(G,i);
}
void BFS(Graph G,int v)
{
    visit(v);
    visited[v]=TRUE;
    Enqueue(Q,v);
    while(!isEmpty(Q))
    {
        DeQueue(Q,v);
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
        {
            if(!visited[w])
            {
                visit(w);
                visited[w]=TRUE;
                EnQueue(Q,w);
            }
		}
    }
}

DFS深度搜索

bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph)
{
    for(v=0;v<G.vexnum;++v)
        visited[v]=FALSE;
    for(v=0;v<G.vexnum;++V)
        if(!visited[v])
            DFS(G,v);
}
void DFS(Graph G,int v)
{
    visit(v);
    visited[v]=TRUE;
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighor(G,v,w))
        if(!visited[w])
        {
            DFS(G,w);
        }
}

最小生成树MST

Prim算法

O(V^2)适合边稠密

Kruskal算法克鲁斯卡尔

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<stdio.h>
using namespace std;
struct Node
{
    int init;
    int end;            //init，end为两个结点
    int weight;    
    Node(int a,int b,int c):init(a),end(b),weight(c){}
};
bool cmp(Node a,Node b)
{
    return a.weight<b.weight;
}
bool isequal(char a,char b,Node edge)//用于输入之后的更改权重，
{
    if(a==edge.end&&b==edge.init)return true;
    if(a==edge.init&&b==edge.end)return true;
    return false;
}
int main()
{
    vector<Node>edge;
    vector<Node>mintree;
    int a[200];
    for(int i='A';i<='J';i++)
    {
        a[i]=i;
    }//初始化并查集
    edge.push_back(Node('A','B',3));
    edge.push_back(Node('A','E',4));
    edge.push_back(Node('A','D',4));
    edge.push_back(Node('B','E',2));
    edge.push_back(Node('F','B',3));
    edge.push_back(Node('C','B',10));
    edge.push_back(Node('C','F',6));
    edge.push_back(Node('C','G',1));
    edge.push_back(Node('D','E',5));
    edge.push_back(Node('D','H',6));
    edge.push_back(Node('E','H',2));
    edge.push_back(Node('E','I',1));
    edge.push_back(Node('E','F',11));
    edge.push_back(Node('F','I',3));
    edge.push_back(Node('F','J',11));
    edge.push_back(Node('F','G',2));
    edge.push_back(Node('G','J',8));
    edge.push_back(Node('H','I',4));
    edge.push_back(Node('I','J',7));
    char m,n;
    int c;
    scanf("%c,%c,%d",&m,&n,&c);
    for(int i=0;i<19;i++)
    {
        if(isequal(m,n,edge[i]))
        {
            edge[i].weight=c;//改权重
        }
    }
    sort(edge.begin(),edge.end(),cmp);//排序
    int cnt=0;
    // mintree.push_back(edge[0]);
    for(int i=0;;i++)
    {
        if(a[edge[i].init]!=a[edge[i].end])//两个结点不属于同一集合
        {
            mintree.push_back(edge[i]);//放入生成树中
            int elem=a[edge[i].end];//准备把和edge[i].end一个集合的元素都纳入init的集合中
            for(int j='A';j<='J';j++)
            {

                if(a[j]== elem)
                {
                    a[j]=a[edge[i].init];
                }
            }
            cnt++;
            if(cnt==9)break;
        }
    }
    for(int i=0;i<9;i++)
    {
        cout<<mintree[i].weight<<',';
    }
    return 0;
}
    

O(E*logE) 适合边稀疏图

单源最短路径

BFS算法（无权图）

//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G,int u)
{
    //d[i]表示从u到i结点的最短路径
    for(int i=0;i<G.vexnum;i++)
    {
        d[i]=INF;
        path[i]=-1;
    }
    d[u]=0;
    visited[u]=TRUE;
    EnQueue(Q,u);
    while(!isEmpty)
    {
		DeQueue(Q,u);
        for(w=FirstNeighbor(G,u);w>=0;w=NextNeighboe(G,u,w))
            if(!visited[w])
            {
                d[w]=d[u]+1;
                path[2]=u;
                visited[w]=TRUE;
                EnQueue(Q,w);
            }
    }
}

Dijkstra（带权、无权）负权无效

#include<iostream>
#include<string>
#include<vector>
#include<string.h>
#include<stack>
using namespace std;
struct Node{
    int length;
    int x;
    Node(int _x, int _length):x(_x),length(_length){}
};
int dis[8];
int vis[8];
int front[8];
vector<Node>g[8];

void dijikstra(int s)
{
    memset(dis,63,sizeof(dis));
    dis[s]=0;
    front[s]=-1;
    for(int i=1;i<=7;i++)
    {
        int u=0;
        int mind=0x3f3f3f3f;
        for(int j=1;j<=7;j++)
        {
            if(!vis[j]&&dis[j]<mind)u=j,mind=dis[j];
        }
        vis[u]=true;
        for(auto ed:g[u])
        {
            int v=ed.x,w=ed.length;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                front[v]=u;
            }
        }
    }

}
int main()
{
    int a,b;
    cin>>a;
    cin.get();
    cin>>b;
    g[1].push_back(Node(4,1));
    g[1].push_back(Node(2,2));
    g[2].push_back(Node(4,3));
    g[2].push_back(Node(5,10));
    g[3].push_back(Node(1,4));
    g[3].push_back(Node(6,5));
    g[4].push_back(Node(3,2));
    g[4].push_back(Node(5,2));
    g[4].push_back(Node(6,8));
    g[4].push_back(Node(7,4));
    g[5].push_back(Node(7,6));
    g[7].push_back(Node(6,1));
    dijikstra(a);
    // for(int i=1;i<=7;i++)
    // {
    //     cout<<front[i]<<' ';
    // }
    if(dis[b]==0x3f3f3f3f)
    {
        cout<<-1;
        return 0;
    }
    stack<int>s;
    s.push(b);
    while(front[b]!=-1)
    {
        b=front[b];
        s.push(b);
    }
    while(!s.empty())
    {
        cout<<s.top()<<',';
        s.pop();
    }
    return 0;
}

各顶点最短路径

Floyd（带权、无权）负权回路无效

动态规划

//O(V^3);
for(int k=0;k<n;k++)
{
    for(i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(A[i][j]>A[i][k]+A[k][j])
            {
                A[i][j]=A[i][k]+A[k][j];
                path[i][j]=k
            }
        }
    }
}

DAG图有向无环图

拓扑排序

aov网

拓扑排序：找到avo网里事情的先后顺序

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

class Solution
{
private:
    bool Graph[11][11]={false};
    int in[11];
    void initial()
    {
        Graph[0][1] = true, Graph[0][4] = true, Graph[0][7] = true, in[0] = 0;
        Graph[1][2] = true, Graph[1][5] = true, in[1] = 2;
        Graph[2][3] = true, in[2] = 1;
        Graph[3][10] = true, in[3] = 3;
        Graph[4][1] = true, Graph[4][5] = true, in[4] = 2;
        Graph[5][3] = true, Graph[5][6] = true, Graph[5][9] = true, in[5] = 4;
        Graph[6][3] = true, Graph[6][10] = true, in[6] = 2;
        Graph[7][4] = true, Graph[7][5] = true, Graph[7][8] = true, in[7] = 1;
        Graph[8][5] = true, Graph[8][9] = true, in[8] = 1;
        Graph[9][6] = true, Graph[9][10] = true, in[9] = 2;
        in[10] = 3;
    }
    int atoIndex(char alpha)
    {
        if(alpha=='S')
        {
            return 0;
        }
        if(alpha=='T')
        {
            return 10;
        }
        return alpha-'A'+1;
    }
    char itoAlpha(int index)
    {
        if(index==0)
        {
            return 'S';
        }
        if(index==10)
        {
            return 'T';
        }
        return 'A'+index-1;
    }
public:
    void topological_sort(void)
    {
        initial();
        string input;
        cin>>input;
        Graph[atoIndex(input[0])][atoIndex(input[2])]=false;
        in[atoIndex(input[2])]--;
        queue<int>zeroInDegreeNode;
        for(int i=0;i<11;i++)
        {
            if(in[i]==0)
            {
                zeroInDegreeNode.push(i);
            }
        }
        while(zeroInDegreeNode.size()!=0)
        {
            int outVertex=zeroInDegreeNode.front();
            zeroInDegreeNode.pop();
            cout<<itoAlpha(outVertex)<<',';
            for(int i=0;i<11;i++)
            {
                if(Graph[outVertex][i])
                {
                    in[i]--;
                    if(in[i]==0)
                    {
                        zeroInDegreeNode.push(i);
                    }
                }
            }
        }
    }
};
int main()
{
    Solution().topological_sort();
    return 0;
}

关键路径

排序

插入排序(Insertion Sort)

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[21];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];getchar();
    }

        int j;
    for(int i=1;i<n;i++)
    {
        int temp=a[i];
        for(j=i;j>0&&a[j-1]>temp;j--)
        {
            a[j]=a[j-1];
        }
        a[j]=temp;
        for(int k=0;k<n;k++)cout<<a[k]<<',';
        cout<<'\n';
    }
}

希尔排序(Shell Sort)

#include<iostream>
using namespace std;
void ShellSort(int a[],int n);
int main()
{
    int n;
    cin>>n;
    int a[21];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        getchar();
    }
    ShellSort(a,n);
    return 0;
}
void ShellSort(int a[],int n)
{
    int i,j,Increment;
    int tmp;
    for(Increment=n/2;Increment>0;Increment/=2)
    {
        for(i=Increment;i<n;i++)
        {
            tmp=a[i];
            for(j=i;j>=Increment;j-=Increment)
            if(tmp>a[j-Increment])
            a[j]=a[j-Increment];
            else break;
            a[j]=tmp;
        }
        for(int i=0;i<n;i++)cout<<a[i]<<',';
        cout<<'\n';
    }
}

冒泡排序

#include<iostream>
using namespace std;
void BubbleSort(int *a,int n);
int main()
{
    int n;
    int a[1000];
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        getchar();
    }
    BubbleSort(a,n);

    return 0;
}
void BubbleSort(int *a,int n)
{
    for(int i=0;i<n-1;i++)
    {
        for(int j=0;j<n-i-1;j++)
        {
            if(a[j]>a[j+1])
            {
                int temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
    for(int i=0;i<n;i++)cout<<a[i]<<',';
}

快排

#include <iostream>
#include <stdio.h>
using namespace std;
int N = 10;
int cnt = 0;
int First_pivot;

void Swap(int *a, int *b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}
void Qsort(int a[], int left, int right);
int Median3(int a[], int left, int right);
void InsertionSort(int a[], int left, int right);

int main() {
	int a[10] = {49,38,65,97,76,13,27,50,2,8};
    cin>>First_pivot;
	Qsort(a, 0, 9);
}
void Qsort(int a[], int left, int right) {
    if(cnt==0)
    {
        printf("Qsort(%d,%d):",left,right);
        int pivot=a[First_pivot];
    Swap(&a[First_pivot],&a[9]);
    int i=0,j=8;
		for (;;) {

			while (a[i] < pivot) {i++;}

			while (a[j] > pivot) {j--;}

			if (i < j) {
				Swap(&a[i],&a[j]);
			} 
            else
				break;
		}
	Swap(&a[i],&a[9]);
    cnt++;
    for (int k = 0; k < N; k++)cout << a[k] << ',';
	cout << '\n';
    Qsort(a, left, i - 1);
	Qsort(a, i + 1, right);
    }
    else{
	int i, j;
	int Pivot;
	if (left + 2 < right) {
        printf("Qsort(%d,%d):",left,right);
		Pivot = Median3(a, left, right);
		i = left;
		j = right - 1;

		for (;;) {

			while (a[++i] < Pivot) {}

			while (a[--j] > Pivot) {}

			if (i < j) {
				Swap(&a[i],&a[j]);
			} else
				break;
		}
		Swap(&a[i],&a[right-1]);
        for (int k = 0; k < N; k++)cout << a[k] << ',';
	cout << '\n';
		Qsort(a, left, i - 1);
		Qsort(a, i + 1, right);
	} else
    {
		InsertionSort(a + left, left, right);
        for (int k = 0; k < N; k++)cout << a[k] << ',';
	cout << '\n';
    }}
}

int Median3(int a[], int left, int right) {
	int center = (left + right) / 2;

	if (a[left] > a[center])
		Swap(&a[left], &a[center]);

	if (a[left] > a[right])
		Swap(&a[left], &a[right]);

	if (a[center] > a[right])
		Swap(&a[center], &a[right]);
	Swap(&a[center], &a[right - 1]);
	return a[right - 1];
}

void InsertionSort(int a[], int left, int right) {
	int j;
	int n = right - left + 1;

	printf("insert(%d,%d):",left,n);
	for (int i = 1; i < n; i++) {

		int temp = a[i];

		for (j = i; j > 0 && a[j - 1] > temp; j--) {

			a[j] = a[j - 1];
		}

		a[j] = temp;
	}
    
}
//insert(9,1):2,8,13,27,38,49,50,65,76,97,

选择排序

#include<iostream>
using namespace std;
void SelectionSort(int a[],int n);
int main()
{
    int a[21];
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];getchar();
    }
    SelectionSort(a,n);
}
void SelectionSort(int a[],int n)
{   int j;int temp=0;
    for(int i=0;i<n-1;i++)
    {
        int Min=0x3f3f3f3f;
        for(j=i;j<n;j++)
        {
            if(Min>a[j])
            {
                Min=a[j];temp=j;
            }
            
        }
        a[temp]=a[i];
        a[i]=Min;
        for(int i=0;i<n;i++)cout<<a[i]<<',';
        cout<<'\n';
    }
}

堆排序

#include <bits/stdc++.h>
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int n;
void HeapSort(int a[],int len);
void downadjust(int a[],int start,int end);
int main()
{
    int a[50];
    char b[50];
    int cnt=0;
    scanf("%s",b);
    char str[10];
    int k=0;
    for(int i=0;b[i]!='\0';i++)
    {
        if(b[i]!=',')
        {
            str[k]=b[i];
            k++;
        }
        else
        {
            str[k]='\0';
            sscanf(str,"%d",&a[cnt]);cnt++;
            k=0;
        }
    }
    cin>>n;
    HeapSort(a,cnt);
}
void HeapSort(int a[],int len)
{
    for(int j=(len-1)/2;j>=0;j--)
    {
        downadjust(a,j,len-1);
    }
    if(n==1)for(int j=0;j<len;j++)cout<<a[j]<<',';
    for(int j=len-1;j>0;j--)
    {   
        swap(a[0],a[j]);
        downadjust(a,0,j-1);
                n--;
        if(n==1)
    {
        for(int j=0;j<len;j++)cout<<a[j]<<',';
        return;
    }
    }
}
void downadjust(int a[],int start,int end)
{   
    int record=a[start],j;
    for(j=2*start+1;j<=end;j=j*2+1)
    {
        if(j<end&&a[j]<=a[j+1])
        {
            j++;
        }
        if(a[j]<=record)
        {
            break;
        }
        a[start]=a[j];
        start=j;
    }
    a[start]=record;
}

归并排序

桶排序