《数据结构课程设计》报告
题目： 单链表操作
专业： 计算机科学与技术 班级：
单链表操作
针对带头结点的单循环链表，编写实现以下操作的算法函数。
实现要求：
⑴ 单链表建立函数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;