1662_基于列表的插入操作

定义列表List的数据类型如下：

#define MAX_SIZE 100000

/// 节点基础数据类型
typedef struct Node {
   int  id;  /// 员工编号，唯一
   char  name[20];  /// 员工名字
   int  succ;  /// 本节点的下一个元素所在位置的下标
   int  pred;  /// 本节点的上一个元素所在位置的下标
} mytype;

typedef struct {
   mytype data[ MAX_SIZE ];  /// 列表元素存放的数组
   bool used[ MAX_SIZE ];   /// 单元是否被占用的标记
   int head, tail;  /// 首元素的下标位置，尾元素的下标位置
   int _size;  /// 列表元素的实际个数
} mylist;

需要用到的函数原型如下：

void init( mylist &L )  /// 初始化列表L

insert( mylist &L, int p, mytype e )  /// 在列表L的第p个位置，插入一个节点e

traverse( mylist &L ) /// 遍历列表L

第一行是一个正整数n，表示要插入n个节点。( 0 < n < 100000 ）

接下来n行，每行是一个非负整数 p 、一个非负整数id 和 一个字符串str ，表示在列表的第p个位置插入一个节点，节点的员工编号是id、姓名是str 。员工姓名字符串不含空格，0 < |str| < 20

当 p ≥ _size 时，表示将本节点插在列表末尾。

从位置 0 到 _size-1 ，输出列表元素，一个一行：先输出员工id，再输出员工名字。

5
0 1 Tom
0 2 Jack
3 3 Alice
1 4 Bob
3 5 Apple

2 Jack
4 Bob
1 Tom
5 Apple
3 Alice