链表的选择排序.doc

排序采用选择法： 把30 接到80后面 45接到90后面 90替原来45的位置 *************************** 预备知识： NODE *v,*u,*p,*h; U,v,h,p都是指针，它们只是地址性的可以指向结构 而链表中的表 有next指针 **************************************** 链表排序 h 45 65 54 80 90 30 要实现45和90 的交换： 要接到80后面 要接到90后面 要接到h后面 90 45 65 54 80 30 要实现45和80 的交换： 30 接到54后面 接到80后面 80要接到90后面。即插入到90后面 所以一般情况需要用： 两个指针 vold v 指出45 两个指针 mold max 指出最大 这样可以方便的实现 v 或max,移走或被替换时，其它的可以接上。 但如果要被替换的是第一个，如45被90替换。 h,vold,v max 45 65 54 80 90 30 Max指向90， 30 放到80后面， h,vold,v max 45 65 54 80 30 90 45 放到90后面，h,v,vold都跟着45移动， max h,vold,v 90 45 65 54 80 30 h=max 还要一个游动指针 ，u， 用于不断和v比较 为了继续进行,下一轮开始前应该为： h ,vold v,max u 90 45 65 54 80 30 vold要指向90, v指向45, u指向54 所以对于第一次交换后还要移动vold if(vold==v) 时，vold=h; 总之一个比较可行的程序为： while (v-next != NULL) //省去 空的v， //选择法 { for(max=v,uold= u = v-next; u-next != NULL; uold=u, u = u-next) { if (u-score max-score ) { mold=uold; max = u; } //找到最大的 } //u已移动，但队列未动 // u-next == NULL即u是最后一个表，跳出循环， // 还要判别u指向的表是最大吗？ if(u-scoremax-score) {mold =uold; max=u;} //最后一个 if (max!= v) { mv-next= max-next; max-next =v; if(vold==v) { h=max; } else { vold-next=max; } } 。。。。。 可见用以上方法指针比较多，而且指针移动比较麻烦。 因为一开始，不能够用vold=vold-next;方式。 并且上述程序还未完全调通 *************************************** 为此，一种常用的方法，引入一个空表接到h的后面 先比较45 和65 ： if( v-next-score u-next-score ) ,………. 比出最大后 ， 90要插入到u的位置时，要做下面的步骤： 1. 30 接到 80后面 . max独立出来 2. max-next =u; 3. v-next=max; v=v-.next, u=v-next 将来输出时 return h-next;, 就可以把空表让过 具体分析： 引进一个v NODE *v=(NODE*)malloc(sixeof(NODE)); V u h p p1 p2 p3 p4 p5 p6 v-next =h; h=v; 把v插入h和p1(45)之间 先比较p1==u(45)和p2 (65) 为了适合循环： v-next-score， u-next-score表示要比较的数据：u-score==45，p2.score == 65 P=v; u=v-next ; （v-next==u） u-score==45 , v-next-sc