数据结构实验2链表的基本操作.docx
- 文档编号:5693434
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:15
- 大小:81.63KB
数据结构实验2链表的基本操作.docx
《数据结构实验2链表的基本操作.docx》由会员分享,可在线阅读,更多相关《数据结构实验2链表的基本操作.docx(15页珍藏版)》请在冰点文库上搜索。
数据结构实验2链表的基本操作
《数据结构》实验报告
院系光电信息科学系专业电子信息工程
姓名潘成瑶学号122672012079电话
2012级2班2014年9月22日
一、实验题目
链表的基本操作
二、需求分析
1、编写链表基本操作函数。
①初始化链表InitList(LIST*L,intms)
②向链表指定位置插入元素InsertList1(LIST*L,intitem,intrc)
③向有序链表指定位置插入元素InsertList2(LIST*L,intitem,intrc)
④删除指定元素之的链表记录DeleteList(LIST*L,intitem)
⑤查找链表中的元素FindList(LIST*L,intitem)
⑥输出链表元素OutputList(LIST*L)
2、调用上述函数实现下列操作,操作步骤如下:
①初始化链表
②调用插入函数建立一个链表
③在链表中寻找指定的元素
④在链表中删除指定值的元素
⑤遍历并输出链表
三、概要设计
(1)为了实现上述程序功能,需要定义一个简化的单链表抽象数据类型:
ADTLinearList{
数据对象:
D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0}
结构关系:
R={
基本操作:
OutputLis(LinkListL)
操作前提:
L是一个未初始化的链表
InitLinkList(L,n)
操作前提:
L是一个未初始化的单链表
操作结果:
将L初始化为一个空的单链表
InertList(L,pos,e)
操作前提:
单链表L已存在
操作结果:
将元素e插入到单链表L的pos位置
DeleteLinkList(L,pos,e)
操作前提:
单链表L已存在
操作结果:
将单链表L中pos位置的元素删除,
删除的元素值通过e返回
findList(L,e)
操作前提:
单链表L已存在
操作结果:
在单链表L中查找元素e,
若存在,返回元素在表中的序号位置;
若不存在,返回-1
}
(2)本程序包含6个函数:
•主函数main()
•初始化单链表函数IniList()
•显示单链表内容函数outputList()
•插入元素函数InsertList()
•删除元素函数DeeteList()
•查找元素函数findList()
(3)主函数的伪码
main()
{说明一个单链表L;
初始化L;
建立L;
显示L;
循环做下面处理,直到读入的选项是“退出”:
{清屏;
显示菜单;
读入选项;
根据具体选项,读入需要的数据,调用相应的函数进行处理,
然后对得到的结果做必要的后处理,如打印输出。
}
}
四、详细设计
采用单链表实现概要设计中定义的抽象数据类型,有关的数据类型和伪码算法定义如下:
(1)类型定义
typedefintElemType;
typedefstructnode{
ElemTypedata;
structnode*next;
}Node,*LinkList;
(2)基本操作的伪码算法
为了方便,在单链表中设头结点,其data域没有意义。
●初始化
voidInitList(LinkList*L)
{
*L=申请新结点;
如果申请失败,返回失败标志;
(L)->next=NULL;
返回成功标志;
/*L是已经初始化好的空链表的头指针,通过键盘输入元素值,
利用尾插法建单链表L*/
q=L;
打印输入提示:
“请输入若干个正整数(用空格分隔),并用-1结束:
”
读入一个数x;
当x不是结束标志时,循环做如下处理:
{申请一个新结点p;
如果申请失败,返回失败标志;
将x送到p的data域;
q->next=p;
q=p
读入下一个数x;
}
q->next=NULL;
返回成功标志;
}
●显示单链表
voidoutputList(LinkListL)
{p=首元素结点地址;
while(p不空)
{
打印结点p的元素值;
p=下一个结点地址;}
}
●插入操作
boolInertList(LinkListL,intpos,inte)
/*在带头结点的单链表L中第pos个位置插入值为e的新结点s*/
{从“头”开始,查找第i-1个结点pre;
if(查找失败)
{显示参数错误信息;
returnERROR;}
else
{申请一个新的结点s;
将e放入s的数据域;
将s插到pre后面;
returnOK;}
}
●删除操作
boolDeLeteist(LinkListL,intitem)
{//在带头结点的单链表L中,删除第pos个元素,并由e返回其值
LinkListp=L,q;
intj=0;
while(p->next&&j {//寻找第item个结点,令p指向其前趋 p=p->next;++j; } //if(! (p->next)||j>item-1)returnerror;//删除位置不合理 q=p->next; p->next=q->next;//删除并释放结点 OutputLis(L); }//ListDelete_L ●查找操作 intfindList(LinkListL,inte) { intj=1; LinkListp; p=L->next; while(j { p=p->next; j++; } printf("%d\n",p->data); } 五、调试分析 1.在调试过程中总会遇到缺了逗号或者双引号的情况,所以我们得尽量减少这些低级错误的概率。 2.而且在调试的过程中,由于output函数没有在其他程序之前先定义,到后面就无法把查入和删除的链表输出。 所以要在定义其他函数之前先把输出链表的函数先定义好。 3.在main中函数调用经常会把调用的函数打错,而无法调用自定义函数。 六、使用说明 程序执行过程如下: 提示用户输入插入的位置和数; 用户按要求输入插入的位置和数 屏幕显示插入数后的链表; 提示用户输入指定删除的位置; 用户按要求输入删除的位置; 屏幕显示删除后的链表; 提示用户输入寻找的数; 用户按要求输入寻找的数; 屏幕显示该数的位置; 七、测试结果 1.向链表指定位置插入元素 2.在链表中查找指定的元素 3.在链表中删除指定值的元素 9.附录 #include #include typedefstructlist { intdata; structlist*next; }LIST; voidInitList(LIST**p) {//初始化链表 *p=NULL; } voidInsertList1(LIST**p,intrc,intitem) {//向链表指定位置【rc】插入元素【item】 inti; LIST*u,*q,*r;//u为新结点,q插入点前驱,r为插入点后继 u=(LIST*)malloc(sizeof(LIST)); u->data=item; for(i=0,r=*p;i =NULL;i++)//i! =rc {q=r; r=r->next; } if(r==*p)//p==NULL//插入首结点或p为空指针 *p=u; else q->next=u; u->next=r; } voidInsertList2(LIST**p,intitem) //向有序链表【p】插入键值为【item】的结点 { LIST*u,*q,*r;//u为新结点,q插入点前驱,r为插入点后继 u=(LIST*)malloc(sizeof(LIST)); u->data=item;//p! =NULL for(r=*p;r! =NULL&&r->data //插入首结点或p为空指针 if(r==*p) *p=u;//r->next=u; else q->next=u; u->next=r; } intDeleteList(LIST**p,intitem)// //删除键值为【item】的链表结点,返回0为删除成功,1为没找到 { LIST*q,*r;//q为结点前驱,r为结点后继 q=*p; if(q==NULL)//链表为空 return1; if(q->data==item)//要删除链表首结点 { *p=q->next;//p=q->link更改链表首结点指针 free(q);//释放被删除结点的空间 return0;//删除头结点成功 } for(;q->data! =item&&q->next! =NULL;r=q,q=q->next);//q! =NULL&&p //寻找键值为【item】的结点//r为结点,q为结点后继 if(q->data==item)//找到结点 { r->next=q->next;//被删结点从链表中脱离 free(q);//释放被删除结点的空间 return0;//删除成功 } return1;//没有指定值的结点,删除失败 } intFindList(LIST*p,intitem) {//查找键值【item】的链表结点位置,返回≥1为找到,-1为未找到 inti; for(i=1;p->data! =item&&p! =NULL;p=p->next,i++); //查找键值【item】的链表结点 return(p==NULL)? -1: i;//找到返回【i】 } voidOutputList(LIST*p) {//输出链表结点的键值 while(p! =NULL) { printf("%4d",p->data); p=p->next; } } voidFreeList(LIST**p) {//释放链表空间 LIST*q,*r; for(q=*p;q! =NULL;) {r=q;//q=*p q=q->next; free(r); } *p=NULL;//将链表首结点指针置空 } voidmain() { LIST*p; intop,i,rc; InitList(&p); while (1) { printf("\n请选择操作1: 指定位置追加2: 升序追加3: 查找结点\n"); printf("4、删除结点5: 输出结点6、清空链表0: 退出\n"); fflush(stdin); scanf("%d",&op); switch(op) { case0: return; case1: printf("\n请输入新增结点位置和键值: "); scanf("%d%d",&rc,&i); InsertList1(&p,rc,i); break; case2: printf("\n请输入新增结点键值: "); scanf("%d",&i); InsertList2(&p,i); break; case3: printf("\n请输入要查找结点的键值: "); scanf("%d",&i); rc=FindList(p,i); if(rc>0) printf("位置为【%d】\n",rc); else printf("没找到! "); break; case4: printf("\n请输入要删除结点的键值: "); scanf("%d",&i); rc=DeleteList(&p,i); if(rc==0) printf("删除成功\n",rc); else printf("没找到\n"); break; case5: printf("\n链表内容为: \n"); OutputList(p); break; case6: FreeList(&p); break; } } }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 基本 操作
![提示](https://static.bingdoc.com/images/bang_tan.gif)