1999.cpp

来自「哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码」· C++ 代码 · 共 81 行

/*  This Code is Submitted by wywcgs for Problem 1999 on 2005-09-22 at 22:24:03 */ 
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

class LinkedList {
    public:
    LinkedList *before;
    LinkedList *next;
    long value;
    LinkedList* add(LinkedList *list) {
        LinkedList *p = this, *f = this;
        bool isMax = false;
        while(list->value > p->value) {
            if(p->next != NULL) {
                p = p->next;
            } else {
                isMax = true;
                break;
            }        
        }
        if(!isMax) {
            if(p->before != NULL) {
                p->before->next = list;
                list->before = p->before;
            } else {
                f = list;
            }
            p->before = list;
            list->next = p;
        } else {
            p->next = list;
            list->before = p;
        }
        return f;
    }
    LinkedList* del() {
        LinkedList *f = this->next;
        if(this->next != NULL) {
            this->next->before = NULL;
        }
        return f;
    }    
    LinkedList(long va) {
        before = NULL;
        next = NULL;
        value = va;
    }
};

int main()
{
    LinkedList *first = NULL, *list;
    char order[10];
    long T, i, value;
    
    scanf("%ld", &T);
    for(i = 0; i < T; i++) {
        scanf("%s", order);
        if(!strcmp(order, "add")) {
            scanf("%ld", &value);
            if(first == NULL) {
                first = new LinkedList(value);
            } else {
                list = new LinkedList(value);
                first = first->add(list);
            }
        } else if(!strcmp(order, "query")) {
            if(first != NULL) {
                printf("%ld\n", first->value);
            }
        } else if(!strcmp(order, "delete")) {
            if(first != NULL) {
                first = first->del();
            }    
        }    
    }
    
    return 0;    
}