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

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

专业_10软件工程2班___姓名___李芳云号1067001085日期__3。27__

课程名称数据结构实验室名称X2407

实验名称线性表及其应用

指导教师吴福英成绩

一、实验目的

1.学会定义单链表的结点类型，实现对单链表的一些基本操作和具体的函数定义，

了解并掌握单链表的类定义以及成员函数的定义与调用。

2.掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。

二、实验要求

1．预习C语言中结构体的定义与基本操作方法。

2．对单链表的每个基本操作用单独的函数实现。

3．编写完整程序完成下面的实验内容并上机运行。

4．整理并上交实验报告。

三、实验内容

1．构造一个单链表L，其头结点指针为head，编写程序实现将L逆置。（即最后

一个结点变成第一个#includestdio.h

#includemalloc.h

#includeslnklist.h

voidmain()

{

intx;

node*L;

L=init();

printf(enterdigtials:);

scanf(%d,x);

while(x!=-1)

{

L=insert(L,x,0);

scanf(%d,x);

}

printf(outputnewdigtials:);

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-infop2-info)

{

p1=p2;

p2=p2-next;

}

q1-next=p2;

p1-next=q1;

p1=q1;

q1=q2;

q2=q2-next;

}

returnhead2;

}

合并思想是：程序需要3个指针：pa、pb、pc，其中pa，pb分别指向La表与

Lb表中当前待比较插入的结点，pc指向Lc表中当前最后一个结点。依次扫描La和

Lb中的元素，比较当前元素的值，将较小者链接到*pc之后，如此重复直到La或Lb

结束为止，再将另一个链表余下的内容链接到pc所指的结点之后。

3、设单链表L是一个递减有序表，试写一算法将X插入其中后仍保持L的有序

node*charumyhead(node*head,intx)

{

node*p,*q,*pre;

pre=head;

q=head-next;

p=(node*)malloc(sizeof(node))；