UVa 11988 Broken Keyboard (a.k.a. Beiju Text)

Broken Keyboard (a.k.a. Beiju Text)

Time Limit: Unknown Memory Limit: Unknown
Total Submission(s): Unknown Accepted Submission(s): Unknown

UVa 11988


https://uva.onlinejudge.org/i...

Accepted Code

// Author : Weihao Long
// Created : 2018/01/10

#include "stdio.h"
#include "stdlib.h"

#define MAX 100007

struct LNode {
    char data;
    struct LNode *next;
};

void Destroy_List(LNode *head);

char str[MAX];

int main() {
    LNode *head, *tail, *pnew, *pnow;
    head = (LNode *)malloc(sizeof(LNode));
    pnow = tail = head;
    tail->next = NULL;
    while (gets(str) != NULL) {
        for (int i = 0; str[i] != '\0'; i++) {
            if (str[i] == '[') {
                pnow = head;
            }
            else if (str[i] == ']') {
                pnow = tail;
            }
            else {
                pnew = (LNode *)malloc(sizeof(LNode));
                pnew->data = str[i];
                pnew->next = pnow->next;
                pnow->next = pnew;
                if (pnow == tail) {
                    tail = pnew;
                }
                pnow = pnew;
            }
        }
        for (LNode *p = head->next; p != NULL; p = p->next) {
            printf("%c", p->data);
        }
        putchar('\n');
        Destroy_List(head);
        head = (LNode *)malloc(sizeof(LNode));
        pnow = tail = head;
        tail->next = NULL;
    }
    return 0;
}

void Destroy_List(LNode *head) {
    LNode *p;
    while (head->next != NULL) {
        p = head->next;
        head->next = head->next->next;
        free(p);
    }
    free(head);
}

Notes

题意:
输入一个字符串,遇到 '[' 则将输入光标移到最前面,遇到 ']' 则将输入光标移到最后面,问屏幕上最终得到的字符串是什么样子。

分析:
用数组的话移动元素的开销太大,用链表做即可。
相较常规的链表,这里多设一个 pnow 指针,视作输入光标,总是指向下一个元素插入的位置,以减少查找光标的时间开销。

评论

暂无评论