基本算法模板整理——链表，二叉树，快速排序

一些模板

1、链表

1）链表节点的定义

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};
1
2
3
4
5
6
7

2）链表节点的初始化

ListNode* initList(vector<int>v) {
    auto begin = v.begin();
    auto end = v.end();
    //新建哑结点
    ListNode* dummyHead = new ListNode(0);
    ListNode* now = dummyHead;
    while (begin != end) {

        cout << *begin << endl;

        ListNode* node = new ListNode(*begin);
        now->next = node;
        now = node;
        begin++;
    }
    return dummyHead->next;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2）链表的打印

void printList(ListNode* head) {
    cout << "链表的节点值为:";
    while (head != NULL) {
        cout << head->val <<"  ";
        head = head->next;
    }
}
1
2
3
4
5
6
7

2、二叉树

1)二叉树节点的定义

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) {}
};
1
2
3
4
5
6
7
8

2)从数组中初始化二叉树代码

以-1为空节点

TreeNode* initBTree(int elements[], int size)
{

    if (size < 1)
    {
        return NULL;
    }
    if (size == 1 && elements[0] == 0) return NULL;
    cout << "开始创建" << endl;
    //动态申请size大小的指针数组
    TreeNode** nodes = new TreeNode * [size];
    //将int数据转换为TreeNode节点
    for (int i = 0; i < size; i++)
    {
        if (elements[i] == -1)
        {
            nodes[i] = nullptr;
        }
        else 
        {
            nodes[i] = new TreeNode(elements[i]);
            if (elements[i] == 3) forgeinnode = nodes[i];
        }
    }

    

    queue<TreeNode*> nodeQueue;
    nodeQueue.push(nodes[0]);

    TreeNode* node;
    int index = 1;
    while (index < size)
    {

        node = nodeQueue.front();
        nodeQueue.pop();
        TreeNode* lnode= nodes[index++];
        if (lnode != nullptr)
        {
            nodeQueue.push(lnode);
            node->left = lnode;
        }
        if (index == size) break;

        TreeNode* rnode = nodes[index++];
        if (rnode != nullptr)
        {
            nodeQueue.push(rnode);
            node->right = rnode;
        }
    }
    return nodes[0];
}

int main(){
    int elements[] = { 1,2,10,4,3,6,7,8};
    //cout << "节点的数量为" << sizeof(elements) / sizeof(int) << endl;
    TreeNode* node = initBTree(elements, sizeof(elements) / sizeof(int));
    return 0;
}
 
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

3）打印二叉树节点

void printTree(TreeNode* root)
{
    cout << "开始打印二叉树" << endl;
    if (root == nullptr)
    {
        cout << "二叉树为空" << endl;
        return;
    }
    queue<TreeNode*> que;
    que.push(root);
    int bottomLeft = 0;
    while (!que.empty()) {
        int size = que.size();
        bool flag = 0;
        for (int i = 0; i < size; ++i) {
            TreeNode* node = que.front();
            que.pop();
            cout << "节点" << node->val;
            if (node->left != nullptr) 
            {

                cout << "  左节点为  " << node->left->val;
                if (node->left != nullptr)
                    que.push(node->left);

            }
            else cout << "  左节点为  空";
            if (node->right != nullptr) {

                cout << "  右节点为  " << node->right->val << endl;
                if (node->right != nullptr)
                    que.push(node->right);
            }
            else cout << "  右节点为  空" << endl;

            cout << endl;
        }
    }

}
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

1、快速排序（递归方式）

1）思想：

**以升序为例，给了一个序列，选择一个关键字（通常是第一个）作为枢轴，将当前序列中比关键字小的移动到左边，比关键字大的移动到右边，这样分为了两个更小的子序列。

2）过程

3）实现的效果

4）总结

左右两个指针进行靠近
右指针负责找比基准小的元素，遇到停下，把这个值给左指针，然后让左指针移动
左指针负责找比基准大的元素，遇到停下，把这个值给右指针，然后下一次大while循环
当左右指针不能再靠近时，将此时的key赋给左右指针指向的元素
此时形成了左右指针的左边都比key小，右边都比key大

