数据结构课程设计单链表操作.doc

《数据结构课程设计》报告

题目： 单链表操作
专业： 计算机科学与技术
班级：

单链表操作
针对带头结点的单循环链表，编写实现以下操作的算法函数。
实现要求：
⑴ 单链表建立函数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的后继结点
三、设计具有上述处理要求和退出系统菜单
⒉ 所采用的数据结构：单链表
数据结构的定义：
typedef struct Node //定义结点的结构体
{
DataType data; //数据域
struct Node *next; //指针域
}LNode; //结点的类型

⒊ 所设计的函数
（1） Create(void)
LNode *Create(void) //建立单循环链表，链表头结点head作为返回值
{
int i,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<n;i++) //保存数组元素
scanf("%d",&A[i]);

//勾链建表，使链表中元素的次序与数组A各元素次序一样
for(j=0;j<n;j++) //根据一维数组A[M]建立一个单循环链表
{
p=(LNode*)malloc(sizeof(LNode));
p->data=A[j];
p->next=move->next;
move->next=p;
move=move->next;
}
return head; //返回头指针
}
开始
定义变量：int i ,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->data=A[j];
p->next=move->next; //
move->next=p;
move=move->next;
完毕
J++
Y
N

（2） Locate(LNode *head,DataType key)
LNode *Locate(LNode *head,DataType key) //建立定位查找函数Locate
{
LNode *q=head->next;
//查找并返回值为key的第1个元素的结点指针；假设找不到，那么返回NULL
while(q!=head && q->data!=key)
q=q->next;
if(q->data==key)
return q;
else
{
printf("查找的结点不存在！！\n");
return NULL;
}
}

Y
开始
定义变量：
*q=head->next；;
完毕
q!=head&&q->data!=key
q=q->next
q->data==key
return q
Return NULlL
Y
N
N

〔3〕Search(LNode *head,DataType *a,DataType *b)
//求链表的最大值和次大值，分别由*a和*b带回

void Search(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;
}

开始
LNode *p,*Max,*Secmax;
p=head->next->next;
Max=head->next;
Secmax=p;
P!=head
Max->data> p->data
p->data> Secmax->data
Secmax=p;
Secmax=Max;
Max=p;
*a=Max->data;
*b=Secmax->data;
完毕
N
Y
Y
N
N
Y
p=p->next;

〔4〕Sort(LNode *head)
//查找key,把链表中比key小的作为前驱结点，比key大的作为后继结点
LNode *Sort(LNode *head)
{ //*front指向key前局部链表，*rear指向key后局部链表
LNode *k,*p,*front,*rear,*L; DataType key;
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 < k->data)//将key结点后继比key小的插到key前面
{
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;
}
}
}
return head; //返回头指针
}

开始
LNode *k,*p,*front,*rear,*L;
DataType key;
front=head; p=head->next;
printf("请输入key：");
scanf("%d",&key);
L=Locate(head,key);
k=L;
rear=k;
p!=head
front->next!=k
p->data> k->data
front->next=front->next->next;
p->next=rear->next;
rear->next=p;
rear=rear->next;
p=front->next;
p=p->next;
front=front->next;
p=rear->next;
p->data< k->data
rear->next=rear->next->next;
p->next=front->next;
front->next=p;
front=front->next;
p=rear->next;
p=p->next;
rear=rear->next;
return head;
完毕
Y
N
Y
N
N
Y
N
Y

〔5〕主函数：
void main() //主函数
{
LNode *L,*W,*H;
DataType a,b;
int key,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)
{
case 1: //查找数值key并返回指针
{
printf("请输入要查找的值：");
scanf("%d",&key);
L=Locate(H,key);
if(L!=NULL)
printf("查找成功!!\n");
}
break;
case 2: //求链表的最大和次大值
{
Search(H,&a,&b);
printf("最大值：%d\n",a);
printf("次大值：%d\n",b);
}
break;
case 3: //将key插入链表中
{
H=Sort(H);
W=H->next;
printf("结果是："); //输出结果
while(W!=H)
{
printf(" %d",W->data); //依次输出
W=W->next;
}
printf("\n");
}
break;
case 4:
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〕健壮性处理：设计菜单是多一个功能：可以重新输入数组。
16 / 16