排序构建线性表（线性表实训）排序构建线性表（线性表实训

补全函数insertSort，实现将一个结点按结点数据data从小到大的顺序插入到一个有序链表中。根据插入结点data的大小，插入点可能是链表头、尾或者中间某个位置。
本关的实现可以分为两个步骤：

一是找到插入点；
二是插入结点。

相关知识如何找到插入点 【排序构建线性表（线性表实训）】插入点的定位可以使用两个指针（p和q），定位步骤如下图所示：

文章图片

上图中链表有4个结点，则共有5个可能的插入点。用两个指针首先定位第一个插入点（step1，p为NULL，q指向第一个结点），如果插入结点的data小于q指向结点的data，则就是该插入点（两个指针指向的结点之间），否则两个指针一起往后移动（step2）；定位第二个插入点，判断条件依然是插入结点的data是否小于q指向的结点的data，是则就是该插入点，否则两个指针往后平移（step3）；定位第三个插入点……直到最后当q指针为NULL时，说明插入结点的data比链表中所有数据都大，则插入点应该是链尾（第5个插入点）。插入点的定位操作可以很容易地用循环实现。
定位好插入点后，当p为NULL时，插入点是链表头部；当q为NULL时，插入点是链表尾部；否则，插入点为p和q指向的两个结点之间。
如何插入结点上述定位好插入点后，接下来是插入结点。对于头部插入和尾部插入的内容前两关已做过介绍，本关只介绍中间插入的情况，即将t指向的结点插入到p和q指向的两个结点之间。这种情况只需要让p指向结点的指针域指向t指向的结点，t指向结点的指针域指向q指向的结点即可。具体参见下面代码：

p->next = t; t->next = q;

#include //#include "linearList.h" using namespace std; // 定义结点结构 struct node { int data; // 数据域 node * next; // 指针域,指向下一个结点 }; // 函数insertSort：链表排序插入 // 参数：h-链表头指针，t-指向要插入的结点 // 返回值：插入结点后链表的首结点地址 node * insertSort(node *h, node *t); // 函数insertHead：链表头部插入 // 参数：h-链表头指针，t-指向要插入的结点 // 返回值：插入结点后链表的首结点地址 node * insertHead(node *h, node *t); // 函数printList：输出链表，每个数据之间用一个空格隔开 // 参数：h-链表头指针 void printList(node *h); // 函数insertTail：链表尾部插入 // 参数：h-链表头指针，t-指向要插入的结点 // 返回值：插入结点后链表的首结点地址 node *insertTail(node *h, node *t); // 函数delList：删除链表，释放空间 // 参数：h-链表头指针 void delList(node *h); int main() { int n,i; node *t; node *head=NULL; //头指针为NULL，表示线性表为空，结点数为0 //输入结点数 cin>>n; for(i=0; i>t->data; //输入结点数据 t->next=NULL; //结点指针域值为空 //调用函数插入结点，按data从小到大排序插入 head = insertSort(head, t); } //输出链表 printList(head); //删除结点，释放空间 delList(head); return 0; } //函数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:"; while(h) {//h为真，即h指向的结点存在，则输出该结点的数据 cout<<" "next; //将该结点的指针域赋值给h，h就指向了下一个结点 } cout<next=NULL; //链表尾指针置为NULL return t; //返回第一个结点的地址（即链表头指针） } //非空链表的情况 node *p=h; //让p指向最后一个结点 while(p->next) { p=p->next; } p->next = t; //让最后一个结点的指针域指向结点t t->next=NULL; //链表尾指针置为NULL return h; //返回第一个结点的地址（即链表头指针） } //函数insertHead：链表头部插入 //参数：h-链表头指针，t-指向要插入的结点 //返回值：插入结点后链表的首结点地址 node * insertHead(node *h, node *t) { t->next=h; return t; } node * insertSort(node *h, node *t) { node *p = NULL, *q = h; // 定位第一个插入点：链首 // 查找插入点 while(q && q->data < t->data) {// 两个指针并行后移 p = q; q = q->next; } // 插入链首 if(p == NULL) { t->next = h; return t; } // 插入链尾 if(q == NULL) { p->next = t; t->next = NULL; } // 插入p、q之间 t->next = q; p->next = t; return h; }