传说战国时期有位非常残暴的将军，他每天都会挑选出一至两名战俘，屠杀或者立即释放（仅在他心情非常好时）。挑选战俘时，将军会说一个“幸运”数字，编号离这个数字最近的战俘将被选出，永远地离开战俘营。因此，他的助手每天都要更新在押战俘名单。现在要编写一个程序，自动生成在押战俘名单。
函数接口定义：
Node *create(int n) ; Node* remove(Node *head, int k);
create函数建立一个长度为n的链表，链表中的结点依战俘编号严格从小到大排序（每个战俘的编号都是唯一的），返回链表的头指针。remove函数从链表中去除编号距离数字k最近的结点，第一个参数为头指针，返回值为头指针。
裁判测试程序样例：
#include<iostream>using namespace std;struct Node{ int num;//战俘编号 Node *next; };
/* 请在这里填写答案 */void display(Node* head){ cout<<head->num; if(head->next!=NULL){ cout<<' '; display(head->next); }else cout<<endl; }
int main() { int i,k,m,n; Node *head=NULL; cin>>n; head=create(n); cin>>m; for(i=0;i<m;i++){ cin>>k; head=remove(head, k); if(head==NULL) cout<<"ERROR"<<endl; else display(head); } return 0; }
输入样例：
10 1 3 5 7 9 2 4 6 8 10 3 5 2 2
输出样例：
1 2 3 4 6 7 8 9 10 1 3 4 6 7 8 9 10 4 6 7 8 9 10
说明：
输入10，说明开始一共有10个战俘，接下来一行数字，是各个战俘的编号。然后输入要考察的天数（输入3，说明一共考察3天），接下来是输入各天的幸运号。
（1）第1天幸运号为5,在链表中找到了编号为5的结点，直接删除。然后输出此时的链表
（2）第2天幸运号为2，在链表中找到了编号为2的结点，直接删除。然后输出此时的链表。
（3）第3天幸运号为2, 此时距离2最近的编号是1和3，将这两个结点后，然后输出此时的链表。
我的实现感觉有点繁琐，请高手指点
#include<iostream> using namespace std; struct Node { int num;//战俘编号 Node* next; }; /* 请在这里填写答案 */ Node* create(int n) { int nb; Node* head = new Node; head->next = NULL; Node * tail, * Ntmp,*Stmp; tail = head; for (int i=0;i<n;i++) { cin >> nb; Ntmp = new Node; Ntmp->next = NULL; Ntmp->num = nb; Stmp = head; while (Stmp->next!=NULL) { if (Stmp->next->num < nb) { Stmp = Stmp->next; } else break; } tail= Stmp->next; Stmp->next = Ntmp; Ntmp->next = tail; } return head->next; } Node* remove(Node* head, int k) { Node* tmp,*tail; tail = head; if (head==NULL)//没有结点时 { return head; } if (tail->next == NULL)//只有一个结点 { head = NULL; delete tail; return head; } while (tail->next!=NULL) { if (tail->next->next != NULL) { if (tail->num >= k && tail == head)//处理头结点 { tmp = tail; head = tail->next; delete tmp; break; } else if (tail->next->num == k)//处理后续结点 { tmp = tail->next; tail->next = tail->next->next; delete tmp; break; } else if (k<tail->next->next->num && k>tail->next->num)//处理中间结点 { tmp = tail->next; tail->next = tail->next->next->next; delete tmp->next; delete tmp; break; } else if (tail==head&&k>tail->num&&k<tail->next->num)//处理头部开始的两结点 { tmp = tail; head=tail->next->next; delete tmp->next; delete tmp; break; } else tail = tail->next;//没有符合条件的，后移指针 } else if (tail->next->next == NULL)//只有两结点时 { if (tail->next->num<=k)//处理尾结点 { tmp = tail->next; tail->next = NULL; delete tmp; }else if (tail->num<k&&tail->next->num>k)//两个结点一起处理 { tmp = tail; head = NULL; delete tmp->next; delete tmp; break; }else if (tail->num>k)//处理前面结点 { tmp = tail; head = tail->next; delete tmp; break; } } } return head; } void display(Node* head) { cout << head->num; if (head->next != NULL) { cout << ' '; display(head->next); } else cout << endl; } int main() { int i, k, m, n; Node* head = NULL; cin >> n; head = create(n); cin >> m; for (i = 0; i < m; i++) { cin >> k; head = remove(head, k); if (head == NULL) cout << "ERROR" << endl; else display(head); } return 0; }
