基本数据结构与算法

Posted on | | Visitors:

放一些基本的数据结构与算法的代码，方便复习，查漏补缺。

目录：

1. 直接插入排序
2. 折半直接插入排序
3. 快速排序
4. 归并排序
5. 冒泡排序
6. 堆排序
7. 希尔排序
8. 二叉树递归遍历
9. 二叉树非递归遍历
10. 二叉树层次遍历
11. kmp字符串搜索—待填
12. 头插法链表转置—待填

直接插入排序


假设前i个已经排好序，时间复杂度为O(n*n)，稳定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void insert_sort(int *A,int size)
{
	//升序
	int key,j;
	for(int i=1;i<size;i++)
	{
		key = A[i];
		j = i-1;
		while(j>=0 && A[j] > key)
		{
			A[j+1] = A[j];
			j--;
		}
		A[j+1] = key;
	}
}


折半直接插入排序

插入排序是将第i个数插入到，前i-1个有序数字里面，折半排序只是将在前i-1个有序树中查找的过程改成了二分法。由于数字移动次数没有改变，复杂度仍为O(N*N),稳定。

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
27
28
void bs_insert_sort(int *A,int size)
{
	//升序
	int key,high,low,mid;

	for(int i=1;i<size;i++)
	{
		key = A[i];
		high = i-1;
		low = 0;
		//二分查找
		while(low<high)
		{
			mid = (low+high)/2;
			if(A[mid] >= key)
				high = mid-1;
			else low = mid+1;
		}
		high = i-1;
		//移动数字
		while(low<=high)
		{
			A[high+1] = A[high];
			high--;
		}
		A[low] = key;
	}
}

快速排序

平均复杂度为O(NlogN),最坏复杂度O(NN),即数据本来就是有序的，不稳定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int partition(int *A, int low,int high)
{
	int priv = A[low];
	while (low < high)
	{
		while (low < high && A[high]>=priv)high--;
		A[low] = A[high];
		while (low < high && A[low]<=priv)low++;
		A[high] = A[low];
	}
	A[low] = priv;
	return low;
}

void quick_sort(int *A, int low, int high)
{
	if(low<high)
	{
		int mid = partition(A, low, high);
		quick_sort(A,low, mid);
		quick_sort(A,mid+1,high);
	}
}

归并排序

时间复杂度为O(N*logN),空间复杂度为O(N),稳定。

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
void merge_array(int *A, int i, int j, int k,int *C)
{
	int mid = j,index=i;
	while (i <= mid && j+1 <= k)
	{
		if (A[i] < A[j+1])
		{
			C[index++] = A[i];
			i++;
		}
		else
		{
			C[index++] = A[j + 1];
			j++;
		}
	}
	while (i <= mid)
	{
		C[index++] = A[i++];
	}
	while (j + 1 <= k)
	{
		C[index++] = A[j + 1];
		j++;
	}
	//将C复制给A
	for (i = 0; i < index; i++)
		A[i] = C[i];
}

void merge_sort(int *A, int first,int last,int *C)
{
	/*
	//全局变量
	int *C = new int[size_A];
	*/
	if (first < last)
	{
		int mid = (first + last) / 2;
		merge_sort(A, first, mid,C);
		merge_sort(A, mid + 1, last,C);
		merge_array(A, first, mid, last, C);
	}	
}

冒泡排序

冒泡是依次将最大的数冒泡到数组最后端，时间复杂度为O(N*N),稳定。最好加一个flag，如果某一趟遍历之后一个数据都没有交换，证明被遍历的部分数组本来就是有序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void bubble_sort(int *A,int n)
{
	int flag = 1;
	for(int i=0;i<n;i++)
	{
		flag = 1;
		for(int j=0;j<n-i-1;j++)
		{
			//升序
			if(A[j]>A[j+1])
			{
				int tmp = A[j];
				A[j] = A[j+1];
				A[j+1] = tmp;
				flag = 0;
			}
		}
		if(flag)break;
	} 
}

堆排序

