C++ 创建有序链表

Question

因此，我正在尝试创建一个有序链表以将它们存储在一个数组中，以便能够组织一个图书和作者库。但是，我发现创建有序链表非常困难。我设法找到了在线创建链表的代码，但是，我不知道如何开始制作有序链表。我对这种语言比较陌生，发现创建这种语言压力很大。

关于如何使用下面的链表结构创建它有什么建议吗？

我是 C++ 的新手，这是我第一次使用的数据结构之一，对于这个相当模糊的问题，我深表歉意。

如果我要将其表述为一个固化的问题，那就是:我如何使用此代码作为一般基础来创建有序链表？

 #ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <stdexcept>
using namespace std;

template<typename T>
class Node
{
public:
    T element;  // Element contained in the node
    Node<T>* next; // Pointer to the next node

    Node() // No-arg constructor
    {
        next = nullptr;
    }

    Node(T element) // Constructor
    {
        this->element = element;
        next = nullptr;
    }
};

template<typename T>
class Iterator : public std::iterator<std::forward_iterator_tag, T>
{
public:
    Iterator(Node<T>* p)
    {
        current = p;
    }

    Iterator operator++() // Prefix ++
    {
        current = current->next;
        return *this;
    }

    Iterator operator++(int dummy) // Postfix ++
    {
        Iterator temp(current);
        current = current->next;
        return temp;
    }

    T& operator*()
    {
        return current->element;
    }

    bool operator==(const Iterator<T>& iterator)
    {
        return current == iterator.current;
    }

    bool operator!=(const Iterator<T>& iterator)
    {
        return current != iterator.current;
    }

private:
    Node<T>* current;
};

template<typename T>

class LinkedList
{
public:
    LinkedList();
    LinkedList(const LinkedList<T>& list);
    virtual ~LinkedList();
    void addFirst(T element);
    void addLast(T element);
    T getFirst() const;
    T getLast() const;
    T removeFirst() throw (runtime_error);
    T removeLast();
    void add(T element);
    void add(int index, T element);
    void clear();
    bool contains(T element) const;
    T get(int index) const;
    int indexOf(T element) const;
    bool isEmpty() const;
    int lastIndexOf(T element) const;
    void remove(T element);
    int getSize() const;
    T removeAt(int index);
    T set(int index, T element);

    Iterator<T> begin() const
    {
        return Iterator<T>(head);
    }

    Iterator<T> end() const
    {
        return Iterator<T>(tail->next);
    }

private:
    Node<T>* head;
    Node<T>* tail;
    int size;
};

template<typename T>
LinkedList<T>::LinkedList()
{
    head = tail = nullptr;
    size = 0;
}

template<typename T>
LinkedList<T>::LinkedList(const LinkedList<T>& list)
{
    head = tail = nullptr;
    size = 0;

    Node<T>* current = list.head;
    while (current != nullptr)
    {
        this->add(current->element);
        current = current->next;
    }
}

template<typename T>
LinkedList<T>::~LinkedList()
{
    clear();
}

template<typename T>
void LinkedList<T>::addFirst(T element)
{
    Node<T>* newNode = new Node<T>(element);
    newNode->next = head;
    head = newNode;
    size++;

    if (tail == nullptr)
        tail = head;
}

template<typename T>
void LinkedList<T>::addLast(T element)
{
    if (tail == nullptr)
    {
        head = tail = new Node<T>(element);
    }
    else
    {
        tail->next = new Node<T>(element);
        tail = tail->next;
    }

    size++;
}

template<typename T>
T LinkedList<T>::getFirst() const
{
    if (size == 0)
        throw runtime_error("Index out of range");
    else
        return head->element;
}

template<typename T>
T LinkedList<T>::getLast() const
{
    if (size == 0)
        throw runtime_error("Index out of range");
    else
        return tail->element;
}

template<typename T>
T LinkedList<T>::removeFirst() throw (runtime_error)
{
    if (size == 0)
        throw runtime_error("No elements in the list");
    else
    {
        Node<T>* temp = head;
        head = head->next;
        if (head == nullptr) tail = nullptr;
        size--;
        T element = temp->element;
        delete temp;
        return element;
    }
}

template<typename T>
T LinkedList<T>::removeLast()
{
    if (size == 0)
        throw runtime_error("No elements in the list");
    else if (size == 1)
    {
        Node<T>* temp = head;
        head = tail = nullptr;
        size = 0;
        T element = temp->element;
        delete temp;
        return element;
    }
    else
    {
        Node<T>* current = head;

        for (int i = 0; i < size - 2; i++)
            current = current->next;

        Node<T>* temp = tail;
        tail = current;
        tail->next = nullptr;
        size--;
        T element = temp->element;
        delete temp;
        return element;
    }
}

template<typename T>
void LinkedList<T>::add(T element)
{
    addLast(element);
}

template<typename T>
void LinkedList<T>::add(int index, T element)
{
    if (index == 0)
        addFirst(element);
    else if (index >= size)
        addLast(element);
    else
    {
        Node<T>* current = head;
        for (int i = 1; i < index; i++)
            current = current->next;
        Node<T>* temp = current->next;
        current->next = new Node<T>(element);
        (current->next)->next = temp;
        size++;
    }
}

template<typename T>
void LinkedList<T>::clear()
{
    while (head != nullptr)
    {
        Node<T>* temp = head;
        head = head->next;
        delete temp;
    }

    tail = nullptr;
    size = 0;
}

template<typename T>
T LinkedList<T>::get(int index) const
{
    if (index < 0 || index > size - 1)
        throw runtime_error("Index out of range");

    Node<T>* current = head;
    for (int i = 0; i < index; i++)
        current = current->next;

    return current->element;
}

template<typename T>
int LinkedList<T>::indexOf(T element) const
{
    // Implement it in this exercise
    Node<T>* current = head;
    for (int i = 0; i < size; i++)
    {
        if (current->element == element)
            return i;
        current = current->next;
    }

    return -1;
}

template<typename T>
bool LinkedList<T>::isEmpty() const
{
    return head == nullptr;
}

template<typename T>
int LinkedList<T>::getSize() const
{
    return size;
}

template<typename T>
T LinkedList<T>::removeAt(int index)
{
    if (index < 0 || index >= size)
        throw runtime_error("Index out of range");
    else if (index == 0)
        return removeFirst();
    else if (index == size - 1)
        return removeLast();
    else
    {
        Node<T>* previous = head;

        for (int i = 1; i < index; i++)
        {
            previous = previous->next;
        }

        Node<T>* current = previous->next;
        previous->next = current->next;
        size--;
        T element = current->element;
        delete current;
        return element;
    }
}

// The functions remove(T element), lastIndexOf(T element),
// contains(T element), and set(int index, T element) are
// left as an exercise

#endif

Answer 1

如果它是您想要的列表，只需使用标准列表即可。像这样插入元素:

#include <iostream>
#include <algorithm>
#include <list>

int main() {
    const int ints[]{ 3,5,1,7,3,9,-1,0,1 };
    std::list<int> sorted;
    for (auto i : ints) {
        // Here's how to insert
        sorted.insert(std::lower_bound(sorted.begin(), sorted.end(), i),i);
    }
    for (auto v : sorted) {
        std::cout << v << '\n';
    }
    return 0;
}

还有其他容器可能更适合您的目的，例如 std::deque 或“heapified”std::vector。研究标准库容器和算法。