#include<stdio.h> #include<malloc.h> #define LEN sizeof(struct Student) struct Student //结构体声明 { long num; int score; struct Student* next; }; int n;

struct Student* creat() //创建单向链表 { struct Student *head=NULL, *p_before, p_later; p_before = p_later = (struct Student) malloc(LEN); scanf_s(“%ld%d”, &p_before->num, &p_before->score); while (p_before->num!=0) { n++; if (n == 1) head = p_before; else p_later->next = p_before; p_later = p_before; p_before = (struct Student*) malloc(LEN); scanf_s(“%ld%d”, &p_before->num, &p_before->score); } p_later->next = NULL; free(p_before); return head; }

struct Student* sort(struct Student* list) //冒泡排序，当初写的是内容交换而不是指针交换，我知道这不是好的做法，但日子一久，当下没时间和热情改了，大家原谅， { //等有时间了一定改 struct Student *p, *q; int temp1,i; long temp2; for (p = list, i =1; i < n;i++,p=p->next) for (q = p->next;q!= NULL;q=q->next)

讯享网</span><span style="color: rgba(0, 0, 255, 1)">if</span> (p-&gt;score &lt; q-&gt;<span style="color: rgba(0, 0, 0, 1)">score) { temp1 </span>= p-&gt;<span style="color: rgba(0, 0, 0, 1)">score; p</span>-&gt;score = q-&gt;<span style="color: rgba(0, 0, 0, 1)">score; q</span>-&gt;score =<span style="color: rgba(0, 0, 0, 1)"> temp1; temp2 </span>= p-&gt;<span style="color: rgba(0, 0, 0, 1)">num; p</span>-&gt;num = q-&gt;<span style="color: rgba(0, 0, 0, 1)">num; q</span>-&gt;num =<span style="color: rgba(0, 0, 0, 1)"> temp2; } </span><span style="color: rgba(0, 0, 255, 1)">return</span><span style="color: rgba(0, 0, 0, 1)"> list; 

}

struct Student* sort1(struct Student* h) //插入排序（下边这堆注释是当初写完代码后又分析时加的，这里必须承认，我参考了网上的一些代码。这里大家要是看不 { //懂或是不想看，就略过吧。还有，这里“结点”写成“节点”了，纠正一下，不好意思 struct Student *f, *t, *p=NULL, *q; f = h->next; //f指向旧链的第一个节点，即等待在新链中“安家落户”（插入）的节点 h->next = NULL; //将原链的第一个节点单拿出来作为新链（待插入链）的第一个节点，默认此节点是关键值最大的节点 while (f!=NULL) //当f=NULL，旧链中的节点都插入到了新链，排序完成 { for (t = f, q = h; (q != NULL && (q->score > t->score)); p = q, q = q->next);//t和f同指，当找到插入位置，f指向旧链的下一个节点时，用t来进行

 </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)">插入操作；q先指向新链的第一个节点，q不断在新链中后移，以找到f（即t）所指节点的插入位置 </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)">p作为q的前驱，用来完成插入。整个语句的作用是：在新链遍历完（q != NULL）的前提下，在新 </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)">链中找到第一个关键值比f（即t）所指节点关键值小的节点，毫无疑问，q的前驱，即p（如果有的 </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)">话）的关键值一大于定f（即t）所指节点关键值（否则q怎么会后移到当前位置呢?）；如果没有， </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)">那说明当前新链的头节点关键值比f（即t）所指节点关键值小；如果最后q = NULL了，说明当前新 </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)">链的最后一个节点（此时p正指向它）的关键值都比f（即t）所指节点关键值大。不管哪种情况，f </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)">（即t）所指节点都应插在q所指节点前，p所指节点后（如果有的话）</span> 

f = f->next; //在进行插入操作前，先使f后移 if (q == h) h = t; //如果当前新链的头节点关键值比f（即t）所指节点关键值小，需要将f（即t）所指节点插在该头节点前，先让新链头节点指针指向

讯享网 </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)">f（即t）所指节点，作为新链的新的头节点</span> 

else p->next = t; //否则，将f（即t）所指节点连在p所指节点后 t->next = q; //不管if还是else，都需要将f（即t）所指节点连在q所指节点前，如果q=NULL，就是让f（即t）所指节点的next域指向NULL,这显然也是正确的 } return h; //返回新链（排好序的链）的头节点指针 }

struct Student* sort2(struct Student* h) //选择排序 {


struct Student *f=NULL,*t=NULL, *max, *maxbf=NULL, *p;

