非递减有序插入

#includestdio.h#includestdlib.htypedefstructnode{intdata;node*next;}Linklist;Linklist*Lcreat(){//创建链表Linklist*L,*p,*S,*pre;inta;L=(Linklist*)malloc(sizeof(Linklist));L-next=NULL;printf(请输入一整型序列，并以0结束!\n);scanf(%d,&a);while(a!=0){S=(Linklist*)malloc(sizeof(Linklist));S-data=a;p=L-next;pre=L;while(p!=NULL){//查找增加结点的插入位置if(a=p-data){pre-next=S;S-next=p;break;}else{pre=p;p=p-next;}}if(p==NULL){//增加结点的数值最大或链表中只有头结点时pre-next=S;S-next=NULL;}scanf(%d,&a);}returnL;}Linklist*Linsert(Linklist*L,intx){//插入数值为x的结点Linklist*p,*pre,*S;p=L-next;pre=L;S=(Linklist*)malloc(sizeof(Linklist));S-data=x;while(p!=NULL){//查找数值为x的结点的插入位置if(x=p-data){pre-next=S;S-next=p;break;}else{pre=p;p=pre-next;}}if(p==NULL){pre-next=S;S-next=NULL;}returnL;}voidLout(Linklist*L){//链表输出Linklist*p;p=L-next;printf(链表输出：);while(p!=NULL){printf(%d\t,p-data);p=p-next;}printf(\n);}voidmain(){Linklist*L,*q;inta;L=Lcreat();printf(链表创建);Lout(L);printf(请输入要插入的数值：);scanf(%d,&a);q=Linsert(L,a);printf(插入一个数值后);Lout(q);}问题分析：本程序要求实现在一个非递减有序链表中插入一个结点，并且插入后的链表仍非递减有序，为完成上述功能，需要解决的关键问题是：创建一个非递减有序链表和将待插结点插入非递减有序链表过程。概要设计：①创建链表，每当准备曾加一个结点时，将该结点的数值与已建的非递减有序链表中结点的数值进行比较，将它插入准确位置，使链表非递减有序。②将待查结点的数值与非递减有序链表中结点的数值进行比较，若比较到比一个结点的数值小，即将待插结点插到该结点前。详细设计：①创建非递减有序链表的关键操作是边增加结点边插入排序。②每当增加一个结点时，将该结点的数值与已建的非递减有序链表中结点数值进行比较，若已建链表只有头结点，则直接将该结点插入头结点后面。若已建链表有多个结点，当该结点数值最大时，将该结点插入尾结点后面，否则插入比该结点数值大的第一个结点的前面。③插入值为x的结点的步骤同②。调试分析及小结：错误：在创建非递减链表将结点插入非递减链表的过程中，当找到待插入结点的准确位置时，将链表插入，然后继续从键盘读取数据，执行上述操作。源代码：while(p!=NULL){if(a=p-data){pre-next=S;S-next=p;}else{pre=p;p=p-next;}}调试时出现死循环。错误分析及改正：上面程序中，若执行if语句，则即找到待插结点的插入位置。当执行完if后程序并没跳出此次查找插入位置循环（while（...）），因此导致死循环。据此，在if语句中加入break。小结：通过本次实验，了解了正确地设置循环条件和判断条件会使程序更容易地编译调试，同时也不会让自己陷入逻辑胡同中。