单链表尾插入和头插入
单链表尾插入和头插入函数代码实现是怎样的呢？虽然有注释 但是还是看不太明白逻辑 能以生动形象的方式解答以下吗？
或者图片的方式给我以下分析思路！万分感谢！
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int value; // 节点存储的值
struct Node *next; // 指向下一个节点的指针
};
// 判断单链表是否为回文链表
int recurCheck(struct Node *head, struct Node *tail);
// 遍历并打印单链表
void printNode(struct Node *head);
// 在链表头部插入节点
void insertNode_one(struct Node **head, int value);
// 在链表尾部插入节点
void insertNode_two(struct Node **head, int value);
void insertNode_one(struct Node **head, int value)
{
struct Node *node; // 定义节点指针
struct Node *temp; // 临时变量指针，用于保存当前头结点的下一个节点
node = (struct Node *)malloc(sizeof(struct Node)); // 为节点分配内存空间
if(node == NULL) // 判断内存分配是否成功
{
printf("内存分配失败了！\n");
exit(1);
}
node->value = value; // 将输入的值存入新节点value成员变量中
if(*head != NULL) // 单链表不为空
{
temp = *head; // 将临时指针变量保存为当前头结点的下一个节点
*head = node; // 将node指针变量的值更新为头结点指针变量的值
node->next = temp; // 将node指针变量的下一个节点为当前头结点的下一个节点
}
else // 单链表为空
{
*head = node; // 直接将node指针变量赋值给头结点指针变量
node->next = NULL; // 将node指针变量的下一个节点赋值为NULL
}
}
void insertNode_two(struct Node **head, int value)
{
struct Node *node; // 定义节点指针
struct Node *temp; // 临时变量指针，用于保存当前头结点的下一个节点
node = (struct Node *)malloc(sizeof(struct Node)); // 为节点分配内存空间
if(node == NULL) // 判断内存分配是否成功
{
printf("内存分配失败了！\n");
exit(1);
}
node->value = value; // 将输入的值存入新节点value成员变量中
if(*head != NULL) // 单链表不为空
{
temp = *head;
while(temp->next != NULL) // 寻找最后一个节点
{
temp = temp->next;
}
temp->next = node; // 最后一个节点的下一个节点为新插入的节点
node->next = NULL; // 新插入的节点的下一个节点为NULL
}
else // 单链表为空
{
*head = node;
node->next = NULL;
}
}
void printNode(struct Node *head)
{
struct Node *current; // 当前节点指针变量
current = head; // 将head指针变量赋值给current指针变量
printf("录入的单链表是：");
while(current != NULL) // 循环打印链表中的所有节点
{
printf("%d ",current->value);
current = current->next;
}
putchar('\n');
}
int recurCheck(struct Node *head_one, struct Node *head_two)
{
// 循环遍历两个链表中的每个节点，并比较节点值是否相等
while(head_one)
{
if(head_one->value != head_two->value)
{
return 0;
}
head_one = head_one->next;
head_two = head_two->next;
}
return 1;
}
int main(void)
{
struct Node *head_one = NULL; // 链表1的头结点指针变量
struct Node *head_two = NULL; // 链表2的头结点指针变量
int input; // 用于存储用户输入的数字
while(1)
{
printf("请输入一个整数（输入-1表示结束）：");
scanf("%d",&input);
if(input == -1)
{
break;
}
insertNode_one(&head_one, input); // 头插入链表1
insertNode_two(&head_two, input); // 尾插入链表2
}
printNode(head_two); // 打印链表2，确认尾插入是否成功
printNode(head_one); // 打印链表1，确认头插入是否成功
if (recurCheck(head_one, head_two)) // 判断链表是否为回文链表
{
printf("录入的单链表是回文链表！\n");
}
else
{
printf("录入的单链表不是回文链表！\n");
}
return 0;
}
这段代码实现了单链表的头**和尾**两个函数，下面我们来简单解释一下它们的逻辑：
头**函数 insertnode_one
1. 首先判断单链表是否为空，如果不为空，将当前链表的头结点保存在temp指针变量中；
2. 分配新节点空间，将输入的值存储在value成员变量中；
3. 将头指针变量head指向新分配的节点，更新为当前节点；
4. 将新节点的next成员变量指向之前的头节点temp。
尾**函数 insertnode_two
1. 首先判断单链表是否为空，如果不为空，遍历整个链表，找到最后一个节点；
2. 分配新节点空间，将输入的值存储在value成员变量中；
3. 将最后一个节点的next成员变量指向新分配的节点；
4. 将新节点的next成员变量设置为null。
通过这两个函数实现的单链表可以用于判断回文字符串。其中，头**函数可以快速地构造与原字符串相反的字符串（即翻转后的字符串），而尾**函数构造的则是原字符串。最后比较这两个链表是否相等即可判断回文字符串。
同时，该代码还提供了打印链表的函数printnode和判断回文链表的函数 recurcheck，可以方便地观察和调试单链表的构建过程。 我将用一个简单的示例来解释头插入和尾插入的不同之处，并帮助您理解代码中的逻辑。
假设我们有一个空链表，现在我们要向链表中插入三个整数：1、2 和 3。以下是头插入和尾插入的过程及结果。
头插入：
1、插入 1
链表：1
2、插入 2
链表：2->1
3、插入 3
链表：3->2->1
尾插入：
1、插入 1
链表：1
2、插入 2
链表：1->2
3、插入 3
链表：1->2->3
现在，我们将分析这两个插入函数的代码实现。
1、头插入函数（insertNode_one）：
a. 创建一个新的节点，并将输入值赋给新节点。
b. 如果链表不为空，则将当前头节点的下一个节点赋给新节点的下一个节点，然后将新节点作为新的头节点。
c. 如果链表为空，则将新节点作为头节点，新节点的下一个节点设置为 NULL。
2、尾插入函数（insertNode_two）：
a. 创建一个新的节点，并将输入值赋给新节点。
b. 如果链表不为空，遍历链表直到找到最后一个节点，将新节点插入到最后一个节点的后面，新节点的下一个节点设置为 NULL。
c. 如果链表为空，将新节点作为头节点，新节点的下一个节点设置为 NULL。
通过这些解释，希望您能对头插入和尾插入有更清晰的认识。如果您还有其他问题，请随时询问。 isdkz 发表于 2023-4-10 21:27
我将用一个简单的示例来解释头插入和尾插入的不同之处，并帮助您理解代码中的逻辑。
假设我们有一个空链 ...
还能再详细点吗？我想在草稿纸自己代入演算以下。。 a905448839 发表于 2023-4-10 21:29
还能再详细点吗？我想在草稿纸自己代入演算以下。。
当然可以。让我们用一个详细的示例，分步骤解释头插入和尾插入的过程。
首先，我们将使用头插入法。我们将使用相同的整数序列：1、2 和 3。
1、插入 1：
[*]创建新节点 node，将值 1 赋给 node->value
[*]检查链表是否为空（*head == NULL），链表为空
[*]设置 node 为头节点：*head = node
[*]设置 node->next = NULL
结果：链表：1
2、插入 2：
[*]创建新节点 node，将值 2 赋给 node->value
[*]检查链表是否为空（*head != NULL），链表不为空
[*]将临时指针 temp 指向头节点：temp = *head
[*]设置新节点为头节点：*head = node
[*]设置新头节点的下一个节点为原头节点：node->next = temp
结果：链表：2->1
3、插入 3：
[*]创建新节点 node，将值 3 赋给 node->value
[*]检查链表是否为空（*head != NULL），链表不为空
[*]将临时指针 temp 指向头节点：temp = *head
[*]设置新节点为头节点：*head = node
[*]设置新头节点的下一个节点为原头节点：node->next = temp
结果：链表：3->2->1
现在，我们使用尾插入法。我们将使用相同的整数序列：1、2 和 3。
1、插入 1：
[*]创建新节点 node，将值 1 赋给 node->value
[*]检查链表是否为空（*head == NULL），链表为空
[*]设置 node 为头节点：*head = node
[*]设置 node->next = NULL
结果：链表：1
2、插入 2：
[*]创建新节点 node，将值 2 赋给 node->value
[*]检查链表是否为空（*head != NULL），链表不为空
[*]将临时指针 temp 指向头节点：temp = *head
[*]遍历链表，直到找到最后一个节点（temp->next == NULL）
[*]将新节点连接到最后一个节点：temp->next = node
[*]设置 node->next = NULL
结果：链表：1->2
3、插入 3：
[*]创建新节点 node，将值 3 赋给 node->value
[*]检查链表是否为空（*head != NULL），链表不为空
[*]将临时指针 temp 指向头节点：temp = *head
[*]遍历链表，直到找到最后一个节点（temp->next == NULL）
[*]将新节点连接到最后一个节点：temp->next = node
[*]设置 node->next = NULL
结果：链表：1->2->3
现在您可以用这个详细的示例在草稿纸上代入演算。这将帮助您更好地理解头插入和尾插入的过程。
在演算时，请注意以下关键点：
[*]对于头插入法，新节点总是插入到链表的开头。因此，当我们插入一个新节点时，原来的头节点需要变成新节点的下一个节点。这就是为什么我们需要将原头节点的指针赋给新节点的 next 指针，并将新节点设置为头节点。
[*]对于尾插入法，新节点总是插入到链表的末尾。因此，我们需要遍历链表，找到最后一个节点，然后将新节点连接到最后一个节点。最后一个节点的 next 指针需要指向新节点，新节点的 next 指针设置为 NULL。
通过对这些示例进行演算，您将更深入地了解头插入和尾插入的概念和实现。如果您在演算过程中遇到任何困惑或问题，请随时向我求助。 a905448839 发表于 2023-4-10 21:29
还能再详细点吗？我想在草稿纸自己代入演算以下。。
不看我的吗 sfqxx 发表于 2023-4-10 21:36
不看我的吗
看，吸收各位大佬的精华！ isdkz 发表于 2023-4-10 21:35
当然可以。让我们用一个详细的示例，分步骤解释头插入和尾插入的过程。
首先，我们将使用头插入法。我 ...
头插入问题：
插入1：
设置 node->next = NULL
结果：链表：1
插入2：
设置新头节点的下一个节点为原头节点：node->next = temp
结果：链表：2->1
插入 3：
设置新头节点的下一个节点为原头节点：node->next = temp
结果：链表：3->2
问题1：
插入数据3的时候 链表是（3->2） 而这个2 和插入数据2里（2->1）的2是一个结构体吗？
为什么能程序能知道插入数据3（3->2）的这个2 是插入数据2那个（2->1）的那个2呢？
简单点来说 就是插入数据3后结果是3->2这个2凭什么会去指向1 变成3->2->1?
问题2：
如果成立 应该是node链表为3->2->1和传入进来的struct Node **head 或者说是 main主函数里的struct Node *head_one有什么关系呢？他们不是单独的两个链表吗？ 是怎么返回出去值的呢？ a905448839 发表于 2023-4-10 22:23
头插入问题：
插入1：
设置 node->next = NULL
问题1：
在插入数据3时，链表确实为3->2，但是这里我漏掉了一步。我为您更正一下头插入过程的步骤：
1、插入 1：
[*]创建新节点 node，将值 1 赋给 node->value
[*]检查链表是否为空（*head == NULL），链表为空
[*]设置 node 为头节点：*head = node
[*]设置 node->next = NULL
结果：链表：1
2、插入 2：
[*]创建新节点 node，将值 2 赋给 node->value
[*]检查链表是否为空（*head != NULL），链表不为空
[*]将临时指针 temp 指向头节点：temp = *head
[*]设置新节点为头节点：*head = node
[*]设置新头节点的下一个节点为原头节点：node->next = temp
结果：链表：2->1
3、插入 3：
[*]创建新节点 node，将值 3 赋给 node->value
[*]检查链表是否为空（*head != NULL），链表不为空
[*]将临时指针 temp 指向头节点：temp = *head
[*]设置新节点为头节点：*head = node
[*]设置新头节点的下一个节点为原头节点：node->next = temp
结果：链表：3->2->1
当我们插入数据3时，我们将当前的头节点保存在临时指针temp中（temp = *head，此时temp指向节点2）。
然后，我们将新创建的节点3设置为新的头节点（*head = node）。
最后，我们将新头节点（节点3）的下一个节点设置为原头节点（节点2），即node->next = temp。这样，链表就变成了3->2->1。
问题2：
在main函数里，我们创建了一个链表头指针变量head_one。
当我们调用头插入函数insertNode_one时，我们传递head_one的地址作为参数（&head_one）。
因此，我们在函数内部操作的是head_one的指针，所以对其所指向的链表进行的任何更改都会反映到main函数中的head_one变量上。
这就是为什么当我们在函数insertNode_one内部更新链表时，main函数中的head_one链表也会相应地更新。
在函数执行完毕后，head_one现在指向已更新的链表。
这两个链表不是独立的，实际上它们是同一个链表，只是在函数调用时通过传递指针来实现它们之间的连接。 isdkz 发表于 2023-4-10 22:30
问题1：
在插入数据3时，链表确实为3->2，但是这里我漏掉了一步。我为您更正一下头插入过程的步骤：
原问题1：最后，我们将新头节点（节点3）的下一个节点设置为原头节点（节点2），即node->next = temp。这样，链表就变成了3->2->1。
由于在草稿纸演算问题，我一直理解node->next = temp表达的是 把temp节点的值赋值给了当前node单链表节点指向的下一个节点的值。其实应该这样理解成 当前node单链表节点指向的下一个节点是temp这个节点才对吗？这个=不是赋值 因为team是一个节点指针 是地址，相当于把node当前单链表节点的下一个节点指向了team的地址？可以这样理解吗？
原问题2：
我始终无法明白，在头插入函数里，一直在操作node，node的链表值在改变和外面传进来的*head_one值有什么关系？如果他们是一个单链表，我也没有在代码里找到node指向*head_one。为什么node改变*head_one就会改变呢？
我只在当第一次插入的时候 if(*head == NULL)的判断语句里看到*head = node;
相当于外面head_one的地址已经改变成了node的地址是吧？
所以后面无论怎么改变node 不去改变*head也没关系，*head已经指向node了，我们只用修改node就是了吗？
问题3：
指针的地址变量是在整个文件中都是有效的吗？无论在哪个函数都可以访问吗？ a905448839 发表于 2023-4-10 23:02
原问题1：最后，我们将新头节点（节点3）的下一个节点设置为原头节点（节点2），即node->next = temp。这 ...
原问题1：
是的，您的理解是正确的。node->next = temp 的意思是将当前 node 节点的下一个节点设置为 temp 指向的节点。在这里，= 是指将 temp 指针所存储的地址赋给 node->next，因此，当前 node 节点的下一个节点就是 temp 指向的节点。
原问题2：
您的理解是正确的。在头插入函数中，当链表为空（即 *head == NULL）时，我们将 *head 指向 node，此时 head_one 的地址被更改为 node 的地址。之后，无论如何改变 node，我们只需要更新 *head 即可。实际上，在头插入函数中，我们将 *head 设置为新的头节点，这意味着我们已经将链表的头节点更新为新插入的节点。因此，当我们在函数内部修改 node 时，链表实际上已经更新了，而我们不需要再次改变 *head。
问题3：
指针变量的作用域（可访问性）取决于它们声明的位置。如果指针变量在函数内部声明，则只能在该函数内访问。如果指针变量在函数外部声明，则在整个文件中都可以访问。然而，要在其他函数中访问一个指针变量，您需要将该指针作为参数传递给其他函数，就像在头插入和尾插入函数中传递链表头指针一样。 isdkz 发表于 2023-4-10 23:52
原问题1：
是的，您的理解是正确的。node->next = temp 的意思是将当前 node 节点的下一个节点设置为 te ...
太感谢你！！！！！！！！！I LOVE YOU ! isdkz 发表于 2023-4-10 21:35
当然可以。让我们用一个详细的示例，分步骤解释头插入和尾插入的过程。
首先，我们将使用头插入法。我 ...
尾插入问题：
插入1：
node->value = value;node->value == 1
此时*head为NULL
*head = node; *head == 1
node->next = NULL; node->next == 1->NULL
插入2：
node->value = value;node->value == 2
此时*head不为NULL
temp = *head; temp == 1；
while(temp->next != NULL)
{
temp = temp->next;
}
循环结束后：temp->next == NULL 相当于1->NULL
temp->next = node; temp->next == 1->2
node->next = NULL; node->next == 2->NULL
插入3：
node->value = value;node->value == 3
此时*head不为NULL
temp = *head; temp == 1；
while(temp->next != NULL)
{
temp = temp->next;
}
循环结束后：temp->next == NULL 相当于1->NULL
temp->next = node; temp->next == 1->3
node->next = NULL; node->next == 3->NULL
我这样演算好像是有问题的是插入数据3的时候我演算这个出问题
因为（在插入数据1：*head = node; *head == 1）
因为（在插入数据2：temp = *head; temp == 1；）//此时*head为插入数据1中的值为1。
所以（在插入数据2：temp->next = node; temp->next == 1->2）
所以 此时temp和*head都为 1
然后（在插入数据3：temp = *head; temp == 1；）
最后在插入数据3中，temp和*head都为1 就出问题了。。。
所以我认为在输入数据3中temp节点里的那个值应该是，但是思来想去无法理解有点绕晕了 能给我解释以下吗？谢谢！（好像和之前请教你的地址问题有关是吗？）
a905448839 发表于 2023-4-11 00:55
尾插入问题：
插入1：
node->value = value;node->value == 1
在您的演算中，插入3时有一点问题。
插入1：
[*]node->value = 1
[*]*head 为 NULL
[*]*head = node; 此时 *head 指向 1
[*]node->next = NULL; 此时链表为：1->NULL
插入2：
[*]node->value = 2
[*]*head 不为 NULL
[*]temp = *head; 此时 temp 指向 1
[*]while 循环找到链表尾部，temp 指向 1
[*]temp->next = node; 此时链表变为：1->2
[*]node->next = NULL; 此时链表为：1->2->NULL
插入3：
[*]node->value = 3
[*]*head 不为 NULL
[*]temp = *head; 此时 temp 指向 1
[*]while 循环找到链表尾部，temp 指向 2（因为 2 是链表中的最后一个节点）
[*]temp->next = node; 此时链表变为：1->2->3
[*]node->next = NULL; 此时链表为：1->2->3->NULL
在插入3时，您需要在 while 循环中找到链表尾部，即找到最后一个节点。在插入3时，链表为：1->2->NULL，最后一个节点为2。
所以，当您在 while 循环中遍历链表时，temp 指针最终将指向节点2。然后，将新节点3连接到节点2，链表变为：1->2->3->NULL。
关键在于理解 while 循环的目的是找到链表尾部，而不是找到 NULL。这就是为什么在插入3时，temp 指针最终指向2，而不是1。 isdkz 发表于 2023-4-11 08:02
在您的演算中，插入3时有一点问题。
插入1：
此代码尾插入中，用的是循环找到最后一个节点，每次插入都要循环一次呢。有没有更省效率的方法呢?我记得小甲鱼有说过可以定义一个永远指向尾节点的指针，代码如何写呢？详细的逻辑思维能告知一下吗？谢谢！ a905448839 发表于 2023-4-11 21:30
此代码尾插入中，用的是循环找到最后一个节点，每次插入都要循环一次呢。有没有更省效率的方法呢?我记得 ...
当然可以优化尾插入的效率。通过定义一个永远指向尾节点的指针，可以将尾插入的时间复杂度降低为 O(1)。
以下是如何实现这一优化的详细逻辑思维和代码：
[*]定义一个尾节点指针 tail。
[*]每次插入新节点时，直接将新节点插入到 tail 后面。
[*]更新 tail 为新插入的节点。
以下是相应的 C 代码：
#include <stdio.h>
#include <stdlib.h>
struct Node {
int value;
struct Node *next;
};
void insert_tail(struct Node **head, struct Node **tail, int value) {
struct Node *node = (struct Node *) malloc(sizeof(struct Node));
node->value = value;
node->next = NULL;
if (*head == NULL) {
*head = node;
*tail = node;
} else {
(*tail)->next = node;
*tail = node;
}
}
void print_list(struct Node *head) {
while (head != NULL) {
printf("%d->", head->value);
head = head->next;
}
printf("NULL\n");
}
int main() {
struct Node *head = NULL;
struct Node *tail = NULL;
insert_tail(&head, &tail, 1);
insert_tail(&head, &tail, 2);
insert_tail(&head, &tail, 3);
insert_tail(&head, &tail, 4);
print_list(head);
return 0;
}
在这个代码示例中，我们定义了一个名为 tail 的指针，它总是指向链表的尾节点。
每次插入一个新节点时，我们直接将其插入到 tail 指向的节点后面，然后更新 tail 为新插入的节点。
这样，尾插入操作的时间复杂度就降低为 O(1) 了。 isdkz 发表于 2023-4-11 21:35
当然可以优化尾插入的效率。通过定义一个永远指向尾节点的指针，可以将尾插入的时间复杂度降低为 O(1)。
...
这个tail尾节点指针能在尾插入函数的代码块里定义和使用吗？不从it main函数里传入能实现吗？ a905448839 发表于 2023-4-12 00:35
这个tail尾节点指针能在尾插入函数的代码块里定义和使用吗？不从it main函数里传入能实现吗？
要在尾插入函数内部定义和使用 tail 尾节点指针，需要将其声明为静态变量。
这样，tail 的值在函数的多次调用之间会保持。请注意，这种方法不太适用于处理多个链表，因为所有链表将共享同一个 tail 指针。
然而，在处理单个链表的情况下，它可以很好地工作。
以下是修改后的代码：
#include <stdio.h>
#include <stdlib.h>
struct Node {
int value;
struct Node *next;
};
void insert_tail(struct Node **head, int value) {
struct Node *node = (struct Node *) malloc(sizeof(struct Node));
node->value = value;
node->next = NULL;
static struct Node *tail = NULL;
if (*head == NULL) {
*head = node;
tail = node;
} else {
tail->next = node;
tail = node;
}
}
void print_list(struct Node *head) {
while (head != NULL) {
printf("%d->", head->value);
head = head->next;
}
printf("NULL\n");
}
int main() {
struct Node *head = NULL;
insert_tail(&head, 1);
insert_tail(&head, 2);
insert_tail(&head, 3);
insert_tail(&head, 4);
print_list(head);
return 0;
}
在这个修改后的代码中，我们将 tail 声明为静态变量。这意味着它将在整个程序执行过程中一直存在，并且只在函数的第一次调用时被初始化。
这样，我们就可以在 insert_tail 函数内部定义和使用 tail 指针了。 isdkz 发表于 2023-4-10 21:35
当然可以。让我们用一个详细的示例，分步骤解释头插入和尾插入的过程。
首先，我们将使用头插入法。我 ...
chat GPD? 18227452746 发表于 2023-4-18 15:41
chat GPD?
不是，是chatgpt{:10_256:}
页:
[1]