堆排序相对比较复杂，堆是一个二叉树，首先对于数组A[n],i节点的子节点为2i+1和2i+2,i的父节点为(i-1)/2。调整堆时从最后一个叶子节点的父节点开始。
首先需要一个调整堆的函数fix()，这个函数的功能是调整A[i…n)为大根堆，他的假设是子树已经是大根堆，但调整之后可能会发生变化，所以要循环往下调整，如果调整之后子树仍然是大根堆就跳出循环。堆排序的第一步是建立一个大根堆，可以利用fix()，从最后一个叶子节点的父节点循环向堆顶调整;交换A[0]和A[n-1]，用fix()调整A[0…n-1)(不包括n-1)，调整完之后首尾交换…..

时间复杂度为O(N*logN),不稳定。

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
27
28
29
30
31
32
33
34
//升序,调整A[i...n),不包括n
void fix(int *A,int i,int n)
{
	int j = 2*i+1;
	int tmp = A[i];
	while(j<n)
	{
		//取子节点中最大的一个
		if(j+1<n && A[j]<A[j+1])
			j++;
		if(tmp >= A[j])
			break;
		A[i] = A[j];
		i = j;
		j = 2*i+1;
	}
	A[i] = tmp;
}

void heap_sort(int *A,int n)
{
	//初始建立大根堆
	for(int i=(n-2)/2;i>=0;i--)
		fix(A,i,n);

	//交换A[0]和A[n-1],然后用fix调整
	for(int i=n;i>0;i--)
	{
		int tmp = A[0];
		A[0] = A[i-1];
		A[i-1] = tmp;
		fix(A,0,i-1);
	}
}

希尔排序

希尔排序按步长进行直插排序，第一次步长为G，将A[0],A[G],A[2G]作为一组，A[1],A[1+G],A[1+2G]作为一组….，下一次迭代步长为G=G/2。步长为1是就是直接插入排序了。
时间复杂度为O(N1.25),不稳定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void shell_sort(int *A,int n)
{
	for(int gap=n/2;gap>0;gap=gap/2)
	{
		for(int i=0;i<gap;i++)
		{
			for(int j=i+gap;j<n;j+=gap)
			{
				int tmp = A[j];
				int k=j-gap;
				while(k>=i&&A[k]>tmp)
				{
					A[k+gap] = A[k];
					k-=gap;
				}
				A[k+gap] = tmp;
			}
		}
	}
}

改进版即上面的for(i=0;i<gap;i++)和for(j=i;j<n;j+=gap)可以合并到一起。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void shell_sort(int *A,int n)
{
	for(int gap=n/2;gap>0;gap=gap/2)
	{
		for(int i=gap;i<n;i++)
		{
			int tmp = A[i];
			int j = i-gap;
			while(j>=0&&A[j]>tmp)
			{
				A[j+gap] = A[j];
				j-=gap;
			}
			A[j+gap] = tmp;
		}
	}
}

二叉树递归遍历

树的定义:

1
2
3
4
5
6
struct BsTree
{
	ElementType val;
	BsTree *left;
	BsTree *right;
};

树的建立请参见这里

先序遍历：

1
2
3
4
5
6
7
8
9
void preorder_travel(BsTree *root)
{
	if(root!=NULL)
	{
		visit(root);
		preorder_travel(root->left);
		preorder_travel(root->right);
	}
}

中序遍历：

1
2
3
4
5
6
7
8
9
void inorder_travel(BsTree *root)
{
	if(root!=NULL)
	{
		inorder_travel(root->left);
		visit(root);
		inorder_travel(root->right);
	}
}

后序遍历：

1
2
3
4
5
6
7
8
9
void postorder_travel(BsTree *root)
{
	if(root!=NULL)
	{
		postorder_travel(root->left);
		postorder_travel(root->right);
		visit(root);
	}
}

二叉树非递归遍历

非递归遍历实际就是用栈模拟递归调用过程。