while (h!=NULL)
{

for (p = h, max = h; p->next != NULL; p = p->next) {

</span><span style="color: rgba(0, 0, 255, 1)">if</span> (p-&gt;next-&gt;score &gt; max-&gt;<span style="color: rgba(0, 0, 0, 1)">score) { maxbf </span>=<span style="color: rgba(0, 0, 0, 1)"> p; max </span>= p-&gt;<span style="color: rgba(0, 0, 0, 1)">next; } 

} if (f==NULL) {

讯享网

讯享网f </span>=<span style="color: rgba(0, 0, 0, 1)"> max; t </span>=<span style="color: rgba(0, 0, 0, 1)"> max; 

} else {

t</span>-&gt;next =<span style="color: rgba(0, 0, 0, 1)"> max; t </span>=<span style="color: rgba(0, 0, 0, 1)"> max; 

} if (max==h) {

讯享网h </span>= h-&gt;<span style="color: rgba(0, 0, 0, 1)">next; 

} else {

maxbf</span>-&gt;next = max-&gt;<span style="color: rgba(0, 0, 0, 1)">next; 

} } t->next = NULL; return f; }

struct Student* sort3(struct Student* h) //这是什么排序呢？我也说不好。这是我自己想出来的算 { //法……大体思想是：先从链表第一个结点开始遍历链表，找出关键值（这里是成绩score）最大的（因为 struct Student *p, *q, *pt=NULL, *pbf=NULL, *qbf=NULL; //是从大到小排序）结点和链表中第一个结点交换（利用指针实现）；然后，从链表中第二个结点开始遍历链 for (p = h ; p->next!=NULL; pbf = p, p = p->next) //表，找出关键值最大的结点和链表中第二个结点交换……如此操作，直到从链表中最后一个结点开始的那趟 { //遍历和操作结束 for (q = p; q->next != NULL;q=q->next) //代码格式很不好，写这段代码时在下还很渣很渣……粘贴到这里时，就更不好看了……对不起大家了 {

if (p->score < q->next->score)

讯享网{ qbf </span>= q; q = q-&gt;<span style="color: rgba(0, 0, 0, 1)">next; </span><span style="color: rgba(0, 0, 255, 1)">if</span> (p==h &amp;&amp; p-&gt;next==<span style="color: rgba(0, 0, 0, 1)">q) { h </span>= q; p-&gt;next = q-&gt;next; q-&gt;next = p; p =<span style="color: rgba(0, 0, 0, 1)"> q; } </span><span style="color: rgba(0, 0, 255, 1)">else</span><span style="color: rgba(0, 0, 0, 1)"> { </span><span style="color: rgba(0, 0, 255, 1)">if</span> (p == h&amp;&amp;p-&gt;next !=<span style="color: rgba(0, 0, 0, 1)"> q) { h </span>= q; pt = q-&gt;next; q-&gt;next = p-&gt;next, qbf-&gt;next = p; p-&gt;next = pt; p = q; q =<span style="color: rgba(0, 0, 0, 1)"> qbf; } </span><span style="color: rgba(0, 0, 255, 1)">else</span><span style="color: rgba(0, 0, 0, 1)"> { </span><span style="color: rgba(0, 0, 255, 1)">if</span> (p != h &amp;&amp; p-&gt;next ==<span style="color: rgba(0, 0, 0, 1)"> q) { pt </span>= q-&gt;next; pbf-&gt;next = q; q-&gt;next = p; p-&gt;next = pt; p =<span style="color: rgba(0, 0, 0, 1)"> q; } </span><span style="color: rgba(0, 0, 255, 1)">else</span><span style="color: rgba(0, 0, 0, 1)"> { </span><span style="color: rgba(0, 0, 255, 1)">if</span> (p != h &amp;&amp; p-&gt;next !=<span style="color: rgba(0, 0, 0, 1)"> q) { pt </span>= q-&gt;next; pbf-&gt;next = q; q-&gt;next = p-&gt;next; qbf-&gt;next = p; p-&gt;next = pt; p = q; q =<span style="color: rgba(0, 0, 0, 1)"> qbf; } } } } } 

} } return h; }

//快排 这里在下也参考了网上的代码，但在下也着实进行了一番改进才编译通过，这里使用了指针的指针，不详细讲了，大家自己分析吧

