©2020-2024 ioDraw All rights reserved
C When using linked list , Sometimes the data in the linked list will be sorted . The following describes the sorting methods available when using linked lists , Bubble sort and selection sort .
This linked list sorting only sorts the data in the linked list , If you want to sort the entire structure , That is to use the data order to adjust the information in the node , Nodes need to be exchanged , But this method is different , Readers are expected to know .
Please refer to the complete test code below for the test sorting code .
Programming environment ：Visual C++ 6.0.
<> Bubble sorting
NODE* bubblesort(NODE* Head) { NODE *pfirst=NULL,*psecond=NULL,*pend=NULL;
pfirst=Head; psecond=Head; int temp; while(pfirst != pend) // External circulation { //pfirst !=
pend Very interesting while(pfirst->next != pend)// Internal circulation { if(pfirst->date > pfirst->next->
date) { temp=pfirst->date; pfirst->date=pfirst->next->date; pfirst->next->date=
temp; } pfirst=pfirst->next; } pend=pfirst;// Reduce the last scheduled cycle pfirst=Head; } return
Head; }
<> Select sort
/* Selection and sorting of linked list */ NODE* selectsort(NODE* head) { NODE *pfirst=NULL,*psecond=NULL,*
pend=NULL; pfirst=head; psecond=head; int temp; while(pfirst != pend) // External circulation {
while(pfirst->next != pend)// Internal circulation { if(psecond->date > pfirst->next->date) { temp
=psecond->date; psecond->date=pfirst->next->date; pfirst->next->date=temp; }
pfirst=pfirst->next; } psecond=psecond->next; pfirst=psecond; } return head; }
<> Test code
/* * Linked list sorting Writen by YU */ #include<stdio.h> #include<stdlib.h> /* Result output view */ void
endscan() { printf("\n Click enter to continue ..."); fflush(stdin); getchar(); } /* structural morphology */ struct
node{ int date; struct node *next; }; typedef struct node NODE; // hold struct node
Defined as NODE int count = 0; /* Create a linked list and enter data */ NODE* creat() { NODE *pHead=NULL,*pNew,*
pEnd; printf(" input data , When input 0 Stop when \n"); pNew=(NODE*)malloc(sizeof(NODE)); scanf("%d",&
pNew->date); while(pNew->date != 0) { count++; if(count == 1) // If head node { pNew->
next= NULL; pEnd = pNew; pHead = pNew; } else // If not the head node { pNew->next=NULL; pEnd
->next=pNew; pEnd=pNew; } pNew=(NODE*)malloc(sizeof(NODE)); scanf("%d",&pNew->
date); } free(pNew); return pHead; } /* Output linked list */ void print(NODE* Head) { NODE* p=
Head; while(p!=NULL) { printf("%d ",p->date); p=p->next; } } /* Bubble sorting of linked lists */ NODE*
bubblesort(NODE* Head) { NODE *pfirst=NULL,*psecond=NULL,*pend=NULL; pfirst=Head
; psecond=Head; int temp; while(pfirst != pend) // External circulation { //pfirst != pend Very interesting
while(pfirst->next != pend)// Internal circulation { if(pfirst->date > pfirst->next->date) { temp=
pfirst->date; pfirst->date=pfirst->next->date; pfirst->next->date=temp; } pfirst
=pfirst->next; } pend=pfirst;// Reduce the last scheduled cycle pfirst=Head; } return Head; }
/* Selection and sorting of linked list */ NODE* selectsort(NODE* head) { NODE *pfirst=NULL,*psecond=NULL,*pend
=NULL; pfirst=head; psecond=head; int temp; while(pfirst != pend) // External circulation { while(
pfirst->next != pend)// Internal circulation { if(psecond->date > pfirst->next->date) { temp=
psecond->date; psecond->date=pfirst->next->date; pfirst->next->date=temp; }
pfirst=pfirst->next; } psecond=psecond->next; pfirst=psecond; } return head; }
int main() { NODE* pHead=NULL; pHead=creat(); printf(" Before sorting ：\n"); print(pHead);
// pHead=bubblesort(pHead); // Bubble sorting pHead=selectsort(pHead); // Select sort printf(
"\n After sorting ：\n"); print(pHead); endscan(); return 0; }
Technology