此页面记录我在学习数据结构时遇到的一些难点

二叉树

节点定义

1
2
3
4
5
// 定义节点
typedef struct BiTNode{
    int data;
    struct BiTNode *Lchid,*Rchid;
}BiTNode,*BiTree;

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
// 排序二叉树的插入
int BST_Insert(BiTree &T, int number){
    if(T == NULL){
        T = new BiTNode;
        T->data = number;
        T->Lchid = T->Rchid = NULL;
        return 1;
    }
    else if(T->data == number) return 0;
    else if(number < T->data) return BST_Insert(T->Lchid, number);
    else if(number > T->data) return BST_Insert(T->Rchid, number);
    return 0;
}

查找

1
2
3
4
5
6
7
8
//有序二叉树的查找
BiTNode *BST_Search(BiTree T,int number){
	while(T!=NULL&&number!=T->data){
		if(number>T->data) T=T->Rchid;
		else T=T->Lchid; 
	}
	return T;
}

遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 二叉树的先序遍历
void PreOrder(BiTree T){
    if(T != NULL){
        cout << T->data << " ";
        PreOrder(T->Lchid);
        PreOrder(T->Rchid);
    }
}

// 二叉树的中序遍历
void InOrder(BiTree T){
	if(T!=NULL){
		InOrder(T->Lchid);
		cout<<T->data << " ";
		InOrder(T->Rchid);
	}
} 

// 二叉树的后序遍历
void PostOrder(BiTree T){
	if(T!=NULL){
		PostOrder(T->Lchid);
		PostOrder(T->Rchid);
		cout<<T->data << " ";
	}
}

kmp算法

吐槽:好好好，kmp考纲不参考《算法笔记》，反而按照国内自己的教材，真麻烦

1
2
3
4
5
6
7
8
9
10
11
12
void kmp(string s){
	int i,k=0;
	next[0]=0;
	for(i=1;i<s.size();i++){
		while(k>0 && s[i]!=s[k])k=next[k-1];
		if(s[i]==s[k])k++;
		next[i]=k;
	}
	for(i=0;i<s.size();i++){
		printf("%d",next[i]);
	}
}

手动求nextval数组（模式串下标从1开始）
若在KMP算法设计中，将模式串下标从1开始计数，那么求nextval数组的算法步骤为：
（1）求出next数组的值（定义next[1]=0，next[2]=1）；
（2）定义nextval[1]=0。然后，比较模式串的第j个（j>1）字符是否与第next[j]个字符相等。若相等，则模式串第j个字符的nextval值等于第next[j]个字符的nextval值。若不等，则模式串第j个字符的nextval值等于其next数组值。

1
2
3
if(T[j]==T[next[j]])
    nextval[j]=nextval[next[j]];
else nextval[j]=next[j]。

手动求nextval数组（模式串下标从0开始）
若在KMP算法设计中，将模式串下标从0开始计数，那么求nextval数组的算法步骤为：
（1）求出next数组的值（定义next[0]=-1，next[1]=0）；
（2）定义nextval[0]=-1。然后，比较模式串的第j个（j>0）字符是否与第next[j]个字符相等。若相等，则模式串第j个字符的nextval值等于第next[j]个字符的nextval值。若不等，则模式串第j个字符的nextval值等于其next数组值。

树

(1)树中的结点数等于所有结点的的度数之和加1
(2)度为m的树中第i层上至多有m^(i-1)个结点(i>=1)
(3)高度为h的m叉树至多有(m^h-1)/(m-1)个结点
(4)具有n个结点的m叉树的最小高度为logm(n(m-1)+1) 还要取整

排序

直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
using namespace std;

void InsertSort(int *arr,int n){
	int i,j;
	for(i=2;i<=n;i++){
		if(arr[i]<arr[i-1]){
			arr[0]=arr[i];
			for(j=i-1;arr[0]<arr[j];j--){
				arr[j+1]=arr[j];
			}
			arr[j+1]=arr[0];
		}
	}
}

半折插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void InsertSort(int *arr,int n){
	int i,j,low,high,mid;
	for(i=2;i<=n;i++){
		arr[0]=arr[i];
		low=1,high=i-1;
		while(low<=high){
			mid=(low+high)/2;
			if(arr[mid]>arr[0]){
				high=mid-1;
			}else low=mid+1;
		}
		for(j=i-1;j>=high+1;j--){
				arr[j+1]=arr[j];
		}
		arr[high+1]=arr[0];
		}
}

希尔排序