前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >模拟链表

模拟链表

作者头像
Zoctopus
发布2018-06-04 11:18:34
7000
发布2018-06-04 11:18:34
举报
文章被收录于专栏:章鱼的慢慢技术路

一、问题描述

有一串已经从小到大排好序的数2 3 5 8 9 10 18 26 32.现需要往这串数中插入6使其得到的新序列仍符合从小到大的排列。

二、问题分析

我们可以用一个数组data来存储每个序列中的每一个数,再用一个数组right来存放序列中每一个数右边的数是谁。

              1            2              3           4            5              6           7             8            9              10

data

             1            2              3           4            5              6           7             8            9              10

right 

上图的两个数组中,第一个整型数组data是用来存放序列中具体数字的,另外一个整型数组right是用来存放当前序列中每一个元素右边的元素在数组data中位置的。

比如right[1]的值为2,就表示当前序列中1号元素右边的元素存放在data[2]中;如果是0,比如right[9]的值为0,就表示当前序列中9号元素的右边没有元素。

现在需要在8前面插入一个6,只需将6直接存放在数组data的末尾即data[10]=6。接下来只需要将right[3]改为10,表示新序列中3号元素右边的元素存放在data[10]中。再将right[10]改为4,表示新序列中10号元素右边的元素存放在data[4]中。这样我们通过right数组就可以从头到尾遍历整个序列了(序列的每个元素的值存放在对应的数组data中),如下:

              1            2              3           4            5              6           7             8            9              10

data 

              1            2              3           4            5              6           7             8            9              10

right 

三、代码实现

代码语言:javascript
复制
    int data[101],right[101];
    int i,n,t,len;
    scanf("%d",&n);  //输入已有的数
    for(i=1;i<=n;i++)
        scanf("%d",&data[i]);
    len=n;
    for(i=1;i<=n;i++)  //初始化数组right
    {
        if(i!=n)
            right[i]=i+1;
        else
            right[i]=0;
    } 
    len++;  //直接在数组data的末尾增加一个数 
    scanf("%d",&data[len]);  
    /*从链表的头部开始遍历*/
    t=1;
    while(t!=0)
    {
        if(data[right[t]]>data[len])  //如果当前结点下一个结点的值大于待插入数,将数输入到中间
        {
            right[len]=right[t];  //新插入数的下一个结点标号等于当前结点的下一个结点标号
            right[t]=len;  //当前结点的下一个结点编号就是新插入数的编号
            break;  //插入完成跳出循环 
        } 
        t=right[t];
    } 
    /*输出链表中所有的数*/ 
    t=1;
    while(t!=0)
    {
        printf("%d ",data[t]);
        t=right[t];    
    }
    return 0;
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017-04-04 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、问题描述
  • 二、问题分析
  • 三、代码实现
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档