为充分测试，该程序运行了5次，所用的测试输入数据分别为：
5 2 9 9 7 11 3 0
3 5 2 9 9 7 11 0
3 5 2 9 3 9 7 11 0
3 5 2 9 4 9 7 11 0
3 3 3 3 3 3 3 0
（5）编写make_list3()函数建立有序链表，使建立链表时，结点中的数据呈现升序。若输入为3 5 2 9 4 7 0，建立的链表为：
----参考解答----
#include
#include
using namespace std; struct Node { int data; struct Node *next; }; Node *head=NULL; void make_list3(); //建立有序链表，各结点由小到大 void out_list(); int main( ) { freopen("input.txt","r",stdin);//调试中用重定向方便 make_list3(); out_list(); return 0; } void make_list3() { int n; Node *t,*p,*q; //p用于指向新建立的结点, q指向链表尾部 cout<<"输入若干正数（以0或一个负数结束）建立链表："<
>n; while(n>0) { t=new Node; t->data=n; t->next=NULL; if(head==NULL) //是空链表，p作为第一个结点即可 head=t; else //插入p结点后，各结点应该保持有序 { if(n<=head->data) //新加入的结点应该为首结点 { t->next=head; head=t; } //应该找到合适的位置后，将结点插入 //此时，链表中至少已经有一个结点，且插入结点不是首结点 else { p=head; q=p->next; //p与q相邻，p更靠近q，插入位置将在p和q之间 while(q!=NULL&&n>q->data) //链表没有完且p结点比n小，一直往后找 { p=q; q=p->next; } if(q==NULL) //q为null，作为最后一个结点直接插入到p后即可 { p->next = t; } else //t插入到p和q之间 { t->next=q; p->next=t; } } } cin>>n; } return; } //输出所有的节点 void out_list() { Node *p=head; cout<<"链表中的数据为："<
data<<" "; p=p->next; } cout<
（6）编写函数void insert(int x)，将值为x的结点插入到由make_list3建立起来的有序链表中。
----参考解答1----
#include
#include
using namespace std; struct Node { int data; struct Node *next; }; Node *head=NULL; void make_list3(); //建立有序链表，各结点由小到大 void out_list(); void insert(int x); //将值为x的结点插入到有序链表中，使仍有序 int main( ) { freopen("input.txt","r",stdin);//调试中用重定向方便 make_list3(); out_list(); insert(15); out_list(); return 0; } void make_list3() { int n; Node *t,*p,*q; //p用于指向新建立的结点, q指向链表尾部 cout<<"输入若干正数（以0或一个负数结束）建立链表："<
>n; while(n>0) { t=new Node; t->data=n; t->next=NULL; if(head==NULL) //是空链表，p作为第一个结点即可 head=t; else //插入p结点后，各结点应该保持有序 { if(n<=head->data) //新加入的结点应该为首结点 { t->next=head; head=t; } //应该找到合适的位置后，将结点插入 //此时，链表中至少已经有一个结点，且插入结点不是首结点 else { p=head; q=p->next; //p与q相邻，p更靠近q，插入位置将在p和q之间 while(q!=NULL&&n>q->data) //链表没有完且p结点比n小，一直往后找 { p=q; q=p->next; } if(q==NULL) //q为null，作为最后一个结点直接插入到p后即可 { p->next = t; } else //t插入到p和q之间 { t->next=q; p->next=t; } } } cin>>n; } return; } void insert(int x) //将值为x的结点插入到有序链表中，使仍有序 { Node *t,*p,*q; //p用于指向新建立的结点, q指向链表尾部 t=new Node; t->data=x; t->next=NULL; if(head==NULL) //是空链表，p作为第一个结点即可 head=t; else //插入p结点后，各结点应该保持有序 { if(x<=head->data) //新加入的结点应该为首结点 { t->next=head; head=t; } //应该找到合适的位置后，将结点插入 //此时，链表中至少已经有一个结点，且插入结点不是首结点 else { p=head; q=p->next; //p与q相邻，p更靠近q，插入位置将在p和q之间 while(q!=NULL&&x>q->data) //链表没有完且p结点比n小，一直往后找 { p=q; q=p->next; } if(q==NULL) //q为null，作为最后一个结点直接插入到p后即可 { p->next = t; } else //t插入到p和q之间 { t->next=q; p->next=t; } } } return; } //输出所有的节点 void out_list() { Node *p=head; cout<<"链表中的数据为："<
data<<" "; p=p->next; } cout<
----参考解答2----
实际上，从程序整体上看，makelist3()可以直接调用insert(int x)实现，这样写出的程序合乎工程上的原则。这启示我们，用函数组织程序结构，应该成为一种意识。
#include
#include
using namespace std; struct Node { int data; struct Node *next; }; Node *head=NULL; void make_list3(); //建立有序链表，各结点由小到大 void out_list(); void insert(int x); //将值为x的结点插入到有序链表中，使仍有序 int main( ) { freopen("input.txt","r",stdin);//调试中用重定向方便 make_list3(); out_list(); insert(15); out_list(); return 0; } void make_list3() { int n; cout<<"输入若干正数（以0或一个负数结束）建立链表："<
>n; while(n>0) { insert(n);//调用insert，makelist简单