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

《数据结构》课程设计报告内容及其格式

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

题目： 单链表操作

专业： 计算机科学与技术 班级：

单链表操作

针对带头结点的单循环链表，编写实现以下操作的算法函数。

《数据结构》课程设计报告内容及其格式

实现要求：

⑴ 单链表建立函数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) {

//勾链建表，使链表中元素的次序与数组A各元素次序相同 for(j=0;j

return head;

//返回头指针

p=(LNode*)malloc(sizeof(LNode)); p->data=A[j];

//根据一维数组A[M]建立一个单循环链表

int i,j,n,A[M];

//建立数组A【M】

//建立单循环链表，链表头结点head作为返回值

LNode *head,*p,*move;

head=(LNode*)malloc(sizeof(LNode)); head->next=head; move=head;

printf(\请输入数组元素的个数：\ scanf(\printf(\请输入数组：\for(i=0;i

//创建空单循环链表

//输入数组

//保存数组元素

p->next=move->next; move->next=p; move=move->next;

《数据结构》课程设计报告内容及其格式

}

开始 定义变量：int i ,j,n,A[M]; LNode *head,*p,*move; 建立空单循环链表head 建立一维数组A【M】 j=0 N Jdata=A[j]; p->next=move->next; J++ 结束

（2） Locate(LNode *head,DataType key)

LNode *Locate(LNode *head,DataType key) {

LNode *q=head->next;

//查找并返回值为key的第1个元素的结点指针；若找不到，则返回NULL

//建立定位查找函数Locate

while(q!=head && q->data!=key)

q=q->next;

if(q->data==key)

return q;

else

《数据结构》课程设计报告内容及其格式

}

{

printf(\查找的结点不存在！！\\n\ }

return NULL;

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

（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) { } else { }

p=p->next;

}

}

*a=Max->data; *b=Secmax->data;

//把最大和次大值分别赋值给*a和*b

Secmax=Max; Max=p;

//*Sexmax指向次大值

if(p->data > Secmax->data)

Secmax=p;

//*Max指向最大值

《数据结构》课程设计报告内容及其格式

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

《数据结构》课程设计报告内容及其格式

（4）Sort(LNode *head)

//查找key,把链表中比key小的作为前驱结点，比key大的作为后继结点

LNode *Sort(LNode *head) {

//*front指向key前部分链表，*rear指向key后部分链表

DataType key;

LNode *k,*p,*front,*rear,*L;

front=head; p=head->next;

printf(\请输入key：\scanf(\L=Locate(head,key); k=L; rear=k; while(p!=head) {

if(front->next!=k) { }

//调用Locate()查找key

//判断key前面链表是否已经比较完毕

if(p->data > k->data)//将key结点前驱比key大的插到key后面 { } else{ }

p=p->next;

//移动指针

front->next=front->next->next; p->next=rear->next; rear->next=p; rear=rear->next; p=front->next;

//*p指回key的前驱结点

//断开结点 //插入结点

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;

} else{ p=p->next;

rear=rear->next;

}

}

}

return head; }

//断开结点

//插入结点

//*p指回key的后继结点

//移动指针

//返回头指针

《数据结构》课程设计报告内容及其格式

开始 LNode *k,*p,*front,*rear,*L; DataType key; front=head; p=head->next; printf(\请输入key：\scanf(\L=Locate(head,key); k=L; rear=k; N p!=head Y front->next!=k Y N p->data> k->data Y front->next=front->next->next; p->next=rear->next; rear->next=p; rear=rear->next; p=front->next; p->data< k->data Y rear->next=rear->next->next; p->next=front->next; front->next=p; front=front->next; p=rear->next; p=rear->next; N N p=p->next; front=front->nextp=p->next; rear=rear->next; return head; 结束

《数据结构》课程设计报告内容及其格式

（5）主函数：

void main() {

LNode *L,*W,*H; DataType a,b;

//主函数

int key,choice; printf(\H=Create(); //界面美化 printf(\

//choice记载操作,key为输入值

//调用Create()建立单循环链表

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(\

《数据结构》课程设计报告内容及其格式

//功能选择

printf(\请选择系统功能:\scanf(\printf(\

while(choice != 0) { switch (choice) { case 1:

{ printf(\请输入要查找的值：\ scanf(\ L=Locate(H,key); if(L!=NULL)

printf(\查找成功!!\\n\

}

break;

case 2:

{ Search(H,&a,&b);

printf(\最大值：%d\\n\

printf(\次大值：%d\\n\

}

break;

case 3: {

H=Sort(H);

//查找数值key并返回指针//求链表的最大和次大值

//将key插入链表中

《数据结构》课程设计报告内容及其格式

}

W=H->next;

printf(\结果是：\ while(W!=H) { }

printf(\

printf(\ W=W->next;

//依次输出

//输出结果

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(\

⒋运行结果：

《数据结构》课程设计报告内容及其格式

⒌ 问题与总结

（1）在编写Create()函数时，要根据一维数组A【M】建立单循环链表，一开始只是用for语句结合头结点创建单链表方法。后来测试时发现这样无法建立有序的单循环链表，要定义一个移动指针*move总是指向链表最后一个结点。 （2）在编写Search()函数时，一开始是找出链表中最大值，然后删去这个结点，在剩下的结点中找出最大值，最后输出。但后来测试整个程序运行时，出现每次执行Search()的功能后，别的函数就执行不了，调试之后才知道是找最大和次大值破坏了链表的完整性，导致其他函数执行不了，最后定义了两个指针来带回最大和次大值。

（3）设计Sort（）函数时，为了保持结点之间的顺序时，一开始用各种方法，就是实现不了，后来看了队列的一章受到启发，定义指针front和指针rear分别控制结点key的前驱部分和后继部分，最后实现了保持顺序的功能。 （4）设计菜单，一开始选择一个功能时都要输入一个数组，后来在主函数里面调用函数Create()，解决了这个问题。

（5）健壮性处理：设计菜单是多一个功能：可以重新输入数组。

本文来源：https://www.bwwdw.com/article/7fbp.html