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 /定义结点的结构体 Da
3、taType 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(
4、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; /返回头指针开始定义变量: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,Da
5、taType key)LNode *Locate(LNode *head,DataType key) /建立定位查找函数Locate LNode *q=head-next; /查找并返回值为key的第1个元素的结点指针;若找不到,则返回NULLwhile(q!=head & q-data!=key) q=q-next; if(q-data=key) return q; else printf(查找的结点不存在!n); return NULL; Y开始定义变量:*q=head-next;;结束q!=head&q-data!=keyq=q-nextq-data=keyreturn qReturn
6、NULlLYNN(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=head-next; Secmax=head-next-next;while(p!=head) if(Max-data p-data) /*Max指向最大值 if(p-data Secmax-dat
7、a) Secmax=p; else /*Sexmax指向次大值 Secmax=Max; Max=p; p=p-next; *a=Max-data; /把最大和次大值分别赋值给*a和*b *b=Secmax-data;(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(请输
8、入key:); scanf(%d,&key); 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; /移动指
9、针 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; /返回头指针(5)主函数:void main() /主函数 LNode *L,*W,*H; DataType a,b
10、; 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(请选择系统功
11、能:); scanf( %d, &choice); printf(n); while(choice != 0) switch (choice) case 1: /查找数值key并返回指针 printf(请输入要查找的值:); scanf(%d,&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插入链表中 H=Sort(H); W=H-nex
12、t; 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(*
13、*n); printf(*n); printf(请选择系统功能:); scanf( %d, &choice);运行结果: 问题与总结(1)在编写Create()函数时,要根据一维数组A【M】建立单循环链表,一开始只是用for语句结合头结点创建单链表方法。后来测试时发现这样无法建立有序的单循环链表,要定义一个移动指针*move总是指向链表最后一个结点。(2)在编写Search()函数时,一开始是找出链表中最大值,然后删去这个结点,在剩下的结点中找出最大值,最后输出。但后来测试整个程序运行时,出现每次执行Search()的功能后,别的函数就执行不了,调试之后才知道是找最大和次大值破坏了链表的完整性,导致其他函数执行不了,最后定义了两个指针来带回最大和次大值。(3)设计Sort()函数时,为了保持结点之间的顺序时,一开始用各种方法,就是实现不了,后来看了队列的一章受到启发,定义指针front和指针rear分别控制结点key的前驱部分和后继部分,最后实现了保持顺序的功能。(4)设计菜单,一开始选择一个功能时都要输入一个数组,后来在主函数里面调用函数Create(),解决了这个问题。(5)健壮性处理:设计菜单是多一个功能:可以重新输入数组。