数据结构与算法

stach

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
class Teacher {
private:
int age;
char* name;
public:

Teacher() {
age = 18;
name = new char[10];
strcpy(name, "default");
}
Teacher(int _age, char* _name) {
age = _age;
name = new char[strlen(_name) + 1];
strcpy(name, _name);
}
Teacher(Teacher& obj) {
age = obj.age;
name = new char[strlen(obj.name) + 1];
strcpy(name, obj.name);
}
~Teacher() {
age = 0;
if (name != NULL) {
delete [] name;
name = NULL;
}
}
Teacher& operator=(Teacher& obj) {
age = obj.age;
if (name != NULL) {
delete [] name;
name = NULL;
}

name = new char[strlen(obj.name) + 1];
strcpy(name, obj.name);

return *this;
}

char* getName() {
return name;
}
int getAge() {
return age;
}
};

template <typename T>
struct MyLink {
T* data;
MyLink<T>* prev;
};

template <typename T>
class MyStack {
private:
int _size = 0;
MyLink<T>* head;
public:
MyStack() {
head = new MyLink<T>;
head->data = NULL;
head->prev = NULL;
}
~MyStack() {
clear();
if (head != NULL) {
if (head->data != NULL) {
delete head->data;
head->data = NULL;
}

if (head->prev != NULL) {
delete head->prev;
head->prev = NULL;
}
}
}

int push(T* objP) {
MyLink<T>* p = new MyLink<T>;
p->data = objP;
p->prev = head;
head = p;
_size++;

return _size;
}

T* pop() {
if (_size == 0) {
return NULL;
}

MyLink<T>* curr = head;
head = head->prev;
_size--;
return curr->data;
}

int size() {
return _size;
}

void clear() {
if (_size == 0) {
return;
}

while (_size > 0) {
pop();
}
}
};
int main(int argc, const char * argv[]) {
Teacher t1(1, "t1"), t2(2, "t2"), t3(3, "t3");
MyStack<Teacher> s = MyStack<Teacher>();
s.push(&t1);
s.push(&t2);
s.push(&t3);

while (s.size()) {
Teacher* tmp = s.pop();
cout << "name: " << tmp->getName() << " age: " << tmp->getAge() << endl;
}
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdio.h>

typedef struct {
int data;
struct BiTNode* lChild, *rChild;
}BiTNode, *BiTree;

void printData(int num) {
printf(" %d ", num);
}

void inOrder(BiTNode* T) {
if (T == NULL) {
return;
}
inOrder(T->lChild);
printData(T->data);
inOrder(T->rChild);
}

BiTNode* copyTree(BiTNode* T) {
if (T == NULL) {
return NULL;
}
BiTNode* newNode = NULL;
BiTNode* newLChild = NULL;
BiTNode* newRChild = NULL;

if (T->lChild != NULL) {
newLChild = copyTree(T->lChild);
}

if (T->rChild != NULL) {
newRChild = copyTree(T->rChild);
}

newNode = (BiTNode*)malloc(sizeof(BiTNode));
memset(newNode, 0, sizeof(BiTNode));
if (newNode == NULL) {
return NULL;
}
newNode->data = T->data;
newNode->lChild = newLChild;
newNode->rChild = newRChild;


return newNode;
}

int main(int argc, const char * argv[]) {

BiTNode t1, t2, t3, t4, t5;
memset(&t1, 0, sizeof(BiTNode));
memset(&t2, 0, sizeof(BiTNode));
memset(&t3, 0, sizeof(BiTNode));
memset(&t4, 0, sizeof(BiTNode));
memset(&t5, 0, sizeof(BiTNode));
t1.data = 1;
t1.lChild = &t2;
t1.rChild = &t3;
t2.data = 2;
t2.lChild = &t4;
t3.data = 3;
t3.rChild = &t5;
t4.data = 4;
t5.data = 5;

printf("\nold tree: \n");
inOrder(&t1);

printf("\nnew tree: \n");
BiTNode* newT = NULL;
newT = copyTree(&t1);
inOrder(newT);

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <stack>
struct BiTNode{
int data;
struct BiTNode* lChild, *rChild;
};

void printData(int num) {
printf(" %d ", num);
}

void inOrder(BiTNode* T) {
if (T == NULL) {
return;
}
inOrder(T->lChild);
printData(T->data);
inOrder(T->rChild);
}


BiTNode* goLeft(BiTNode* T,stack<BiTNode*> &s) {
if (T == NULL) {
return NULL;
}

//判断是否有左节点, 如果有就入栈, 否则就返回当前节点
while (T->lChild != NULL) {
s.push(T);
T = T->lChild;
}
return T;
}

void inOrder2(BiTNode* T) {
if (T == NULL) {
return;
}

stack<BiTNode*> s;

//步骤1
T = goLeft(T, s);

while (T) {
printData(T->data);
if (T->rChild) {
//如果有右子树 就重复步骤1
T = goLeft(T->rChild, s);
} else if (!s.empty()) {
//如果没右子树并且栈顶不为空, 则取出栈顶, 回退到栈顶元素
T = s.top();
s.pop();
} else {
T = NULL;
}
}
}


int main(int argc, const char * argv[]) {

BiTNode t1, t2, t3, t4, t5;
memset(&t1, 0, sizeof(BiTNode));
memset(&t2, 0, sizeof(BiTNode));
memset(&t3, 0, sizeof(BiTNode));
memset(&t4, 0, sizeof(BiTNode));
memset(&t5, 0, sizeof(BiTNode));
t1.data = 1;
t1.lChild = &t2;
t1.rChild = &t3;
t2.data = 2;
t2.lChild = &t4;
t3.data = 3;
t3.rChild = &t5;
t4.data = 4;
t5.data = 5;

printf("\n递归方法: \n");
inOrder(&t1);

printf("\n非递归方法: \n");
inOrder2(&t1);

return 0;
}

Morris方法遍历二叉树

  1. 如果当前节点的左孩子为空,则输出当前节点并将其右孩子作为当前节点。

  2. 如果当前节点的左孩子不为空,在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。

    a) 如果前驱节点的右孩子为空,将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。

    b) 如果前驱节点的右孩子为当前节点,将它的右孩子重新设为空(恢复树的形状)。输出当前节点。当前节点更新为当前节点的右孩子。

  3. 重复以上1、2直到当前节点为空。

