内容发布更新时间 : 2024/6/30 0:41:08星期一 下面是文章的全部内容请认真阅读。

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

题目： 单链表操作

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

单链表操作

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

实现要求：

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