双链表的插入排序算法

偏执的太偏执、 2022-04-13 10:59 316阅读 0赞

#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
int data;
struct Node *llink,*rlink;
}*DLinkList;
void INSLINKLIST(DLinkList list){
    DLinkList save,p,q,r;
    p=list->rlink->rlink; //从头结点的第二个结点开始插入
    while(p!=list){
        q = p->llink; //q指向本次排序的起始位置
        save = p->rlink;//保存下一趟插入的开始起始位置
        r = save; 
        while(q!=list && p->data<q->data){
            if (r==save)  //只要执行这一步,就说明p结点小于q结点,所以跟定不是q结点的后继,所以需要先把p结点剪出来
            {
                r->rlink = q; //将结点p剪出来,让p的前驱和p的后继直接连接成一条链,方便以后遇到合适的直接插入,而不用再删除p结点
                q->llink = r;
            }
            r = q;
            q=q->llink;
        }
        if (r!=save)//寻找插入位置
        {
            r->llink = p;
            q->rlink = p;
            p->llink = q;
            p->rlink = r; //将p结点插入q结点与r 结点之间
        }
        p = save;
    }
}