实验二单链表基本操作技巧.docx
- 文档编号:13714410
- 上传时间:2023-06-16
- 格式:DOCX
- 页数:15
- 大小:16.89KB
实验二单链表基本操作技巧.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指向下一个要插入的结点*/ } }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 二单链表 基本 操作 技巧
![提示](https://static.bingdoc.com/images/bang_tan.gif)