C语言解决 头插+尾插法建立单链表 【问题描述】 小明尝试用头插法和尾插法建立一个单链表，从空表开始， 他每次输入两个整数 p,q，其中 p 是插入的类型(1 表示头插法，2 表示尾插法)，q 是插入的元素。 例如假设单链表 t 最初为空，即[], 若用户输入 1 5 ，表示用头插法插入元素5， 则单链表 t 的内容为 [5] 请编写程序实现上述过程。 【输入格式】 用户输入若干行， 每一行有两个格式： 如果包含两个整数p,q，用空格分隔，则 p=1 表示头插法，p=2 表示尾插法插入元素q; 如果只包含一个整数p, 且p不是1或者2，则表示插入操作结束。 【输出格式】 每一次插入操作后，打印当前单链表的内容，例如： [->5->6->8] 单链表的内容用[]包裹，每个元素之前用->表示链。 【样例输入】 1 5 2 8 1 6 0 【样例输出】 [->5] [->5->8] [->6->5->8] 【样例输入】 1 9 2 8 1 7 2 6 2 5 1 10 1 4 2 3 2 2 1 1 1 10 2 11 -1 【样例输出】 [->9] [->9->8] [->7->9->8] [->7->9->8->6] [->7->9->8->6->5] [->10->7->9->8->6->5] [->4->10->7->9->8->6->5] [->4->10->7->9->8->6->5->3] [->4->10->7->9->8->6->5->3->2] [->1->4->10->7->9->8->6->5->3->2] [->10->1->4->10->7->9->8->6->5->3->2] [->10->1->4->10->7->9->8->6->5->3->2->11] 【样例输入】 2 4 1 3 1 6 1 1 2 5 1 2 3 【样例输出】 [->4] [->3->4] [->6->3->4] [->1->6->3->4] [->1->6->3->4->5] [->2->1->6->3->4->5]

