常见与链表相关的算法.docVIP

常见和链表相关的算法 常见和链表相关的算法 2011年01月02日 　　一、 链表排序 　　链表排序和数组排序的思路类似，只是链表操作起来比较麻烦，因为不能随机访问，所以只能借助于类似于前置或后置插入，添加等概念来完成。下面给出了链表排序的几种方法。 　　辅助代码: 　　//单链表节点的定义 　　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(