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

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

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

3、aType 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",&n);

4、printf(" 请输入数组：");for(i=0;i<n;i+)scanf("%d",&Ai);/ 输入数组/ 保存数组元素/勾链建表，使链表中元素的次序与数组 A各元素次序相同for(j=0;j<n;j+)根据一维数组AM建立一个单循环链表p=(LNode*)malloc(sizeof(LNode);p->data=Aj;p->next=move->next;move->next=p;move=move->next;return head;/ 返回头指针(2) Locate(LNode *head,D

5、ataType key)LNode *Locate(LNode *head,DataType key) / 建立定位查找函数 Locate LNode *q=head->next;/查找并返回值为key的第1个元素的结点指针；若找不到，则返回NULL while(q!=head && q->data!=key)q=q->next;if(q->data=key)return q;elseprintf（" 查找的结点不存在！ ！ n"）;return NULL;YN(3) Search(LNode *head,DataType *a,Da

6、taType *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->da

7、ta)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;front=head;p=head->next;printf(&qu

8、ot; 请输入 key： ");scanf("%d",&key);L=Locate(head,key);k=L;DataType key;/ 调用 Locate() 查找 keyrear=k;while(p!=head)if(front->next!=k)if(p->data > k->data)/ 判断 key 前面链表是否已经比较完毕将 key 结点前驱比key 大的插到key 后面front->next=front->next->next;p->next=rear->next;rear->n

9、ext=p;rear=rear->next;p=front->next;elsep=p->next;front=front->next;/ 断开结点/ 插入结点/*p 指回 key 的前驱结点/ 移动指针elsep=rear->next;if(p->data < k->data)/ 将 key 结点后继比key 小的插到key 前面rear->next=rear->next->next;p->next=front->next;front->next=p;front=front->next;p=rear-&

10、gt;next;elsep=p->next;rear=rear->next;/ 断开结点/ 插入结点/*p 指回 key 的后继结点/ 移动指针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;NNNp->data< k->dataYfront=front-&

11、gt;nextp=p->next;rear=rear->next;rear->next=rear->next->next;p->next=front->next;front->next=p;front=front->next;p=rear->next;p=rear->next;return head;结束(5)主函数：void main()/ 主函数LNode *L,*W,*H;DataType a,b;int key,choice;/choice 记载操作,key 为输入值printf("n");H=Cre

12、ate();/ 界面美化 printf("n");/ 调用 Create() 建立单循环链表printf("I*n");printf("*n");printf("*定printf("*输出最2 *n");printf("*输出比较3 *n");printf("*重新输4 *n");printf("*退位查找大和次大值值key后的结果入一个数组出系统1 *n");0 *n");printf("*n");printf(&

13、quot;I*n");printf("n");/ 功能选择printf(" 请选择系统功能:");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&qu

14、ot;);break;case 2: / 求链表的最大和次大值Search(H,&a,&b);printf("最大值：%dn",a);printf("次大值：%dn",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(

15、);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(&q

16、uot;I*n");printf（" 请选择系统功能:"）;scanf(" %d”, &choice);4 .运行结果:4.1 1萩组元素的平栽，Q人数3：121 B1 W a GGGG 211 21J3 GSGS4 41 &付LJd-tH新山退古最雪茄一僵二找+<统12 3-0身i戈的值;321WL k . 一和当二 找大英玩 付出旧新旧 |谓XM MM NMKMXMXMK KM MM MMKMXMXMrf MM MM1nKtrXttXWN<MPO«M MM M K M M M M M M WM M M N M N

17、 M N融择系统功能eT 输 Kkos is果悬 11212 3 321 21 l 由IS E566 2133 B5fi5-4果 士II 1 1一揩二找大斐(统占最比博条位出H新山请迤择系统功能;5 nn Ikrsfcri cn-nfc irnift5 .问题与总结(1)在编写Create()函数时，要根据一维数组 A【M建立单循环链表，一开始 只是用 for 语句结合头结点创建单链表方法。后来测试时发现这样无法建立有序的单循环链表，要定义一个移动指针*move总是指向链表最后一个结点。( 2) 在编写 Search() 函数时， 一开始是找出链表中最大值，然后删去这个结点，在剩下的结点中找出最大值，最后输出。但后来测试整个程序运行时，出现每次执行 Search()