江西师范大学软件学院学生实验报告.doc

江西师范大学软件学院学生实验报告 专业_10软件工程2班___ 姓名___李芳云号1067001085 日期__3。27 __ 课程名称 数据结构 实验室名称 X2407 实验名称 线性表及其应用 指导教师 吴福英 成绩 一、 实验目的 1. 学会定义单链表的结点类型，实现对单链表的一些基本操作和具体的函数定义，了解并掌握单链表的类定义以及成员函数的定义与调用。 2. 掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。 二 、实验要求 1．预习C语言中结构体的定义与基本操作方法。 2．对单链表的每个基本操作用单独的函数实现。 3．编写完整程序完成下面的实验内容并上机运行。 4．整理并上交实验报告。 三、实验内容 1．构造一个单链表L，其头结点指针为head，编写程序实现将L逆置。（即最后一个结点变成第一个#include stdio.h #include malloc.h #include slnklist.h void main() { int x; node *L; L=init(); printf(enter digtials:); scanf(%d,x); while(x!=-1) { L=insert(L,x,0); scanf(%d,x); } printf(output new digtials:); display(L); printf(\n)；} 结点，原来倒数第二个结点变成第二个结点，如此等等。） 2 .构造两个带有表头结点的有序单链表La、Lb，编写程序实现将La、Lb合并成序单链表Lc。node *hebing(node *head1,node *head2) { node *q1,*q2,*p1,*p2; q1=head1-next; q2=head1-next-next; p1=head2; p2=head2-next; while(q2) { while(q1-info p2-info) { p1=p2; p2=p2-next; } q1-next=p2; p1-next=q1; p1=q1; q1=q2; q2=q2-next; } return head2; } 合并思想是：程序需要3个指针：pa、pb、pc，其中pa，pb分别指向La表与Lb表中当前待比较插入的结点，pc 指向Lc表中当前最后一个结点。依次扫描La和Lb中的元素，比较当前元素的值，将较小者链接到*pc之后，如此重复直到La或Lb结束为止，再将另一个链表余下的内容链接到pc所指的结点之后。 3、设单链表L是一个递减有序表，试写一算法将X插入其中后仍保持L的有序node *charumyhead(node *head,int x) { node *p,*q,*pre; pre=head; q=head-next; p=(node*)malloc(sizeof(node))； p-info=x; while(q q-infop-info) { pre=q; q=q-next; } p-next=q-next; q-next=p; return head; }性。 4、设计一个算法，对单链表按结点值从小到大对结点进行排序。 node *paixu(node *head) { node *q,*pre,*n,*m; q=head-next; head-next=NULL; while(q) { pre=head; n=head-next; m=q; q=q-next; while(n n-infom-info) { pre=n; n=n-next; } pre-next=m;; m-next=n; } return head; } 5、(选做题)写一算法将单链表中值重复的结点删除，node *delemyhead(node *head) { node *p,*q,*r; //for(p=head-next;p!=NULL;p=p-next) // for(q=head-next-next;q!=NULL;q=q-next) // if(p-info==q-info) // { // r=p-next; // p-next=r-next;