立一个字符串链表，程序输入若干个字符串（用空格隔开，输入#表示结束输入），将输入的字符串分别插入容器的两端，其中大写字母开头的字符串依次插入尾端，小写字符开头的字符串依次插入前端）；完成输入后，遍历输出链表容器内所有字符串。

以下是C++的实现代码：

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

int main()
{
    list<string> strList;
    string str;
    cout << "请输入若干个字符串（用空格隔开，输入#表示结束输入）：" << endl;
    while (cin >> str && str != "#")
    {
        if (str[0] >= 'a' && str[0] <= 'z')
            strList.push_front(str);
        else if (str[0] >= 'A' && str[0] <= 'Z')
            strList.push_back(str);
    }

    cout << "链表容器内所有字符串为：" << endl;
    for (auto it = strList.begin(); it != strList.end(); ++it)
        cout << *it << " ";
    cout << endl;

    return 0;
}

运行结果示例：

请输入若干个字符串（用空格隔开，输入#表示结束输入）：
abc DEF Ghi JKL mno #
链表容器内所有字符串为：
mno Ghi DEF JKL abc

相关问题

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以二叉链表存储）。 例如如下的先序遍历字符串： abc##de#g##f### 其中“#”表示的是空格，代表一棵空树。然后再对

### 回答1：
这个二叉树进行中序遍历，并输出遍历结果。

程序如下：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def buildTree(preorder):
    if not preorder:
        return None
    val = preorder.pop(0)
    if val == '#':
        return None
    root = TreeNode(val)
    root.left = buildTree(preorder)
    root.right = buildTree(preorder)
    return root

def inorderTraversal(root):
    if not root:
        return []
    res = []
    stack = []
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        res.append(root.val)
        root = root.right
    return res

preorder = input("请输入先序遍历字符串：")
root = buildTree(list(preorder))
print("中序遍历结果为：", inorderTraversal(root))

运行程序后，输入先序遍历字符串“abc##de#g##f###”，输出中序遍历结果为“c b e g d f a”。

### 回答2：
首先，需要了解先序遍历的规则：先遍历根结点，再遍历左子树，最后遍历右子树。

接下来，根据先序遍历字符串构建二叉树的步骤如下：

1. 定义一个二叉树结构体，包含三个成员变量，一个是结点值，一个是左子树指针，一个是右子树指针；

2. 从先序遍历字符串中读取第一个字符，作为根结点的值，创建一个二叉树结点；

3. 如果字符串没有结束或者当前字符不是空格，那么递归地调用函数，读取下一个字符，创建一个左子结点；

4. 如果字符串没有结束或者当前字符不是空格，那么递归地调用函数，读取下一个字符，创建一个右子结点；

5. 返回二叉树结点指针。

下面是一个示例代码：

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        
        
def buildTree(string):
    if not string or string[0] == " ":
        return None
    
    node = Node(string[0])
    index = 1
    
    left = buildTree(string[index:])
    right = buildTree(string[index:])

    node.left = left
    node.right = right
    return node


def inorderTraversal(node):
    if not node:
        return
    inorderTraversal(node.left)
    print(node.data)
    inorderTraversal(node.right)


if __name__ == "__main__":
    string = "abc"
    root = buildTree(string)
    inorderTraversal(root)

在上面的代码中，我们首先定义了一个 `Node` 类，表示二叉树的结点。然后定义了一个 `buildTree` 函数，实现了根据先序遍历字符串建立二叉树的功能。最后再定义了一个 `inorderTraversal` 函数，用于验证建立的二叉树是否正确。我们将输入的先序遍历字符串作为函数的参数传入，返回根结点指针，然后利用中序遍历的方式遍历输出二叉树的每个结点值。

运行代码后，输出结果为：

a
b
c

即证明我们成功地根据给定的先序遍历字符串建立了一棵二叉树。

### 回答3：
先序遍历：先访问根节点，再访问左子树，最后访问右子树。

建立二叉树需要遵循如下规则：如果当前遇到的字符不是'#'，则新建一个节点，并记录上一个节点的状态；如果当前遇到的字符是'#'，则需要回溯到上一个节点，直到找到可以作为右节点的节点位置。

因此，我们可以使用栈来辅助建立二叉树，具体步骤如下：

1. 读入用户输入的一串先序遍历字符串。

2. 创建一个栈和一个根节点，并将根节点入栈。

3. 遍历输入的字符串，从左到右依次取出一个字符。

4. 如果当前字符不是'#'，则创建一个新节点，并判断栈顶节点是否有左子树。如果有，则将新节点作为其左子节点，并将其入栈；如果没有，则将新节点作为其右子节点，并将其入栈。同时，将新节点作为新的根节点。

5. 如果当前字符是'#'，则说明当前节点没有右子节点。需要回溯到上一个节点，并继续找到可以作为右子节点的节点。

6. 当所有字符遍历完成后，根据栈内节点的状态，可以建立出一个完整的二叉树。

代码如下：

请用c++编写程序，要求实现以下功能。第一，用户按行循环输入字符串，每行最多80个字符（包含空格），当用户输入的字符串不满80个时，将字符串长度加一位置的字符用换行代替，当用户输入回车时换行，键入CTRL+E时，结束循环，第二，将用户输入的字符串用尾插法插入链表，每个结点的数据域只储存一个字符，第三，按行输出链表

好的，我来解答您的问题。

下面是用C++实现该程序的代码：

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

struct Node {
    char data;      // 每个节点存储的字符
    Node* next;     // 下一个节点的指针
};

int main() {
    Node* head = new Node;  // 创建头节点
    Node* tail = head;      // 定义尾指针，初始指向头节点

    cout << "请按行输入字符串，每行最多80个字符（包含空格），CTRL+E结束输入：" << endl;
    char c;
    int i = 0;
    while ((c = getchar()) != 5) {  // 用CTRL+E结束输入
        if (c == '\n') {   // 每行结束
            if (i < 80) {  // 不满80个字符，用换行代替
                tail->data = '\n';
                tail->next = new Node;
                tail = tail->next;
                tail->next = nullptr;
            }
            i = 0;                  // 清空计数器
        } else {            // 继续输入字符
            tail->data = c;         // 存储字符
            tail->next = new Node;  // 创建新节点
            tail = tail->next;      // 尾指针后移
            tail->next = nullptr;   // 尾节点的next指针指向空
            i++;                    // 字符计数器加一
            if (i == 80) i--;      // 输入超过80个字符，强制结束该行输入
        }
    }

    cout << "您输入的字符串链表为：" << endl;
    Node* p = head->next;   // 指向第一个实际节点
    while (p != nullptr) {
        if (p->data != '\n') cout << p->data;   // 输出该节点存储的字符
        else cout << endl;                      // 换行符输出换行
        p = p->next;                            // 指针后移
    }

    // 释放链表中的节点
    p = head;
    while (p != nullptr) {
        Node* q = p->next;
        delete p;
        p = q;
    }

    return 0;
}

该程序首先创建一个头节点，接着循环输入字符串，每行最多80个字符（包含空格），当用户输入的字符串不满80个时，将字符串长度加一位置的字符用换行代替，用尾插法将每个字符存储在链表中。最后按行输出链表，并释放链表中的节点。