一个学校里老师要将班上 N 个同学排成一列,同学被编号为 1∼N,他采取如下的方法:
先将 1 号同学安排进队列,这时队列中只有他一个人;
2−N 号同学依次入列,编号为 i 的同学入列方式为:老师指定编号为 i 的同学站在编号为1∼(i−1) 中某位同学(即之前已经入列的同学)的左边或右边;
从队列中去掉 M 个同学,其他同学位置顺序不变。
在所有同学按照上述方法队列排列完毕后,老师想知道从左到右所有同学的编号。
输入格式
第 1 行为一个正整数 N(1≤N≤10^5),表示了有 N 个同学。
第 2∼N 行,第 i 行包含两个整数 k,p,其中 k 为小于 i 的正整数,p 为 0 或者 1。若 p 为 0,则表示将 i 号同学插入到 k 号同学的左边,p 为 1 则表示插入到右边。
第N+1 行为一个正整数 M(1≤M≤10 ^5),表示去掉的同学数目。
接下来 M 行,每行一个正整数 x,表示将 x 号同学从队列中移去,如果 x 号同学已经不在队列中则忽略这一条指令。
输出格式
一行,包含最多 N 个空格隔开的正整数,表示了队列从左到右所有同学的编号,行末换行且无空格。
输出时每行末尾的多余空格,不影响答案正确性
样例输入
4
1 0
2 1
1 0
2
3
3
样例输出
2 4 1
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
typedef struct student {
int id;
struct student* pNext;
}NODE, *PNODE;
PNODE create_list(void);
void insert_list(PNODE, int, int);
void traverse_list(PNODE);
void delete_list(PNODE, int);
int main() {
PNODE pHead = NULL;
pHead = create_list();
int m, x;
cin >> m;
for (int i = 0; i < m; i++) {
cin >> x;
delete_list(pHead, x);
}
traverse_list(pHead);
}
PNODE create_list(void) {
PNODE pHead = (PNODE) malloc (sizeof(NODE));
if (NULL == pHead) {
printf("head分配内存失败");
exit(-1);
}
PNODE pNew = (PNODE) malloc (sizeof(NODE));
if (NULL == pNew) {
printf("new分配内存失败");
exit(-1);
}
int i = 1;
pNew->id = i;
pHead->pNext = pNew;
pNew->pNext = NULL;
int n, pos, f;
cin >> n;
for (i = 2; i <= n; i++) {
scanf("%d %d", &pos, &f);
if (f == 0) {
insert_list(pHead, i, pos);
} else {
insert_list(pHead, i, pos+1);
}
}
return pHead;
}
void insert_list(PNODE pHead, int data, int pos) {
int i = 0;
PNODE p = pHead;
while (NULL != p && i < pos-1) {
p = p->pNext;
++i;
}
if (i > pos-1 || NULL == p) return;
PNODE pNew = (PNODE) malloc (sizeof(NODE));
if (NULL == pNew) {
printf("new分配内存失败");
exit(-1);
}
pNew->id = data;
PNODE q = p->pNext;
p->pNext = pNew;
pNew->pNext = q;
return ;
}
void delete_list(PNODE pHead, int num) {
int flag = 0;
PNODE p = pHead->pNext;
while (NULL != p) {
if (p->id == num) {
flag = 1;
break;
}
p = p->pNext;
}
if (!flag) return;
PNODE q = p->pNext;
p->pNext = p->pNext->pNext;
free(q);
return;
}
void traverse_list(PNODE pHead) {
PNODE p = pHead->pNext;
while (NULL != p) {
printf("%d ", p->id);
p = p->pNext;
}
cout << endl;
return;
}
输到最后一个三的时候程序就终止了我觉得可能是delete_list()函数里的问题,请大家帮忙看看哪里出错了