对具有多个元素的链表进行排序 [英] Sorting linked list with multiple elements

问题描述

我有这个csv文件:

NAME, NUMBER, ADDRESS, EMAIL
Kevin, +62 812-xxx-xxx, Jln.Anggrek Merah 3, [e-mail]
Adwi, +62 821-xxxx-xxxx, Jln.Ruhui Rahayu, [e-mail]
Wasis, +62 813-xxxx-xxxx, Jln.Pramuka 6 25, [e-mail]
Alief, +62 811-xxxx-xxx, Jln.Padat Karya, [e-mail]

这是我的代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 50

typedef struct Contact
{
    char name[MAX];
    char number[MAX];
    char address[MAX];
    char email[MAX];
    struct Contact *next;
} 
Contact;

void create_linkedList(Contact **start, Contact p)
{
    Contact *new = malloc(sizeof(Contact));
    strcpy(new->name, p.name);
    strcpy(new->number, p.number);
    strcpy(new->address, p.address);
    strcpy(new->email, p.email);

    new->next = *start;
    *start = new;
}

void printList(Contact *start)
{
    Contact *cursor = start;
    while (cursor != NULL)
    {
        printf("%s\n", cursor->name);
        cursor = cursor->next;
    }
}

void sorting(Contact *start)
{
    Contact *cursor = start, *traverse = NULL;
    Contact *tmp, *tmp_next;
        
    while (cursor != NULL)
    {
        traverse = cursor;

        while (traverse->next != NULL)
        {
            if (strcasecmp(traverse->name, traverse->next->name) > 0)
            {
                tmp = traverse;
                tmp_next = traverse->next->next;
    
                traverse->next = tmp;

                traverse->next->next = tmp_next;
            }
            traverse = traverse->next;
        }
        printf("Prepare!\n");
        cursor = cursor->next;
    }
}

int main(void)
{
    FILE *file = fopen("contacts.csv", "r");
    if (file == NULL)
        return 1;

    Contact person;
    Contact *start = NULL;

    // Loop inside csv file til' the end of file
    while(fscanf(file, "%[^,], %[^,], %[^,], %[^\n] ", person.name, person.number, person.address, person.email) == 4)
    {   
        # Skip header file from csv
        if (strcmp("NAME", person.name) == 0) 
            continue;
        
        create_linkedList(&start, person);
    }    

    printList(start);

    // Swapped
    sorting(start);

    printList(start);

    return 0;
}

因此，在我成功创建了一个链接列表，该列表连接了我的csv文件中的每个人数据之后，我想按其名称对它进行排序，然后打印出来.但是，如果编译我的代码，则会导致分段错误.

So, after i successfully created a linked list that connect each person data in my csv file, i want to sort it by their name and then print it. But if you compile my code, it causes segmentation fault.

在我的 sort()函数中，我尝试更改每个人的 node(next).因为我认为如果只交换每个元素的值，节点(下一个)仍将指向与以前相同的人.所以我在想，也许我只能交换 node(next).

In my sort() function i try to change the node (next) of each person. Because i think if i only swap the value of each element, the node (next) will still point same person as before. So i was thinking maybe i can only swap the node (next).

如果仅对数组中的值进行排序，我可以这样做.但是链表对于初学者来说很难.

I can do it if it's only sorting value in an array. But linked list it's difficult for me as beginner.

可以帮我吗?如果有的话，也许给我写一些新代码并解释解决方案.谢谢！

Can you help me, please? Maybe write me some new code and explain the solution, if you guys have it. Thanks!

推荐答案

要创建链接列表时，应使用包含两种日期类型的struct Cell:第一种是数据本身(在您的情况下为Contact))另一个是指向列表中下一个单元格的指针(下一个).使用这种类型的实现，您可以使代码更具可读性，模块化和可重用性.

When you want to create a linked list, you should use a struct Cell that contains two types of date: the first is your data itself (Contact in your case) the other is a pointer to the next cell in the list (next). Using this type of implementation you make your code more readable, modular and reusable.

typedef struct Contact
{
   char name[MAX];
   char number[MAX];
   char address[MAX];
   char email[MAX];
   struct Contact *next;
}
Contact;

typedef struct ContactCell {
   Contact info;
   struct ContactCell* next;
}
ContactCell;
typedef ContactCell* ContactList;

使用上面的功能实现

void addContactToList(ContactList start, Contact p)
{
   ContactCell* aux = malloc(sizeof(ContactCell));
   aux->info = p;

   aux->next = start;
   start = aux;
}

void printList(ContactList start)
{
   ContactList cursor = start;
   while (cursor != NULL)
   {
    printf("%s\n", cursor->info.name);
    cursor = cursor->next;
   }
}

对于排序，我会在单元格之间交换 info (使用上面的实现)，因为这种方法使交换更容易理解，尤其是对于诸如Contact之类的数据类型(不重要)使用第三个变量进行交换).以下版本使用选择排序算法(效率不高，但更容易).

For the sorting I would have swapped the info between the cell (using the implementation above), because this method makes the swapped easier to understand especially for a type of data like Contact (not weighty to be swapped using a third variable). The following version uses selection sort algorithm (not super efficient, but easier).

void sorting(ContactList start)
{

  for (ContactList i= start; i!=NULL; i = i->next)
  {
     ContactList current_min = i;

     for (ContactList j=i->next ;j!=NULL; j = j->next)
        if (strcasecmp(current_min->info.name,j->info.name) > 0)
           current_min = j;

     //swap using a Contact aux variable
     Contact tmp = i->info;
     i->info = current_min->info;
     current_min->info = tmp;
  }

}

这篇关于对具有多个元素的链表进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！