数据结构课程设计单

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的后继结点 三、设计具有上述处理要求和退出系统菜单 单链表 所

3、采用的数据结构： 数据结构的定义： typedef struct Node /定义结点的结构体 / DataType data; 数据域 struct Node *next; 指针域/ 数据结构课程设计报告内容及其格式 LNode; /结点的类型 所设计的函数 （1） Create(void) LNode *Create(void) /建立单循环链表，链表头结点head作为返回值 M】/ int i,j,n,AM; 建立数组A【LNode *head,*p,*move; head=(LNode*)malloc(sizeof(LNode); /创建空单循环链表 head-next=head; m

4、ove=head; /输入数组 ); 牰湩晴尨 请输入数组元素的个数：scanf(%d,&n); ); 请输入数组： 牰湩晴尨 / for(i=0;in;i+) 保存数组元素 scanf(%d,&Ai); 各元素次序相同 A/勾链建表，使链表中元素的次序与数组 建立一个单循环链表 AM for(j=0;jdata=Aj; p-next=move-next; move-next=p; move=move-next; 返回头指针/ return head; 数据结构课程设计报告内容及其格式 开始：变量定义循空单建立数维建立一j=0 N JY if J+ (Aj=32767)br结 Locate(L

5、Node *head,DataType key) （2）Locate LNode *Locate(LNode *head,DataType key) /建立定位查找函数 LNode *q=head-next; NULL 若找不到，key查找并返回值为的第1个元素的结点指针；则返回/ while(q!=head & q-data!=key) q=q-next; if(q-data=key) return q; else 数据结构课程设计报告内容及其格式 牰湩晴尨查找的结点不存在！n); return NULL; 开 定义变量： q!=head&Y q=q-Nq-daNYReturnretu结 S

6、earch(LNode *head,DataType *a,DataType *b) ）3（数据结构课程设计报告内容及其格式 /求链表的最大值和次大值，分别由*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-dat

7、a Secmax-data) Secmax=p; 指向次大值else /*Sexmax Secmax=Max; Max=p; p=p-next; *b 和*a=Max-data; *a把最大和次大值分别赋值给/ *b=Secmax-data; 数据结构课程设计报告内容及其格式 开LNode *p,*Max,*SeN P!=Y N Max-dataY p-data Y N Secmaxp=p-Secm*a=Max- 数据结构课程设计报告内容及其格式 （4）Sort(LNode *head) /查找key,把链表中比key小的作为前驱结点，比key大的作为后继结点 LNode *Sort(LNod

8、e *head) /*front指向key前部分链表，*rear指向key后部分链表 DataType key; LNode *k,*p,*front,*rear,*L; front=head; p=head-next; ); ：请输入 key牰湩晴尨scanf(%d,&key); /调用L=Locate(head,key); Locate()查找 key k=L; rear=k; while(p!=head) / 判断 key前面链表是否已经比较完毕if(front-next!=k) if(p-data k-data)/将key 结点前驱比key大的插到key后面 front-next=fr

9、ont-next-next; /断开结点 / p-next=rear-next; 插入结点 rear-next=p; rear=rear-next; p=front-next; key/*p指回的前驱结点 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

10、-next; /*p指回key p=rear-next; 的后继结点 else /移动指针 p=p-next; rear=rear-next; return head; 返回头指针/ 数据结构课程设计报告内容及其格式 开LNode *k,*p,*front,*rear,*L; DataType key; front=headN p!=Y N front-Y p=rearN N p-datap-dataY Y front-next=frear-next=rront-next-near-next-ext;ext;p=p-p=p-nretu结 数据结构课程设计报告内容及其格式 （5）主函数： voi

11、d main() /主函数 LNode *L,*W,*H; DataType a,b; int key,choice; /choice 记载操作 ,key 为输入值 printf(); / H=Create(); 调用Create() 建立单循环链表 界面美化/printf(); printf(* *n); printf(* *n); printf(* 定位查找-1 *n); printf(* 输出最大和次大值-2 *n); printf(* 输出比较值key后的结果-3 *n); printf(* 重新输入一个数组-4 *n); printf(* 退出系统-0 *n); printf(* *

12、n); printf(*n); printf(); 数据结构课程设计报告内容及其格式 /功能选择 牰湩晴尨请选择系统功能:); scanf( %d, &choice); printf(); while(choice != 0) switch (choice) case 1: /查找数值key并返回指针 ); 牰湩晴尨请输入要查找的值： scanf(%d,&key); L=Locate(H,key); if(L!=NULL) !n); 牰湩晴尨查找成功 break; /求链表的最大和次大值 case 2: Search(H,&a,&b); %dn,a); 牰湩晴尨最大值： %dn,b); 次大值

13、： 牰湩晴尨 break; / 将key插入链表中 case 3: H=Sort(H); 数据结构课程设计报告内容及其格式 W=H-next; 牰湩晴尨结果是：); /输出结果 while(W!=H) / 依次输出 printf( %d,W-data); W=W-next; printf(); break; case 4: main(); default: 牰湩晴尨请输入正确的选项！n); /错误处理 /功能重复 printf(*n); printf(* *n); printf(* 定位查找-1 *n); printf(* 输出最大和次大值-2 *n); printf(* 输出比较值key后的

14、结果-3 *n); printf(* 重新输入一个数组-4 *n); 统系出退printf(* 数据结构课程设计报告内容及其格式 -0 *n); printf(* *n); printf(*n); 牰湩晴尨请选择系统功能:); scanf( %d, &choice); 运行结果： 数据结构课程设计报告内容及其格式 问题与总结 （1）在编写Create()函数时，要根据一维数组A【M】建立单循环链表，一开始只是用for语句结合头结点创建单链表方法。后来测试时发现这样无法建立有序的单循环链表，要定义一个移动指针*move总是指向链表最后一个结点。 （2）在编写Search()函数时，一开始是找出链表中最大值，然后删去这个结点，在剩下的结点中找出最大值，最后输出。但后来测试整个程序运行时，出现每次执行Search()的功能后，别的函数就执行不了，调试之后才知道是找最大和次大值破坏了链表的完整性