2015-11-24 106 views
1

该程序应该创建一个排序列表并按照姓名排序每个用户。我似乎无法弄清楚如何正确排序名称。C程序排序的链接列表

我只有append_to_list函数的问题,其余的功能工作正常。

当我第一次开始输入名称:

user ID: Last Name: First Name: 
3    Alex   Alex 
2    Jones   Alex 
1    andrew  john 

,直到我进入应该排序其间两个名字 ,当我输入名字安德鲁的名称为其分类精细,亚历克斯出现这种情况。

user ID: Last Name: First Name: 
4    Andrew  Alex 
3    Alex   Alex 
2    Jones   Alex 
1    andrew  john 

但安德鲁,亚历克斯应该是用户2和3


#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include "user.h" 
#include "readline.h" 

// function append_to_list takes user input from user, id, name and puts it  to the end of the list 
// as well as sorts each name alphabetically 
struct user *append_to_list(struct user *family) 
{ 
    struct user *cur, *prev, *new_node; 

    // generate memory 
    new_node = malloc(sizeof(struct user)); 

    if (new_node == NULL) { 
     printf("malloc failed in append\n"); 
     return family; 
    } 

    printf("Enter user ID: \n"); 
    scanf("%d", &new_node->number); 
    printf("Enter user last name: \n"); 
    read_line(new_node->last_name,NAME_LEN); 
    printf("Enter user first name: \n"); 
    read_line(new_node->first_name,NAME_LEN); 

    for(cur=family; cur != NULL; cur = cur->next) { 
     if (new_node->number == cur->number) { 
       printf("user already exists: %s, %s\n",new_node->first_name,  new_node->last_name); 
       free(new_node); 
       return family; 
     } 
    }  
    for (cur=family, prev = NULL; cur != NULL 
     && (strcmp(new_node->first_name,cur->first_name) < 0) 
     && (strcmp(new_node->last_name,cur->last_name) < 0); 
      prev = cur, cur = cur->next) { 

     if((strcmp(new_node->last_name,cur->last_name) < 0)) break; 

     if((strcmp(new_node->first_name,cur->first_name) == 0)) 

     if((strcmp(new_node->first_name,cur->first_name) < 0)) break; 
     ; 
     } 
     // use strcmp == 0 to see if name already exists 
     if (cur != NULL && (strcmp(new_node->first_name,cur->first_name) == 0) 
      && (strcmp(new_node->last_name,cur->last_name)) == 0) 
     { 
       printf("user already exists: %s, %s\n",new_node->first_name, new_node->last_name); 
       free(new_node); 
       return family; 
     } 

    // append the linkedlist to the end 
    new_node->next = cur; 
    // check to see if the node is empty 
    if (prev == NULL) { 
     return new_node; 
    } else { 
     prev->next = new_node->next; 
     return family; 
    } 
} 
// function delete_from_list removes a user from the family 
struct user* delete_from_list(struct user *family) 
{ 
    struct user *prev, *cur; 
    int id; 
    int not_found = 0; 
    printf("Enter user ID: \n"); 
    scanf("%d", &id); 

    for (cur = family, prev = NULL; cur != NULL; prev = cur, cur = cur->next) { 
     if (id == cur->number) { 
       // if only one user on family 
      if (prev == NULL) { 
       family = cur->next; 
      // if user is in the middle of family 
      // connects prev node to cur node 
      } else { 
       prev->next = cur->next; 
      } 
      printf("user deleted: %s ,%s\n",cur->first_name, cur->last_name); 
      free(cur); 
     } 
     else 
      not_found = 1; 
    } 
    if (not_found == 1) { 
     printf("user not found\n"); 
    } 
    return family; 
} 
// function find_user searches the family by ID and matches it with the users name 
void find_user(struct user *family) 
{ 
    struct user *p = family; 
    int id; 
    int count = 0; 
printf("Enter user ID: \n"); 
scanf("%d", &id); 

    // compares the family with the user entered ID 
    // if the ID is the same count set to 1 
    if (p != NULL) { 
     for (p = family; p != NULL; p = p->next) { 
      if (id == p->number) { 
       count = 1; 
       break; 
      } 
     } 
    } 
    // if count is 1 we know the function found that specific user 
    if (count == 1) { 
     printf("user found: %s, %s\n", p->last_name, p->first_name); 
    } else { 
     printf("user not found"); 
    } 
} 

