任务描述
线性表的结点是有序号的，包含n（1<=n<=100）个结点（不包括头结点）的线性表从链头到链尾的结点序号分别为1、2、……n。本关要求按照数据输入的顺序构建一个线性表，然后输入待删除结点编号i，删除第i个结点，并输出删除结点后的线性表元素。
编程要求
本关的编程任务是补全step4/deleteAt.h文件中deleteAt函数，以实现删除线性表指定位置结点的要求。 // 函数deleteAt：删除链表中序号为i的结点，如果i是非法序号(i<=0||i>n)则不做操作 // 参数：h-链表头指针，i-要删除结点的序号 // 返回值：删除结束后链表首结点地址 node* deleteAt(node* h, int i);
相关知识
结点的删除可以根据结点位置的需要注意3个问题：被删除结点位置合法性的检查、被删除结点的空间的释放、删除最后一个结点时的处理。
-
被删除顶点位置合法性的检查：n个结点的合法删除位置为1~n，若超出该范围，则链表保持不变。
-
被删除结点的空间的释放：当删除第i个顶点的时候，除了需要修改第i-1个顶点的指针之外，还要释放被删除顶点的存储空间，因此在修改第i-1个结点的指针域之前，应该先利用一个指针变量指向第i个结点，并在修改完第i-1个结点的指针域后，释放被删除顶点的存储空间。
-
删除最后一个结点时的处理：针对非循环单链表，当删除的第i个顶点为最后一个结点时，应该修改第i-1个顶点的指针域为空指针域。
评测说明
本关中包含三个文件分别是： step4/deleteAt.h ：此文件为学员文件，包含删除链表指定位置结点函数实现。 step4/linkList.h：此文件包含链表常见操作的说明与实现，引用了deleteAt.h step4/test.cpp：此文件为评测文件（含main函数），引用“linkList.h”。 （上述三个文件可通过点击在代码取的右上角文件夹中的step4文件夹中查看） (注意：本关所实现链式线性表为带头结点的单链表)
输入输出说明
输入n(1<=n<=100),然后输入n个整数，最后输入位置i（1<=i<=n）,按元素输入书顺序删除第i个元素后，输出剩余元素，如下所示：（注意：链表的输出函数已经实现，详情请阅读step4文件夹中的文件。）
测试输入： 5 2 4 6 8 1 1 预期输出： List: 4 6 8 1
测试输入： 5 1 2 3 4 5 6 预期输出： List: 1 2 3 4 5
test.cpp
#include "linkList.h" int main() { int n, i; 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 >> i; //在链表中删除序号为i的结点 head = deleteAt(head, i); //输出链表 printList(head); //删除结点，释放空间 delList(head); return 0; }
linkList.h
#include <iostream> using namespace std; // 定义结点结构 struct node { int data; // 数据域 node* next; // 指针域,指向下一个结点 }; // 函数deleteAt：删除链表中序号为i的结点，如果i是非法序号则不做操作 // 参数：h-链表头指针，i-要删除结点的序号 // 返回值：删除结束后链表头结点地址 node* deleteAt(node* h, int i); // 函数insertTail：链表尾部插入 // 参数：h-链表头指针，t-指向要插入的结点 // 返回值：插入结点后链表的头结点地址 node* insertTail(node* h, node* t); // 函数printList：输出链表，每个数据之间用一个空格隔开 // 参数：h-链表头指针 void printList(node* h); // 函数delList：删除链表，释放空间 // 参数：h-链表头指针 void delList(node* h); #include "deleteAt.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; // 输出换行符 } // 函数insertTail：链表尾部插入 // 参数：h-链表头指针，t-指向要插入的结点 // 返回值：插入结点后链表的头结点地址 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 **********/ }
deleteAt.h
// 函数deleteAt：删除链表中序号为i的结点，如果i是非法序号则不做操作 // 参数：h-链表头指针，i-要删除结点的序号 // 返回值：删除结束后链表头结点地址 node* deleteAt (node* h, int i) { // 请在此添加代码，补全函数deleteHas /********** Begin *********/ if(i<0) { return h; } node *p = NULL, *q = h; // 定位删除结点，试图让q指向要删除结点，p指向其前面的结点 for(int k = 0; k < i; k++) { if(q->next == NULL) // 后面没有结点了，序号非法 { return h; } p = q; q = q->next; } if(p) // p指向的结点存在，不是删除首结点 { // 删除q指向的结点，让p指向结点的指针域指向q的后续结点 p->next = q->next; // 释放空间 delete q; return h; } else // 删除首结点 { h = q->next; // 下一个结点成了首结点 // 释放空间 delete q; return h; } /********** End **********/ }