PTA Problem Sets 14

7-32 说反话-加强版

给定一句英语，要求你编写程序，将句中所有单词的顺序颠倒输出。

输入格式

测试输入包含一个测试用例，在一行内给出总长度不超过500 000的字符串。字符串由若干单词和若干空格组成，其中单词是由英文字母（大小写有区分）组成的字符串，单词之间用若干个空格分开。

输出格式

每个测试用例的输出占一行，输出倒序后的句子，并且保证单词间只有1个空格。

输入样例

Hello World   Here I Come

输出样例

Come I Here World Hello

分析与答案

题目给出了总长度，可以采用大数组的形式，但下面的程序依然使用链表的形式处理，为了方便指针的来回移动，这一道题建立的是双向链表，每个节点包含一个字符，一个指向前一节点的指针和一个指向下一节点的指针。

输入的处理和之前统计字符串单词长度的处理类似，但由于这一道题要求的是单词倒序输出而不是字母倒序输出，输出采取的是以下循环方式（输出前已完成链表处理，单词之间只有一个空格，结尾没有空格）：

  1. 如果已经到达头节点，退出循环；
  2. 如果没有到达头节点，则指向单词结尾的q指针先移动到指向单词开头的p指针的位置（在最开始，p指针位于链表末尾）；
  3. 移动p指针，直到p指针中指向前一节点的指针为空（已经到头节点）或者前一节点储存的是空格，此时p指针已经在单词的开头；
  4. 把链表自己的指针拉到p的位置，p指针开始输出并移动，直到q的位置；
  5. 把p指针拉回到单词开头，如果此时还没有到链表头节点，就把储存的前一节点（必定是空格）输出，并移动到空格之前的节点，进入下一个循环。

如果只有一个字母，意味着上面的循环一开始就在头节点，会直接退出循环。这种情况可以单独处理，直接输出头结点的字母（测试点中，如果只有空格，输出空格是符合要求的）。

#include <stdio.h>
#include <stdlib.h>

//定义链表节点
typedef struct list{
    struct list * pre;
    char letter;
    struct list * next;
} str;

int main(){
    str * char_list = (str*)malloc(sizeof(str));
    //头节点完全初始化，只对头节点这样做
    char_list->pre = NULL;
    char_list->letter = EOF;
    char_list->next = NULL;
    char c=getchar();
    while(c!='\n'){
        //遇到换行符结束
        if(c!=' '){
            //非空格非换行符，为字母，塞入节点
            if(char_list->letter==EOF){
                //头节点，只塞入字符
                char_list->letter = c;
            }
            else{
                //非头节点，创建新节点塞入
                char_list->next = (str*)malloc(sizeof(str));
                char_list->next->pre = char_list;
                char_list = char_list->next;
                char_list->letter = c;
            }
        }
        else{
            if(char_list->letter!=' '&& char_list->pre!=NULL){
                //现节点不是空格，也不是第一个节点，创建新节点插入一个空格
                //如果先节点是空格，或者是第一个节点，那就什么都不做
                char_list->next = (str*)malloc(sizeof(str));
                char_list->next->pre = char_list;
                char_list = char_list->next;
                char_list->letter = c;
            }
        }
        //读取下一个字符
        c= getchar();
    }
    //如果结尾有空格，删掉最后一个节点
    if(char_list->letter==' '){
        str *tmp = char_list;
        char_list = char_list->pre;
        free(tmp);
    }
    //最后一个字母的next指针置空
    char_list->next = NULL;
    str *p = char_list,*q;
    while(1){
        if(p->pre==NULL)
            //已经到头节点，结束循环
            break;
        //q指针拉上来
        q = p;
        while(p->pre!=NULL && p->pre->letter!=' ')
            //到头节点或者到空格前停下
            p = p->pre;
        //char_list指针拉上来
        char_list = p;
        while(p != q){
            printf("%c",p->letter);
            p = p->next;
        }
        //打完最后一个字母
        printf("%c",p->letter);
        //p指针拉上来
        p = char_list;
        if(p->pre!=NULL){
            //p还没到头节点，打空格
            p = p->pre;
            printf("%c",p->letter);
            p = p->pre;
        }
    }
    //如果只有一个字母
    if(p->next==NULL&&p->letter!=EOF)
        printf("%c",p->letter);
    return 0;
}

7-32 测试点