第六章
22.
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
| template <class T>
void chain<T>::split(chain<T> &a, chain<T> &b)
{
a.clear();
b.clear();
if (firstNode == nullptr)
{
return;
}
chainNode<T> *current = firstNode;
chainNode<T> *lastA = nullptr;
chainNode<T> *lastB = nullptr;
int index = 0;
while (current != nullptr)
{
chainNode<T> *nextNode = current->next;
current->next = nullptr;
if (index % 2 == 1)
{
if (a.firstNode == nullptr)
{
a.firstNode = current;
}
else
{
lastA->next = current;
}
lastA = current;
a.listSize++;
}
else
{
if (b.firstNode == nullptr)
{
b.firstNode = current;
}
else
{
lastB->next = current;
}
lastB = current;
b.listSize++;
}
current = nextNode;
index++;
}
firstNode = nullptr;
listSize = 0;
}
|
时间复杂度为 $\Theta(n)$
空间复杂度为 $\Theta(1)$
23.
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
| template <class T>
void extendedChain<T>::circularShift(int i)
{
if (this->listSize <= 1)
{
return;
}
int k = i % this->listSize;
if (k < 0)
{
k += this->listSize;
}
if (k == 0)
{
return;
}
this->lastNode->next = this->firstNode;
chainNode<T> *newLast = this->firstNode;
for (int step = 0; step < k - 1; ++step)
{
newLast = newLast->next;
}
this->firstNode = newLast->next;
newLast->next = nullptr;
this->lastNode = newLast;
}
|
30.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| template <class T>
void circularList<T>::reverse()
{
if (listSize <= 1)
return;
chainNode<T> *prev = firstNode;
chainNode<T> *curr = firstNode->next;
chainNode<T> *nextNode = nullptr;
while (curr != firstNode)
{
nextNode = curr->next;
curr->next = prev;
prev = curr;
curr = nextNode;
}
firstNode->next = prev;
firstNode = prev;
}
|
时间复杂度为 $\Theta(n)$
空间复杂度为 $\Theta(1)$
31.
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
| #include <stack>
template <class T>
void reverse(circularList<T> &theList)
{
int n = theList.size();
if (n <= 1)
return;
std::stack<T> s;
for (auto it = theList.begin(); it != theList.end(); ++it)
{
s.push(*it);
}
while (!theList.empty())
{
theList.erase(0);
}
int index = 0;
while (!s.empty())
{
theList.insert(index++, s.top());
s.pop();
}
}
|
时间复杂度为 $\Theta(n^2)$
空间复杂度为 $\Theta(n)$
32.
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
| template <class T>
void meld(const circularList<T> &a, const circularList<T> &b, circularList<T> &c)
{
c.clear();
auto itA = a.begin();
auto itB = b.begin();
while (itA != a.end() && itB != b.end())
{
c.push_back(*itA);
++itA;
c.push_back(*itB);
++itB;
}
while (itA != a.end())
{
c.push_back(*itA);
++itA;
}
while (itB != b.end())
{
c.push_back(*itB);
++itB;
}
}
|
时间复杂度为 $O(a.listSize + b.listSize)$
空间复杂度为 $O(a.listSize + b.listSize)$
39.
(15)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| template <class T>
void circularListWithHeader<T>::reverse()
{
if (listSize <= 1)
return;
chainNode<T> *prev = headerNode;
chainNode<T> *curr = headerNode->next;
chainNode<T> *nextNode = nullptr;
while (curr != headerNode)
{
nextNode = curr->next;
curr->next = prev;
prev = curr;
curr = nextNode;
}
headerNode->next = prev;
}
|
时间复杂度为 $\Theta(n)$
空间复杂度为 $\Theta(1)$
(16)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <vector>
template <class T>
void reverse(circularListWithHeader<T> &theList)
{
int n = theList.size();
if (n <= 1)
return;
std::vector<T> elements;
for (auto it = theList.begin(); it != theList.end(); ++it)
{
elements.push_back(*it);
}
theList.clear();
for (int i = n - 1; i >= 0; --i)
{
theList.push_back(elements[i]);
}
}
|
时间复杂度为 $\Theta(n)$
空间复杂度为 $\Theta(n)$
40.
(17)
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
| template <class T>
void meld(const circularListWithHeader<T> &a,
const circularListWithHeader<T> &b,
circularListWithHeader<T> &c)
{
c.clear();
auto itA = a.begin(), itB = b.begin();
while (itA != a.end() && itB != b.end())
{
c.push_back(*itA);
++itA;
c.push_back(*itB);
++itB;
}
while (itA != a.end())
{
c.push_back(*itA);
++itA;
}
while (itB != b.end())
{
c.push_back(*itB);
++itB;
}
}
|
时间复杂度为 $\Theta(m + n)$
空间复杂度为 $\Theta(m + n)$
(18)
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
| template <class T>
void circularListWithHeader<T>::meld(circularListWithHeader<T> &a,
circularListWithHeader<T> &b)
{
if (this == &a || this == &b)
return;
this->clear();
chainNode<T> *pa = a.headerNode->next;
chainNode<T> *pb = b.headerNode->next;
chainNode<T> *last = this->headerNode;
while (pa != a.headerNode && pb != b.headerNode)
{
last->next = pa;
last = pa;
pa = pa->next;
last->next = pb;
last = pb;
pb = pb->next;
}
while (pa != a.headerNode)
{
last->next = pa;
last = pa;
pa = pa->next;
}
while (pb != b.headerNode)
{
last->next = pb;
last = pb;
pb = pb->next;
}
last->next = this->headerNode;
this->listSize = a.listSize + b.listSize;
a.headerNode->next = a.headerNode;
a.listSize = 0;
b.headerNode->next = b.headerNode;
b.listSize = 0;
}
|
时间复杂度为 $\Theta(m + n)$
空间复杂度为 $\Theta(1)$
41.
(19)
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
| template <class T>
void merge(const circularListWithHeader<T> &a,
const circularListWithHeader<T> &b,
circularListWithHeader<T> &c)
{
c.clear();
auto itA = a.begin(), itB = b.begin();
while (itA != a.end() && itB != b.end())
{
if (*itA <= *itB)
{
c.push_back(*itA);
++itA;
}
else
{
c.push_back(*itB);
++itB;
}
}
while (itA != a.end())
{
c.push_back(*itA);
++itA;
}
while (itB != b.end())
{
c.push_back(*itB);
++itB;
}
}
|
时间复杂度为 $\Theta(m + n)$，空间复杂度为 $\Theta(m + n)$
(20)
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
| template <class T>
void circularListWithHeader<T>::merge(circularListWithHeader<T> &a,
circularListWithHeader<T> &b)
{
if (this == &a || this == &b)
return;
this->clear();
chainNode<T> *pa = a.headerNode->next;
chainNode<T> *pb = b.headerNode->next;
chainNode<T> *last = this->headerNode;
while (pa != a.headerNode && pb != b.headerNode)
{
if (pa->element <= pb->element)
{
last->next = pa;
last = pa;
pa = pa->next;
}
else
{
last->next = pb;
last = pb;
pb = pb->next;
}
}
while (pa != a.headerNode)
{
last->next = pa;
last = pa;
pa = pa->next;
}
while (pb != b.headerNode)
{
last->next = pb;
last = pb;
pb = pb->next;
}
last->next = this->headerNode;
this->listSize = a.listSize + b.listSize;
a.headerNode->next = a.headerNode;
a.listSize = 0;
b.headerNode->next = b.headerNode;
b.listSize = 0;
}
|
时间复杂度为 $\Theta(m + n)$
空间复杂度为 $\Theta(1)$
