数据结构实验指导书-单链表的基本操作

实验02单链表的基本操作实验学时：2学时实验类型：上机背景知识：单链表的插入、删除及应用。目的要求：.掌握单链表的存储特点及其实现。.掌握单链表的插入、删除算法及其应用算法的程序实现。实验内容：编写一个完整的程序，实现单链表的生成、插入、删除、输出等基本操作。随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。计算单链表的长度，遍历单链表。把单链表中的元素逆置（不允许申请新的结点空间）。在单链表中删除所有值为偶数的元素结点。编写在非递减有序单链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单链表。*利用算法5建立两个非递减有序单链表，然后合并成一个非递增有序链表。*利用算法5建立两个非递减有序单链表，然后合并成一个非递减有序链表。*利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数,另一个全部为偶数（尽量利用已知的存储空间）。*采用单链表实现一元多项式的存储并实现两个多项式相加并输出结果。在主函数中设计一个简单的菜单，分别调试上述算法。*综合训练：1）利用链表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等，并能够实现将数据存储到文件中）2）约瑟夫环问题：设有n个人围坐在圆桌周围，从某个位置开始编号为1,2,3,…，n,坐在编号为1的位置上的人从1开始报数，数到m的人便出列；下一个（第川+1个）人又从1开始报数，数到m的人便是第二个出列的人；如此重复下去，直到最后一个人出列为止，得到一个出列的编号顺序。例如，当n=8,mU时，若从第一个位置数起，则出列的次序为4,8,5,2,1,3,7,6o试编写程序确定出列的顺序。要求用不带头结点的单向循环链表作为存储结构模拟此过程，按照出列顺序打印出个人编号。实验说明：.类型定义typedefintElemType;〃元素类型typedefstructnodeElemTypedata;

structnode*next;JLinkNode,*LinkList;.为了算法实现简单，建议采用带头结点的单链表。注意问题：.重点理解链式存储的特点及指针的含义。.注意比较顺序存储与链式存储的各自特点。.注意比较带头结点、无头结点链表实现插入、删除算法时的区别。.单链表的操作是数据结构的基础，一定要注意对这部分常见算法的理解。部分源代码：DS.hinclude<stdio.h>include<stdlib.h>#include<string.h>include<math.h>defineTRUE1defineFALSE0defineOK1defineERROR0typedefintStatus;LinkList.hinclude“DS.h”typedefintElemtype;typedefstructNode{Elemtypedata;structNode*next;}Lnode,*LinkList;/*菜单*//*/*菜单*//*初始化空表*//*尾插法建立单链表*//*单链表遍历*//★计算单链表长度*//*单链表逆置///*删除值为偶数的结点*//*在有序单链表L中插入元素x,链表仍然有序StatusCreat_Linklist(LinkList&L);voidDisp_Linklist(LinkListL);intlength_Linklist(LinkListL);voidReverse_Linklist(LinkListL);voidDelEven_Linklist(LinkListL);Statuslnsert_Linklist(LinkListL,intx);

*/StatusCreatOrder_Linklist(LinkList&L);/*创建非递减有序单链表*/voidMergeDescend_Linklist(LinkListLa,LinkListLb,LinkList&Lc);/*两个非递减有序单链表La和Lb合并成一个非递增有序链表Lc*/voidMergeAscend_Linklist(LinkListLa,LinkListLb,LinkList&Lc);/*两个非递减有序单链表La和Lb合并成一个非递减有序链表Lc*/voidSplit_Linklist(LinkListLa,LinkList&Lb);/*链表La按值分解成两个链表，La全部为奇数，Lb全部为偶数*/LinkList.cpp#include"LinkList.h"voidmenu()printf(H\t\t\t单链表基本操作\n\n“);printf(”\t\t\t1printf(”\t\t\t1.建printf(”\t\t\t2.遍printf("\t\t\t3.计printf(”\t\t\t4.链printf(”\t\t\t5,删printf(”\t\t\t1.建printf(”\t\t\t2.遍printf("\t\t\t3.计printf(”\t\t\t4.链printf(”\t\t\t5,删立单链表\rT);历单链表\n")；printf(”\t\t\t1.建printf(”\t\t\t2.遍printf("\t\t\t3.计printf(”\t\t\t4.链printf(”\t\t\t5,删printf(”\t\t\t6,生成值有序单链表\n”);printf(”\t\t\t7printf(”\t\t\t7.合printf(”\t\t\t8.合printf(”\t\t\t9.分printf(”\t\t\tO.退printf(”\t\t\t7.合printf(”\t\t\t8.合printf(”\t\t\t9.分printf(”\t\t\tO.退并生成降序链表\n)printf(”\t\t\t7.合printf(”\t\t\t8.合printf(”\t\t\t9.分printf(”\t\t\tO.退/*初始化空表*/Statuslnit_Linklist(LinkList&L))/*尾插法建立单链表*/StatusCreat_Linklist(LinkList&L){)/*单链表遍历*/voidDisp_Linklist(LinkListL)}/*计算单链表长度*/intlength_Linklist(LinkListL){}/*单链表逆置★/voidReverse_Linklist(LinkListL){}/*删除值为偶数的结点*/voidDelEven_Linklist(LinkListL){}/*在有序单链表中插入元素，链表仍然有序★/Statuslnsert_Linklist(LinkListL,intx){LinkListp,q,s;}/*创建非递减有序单链表*/StatusCreatOrder_Linklist(LinkList&L){}/*两个非递减有序单链表La和Lb合并成一个非递增有序链表Lc*/voidMergeDescend_Linklist(LinkListLa,LinkListLb,LinkList&Lc){}/*两个非递减有序单链表La和Lb合并成一个非递减有序链表Lc*/voidMergeAscend_Linklist(LinkListLa,LinkListLb,LinkList&Lc)}/*链表La按值分解成两个链表，La全部为奇数，Lb全部为偶数*/voidSplit_Linklist(LinkListLa,LinkList&Lb)()main.cppinclude“LinkList.h"intmain()(intchoice,length;LinkListL,La,Lb,Lc;while(1)(menu();printf("选择你的操作：”);scanf(,,%d,,,&choice);switch(choice)(if(Creat_Linklist(L))printf("单链表创建成功\n”);elseprintf("单链表创建失败\n“);break;Disp_Linklist(L);break;length=length_Linklist(L);printf("单链表长度为：％d\n”,length);break;Reverse_Linklist(L);printf("逆置后的链表为:\nH);Disp_Linklist(L);break;DelEven_Linklist(L);printf("新链表为：\n”)；Disp_Linklist(L);break;if(CreatOrder_Linklist(L))(printf(”值有序链表为：\nH);Disp_Linklist(L);}elseprintf("单链表创建失败\n“);break;CreatOrder_Linklist(La);CreatOrder_Linklist(Lb);MergeDescend_Linklist(La,Lb,Lc);printf("合并后的新链表为:\nH)；Disp_Linklist(Lc);break;CreatOrder_Linklist(La);CreatOrder_Linklist(Lb);MergeAscend_Linklist(L