P4858 输出字母（入门）

解题思路

第一步，理解题意。 这道题要练习结构体和链表：创建 5 个结构体变量，分别存储字母 A、B、C、D、E，然后把 5 个变量用指针链接成一个链表，最后从第一个结点开始依次输出链表里的数据。本题没有输入，直接输出 ABCDE。

第二步，认识链表结点。 链表就像一列手拉手的小朋友，每个人一只手拉着下一个人。用 struct 定义结点 Node，它有两个成员：一个 char 类型的 ch 用来存字母，一个 Node* 类型的 next 用来存"下一个结点的地址"（指针）。这样一个结点既能存数据，又能找到下一个结点。

第三步，链接成链表。 定义 n1 到 n5 五个结点，分别给 ch 赋 A、B、C、D、E。然后用取地址符 & 把结点连起来：n1.next = &n2，n2.next = &n3，n3.next = &n4，n4.next = &n5。最后一个结点 n5.next 要赋成 0（空指针），表示链表到这里结束，否则遍历时就不知道什么时候该停下来。

第四步，遍历输出。 用一个指针 p 从第一个结点开始：p = &n1。循环里先输出 p->ch，再让 p 指向下一个结点 p = p->next。当 p 变成 0（空指针）时，说明链表走完了，循环结束。用 p->ch 是"箭头取成员"的写法，等价于 (*p).ch。

第五步，验证结果。 从 n1 开始依次走：n1 是 A，走到 n2 是 B，再到 n3 是 C、n4 是 D、n5 是 E，输出就是 ABCDE，和样例一致。

参考代码

// 输出字母：5个结构体变量存A~E，链接成链表依次输出
#include <iostream>
using namespace std;
struct Node {       // 链表结点
    char ch;
    Node *next;
};
int main() {
    Node n1, n2, n3, n4, n5;
    n1.ch = 'A'; n2.ch = 'B'; n3.ch = 'C'; n4.ch = 'D'; n5.ch = 'E';
    n1.next = &n2;  // 依次链接成链表
    n2.next = &n3;
    n3.next = &n4;
    n4.next = &n5;
    n5.next = 0;    // 最后一个结点的next为空
    Node *p = &n1;
    while (p) {     // 从头到尾遍历链表
        cout << p->ch;
        p = p->next;
    }
    cout << endl;
    return 0;
}

复杂度分析

时间复杂度：链表一共有 5 个结点，从头到尾只走一遍，所以是 O(5) 的常数时间。

空间复杂度：只用了 5 个固定结点，是 O(1) 的常数空间。