第六版数据结构课本的部分练习解答，以及一些可能补充的内容，leetcode的在线习题收录至另外的post。
第一章
exp1-1
调用ctime的clock函数相关进行时间测算。
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
| #include <iostream>
#include <ctime>
using namespace std;
int add1(int n){
int result=0;
for(int i=1;i<n+1;i++){
result+=i;
}
return result;
}
int add2(int n){
int result=0;
result=n*(n+1)/2;
return result;
}
int main(){
int n;
cout<<"please input your num: \n";
cin>>n;
clock_t start1=clock();
cout<<add1(n)<<endl;
clock_t end1=clock();
clock_t start2=clock();
cout<<add2(n)<<endl;
clock_t end2=clock();
double duration1 = static_cast<double>(end1 - start1) / CLOCKS_PER_SEC;
double duration2 = static_cast<double>(end2 - start2) / CLOCKS_PER_SEC;
cout<<"time1:"<<duration1<<endl<<"time2: "<<duration2<<endl;
}
|
测算结果
1
2
3
4
5
6
| please input your num:
200
20100
20100
time1: 2.3e-05
time2: 2e-06
|
可见add1的数量级更大
exp1-2
因为懒得写所以用template模板了一下（（
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 <iostream>
#include <cmath>
#include <iomanip>
#include <ctime>
using namespace std;
long long fact(int n) {
long long result = 1;
for (int i = 2; i <= n; ++i) result *= i;
return result;
}
template<typename Func>
void measure_time(const char* name, Func func) {
clock_t start = clock();
auto result = func();
clock_t end = clock();
double duration = static_cast<double>(end - start) / CLOCKS_PER_SEC;
cout << setw(10) << name << " = " << setw(12) << result
<< " time: " << duration << " s" << endl;
}
int main() {
int n;
cout << "Please input your num: ";
cin >> n;
measure_time("log2(n)", [&]() { return log2(n); });
measure_time("sqrt(n)", [&]() { return sqrt(n); });
measure_time("n", [&]() { return n; });
measure_time("n*log2(n)", [&]() { return n * log2(n); });
measure_time("n*n", [&]() { return n * n; });
measure_time("n*n*n", [&]() { return n * n * n; });
measure_time("pow(2,n)", [&]() { return pow(2, n); });
measure_time("fact(n)", [&]() { return fact(n); });
return 0;
}
|
运行结果：
1
2
3
4
5
6
7
8
9
10
| Please input your num: 20
log2(n) = 4.32193 time: 2.5e-05 s
sqrt(n) = 4.47214 time: 1e-05 s
n = 20 time: 1e-06 s
n*log2(n) = 86.4386 time: 2e-06 s
n*n = 400 time: 0 s
n*n*n = 8000 time: 1e-06 s
pow(2,n) = 1.04858e+06 time: 9e-06 s
fact(n) = 2432902008176640000 time: 1e-06 s
|
lambda表达式是现代C++中的一种语法糖，用于在调用或作为函数参数传递的位置定义匿名函数对象。它在C++11、C++14、C++17和C++20中不断更新和改进。拉姆达表达式通常用于封装传递给算法或异步方法的几行代码。
1
2
| [capture list] (parameter list) -> return type { function body }
[&]() { return log2(n); }
|
exp1-3
素数筛查比较不同算法的速率，func1用了暴力筛查，func2是埃氏筛
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
| #include <iostream>
#include <ctime>
#include <cmath>
#include <vector>
using namespace std;
bool isPrime(int x) {
if (x < 2) return false;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) return false;
}
return true;
}
void func1(int n){
clock_t start=clock();
int cnt=0;
for(int i=0;i<n;i++){
if(isPrime(i)) cnt++;
}
clock_t end=clock();
double duration = static_cast<double>(end - start) / CLOCKS_PER_SEC;
cout<<cnt<<"个"<<" "<<"time: "<<duration<<endl;
}
void func2(int n) {
clock_t start=clock();
if (n < 2) return ;
vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; ++i) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
int cnt = 0;
for (int i = 2; i <= n; ++i) {
if (isPrime[i]) cnt++;
}
clock_t end=clock();
double duration = static_cast<double>(end - start) / CLOCKS_PER_SEC;
cout<<cnt<<"个"<<" "<<"time: "<<duration<<endl;
}
int main(){
int n;
cout << "Please input your num: ";
cin >> n;
func1(n);
func2(n);
}
|
结果：
1
2
3
| Please input your num: 100
25个 time: 7e-06
25个 time: 2.9e-05
|
从理论上来说的话好像是埃氏筛时间复杂度更低来着……可能是因为函数范围的问题吧。。。
exp1-4
计算阶乘求和，要求时间复杂度为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
| #include <iostream>
using namespace std;
long long sum(int n){
int sum=0;
int fact=1;
for(int i=1;i<n+1;i++){
fact*=i;
sum+=fact;
}
return sum;
}
int main(){
cout<<"please input your num: ";
int n;
cin>>n;
cout<<sum(n)<<endl;
}
|
结果：
1
2
| please input your num: 10
4037913
|
本来写了个独立函数递归计算各级阶乘的，但是被sum又调用了所以改之。
第二章
感觉边抄边改了很多板子（
sqlist&&exp2-1
数据类型为char的sqlist,顺序数组存放。函数挺多的，对比书上的函数稍微优化了一点吧（
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
| #include <iostream>
using namespace std;
struct sqlist
{
char data[50];
int length;
};
void CreatList(sqlist *&l, char a[], int n) {
l = new sqlist;
int i = 0;
while (i < n) {
l->data[i] = a[i];
i++;
}
l->length = n;
}
void InitList(sqlist*&l){
l= new sqlist;
l->length=0;
}
void DestroyList(sqlist*&l){
delete l;
}
bool Empty(sqlist *l){
return(l->length==0);
}
int ListLength(sqlist*l){
return l->length;
}
void DispList(sqlist*l){
for(int i=0;i<l->length;i++)
cout<<l->data[i]<<" ";
cout<<endl;
}
bool GetElem(sqlist*l,int i,char &e){
if(i<1||i>l->length) return false;
e=l->data[i-1];
return true;
}
int LocateElem(sqlist *l, char e) {
int i = 0;
while (i < l->length && l->data[i] != e)
i++;
if (i == l->length) return 0;
else return i + 1;
}
bool ListInsert(sqlist *&l, int i, char e) {
if (i < 1 || i > l->length + 1 || l->length == 50)
return false;
i--;
for (int j = l->length; j > i; j--)
l->data[j] = l->data[j - 1];
l->data[i] = e;
l->length++;
return true;
}
bool Delete(sqlist *&l, int i, char &e) {
if (i < 1 || i > l->length)
return false;
i--;
e = l->data[i];
for (int j = i; j < l->length - 1; j++)
l->data[j] = l->data[j + 1];
l->length--;
return true;
}
|
测试ing
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
| int main() {
sqlist *l;
InitList(l);
ListInsert(l, 1, 'a');
ListInsert(l, 2, 'b');
ListInsert(l, 3, 'c');
ListInsert(l, 4, 'd');
ListInsert(l, 5, 'e');
DispList(l);
cout << "length of l is:" << ListLength(l) << endl;
cout <<"if empty: "<< Empty(l) << endl;
char a;
GetElem(l,3,a);
cout <<"the third is: "<<a<<endl;
cout <<"the location of a is: "<<LocateElem(l,'a')<<endl;
ListInsert(l,4,'f');
DispList(l);
char b;
Delete(l,3,b);
cout<<"the deleted elem is:"<<b<<endl;
DispList(l);
DestroyList(l);
return 0;
}
|
结果
1
2
3
4
5
6
7
8
| a b c d e
length of l is:5
if empty: 0
the third is: c
the location of a is: 1
a b c f d e
the deleted elem is:c
a b f d e
|
linklist&&exp2-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
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
| #include <iostream>
using namespace std;
struct linklist
{
char data;
linklist* next;
};
void InitList(linklist*&l){
l= new linklist;
l->next=nullptr;
}
void DestroyList(linklist*&l){
linklist *pre =l,*p=l->next;
while(p!=nullptr){
delete pre;
pre=p;
p=p->next;
}
delete pre;
}
bool Empty(linklist *l){
return (l->next==nullptr);
}
int ListLength(linklist *l){
int n=0;
linklist *p=l;
while(p->next!=nullptr){
n++;
p=p->next;
}
return n;
}
void DispList(linklist *l) {
linklist *p = l->next;
while (p != nullptr) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
bool GetElem(linklist*l,int i,char &e){
int j=0;
linklist *p=l;
if(i<=0) return false;
while(j<i&&p!=nullptr){
j++;
p=p->next;
}
if(p==nullptr){
return false;
}else{
e=p->data;
return true;
}
}
int LocateElem(linklist *l, char e) {
int i=1;
linklist *p=l->next;
while(p!=nullptr&&p->data!=e){
p=p->next;
i++;
}
if(p==nullptr) return 0;
else return i;
}
bool ListInsert(linklist *&l, int i, char e) {
int j=0;
linklist *p=l,*s;
if(i<=0) return false;
while(j<i-1&&p!=nullptr){
j++;
p=p->next;
}
if(p==nullptr) return false;
else{
s=new linklist;
s->data=e;
s->next=p->next;
p->next=s;
return true;
}
}
bool Delete(linklist *&l, int i, char &e) {
if (i <= 0) return false;
linklist *p = l;
int j = 0;
while (j < i - 1 && p != nullptr) {
j++;
p = p->next;
}
if (p == nullptr || p->next == nullptr) return false;
linklist *q = p->next;
e = q->data;
p->next = q->next;
delete q;
return true;
}
|
主函数同上即可（