实验二单链表基本操作.docx
《实验二单链表基本操作.docx》由会员分享，可在线阅读，更多相关《实验二单链表基本操作.docx（15页珍藏版）》请在冰点文库上搜索。
实验二单链表基本操作
实验二单链表基本操作
一实验目的
1.学会定义单链表的结点类型，实现对单链表的一些基本操作和具体的函数定义，了解并掌握单链表的类定义以及成员函数的定义与调用。
2.掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。
二实验要求
1．预习C语言中结构体的定义与基本操作方法。
2．对单链表的每个基本操作用单独的函数实现。
3．编写完整程序完成下面的实验内容并上机运行。
4．整理并上交实验报告。
三实验内容
1．编写程序完成单链表的下列基本操作：
（1）初始化单链表La。
（2）在La中第i个元素之前插入一个新结点。
（3）删除La中的第i个元素结点。
（4）在La中查找某结点并返回其位置。
（5）打印输出La中的结点元素值。
2.构造两个带有表头结点的有序单链表La、Lb，编写程序实现将La、Lb合并成一个有序单链表Lc。
合并思想是：
程序需要3个指针：
pa、pb、pc，其中pa，pb分别指向La表与Lb表中当前待比较插入的结点，pc指向Lc表中当前最后一个结点。
依次扫描La和Lb中的元素，比较当前元素的值，将较小者链接到*pc之后，如此重复直到La或Lb结束为止，再将另一个链表余下的内容链接到pc所指的结点之后。
3．构造一个单链表L，其头结点指针为head，编写程序实现将L逆置。
（即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。
）
四思考与提高
1．如果上面实验内容2中合并的表内不允许有重复的数据该如何操作？
2．如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb，Lc，使得Lb中只含La表中奇数结点，Lc中含有La表的偶数结点？
1．编写程序完成单链表的下列基本操作：
（1）初始化单链表La。
（2）在La中第i个元素之前插入一个新结点。
（3）删除La中的第i个元素结点。
（4）在La中查找某结点并返回其位置。
（5）打印输出La中的结点元素值。
#include
#include
#include
#defineOK1
#defineERROR0
typedefintStatus;
typedefintElemType;
//定义存储结构
typedefstructLnode{
intdata;/*每个元素数据信息*/
structLnode*next;/*存放后继元素的地址*/
}LNode,*LinkList;
intmain（）
{
voidCreate_L（LinkList&L,intn）;
voidPrint_L（LinkListL）;
StatusListInsert_L（LinkList&L,inti,ElemTypee）;
StatusListDelete_L（LinkList&L,inti,ElemType&e）;
StatusFind_L（LinkListL,inte）;
LinkListLa;//创建单链表La
intn;
printf（"请输入链表La中的元素个数:
\n"）;
scanf（"%d",&n）;
Create_L（La,n）;//初始化单链表
printf（"现在La中的元素为:
\n"）;
Print_L（La）;
printf（"-------------------------------------\n\n"）;
printf（"现在准备插入元素，请输入插入位置及所插入元素的值\n"）;
inti,e;
scanf（"%d%d",&i,&e）;
ListInsert_L（La,i,e）;
printf（"插入后La中的元素为:
\n"）;
Print_L（La）;
printf（"-------------------------------------\n\n"）;
printf（"现在准备删除元素，请输入删除位置\n"）;
scanf（"%d",&i）;
ListDelete_L（La,i,e）;
printf（"删除后La中的元素为:
\n"）;
Print_L（La）;
printf（"-------------------------------------\n\n"）;
printf（"请输入所要查找元素的值:
\n"）;
scanf（"%d",&e）;
Find_L（La,e）;
printf（"所要查找元素的位置为:
%d\n",Find_L（La,e））;
}
voidCreate_L（LinkList&L,intn）
{
intj=1;
L=（LinkList）malloc（sizeof（Lnode））;
L->next=NULL;//先建立一个带头结点的单链线性表L
for（inti=n;i>0;--i）
{
LinkListp=（LinkList）malloc（sizeof（Lnode））;
printf（"请输入链表La中的第%d个元素:
\n",j++）;
scanf（"%d",&p->data）;
p->next=L->next;
L->next=p;
}//（逆序实现）
/*
LinkListq=L;
for（inti=1;i<=n;i++）
{
LinkListp=（LinkList）malloc（sizeof（Lnode））;
q->next=p;
p->next=NULL;
q=q->next;
printf（"请输入链表La中的第%d个元素:
\n",i）;
scanf（"%d",&p->data）;
}//（正序实现）
*/
}//初始化单链表
//输出单链表
voidPrint_L（LinkListL）
{
LinkListp;
p=L->next;
while（p）
{
printf（"%d",p->data）;
p=p->next;
}
printf（"\n"）;
}
//在单链表L的第i个位置前插入元素e
StatusListInsert_L（LinkList&L,inti,ElemTypee）
{
LinkListp=L;
intj=0;
while（p&&j{
p=p->next;++j;
}
if（!
p||j>i-1）returnERROR;
LinkLists=（LinkList）malloc（sizeof（LNode））;
s->data=e;s->next=p->next;
p->next=s;
returnOK;
}//ListInsert_L
//删除单链表L中第i个位置上的元素
StatusListDelete_L（LinkList&L,inti,ElemType&e）
{
LinkListp=L;
intj=0;
while（p->next&&j{
p=p->next;++j;
}
if（!
p->next||j>i-1）returnERROR;
LinkListq=p->next;p->next=q->next;
e=q->data;
free（q）;
returnOK;
}//LinkDelete_L
/*查找元素并返回位置*/
StatusFind_L（LinkListL,inte）
{
LinkListp=L->next;
intj=1;
while（p->data!
=e&&p->next）
{
p=p->next;
j++;
}
if（p->data==e）returnj;
else
{
printf（"无当前元素\n"）;
returnERROR;
}
if（!
p）
{
printf（"无当前元素\n"）;
returnERROR;
}
}//定位
2.构造两个带有表头结点的有序单链表La、Lb，编写程序实现将La、Lb合并成一个有序单链表Lc。
合并思想是：
程序需要3个指针：
pa、pb、pc，其中pa，pb分别指向La表与Lb表中当前待比较插入的结点，pc指向Lc表中当前最后一个结点。
依次扫描La和Lb中的元素，比较当前元素的值，将较小者链接到*pc之后，如此重复直到La或Lb结束为止，再将另一个链表余下的内容链接到pc所指的结点之后。
#include
#include
#include
#defineOK1
#defineERROR0
typedefintStatus;
typedefintElemType;
//定义存储结构
typedefstructLnode{
intdata;/*每个元素数据信息*/
structLnode*next;/*存放后继元素的地址*/
}LNode,*LinkList;
voidmain（）
{
voidCreate_L（LinkList&L,intn）;
voidPrint_L（LinkListL）;
voidMergeList_L（LinkList&La,LinkList&Lb,LinkList&Lc）;
LinkListLa,Lb,Lc;//创建单链表La,Lb,Lc
intn;
printf（"请输入链表La中的元素个数:
\n"）;
scanf（"%d",&n）;
Create_L（La,n）;//初始化单链表
printf（"现在La中的元素为:
\n"）;
Print_L（La）;
printf（"请输入链表Lb中的元素个数:
\n"）;
scanf（"%d",&n）;
Create_L（Lb,n）;//初始化单链表
printf（"现在Lb中的元素为:
\n"）;
Print_L（Lb）;
Create_L（Lc,0）;
printf（"-------------------------------------\n\n"）;
printf（"开始合并:
\n"）;
MergeList_L（La,Lb,Lc）;
printf（"-------------------------------------\n\n"）;
printf（"合并后，Lc的元素为\n"）;
Print_L（Lc）;
}
voidCreate_L（LinkList&L,intn）
{
intj=1;
L=（LinkList）malloc（sizeof（Lnode））;
L->next=NULL;//先建立一个带头结点的单链线性表L
for（inti=n;i>0;--i）
{
LinkListp=（LinkList）malloc（sizeof（Lnode））;
printf（"请输入链表中的第%d个元素:
\n",j++）;
scanf（"%d",&p->data）;
p->next=L->next;
L->next=p;
}//（逆序实现）
/*
LinkListq=L;
for（inti=1;i<=n;i++）
{
LinkListp=（LinkList）malloc（sizeof（Lnode））;
q->next=p;
p->next=NULL;
q=q->next;
printf（"请输入链表La中的第%d个元素:
\n",i）;
scanf（"%d",&p->data）;
}//（正序实现）
*/
}//初始化单链表
//有序单链表La和Lb的归并
voidMergeList_L（LinkList&La,LinkList&Lb,LinkList&Lc）
{
LinkListpa=La->next;
LinkListpb=Lb->next;
LinkListpc;
Lc=pc=La;
while（pa&&pb）
{
if（pa->data<=pb->data）
{
pc->next=pa;pc=pa;pa=pa->next;
}
else{pc->next=pb;pc=pb;pb=pb->next;}
}
pc->next=pa?
pa:
pb;
free（Lb）;
printf（"ppppppppppppppp"）;
}//MergeList
//输出单链表
voidPrint_L（LinkListL）
{
LinkListp;
p=L->next;
while（p）
{
printf（"%d",p->data）;
p=p->next;
}
printf（"\n"）;
}
3．构造一个单链表L，其头结点指针为head，编写程序实现将L逆置。
（即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。
）
#include
#include
#include
//定义存储结构
typedefstructLnode{
intdata;/*每个元素数据信息*/
structLnode*next;/*存放后继元素的地址*/
}LNode,*LinkList;
voidmain（）
{
voidCreate_L（LinkList&L,intn）;
voidPrint_L（LinkListL）;
voidReverseList（LinkListL）;
LinkListLa;//创建单链表La
intn;
printf（"请输入链表La中的元素个数:
\n"）;
scanf（"%d",&n）;
Create_L（La,n）;//初始化单链表
printf（"现在La中的元素顺序为:
\n"）;
Print_L（La）;
printf（"-------------------------------------\n\n"）;
ReverseList（La）;
printf（"逆置后，La的元素顺序为:
\n"）;
Print_L（La）;
}
voidCreate_L（LinkList&L,intn）
{
intj=1;
L=（LinkList）malloc（sizeof（Lnode））;
L->next=NULL;//先建立一个带头结点的单链线性表L
for（inti=n;i>0;--i）
{
LinkListp=（LinkList）malloc（sizeof（Lnode））;
printf（"请输入链表中的第%d个元素:
\n",j++）;
scanf（"%d",&p->data）;
p->next=L->next;
L->next=p;
}//（逆序实现）
/*
LinkListq=L;
for（inti=1;i<=n;i++）
{
LinkListp=（LinkList）malloc（sizeof（Lnode））;
q->next=p;
p->next=NULL;
q=q->next;
printf（"请输入链表La中的第%d个元素:
\n",i）;
scanf（"%d",&p->data）;
}//（正序实现）
*/
}//初始化单链表
//输出单链表
voidPrint_L（LinkListL）
{
LinkListp;
p=L->next;
while（p）
{
printf（"%d",p->data）;
p=p->next;
}
printf（"\n"）;
}
voidReverseList（LinkListL）
{
LinkListp,q;
p=L->next;
L->next=NULL;
while（p!
=NULL）
{
q=p->next;/*q指针保留p->next得值*/
p->next=L->next;
L->next=p;/*将p结点头插入到单链表L中*/
p=q;/*p指向下一个要插入的结点*/
}
}
升级会员 