转载 常见与链表相关的算法.doc

转载 常见和链表相关的算法 原文地址：常见和链表相关的算法作者：daniel一、链表排序 链表排序和数组排序的思路类似，只是链表操作起来比较麻烦，因为不能随机访问，所以只能借助于类似于前置或后置插入，添加等概念来完成。下面给出了链表排序的几种方法。 辅助代码： //单链表节点的定义 typedef struct LinkNode{ int val； struct LinkNode*next； }LinkNode； //由一个数组创建单链表 LinkNode*CreateList(int A,int count) { if(NULL==A) return NULL； LinkNode*head=(LinkNode*)malloc(sizeof(LinkNode))； head-val=A[0]； head-next=NULL； LinkNode*p=head； for(int i=1；i count；++i) { p-next=(LinkNode*)malloc(sizeof(LinkNode))； p-next-val=A[i]； p-next-next=NULL； p=p-next； } return head； } //显示该单链表 void ShowList(LinkNode*L) { LinkNode*p=L； printf(%d,p-val)； while(p-next) { p=p-next； printf(--%d,p-val)； } printf(n)； } 1.插入排序(以从小到大排序为例) 链表排序最容易想到的是插入排序，它的基本想法是从第一个节点开始，每次将一个节点放到结果链表，并保证每个节点加入到结果链表前后，结果链表都是有序的。每个节点在被链入结果链表时有三种情况： 1)该节点值比结果链表中的所有元素值都大，则将该节点追加到结果链表的最后； 2)该节点值比结果链表中的所有元素值都小，则将该节点插入到结果链表最前面； 3)该节点值在结果链表中处于中间位置，则将该节点插入到合适位置。 下面是该算法思路的流程图： 代码实现如下： LinkNode*SortLinkListInsertion(LinkNode*head) { //链表空或链表只有一个节点，不必排序，直接返回原头结点 if(NULL==head||NULL==head-next) { return head； } //我们从第二个节点进行处理，第一个节点作为结果链表的初始节点 LinkNode*r=head-next； LinkNode*tmp； head-next=NULL；//将结果链表末尾标记为结束 while(NULL！=r)//依次处理每一个节点 { if(r-val head-val) { //将该节点插到结果链表最前，并修改链表头，同时注意辅助变量的使用 tmp=r-next； r-next=head； head=r； r=tmp； } else { //否则从链表头部开始搜索，注意这里搜索结束的条件是当前被搜索节点不是最后一个节点 LinkNode*p=head； while(NULL！=p-next) { //注意只有当节点严格小于被搜索节点的下一节点的值是，才将其插入到被搜索节点后 //这样能保证排序是稳定的！ if(r-val p-next-val) { tmp=r-next； r-next=p-next； p-next=r； r=tmp； continue；//注意跳出，开始处理下一个节点 } else { p=p-next； } } //此时，p是结果链表中的末尾节点，将被处理节点追加到其后 if(NULL==p-next) { tmp=r-next； r-next=NULL； p-next=r； r=tmp； } }//end else }//end while(NULL！=r) return head； } 2.选择排序(以从小到大排序为例) 选择排序的基本思想是每次从源链表中选取并移除一个最小的元素，追加到结果链表的尾部，直到源链表变空为止。因此本算法的关键点在于如何从源链表中选取并移除一个最小的元素。考虑到一般情况下，我们在移除链表中的某个元素时，需要知道它的前一个节点的指针(我知道你在想那个trick，但我想我们还是用正统的方法吧)，于是我们可以按照最小元素的出现位置分为两种情况：最小元素是链表头部节点和最小元素不是链表头部节点。我们先找出链表中除头结点外的最小值节点，然后再和头节点的值比较，然后进行处理。寻找除头结点外的最小值节点的代码可以很简洁，这也是为什么要分成这两部分处理的原因。 代码实现如下： LinkNode*SortLinkListSelection2(LinkNode*head) { //我们