数据结构作业20261003

发表于

第五章

5.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <class T>
void arrayList<T>::trimToSize()
{
    int targetLength = std::max(listSize, 1);
    if (arrayLength == targetLength)
    {
        return;
    }

    T *temp = new T[targetLength];
    for (int i = 0; i < listSize; ++i)
    {
        temp[i] = element[i];
    }
    delete[] element;
    element = temp;
    arrayLength = targetLength;
}

时间复杂度为 $O(listSize)$

11.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class T>
void arrayList<T>::push_back(const T &theElement)
{
    if (listSize == arrayLength)
    {
        int newLength = (arrayLength == 0) ? 1 : 2 * arrayLength;
        T *temp = new T[newLength];
        for (int i = 0; i < listSize; ++i)
        {
            temp[i] = element[i];
        }
        delete[] element;
        element = temp;
        arrayLength = newLength;
    }
    element[listSize++] = theElement;
}

最坏时间复杂度为 $O(listSize)$

均摊时间复杂度为 $O(1)$

12.

1
2
3
4
5
6
7
8
9
10
template <class T>
void arrayList<T>::pop_back()
{
    if (listSize == 0)
    {
        throw std::out_of_range("abab");
    }
    --listSize;
    element[listSize].~T();
}

时间复杂度为 $O(1)$

13.

1
2
3
4
5
6
7
8
9
#include <utility>

template <class T>
void arrayList<T>::swap(arrayList<T> &theList)
{
    std::swap(element, theList.element);
    std::swap(arrayLength, theList.arrayLength);
    std::swap(listSize, theList.listSize);
}

时间复杂度为 $O(1)$

29.

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
template <class T>
void arrayList<T>::merge(const arrayList<T> &a, const arrayList<T> &b)
{
    int newSize = a.listSize + b.listSize;
    int newCapacity = std::max(newSize, 1);
    T *newElement = new T[newCapacity];

    int i = 0, j = 0, k = 0;
    while (i < a.listSize && j < b.listSize)
    {
        if (a.element[i] <= b.element[j])
        {
            newElement[k++] = a.element[i++];
        }
        else
        {
            newElement[k++] = b.element[j++];
        }
    }

    while (i < a.listSize)
    {
        newElement[k++] = a.element[i++];
    }
    while (j < b.listSize)
    {
        newElement[k++] = b.element[j++];
    }

    delete[] element;
    element = newElement;
    listSize = newSize;
    arrayLength = newCapacity;
}

时间复杂度为 $O(a.listSize + b.listSize)$

30.

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
template <class T>
void arrayList<T>::split(arrayList<T> &a, arrayList<T> &b)
{
    int sizeA = (listSize + 1) / 2;
    int sizeB = listSize / 2;

    T *elemA = new T[std::max(sizeA, 1)];
    T *elemB = new T[std::max(sizeB, 1)];

    int idxA = 0, idxB = 0;
    for (int i = 0; i < listSize; ++i)
    {
        if (i % 2 == 0)
        {
            elemA[idxA++] = element[i];
        }
        else
        {
            elemB[idxB++] = element[i];
        }
    }

    delete[] a.element;
    a.element = elemA;
    a.listSize = sizeA;
    a.arrayLength = std::max(sizeA, 1);

    delete[] b.element;
    b.element = elemB;
    b.listSize = sizeB;
    b.arrayLength = std::max(sizeB, 1);
}

时间复杂度为 $O(listSize)$