A.1 (C++)

开始时间 2021-05-25 16:00:00
截止时间 2021-05-31 21:00:00

In this exercise, please change the linked-list we learned into a compressed linked-list.

compressed linked-list:
long prev_xor_next = long(prev_node) ^ long(next_node);
Node prev_node = (Node )(prev_xor_next ^ long(next_node));
Node next_node = (Node )(prev_xor_next ^ long(prev_node));

输入

8 9
80 30 23 95 30 3 98 59
37 13 94 57 99 4 11 28 15
3

输出

15
28
11
4
99
57
94
13
37
59
98
30
95
23
30
80

主程序 (不能修改)

#include <iostream>
using namespace std;

template <typename E>
class Node
{
    long prev_xor_next;
public:    
    E element;

    Node * prev_node(Node * next_node) {
        return (Node *)(prev_xor_next ^ (long)next_node);
    }
    Node * next_node(Node * prev_node) {
        return (Node *)(prev_xor_next ^ (long)prev_node);
    }
    void update_prev_and_next_node(Node * prev_node, Node * next_node) {
        prev_xor_next = long(prev_node) ^ long(next_node);
    }
    void update_prev_node(Node * old_prev_node, Node * prev_node) {
        Node * next_node = this->next_node(old_prev_node);
        update_prev_and_next_node(prev_node, next_node);
    }
    void update_next_node(Node * old_next_node, Node * next_node) {
        Node * prev_node = this->prev_node(old_next_node);
        update_prev_and_next_node(prev_node, next_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; }

#include "source.cpp"
};

int main() {
    int size1, size2;
    cin >> size1 >> size2;
    LinkedList<double> list1;
    I(i,size1) {
        int val;
        cin >> val;
        list1.addFirst(val);
    }
    I(i,size2) {
        int val;
        cin >> val;
        list1.addLast(val);
    }
    LinkedList<double> list2 = list1;
    int val;
    cin >> val;
    list2.removeFirstOccurrence(val);
    I(i,size2) {
        cout << list2.get(list2.size()-1) << endl;
        list2.removeLast(); 
    }
    I(i,size1-1) {
        cout << list2.get(0) << endl;
        list2.removeFirst(); 
    }
}

参考答案

void addFirst(const E & e){
    Node<E> * node=new Node<E>();//
    node->element=e;
    node->update_prev_and_next_node(0,head);
    if(head!=0){head->update_prev_node(0,node);}
    head=node;
    if(tail==0){tail=node;}
    ++_size;
}

void addLast(const E & e){
    Node<E> * node=new Node<E>();
    node->element=e;
    node->update_prev_and_next_node(tail,0);
    if(tail!=0){tail->update_next_node(0,node);}
    tail=node;
    if(head==0){head=node;}
    ++_size;
}

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

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

void removeFirst(){
    if(head == 0){
        throw NotSuchElementException();
    }
    Node<E> * temp=head;
    head = head->next_node(0);
    if(head != 0){
        head->update_prev_node(temp,0);
    }
    delete temp;
    _size--;
}

void removeLast(){
    if(tail == 0){
        throw NotSuchElementException();
    }
    Node<E> * temp=tail;
    tail = tail->prev_node(0);
    if(tail != 0){
        tail->update_next_node(temp,0);
    }
    delete temp;
    _size--;
}

void removeFirstOccurrence(const E & e){
    Node<E> * node=head;
    Node<E> * tmp = 0;
    I(i,_size){
        if(node->element==e){
            break;//找到 此刻tmp存储的是prev_node
        }
        Node<E> * p=node;
        node = node->next_node(tmp);
        tmp=p;
    }
    Node<E> * prev_node=tmp;
    Node<E> * next_node=node->next_node(tmp);
    if(prev_node!=0){
        prev_node->update_next_node(node,next_node);
    }
    if(next_node!=0){
        next_node->update_prev_node(node,prev_node);
    }
    if(prev_node==0){
        head=next_node;
    }
    if(next_node==0){
        tail=prev_node;
    }
    delete node;
    _size--;
}
//来自：https://cxsj.yizuodi.cn/60
//time: 6 ms
//memory: 2.356 MB

其他答案 Aholic的答案