我得到了一个代码来排序一个包含Opera类型的链接的链表(我们在法语中称之为maillons，对不起，我真的不知道它在英语中是怎么叫的)，这是它的结构的定义:
typedef struct opera_s {
char * titre; /* title */
date * date_creation;
char * ville_creation; /* city of creation */
individu * compositeur; /* composer*/
} opera;
typedef struct individu_s {
char * nom; /* family name */
char * prenom; /* first name*/
date * naissance; /* date of birth */
} individu;
typedef struct date_s {
unsigned int jour; /* day */
unsigned int mois; /* month */
unsigned int annee; /* year */
} date;
也定义了单个链接和列表
struct maillon_s{
opera * valeur; /* value of opera type */
struct maillon_s * suivant; /* the next link */
};
typedef struct maillon_s maillon;
struct liste_s{
struct maillon_s * debut; /* first link */
int taille; /* list size */
};
typedef struct liste_s liste;
，然后排序列表的代码是:
void sort_list_title (liste * l) {
maillon *p, *q;
liste * tmp=create_empty_list();
add_link_head_list(tmp,create_link()); /* a function that adds a link as head */
while(!test_empty_list(l)){
p=extract_link_from_head_list(l); /* function that extracts a link from the head of the list, thus reducing it and the extracted link's next will point towards NULL */
q=tmp->debut;
while((q->suivant!=NULL) && (strcmp(q->suivant->valeur->titre,p->valeur->titre)<0))
q=q->suivant;
p->suivant=q->suivant;
q->suivant=p;
tmp->taille++;
}
destroy_link(extract_link_from_head_list(tmp));
l->debut=tmp->debut;
l->taille=tmp->taille;
free(tmp);
}
我不明白为了排序这个链表所使用的策略，有人能给我解释一下吗(我必须理解老师给我们的这个特定代码)?我甚至不能得到算法，我很感激示范的例子，如果你有一个更简单的代码，我很高兴知道它，提前谢谢你
这是工作代码示例
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node* next;
};
void display(struct node* head)//function to print linked list
{
struct node* ptr = head;
while (ptr)
{
printf("%d ",ptr->data);
ptr = ptr->next;
}
}
struct node* newNode(int data)
{
struct node* newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void insertion_sort(struct node** head, struct node* newNode)//function to insert data in sorted position
{
//If linked list is empty
if (*head == NULL || (*head)->data >= newNode->data)
{
newNode->next = *head;
*head = newNode;
return;
}
//Locate the node before insertion
struct node* current = *head;
while (current->next != NULL && current->next->data < newNode->data)
current = current->next;
newNode->next = current->next;
current->next = newNode;
}
int main(void)//main method
{
int n,k;
printf("Enter the size of linked list :n");
scanf("%d",&n);
struct node* head = NULL;
//constructing linked list
for (int i = n-1; i >= 0; i--){
printf("nEnter data you want to insert: ");
scanf("%d",&k);
insertion_sort(&head, newNode(k));
}
printf("Sorted Linked list after insertion : ");
display(head);
return 0;
}
注释代码。在英语中，maillon被称为node。代码在列表tmp中创建一个临时列表tmp和一个临时头节点，然后每次从列表l中删除一个maillon，并将它们按排序顺序插入列表tmp，直到列表l清空。删除列表tmp中的临时头节点。Listldebut和taille设置为列出tmp的值。Listtmp被释放
void sort_list_title (liste * l) {
maillon *p, *q; /* declare p and q as pointers to maillon */
liste * tmp=create_empty_list(); /* create an empty list tmp */
add_link_head_list(tmp,create_link()); /* add a temp head node to list tmp */
while(!test_empty_list(l)){ /* while the orignal list is not empty */
p=extract_link_from_head_list(l); /* p = removed debut maillon from list l */
q=tmp->debut; /* q = ptr to temp head node in list tmp */
/* advance q until end of list or until q maillon is >= p maillion */
while((q->suivant!=NULL) && (strcmp(q->suivant->valeur->titre,p->valeur->titre)<0))
q=q->suivant;
/* insert p between q and q->suivant */
p->suivant=q->suivant; /* set p's suviant to q's suivant */
q->suivant=p; /* set q's suviant to p */
tmp->taille++; /* increment list l count */
}
destroy_link(extract_link_from_head_list(tmp)); /* remove | free head node from list tmp */
l->debut=tmp->debut; /* set list l debut to the sorted tmp debut */
l->taille=tmp->taille; /* set list l count to list tmp count */
free(tmp); /* free list tmp */
}