任务描述
删除链表的结点时，有时候不知道结点在哪，只知道结点数据的特征，如删除成绩低于60的学生结点、删除学号为20160903的学生等。本关要求按照数据输入的顺序构建一个线性表，然后输入待删除节点数据信息，在链表中查找符合该信息的节点，并删除；若不存在符合该数据信息的节点，则不操作。
编程要求
本关的编程任务是补全step5/deletehas.h文件中deletehas函数，以实现删除线性表指定位置结点的要求。 // 函数deleteHas：删除链表中data域为x的第一个节点，若不存在该节点，则操作 // 参数：h-链表头指针，x-结点包含的数据 // 返回值：删除结束后链表首结点地址 node * deleteHas(node * h, int x);
相关知识
程序可以分为两步： 1、利用循环顺序查找值为x的节点的**前驱节点**，并用指针P指向该前驱节点，若不存在值为x的节点，则前驱节点指针P为空； 2、前驱节点指针P不为空，则删除值P指针指向的节点的后继节点，删除时注意释放节点空间。
评测说明
本关中包含三个文件分别是： step5/deleteHas.h ：此文件为学员文件，包含尾插法构建链表的函数实现。 step5/linkList.h：此文件包含链表常见操作的说明与实现，引用了deleteHas.h step5/test.cpp：此文件为评测文件（含main函数），引用“linkList.h”。 （上述三个文件可通过点击在代码取的右上角文件夹中的step5文件夹中查看） (注意：本关所实现链式线性表为带头结点的单链表) 以下是平台对step5/test.cpp的样例测试集：
输入输出说明
输入n(1<=n<=100),然后输入n个整数，最后输入待删除元素x,按元素输入书顺序删除首个x元素（若不存在则不删除），输出剩余元素，如下所示：（注意：链表的输出函数已经实现，详情请阅读step5文件夹中的文件。）
测试输入： 5 2 3 8 5 1 2 预期输出： List: 3 8 5 1
测试输入： 6 9 8 7 6 5 4 6 预期输出： List: 9 8 7 5 4
test.cpp
#include "linkList.h" int main() { int n, i, num; node* t; node* head = new node;// 带头结点单链表,头结点指针head head->next = NULL; // 头结点head->next==NULL，链表为空 //输入结点数 cin >> n; for (i = 0; i < n; i++) { //为新节点动态分配空间 t = new node; cin >> t->data; //输入结点数据 t->next = NULL; //结点指针域值为空 //按输入顺序构建链表 head = insertTail(head, t); } //输入要删除结点包含的数据 cin >> num; //删除包含num的结点 head = deleteHas(head, num); //输出链表 printList(head); //删除结点，释放空间 delList(head); return 0; }
linkList.h
#include <iostream> using namespace std; // 定义结点结构 struct node { int data; // 数据域 node* next; // 指针域,指向下一个结点 }; // 函数deleteHas：删除链表中data为x的结点，如果有多个这样的结点，只删除第一个,若不存在data为x的节点，则不操作 // 参数：h-链表头指针，n-结点包含的数据 // 返回值：删除结束后链表首结点地址 node* deleteHas(node* h, int x); // 函数insertTail：链表尾部插入 // 参数：h-链表头指针，t-指向要插入的结点 // 返回值：插入结点后链表的头结点地址 node* insertTail(node* h, node* t); // 函数printList：输出链表，每个数据之间用一个空格隔开 // 参数：h-链表头指针 void printList(node* h); // 函数delList：删除链表，释放空间 // 参数：h-链表头指针 void delList(node* h); #include "deleteHas.h" //函数delList：删除链表，释放空间 //参数：h-链表头指针 void delList(node* h) { node* p = h; //指针p指向头结点，第一个要删除的结点 while (p) //这个结点是存在的 { h = h->next; //头指针h指向下一个结点（下一个结点的地址存在当前结点的指针域中，即h->next中 delete p; //删除p指向的结点 p = h; //p指向当前的头结点，即下一个要删除的结点 } } //函数printList：输出链表，每个数据之间用一个空格隔开 //参数：h-链表头指针 void printList(node* h) { cout << "List:"; h = h->next; while (h) {// h为真，即h指向的结点存在，则输出该结点的数据 cout << " " << h->data; // 输出结点数据 h = h->next; // 将该结点的指针域赋值给h，h就指向了下一个结点 } cout << endl; // 输出换行符 } node* insertTail(node* h, node* t) { // 请在此添加代码，补全函数insertTail /********** Begin *********/ node* p = h; // 让p指向最后一个结点 while (p->next) p = p->next; p->next = t; // 让最后一个结点的指针域指向结点t t->next = NULL; // 链表尾指针置为NULL return h; // 返回第一个结点的地址（即链表头指针） /********** End **********/ }
deleteHas.h
// 函数deleteHas：删除链表中data为x的结点，如果有多个这样的结点，只删除第一个 // 参数：h-链表头指针，n-结点包含的数据 // 返回值：删除结束后链表首结点地址 node* deleteHas(node* h, int n) { // 请在此添加代码，补全函数deleteHas /********** Begin *********/ node *p = NULL, *q = h; // p为要删除结点的前结点，q指向要删除结点 while(q) {// h为真，即h指向的结点存在 if(q->data == n) break; // 找到了 if(q->next == NULL) // 后面没有结点了，没有结点满足条件 return h; // 不删除，直接返回 // 继续往后找，两个指针一起后移 p = q; q = q->next; } // 删除q指向的结点 if(p == NULL) // 删除头结点 { h = q->next; // 下一个结点变成头结点 delete q; // 删除结点 return h; } // 不是头结点 p->next = q->next; // 把q指向结点的指针域（q后面结点的地址）赋值给p指向结点的指针域 return h; /********** End **********/ }