数据结构课程设计单链表操作.docx
- 文档编号:14189864
- 上传时间:2023-06-21
- 格式:DOCX
- 页数:15
- 大小:129.96KB
数据结构课程设计单链表操作.docx
《数据结构课程设计单链表操作.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计单链表操作.docx(15页珍藏版)》请在冰点文库上搜索。
数据结构课程设计单链表操作
《数据结构课程设计》报告
题目:
单链表操作
专业:
计算机科学与技术
班级:
单链表操作
针对带头结点的单循环链表,编写实现以下操作的算法函数。
实现要求:
⑴单链表建立函数create:
先输入数据到一维数组A[M]中,然后根据一维数组A[M]建立一个单循环链表,使链表中个元素的次序与A[M]中各元素的次序相同,要求该函数的时间复杂度为O(m);
⑵定位查找函数Locate:
在所建立的单循环链表中查找并返回值为key的第1个元素的结点指针;若找不到,则返回NULL;
⑶求出该链表中值最大和次大的元素值,要求该算法的时间复杂度为O(m),最大和次大的元素值通过指针变量带回,函数不需要返回值;
⑷将链表中所有值比key(值key通过形参传入)小的结点作为值为key的结点前驱,所有值比key大的结点作为值为key的结点后继,并尽量保持原有结点之间的顺序,要求该算法的时间复杂度为O(m);
⑸设计一个菜单,具有上述处理要求和退出系统功能。
⒈本人完成的工作:
一、定义结构体:
LNode
二、编写以下函数:
(1)建立单循环链表
(2)建立定位查找函数
(3)求出链表中最大和次大值
(4)将链表中的值和输入的Key比较,小的作为key前驱结点,大的作为key的后继结点
三、设计具有上述处理要求和退出系统菜单
⒉所采用的数据结构:
单链表
数据结构的定义:
typedefstructNode//定义结点的结构体
{
DataTypedata;//数据域
structNode*next;//指针域
}LNode;//结点的类型
⒊所设计的函数
(1)Create(void)
LNode*Create(void)//建立单循环链表,链表头结点head作为返回值
{
inti,j,n,A[M];//建立数组A【M】
LNode*head,*p,*move;
head=(LNode*)malloc(sizeof(LNode));//创建空单循环链表
head->next=head;
move=head;
printf("请输入数组元素的个数:
");//输入数组
scanf("%d",&n);
printf("请输入数组:
");
for(i=0;i scanf("%d",&A[i]); //勾链建表,使链表中元素的次序与数组A各元素次序相同 for(j=0;j { p=(LNode*)malloc(sizeof(LNode)); p->data=A[j]; p->next=move->next; move->next=p; move=move->next; } returnhead;//返回头指针 } 开始 定义变量: inti,j,n,A[M]; LNode*head,*p,*move; 建立空单循环链表head 建立一维数组A【M】 j=0 J if(A[j]==32767)break; p=(LNode*)malloc(sizeof(LNode)); p->data=A[j]; p->next=move->next;// move->next=p; move=move->next; 结束 J++ Y N (2)Locate(LNode*head,DataTypekey) LNode*Locate(LNode*head,DataTypekey)//建立定位查找函数Locate { LNode*q=head->next; //查找并返回值为key的第1个元素的结点指针;若找不到,则返回NULL while(q! =head&&q->data! =key) q=q->next; if(q->data==key) returnq; else { printf("查找的结点不存在! ! \n"); returnNULL; } } Y 开始 定义变量: *q=head->next;; 结束 q! =head&&q->data! =key q=q->next q->data==key returnq ReturnNULlL Y N N (3)Search(LNode*head,DataType*a,DataType*b) //求链表的最大值和次大值,分别由*a和*b带回 voidSearch(LNode*head,DataType*a,DataType*b) { LNode*p,*Max,*Secmax; p=head->next->next;//*Max和*Secmax指第一个结点,*p指向第二个结点, Max=head->next; Secmax=head->next->next;; while(p! =head) { if(Max->data>p->data)//*Max指向最大值 { if(p->data>Secmax->data) Secmax=p; } else//*Sexmax指向次大值 { Secmax=Max; Max=p; } p=p->next; } *a=Max->data;//把最大和次大值分别赋值给*a和*b *b=Secmax->data; } (4)Sort(LNode*head) //查找key,把链表中比key小的作为前驱结点,比key大的作为后继结点 LNode*Sort(LNode*head) {//*front指向key前部分链表,*rear指向key后部分链表 LNode*k,*p,*front,*rear,*L;DataTypekey; front=head; p=head->next; printf("请输入key: "); scanf("%d",&key); L=Locate(head,key);//调用Locate()查找key k=L; rear=k; while(p! =head) { if(front->next! =k)//判断key前面链表是否已经比较完毕 { if(p->data>k->data)//将key结点前驱比key大的插到key后面 { front->next=front->next->next;//断开结点 p->next=rear->next;//插入结点 rear->next=p; rear=rear->next; p=front->next;//*p指回key的前驱结点 } else{ p=p->next;//移动指针 front=front->next; } } else{ p=rear->next; if(p->data { rear->next=rear->next->next;//断开结点 p->next=front->next;//插入结点 front->next=p; front=front->next; p=rear->next;//*p指回key的后继结点 } else{ p=p->next;//移动指针 rear=rear->next; } } } returnhead;//返回头指针 } (5)主函数: voidmain()//主函数 { LNode*L,*W,*H; DataTypea,b; intkey,choice;//choice记载操作,key为输入值 printf("\n"); H=Create();//调用Create()建立单循环链表 //界面美化 printf("\n"); printf("***************************************************************\n"); printf("**\n"); printf("*定位查找-------------------------------------------------1*\n"); printf("*输出最大和次大值-----------------------------------------2*\n"); printf("*输出比较值key后的结果------------------------------------3*\n"); printf("*重新输入一个数组-----------------------------------------4*\n"); printf("*退出系统-------------------------------------------------0*\n"); printf("**\n"); printf("***************************************************************\n"); printf("\n"); //功能选择 printf("请选择系统功能: "); scanf("%d",&choice); printf("\n"); while(choice! =0) { switch(choice) { case1: //查找数值key并返回指针 { printf("请输入要查找的值: "); scanf("%d",&key); L=Locate(H,key); if(L! =NULL) printf("查找成功! ! \n"); } break; case2: //求链表的最大和次大值 { Search(H,&a,&b); printf("最大值: %d\n",a); printf("次大值: %d\n",b); } break; case3: //将key插入链表中 { H=Sort(H); W=H->next; printf("结果是: ");//输出结果 while(W! =H) { printf("%d",W->data);//依次输出 W=W->next; } printf("\n"); } break; case4: main(); default: printf("请输入正确的选项! ! \n");//错误处理 } //功能重复 printf("***************************************************************\n"); printf("**\n"); printf("*定位查找-------------------------------------------------1*\n"); printf("*输出最大和次大值-----------------------------------------2*\n"); printf("*输出比较值key后的结果------------------------------------3*\n"); printf("*重新输入一个数组-----------------------------------------4*\n"); printf("*退出系统-------------------------------------------------0*\n"); printf("**\n"); printf("***************************************************************\n"); printf("请选择系统功能: "); scanf("%d",&choice);} } ⒋运行结果: ⒌问题与总结 (1)在编写Create()函数时,要根据一维数组A【M】建立单循环链表,一开始只是用for语句结合头结点创建单链表方法。 后来测试时发现这样无法建立有序的单循环链表,要定义一个移动指针*move总是指向链表最后一个结点。 (2)在编写Search()函数时,一开始是找出链表中最大值,然后删去这个结点,在剩下的结点中找出最大值,最后输出。 但后来测试整个程序运行时,出现每次执行Search()的功能后,别的函数就执行不了,调试之后才知道是找最大和次大值破坏了链表的完整性,导致其他函数执行不了,最后定义了两个指针来带回最大和次大值。 (3)设计Sort()函数时,为了保持结点之间的顺序时,一开始用各种方法,就是实现不了,后来看了队列的一章受到启发,定义指针front和指针rear分别控制结点key的前驱部分和后继部分,最后实现了保持顺序的功能。 (4)设计菜单,一开始选择一个功能时都要输入一个数组,后来在主函数里面调用函数Create(),解决了这个问题。 (5)健壮性处理: 设计菜单是多一个功能: 可以重新输入数组。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 单链表 操作