PTA 算法2-4 求单链表list中的元素个数，即表长

算法2-4 求单链表list中的元素个数，即表长

分数 15 作者 陈越 单位 浙江大学

请编写程序，将 n 个整数顺次插入一个初始为空的单链表的表头。最后输出单链表的表长。
本题旨在训练学习者熟悉单链表的基本操作，不建议直接输出 n。

输入格式：

输入首先在第一行给出非负整数 n（≤15）；随后一行给出 n 个 int 范围内的整数，数字间以空格分隔。

输出格式：

在一行中输出单链表的表长。

输入样例：

5
1 2 3 4 5

输出样例：

5

答案

#include <iostream>
using namespace std;
typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

// 初始化链表，使其指向头结点
void InitList(LinkList &L) {
    L = new LNode; // 头指针存的是头结点的地址，指向头结点
    L->next = NULL; // L->next是头结点里面的元素next，里面是下一个结点的地址
}

// 头插法插入元素
void InsertList(LinkList &L, int num) {
    LNode *newNode = new LNode;
    newNode->data = num;
    newNode->next = L->next;
    L->next = newNode;
}

// 计算链表长度
int GetLength(LinkList L) {
    int length = 0;
    LinkList p = L->next; // 遍历指针
    while (p != NULL) {
        p = p->next;
        length++;
    }
    return length;
}

int main() {
    int n,num;
    // 读取输入整数的个数n
    cin >> n;
    LinkList L; // 定义头指针
    InitList(L);
    // 依次插入读取的整数
    for (int i = 0; i < n; i++) {
        cin >> num;
        InsertList(L,num);
    }
    // 计算链表长度
    cout << GetLength(L);
}

Summary

1.struct LNode *next;

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

• next是存下一个结点的地址的变量，next指向下一个结点（ 比如当前节点是 p，通过 p->next 就能拿到下一个节点的地址，再通过 p->next->data 就能访问下一个节点的数据 ）
• 不可以直接LNode *next;这样写，原因如下：
  • 在 typedef struct LNode{...} 内部，当定义 next 指针时，如果直接写 LNode *next;，此时 LNode 这个类型名还没有完成 typedef 的定义（typedef 是在结构体定义完成后才生效的），编译器会不认识 LNode 这个类型，从而报错。

2.LinkList L;

• 首先就是声明一个指向单链表的指针: 头指针，用头指针L可以访问头结点（而顺序表是先SqList L，声明一个顺序表，用L可以访问里面的数组和表长）

3.InitList L

// 初始化链表，使其指向头结点
void InitList(LinkList &L) {
    L = new LNode;
    L -> next = NULL;// 头结点之后暂时还没有结点
}