正文 

当前位置： 首页 > 技术 > java教程

在有序链表中插入数据

luolinjin luolinjin     2023-04-07     689

关键词：

给定一批严格递增排列的整型数据，给定一个x，若x不存在，则插入x，要求插入后保持有序。存在则无需任何操作。

输入格式:

输入有两行： 第一个数是n值，表示链表中有n个数据。后面有n个数，分别代表n个数据。 第二行是要插入的数。

输出格式:

输出插入后的链表数据，以空格分开。行末不能有多余的空格。

输入样例1:

在这里给出一组输入。例如：

5 1 3 6 9 11
4
 

输出样例1:

在这里给出相应的输出。例如：

1 3 4 6 9 11
 

输入样例2:

在这里给出一组输入。例如：

5 1 3 6 9 11
3
 

输出样例2:

在这里给出相应的输出。例如：

1 3 6 9 11






#include <iostream>
using namespace std;

typedef int ElemType;
typedef struct LNode
    ElemType data;
    struct LNode* next;
LNode, * LinkList;


void CreateList(LinkList& L, int n)
    L = new LNode;
    L->next = NULL;
    LNode* p = L;
    int m;
    for (int i = 0; i < n; i++)
    
        cin >> m;
        p->next = new LNode;
        p = p->next;
        p->data = m;
        p->next = NULL;
    

void InsertList(LinkList& L, int n, int x)
    LNode* p = L;
    if (p->next == NULL)//这种情况下是为空链表直接插入节点的
    
        LNode* q = new LNode;
        q->data = x;
        q->next = NULL;
        p->next = q;
        p = q;
        return;
    
    while (p->next != NULL)
    
        LNode* temp = p;
        p = p->next;
        if (p->data == x) return;
        if (p->data > x)
        
            LNode* q = new LNode;
            q->data = x;
            q->next = p;
            temp->next = q;
            return;
        
    

    LNode* q = new LNode;
    q->data = x;
    q->next = NULL;
    p->next = q;
    p = q;
    return;


void OutputList(LinkList L)
    LNode* p = L->next;
    while (p != NULL)
        cout << p->data;
        if (p->next != NULL)
            cout << " ";
        p = p->next;
    

int main()
    int n, x;
    cin >> n;
    LinkList L;
    CreateList(L, n);

    cin >> x;
    InsertList(L, n, x);
    OutputList(L);
    return 0;
 
 
 
 
同学的代码 
个人感觉写的和清晰
值得收藏学习
 

数据结构编程实验(代码片段)

...单向链表中删除所有的偶数元素结点。5．编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。6．利用算法5建立两个非递减有序单向链表，然后合并成一个非递增链表。... 查看详情

有序的双链表的实现(代码片段)

描述定义有序的双链表类,链表中存储整型数据，创建带头结点的有序双链表，要求包含以下成员函数：双链表的构造函数（非空的链表，输入数据为0,表示输入结束）插入操作（将一个数据元素插入到有序的双链表中，插入之后... 查看详情

数据结构-二叉树(代码片段)

...势      在实际使用时会根据链表和有序数组等数据结构的不同优势进行选择。有序数组的优势在于二分查找，链表的优势在于数据项的插入和数据项的删除。但是在有序数组中插入数据就会很慢，同样在链... 查看详情

栈和队列----向有序的环形单链表中插入新节点(代码片段)

向有序的环形单链表中插入新节点　　　　一个环形链表从头节点开始不会降序，同时最后的节点指向头节点。给定一个环形单链表的头节点head和一个整数num，生成新节点并将其插入到环形链表中，保证插入后的链表仍然有序... 查看详情

redis跳跃表实现原理(加快在有序链表中的查找速度)(代码片段)

Redis跳跃表实现原理我们知道二叉搜索算法能够高效的查询数据，但是需要一块连续的内存，而且增删改效率很低。跳表，是基于链表实现的一种类似“二分”的算法。它可以快速的实现增，删，改，查操... 查看详情

在有序链表中编写删除算法

