数据结构王道习题
线性表：
删除最小值
从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。
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
| #include <iostream>
const int MaxSize = 100;
typedef int ElemType;
struct sqlist{
ElemType data[MaxSize];
int lenth;
};
sqlist initSqlist() {
sqlist L;
L.lenth = 0;
return L;
}
bool addElement(sqlist &L,ElemType e) {
if (L.lenth>=MaxSize) {
std::cout<<"list is full"<<std::endl;
return false;
}
L.data[L.lenth] = e;
L.lenth++;
return true;
}
bool DeletelowElement(sqlist &L,ElemType &e) {
if(L.lenth==0) {
std::cout << "list is empty";
}
int minIndex = 0;
for (int i=1;i<L.lenth;i++) {
if(L.data[i]<L.data[minIndex]) {
minIndex=i;
}
}
e = L.data[minIndex];
L.data[minIndex] = L.data[L.lenth-1];
L.lenth--;
return true;
}
int main() {
sqlist L =initSqlist();
addElement(L,10);
addElement(L,8);
addElement(L,15);
std::cout << L.data[0];
ElemType deleted;
DeletelowElement(L,deleted);
for(int i=0;i<L.lenth;i++) {
std::cout << L.data[i];
}
}
|
讲解：
- 设计一个高效算法，将顺序表工的所有元素递置， 要求算法的空间复杂度为O(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
36
37
38
39
40
41
42
43
44
45
| #include <iostream>
const int MaxSize = 100;
typedef int ElemType;
struct sqlist{
ElemType data[MaxSize];
int lenth;
};
void reverseList(sqlist &L) {
int start = 0;
int end = L.lenth - 1;
ElemType temp;
while (start < end) {
temp = L.data[start];
L.data[start] = L.data[end];
L.data[end] = temp;
start++;
end--;
}
}
int main() {
sqlist L = { {1, 2, 3, 4, 5}, 5 };
std::cout << "Original list:\n";
for (int i = 0; i < L.lenth; i++) {
std::cout << L.data[i] << " ";
}
std::cout << "\n";
reverseList(L);
std::cout << "Reversed list:\n";
for (int i = 0; i < L.lenth; i++) {
std::cout << L.data[i] << " ";
}
std::cout << "\n";
return 0;
}
|
- 对长度为 n的顺序表L，編写一个时间复杂度为 O(n)、空间复杂度为 O(1)的算法，该算法删除顺序表中所有值为x的数据元素。
思路：
首先时间复杂度为O(n)，也就意味着只能遍历一次线性表，空间复杂度为 O(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
36
37
38
39
40
41
42
43
44
| #include <iostream>
const int MaxSize = 100;
typedef int ElemType;
struct sqlist {
ElemType data[MaxSize];
int lenth;
};
void deleteAllX(sqlist &L, ElemType x) {
int k = 0;
for (int i = 0; i < L.lenth; i++) {
if (L.data[i] != x) {
L.data[k] = L.data[i];
k++;
}
}
L.lenth = k;
}
int main() {
sqlist L = { {1, 2, 3, 2, 4, 2, 5}, 7 };
std::cout << "Original list:\n";
for (int i = 0; i < L.lenth; i++) {
std::cout << L.data[i] << " ";
}
std::cout << "\n";
deleteAllX(L, 2);
std::cout << "List after removing all occurrences of 2:\n";
for (int i = 0; i < L.lenth; i++) {
std::cout << L.data[i] << " ";
}
std::cout << "\n";
return 0;
}
|
