数据结构实验二.docx
- 文档编号:10536938
- 上传时间:2023-05-26
- 格式:DOCX
- 页数:19
- 大小:64.09KB
数据结构实验二.docx
《数据结构实验二.docx》由会员分享,可在线阅读,更多相关《数据结构实验二.docx(19页珍藏版)》请在冰点文库上搜索。
数据结构实验二
《数据结构》实验报告二
学校:
班级:
学号:
姓名:
日期:
程序名:
一、上机实验得问题与要求:
单链表得查找、插入与删除。
设计算法,实现线性结构上得单链表得产生以及元素得查找、插入与删除。
具体实现要求:
1.从键盘输入20个整数,产生不带表头得单链表,并输入结点值。
2.从键盘输入1个整数,在单链表中查找该结点得位置。
若找到,则显示“找到了”;否则,则显示“找不到”。
3.从键盘输入2个整数,一个表示欲插入得位置i,另一个表示欲插入得数值x,将x插入在对应位置上,输出单链表所有结点值,观察输出结果。
4.从键盘输入1个整数,表示欲删除结点得位置,输出单链表所有结点值,观察输出结果。
5.将单链表中值重复得结点删除,使所得得结果表中个结点值均不相同,输出单链表所有结点值,观察输出结果。
6.删除其中所有数据值为偶数得结点,输出单链表所有结点值,观察输出结果。
7.把单链表变成带表头结点得循环链表,输出循环单链表所有结点值,观察输出结果。
8.(★)将单链表分解成两个单链表A与B,使A链表中含有原链表中序号为奇数得元素,而B链表中含有原链表中序号为偶数得元素,且保持原来得相对顺序,分别输出单链表A与单链表B得所有结点值,观察输出结果。
二、程序设计得基本思想,原理与算法描述:
(包括程序得结构,数据结构,输入/输出设计,符号名说明等)
这就是一个带头结点得线性链表,数据域存放整形数据,由用户输入。
头结点数据域存链表长度,所以程序中有个求链表长度得函数
intLengthList(LinkListL);//求链表长度
L就是指向头结点得指针,将长度值存入语句为
L>data=LengthList(L);
为了实时观察链表情况,程序中有个输出链表数据得函数
voidPrintList(LinkListL);//输出链表
程序可以实现8种不同得操作,这8种不同得操作由8个函数实现,分别就是
voidCreateList(LinkList&L);//创建链表
voidLocate(LinkListL);//查询数值
voidInsertList(LinkList&L);//插入数值
voidDeleteList(LinkList&L);//选择删除
voidDeleterepeat(LinkList&L);//删除重复结点
voidDeleteEven(LinkList&L);//删除数值为偶数得结点
voidRotate(LinkList&L);//变为循环链表
voidDivide(LinkList&L);//分解成两个链表
这些基本操作得实现算法都比较简单,有些跟书本上一样,有些需要自己稍作思考才能写出,具体程序见第三部分
8种不同得操作可以由用户通过按AH这八个字母键来选择,分别就是A:
创建B:
查询C:
插入D:
选择删除E:
删除重复F:
删除偶数G:
变为循环链表H:
分解为两个链表,见第四部分输出截图,可以清晰得瞧到整个过程
主程序中用开关语句实现:
charoperate;
printf("\n\n输入字符选择链表操作类型\nA:
创建B:
查询C:
插入D:
选择删除E:
删除重复F:
删除偶数\nG:
变为循环链表H:
分解为两个链表\n");
scanf("%c",&operate);
switch(operate)
{
case'a':
case'A':
CreateList(L);break;
case'b':
case'B':
Locate(L);break;
case'c':
case'C':
InsertList(L);break;
case'd':
case'D':
DeleteList(L);break;
case'e':
case'E':
Deleterepeat(L);break;
case'f':
case'F':
DeleteEven(L);break;
case'g':
case'G':
Rotate(L);break;
case'h':
case'H':
Divide(L);break;
case'\n':
gotolabel;
default:
printf("输入有误,请重新输入!
");break;
}
三、源程序及注释:
#include
#include
typedefstructLNode//链表结点
{
intdata;
structLNode*next;
}LNode,*LinkList;
intover_flag=0;//主函数结束标识符
voidCreateList(LinkList&L);//创建链表
voidLocate(LinkListL);//查询数值
voidInsertList(LinkList&L);//插入数值
voidDeleteList(LinkList&L);//选择删除
voidDeleterepeat(LinkList&L);//删除重复结点
voidDeleteEven(LinkList&L);//删除数值为偶数得结点
voidRotate(LinkList&L);//变为循环链表
voidDivide(LinkList&L);//分解成两个链表
intLengthList(LinkListL);//求链表长度
voidPrintList(LinkListL);//输出链表
/**********************************************************************
主函数
**********************************************************************/
voidmain(void)
{
charoperate;
LinkListL;
intn;
for(n=0;n<40;n++)
{
printf("\n\n输入字符选择链表操作类型\nA:
创建B:
查询C:
插入D:
选择删除E:
删除重复F:
删除偶数\nG:
变为循环链表H:
分解为两个链表\n");
label:
scanf("%c",&operate);
switch(operate)
{
case'a':
case'A':
CreateList(L);break;
case'b':
case'B':
Locate(L);break;
case'c':
case'C':
InsertList(L);break;
case'd':
case'D':
DeleteList(L);break;
case'e':
case'E':
Deleterepeat(L);break;
case'f':
case'F':
DeleteEven(L);break;
case'g':
case'G':
Rotate(L);break;
case'h':
case'H':
Divide(L);break;
case'\n':
gotolabel;//排除换行键得影响
default:
printf("输入有误,请重新输入!
");break;
}
if(over_flag)return;
}
}
/**********************************************************************
创建链表
**********************************************************************/
voidCreateList(LinkList&L)
{
inttemp;
printf("创建链表:
\n请输入创建链表所需得整数值(以1结束):
");
L=(LinkList)malloc(sizeof(LNode));
L>next=NULL;
LinkListq=L;
scanf("%d",&temp);
while(temp!
=1)
{
LinkListp;
p=(LinkList)malloc(sizeof(LNode));
p>data=temp;
p>next=NULL;
q>next=p;
q=q>next;
scanf("%d",&temp);
}
L>data=LengthList(L);
PrintList(L);
}
/**********************************************************************
查询元素
**********************************************************************/
voidLocate(LinkListL)
{if(!
L)printf("错误:
链表未创建!
");
intelement;
printf("查询数值:
\n输入要查询得数值:
");
scanf("%d",&element);
LinkListp=L>next;
inti=1;
while(p)
{
if(p>data==element)
{
printf("找到了,它就是链表得第%d个元素。
\n",i);
return;
}
p=p>next;
i++;
}
printf("找不到。
\n");
}
/**********************************************************************
插入数值
**********************************************************************/
voidInsertList(LinkList&L)
{
intx,i;
printf("插入数值:
\n输入要插入得数值与插入得位置:
");
scanf("%d",&x);
scanf("%d",&i);
LinkListp=L;
intj=0;
while(p&&j { p=p>next; ++j; } if(! p||j>i1) { printf("输入位置错误! "); return; } LinkLists=(LinkList)malloc(sizeof(LNode)); s>data=x; s>next=p>next; p>next=s; L>data=LengthList(L); PrintList(L); } /********************************************************************** 选择位置删除节点 **********************************************************************/ voidDeleteList(LinkList&L) { inti; LinkListp=L; printf("选择位置删除结点: \n输入要删除数值得位置: "); scanf("%d",&i); intj=0; while(p>next&&j { p=p>next; ++j; } if(! (p>next)||j>i1) { printf("输入位置错误! "); return; } LinkListq=p>next; p>next=q>next; free(q); L>data=LengthList(L); PrintList(L); } /********************************************************************** 删除重复结点 **********************************************************************/ voidDeleterepeat(LinkList&L) { printf("删除重复结点后得链表为: \n"); intn=1; inta[20]; LinkListq=L>next; LinkListp=q>next; a[0]=q>data; while(p) { for(inti=0;i { if(p>data==a[i]) { LinkListr=p; q>next=p>next; p=p>next; free(r); break; } } if(i==n) { a[n++]=p>data; p=p>next; q=q>next; } } L>data=LengthList(L); PrintList(L); } /********************************************************************** 删除数值为偶数得结点 **********************************************************************/ voidDeleteEven(LinkList&L) { printf("删除偶数结点后得链表为: \n"); LinkListq=L; LinkListp=L>next; while(p) { if(p>data%2==0) { LinkListr=p; q>next=p>next; p=p>next; free(r); } else { p=p>next; q=q>next; } } L>data=LengthList(L); PrintList(L); } /********************************************************************** 变为循环链表 **********************************************************************/ voidRotate(LinkList&L) { printf("变为循环链表: \n"); LinkListp=L; while(p>next)p=p>next; p>next=L; LinkListt=L>next; printf("长度: %d\t",L>data); printf("各个结点数值为: "); while(t! =L) { printf("%d\t",t>data); t=t>next; } printf("\n"); printf("已经变为循环链表,其她操作将受影响,程序结束! \n"); over_flag=1; } /********************************************************************** 分解成两个链表 **********************************************************************/ voidDivide(LinkList&L) { printf("分解成两个链表: \n"); LinkListA=L; LinkListB=(LinkList)malloc(sizeof(LNode)); B>next=NULL; LinkListLb=B; inti=1; LinkListLa=L; LinkListp=L>next; while(p) { if(i++%2==0) { La>next=p>next; p>next=NULL; Lb>next=p; Lb=Lb>next; p=La>next; } else { p=p>next; La=La>next; } } A>data=LengthList(A); printf("链表A: "); PrintList(A); B>data=LengthList(B); printf("链表B: "); PrintList(B); printf("已经分解成两个链表,其她操作将受影响,程序结束! \n"); over_flag=1; } /********************************************************************** 求链表长度 **********************************************************************/ intLengthList(LinkListL) { inti=0; LinkListp=L>next; while(p) { p=p>next; i++; } returni; } /********************************************************************** 输出链表 **********************************************************************/ voidPrintList(LinkListL) { LinkListt=L>next; printf("长度: %d\t",L>data); printf("结点数值: "); while(t) { printf("%d\t",t>data); t=t>next; } printf("\n"); } 四、运行输出结果: 五、调试与运行程序过程中产生得问题及采取得措施: 1、主程序中我用到charoperate; scanf("%c",&operate); Operate存放用户选择操作类型得字母AH,但就是当用户键入字母后,要按ENTER键表示输入完毕,所以以后执行scanf("%c",&operate);就是会把ENTER输入到operate中,从而影响了后面得操作,解决方案就是加一个标记位 label: scanf("%c",&operate); 当程序发现输入为ENTER时,回到labeL处,这样解决了问题。 请瞧下面语句,注意case'\n': gotolabel; label: scanf("%c",&operate); switch(operate) { case'a': case'A': CreateList(L);break; case'b': case'B': Locate(L);break; case'c': case'C': InsertList(L);break; case'd': case'D': DeleteList(L);break; case'e': case'E': Deleterepeat(L);break; case'f': case'F': DeleteEven(L);break; case'g': case'G': Rotate(L);break; case'h': case'H': Divide(L);break; case'\n': gotolabel;//排除换行键得影响 default: printf("输入有误,请重新输入! ");break; } 2、、最后两个操作 voidRotate(LinkList&L);//变为循环链表 voidDivide(LinkList&L);//分解成两个链表 一旦执行,将破坏链表得结构,无法再进行其她操作,需要结束整个程序。 而在Rotate与Divide子程序中无法直接结束主函数,所以我设置了一个主函数结束标志位 intover_flag=0;//主函数结束标识符 初值为0,当它变为1时表示主函数需要结束 子函数中写 : voidRotate(LinkList&L) { 、、、、、、、、、、 over_flag=1; } voidDivide(LinkList&L) { 、、、、、、、、、、、 over_flag=1; } 主函数中写 voidmain(void) { 、、、、、、、、、、 if(over_flag)return; } 六、对算法得程序得讨论、分析,改进设想,其它经验教训: 原来我写得程序就是8个基本操作按顺序自动执行,后来听取其她同学得意见,设置不同得字母对应这些基本操作,由用户自己选择执行,这样就比原来得程序要灵活很多,也便于用户使用与观察。 在创建链表时,原来设计得就是输入固定长度得链表,后来改进为由用户输入任意长度得数据,只需要用1表示结束即可。 七、对实验方式、组织、设备、题目得意见与建议: 这个试验题目还可以,基本涵盖了单链表所有得简单操作,只要能写完程序并顺利运行,也就掌握了单链表得相关知识内容。 但就是由于涵盖内容太多,课内无法完成,必须在课外花很多时间。 所以我认为在上完这一章得内容后,老师就应该要求我们做这个程序,这样早点开始,做得时间长一些,效果更应该好一点。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验
![提示](https://static.bingdoc.com/images/bang_tan.gif)