A.2 (C++)

开始时间 2021-05-28 10:00:00
截止时间 2021-05-28 11:40:00

In this exercise, please add a member function, removeAll, into the linked-list class.

输入

9
77 57 70 21 31 95 14 77 95
77

输出

57
70
21
31
95
14
95

主程序 (不能修改)

#include <iostream>
using namespace std;

template <typename E>
struct Node
{
    E element;
    Node * next_node;
    Node * prev_node;
};

#define I(i,n) for (int i = 0; i < n; ++ i)

class NotSuchElementException {};

template <typename E>
class LinkedList
{
    int _size;
    Node<E> * head;
    Node<E> * tail;

public:
    LinkedList() : _size(0), head(0), tail(0) {}

    int size() const { return _size; }

private:
    Node<E> * get_node(int index) const {
        if (index < 0 || index >= _size) 
            throw NotSuchElementException();
        if (index < _size / 2) {
            Node<E> * node = head;
            I(i, index) node = node->next_node;
            return node;
        }
        else {
            Node<E> * node = tail;
            I(i, (_size-1-index)) node = node->prev_node;
            return node;
        }
    }

public:
    E & get(int index) const {
        Node<E> * node = get_node(index);
        return node->element;
    }
    void set(int index, const E & e) {
        Node<E> * node = get_node(index);
        node->element = e;
    }

    E & getFirst() const {
        return get(0);
    }

    E & getLast() const {
        return get(_size - 1);
    }

    void remove (int index) {
        Node<E> * node = get_node(index);
        Node<E> * prev_node = node->prev_node;
        Node<E> * next_node = node->next_node;
        if (prev_node != 0) prev_node->next_node = next_node;
        if (next_node != 0) next_node->prev_node = prev_node;
        if (prev_node == 0) head = next_node;
        if (next_node == 0) tail = prev_node;
        delete node;
        -- _size;
    }

    void removeFirst () {
        remove(0);
    }

    void removeLast () {
        remove(_size-1);
    }

    void add(int index, const E & e) {
        if (index < 0 || index > _size) 
            throw NotSuchElementException();
        Node<E> * node = new Node<E>();
        node->element = e;
        Node<E> * next_node = (index == _size ? 0 : get_node(index));
        Node<E> * prev_node = (next_node == 0 ? tail : next_node->prev_node);
        node->next_node = next_node;
        node->prev_node = prev_node;
        if (prev_node != 0) prev_node->next_node = node;
        if (next_node != 0) next_node->prev_node = node;
        if (prev_node == 0) head = node;
        if (next_node == 0) tail = node;
        ++ _size;
    }

    void addFirst (const E & e) {
        add(0, e);
    }

    void addLast (const E & e) {
        add(_size, e);
    }

public:
    void clear() {
        while (_size > 0) removeFirst();
    }

    void addAll(const LinkedList & list, int index=-1) {
        if (index == -1) index = _size;
        Node<E> * node = list.head;
        I(i, list._size) {
            add(index, node->element);
            node = node->next_node;
            ++ index;
        }
    }

    LinkedList(const LinkedList & list) : _size(0), head(0), tail(0) {
        addAll(list);
    }

    LinkedList & operator = (const LinkedList & list) {
        clear();
        addAll(list);
    }

    ~LinkedList() {
        clear();
    }

    int indexOf(const E & e) const {
        Node<E> * node = head;
        I(i, _size) {
            if (node->element == e) return i;
            node = node->next_node;
        }
        return -1;
    }

    int lastIndexOf(const E & e) const {
        Node<E> * node = tail;
        I(i, _size) {
            if (node->element == e) return i;
            node = node->prev_node;
        }
        return -1;
    }

    bool contains(const E & e) const {
        return indexOf(e) >= 0;
    }

    void removeFirstOccurrence(const E & e) {
        int index = indexOf(e);
        if (index == -1)
            throw NotSuchElementException();
        remove(index);
    }

    void removeLastOccurrence(const E & e) {
        int index = lastIndexOf(e);
        if (index == -1)
            throw NotSuchElementException();
        remove(index);
    }

    void removeAll(const E & e); // TODO
};

#include "source.cpp"

int main() {
    int size;
    cin >> size;
    LinkedList<double> list;
    I(i, size) {
        int val;
        cin >> val;
        list.addLast(val);
    }
    int val;
    cin >> val;
    list.removeAll(val);
    I(i, list.size())
        cout << list.get(i) << endl;

}

参考答案

template <typename E>
void LinkedList<E>::removeAll(const E & e){
    while(1){
    int index = indexOf(e);
    if (index == -1){break;}
    remove(index);
    }
}
//来自：https://cxsj.yizuodi.cn/61
//time: 6 ms
//memory: 2.144 MB