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

1、数据结构课程设计报告题目：单链表操作专业：计算机科学与技术班级:单链表操作针对带头结点的单循环链表，编写实现以下操作的算法函数实现要求： 单链表建立函数 create ：先输入数据到一维数组 AM 中，然后根据一维 数组AM建立一个单循环链表，使链表中个元素的次序与AM中各元素的次序相同，要求该函数的时间复杂度为 O（m）； 定位查找函数 Locate ：在所建立的单循环链表中查找并返回值为 key 的 第 1 个元素的结点指针；若找不到，则返回 NULL； 求出该链表中值最大和次大的元素值， 要求该算法的时间复杂度为 O（m）， 最大和次大的元素值通过指针变量带回，函数不需要返回值； 将链表

2、中所有值比 key（ 值 key 通过形参传入 ） 小的结点作为值为 key 的结 点前驱，所有值比 key 大的结点作为值为 key 的结点后继，并尽量保持原有 结点之间的顺序，要求该算法的时间复杂度为 O（m）; 设计一个菜单，具有上述处理要求和退出系统功能。1. 本人完成的工作：一、定义结构体： LNode二、编写以下函数：（1）建立单循环链表（2）建立定位查找函数（3）求出链表中最大和次大值（4）将链表中的值和输入的 Key比较，小的作为key前驱结点，大的作为key 的后继结点三、设计具有上述处理要求和退出系统菜单2. 所采用的数据结构：单链表数据结构的定义：typedef stru

3、ct Node/定义结点的结构体DataType data;/数据域struct Node *next;/指针域LNode;/ 结点的类型3.所设计的函数( 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

4、,&n);printf( 请输入数组： );for(i=0;in;i+)scanf(%d,&Ai);/ 勾链建表，使链表中元素的次序与数组 A 各元素次序相同 for(j=0;jdata=Aj;p-next=move-next; move-next=p;move=move-next;/ 返回头指针 return head;(2) Locate(LNode *head,DataType key)LNode *Locate(LNode *head,DataType key) / 建立定位查找函数 LocateLNode *q=head-n ext;/查找并返回值为key的第1个元素的结点指针；若找

5、不到，则返回NULLwhile(q!=head & q-data!=key)q=q-n ext;if(q-data=key)return q;elseprintf(查找的结点不存在！ n);return NULL;Y(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

6、=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 *k,*p,*front,*rear,*L;front=head;p=head-next;printf( 请输入 key：);scanf(%d,&key);L=Locate(head,key);

7、k=L;rear=k; while(p!=head)if(front-next!=k)if(p-data k-data)/4) Sort(LNode *head)/ 查找 key, 把链表中比 key 小的作为前驱结点，比 key 大的作为后继结点LNode *Sort(LNode *head) /*front 指向 key 前部分链表， *rear 指向 key 后部分链表DataType key;/ 调用 Locate() 查找 key/ 判断 key 前面链表是否已经比较完毕 将 key 结点前驱比 key 大的插到 key 后面front-next=front-next-next; p

8、-next=rear-next; rear-next=p; rear=rear-next; p=front-next;elsep=p-next;front=front-next;/ 断开结点/ 插入结点/*p 指回 key 的前驱结点/ 移动指针/ 断开结点/ 插入结点/*p 指回 key 的后继结点/ 移动指针/ 返回头指针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;

9、p=rear-next;elsep=p-next; rear=rear-next; return head;开始LNode *k,*p,*fro nt,*rear,*L;DataType key; fron t=head; p=head-n ext; printf(” 请输入 key:); sca nf(%d,&key); L=Locate(head,key);k=L;rear=k;NNfront-n ext=fr ont-n ext- n ext;p-n ext=rear- n ext;rear-n ext=p;rear=rear- n ext;p=front-n ext;rear-n ex

10、t=rear- n ext-n ext; p-n ext=fr ont-n ext;fron t- n ext=p; front=front-n ext;p=rear- n ext;p=p-n ext; fron t=fr ont-nextp=p-n ext; rear=rear- n ext;retur n head;结束L( 5)主函数：/ 主函数void main()LNode *L,*W,*H;DataType a,b;int key,choice;/choice 记载操作 ,key 为输入值printf(*n);printf(n);H=Create(); / 调用 Create()

11、建立单循环链表 / 界面美化 printf(n);f*printf(*n);printf(*定位查找1*n);printf(*输出最大和次大值2 *n);printf(*输出比较值key后的结果3 *n);printf(*重新输入一个数组4 *n);printf(*退出系统0*n);printf(*n);printf(f*n);printf(n);/ 功能选择printf( 请选择系统功能 :);scanf( %d, &choice);printf(n);while(choice != 0)switch (choice)case 1:printf( 请输入要查找的值： ); scanf(%d,

12、&key); L=Locate(H,key);if(L!=NULL)printf( 查找成功 !n);break;case 2:Search(H,&a,&b);printf( 最大值： %dn,a); printf( 次大值： %dn,b);break;case 3:/ 查找数值 key 并返回指针/ 求链表的最大和次大值/ 将 key 插入链表中H=Sort(H);printf(*n);W=H-next;printf( 结果是： ); while(W!=H)printf( %d,W-data);/ 输出结果/ 依次输出W=W-next; printf(n);break;case 4:main

13、();default:printf( 请输入正确的选项！ ！n);/ 错误处理/ 功能重复f*4 *n);退printf(*printf(*printf(*定位查找1 *n);printf(*输出最大和次大值2 *n);printf(*输出比较值key后的结果3 *n);printf(*重新输入一个数组*n);出系统0 *n);printf(*n);printf(*n)；printf(请选择系统功能:);sea nf(” d, & choice);4运行结果:且目/， 券養i5103 (566 321 211 2133 65654 415大號五直二找大英先皇1H.旳结爭-rJMMMMMMNMX

14、MXMKMM MM MM KMKMXMrfMMMM1KKMNMNMPMr KM KM NM MFKH MMMM M MXM X霍二找大燹猊付岀幕出rl* H-stle退右累蜒一 -_0 *MM鯉璨聲虧茶二二二二二二二二二二二二二二二亏:请选擇系统功能诩nna finy )(u fcn cnnlziniim找大费绕 咅出新曲 定Bs迫杲415 f.bf-h W1335.问题与总结(1)在编写Create()函数时，要根据一维数组 A【M建立单循环链表，一开始 只是用 for 语句结合头结点创建单链表方法。 后来测试时发现这样无法建立有序 的单循环链表，要定义一个移动指针 *move 总是指向链表最后一个结点。( 2)在编写 Search() 函数时， 一开始是找出链表中最大值， 然后删去这个结点， 在剩下的结点中找出最大值，最后输出。 但后来测试整个程序运行时， 出现每次 执行 Search() 的功能后，别的函数就执行不了，调试之后才知道是找最大和次 大值破坏了链表的完整性， 导致其他函数执行