// function printList prints the entire family 
void printList(struct user *family) 
{ 
    struct user *p; 
    printf("user ID:\tLast Name:\tFirst Name:\n"); 
    for (p = family; p != NULL; p = p->next) { 
     printf("%d\t\t%s\t\t%s\n", p->number, p->last_name, p->first_name); 
    } 

} 

// function clearList clears the entired linked list 
void clearList(struct user *family) 
{ 
    struct user *p; 
    while (family != NULL) { 
     p = family; 
     family = family->next; 
     if (p != NULL) { 
      free(p); 
     } 
    } 
} 
+0

为什么在循环终止条件和'append_to_list()'循环的主体中都有名称比较? –

+0

在任何情况下,我认为终止条件和循环体中的比较都是*错误。至少,在两个地方似乎都有相同姓氏的情况被错误地处理。 –

回答

0

之间我认为这是一个更好的主意重叠表的比较运营商,然后那种后您的一些列表存在的算法。

1

的问题是你比较节点的方式:

for (cur=family, prev = NULL; cur != NULL 
    && (strcmp(new_node->first_name,cur->first_name) < 0) 
    && (strcmp(new_node->last_name,cur->last_name) < 0); 
     prev = cur, cur = cur->next) { ... } 

你应该跳过有一个较小的家庭或(同一家族名称和较小的名字)节点。修正这样的比较:

for (cur=family, prev = NULL; 
    cur != NULL 
    && ((strcmp(new_node->first_name, cur->first_name) < 0) 
    || ((strcmp(new_node->first_name, cur->first_name) == 0) 
    && (strcmp(new_node->last_name,cur->last_name) < 0))); 
    prev = cur, cur = cur->next) { ... } 

并简化后面的代码。你其实不需要任何代码。循环将在插入点停止。只要检查是否存在相同的姓氏和名字(但如果有2约翰呢?),并在prevcur之间插入,或者在family之间插入,如果prevNULL

for循环看起来很丑陋:很难阅读,很容易出错。编写一个单独的比较函数,该函数需要2个节点,并根据电话簿顺序返回-1, 0, +1。您将使用append_to_listdelete_from_list这个函数,编写更少的代码,更具可读性和更一致。

+0

您提到的比较函数在某些语言中有时称为'太空船'运算符<=>。 – ChuckCottrill

+0

@ChuckCottrill:飞船运营商来自Perl。我不确定我后悔没有在C ...'<=>'会在C中作为2个左值之间的交换运算符更有用。 – chqrlie

+0

是的,perl(numerics),ruby(http://stackoverflow.com/questions/26581619/rubys-operator-and-sort-method),php,python(spelled cmp)和ocaml(spelled compare)。 – ChuckCottrill

0

您有问题,在这个循环条件:

for (cur=family, prev = NULL; 
     cur != NULL && (strcmp(new_node->first_name,cur->first_name) < 0) 
        && (strcmp(new_node->last_name,cur->last_name) < 0); 
       prev = cur, cur = cur->next) 

循环将不会执行:

(cur=family, family exist) 
cur != NULL -> True 
(Alex == Alex) 
((strcmp(new_node->first_name,cur->first_name) -> 0) < 0 -> False 
(Andrew > Alex) 
((strcmp(new_node->last_name,cur->last_name) -> 1) < 0 -> False 
True && False && False -> False 

结果,你会在开始添加新的记录。

而且在循环中,您有一个坏的 '如果' 的代码:

if((strcmp(new_node->first_name,cur->first_name) == 0)) 

if((strcmp(new_node->first_name,cur->first_name) < 0)) break; 
; 

Doc. strcmp

提示:有关删除无用的代码。 欢呼!