数据结构

前言

没有前言

二叉树

  • 有n个结点的二叉树的分支数为n-1
  • 若二叉树的高度为h,则该二叉树最少有h个几点,最多有2^h -1 (等比数列求和S=a_1*(1-q^n)/(1-q) )
  • 含有n个结点的二叉树的高度最大是n,最小是ceil(log2(n+1))

满二叉树: 高度为h的二叉树具有最大数目(2^h-1)个结点
完全二叉树: 高度为h的二叉树,除了第h层外,其各层点数都达到最大,并且第h层是自左向右连续分布的。

  • 若i=0,则i无双亲。若i>0,则双亲为ceil(i/2)-1
  • 若2i+1<=n,则i的左孩子为2i+1,右孩子为2*i+2
  • 若i为偶数,且i>=1,则i是双亲的有孩子;奇数为左孩子。

先序遍历

根节点\左子树\右子树

中序遍历

左子树\根节点\右子树

后序遍历

左子树\右子树\根节点

层序遍历

按层遍历,先访问完一个节点再一次访问他的子节点,所以需要队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void leverOrder()
{
LinkQueque<int> q;
Node *p
if(root != NULL)
{
q.EnQueue(root);
}
while(!q.isempty())
{
q.DelQueue(p); //用P存储出队的
(*Visit)(p->data);
if(p->leftChild != NULL)
q.EnQueue(p->leftChild);
if(p->rightChild != NULL)
q.EnQueue(p->rightChild);
}
}

向下调整算法

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
void FilterDown(int start)//向下调整
{
//start的左右子树已经是最小堆了
int i=start,j;
j = 2*i+1;
int temp = heapArr[i];
while(j <= size -1 )
{
if(j < size-1 && heapArr[j] < heapArr[j+1])
j++;
if(temp > heapArr[j]){
heapArr[i] = heapArr[j];
i = j;
j = 2*j+1;
}
}
heapArr[i] = temp;
}
//找到完全二叉树结点编号最后的分支节点i,即,其左右孩子都是叶子。然后一层一层调整
void MinHeap(int a[], int maxSize, int n)
{
if(n<=0)
{
cout <<"error"<<endl;
exit(1);
}
int i = (n-2)/2 // 序列最右的分支结点
while(i>0)
{
FileDown(i);
i--;
}
}

向上调整算法

插入元素时,先插入到最后,然后自下而上调整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void FileUp(int End)
{
int j = End;
int i = (j-2)/2;
int temp = heapArr[j];

while(j>0)
{
if(heapArr[i] <=temp)
break;
else
{
heapArr[j] = heapArr[i];
j=i;
i=(j-2)/2;
}
}
heapArr[j]=temp;
}
  • 向上调整和向下调整的时间复杂度为O(log2n)

哈夫曼树

深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
void DFS()
{
int e;
g.setTag(v,VISITED);//g是图
g.getElem(v, e);
Visit(v);
for(int w = g.FirstAdjVex(v); w!=-1;w=getNext(v,w))
{
if(g.GetTag(w) == UNVISITED)
DFS(g,w,Visit)
}

}

广度优先搜索

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
void BFS()
{
queue<int> q;
int u,w;
int e;
g.setTag(v,VISITED);
g.getElem(v,e);
visit(e);
q.push(v);
while(!q.empty())
{
u = q.front();
q.pop();
for(w = g.FirstAdjVex(u);w!=-1;w=g.NextAdjVex(u,w))
{
if(g.GetTag(w) == UNVISITED)
{
G.setTag(w,VISITED);
g.GetElem(w,e);
Visit(e);
q.push(w);
}
}
}
}

最短路径

查找

二叉排序树

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
//查找
void Find(int &key, node *&f)
{
Node *p = root;
f = NULL;//用来保留双亲结点
while(p!=NULL && p->data!=key)
{
if(key < p->data)
{
f = p;
p = p->leftChild;
}
else
{
f = p;
p = p->rightChild;
}
}
return p;
}
//插入
void Insert(int &e)
{
Node *f;
if(fine(e, *f) == NULL)
{
Node *p;
p = (Node*)malloc(sizeof(Node*));
if(isempty())
{
root = p;
}
else if(e > f->data)
{
f->rightChild = p;
}
else
f->leftChile = p;
}
}
//删除
void delete(Node *&p)
{
Node* tmpptr, *tmpf;
if(p->leftChild == NULL && p->rightChild == NULL)
{
delete p;
p = NULL;
}
else if (p->leftChild == NULL)
{
tmpptr = p;
p = p->rightChild;
delete tmpptr;
}
else if(p->rightChild == NULL)
{
tmpptr = p;
p = p->leftChild;
delete tmpptr;
}
else
{
tmpF = p;
tmpptr = p->leftChild;
while(tmpptr->rightChild != NULL)
{
tmpF = tmpptr;
tmpptr = tmpptr->rightChild;
}
p->data = tmpptr->data
if(tmpF->rightChild == tmpptr)
delete(tmpF->rightChild)
else
delete(tmpF->leftChild)
}
}

