小白书里数据结构基础线性表的训练参考 题目都是从uva中取的

 

题目连接

virtual judge 里有，可以去注册。

 

解题思路

试着解样例，会得到这样的经验：

　　找到目标序列中第一个匹配不到的名字（从初始序列中的上一个匹配的位置找起）。把这个名字从初始位置拉到栈顶。

　　重复直到目标序列全部匹配。

注 匹配是指一次扫描序列，指针不回头。

用这个思路写代码，交上去AC了。为什么这样的步数最少呢？每次把不匹配的名字从初始位置拉倒栈顶，总的匹配数加一，而且不可能减少，因为你是从序列

开头一个一个匹配的。有没可能一次移动后匹配数增加不止一呢？也不可能（想一想为啥）。

 

代码中我是用动态的单链表模拟乌龟们的。

哦，对了。读入数据的时候记得把所有的空格吃掉。。。别以为一个getchar()就吃掉了，可能有很多个空格。。。

 

代码：

#include
     
      #include
      
        #include
       
        using namespace std;//#define LOCALtypedef struct node {    char s[90];    struct node *next;}Node;void Add(Node *first, Node *&rear){    Node *temp = new Node;    gets(temp->s); temp->next = first->next;    first->next = temp;    if(rear->next != NULL) rear = rear->next;}void DeleteAdd(char *s, Node *f, Node *&r){    Node *p = f->next, *pre = f;    while(p != NULL && strcmp(s, p->s)) { pre = p; p = p->next; }    pre->next = p->next;    r->next = p;    r = p;    p->next = NULL;}void doIt(Node *firstR, Node *&rearR, Node *firstT, Node *&rearT){    Node *rawf = firstR;    Node *targetf = firstT;    Node *rawr = rearR;    Node *targetr = rearT;    Node *pr, *pt;    pr = rawf->next; pt = targetf->next;    while(pt != NULL) {        while(pr != NULL && strcmp(pr->s, pt->s)) pr = pr->next;        if(pr == NULL) {            cout << pt->s << endl;            DeleteAdd(pt->s, rawf, rearR);            pr = rawf->next; pt = targetf->next;        }        else pt = pt->next;    }}void Delete(Node *f){    Node *p;    while(p!=NULL) { f = f->next; delete p; p = f; }}int main(){    #ifdef LOCAL        freopen("data.txt", "r", stdin);        freopen("ans.txt", "w", stdout);    #endif    int n;    scanf("%d", &n);    while(n--) {        Node *firstR = new Node; firstR->next = NULL;        Node *rearR = firstR;        Node *firstT = new Node; firstT->next = NULL;        Node *rearT = firstT;        int number;        scanf("%d", &number);        char c;        while(c = getchar()!='\n') ;        for(int i=0; i