步骤

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 inorderMorrisTraversal(BiTNode *root) {
BiTNode* curr = NULL, *prev = NULL;

while (curr != NULL) {
if (curr->lChild == NULL) {
//1. 如果当前节点的左孩子为空,则输出当前节点并将其右孩子作为当前节点。
printData(curr->data);
curr = curr->rChild;
} else {
prev = curr->lChild;
while (prev->rChild != NULL && prev->rChild != curr) {
prev = curr->rChild;
}

if (prev->rChild == NULL) {
//a) 如果前驱节点的右孩子为空,将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。
prev->rChild = curr;
curr = curr->lChild;
} else {
//b) 如果前驱节点的右孩子为当前节点,将它的右孩子重新设为空(恢复树的形状)。输出当前节点。当前节点更新为当前节点的右孩子。
printData(curr->data);
curr = curr->rChild;
prev->rChild = NULL;
}
}
}

}

参考

插入排序

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
void printArr(int* arr, int len) {
printf("开始打印: ");
for (int i = 0; i < len; i ++) {
printf(" %d ", arr[i]);
}
}
void selectSort(int *arr, int len) {

for (int i = 1; i < len; i++) {
int tmp = arr[i];
int k = i;

for (int j = i - 1; (j >= 0) && (arr[j] > tmp); j--) {
arr[j + 1] = arr[j];
k = j;
}

arr[k] = tmp;
}
}

int main(int argc, const char * argv[]) {
int arr[] = {2,1,32,12,42,5};
int len = sizeof(arr) / sizeof(int);
selectSort(arr, len);
printArr(arr, len);

return 0;
}

希尔排序

与插入排序类似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void shellSort(int *arr, int len) {
int i = 0, j = 0, k = -1, temp = -1, gap = len;
do {
gap = gap / 3 + 1; //业界统一实验的结果

for (i = gap; i < len; i += gap) {
k = i;
temp = arr[k];

for (j = i - gap; (j >= 0) && (arr[j] > temp); j -= gap) {
arr[j + gap] = arr[j];
k = j;
}
arr[k] = temp;
}
} while (gap > 1);
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void bubbleSort(int *arr, int len) {
int flag = 1; //0表示没有发生交换, 1表示发生交换

for (int i = 0; (i < len) && flag; i++) {
flag = 0;
for (int j = len - 1; j > i; j--) {
if (arr[j - 1] > arr[j]) {
int tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
flag = 1;//发生了交换
}
}
}
}

快速排序

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
void swap(int *arr, int low, int high) {
int temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}

int partition(int *arr, int low, int high) {
//找出基准值
int pv = arr[low];
while (low < high) {
//找出比基准值小的数 并交换
while ((low < high) && arr[high] >= pv) {
high--;
}
swap(arr, low, high);
//找出比基准值大的数 并交换
while ((low < high) && arr[low] <= pv) {
low++;
}
swap(arr, low, high);
}

return low;
}

void quickSort(int *arr, int low, int high) {
if (low < high) {
//分区
int mid = partition(arr, low, high);
//分治左边
quickSort(arr, low, mid - 1);
//分治右边
quickSort(arr, mid + 1, high);
}
}