《数据结构课程设计单链表操作》由会员分享，可在线阅读，更多相关《数据结构课程设计单链表操作（15页珍藏版）》请在金锄头文库上搜索。
1、精选优质文档-倾情为你奉上数据结构课程设计报告题目： 单链表操作专业： 计算机科学与技术 班级： 单链表操作针对带头结点的单循环链表，编写实现以下操作的算法函数。实现要求： 单链表建立函数create：先输入数据到一维数组AM中，然后根据一维数组AM建立一个单循环链表，使链表中个元素的次序与AM中各元素的次序相同，要求该函数的时间复杂度为O(m)； 定位查找函数Locate：在所建立的单循环链表中查找并返回值为key的第1个元素的结点指针；若找不到，则返回NULL； 求出该链表中值最大和次大的元素值，要求该算法的时间复杂度为O(m)，最大和次大的元素值通过指针变量带回，函数不需要返回值； 将链
2、表中所有值比key(值key通过形参传入)小的结点作为值为key的结点前驱，所有值比key大的结点作为值为key的结点后继，并尽量保持原有结点之间的顺序，要求该算法的时间复杂度为O(m); 设计一个菜单，具有上述处理要求和退出系统功能。 本人完成的工作：一、定义结构体：LNode二、编写以下函数：（1）建立单循环链表（2）建立定位查找函数（3）求出链表中最大和次大值（4）将链表中的值和输入的Key比较，小的作为key前驱结点，大的作为key的后继结点三、设计具有上述处理要求和退出系统菜单 所采用的数据结构：单链表数据结构的定义：typedef struct Node/定义结点的结构体 Data
3、Type data;/数据域struct Node *next;/指针域LNode;/结点的类型 所设计的函数（1） Create(void)LNode *Create(void)/建立单循环链表，链表头结点head作为返回值int i,j,n,AM;/建立数组A【M】 LNode *head,*p,*move;head=(LNode*)malloc(sizeof(LNode);/创建空单循环链表head-next=head;move=head;printf(请输入数组元素的个数：);/输入数组scanf(%d,&n);printf(请输入数组：);for(i=0;in;i+)/保存数组元素s
4、canf(%d,&Ai);/勾链建表，使链表中元素的次序与数组A各元素次序相同for(j=0;jdata=Aj;p-next=move-next;move-next=p;move=move-next;return head;/返回头指针开始定义变量：int i ,j,n,AM;LNode *head,*p,*move;建立空单循环链表head建立一维数组A【M】j=0Jdata=Aj;p-next=move-next;/move-next=p;move=move-next;结束J+YN（2） Locate(LNode *head,DataType key)LNode *Locate(LNode
5、 *head,DataType key)/建立定位查找函数LocateLNode *q=head-next;/查找并返回值为key的第1个元素的结点指针；若找不到，则返回NULLwhile(q!=head & q-data!=key)q=q-next;if(q-data=key)return q;elseprintf(查找的结点不存在！n);return NULL;Y开始定义变量：*q=head-next；;结束q!=head&q-data!=keyq=q-nextq-data=keyreturn qReturn NULlLYNN（3）Search(LNode *head,DataType *
6、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=
7、p-next;*a=Max-data;/把最大和次大值分别赋值给*a和*b*b=Secmax-data;开始LNode *p,*Max,*Secmax;p=head-next-next;Max=head-next;Secmax=p;P!=headMax-data p-datap-data Secmax-dataSecmax=p;Secmax=Max;Max=p;*a=Max-data;*b=Secmax-data;结束NYYNNYp=p-next;（4）Sort(LNode *head)/查找key,把链表中比key小的作为前驱结点，比key大的作为后继结点LNode *Sort(LNode
8、*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()查找keyk=L;rear=k;while(p!=head)if(front-next!=k)/判断key前面链表是否已经比较完毕if(p-data k-data)/将key结点前驱比key大的插到key后面front-next=front-next-next;/断开结点
9、p-next=rear-next;/插入结点rear-next=p;rear=rear-next;p=front-next;/*p指回key的前驱结点elsep=p-next;/移动指针front=front-next;elsep=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的后继结点elsep=p-next;/移动指针rear=rear-n
10、ext;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!=headfront-next!=kp-data k-datafront-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-n
11、ext;p-datadatarear-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;结束YNYNNYNY（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(*
