数据结构经典案例

安康学院电子与信息工程系付争方1数据结构双语教学课程第二章链表一．单链表的建立，输出，插入和删除#includestdlib.hstructnode{intdata;structnode*next;};structnode*create()/*用头插法创建一个链表*/{intx;structnode*head,*p;head=(structnode*)malloc(sizeof(structnode));/*建立头结点*/head-next=NULL;scanf(%d,&x);while(x!=-999){p=(structnode*)malloc(sizeof(structnode));p-data=x;p-next=head-next;/*将p放在头结点之后*/head-next=p;scanf(%d,&x);}return(head);}voidoutline(structnode*h)/*输出一个链表*/{structnode*p;p=h-next;printf(\n);while(p!=NULL){printf(%5d,p-data);p=p-next;}}voidinsert(structnode*h,intx,inty)/*将y插到x后面*/{structnode*p,*s;p=h-next;while(p-data!=x&&p!=NULL)p=p-next;s=(structnode*)malloc(sizeof(structnode));s-data=y;s-next=p-next;p-next=s;}voiddelete(structnode*h,intx)/*删除链表中数据为x的结点*/{structnode*p,*s;p=h-next;while(p-data!=x&&p!=NULL)p=p-next;s=p-next;p-next=s-next;free(s);}main(){inta,b;structnode*h;printf(inputa，b:);scanf(%d%d,&a,&b);h=create();outline(h);insert(h,a,b);outline(h);delete(h,a);outline(h);}安康学院电子与信息工程系付争方2数据结构双语教学课程二、数组的插入和删除#includestdio.h#includestdlib.h#definen100voidinsert(inta[],inti,inty,intm){intj;for(j=m;ji;j--)a[j]=a[j-1];a[i]=y;m++;}voiddelate(inta[],inti,intm){intj;for(j=i;jm-1;j++)a[j]=a[j+1];}main(){inta[n];intm=1;intx,y,b,i=0,k;printf(inputx:);scanf(%d,&x);while(x!=-999){a[i]=x;i++;m++;scanf(%d,&x);}i=0;printf(inputthevalueofinsert);scanf(%d%d,&k,&y);insert(a,k,y,m);for(i=0;im;i++)printf(%d,a[i]);printf(inputthevalueofdelete);scanf(%d,&i);delate(a,i,m);for(i=0;im-1;i++)printf(%d,a[i]);}三、对无序链表排序#includestdlib.h#includestdio.hstructnode{intdata;structnode*next;};voidcreate(structnode*head)/*尾插法创建链表*/{structnode*p,*r=head;intx;scanf(%d,&x);while(x!=-999){p=(structnode*)malloc(sizeof(structnode));p-data=x;p-next=NULL;r-next=p;r=p;scanf(%d,&x);}}voidoutline(structnode*head)/*输出链表*/{structnode*p=head-next;printf(\n);while(p!=NULL){printf(%5d,p-data);p=p-next;}}voidarrange(structnode*head)/*对无序链表排序*/{structnode*q,*r,*p,*u;p=head-next;head-next=NULL;while(p!=NULL)安康学院电子与信息工程系付争方3数据结构双语教学课程{r=head;q=p-next;while(q!=NULL&&q-data=p-data){r=q;q=q-next;}u=p-next;p-next=r-next;r-next=p;p=u;}}main(){structnode*head;head=(structnode*)malloc(sizeof(structnode));head-next=NULL;create(head);outline(head);printf(outputarrange:);arrange(head);outline(head);}四、将两个有序单链表合并，并保持它的有序性.#includestdlib.h#includestdio.hstructnode{intdata;structnode*next;};voidcreate(structnode*head)/*尾插法创建链表*/{structnode*p,*r=head;intx;scanf(%d,&x);while(x!=-999){p=(structnode*)malloc(sizeof(structnode));p-data=x;p-next=NULL;r-next=p;r=p;scanf(%d,&x);}}voidoutline(structnode*head)/*链表的输出*/{structnode*p=head-next;printf(\n);while(p!=NULL){printf(%5d,p-data);p=p-next;}}voidmergelist(structnode*head1,structnode*head2)/*将两个有序链表合并*/{structnode*p,*q,*r;p=head1-next;q=head2-next;r=head1;while(p!=NULL&&q!=NULL){if(p-data=q-data){r-next=p;r=p;p=p-next;}else{r-next=q;r=q;q=q-next;}}if(q==NULL)r-next=p;elser-next=q;安康学院电子与信息工程系付争方4数据结构双语教学课程}main(){structnode*head1,*head2;head1=(structnode*)malloc(sizeof(structnode));head2=(structnode*)malloc(sizeof(structnode));head1-next=NULL;head2-next=NULL;create(head1);create(head2);printf(outputarrange:);mergelist(head1,head2);outline(head1);}五、（1）两个一元多项式相加#includestdlib.h#includestdio.hstructnode{intcoef,exp;structnode*next;};voidcreat(structnode*head)/*头插法创建链表*/{structnode*p;inti,j;printf(inputi,j:);scanf(%d,%d,&i,&j);while(i!=-999&&j!=-999){p=(structnode*)malloc(sizeof(structnode));p-coef=i;p-exp=j;p-next=head-next;head-next=p;scanf(%d,%d,&i,&j);}}voidoutline(structnode*head)/*链表的输出*/{structnode*p=head-next;while(p!=NULL){printf(%d,%-5d,p-coef,p-exp);p=p-next;}}voidpadd(structnode*head1,structnode*head2)/*两个一元多项式相加*/{structnode*p=head1-next,*q=head2-next,*r;if(p-exp=q-exp){r=p;p=p-next;free(head2);}else{r=q;q=q-next;free(head1);}while(p!=NULL&&q!=NULL){if(p-exp==q-exp){p-coef=p-coef+q-coef;if(p-coef!=0){r=p;p=p-next;q=q-next;}}elseif(p-expq-exp){安康学院电子与信息工程系付争方5数据结构双语教学课程r-next=p;r=p;p=p-next;}else{r-next=q;r=q;q=q-next;}}if(p==NULL)r-next=q;elser-next=p;}main(){structnode*head1,*head2;head1=(structnode*)malloc(sizeof(structnode));head2=(structnode*)malloc(sizeof(structnode));head1-next=NULL;head2-next=NULL;creat(head1);creat(head2);if(head1-next-exp=head2-next-exp){padd(head1,head2);printf(\noutput:);outline(head1);}else{padd(head1,head2);printf(\noutput:);outline(head2);}}（2）计算两个一元多项式之和放到第三个链表#includestdlib.hstructnode{intcoef,exp;structnode*next;};structnode*create()/*用头插法建立双链表*/{intx,y;structnode*head,*p;head=(structnode*)malloc(sizeof(structnode));/*建立头结点*/head-next=NULL;scanf(%d%d,&x,&y);while(x!=-999){p=(structnode*)malloc(sizeof(structnode));/*建立新结点*/p-coef=x;p-exp=y;p-next=head-next;head-next=p;scanf(%d%d,&x,&y);}return(head);}voidoutline(structnode*h)/*输出链表h*/{structnode*p;p=h-next;17787172522117)()()(9228)(5937)(xxxxBxAxCxxxxBxxxxA+++=+=−+=+++=安康学院电子与信息工程系付争方6数据结构双语教学课程printf(\n);while(p!=NULL){printf(%d%d**,p-coef,p-exp);p=p-next;}}s