下面是一个建立动态链表的程序。阅读程序，在草稿纸上画出链表建立的过程，借此学会如何建立链表。然后按要求改造程序。
#include <iostream>using namespace std;struct Node{int data;//结点的数据struct Node *next; //指向下一结点};Node *head=NULL; //将链表头定义为全局变量，以便于后面操作void make_list(); //建立链表void out_list(); //输出链表 int main( ){make_list();out_list();return 0;}void make_list(){int n;Node *p;cout<<"输入若干正数（以0或一个负数结束）建立链表："cin>>n;while(n>0) //输入若干正数建立链表，输入非正数时，建立过程结束{p=new Node; //新建结点p->data=n;p->next=head; //新建的结点指向原先的链表头head=p; //链表头赋值为新建的节点，这样，新结点总是链表头cin>>n; //输入下一个数，准备建立下一个结点}return;}void out_list(){Node *p=head;cout<<"链表中的数据为："<<endl;while(p!=NULL){cout<<p->data<<" ";p=p->next;}cout<<endl;return;}运行结果：
在上面的程序基础上定义下面的函数，实现相应的功能。为简便起见，每编写一个函数，立刻在main函数中调用进行测试。
（1）编写make_list2()函数建立链表，使建立链表时，后输入的数据，将新输入的数字对应的结点放在链表末尾。若输入为3 5 2 9 4 7 0，建立的链表为：
（2）编写函数void search(int x)，输出链表中是否有值为x的结点。（3）编写函数delete_first_node()，删除链表中的第一个结点。/* *Copyright (c) 2015,烟台大学计算机学院 *All gight reserved. *文件名称：Demo.cpp *作者：邵帅 *完成时间：2015年3月2日 *版本号：v1.0*/#include <iostream>using namespace std;struct Node{int data;//结点的数据struct Node *next; //指向下一结点};Node *head=NULL; //将链表头定义为全局变量，以便于后面操作void make_list(); //建立链表void out_list();void make_list2(); //输出链表void delete_first_node();void search(int x);int main( ){int x;make_list2();out_list();cin>>x; //测试中输入一个链表中有的数字search(x);cin>>x; //测试中输入一个链表中没有的数字search(x);delete_first_node();out_list();return 0;}void make_list(){int n;Node *p;cout<<"输入若干正数（以0或一个负数结束）建立链表：";cin>>n;while(n>0) //输入若干正数建立链表，输入非正数时，建立过程结束{p=new Node; //新建结点p->data=n;p->next=head; //新建的结点指向原先的链表头head=p; //链表头赋值为新建的节点，这样，新结点总是链表头cin>>n; //输入下一个数，准备建立下一个结点}return;}void out_list(){Node *p=head;cout<<"链表中的数据为："<<endl;while(p!=NULL){cout<<p->data<<" ";p=p->next;}cout<<endl;return;}void make_list2(){int n;Node *p,*q; //p用于指向新建立的结点, q指向链表尾部cout<<"输入若干正数（以0或一个负数结束）建立链表："<<endl;cin>>n;while(n>0){p=new Node;p->data=n;p->next=NULL;if(head==NULL)head=p;elseq->next=p;q=p;cin>>n;}return;}void search(int x){//查找是否有值为x的结点Node *p=head;while(p!=NULL&&p->data!=x){p=p->next;}if(p!=NULL) //退出上一层循环一定是因为p->data==xcout<<"在链表中有值为"<<x<<"的结点"<<endl;elsecout<<"在链表中没有值为"<<x<<"的结点"<<endl;return;}void delete_first_node(){Node *p=head;if (p!=NULL){head = p->next;delete p;cout<<"删除了首结点."<<endl;}else{cout<<"空链表，不能删除."<<endl;}return;}运行结果：
（4）编写函数delete_node(int x)，删除结点值为x的结点。（5）编写make_list3()函数建立链表，使建立链表时，使结点中的数据呈现升序。若输入为3 5 2 9 4 7 0，建立的链表为：
（6）编写函数void insert(int x)，将值为x的结点插入到由make_list3建立起来的有序链表中。
/* *Copyright (c) 2015,烟台大学计算机学院 *All gight reserved. *文件名称：Demo.cpp *作者：邵帅 *完成时间：2015年3月2日 *版本号：v1.0*/#include <iostream>using namespace std;struct Node{int data;//结点的数据struct Node *next; //指向下一结点};Node *head=NULL; //将链表头定义为全局变量，以便于后面操作void make_list(); //建立链表void out_list();void make_list3(); //输出链表void delete_first_node();void search(int x);void delete_node(int x);void insert(int x);int main( ){int x;make_list3();out_list();insert(15);out_list();delete_node(3);out_list();return 0;}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 make_list3(){int n;Node *t,*p,*q; //p用于指向新建立的结点, q指向链表尾部cout<<"输入若干正数（以0或一个负数结束）建立链表："<<endl;cin>>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<<"链表中的数据为："<<endl;while(p!=NULL){cout<<p->data<<" ";p=p->next;}cout<<endl;return;}void make_list2(){int n;Node *p,*q; //p用于指向新建立的结点, q指向链表尾部cout<<"输入若干正数（以0或一个负数结束）建立链表："<<endl;cin>>n;while(n>0){p=new Node;p->data=n;p->next=NULL;if(head==NULL)head=p;elseq->next=p;q=p;cin>>n;}return;}void search(int x){//查找是否有值为x的结点Node *p=head;while(p!=NULL&&p->data!=x){p=p->next;}if(p!=NULL) //退出上一层循环一定是因为p->data==xcout<<"在链表中有值为"<<x<<"的结点"<<endl;elsecout<<"在链表中没有值为"<<x<<"的结点"<<endl;return;}void delete_node(int x){Node *p,*q;if (head==NULL)cout<<"空链表，不能删除";else{//要删除的恰是首结点（不排除连续有若干个结点值为x），while(head!=NULL&&head->data==x){p=head;head=head->next;delete p;}if(head!=NULL){p=head;q=p->next;while(q!=NULL){if(q->data==x)//q就是该删除的结点{p->next=q->next;delete q;}else//q不该删除，继续考察下一个{p=q;}q=p->next; //总是p的下一个结点}}}return;}运行结果：
『 不可能 』只存在於蠢人的字典里