5）代码：

//快速排序
#include  
#include
using namespace std;
void QuickSort(int* array, int low, int high) {	//快排 
	if (low >= high) {	//若待排序序列只有一个元素，返回空 
		return;
	}
	int i = low;	//i作为指针从左向右扫描 
	int j = high;	//j作为指针从右向左扫描
	int key = array[low];//第一个数作为基准数 
	while (i < j) {
		
		//将j指针向左移动一直到一个元素小于基准值
		while (array[j] >= key && i < j) {	//从右边找小于基准数的元素 （此处由于j值可能会变，所以仍需判断i是否小于j） 
			j--;	//找不到则j减一 
		}
		array[i] = array[j];	//找到则赋值 
		//从左边找第一个大于基准值的值
		while (array[i] <= key && i < j) {	//从左边找大于基准数的元素 
			i++;	//找不到则i加一 
		}
		array[j] = array[i];	//找到则赋值 
	}
	array[i] = key;	//当i和j相遇，将基准元素赋值到指针i处 
	QuickSort(array, low, i - 1);	//i左边的序列继续递归调用快排 
	QuickSort(array, i + 1, high);	//i右边的序列继续递归调用快排 
}


int main() {
	int array[] = { 49,38,65,97,76,13,27,49 };
	int length = sizeof(array) / sizeof(*array);
	cout << "原始序列：";
	for (int i = 0; i < length; i++) {
		cout << array[i] << " ";
	}
	cout << endl;
	QuickSort(array, 0, length - 1);
	cout << "快排序列：";
	for (int i = 0; i < length; i++) {
		cout << array[i] << " ";
	}
	return 0;
}
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
45

6）备注：

下一个是另一种实现

2、快速排序2

1）思想：

设置两个指针
指针 p1 始终指向已经发现的最后一个小于中间值的数字位置，所以其初始值为 start - 1。
指针 p2 从位置 start 开始扫描数组寻找比中间值小的数字，若找到一个比中间值小的数字，则指针 p1 移向下一个位置，将当前 p1 和 p2 所指的数字进行交换，这样就可以实现将发现的比中间值小的数字排在了数组的左边，并且 p1 也指向已经发现的最后一个小于中间值的数字位置。遍历完所有数字后，最后将处于数组最后的中间值与 p1++ 所指的位置交换，并返回中间值的位置。这样就完成了一个 partition 函数，实现了将所有比中间值小的元素放在数组的左边，所以比中间值大的元素放在数组的右边。

2）过程

3）实现的效果

实现基准值左边都是小的，右边都是大的

4）总结

首先将基准值和最后元素做交换，然后下面是从前面到后面将所有小值放到前面的过程
两个指针，一个指针i遍历当前数组，一个指针small指明插得位置，刚开始
i指针往前跑，遇到比基准值小的将其和smll++互换位置，这样就将小的放到前面来了
i遍历到最后就将所有小值放到前面来了，然后再small++和最后的基准值做交换实现了基准值左边都是小值，右边都是大值

//快速排序
#include  
#include
using namespace std;

void printVector(vector<int>& nums) {
	auto begin = nums.begin();
	vector<int>::iterator end = nums.end();
	
	while (begin != end) {
		cout << *begin<<"  ";
		begin++;
	}
	cout << endl;
	cout << endl;
}
int partition(vector<int>& nums, int start, int end) {
	//int rad = rand() % (end - start + 1) + start;
	int rad = 1;
	printVector(nums);
	swap(nums[rad], nums[end]);//把基准值和最后的值交换
	cout << nums[end] << endl;
	int small = start - 1;
	for (int i = start; i < end; ++i) {
		if (nums[i] < nums[end]) {
			small++;
			swap(nums[small], nums[i]);
		}
		printVector(nums);
	}
	small++;
	swap(nums[small], nums[end]);
	printVector(nums);
	return small;//返回基准值在排序完成一次后下标
}
int main() {
	vector<int> v1 = { 49,38,65,97,76,13,27,49 };
	cout<<partition(v1, 0, v1.size()-1);
	return 0;
}
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