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

数据结构 课程设计报告内容及其格式 数据结构课程设计 报告 题目 单链表操作 专业 计算机科学与技术 班级 单链表操作单链表操作 针对带头结点的单循环链表 编写实现以下操作的算法函数 数据结构 课程设计报告内容及其格式 实现要求 单链表建立函数 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 printf 请输入数组 for i 0 i n i 保存数组元素 scanf d 勾链建表 使链表中元素的次序与数组 A 各元素次序相同 for j 0 jdata 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 Jdata 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 if q data key return q 数据结构 课程设计报告内容及其格式 else printf 查找的结点不存在 n return NULL Y 开始 定义变量 q head next 结束 q head 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 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 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 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 datadata 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 printf n while choice 0 switch choice case 1 查找数值 key 并返回指 针 printf 请输入要查找的值 scanf d L Locate H key if L NULL printf 查找成功 n break case 2 求链表的最大和次大值 Search H 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 运行结果 运行结果 数据结构 课程设计报告内容及其格式 问题与总结问题与总结 1 在编写 Create 函数时 要根据一维数组 A M 建立单循环链表 一开 始只是用 for 语句结合头结点创建单链表方法 后来测试时发现这样无法建立 有序的单循环链表 要定义一个移动指针 move 总是指向链表最后一个结点 2 在编写 Search 函数时 一开始是找出链表中最大值 然后删去这个结 点 在剩下的结点中找出最大值 最后输出 但后来测试整个程序运行时 出 现每次执行 Search 的功能后 别的函数就执行不了 调试之后才知道是找最 大和次大值破坏了链表的完整性