您当前的位置:首页 > 计算机 > 编程开发 > C语言

有一个带头结点的单链表L,设计一个算法使其元素递增有序

时间:01-03来源:作者:点击数:

问题描述:

有一个带头结点的单链表L,设计一个算法使其元素递增有序。

问题解答:

算法思想:用直接插入排序算法的思想,先构成只含一个数据结点的有序单链表,然后依次扫描单链表中剩下的结点*p (直至p==NULL为止),在有序表中通过比较查找插入 *p的前驱结点*pre,然后将*p插入到*pre之后,如下图所示。

本题代码如下:

void Sort(LinkList &L){
    //本算法实现将单链表L的结点重排,使其递增有序
    LNode *p=L->next, *pre;
    LNode *r=p->next;  //r保持*p后继结点指针,以保证不断链
    p->next=NULL;  //构造只含一个数据结点的有序表
    p=r;
    while(p!=NULL){
        r=p->next;  //保存*p的后继结点指针
        pre=L;
        while (pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;  //在有序表中查找插入的前驱结点*pre
        p->next=pre->next;  //将*p 插入到*pre 之后
        pre->next=p;
        p=r; //扫描原单链表中剩下的结点
    }
}

 

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门