struct Student* Link_Quick_Sort(struct Student head, struct Student end) // 注意这里函数返回值可以写成void，同时将return语句去掉， { //同时，将main函数中(1)(2)两句改为： struct Student * big_head=NULL, *big_end=NULL, *small_head=NULL, *small_end=NULL; //Link_Quick_Sort(&pt, NULL); struct Student * big_tail=NULL, *small_tail = NULL; //for (p=pt, i = 1; i <= n; i++, p = p->next) int key = (*head)->score; //也是可以的。原因是递归是先进后出，后进先出，二第一次调用时传的是&pt（见main函数中 struct Student * traversal = (*head)->next; //第(1)句），故当整个函数结束后，pt的值已修改，且指向排好序的链表的头结点。 (*head)->next = NULL;


struct Student *p = NULL; while (traversal != NULL) { if (traversal->score > key) {

</span><span style="color: rgba(0, 0, 255, 1)">if</span> (big_head == NULL) { big_head = traversal; big_tail =<span style="color: rgba(0, 0, 0, 1)"> traversal; } </span><span style="color: rgba(0, 0, 255, 1)">else</span>{ big_tail-&gt;next = traversal; big_tail =<span style="color: rgba(0, 0, 0, 1)"> traversal; } traversal </span>= traversal-&gt;<span style="color: rgba(0, 0, 0, 1)">next; big_tail</span>-&gt;next =<span style="color: rgba(0, 0, 0, 1)"> NULL; 

} else {

讯享网</span><span style="color: rgba(0, 0, 255, 1)">if</span> (small_head == NULL) { small_head = traversal; small_tail =<span style="color: rgba(0, 0, 0, 1)"> traversal; } </span><span style="color: rgba(0, 0, 255, 1)">else</span>{ small_tail-&gt;next = traversal; small_tail =<span style="color: rgba(0, 0, 0, 1)"> traversal; } traversal </span>= traversal-&gt;<span style="color: rgba(0, 0, 0, 1)">next; small_tail</span>-&gt;next =<span style="color: rgba(0, 0, 0, 1)"> NULL; 

} } big_end = big_tail; small_end = small_tail; if (big_head != NULL && big_head->next != NULL){ Link_Quick_Sort(&big_head, &big_end); } if (small_head != NULL && small_head->next != NULL){ Link_Quick_Sort(&small_head, &small_end); } if (big_end != NULL&&small_head != NULL) {

big_end</span>-&gt;next = (*<span style="color: rgba(0, 0, 0, 1)">head); (</span>*head)-&gt;next =<span style="color: rgba(0, 0, 0, 1)"> small_head; (</span>*head) =<span style="color: rgba(0, 0, 0, 1)"> big_head; </span><span style="color: rgba(0, 0, 255, 1)">if</span> (end == NULL){ end = &amp;<span style="color: rgba(0, 0, 0, 1)">p; } (</span>*end) =<span style="color: rgba(0, 0, 0, 1)"> small_end; 

} else if (big_end!=NULL) {

讯享网big_end</span>-&gt;next = (*<span style="color: rgba(0, 0, 0, 1)">head); </span><span style="color: rgba(0, 0, 255, 1)">if</span> (end == NULL){ end = &amp;<span style="color: rgba(0, 0, 0, 1)">p; } (</span>*end) = (*<span style="color: rgba(0, 0, 0, 1)">head); (</span>*head) =<span style="color: rgba(0, 0, 0, 1)"> big_head; 

} else if (small_head!=NULL) {

(</span>*head)-&gt;next =<span style="color: rgba(0, 0, 0, 1)"> small_head; </span><span style="color: rgba(0, 0, 255, 1)">if</span> (end == NULL){ end = &amp;<span style="color: rgba(0, 0, 0, 1)">p; } (</span>*end) =<span style="color: rgba(0, 0, 0, 1)"> small_end; 

} return (*head); }

void main() //用main函数来测试 { printf(“请依次输入学生的学和姓名 ”); printf(“学号和姓名间以空格隔开 ”); printf(“输入0 0结束 ”); struct Student* pt,p; struct Student creat(); struct Student* sort(); //这里调用的是冒泡排序，要想调用其它排序，在这里改一下函数调用就可以了 pt=creat(); int i; for ( p=pt,i = 1; i <=n; i++,p=p->next) printf(“num=%ld score=%d ”, p->num, p->score); printf(“排序后： ”);

讯享网 p</span>=Link_Quick_Sort(&amp;pt, NULL); <span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)">(1)</span> 

for ( i = 1; i <= n; i++, p = p->next)//(2) printf(“第%d名： num=%ld score=%d ”,i, p->num, p->score); }

代码已经过测试，在VS2013上成功运行！

发此文有两大目的：

1.和大家交流经验，供需要的人参考。

2.在下菜鸟，代码中难免有不妥之处，恳求大神批评指正。您的批评就是在下提高的起点，对于您的批评，在下将不胜感激！