c-对具有多个元素的链表进行排序

我有这个csv文件：

NAME, NUMBER, ADDRESS, EMAIL
Kevin, +62 812-xxx-xxx, Jln.Anggrek Merah 3, kevin@gmail.com
Adwi, +62 821-xxxx-xxxx, Jln.Ruhui Rahayu, adwi@gmail.com
Wasis, +62 813-xxxx-xxxx, Jln.Pramuka 6 25, wasis@gmail.com
Alief, +62 811-xxxx-xxx, Jln.Padat Karya, alief@gmail.com

这是我的代码：

#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("%sn", 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文件中每个人数据的链表后，我想按他们的名字排序，然后打印出来。但如果你编译我的代码，会导致分段错误。

在我的sort()函数中，我尝试更改每个人的node (next)。因为我认为，如果我只交换每个元素的值，node (next)仍然会指向和以前相同的人。所以我在想也许我只能换node (next)。

如果它只是对数组中的值进行排序，我就可以做到这一点。但链表对初学者来说很难。

你能帮我吗？如果你们有，也许可以给我写一些新代码并解释解决方案。谢谢！

当您想要创建一个链表时，您应该使用一个包含两种类型日期的结构Cell：第一种是您的数据本身(在您的情况下是Contact(，另一种是指向列表中下一个单元格(next(的指针。使用这种类型的实现可以使代码更加可读、模块化和可重用。

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("%sn", cursor->info.name);
cursor = cursor->next;
}
}

对于排序，我会在单元格之间交换信息(使用上面的实现(，因为这种方法使交换更容易理解，尤其是对于像Contact这样的数据类型(使用第三个变量交换不重要(。下面的版本使用选择排序算法(不是非常高效，但更容易(。

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;
}
}

与其传递双星指针(例如Contact **start(，我更喜欢单独的List结构。这可以[很容易]扩展为双链接列表。

此外，我总是将struct传递给带有指针的函数。传递值(就像创建列表时所做的那样(较慢。而且，在一般情况下，如果struct很大(例如，它有一个元素：int data[10000000];(，则会导致堆栈溢出

我很难理解你的排序逻辑。而且，对我来说，使用traverse->next->next似乎有问题。我无法准确说出你的排序算法是基于什么。我猜它是在尝试进行插入排序[但我很容易错了]。

我更熟悉的是在合并阶段从源列表中提取并附加到目标列表的链表的合并排序。这会很快(呃(，而且它能很好地适应链表。

但是，我并没有偏离代码那么远，而是从中调整了一些逻辑来创建一个选择排序[我认为]。

无论如何，这里是重构的代码：

#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;
typedef struct {
Contact *head;
} List;
void
create_linkedList(List *list, 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 = list->head;
list->head = new;
}
void
printList(List *list)
{
Contact *cursor = list->head;
printf("List:n");
while (cursor != NULL) {
printf("  %sn", cursor->name);
cursor = cursor->next;
}
}
void
sorting(List *list)
{
Contact *oldhead = list->head;
Contact *newhead = NULL;
Contact *newprev = NULL;
while (oldhead != NULL) {
// lowest element to be selected
Contact *bestcur = oldhead;
Contact *bestprev = NULL;
// find the lowest element in remaining list
Contact *travprev = NULL;
Contact *travcur = oldhead;
for (;  travcur != NULL;  travcur = travcur->next) {
if (strcasecmp(bestcur->name,travcur->name) > 0) {
bestcur = travcur;
bestprev = travprev;
}
travprev = travcur;
}
// remove selected element from old list
if (bestprev != NULL)
bestprev->next = bestcur->next;
else
oldhead = bestcur->next;
bestcur->next = NULL;
// append to new list
if (newprev != NULL)
newprev->next = bestcur;
else
newhead = bestcur;
newprev = bestcur;
}
list->head = newhead;
}
int
main(void)
{
FILE *file = fopen("contacts.csv", "r");
if (file == NULL)
return 1;
Contact person;
List *list = calloc(1,sizeof(*list));
// 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(list, &person);
}
printList(list);
// Swapped
sorting(list);
printList(list);
return 0;
}

相关内容

最新更新

热门标签：