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

Question

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

Answer 1

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

代码：

#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;
}