按字母顺序排序 c 中的列表
Sort in alphabetical order a List in c
您好,我正在编写一个管理学生列表的程序,我正在使用一个列表,每个元素的描述如下:
struct student
{
char lastname[50];
char name[50];
char date_of_birth[50];
char height[50];
struct student *next;
};
struct student *root=0; //this is the root node
这是我向列表中添加元素的方式:
void add_element(struct student **root, char lastname[50], char name[50], char date_of_birth[50], char height[50])
{
if(*root == 0)
{
*root = malloc(sizeof(struct student));
strcpy((*root)->lastname,lastname);
strcpy( (*root)->name,name);
strcpy( (*root)->date_of_birth,date_of_birth);
strcpy( (*root)->height,height);
(*root)->next = 0;
}
else
{
add_element(&(*root)->next,lastname,name,date_of_birth,height);
}
}
我还写了 2 个函数,一个是从文件中读取,另一个是写入文件,文件包含所有学生,一切正常,但我需要一个函数来按字母顺序对所有元素进行排序lastname,我试着写了一个,但它不起作用,它一直崩溃。
我尝试了很多东西都没有用,这是一次尝试,但没有用:-(
请帮帮我
void sort(struct student *head)
{
struct student **current;
struct student *tmp;
for(current = &head ; *current !=NULL ; current = (*current)->next)
{
if((*current)->next == NULL)
{
break;
}
switch(strcmp((*current)->lastname,(*current)->next->lastname))
{
case 0:
{
printf("user not valid");
break;
}
case 1:
{
tmp = *current;
*current = (*current)->next;
(*current)->next = tmp;
break;
}
}
}
}
在包含评论中的评论以更正建议的源代码后,排序链表的算法缺少一些步骤。至少,要对链表进行排序,必须有两个循环。 struct student **current
访问的选择对于两个嵌套循环来说会很复杂。
这是使用优化后的 qsort()
函数的另一个强大的排序函数。
步骤 1 - 在显示函数之前,要对列表进行排序,应修改 root
指针。
First method, used for the add_element()
by sending the address of
the pointer.
void sort(struct student **root)
{
...
}
Second method, to return the modified root
.
struct student *sort(struct student *root)
{
...
return (root);
}
步骤 2 - 函数 sort()
使用 qsort()
快速排序函数。
该方法分配一个临时指针数组,以便对固定大小的元素进行排序。
- 第一个循环需要知道要排序的指针个数(小于2则不需要排序);
- 分配好
struct student *
的数组后,对链表的每一项循环填充数组;
- 使用自定义比较函数
node_compare()
调用qsort()
函数(见下一步);
- 通过强制
struct student *next
的值(第一个是 *root
,最后一个指向 NULL),用排序后的指针恢复链表。
- 释放
struct student *
的临时数组;
就这些了。
//
void sort(struct student **root)
{
struct student *tmp;
struct student **array;
int i,icount;
// number of nodes to be sorted
for(tmp = *root,icount = 0;tmp!=NULL;tmp = tmp->next,icount++);
if (icount<2) {
// no sort needed
return;
}
// allocate an array of pointers
array = (struct student **)malloc(icount*sizeof(struct student *));
// push linked-list into array of pointers
for(tmp = *root,icount = 0;tmp!=NULL;tmp = tmp->next,icount++) {
array[icount]=tmp;
}
// quicksort using node_compare() customized function
qsort(array, icount, sizeof(struct student *), node_compare);
// pop linked-list from array of pointers
*root = array[0];
(*root)->next = NULL;
for(tmp = *root,i = 1;i<icount;i++) {
tmp->next = array[i];
array[i]->next = NULL;
tmp = tmp->next;
}
// free the allocated array of pointer
free(array);
}
//
步骤 3 - qsort()
.
所需的比较函数 node_compare()
The function shall return a signed comparison as strcmp()
does.
int node_compare(const void * a, const void * b)
{
// restore node pointers
struct student *node_a = *((struct student **)a);
struct student *node_b = *((struct student **)b);
if (node_b==NULL) return (-1); // force 'node_a'
if (node_a==NULL) return (+1); // force 'node_b'
// use the strcmp() function
return (strcmp(node_a->lastname,node_b->lastname));
}
增强 - 因为 add_element()
使用不符合长链表的递归调用,这里是一个非常简单的非递归算法。
If the recursive algorithm limits the size to few-centuries of
elements, the proposed one has been tested with 100,000 elements (40Mb
linked-list), generated randomly and sorted.
void add_element(struct student **root, char lastname[50], char name[50], char date_of_birth[50], char height[50])
{
struct student **current;
for(current = root; *current !=NULL ; current = &((*current)->next));
*current = (struct student *)malloc(sizeof(struct student));
strcpy((*current)->lastname,lastname);
strcpy( (*current)->name,name);
strcpy( (*current)->date_of_birth,date_of_birth);
strcpy( (*current)->height,height);
(*current)->next = NULL;
}
您好,我正在编写一个管理学生列表的程序,我正在使用一个列表,每个元素的描述如下:
struct student
{
char lastname[50];
char name[50];
char date_of_birth[50];
char height[50];
struct student *next;
};
struct student *root=0; //this is the root node
这是我向列表中添加元素的方式:
void add_element(struct student **root, char lastname[50], char name[50], char date_of_birth[50], char height[50])
{
if(*root == 0)
{
*root = malloc(sizeof(struct student));
strcpy((*root)->lastname,lastname);
strcpy( (*root)->name,name);
strcpy( (*root)->date_of_birth,date_of_birth);
strcpy( (*root)->height,height);
(*root)->next = 0;
}
else
{
add_element(&(*root)->next,lastname,name,date_of_birth,height);
}
}
我还写了 2 个函数,一个是从文件中读取,另一个是写入文件,文件包含所有学生,一切正常,但我需要一个函数来按字母顺序对所有元素进行排序lastname,我试着写了一个,但它不起作用,它一直崩溃。
我尝试了很多东西都没有用,这是一次尝试,但没有用:-(
请帮帮我
void sort(struct student *head)
{
struct student **current;
struct student *tmp;
for(current = &head ; *current !=NULL ; current = (*current)->next)
{
if((*current)->next == NULL)
{
break;
}
switch(strcmp((*current)->lastname,(*current)->next->lastname))
{
case 0:
{
printf("user not valid");
break;
}
case 1:
{
tmp = *current;
*current = (*current)->next;
(*current)->next = tmp;
break;
}
}
}
}
在包含评论中的评论以更正建议的源代码后,排序链表的算法缺少一些步骤。至少,要对链表进行排序,必须有两个循环。 struct student **current
访问的选择对于两个嵌套循环来说会很复杂。
这是使用优化后的 qsort()
函数的另一个强大的排序函数。
步骤 1 - 在显示函数之前,要对列表进行排序,应修改 root
指针。
First method, used for the
add_element()
by sending the address of the pointer.
void sort(struct student **root)
{
...
}
Second method, to return the modified
root
.
struct student *sort(struct student *root)
{
...
return (root);
}
步骤 2 - 函数 sort()
使用 qsort()
快速排序函数。
该方法分配一个临时指针数组,以便对固定大小的元素进行排序。
- 第一个循环需要知道要排序的指针个数(小于2则不需要排序);
- 分配好
struct student *
的数组后,对链表的每一项循环填充数组; - 使用自定义比较函数
node_compare()
调用qsort()
函数(见下一步); - 通过强制
struct student *next
的值(第一个是*root
,最后一个指向 NULL),用排序后的指针恢复链表。 - 释放
struct student *
的临时数组;
就这些了。
//
void sort(struct student **root)
{
struct student *tmp;
struct student **array;
int i,icount;
// number of nodes to be sorted
for(tmp = *root,icount = 0;tmp!=NULL;tmp = tmp->next,icount++);
if (icount<2) {
// no sort needed
return;
}
// allocate an array of pointers
array = (struct student **)malloc(icount*sizeof(struct student *));
// push linked-list into array of pointers
for(tmp = *root,icount = 0;tmp!=NULL;tmp = tmp->next,icount++) {
array[icount]=tmp;
}
// quicksort using node_compare() customized function
qsort(array, icount, sizeof(struct student *), node_compare);
// pop linked-list from array of pointers
*root = array[0];
(*root)->next = NULL;
for(tmp = *root,i = 1;i<icount;i++) {
tmp->next = array[i];
array[i]->next = NULL;
tmp = tmp->next;
}
// free the allocated array of pointer
free(array);
}
//
步骤 3 - qsort()
.
node_compare()
The function shall return a signed comparison as
strcmp()
does.
int node_compare(const void * a, const void * b)
{
// restore node pointers
struct student *node_a = *((struct student **)a);
struct student *node_b = *((struct student **)b);
if (node_b==NULL) return (-1); // force 'node_a'
if (node_a==NULL) return (+1); // force 'node_b'
// use the strcmp() function
return (strcmp(node_a->lastname,node_b->lastname));
}
增强 - 因为 add_element()
使用不符合长链表的递归调用,这里是一个非常简单的非递归算法。
If the recursive algorithm limits the size to few-centuries of elements, the proposed one has been tested with 100,000 elements (40Mb linked-list), generated randomly and sorted.
void add_element(struct student **root, char lastname[50], char name[50], char date_of_birth[50], char height[50])
{
struct student **current;
for(current = root; *current !=NULL ; current = &((*current)->next));
*current = (struct student *)malloc(sizeof(struct student));
strcpy((*current)->lastname,lastname);
strcpy( (*current)->name,name);
strcpy( (*current)->date_of_birth,date_of_birth);
strcpy( (*current)->height,height);
(*current)->next = NULL;
}