<think>嗯，用户需要编写一个C语言程序，用头插法和尾插法建立单链表，并在每次插入后输出链表内容。首先我得理清楚问题要求。 题目说输入每行有两个整数p和q，p是1或2表示插入方式，q是元素。如果输入一个非1、2的整数就结束。每次插入后要输出当前链表。输出格式是像[->5->8]这样的。 首先，我需要设计链表的结构。单链表通常由节点构成，每个节点包含数据和指向下一个节点的指针。所以结构体应该是这样的： struct Node { int data; struct Node* next; }; 然后，链表的头指针和尾指针可能需要维护。因为头插法只需要头指针，而尾插法如果每次都遍历到尾部会很慢，所以可以维护一个尾指针，这样尾插的时候直接操作尾指针即可，时间复杂度O(1)。 所以，可能需要一个结构体来保存链表的头尾指针，比如： typedef struct { struct Node* head; struct Node* tail; } LinkedList; 初始化的时候，head和tail都是NULL。每次插入的时候，根据p的值选择头插还是尾插。 头插法的步骤是： 1. 创建新节点。 2. 新节点的next指向当前头节点。 3. 更新头节点为新节点。 如果链表为空，那么插入头节点时，尾指针也应该指向这个新节点。 尾插法的步骤是： 1. 创建新节点。 2. 如果链表为空，头尾都指向新节点。 3. 否则，当前尾节点的next指向新节点，然后更新尾指针为新节点。 每次插入后，需要遍历链表输出所有元素。但遍历的话，如果链表很长会影响效率。不过题目中的样例输出似乎每次都是完整的链表，所以必须从头节点开始遍历，依次打印每个节点的数据。 输出的格式需要注意：开始是[，然后是每个元素前的->，最后是]。例如，当链表是5时，输出[->5]。当插入8到尾部，变成5->8，输出[->5->8]。 那如何实现这个输出呢？可以遍历链表，从head开始，每次打印->和节点的数据。如果链表为空，应该输出[]。 接下来处理输入的问题。输入是多行，每行可能有两个整数或者一个结束的整数。在C语言中，可以用循环读取输入，直到遇到不符合的情况。比如，可以用scanf读取第一个整数p，如果成功，再判断是否是1或2。如果是，继续读取q，否则结束循环。 但需要注意，当输入的行只有一个非1、2的整数时，结束。所以每次循环先读p，如果是1或2，再读q。否则，结束。 每次插入操作后都要输出链表。所以每次执行插入函数之后，调用打印函数。 现在，如何管理链表？可以用一个LinkedList变量，初始时head和tail都是NULL。每次插入操作，根据p的值调用对应的函数，比如insert_head或insert_tail。然后打印。 现在考虑具体的函数实现： 插入头部的函数： void insert_head(LinkedList* list, int q) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = q; newNode->next = list->head; list->head = newNode; // 如果链表之前为空，尾指针也要更新 if (list->tail == NULL) { list->tail = newNode; } } 插入尾部的函数： void insert_tail(LinkedList* list, int q) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = q; newNode->next = NULL; if (list->tail == NULL) { // 链表为空 list->head = newNode; list->tail = newNode; } else { list->tail->next = newNode; list->tail = newNode; } } 然后打印链表的函数： void print_list(LinkedList* list) { printf("["); struct Node* current = list->head; while (current != NULL) { printf("->%d", current->data); current = current->next; } printf("]\n"); } 这样每次插入后调用print_list即可。 接下来是主函数的逻辑： 初始化LinkedList结构体，head和tail为NULL。 循环读取输入： 每次先读一个整数p。如果p是1或2，接着读q，执行对应的插入操作，并打印。否则，结束循环。 但需要注意，当输入的一行只有一个非1、2的整数时，比如0或者3，这时候就结束。在C中，如何判断输入行是否有两个整数？ 这里可能出现的问题是，当用户输入的是比如“0”，这时候scanf("%d", &p)会成功，然后判断p不是1或2，结束循环。但如果用户输入的是“1 5”，则读取p=1，q=5。那如何正确处理输入？ 可以用这样的方法：在每次循环中，先尝试读取两个整数。如果成功，且p是1或2，则处理插入。否则，检查是否输入的是一个整数，如果是非1、2的，就结束。 但可能的问题在于，如果用户输入的是例如“abc”这样的非整数，程序会出错。但题目中样例输入都是正确的，所以可能不需要处理这种情况。 或者，更简单的做法是：每次用scanf读取两个整数，如果返回值为2，且p是1或2，处理插入。否则，检查是否返回值是1且p不是1或2，结束。或者，如果返回值是0或EOF，则结束。 但用户输入的结束条件是当输入一个非1、2的整数。例如，样例输入中的第三个输入行是3，所以当读取到p=3时，结束。 所以主函数的读取逻辑可能是这样的： int p, q; while (1) { int result = scanf("%d", &p); if (result != 1) { // 输入结束或错误，退出循环 break; } if (p == 1 || p == 2) { // 继续读取q if (scanf("%d", &q) != 1) { // q读取失败，可能输入错误，退出循环 break; } // 执行插入操作 if (p == 1) { insert_head(&list, q); } else { insert_tail(&list, q); } // 打印链表 print_list(&list); } else { // 输入结束 break; } } 但这里可能存在一个问题：当用户输入的一行有两个整数，第二个是无效的，比如“1 a”，此时scanf读取p=1成功，然后读取q失败，导致程序处理错误。不过题目中的输入都是正确的情况，所以可能不需要处理这种错误。 综上，主函数的大致结构是这样的。 现在需要测试样例输入是否正确。 比如第一个样例输入： 1 5 2 8 1 6 0 处理过程： 第一行，p=1，q=5，头插法，链表变为5，输出[->5] 第二行，p=2，q=8，尾插法，链表变为5->8，输出[->5->8] 第三行，p=1，q=6，头插法，链表变为6->5->8，输出[->6->5->8] 第四行，输入0，p=0，非1、2，结束循环。 输出结果符合样例。 第二个样例输入比较复杂，但按照同样的逻辑处理应该没问题。 现在需要考虑的是，当使用头插法时，如果链表不为空，那么头指针会被更新，而尾指针是否会被正确维护？ 例如，当链表已经有元素，头插法插入新的节点，此时尾指针是否需要改变？ 比如初始链表为空，头插5，头尾都指向5。此时头插6，头指针变为6，next是5。尾指针还是5吗？是的，因为尾指针是最后一个元素，此时链表是6->5，所以尾指针应该是5。而如果头插的时候，原来的链表非空，那么插入新头节点后，尾指针不需要改变，除非原来的链表是空的。所以在头插法的函数中，只有在链表为空时，才需要更新尾指针。否则，尾指针保持不变。 例如： 头插法插入第一个元素，头尾都指向它。 再头插第二个元素，头指针指向新元素，next是原来的头节点。此时尾指针还是原来的头节点。比如插入顺序是头插5，此时头尾都指向5。然后头插6，头是6，next是5，尾仍然是5。因此，当链表非空时，头插法不影响尾指针，只有初始插入的时候才会设置尾指针。 这样，在头插法的函数中，当插入新节点后，如果原来的头指针是NULL（即链表为空），那么尾指针也要指向新节点。否则，尾指针不变。 例如： void insert_head(LinkedList* list, int q) { struct Node* newNode = createNode(q); newNode->next = list->head; list->head = newNode; if (list->tail == NULL) { list->tail = newNode; } } 这样是否正确？ 比如，当链表为空时，插入头节点，head和tail都指向新节点。之后再次头插，此时head更新为新节点，tail保持原来的尾节点（即之前的头节点）。例如： 插入头插5，链表是5，head和tail都是5。 再头插6，链表是6->5。此时head是6，tail还是5，因为插入到头部，尾部没有变化。这是正确的，因为尾节点是最后一个元素，也就是5。 那在这种情况下，当使用尾插法时，如果链表不为空，那么尾指针是正确的，可以正确插入到尾部。 例如，在上述情况后，执行尾插8，那么尾指针是5，插入到5的后面，新的尾是8。链表变成6->5->8。此时头是6，尾是8。这样是正确的。 所以在头插法中，只有当链表为空时，才需要更新尾指针。否则，尾指针保持不变。这确保了在头插之后，尾指针仍然指向原来的最后一个节点，但只有当原链表为空时才需要设置。 这样处理是否正确？ 是的。例如，在头插之后，链表中的尾节点只有在原链表为空时才会改变。否则，尾节点保持不变，而头节点前移。这可能导致链表中间或头部的节点成为新的头，而尾节点不变。 例如： 原链表是空，头插5，head和tail都是5。 再次头插6，head是6，next是5，tail还是5。 这样，此时链表的结构是6->5，尾节点是5。此时，如果执行尾插8，则新的节点8会被插入到5的后面，链表变成6->5->8，tail变为8。正确。 所以，头插法中，当原链表非空时，尾指针不需要更新，是正确的。 因此，头插法的函数是正确的。 接下来是尾插法的情况： 如果链表为空，插入新节点，头尾都指向它。 否则，将新节点添加到当前尾节点的后面，更新尾指针。 这样是正确的。 那整个链表的结构维护是正确的。 现在，测试样例输入的情况： 第一个样例输入： 操作顺序： 1 5 →头插5 →链表是5 →输出[->5] 2 8 →尾插8 →链表是5->8 →输出正确 1 6 →头插6 →链表是6->5->8 →输出正确 此时，链表的头是6，尾是8。正确。 所以，输出第三个结果正确。 第二个样例输入比较复杂，但按照同样的逻辑处理即可。 现在，考虑代码的实现是否正确。 另外，需要注意内存管理，虽然题目可能不要求释放链表内存，但在实际程序中应该释放，但题目中可能不需要，因为程序结束后操作系统会回收。 综上，整个程序的流程是： 初始化LinkedList结构体。 循环读取输入，每次读取p，如果是1或2，读q，插入，打印。 否则，结束。 现在编写代码： 首先，定义结构体和函数： #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* next; }; typedef struct { struct Node* head; struct Node* tail; } LinkedList; void insert_head(LinkedList* list, int q) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = q; newNode->next = list->head; list->head = newNode; if (list->tail == NULL) { list->tail = newNode; } } void insert_tail(LinkedList* list, int q) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = q; newNode->next = NULL; if (list->tail == NULL) { list->head = newNode; list->tail = newNode; } else { list->tail->next = newNode; list->tail = newNode; } } void print_list(LinkedList* list) { printf("["); struct Node* current = list->head; while (current != NULL) { printf("->%d", current->data); current = current->next; } printf("]\n"); } int main() { LinkedList list = {NULL, NULL}; int p, q; while (1) { // 读取p int result = scanf("%d", &p); if (result != 1) { break; } if (p == 1 || p == 2) { // 读取q if (scanf("%d", &q) != 1) { break; } if (p == 1) { insert_head(&list, q); } else { insert_tail(&list, q); } print_list(&list); } else { // 输入结束 break; } } // 释放链表内存（可选，但题目可能不要求） struct Node* current = list.head; while (current != NULL) { struct Node* temp = current; current = current->next; free(temp); } return 0; } 这样应该可以正确处理样例输入。 现在测试样例输入： 第一个样例输入： 1 5 →插入头，链表是5。输出[->5] 第二个输入是2 8 →尾插，链表是5->8 →输出正确。 第三个输入是1 6 →头插，链表是6->5->8 →输出正确。 当输入0时，循环结束。 所以输出结果与样例一致。 第二个样例输入中的情况，比如插入多个头尾操作，应该正确维护头尾指针，所以输出正确。 现在需要注意的是，尾插法在头插后的正确性。比如，头插导致链表头改变，但尾指针不变，如果之后尾插的话，会正确添加到尾部。 例如，在样例输入中，第一组操作是头插5，然后尾插8，此时链表是5->8。此时头是5，尾是8。然后头插6，链表变为6->5->8，头是6，尾还是8。之后尾插的话，应该正确添加到8的后面，比如如果有后续的尾插，会正确。 这样，程序逻辑正确。 综上，这个程序应该可以正确解决问题。</think>以下是C语言实现头插法和尾插法建立单链表并按要求输出的代码： ```c #include <stdio.h> #include <stdlib.h> // 链表节点结构 struct Node { int data; struct Node* next; }; // 链表头尾指针封装 typedef struct { struct Node* head; struct Node* tail; } LinkedList; // 头插法实现 void insert_head(LinkedList* list, int q) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = q; newNode->next = list->head; list->head = newNode; if (list->tail == NULL) { // 初始为空链表时需要更新尾指针 list->tail = newNode; } } // 尾插法实现 void insert_tail(LinkedList* list, int q) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = q; newNode->next = NULL; if (list->tail == NULL) { // 空链表时头尾指针都指向新节点 list->head = list->tail = newNode; } else { // 非空链表时更新尾指针 list->tail->next = newNode; list->tail = newNode; } } // 打印链表内容 void print_list(LinkedList* list) { printf("["); struct Node* current = list->head; while (current != NULL) { printf("->%d", current->data); current = current->next; } printf("]\n"); } int main() { LinkedList list = {NULL, NULL}; // 初始化空链表 int p, q; while (1) { if (scanf("%d", &p) != 1) break; // 读取操作类型 if (p == 1 || p == 2) { // 插入操作 if (scanf("%d", &q) != 1) break; if (p == 1) insert_head(&list, q); else insert_tail(&list, q); print_list(&list); // 插入后立即打印 } else { // 结束操作 break; } } // 内存释放（可选） struct Node* current = list.head; while (current != NULL) { struct Node* temp = current; current = current->next; free(temp); } return 0; } ``` ### 代码解析 1. **数据结构设计** - `struct Node` 表示链表节点，包含数据域 `data` 和指针域 `next` - `LinkedList` 封装头尾指针，方便同时维护头插和尾插操作 2. **核心操作函数** - **头插法**：新节点插入链表头部，若链表为空需同时更新尾指针 - **尾插法**：新节点追加到链表尾部，通过尾指针 $O(1)$ 时间复杂度完成操作 3. **输入处理逻辑** - 循环读取输入直到遇到非1/2的操作码 - 每次插入后立即调用打印函数输出当前链表状态 4. **输出格式控制** - 使用 `[->元素->元素]` 格式，通过遍历链表实现格式化输出 ### 执行流程示例 输入样例： ``` 1 5 2 8 1 6 0 ``` 输出结果： ``` [->5] // 头插5 [->5->8] // 尾插8 [->6->5->8] // 头插6 ```