题目

尾插法建立单链表[1]（带头结点[2]），请补充以下代码：（注意不要有多余的空格和分号，注意大小写，空用NULL表达）typedef struct LNode ( int data; struct LNode *next;) LNode, *LinkList;void CreateList_Tail(LinkList &L, int n) ( / 建立带表头结点的单链表L，并初始化 L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; LNode *r = L; / r指向尾结点 for (int i = 0; i < n; i++) { LNode *p = (LNode*)malloc(sizeof(LNode)); scanf("%d", &(p->data)); / 填空1: 将新结点p插入到r之后 ________; / 填空2: 更新尾指针r ________; ) / 填空3: 尾结点指针域置空 ________;}

尾插法建立单链表[1]（带头结点[2]），请补充以下代码：（注意不要有多余的空格和分号，注意大小写，空用NULL表达）

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

void CreateList_Tail(LinkList &L, int n) {
// 建立带表头结点的单链表L，并初始化
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
LNode *r = L; // r指向尾结点
for (int i = 0; i < n; i++) {
LNode *p = (LNode*)malloc(sizeof(LNode));
scanf("%d", &(p->data));
// 填空1: 将新结点p插入到r之后
________;
// 填空2: 更新尾指针r
________;
}
// 填空3: 尾结点指针域置空
________;
}

题目解答

答案

根据题目要求，尾插法建立单链表（带头结点），需要完成以下步骤： 1. 初始化头结点 `L`，并设置 `L->next = NULL`。 2. 使用指针 `r` 指向当前尾结点（初始为 `L`）。 3. 循环读取 `n` 个元素，每次创建新结点 `p`，将其插入到 `r` 之后，并更新 `r` 指针。 4. 最后，将尾结点的 `next` 指针置为 `NULL`。 具体填空如下： - 填空1：将新结点 `p` 插入到 `r` 之后，即 `r->next = p`。 - 填空2：更新尾指针 `r`，即 `r = p`。 - 填空3：尾结点指针域置空，即 `r->next = NULL`。 完整代码如下： ```c typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; void CreateList_Tail(LinkList &L, int n) { L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; LNode *r = L; // r指向尾结点 for (int i = 0; i < n; i++) { LNode *p = (LNode *)malloc(sizeof(LNode)); scanf("%d", &(p->data)); r->next = p; // 将新结点p插入到r之后 r = p; // 更新尾指针r } r->next = NULL; // 尾结点指针域置空 } ```

解析

本题考查尾插法建立带头结点的单链表的知识。解题思路如下：

  1. 首先，要初始化一个带头结点的单链表。通过 L = (LinkList)malloc(sizeof(LNode)); 为头结点分配内存，并且将头结点的 next 指针初始化为 NULL，即 L->next = NULL;。同时，使用指针 r 指向当前的尾结点，初始时尾结点就是头结点，所以 LNode *r = L;。
  2. 接着，进入循环读取 n 个元素。在每次循环中，创建一个新的结点 p，使用 LNode *p = (LNode*)malloc(sizeof(LNode)); 为其分配内存，然后通过 scanf("%d", &(p->data)); 读取用户输入的数据存储到新结点的 data 域。
  3. 对于填空1，要将新结点 p 插入到尾结点 r 之后。在单链表中，一个结点的 next 指针指向下一个结点，所以将 r 的 next 指针指向新结点 p，即 r->next = p;。
  4. 对于填空2，当新结点 p 插入到 r 之后后，p 就成为了新的尾结点，所以需要更新尾指针 r，让 r 指向新的尾结点 p，即 r = p;。
  5. 最后，当所有元素都插入到链表中后，对于填空3，需要将尾结点的 next 指针置为空，以表示链表的结束，即 r->next = NULL;。