】在有序链表中编写删除算法【英文标题】：Writingadeletealgorithminanorderedlinkedlist【发布时间】：2013-10-1912:55:08【问题描述】：我正在尝试为有序链表编写删除算法。搜索和遍历我认为我已经失败但删除让我很适应。每次都会崩溃... 查看详情

c和c指针小记(十七)-使用结构和指针(代码片段)

...历.1.2在单链表中插入我们怎么才能把一个新节点插入到有序单链表中呢?加入要把7插入到单链表.(如果链表中的值为1,3,5,10,11)思路:从链表的起始位置开始,跟随指针直到找到第一个值大于7的节点,然后把这个新值插入到那个节点之... 查看详情

学习数据结构，寻找优秀代码参考学习（c++），能够实现功能即可，发邮箱413715076@qq.com

...表的前面为奇数,后面为偶数。6．输入整型元素序列利用有序表插入算法建立一个有序表。7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。8．编写一个主函数,调试上述算法。二单向链表的有关操作1．随... 查看详情

链表——链表删除冗余结点&amp;插入结点到有序链表

1.一个以递增方式排列的链表，去掉链表中的冗余值。思路一：设有两个指针p和q。使p不动，q依次往后循环直到p->data不等于q->data，再将中间的冗余数据删除。思路二：设有两个指针p和q，使p在前，q在后，仅仅要找到一个冗... 查看详情

147.对链表进行插入排序(代码片段)

...代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。重复直到所有输 查看详情

数据结构与算法：链表——递增排序

...看书时偶然想到的问题，书上是要求将一个数据插入一个有序链接的线性链表中，所以我想先进行链表内的数据排序在进行插入数据。在这里我只写了排序的函数。 函数实现：voidSort(LinkList&list,int&n) 　　for(inti=0;i<n-1... 查看详情

[数据结构]单向链表插入排序(c语言)(代码片段)

...入排序，其步骤大致为:先将第一个数据元素看作是一个有序序列，后面的n-1个数据元素看作是未排序序列。对后面未排序序列中的第一个数据元素在这个有序序列中进行从后往前扫描，找到合适的插入位置并插入到其中，每次... 查看详情

ds01——线性表(代码片段)

...将前驱指向要删除节点的下一个节点，释放删除的节点3.有序表有序表单链表插入。遍历有序表，找到插入节点的前驱，该节点指向前驱的下一个节点，前驱指向该节点，有插入到末尾的情况有序表单链表删除。遍历有序表，找... 查看详情

数据结构和算法——二叉树

树1.树的优点有序数组：查找很快，二分法实现的查找所需要的时间为O(logN),遍历也很快，但是在有序数组中插入，删除却需要先找到位置，　　　　　　在把数组部分元素后移，效率并不高。链表：链表的插入和删除都是很快... 查看详情

redis跳跃表实现原理(加快在有序链表中的查找速度)(代码片段)

Redis跳跃表实现原理我们知道二叉搜索算法能够高效的查询数据，但是需要一块连续的内存，而且增删改效率很低。跳表，是基于链表实现的一种类似“二分”的算法。它可以快速的实现增，删，改，查操... 查看详情

算法数据结构专题「延时队列算法」史上手把手教你针对层级时间轮（timingwheel）实现延时队列的开发实战落地（下）(代码片段)

...长度限制了其适用场景，这里对此进行优化。因此引入了有序列表时间轮。有序列表时间轮与无序列表时间轮一样，同样使用链表进行实现和设计，但存储的是绝对延时时间点。启动线程：有序插入，比较时间按照时间大小有序... 查看详情

数据结构第三章：不带头结点的单链表操作(代码片段)

...点，插到链表中值为frontData的结点的前面二、在一个有序的链表中，有序(升序)地将值为inputData的结点插入到链表中三、在已知的链表中删除值为delData的结点一、新建一个值为inputData的结点，插到链表中值为frontData的... 查看详情

对链表进行插入排序(代码片段)

...代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。每次迭代中，插入排序只从输入数据中移 查看详情