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