数据与结构 - 链表的排序 - 使用直接插入排序

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

该问题我用C语言写的的 ，大家也可以用Java尝试。

//链表排序 - 直接插入排序算法 - 先构建只含一个数据结点的有序单链表，然后依次扫描单链表中剩下的结点*base
//在有序表中通过比较查找插入base的前驱结点*base_left, 然后将*base插入到*base_left之后
LNode *sort(LNode *L)
{
    LNode *base = L->next, *base_left;//创建一个基准结点
    LNode *base_right = base->next;//基准结点的后继结点 保证不会断链
    base->next = NULL;//这一步必须有 L结点目前只有一个数据结点 构造只含有一个数据结点的有序表
    base = base_right;//base用于表示它的后继结点

    while(base != NULL){

        base_right = base->next;//先将基点的后继结点赋值给base_right变量
        base_left = L;//基点的左边有序序列的首个结点

        //有序序列的后继结点存在 并且 "有序后继结点"的值小于基点的值 那么 有序序列后继基点赋值给base_left
        while(base_left->next != NULL && base_left->next->data < base->data){
            base_left = base_left->next;
        }

        //这里已经找到了大于基点的有序序列的结点，基点指向有序序列的结点的后继结点
        base->next = base_left->next;
        base_left->next = base;//然后 有序序列的结点指向基点
        base = base_right;//将基点的后继结点变身为"基点"接着进行循环，知道变身后的"基点"等于NULL
    }

    return L;
}

剩下的是链表基本操作的demo 我发上去

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

//创建单链表的成员  其实就是结点
//LNode p;  p就是一个结点
typedef struct LNode {
    int data;  //数据域
    struct LNode *next;  //指针域
}LNode;  //LNode 为这个结构体的别名


//初始化链表
LNode *initLink() {
    LNode *p = (LNode*)malloc(sizeof(LNode));  //创建一个头结点
    //动态分配内存
    LNode *temp = p;  //声明一个指针指向头结点，用于遍历链表
    //14行中创建了一个头结点 定义一个指针  因为p是指针变量 temp也是指针变量
    //生成链表
    for (int i = 1; i < 5; i++) {
        LNode *a = (LNode*)malloc(sizeof(LNode));   //创建一个新的结点
        //对这个结点的成员进行赋值
        a->data = i;
        a->next = NULL;   //这个结点的指针指向NULL 表示结束标志
        temp->next = a;   //temp的作用用来遍历链表
        temp = temp->next;
    }
    return p;
}


LNode * insertElem(LNode *L, int elem, int addIndex){
    LNode *temp = L;//创建临时结点用来遍历链表
    //先找到要插入的位置的上一个结点
    for(int i = 1; i < addIndex; i++){
        if(temp == NULL) {
            printf("插入位置无效");
            return L;
            //这里形参为这个链表的首地址，如果首地址的指向为空 1 可能是一个空链表 2 在进行第i次遍历的时候未达到addIndex的位置就结束了
        }
        temp = temp->next;
    }
    //创建插入结点c
    //链表中所以存储方式必须是以结点的方式
    LNode *c = (LNode * )malloc(sizeof(LNode));

    //向链表中插入结点 这里插入结点的方法：先通过新节点连接后面的数 然后原来的结点连接新节点
    c->data = elem;
    c->next = temp->next;
    temp->next = c;
    return L;

}



//链表按值搜索
int selectElem(LNode *L, int elem){
    LNode *temp = L;//
    int i = 1;//位置 初始化为1
    temp = temp->next;//第一个结点
    while(temp != NULL) {
         if(temp->data == elem) return i;
         temp = temp->next;
         i++;
    }

    return -1;

}

LNode *delElem(LNode *p, int add) {
    LNode *temp = p;  //创建一个临时结点用来遍历
    //判断删除位置是否正确
    for (int i = 1; i < add; i++)
    {
        if (temp == NULL) {
            printf("删除位置异常\n");
            return p;
        }
        temp = temp->next;
    }
    LNode *c = temp->next;   //这里定义的这个非常巧妙
    //此时的c指向被删去的结点
    //要删除直接将其覆盖
    temp->next = c->next;    //这里就ok
    free(c);   //释放内存
    return p;
}

//进行更改
LNode *amendElem(LNode *p, int add, int newElem)
{
    LNode *temp = p;   //创建一个临时结点用来遍历
    for (int i = 1; i < add; i++)
    {
        if (temp == NULL) {
            printf("更改位置无效\n");
            return p;
        }
        temp = temp->next;
    }
    //此时的temp指向更改位置的前一个点
    LNode *amend = temp->next;   //创建一个临时结点指向更改的位置
    amend->data = newElem;    //更改数据成功

    return p;
}

//输出链表
void display(LNode *p) {
    LNode *temp = p;  //创建一个临时结点用来遍历
    //只要temp->next不指向NULL就输出
    while (temp->next) {
        temp = temp->next;
        printf("%d ", temp->data);
    }
    printf("\n");
}


//链表排序 - 直接插入排序算法 - 先构建只含一个数据结点的有序单链表，然后依次扫描单链表中剩下的结点*base
//在有序表中通过比较查找插入base的前驱结点*base_left, 然后将*base插入到*base_left之后
LNode *sort(LNode *L)
{
    LNode *base = L->next, *base_left;//创建一个基准结点
    LNode *base_right = base->next;//基准结点的后继结点 保证不会断链
    base->next = NULL;//这一步必须有 L结点目前只有一个数据结点 构造只含有一个数据结点的有序表
    base = base_right;//base用于表示它的后继结点

    while(base != NULL){

        base_right = base->next;//先将基点的后继结点赋值给base_right变量
        base_left = L;//基点的左边有序序列的首个结点

        //有序序列的后继结点存在 并且 "有序后继结点"的值小于基点的值 那么 有序序列后继基点赋值给base_left
        while(base_left->next != NULL && base_left->next->data < base->data){
            base_left = base_left->next;
        }

        //这里已经找到了大于基点的有序序列的结点，基点指向有序序列的结点的后继结点
        base->next = base_left->next;
        base_left->next = base;//然后 有序序列的结点指向基点
        base = base_right;//将基点的后继结点变身为"基点"接着进行循环，知道变身后的"基点"等于NULL
    }

    return L;
}

//测试案例
int main() {
    //初始化链表
    printf("\n------初始化链表----------\n");
    LNode *p = initLink();
    display(p);

    printf("在第4的位置插入元素11：\n");
    p = insertElem(p, 11, 1);
    p = insertElem(p, 5, 2);
    p = insertElem(p, 13, 3);
    p = insertElem(p, 6, 4);
    p = insertElem(p, 8, 5);
    display(p);

    printf("进行排序 \n");
    p = sort(p);
    display(p);
//    printf("删除元素3：\n");
//    p = delElem(p, 3);
//    display(p);
//
//    printf("查找元素2的位置为：\n");
//    int address = selectElem(p, 2);
//    if (address == -1)
//        printf("没有该元素\n");
//    else printf("元素2的位置为：%d\n", address);
//
//    printf("更改第3的位置的数为7：\n");
//    p = amendElem(p, 3, 7);
//    display(p);

    return 0;

}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 214,837评论 6赞 496
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,551评论 3赞 389
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 160,417评论 0赞 350
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,448评论 1赞 288
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,524评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,554评论 1赞 293
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,569评论 3赞 414
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,316评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,766评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,077评论 2赞 330
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,240评论 1赞 343
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,912评论 5赞 338
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,560评论 3赞 322
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,176评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,425评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,114评论 2赞 366
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,114评论 2赞 352