2022年2022年链表的选择排序 .pdf

《2022年2022年链表的选择排序 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年链表的选择排序 .pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、排序采用选择法：把 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 的交换：30 要接到 80 后面45 要接到 90 后面90要接到 h 后面45 65 54 80 90 next 30 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 10 页

2、 - - - - - - - - - 90 45 65 54 80 30 要实现 45 和 80 的交换：30 接到 54 后面45 接到 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,

3、v,vold都跟着 45 移动，max h,vold,v 90 45 65 54 80 30 h=max 还要一个游动指针，u，用于不断和 v 比较为了继续进行 ,下一轮开始前应该为：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 10 页 - - - - - - - - - h ,vold v,max u 90 45 65 54 80 30 vold 要指向 90, v 指向 45, u指向 54 所以对于第一次交换后还要移动vold if(vold=v) 时，vold

4、=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=

5、max-next; max-next =v; if(vold=v) h=max; else vold-next=max; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 10 页 - - - - - - - - - 。 。 。 。 。可见用以上方法指针比较多，而且指针移动比较麻烦。因为一开始， 不能够用 vold=vold-next;方式。并且上述程序还未完全调通* 为此，一种常用的方法，引入一个空表接到h 的后面先比较 45 和 65 ：if( v-next-score

6、 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;, 就可以把空表让过名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 10 页 - - - - - - - - - 具体分析：引进一个 v NODE *v=(NODE*)malloc(sixeof(

7、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-score=45 p2=u-next=65 p2.score= u-next-score=65for(p=v,u=v-next; u-next!=NILL; u=u-next) if( p-ne

8、xt-score next-score) p=u; 找出最大的表 u-next-score=(90)， 然后交换 (90) (45) v u u u ( 即 max ）p 把 30 接到 80 后面：90 的指针要保存65 54 80 90 45 45 65 54 80 90 30 30 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 10 页 - - - - - - - - - 45 接到 90 后面90 替代 45 位置一、90 要独立出来，同时30 接到 80 后面

9、，需要两个指针：1. p=u?, u=p-next : p 指向80 u 指向90 90 要独立出来，所以要用指针u 指向它，以免丢掉，u 要移走，所以先用p 指向 80 2. p-next =u-next : 30 接到 80 后面二、 : 45接到 90 后面，u-next=v-next; 三、90 替代 45 位置v-next =u : V=v-next, u=v-.next 准备下一轮NODE *bubblesort(NODE *h) NODE *v,*u,*p; v = (NODE *)malloc(sizeof(NODE); v-next =h; h=v; while (v-nex

10、t != NULL) /选择法 for(p = v, u = v-next; u-next != NULL; u = u-next) if (u-next-score p-next-score ) p = u; /找到最大的/u已移动，但队列未动名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 10 页 - - - - - - - - - if (p != v) u = p-next; p-next = u-next; /ok u-next =v-next; v-next

11、=u; v=v-next; return h-next; /h; * 14 Sort() 排序由于学生信息采用的是单链表存储结构，所以选用直接插入算法较为简单。直接插入算法的基本方法是： 每步将一个待排序的记录按其排序码值的大小插到前面已经排好序的表中，直到全部插入为止。基于这样的方法首先将链表的头结点看作是已排好序的结点，然后取下一个结点作为待排序的结点，插入到已排好序的表中。 由于单链表的特性，所以具体的思路如下：(1) 先将原表头结点作为新排好序表的头结点h，原表下一个结点作为原表头结点h1 。设原表如图1l 所示，表中只列出总分数据。名师资料总结 - - -精品资料欢迎下载 - - -

12、 - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 10 页 - - - - - - - - - 图 11 设新表头结点即 h 是新链表，h1 是旧链表(2) 原表头结点为待排序结点，将其总分与新表结点的总分进行比较，如果待排序结点总分大，则插在新表的头， 否则插入在其后， 原表头结点后移一位，如图 12 所示。(3) 重复第二步，即将原表头结点的总分和新表结点的总分进行比较，如果待排序结点总分小，则移动新表指针，直到找到合适的位置将其插入，直到原表为空，所有结点排序完毕，如图13 所示。这个排序算法实际上是先从原表删除头结点

13、，然后在新表中查找到合适的位置，进行插入。待排序结点的插入名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 10 页 - - - - - - - - - 位置总是插在表头、表尾和表中间三种情况之一，由于单链表的特性，实际插入结点时，并不需要移动和交换结点信息，而是只改变指针关系，所以排序时间主要用在比较上。排好序后将其名次数据写入数据域order 中。STUDENT *sort(STUDENT *h) int i=0; /* 保存名次 */ STUDENT *p,*q,*t

14、,*hl; /* 定义临时指针 */ hl=h-next; /* 将原表头指针所指的下一个结点作为头指针*/ h1-next=NULL; /* 第 一 个 结 点 为 新 表 的 头 结 点*/ ？while(hl!=NULL) /* 当原表不为空时 ,进行排序 */ t=hl; /* 取原表的头结点 */ hl=hl-next; /* 原表头结点指针后移 */ p=h; /* 设定移动指针 P ,从头指针开始 , 即，h1 中的每一个，从 h 的头比较起 */ q=h; /* 设定移动指针 q 作为 P 的前一个 =pold,初值为头指针*/ 原表取第一个和新表从头进行比较while(t-s

15、um sum & p!=NULL) /* 进行总分比较 */ q=p; /* 待排序点值小 ,则新表指针后移 */ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 10 页 - - - - - - - - - p=p-next; /* 直到 t-sum p-sum时，t 插到 p 的前面if(p=q) /* 说明待排序点值最大 ,应排在首位 */ t-next=p; /* 待排序点的后继为p*/ h=t; /* 新头结点为待排序点 */ else /* 待排序点应插入在中

16、间某个位置q 和 P 之间, 如果 P 为空则是尾部 */ t-next=p; /*t的后继是 P*/ q-next=t; /*q的后继是 t*/ p=h; /* 排序完成 p 指针回到链表头 ,准备填写名次 */ / 因为是降序 i=1 即第一名，i=2, 第二名while(p!=NULL) /* P 不为空时 ,进行下列操作 */ i+; /* 结点序号 */ p-order=i; /* 将名次赋值 */ p=p-next; /* 指针后移 */ printf(sort sucess!n); /* 排序成功 */ return h; /* 返回头指针 */ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 10 页 - - - - - - - - -