我编写了以下程序,以地址格式存储来自文件的输入,并按存储在节点中的城市名称的字母顺序对链接列表进行排序。输入示例如下:
Titus \n
Kollman \n
1522 Foggy Grove Loop \n
Wildcat NC 27507 \n
(252) 644-5477 \n
...ETC
我的代码当前正确地创建了所有条目的未排序链接列表,并且我编写了排序功能以按字母顺序对列表进行排序。当我尝试对列表进行排序时,我的代码一直连续运行而没有输出(卡住),并且我的排序算法找不到任何错误。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* make node structure to store the data in */
struct entry {
char fname[64];
char lname[64];
char city[64];
char address[64];
char cityandstate[64];
char numb[64];
struct entry* next;
};
/* function to add entry that will be used in sort*/
void addEntryForSort(struct entry* list, struct entry* x){
struct entry* newNode = (struct entry*) malloc(sizeof(struct entry));
memcpy(newNode,x,sizeof(struct entry));
newNode->next = NULL;
while (list->next != NULL){
list = list->next;
}
list->next = newNode;
}
/*function to find the minimum (alpha)of a linked list */
struct entry* findMin(struct entry* begin){
struct entry* curr = begin;
struct entry* min = curr;
curr = curr->next;
while (curr != NULL){
if (strcmp(curr->city,min->city) < 0){
min = curr;
}
else if (strcmp(curr->city,min->city))
curr = curr->next;
}
return min;
}
/*sort function (attempt)*/
struct entry* sort(struct entry* top){
struct entry* sorted = (struct entry*) malloc(sizeof(struct entry));
struct entry* min = findMin(top);
struct entry* curr = top;
while (curr->next != NULL){
if (top == min){
addEntryForSort(sorted,min);
top = top->next;
min = findMin(top);
curr = top;
}
if (curr->next == min){
addEntryForSort(sorted,min);
curr->next = curr->next->next;
min = findMin(top);
curr = top;
}
else {
curr = curr->next;
}
}
addEntryForSort(sorted,top);
addEntryForSort(sorted,curr);
return sorted;
}
int main() {
struct entry* head = (struct entry*) malloc(sizeof(struct entry));
char x[64];
fgets(x,64,stdin);
strcpy(head->fname,x);
strtok(head->fname,"\n");
fgets(x,64,stdin);
strcpy(head->lname,x);
strtok(head->lname,"\n");
fgets(x,64,stdin);
strcpy(head->address,x);
strtok(head->address,"\n");
fgets(x,64,stdin);
strcpy(head->cityandstate,x);
strtok(head->cityandstate,"\n");
strncpy(head->city,head->cityandstate,strlen(head->cityandstate)-10);
fgets(x,64,stdin);
strcpy(head->numb,x);
strtok(head->numb,"\n");
fgets(x,64,stdin);
int line = 7;
struct entry* curr = (struct entry*) malloc(sizeof(struct entry));
struct entry* prev = head;
head->next = curr;
while (fgets(x,64,stdin) != NULL) {
switch (line % 6){
case 1:
strcpy(curr->fname,x);
strtok(curr->fname,"\n");
break;
case 2:
strcpy(curr->lname,x);
strtok(curr->lname,"\n");
break;
case 3:
strcpy(curr->address,x);
strtok(curr->address,"\n");
break;
case 4:
strcpy(curr->cityandstate,x);
strtok(curr->cityandstate,"\n");
strncpy(curr->city,curr->cityandstate,strlen(curr->cityandstate)-10);
if (strcmp(curr->city,"Old Roach MO 6") == 0){
strcpy(curr->city,"Old Roach");
}
break;
case 5:
strcpy(curr->numb,x);
strtok(curr->numb,"\n");
break;
case 0:
curr->next = (struct entry*) malloc(sizeof(struct entry));
prev = curr;
curr = curr->next;
break;
}
line++;
}
curr=sort(head);
while (curr!= NULL){
printf("%s %s %s\n",curr->fname,curr->lname,curr->city);
curr = curr->next;
}
}
这段代码有很多问题。
首先,您永远不要初始化您的结构,也不应该使用malloc进行构造,因此该next
成员也不能为null,从而使以下所有代码均失败。您应该写:
struct entry* head = (struct entry*) malloc(sizeof(struct entry));
head->next = NULL; /* ensure next is correctly initialized */
接下来:
struct entry* curr = (struct entry*) malloc(sizeof(struct entry));
curr->next = NULL; /* ensure next is correctly initialized */
您使用strncpy初始化city
字段。但是strncpy不会添加终止null,因此您的字段不会终止。您应该写:
strncpy(curr->city,curr->cityandstate,strlen(curr->cityandstate)-10);
curr->city[strlen(curr->cityandstate)-10] = '\0';
(与head
第一笔记录相同)。
在中findMin
,如果两个记录比较相等,则由于不调用,因此将停留在该位置curr = curr->next
。确实应该是:
/*function to find the maximum (alpha)of a linked list */
struct entry* findMax(struct entry* curr){
struct entry* min = curr;
while (curr != NULL){
if (strcmp(curr->city,min->city) > 0){
min = curr;
}
curr = curr->next;
}
return min;
}
我得到的是最大值,而不是最小值,因为用简单的冒泡排序对单链接列表进行排序,最简单的方法是将其排序到位,将最大的元素从列表中取出,然后将其放在结果列表的第一位。此外,这避免分配新的结构,因为如果您不想泄漏内存,则必须释放每个分配的块。该sort
功能可能变为:
/*sort function (attempt)*/
struct entry* sort(struct entry* top){
struct entry* sorted = NULL;
while (top != NULL) {
struct entry* max = findMax(top);
if (max == top) { /* if max is first, simply increment top */
top = top->next;
}
else { /* else make prev->next = max->next to remove max from the list */
struct entry *curr = top;
while (curr->next != min) curr = curr->next;
curr->next = min->next;
}
/* and put current max in first place of the sorted list */
max->next = sorted;
sorted = max;
}
return sorted;
}
最后,您应该通过在main的末尾添加所有已分配的内存块来释放它们:
/* free all elements of the linked list */
while(head != NULL) {
curr = head->next;
free(head);
head = curr;
}
return 0; /* never return random value to environment */
但是,如果您想进行认真的编程,则还应该:
fgets
不应返回NULL,缓冲区应具有\n
最后一个字符本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句