数据结构C语言单链表的归并实验报告.docx

一、实验目的1．掌握单链表的基本操作：插入、删除、查找以及表的合并等运算。掌握运用C语言上机调试单链表的基本方法。二、实验任务2. 假设有两个按数据元素值递增有序排列的线性表A和B，均以单链表作为存储结构。编写算法将A表和B表归并成一个按元素值递减（即非递增有序，允许值相同）排列的线性表C，并要求利用原表（即A表和B表）节点空间存放表C 三、程序流程图线性表A线性表B定义头指针p,q定义变量指针 rp-dateq-datelast-next=plast-next=qp-next=s结束程序流程图r=plast=rr=p p=p-nextlast=A last-next= NULLyesno四、测试过程及结果五、总结1．程序特点：最小化、模块化、while循环。单链表特点：动态分配内存、必须从已知指针逐一查找数据、通过改变数据间的链接改变顺序。附录 程序清单#includestdio.h#includestdlib.hstruct node{int date;struct node *next;};typedef struct node NODE;void ADD(NODE *A,NODE *B){NODE *p,*q,*r,*last;p=A-next;q=B-next; last=A; last-next= NULL; while(pq){ if(p-dateq-date){ r=p; p=p-next; } else{ r=q; q=q-next; } r-next=last-next; last-next=r; last=r; } if(p)last-next=p; elselast-next=q; B-next =NULL;}void creatlink1(NODE *A){NODE *s,*p=A;int num;scanf(%d,num);while(num!=0){s=(NODE*)malloc(sizeof(NODE));s-date=num;p-next=s;p=s;scanf(%d,num);}p-next=NULL;}void creatlink2(NODE *B){NODE *s,*p=B;int num;scanf(%d,num);while(num!=0){s=(NODE*)malloc(sizeof(NODE));s-date=num;p-next=s;p=s;scanf(%d,num);}p-next=NULL;}void reverse(NODE *A){NODE *p,*q,*r;if(A-next==NULL||A-next-next==NULL){return;}else if(A-next-next-next==NULL){A-next-next-next=A-next;A-next=A-next-next;A-next-next-next = NULL;}else{p = A-next;q = p-next;r = q-next;p-next = NULL; while(r){q-next = p;p = q;q = r;r = r-next;}q-next = p;A-next = q;}}void disp(NODE *A) { NODE *p=A-next; if(A-next==NULL) printf(the linklist is empty!\n); else { printf(output the data:\n); while(p!=NULL) {printf(%5d,p-date); p=p-next; } } printf(\n); }void main(){NODE *A,*B;A=(NODE*)malloc(sizeof(NODE));printf(输入A以0结尾:\n);creatlink1(A); B=(NODE*)malloc(sizeof(NODE));printf(输入B以0结尾:\n);creatlink2(B);ADD(A,B);reverse(A);disp(A); }