前序遍历：先将根入栈，以队列不为空为循环条件，进入循环后开始出栈，出栈的同时按照先右后左的顺序将子节点入栈，比较无脑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> preorderTraversal(TreeNode* root) {
        //非递归
        vector<int> ret;
        stack<TreeNode*> st;
        if(root)st.push(root);
        TreeNode *tmp;
        while(!st.empty())
        {
            tmp = st.top();
            ret.push_back(tmp->val);
            st.pop();
            if(tmp->right)st.push(tmp->right);
            if(tmp->left)st.push(tmp->left);
        }
        return ret;
    }

中序遍历：中序遍历稍微要麻烦一点，需要设置一个是否出栈的flag，因为当一个节点出栈有两种情况，一个是没有左子树，还有一个是左子树已经被遍历过了。初始将flag设置为进栈，如果有左子树，左子树进栈。当该节点没有左子树时则直接出栈，且将右孩子入栈，若没有右孩子说明该节点的父节点左边已经遍历结束，此时flag设置为出栈，即父节点需要出栈。父节点出栈的同时父节点的右孩子入栈，flag设置为进栈。

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

vector<int> inorderTraversal(TreeNode* root) { 
    //非递归
    vector<int> ret;
    stack<TreeNode*> st;
    TreeNode *tmp;
    bool flag = false;
    if(root)
    {
        st.push(root);
        //是否入栈
        if(root->left)flag=true;
    }
    while(!st.empty())
    {
        //入栈
        if(flag)
        {
            tmp = st.top();
            if(tmp->left)st.push(tmp->left);
            else
            {
                ret.push_back(tmp->val);
                st.pop();
                if(tmp->right)st.push(tmp->right);
                else flag=false;
            }
        }
        //出栈
        else
        {
            tmp = st.top();
            ret.push_back(tmp->val);
            st.pop();
            if(tmp->right)
            {
                st.push(tmp->right);
                flag=true;
            }
        }
    }
    return ret;
    
}

后续遍历：后续遍历也要加一个标志，该标志记录最后一次出栈的元素。首先将根节点入栈，进入循环后，判断符不符合出栈的条件。出栈有两个条件：一个是该节点是一个叶子节点，另一个是该节点的孩子节点曾经被访问过，即标记位是否等于该节点的某一个孩子。由于入栈是将两个孩子按先右后左的顺序入栈，所以孩子一定在父节点之前出栈。两个条件满足其中一个便出栈，否则两个孩子均入栈。该题目在leetcode上标记为hard。

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
27

vector<int> postorderTraversal(TreeNode* root) { 
    //非递归
    vector<int> ret;
    stack<TreeNode*> st;
    TreeNode *tmp;
    TreeNode *pre=NULL;
    if(root)st.push(root);
    while(!st.empty())
    {
        tmp = st.top();
        if((tmp->left==NULL&&tmp->right==NULL)||(pre!=NULL&&(pre==tmp->left||pre==tmp->right)))
        {
            ret.push_back(tmp->val);
            st.pop();
            pre = tmp;
        }
        else
        {
            if(tmp->right)
                st.push(tmp->right);
            if(tmp->left)
                st.push(tmp->left);
        }
    }
    return ret;
}

二叉树层次遍历

层序遍历利用队列，先将根加入队列，以队列不为空为循环条件，依次取队列的元素，出队列的同时将其左孩子和右孩子加入队列。如果需要按层次保存（打印），则每次循环的时候算一下队列的长度，一次性把队列内所有的元素（一层）都出队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

vector<vector<int>> levelOrder(TreeNode* root) {
    queue<TreeNode*>qu;
    vector<vector<int>> ret;
    TreeNode *tmp;
    if(root)qu.push(root);
    while(!qu.empty())
    {
        int size = qu.size();
        vector<int> sub;
        for(int i=0;i<size;i++)
        {
            tmp = qu.front();
            qu.pop();
            sub.push_back(tmp->val);
            if(tmp->left)qu.push(tmp->left);
            if(tmp->right)qu.push(tmp->right);
        }
        ret.push_back(sub);
    }
    return ret;
}

kmp字符串搜索


头插法链表转置