链表排序方法分析VIP免费

链表的排序分类：31.NET2005-12-1417:114766人阅读评论(5)收藏举报==========================功能：选择排序(由小到大)返回：指向链表表头的指针==========================*//*选择排序的基本思想就是反复从还未排好序的那些节点中，选出键值（就是用它排序的字段，我们取学号num为键值）最小的节点，依次重新组合成一个链表。我认为写链表这类程序，关键是理解：head存储的是第一个节点的地址，head->next存储的是第二个节点的地址；任意一个节点p的地址，只能通过它前一个节点的next来求得。单向链表的选择排序图示：---->[1]---->[3]---->[2]...---->[n]---->[NULL]（原链表）head1->next3->next2->nextn->next---->[NULL]（空链表）firsttail---->[1]---->[2]---->[3]...---->[n]---->[NULL]（排序后链表）first1->next2->next3->nexttail->next图10：有N个节点的链表选择排序1、先在原链表中找最小的，找到一个后就把它放到另一个空的链表中；2、空链表中安放第一个进来的节点，产生一个有序链表,并且让它在原链表中分离出来（此时要注意原链表中出来的是第一个节点还是中间其它节点）；3、继续在原链表中找下一个最小的，找到后把它放入有序链表的尾指针的next,然后它变成其尾指针；*/structstudent*SelectSort(structstudent*head){structstudent*first;/*排列后有序链的表头指针*/structstudent*tail;/*排列后有序链的表尾指针*/structstudent*p_min;/*保留键值更小的节点的前驱节点的指针*/structstudent*min;/*存储最小节点*/structstudent*p;/*当前比较的节点*/first=NULL;while(head!=NULL)/*在链表中找键值最小的节点。*/{/*注意：这里for语句就是体现选择排序思想的地方*/for(p=head,min=head;p->next!=NULL;p=p->next)/*循环遍历链表中的节点，找出此时最小的节点。*/{if(p->next->numnum)/*找到一个比当前min小的节点。*/{p_min=p;/*保存找到节点的前驱节点：显然p->next的前驱节点是p。*/min=p->next;/*保存键值更小的节点。*/}}/*上面for语句结束后，就要做两件事；一是把它放入有序链表中；二是根据相应的条件判断，安排它离开原来的链表。*//*第一件事*/if(first==NULL)/*如果有序链表目前还是一个空链表*/{first=min;/*第一次找到键值最小的节点。*/tail=min;/*注意：尾指针让它指向最后的一个节点。*/}else/*有序链表中已经有节点*/{tail->next=min;/*把刚找到的最小节点放到最后，即让尾指针的next指向它。*/tail=min;/*尾指针也要指向它。*/}/*第二件事*/if(min==head)/*如果找到的最小节点就是第一个节点*/{head=head->next;/*显然让head指向原head->next,即第二个节点，就OK*/}else/*如果不是第一个节点*/{p_min->next=min->next;/*前次最小节点的next指向当前min的next,这样就让min离开了原链表。*/}}if(first!=NULL)/*循环结束得到有序链表first*/{tail->next=NULL;/*单向链表的最后一个节点的next应该指向NULL*/}head=first;returnhead;}/*==========================功能：直接插入排序(由小到大)返回：指向链表表头的指针==========================*//*直接插入排序的基本思想就是假设链表的前面n-1个节点是已经按键值（就是用它排序的字段，我们取学号num为键值）排好序的，对于节点n在这个序列中找插入位置，使得n插入后新序列仍然有序。按照这种思想，依次对链表从头到尾执行一遍，就可以使无序链表变为有序链表。单向链表的直接插入排序图示：---->[1]---->[3]---->[2]...---->[n]---->[NULL]（原链表）head1->next3->next2->nextn->next---->[1]---->[NULL]（从原链表中取第1个节点作为只有一个节点的有序链表）head图11---->[3]---->[2]...---->[n]---->[NULL]（原链表剩下用于直接插入排序的节点）first3->next2->nextn->next图12---->[1]---->[2]---->[3]...---->[n]---->[NULL]（排序后链表）head1->next2->next3->nextn->next图13：有N个节点的链表直接插入排序1、先在原链表中以第一个节点为一个有序链表，其余节点为待定节点。2、从图12链表中取节点，到图11链表中定位插入。3、上面图示虽说画了两条链表，其实只有一条链表。...