c_mylife 2022-03-11 15:08 采纳率: 100%
浏览 79
已结题

数据结构中的插入和删除算法 尽量使用C++语言书写

题目描述
某便利店员工想将超市中N个相似类型的产品摆在一排货架上,这些商品的被编号为1N,他采取如下方法:
·先把1号商品放入货架,这时货架中只有这一个商品;
·再将2
N号商品依次放入货架,编号为 i 的商品会被摆在编号为1i-1 中某个商品(即已摆好商品)的左边或右边;
·从货架中移去M(M<N)个商品,其他商品的摆放顺序不变。在所有商品按照上述方法全部摆好之后,员工需要统计从左到右所有商品的编号。
输入格式
·第1行:一个正整数N,表示有N个商品。
·第2
N行:每行包括两个整数 k,p,p为0或者1。 如果p=0表示将 i 号商品放在 k 号商品的左边,p=1 则表示摆在右边
·第N+1行:一个正整数M,表示移去的商品数目。
·接下来的M行:每行一个正整数 x,表示将 X号商品从货架中移去,如果 x 号商品已经不再货架中,则忽略这一指令。
输出格式
1行,包含最多N-1个空格隔开的正整数,表示了货架上从左到右商品的编号,行末换行且无空格。
数据规模
N,M≤100000

  • 写回答

2条回答 默认 最新

  • 关注

    运行结果如下(“----链表数据----”这一句在代码中已经注释掉了):

    img

    代码:

    #include <iostream>
    using namespace std;
    
    typedef struct _data 
    {
        int index;
        struct _data* next;
    }StNode;
    
    int main()
    {
        StNode* head,*ph,*th;
    
        //创建链表
        head = new StNode; //头结点
        ph = new StNode; //编号为1的节点
        ph->index = 1;
        ph->next = 0;
        head->next = ph;
    
        int n;
        cin >> n; //输入n的值
        for(int i=1;i<n;i++)
        {
            th = new StNode;
            th->index = i+1;
            th->next = 0;
            //输入k 和 p
            int k,p;
            cin>>k>>p;
            
            if(p==0)//放在k左边
            {
                ph = head;
                while(ph->next)
                {
                    if(ph->next->index == k)
                    {
                        th->next = ph->next;
                        ph->next = th;
                        break;
                    }
                    else
                        ph = ph->next;
                }
                
            }else
            {
                //放在k右边
                ph = head->next;
                while(ph)
                {
                    if(ph->index == k)
                    {
                        th->next = ph->next;
                        ph->next = th;
                        break;
                    }else
                        ph = ph->next;
                }
            }
        }
        //输入m
        int m;
        cin >> m;
        for (int i=0;i<m;i++)
        {
            int x;
            cin >> x; //输入需要删除的编号
            ph = head;
            while(ph->next)
            {
                if(ph->next->index == x)
                {
                    th = ph->next;
                    ph->next = th->next;
                    free(th);
                    break;
                }else
                    ph = ph->next;
            }
        }
    
        //显示链表
        //cout << "----链表数据:----"<<endl; //这一句注释掉就可以了
        ph = head->next;
        int flag = 0;
        while(ph)
        {
            if(flag == 0)
            {
                cout << ph->index ; //第一个只输出值
                flag = 1;
            }
            else
                cout <<" " << ph->index; //从第二个开始,先输出一个空格,然后再输出值
            ph = ph->next;
        }
    
        //释放空间
        while(head)
        {
            ph = head->next;
            free(head);
            head = ph;
        }
        head = 0;
        ph = 0;
        th = 0;
        return 0;
    }
    
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 4月15日
  • 已采纳回答 4月7日
  • 创建了问题 3月11日

悬赏问题

  • ¥15 BP神经网络控制倒立摆
  • ¥20 要这个数学建模编程的代码 并且能完整允许出来结果 完整的过程和数据的结果
  • ¥15 html5+css和javascript有人可以帮吗?图片要怎么插入代码里面啊
  • ¥30 Unity接入微信SDK 无法开启摄像头
  • ¥20 有偿 写代码 要用特定的软件anaconda 里的jvpyter 用python3写
  • ¥20 cad图纸,chx-3六轴码垛机器人
  • ¥15 移动摄像头专网需要解vlan
  • ¥20 access多表提取相同字段数据并合并
  • ¥20 基于MSP430f5529的MPU6050驱动,求出欧拉角
  • ¥20 Java-Oj-桌布的计算