排序

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
//冒泡排序
void bubblesort(int *a,int n)
{
int i,j;
for(i=1;i<n;i++)
{
int sort = 1;
for(j=0;j<n-i;j++)
{
if(a[j] < a[j+1])
{
int t=a[j];
a[j] = a[j+1];
a[j+1] = t;
sort = 0;
}
}
if(sort == 1)
break;
}
for(i=0;i<n;i++)
printf("%d,", a[i]);
}
//快速排序
void QuickSort(int *a,int low,int high)
{
int e = a[low];
int i = low;
int j = high;
while(i < j)
{
while(i < j && e < a[j])
j--;
if(i<j)
a[i++] = a[j];
while(i<j && e > a[i])
i++;
if(i<j)
a[j--] = a[i];
}
a[i] = e;
if(low < i-1)
QuickSort(a,low,i-1);
if(i+1 < high)
QuickSort(a,i+1,high);
}
//直接插入排序
void StraightInsertSort(int *a, int n)
{
int i,j;
for(i=1;i<n;i++)
{
int e = a[i];
for(j=i-1;j>=0 && a[j] > e;j--)
{
a[j+1] = a[j];
}
a[j+1]=e;
}
}
//希尔排序
void shellSort(int *a, int n)
{
int i,j,d = n/2;
while(d >0)
{
for(i=d;i<n;++i)
{
int e = a[i];
j = i-d;
while(j>=0 && e<a[j])
{
a[j+d] = a[j];
j -= d;
}
a[j+d] = e;
}
d /=2;
}
}
//简单选择排序
void SimpleSelect(int *a, int n)
{
int i,j;
for(i=0;i<n;++i)
{
int min = 10000;
int k = -1;
for(j=i;j<n;++j)
{
if(a[j] < min)
{
min = a[j];
k = j;
}
}
if(k != i)
{
int t = a[k];
a[k] = a[i];
a[i] =t;
}
}
}
//简单选择排序链表
void LinkSimpleSelect(Node *a)
{
int p,q,pp,pq,h;
h = p = a[0].next;
a[0].next = -1;
while(p!=-1)
{
q = pq = pp = p;
p = a[p].next;
while(p!=-1)
{
if(a[p].data >= a[q].data)
{
q = p;
pq = pp;
}
pp = p;
p = a[p].next;
}
if(h == q)
{
h = a[q].next;
a[q].next = a[0].next;
a[0].next = q;
}
else
{
a[pq].next = a[q].next;
a[q].next = a[0].next;
a[0].next = q;
}
p = h;
}
}

//堆,向下调整
void FilterDown(int *a,int low,int high)
{
int f = low;
int i = 2*low+1;
int e = a[low];
while(i <= high)
{
if(i+1 <=high && a[i+1] > a[i])
i++;
if(a[i] > e)
{
a[f] = a[i];
f = i;
i = 2*f+1;
}
else
break;
}
a[f] = e;
}
//堆排序
void HeapSort(int *a, int n)
{
int i;
for(i = (n-2)/2; i>=0;--i)
FilterDown(a,i,n-i);
int k;
for(i=n-1;i>0;--i)
{
int t = a[i];
a[i] = a[0];
a[0] = t;
FilterDown(a,0,i-1);
}

}

//归并
void Merge(int *a, int low,int mid,int high)
{
int* tmp = (int *)malloc(sizeof(int)*high);
int i = low, j = mid+1, k = low;
while(i <= mid && j <= high)
{
if(a[i] <= a[j])
{
tmp[k++] = a[i++];
}
else
tmp[k++] = a[j++];
}
while(j <= high)
tmp[k++] = a[j++];
while(i <= mid)
tmp[k++] = a[i++];
for(i=low;i<=high;i++)
{
a[i] = tmp[i];
}
}
//两路归并
void Mergersort(int *a,int n)
{
int len = 1;
while(len < n)
{
int i=0;
while(i+2*len <= n)
{
Merge(a,i,i+len-1,i+2*len-1);
i += 2*len;
}
if(i+len <n )
Merge(a,i,i+len-1,n-1);
len *=2;
}
}

内存中堆和栈的区别

    • 一般由程序员分配释放
    • 编译器自动分配,存放函数参数、局部变量等