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

以下是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/C++：编写程序建立一个单向链表。链表结点中的数据为从键盘输入的一个字符串，但要求将该串字符按由小到大的顺序组织在链表中。 ​

以下是我用 C++ 编写的程序，可以实现你的要求：

#include <iostream>
#include <string>

using namespace std;

// 定义链表结点
struct ListNode {
    string val;
    ListNode* next;
    ListNode(string x) : val(x), next(nullptr) {}
};

// 插入一个结点
void insert(ListNode* head, string val) {
    ListNode* node = new ListNode(val);
    ListNode* prev = head;
    while (prev->next != nullptr && prev->next->val < val) {
        prev = prev->next;
    }
    node->next = prev->next;
    prev->next = node;
}

int main() {
    // 创建头结点
    ListNode* head = new ListNode("");
    cout << "请输入字符串（以空格分隔）：" << endl;
    string s;
    while (cin >> s) {
        // 按顺序插入结点
        insert(head, s);
    }

    // 遍历链表并输出结果
    ListNode* p = head->next;
    while (p != nullptr) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;

    // 释放内存
    p = head;
    while (p != nullptr) {
        ListNode* q = p->next;
        delete p;
        p = q;
    }

    return 0;
}

程序思路如下：

1. 定义链表结点 `ListNode`，其中 `val` 存储字符串，`next` 指向下一个结点。
2. 创建头结点 `head`。
3. 从键盘输入一串字符串，每次调用 `insert` 函数将其插入链表中。
4. `insert` 函数中，从头结点开始遍历链表，找到插入位置并插入结点。
5. 遍历链表并输出结果。
6. 释放内存，从头结点开始遍历链表并依次删除每个结点。

其中比较关键的是 `insert` 函数的实现，它保证了链表中的字符串按从小到大的顺序排列。