问答题 单链表
   实验目的:
   (1)熟练掌握线性表的单链式存储结构及在其上实现线性表的各种基本运算的方法。
   (2)掌握和理解本实验中出现的一些基本的C语言语句。
   (3)体会算法在程序设计中的重要性。
   实验内容:
   (1)设计一算法,逆置带头结点的动态单链表head。要求利用原表的结点空间,并要求用尽可能少的时间完成。
   (2)设有两个按元素值递增有序的单链表A和B,编一程序将A表和B表归并成一个新的递增有序的单链表C(值相同的元素均保留在C表中),并要求利用原表的空间存放C。
【正确答案】(1)
   #define NULL'\0'
   #define DATATYPE2 char
   typedef struct node
   {DATATYPE2 data;
       struct node*next;
   )LINKLIST;    /*单链表类型定义*/
   LINKLIST*init()    /*单链表初始化函数*/
   {LINKLIST*head;
       head=(LINKLIST*)malloc(sizeof(LINKLIST));
       head->next=NULL;
       return head;
   }
   LINKLIST*creat()    /*尾插法建立动态单链表head函数*/
   {LINKLIST*head,*p,*q;    /*q是尾指针*/
       char n;
       head=init();
       q=head;    /*初始时尾指针指向头结点*/
   scanf("/%c",&n);
   while(n!='$')    /*输入$单链表结束*/
   {p=(LINKLIST*)malloc(sizeof(LINKLIST));
           p->data=n;
           p->next=q->next;
           q->next=p;
           q=p:    /*q始终指向最后一个结点*/
           scanf("/%c",&n);
       }
       return head;
   }
   void rev(head)    /*逆置单链表函数*/
   LINKLIST*head;
   {LINKLIST*p,*q;
       p=head->next;    /*p指针用来下移结点*/
       head->next=NULL;
       while(p!=NULL)
       {  q:p;    /*q指向待插入结点,头插法插入*/
           p=p->next;
           q->next=head->next;
           head->next=q*
       }
   }
   void print(head)    /*输出单链表head中的结点函数‘/
   LINKLIST*head;
   {LINKLIST*p;
       p=head->next;
       while(p!=NULL)
       {printf("/%4c",p->data);
           p=p->next;
       }
   }
   main()
   {LINKLIST*head;
       head=creat();    /*调用建立单链表函数*/
       rev(head);    /*调用逆置单链表函数*/
       print(head);    /*调用输出单链表函数*/
   }
   (2)
   #define NULL 0
   #define DATATYPE2 int
   typedef struct node
   {DATATYPE2 data;
       struct node*next;
   }LINKLIST;
   LINKLIST*init()    /*单链表初始化函数*/
   {LINKLIST*head;
       head=(LINKLIST*)malloc(sizeof(LINKLIST));
       head->next=NULL;
       return head;
   }
   LINKLIST*creat()    /*尾插法建立动态单链表函数*/
   {LINKLIST*head,*p,*q;
       int n;
       head=init();
       q=head;
       scanf("/%d",&n);
       while(n!=0)    /*输入0单链表结束*/
       {  p=(LINKLIST*)malloc(sizeof(LINKLIST));
           p->data=n;
           p->next=q->next;
               q->next=p;
           q=p;
           scanf("/%d",&n);
       }
   return head;
   }
   LINKLIST*join(LINKLIST*A,LINKLIST*B)    /*两个单链表归并函数*/
   {LINKLIST*p1,*p2,*q,*r,*c;
       p1=A->next;
       p2=B->next;
       C=A;
       C->next=NULL;
       r=C;
       while((p1!=NULL)&&(p2!=NULL))
       {  if(p1->data<p2->data)    /*pl所指结点*q准备插入+/
             {q=p1;p1=p1->next;}
           else    /*p2所指结点*q准备插入*/
             {q=p2;p2=p2->next;}
           q->next=r->next;    /*尾插法插入q所指结点*/
           r->next=q;
           r=q;
   }
   while(p1!=NULL)    /*若A表未扫完,依次把它的结点插入到C表尾部*/
   {  q=p1;p1=p1->next;
       q->next=r->next;
           r->next=q;
           r=q;
       }
       while(p2!=NULL)    /*若B表未扫完,依次把它的结点插入到C表尾部*/
       { q=p2;p2=p2->next;
           q->next=r->next;
           r->next=q;
           r=q;
       }
       return C;
   }
   void print(head)    /*输出单链表中的结点函数*/
   LINKLI ST*head;
   {LINKLIST*p;
       p=head->next;
       while(p!=NULL)
       {printf("/%4d",p->data);
           p=p->next;
       }
   }
   main()
   {LINKLIST*A,*B,*C;
       A=creat();    /*调用函数建立单链表A*/
       B=creat();    /*调用函数建立单链表B*/
       c=join(A,B);    /*调用归并函数*/
       print(C);    /*输出归并后的单链表C中的结点*/
   }
【答案解析】