Description

In this quiz, you are asked to use linked list to simulate typing a string. You need to implement four operations, i.e., type, move, backspace and print.
Hint: it is easier to use a double linked list to do so.
Notice: <string> is allowed, but other STL are not allowed.
 

There are four operations to be implemented.

1. Type abcd: a string, e.g., abcd, follows the operation Type. You need to add each character as a new node after the cursor (游標). Each time a new node is added, the cursor moves to the end of the new added node.
   For example, assume we have a linked list “abc|” and “|” is the cursor. After the operation Type defg, the linked list becomes “abcdefg|”.
   (Note that the string consists only [0-9A-Za-z], and you don’t have to output the cursor)
    
2. Move N: N is an integer. If N>0, the cursor moves rightward N characters. If N<=0, the cursor moves leftward N characters. If the cursor moves to the very front/end of the linked list, then stop.
   For example, assume we have a linked list “abc|” and “|” is the cursor. After the operation “Move -4”, the linked list becomes “|abc”.
   ( Note that -1000000<N<1000000. )
    
3. Backspace: Delete the character in front of the cursor. If there is no character in front of the cursor, then do nothing.
   For example, assume we have this linked list “abc|” and “|” is the cursor. After the operation “Backspace”, the linked list becomes “ab|”.
    
4. Print: Output all the characters stored in the linked list and shift to new line.

 

////////you can use the below code/////////

#include <iostream>
#include <string>
using namespace std;

class LinkedList;

class ListNode{
public:
    ListNode():data(' '), next(0), pre(0){};
    ListNode(char c):data(c), next(0), pre(0){};

    friend class LinkedList;

private:
    char data;
    ListNode *next;
    ListNode *pre;
};

class LinkedList{
public:
    LinkedList():head(0), cursor(0){};
    void add_node(char c);
    void move_right(int p);
    void move_left(int p);
    void backspace();
    void print();

private:
    ListNode *head;
    ListNode *cursor;

};

void LinkedList::backspace(){
    // your implement

}

void LinkedList::print(){
    // your implement

}

void LinkedList::add_node(char c){
    // your implement

}

void LinkedList::move_right(int p){
    // your implement

}
void LinkedList::move_left(int p){
    // your implement

}


int main(){

    LinkedList list;
    string command;
    string input;
    int p;
    while(cin>>command){
        if(command == "Type"){
            cin >> input;
            if(input.empty()){
                continue;
            }else{
                for(int i=0; i<input.length(); i++){
                    list.add_node(input[i]);
                }
            }
        }else if(command == "Move"){
            cin >> p;
            if(p>0){
                list.move_right(p);
            }else if(p<0){
                list.move_left(p);
            }else{
                continue;
            }
        }else if(command == "Backspace"){
            list.backspace();
        }else if(command == "Print"){
            list.print();
        }else{
            continue;
        }
    }
    return 0;
}

 

Input

There are N operations specified in the input lines and N<300000.

Output

For every operation “Print”, you need to output all characters stored in the linked list and shift a newline.

Sample Input  Download

Sample Output  Download

Tags

Discuss