C中的插入排序链表
Insertion Sorted Linked List in C
所以对于我的 class 我需要用 C 编写一个链表，它在从文件中读取时添加或删除项目，并且在插入时按顺序放置它们插入排序。文件中的每一行都包含一个名称，后跟 a 或 d，表示是添加还是删除该名称。
我了解链表的概念，之前在Java中实现过。出于某种原因，我无法让它在 C 中工作。任何帮助将不胜感激。
第一个值现在已进入列表，但还有另一个问题，如下所述。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
char name[42];
struct node *next;
};
void insertNode(char name[42], struct node *head)
{
struct node *new = (struct node*)malloc(sizeof(struct node));
strcpy(new->name, name);
struct node *curr = head;
int finished = 0;
if(!curr)
{
head = new;
return;
}
while(curr->next != NULL) //This loop right here is not working
//it doesn't make it into the loop, curr somehow equals null
//not sure why this isn't working
{
if((strcmp(curr->name, new->name) < 0))
{
new->next = curr->next;
curr->next = new;
finished = 1;
break;
}
curr = curr->next;
}
if(finished = 0)
{
new->next = curr->next;
curr->next = new;
}
}
void removeNode(char name[42], struct node *head)
{
struct node *temp = (struct node*)malloc(sizeof(struct node));
strcpy(temp->name, name);
struct node *curr = head;
while(curr->next != NULL)
{
if(curr->next == temp)
{
curr->next = temp->next;
free(temp->name);
temp->next = NULL;
}
}
}
void FREE(struct node *head)
{
int i;
struct node *temp;
while(head != NULL)
{
temp = head;
head = head->next;
free(temp);
}
}
void printList(struct node *head)
{
struct node *curr = head;
printf("Linked list:\n");
while(curr != NULL)
{
printf("%s\n", curr->name);
curr = curr->next;
}
}
int main(void)
{
FILE *input = fopen("hw7.data", "r");
struct node *head = (struct node*)malloc(sizeof(struct node));
head->next = NULL;
strcpy(head->name, "");
char *tempText = NULL;
char *tempName = NULL;
char *tempOP = NULL;
size_t lineLen;
int i = 0;
getline(&tempText, &lineLen, input);
while(!feof(input))
{
tempName = strtok(tempText, " ");
tempOP = strtok(NULL, "\n");
if(i == 0)
{
strcpy(head->name, tempName);
i = 1;
}
if(tempOP[0] == 'a')
{
insertNode(tempName, head);
}
else
{
removeNode(tempName, head);
}
getline(&tempText, &lineLen, input);
}
printList(head);
fclose(input);
FREE(head);
return 0;
}
这是数据文件：
Beverly a
Kathy a
Radell a
Gary a
Chuck a
David a
kari a
Tom a
Tanya a
Scott a
Beverly d
Brenda d
Kathy a
Gary a
WenChen a
Chuck a
Mike a
Emanuel a
Linda a
Bernie a
Hassan a
Brian a
Gary d
Kathy d
Gary a
Eunjin a
Kathy a
Brenda a
Jun a
Peanut a
Travis a
这段代码中有很多错误，包括但不限于：
- 不正确的外参数处理（即它们不是外参数，但应该是）。
- 对从未直接
malloc 或 realloc 的数据调用 free
- 在 while 条件下错误地使用
feof。
- 指针移动存在多个问题。
- 需要比较的赋值。可能是错字，但很重要，none-the-less.
- 潜在的缓冲区溢出
重新编写其中每一个的代码，从基础开始。为避免缓冲区溢出您的结构 name 成员，只需使用动态分配。您已经使用链表取消了缓存；不妨确保它低于 6 英尺：
struct node
{
char *name; /* will use strdup() for allocation */
struct node *next;
};
继续，插入例程可以使用指向指针的指针遍历列表（并且 main 通过地址 向我们传递 head 指针 ）所以我们可以通过取消引用来修改它。这很关键，并且在您的代码中缺失：
void insertNode(char const name[], struct node **head)
{
printf("Adding: %s\n", name);
while (*head && strcmp((*head)->name, name) < 0)
head = &(*head)->next;
struct node *p = malloc(sizeof *p);
p->name = strdup(name);
p->next = *head;
*head = p;
}
当涉及到删除时，我们可以做同样的事情，这具有适当的头指针管理的额外优势，即使在链表中的单个节点的情况下，甚至 none全部：
void removeNode(char const name[], struct node **head)
{
int cmp = 0;
while (*head && (cmp = strcmp((*head)->name, name)) < 0)
head = &(*head)->next;
if (*head && (cmp == 0))
{
printf("Removing: %s\n", name);
struct node *tmp = *head;
*head = tmp->next;
free(tmp->name); // note: freeing what we strdup()'d
free(tmp);
}
else
{
printf("Not found: %s\n", name);
}
}
虽然这种情况不需要，但我总是建议使用相同的地址指针指向焦土freeList意识形态的指针机制。它确保您不会给调用者留下悬空指针，他们可能会愚蠢地尝试取消引用。
void freeList(struct node **head)
{
while (*head)
{
struct node *tmp = *head;
*head = tmp->next;
free(tmp->name);
free(tmp);
}
}
在打印列表时，用 const 指针遍历它是微不足道的：
void printList(struct node const *head)
{
printf("Linked list:\n");
for (; head; head = head->next)
printf("%s\n", head->name);
}
最后，你的程序的核心，main。将 while 循环固定为仅在实际读取行内容时继续，并正确地从 getline 中释放最终结果而不是让它泄漏（这里无关紧要，因为程序很快就会退出，但是好的做法） ，我们得到：
int main()
{
FILE *input = fopen("hw7.data", "r");
if (!input)
{
perror("Failed to open file: ");
return EXIT_FAILURE;
}
struct node *head = NULL;
char *text = NULL;
size_t lineLen = 0;
while(getline(&text, &lineLen, input) > 0)
{
char *name = strtok(text, " ");
char *op = strtok(NULL, "\n");
if(*op == 'a')
{
insertNode(name, &head);
}
else if (*op == 'd')
{
removeNode(name, &head);
}
}
fclose(input);
free(text);
printList(head);
freeList(&head);
return EXIT_SUCCESS;
}
输出
以下是您输入的输出，我在 insertNode 和 removeNode 中添加了检测，让您知道发生了什么：
Adding: Beverly
Adding: Kathy
Adding: Radell
Adding: Gary
Adding: Chuck
Adding: David
Adding: kari
Adding: Tom
Adding: Tanya
Adding: Scott
Removing: Beverly
Not found: Brenda
Adding: Kathy
Adding: Gary
Adding: WenChen
Adding: Chuck
Adding: Mike
Adding: Emanuel
Adding: Linda
Adding: Bernie
Adding: Hassan
Adding: Brian
Removing: Gary
Removing: Kathy
Adding: Gary
Adding: Eunjin
Adding: Kathy
Adding: Brenda
Adding: Jun
Adding: Peanut
Adding: Travis
Linked list:
Bernie
Brenda
Brian
Chuck
Chuck
David
Emanuel
Eunjin
Gary
Gary
Hassan
Jun
Kathy
Kathy
Linda
Mike
Peanut
Radell
Scott
Tanya
Tom
Travis
WenChen
kari
总结
有很多错误。我解决了上面我能找到的所有内容，并希望提供一些您现在和将来可以使用的链表管理的具体示例。
我强烈建议您在调试器中运行此代码并非常密切注意变量的变化。载入您的观察列表，并在您逐步完成输入项目时查看每一行的作用。通过调试正确运行的代码来学习可能是一种很好的学习技巧，值得花半个小时在上面。
所以对于我的 class 我需要用 C 编写一个链表，它在从文件中读取时添加或删除项目，并且在插入时按顺序放置它们插入排序。文件中的每一行都包含一个名称，后跟 a 或 d，表示是添加还是删除该名称。
我了解链表的概念，之前在Java中实现过。出于某种原因，我无法让它在 C 中工作。任何帮助将不胜感激。
第一个值现在已进入列表，但还有另一个问题，如下所述。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
char name[42];
struct node *next;
};
void insertNode(char name[42], struct node *head)
{
struct node *new = (struct node*)malloc(sizeof(struct node));
strcpy(new->name, name);
struct node *curr = head;
int finished = 0;
if(!curr)
{
head = new;
return;
}
while(curr->next != NULL) //This loop right here is not working
//it doesn't make it into the loop, curr somehow equals null
//not sure why this isn't working
{
if((strcmp(curr->name, new->name) < 0))
{
new->next = curr->next;
curr->next = new;
finished = 1;
break;
}
curr = curr->next;
}
if(finished = 0)
{
new->next = curr->next;
curr->next = new;
}
}
void removeNode(char name[42], struct node *head)
{
struct node *temp = (struct node*)malloc(sizeof(struct node));
strcpy(temp->name, name);
struct node *curr = head;
while(curr->next != NULL)
{
if(curr->next == temp)
{
curr->next = temp->next;
free(temp->name);
temp->next = NULL;
}
}
}
void FREE(struct node *head)
{
int i;
struct node *temp;
while(head != NULL)
{
temp = head;
head = head->next;
free(temp);
}
}
void printList(struct node *head)
{
struct node *curr = head;
printf("Linked list:\n");
while(curr != NULL)
{
printf("%s\n", curr->name);
curr = curr->next;
}
}
int main(void)
{
FILE *input = fopen("hw7.data", "r");
struct node *head = (struct node*)malloc(sizeof(struct node));
head->next = NULL;
strcpy(head->name, "");
char *tempText = NULL;
char *tempName = NULL;
char *tempOP = NULL;
size_t lineLen;
int i = 0;
getline(&tempText, &lineLen, input);
while(!feof(input))
{
tempName = strtok(tempText, " ");
tempOP = strtok(NULL, "\n");
if(i == 0)
{
strcpy(head->name, tempName);
i = 1;
}
if(tempOP[0] == 'a')
{
insertNode(tempName, head);
}
else
{
removeNode(tempName, head);
}
getline(&tempText, &lineLen, input);
}
printList(head);
fclose(input);
FREE(head);
return 0;
}
这是数据文件：
Beverly a
Kathy a
Radell a
Gary a
Chuck a
David a
kari a
Tom a
Tanya a
Scott a
Beverly d
Brenda d
Kathy a
Gary a
WenChen a
Chuck a
Mike a
Emanuel a
Linda a
Bernie a
Hassan a
Brian a
Gary d
Kathy d
Gary a
Eunjin a
Kathy a
Brenda a
Jun a
Peanut a
Travis a
这段代码中有很多错误，包括但不限于：
- 不正确的外参数处理（即它们不是外参数，但应该是）。
- 对从未直接
malloc或realloc的数据调用free - 在 while 条件下错误地使用
feof。 - 指针移动存在多个问题。
- 需要比较的赋值。可能是错字，但很重要，none-the-less.
- 潜在的缓冲区溢出
重新编写其中每一个的代码，从基础开始。为避免缓冲区溢出您的结构 name 成员，只需使用动态分配。您已经使用链表取消了缓存；不妨确保它低于 6 英尺：
struct node
{
char *name; /* will use strdup() for allocation */
struct node *next;
};
继续，插入例程可以使用指向指针的指针遍历列表（并且 main 通过地址 向我们传递 head 指针 ）所以我们可以通过取消引用来修改它。这很关键，并且在您的代码中缺失：
void insertNode(char const name[], struct node **head)
{
printf("Adding: %s\n", name);
while (*head && strcmp((*head)->name, name) < 0)
head = &(*head)->next;
struct node *p = malloc(sizeof *p);
p->name = strdup(name);
p->next = *head;
*head = p;
}
当涉及到删除时，我们可以做同样的事情，这具有适当的头指针管理的额外优势，即使在链表中的单个节点的情况下，甚至 none全部：
void removeNode(char const name[], struct node **head)
{
int cmp = 0;
while (*head && (cmp = strcmp((*head)->name, name)) < 0)
head = &(*head)->next;
if (*head && (cmp == 0))
{
printf("Removing: %s\n", name);
struct node *tmp = *head;
*head = tmp->next;
free(tmp->name); // note: freeing what we strdup()'d
free(tmp);
}
else
{
printf("Not found: %s\n", name);
}
}
虽然这种情况不需要，但我总是建议使用相同的地址指针指向焦土freeList意识形态的指针机制。它确保您不会给调用者留下悬空指针，他们可能会愚蠢地尝试取消引用。
void freeList(struct node **head)
{
while (*head)
{
struct node *tmp = *head;
*head = tmp->next;
free(tmp->name);
free(tmp);
}
}
在打印列表时，用 const 指针遍历它是微不足道的：
void printList(struct node const *head)
{
printf("Linked list:\n");
for (; head; head = head->next)
printf("%s\n", head->name);
}
最后，你的程序的核心，main。将 while 循环固定为仅在实际读取行内容时继续，并正确地从 getline 中释放最终结果而不是让它泄漏（这里无关紧要，因为程序很快就会退出，但是好的做法） ，我们得到：
int main()
{
FILE *input = fopen("hw7.data", "r");
if (!input)
{
perror("Failed to open file: ");
return EXIT_FAILURE;
}
struct node *head = NULL;
char *text = NULL;
size_t lineLen = 0;
while(getline(&text, &lineLen, input) > 0)
{
char *name = strtok(text, " ");
char *op = strtok(NULL, "\n");
if(*op == 'a')
{
insertNode(name, &head);
}
else if (*op == 'd')
{
removeNode(name, &head);
}
}
fclose(input);
free(text);
printList(head);
freeList(&head);
return EXIT_SUCCESS;
}
输出
以下是您输入的输出，我在 insertNode 和 removeNode 中添加了检测，让您知道发生了什么：
Adding: Beverly
Adding: Kathy
Adding: Radell
Adding: Gary
Adding: Chuck
Adding: David
Adding: kari
Adding: Tom
Adding: Tanya
Adding: Scott
Removing: Beverly
Not found: Brenda
Adding: Kathy
Adding: Gary
Adding: WenChen
Adding: Chuck
Adding: Mike
Adding: Emanuel
Adding: Linda
Adding: Bernie
Adding: Hassan
Adding: Brian
Removing: Gary
Removing: Kathy
Adding: Gary
Adding: Eunjin
Adding: Kathy
Adding: Brenda
Adding: Jun
Adding: Peanut
Adding: Travis
Linked list:
Bernie
Brenda
Brian
Chuck
Chuck
David
Emanuel
Eunjin
Gary
Gary
Hassan
Jun
Kathy
Kathy
Linda
Mike
Peanut
Radell
Scott
Tanya
Tom
Travis
WenChen
kari
总结
有很多错误。我解决了上面我能找到的所有内容，并希望提供一些您现在和将来可以使用的链表管理的具体示例。
我强烈建议您在调试器中运行此代码并非常密切注意变量的变化。载入您的观察列表，并在您逐步完成输入项目时查看每一行的作用。通过调试正确运行的代码来学习可能是一种很好的学习技巧，值得花半个小时在上面。