江西师范大学软件学院学生实验报告.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->info>p->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->info<m->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;
// free(r);
// }
// return head;
p=head->next;
q=p;
while(p)
{
r=p;
q=p->next;
while(q)
{
while(q &&q->info!=p->info)
{
r=q;
q=q->next;
}
if(q)
{
r->next=q->next;
free(q);

}
q=r->next;
}
p=p->next;
q=p;
}
return head;
}使所得的结果表中各结点值均不相同。
6．(选做题) 多相式相加问题:例如
A(x)=7+3x+9x8+5x17
B(x)=8x+22x7-9x8
实现策略：

四、思考与提高
1．如果上面实验内容2中合并的表内不允许有重复的数据该如何操作？
2．如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb，Lc，使得Lb中只含La表中奇数结点，Lc中含有La表