双向链表排序

操作系统内存管理模拟实验中使用到双向链表。由于数据结构时候没有弄得很清楚，现在决定要彻底搞定，所以仔细研究了一下，发现双向链表如果用的熟练的话还是很爽的（在linux内核中，双向链表的使用可是司空见惯的）呵呵，不多废话了。先看看程序

#include <stdio.h>
#include<stdlib.h>

typedef struct node{
    int data;
    struct node *prior,*next;
}Link;

这个是包含的头文件和双向链表的结点数据结构。

void initList(Link *head){//初始化头结点

    head->next = head;
    head->prior = head;
    head->data = 65535;
}

void addList(Link *head,int data){//创建链表

    Link *tmp;
    tmp = (Link *)malloc(sizeof(Link));
    tmp->data = data;
    tmp->next = head->next;
    head->next->prior = tmp;
    head->next = tmp;
    tmp->prior= head;
}

上面两个程序段是链表的初始化和创建。

int main()

{

Link *head,*p;

head =(Link *)malloc(sizeof(Link));

p =(Link *)malloc(sizeof(Link));

int i;

int a[15]={7,4,2,7,5,8,6,3,2,4,5,7,98,3,4};

initList(head);

for(i=0;i<15;i++){

addList(head,a[i]);

}

p = head->next;

while(p->data!=65535){

printf("%d--",p->data);

p = p->next;

}

printf("\n");

sort(head);

p = head->next;

while(p->data!=65535){

printf("%d--",p->data);

p = p->next;

}

printf("\n");

}

main函数，为了简便测试期间使用了一个数组初始化链表。

下面是最主要的部分，排序

void sort(Link *head){

Link *p,*tmp,*flag;

int max;

p = (Link *)malloc(sizeof(Link));

tmp = (Link *)malloc(sizeof(Link));

flag = (Link *)malloc(sizeof(Link));

tmp  = head->prior;

max = tmp->data;

flag = tmp;

p = tmp->prior;

while(p->data != 65535){//找到值最大的节点并且标记

if(p->data > max){

max = p->data;

flag = p;

flag->data = max;

}

p = p->prior;

}

if(flag->data!=head->next->data)

{//交换最大值点到头节点后

flag->prior->next = flag->next;

flag->next->prior = flag->prior;

flag->next = head->next;

flag->prior = head;

head->next->prior = flag;

head->next = flag;

}

while(head->prior->data != flag->data){

tmp = head->prior;//重新寻找时总是从表尾，也就是头结点的前驱开始。

p = tmp->prior;   //从后往前寻找

while(p->data != flag->data){//找到要交换的节点

if(p->data > tmp->data){

tmp = p;

}

p = p->prior;

}

{//交换两个节点

tmp->prior->next = tmp->next;

tmp->next->prior = tmp->prior;

tmp->next = head->next;

tmp->prior = head;

head->next->prior = tmp;

head->next = tmp;

}

}

}

我实现排序的思路大致是这样的：首先从链表中找到data最大的那个节点，肯定是最终链表的尾节点（双向链表没有尾节点一说，为了方便，假设头结点的前驱那个节点就是尾节点），标记上，然后开始排序，每次寻找剩余中最大的点，而且从当前尾节点开始，向前驱寻找（截止到标记的那个节点，想一想为什么？嘿嘿），找到当前最大值便头插在链表的头结点后面，直到尾节点真正到了那个标记的最大值节点。

好了，就这些。由于写的匆忙，其中错误的地方在所难免，希望朋友们指出，谢谢。