文档介绍：实验报告课程名称:数据结构班级:实验成绩:实验名称:顺序表和链表的应用学号:批阅教师签字:实验编号:实验一:实验日期:2017-11-25指导教师:组号:实验时间:18:30~22:30一、实验目的掌握线性表的基本操作(插入、删除、查找)以及线性表合并等运算在顺序存储结构、链式存储结构上的实现。重点掌握链式存储结构实现的各种操作。掌握线性表的链式存储结构的应用。二、实验内容与实验步骤(1)实验内容:实现约瑟夫环,约瑟夫环(Joseph)问题的一种描述是:编号为1、2、3……n的n个人按照顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数的上限值m,从第一个人开始按照顺时针的方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他的顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。设计一个程序求出出列顺序。(2)抽象数据类型和设计的函数描述,说明解决设想。首先定义一个链表,用其中的data项存储每个人的编号,用password项存储每个人所持有的密码,并且声明一个指针。之后使用CreatList_CL函数来创建一个循环链表,在其中的data和password中存入编号和密码,最后使最后一个节点的next指向L,使其能够形成循环队列。定义了函数Display来显示链表当中的内容,以确定存储的数据没有错误。定义了函数Delete_L来实现约瑟夫环中依次删除的功能,依次比较,如果某个人所持的密码和m值相等,则删除这个结点,并且输出此时该结点的编号和密码,实现出列的功能。简短明确地写出实验所采用的存储结构,并加以说明。该实验我主要采用的是线性表的链式存储结构,首先定义了链表的结构,其中包括data项和password项,分别存储每个人的编号和所持密码,还声明了指向下一个结点的指针,该指针可以连接各个结点,并且将最后一个结点的指针指向第一个结点使之成为一个循环链表。三、实验环境操作系统:Windows7调试软件名称:VisioStudio2017上机地点:信息楼B405四、实验过程与分析(1)主要的函数或操作内部的主要算法,分析这个算法的时、空复杂度,并说明设计的巧妙之处。本实验中主要的函数包括创建链表、显示链表内容和出列过程四个部分。主要函数的代码如下:创建链表:typedefintDatatype;typedefstructnode//链表的定义{Datatypedata;intpassword;structnode*next;}ListNode,*CLinkList;voidCreatList_CL(CLinkList*L,intn)//创建一个链表{inti,pin;CLinkListp,q;(*L)=(CLinkList)malloc(sizeof(ListNode)); if((*L)==NULL)printf("error\n");else (*L)->next=NULL; q=*L; for(i=0;i<n;i++) {p=(CLinkList)malloc(sizeof(ListNode)); if(p==NULL) printf("error\n"); printf("请输入第%d个人的密码:",i+1); scanf("%d",&pin); p->data=i+1; p->password=pin;q->next=NULL; q->next=p; q=p; } q->next=(*L)->next;//指向L结点,形成}创建这个链表的时间复杂度为O(n),空间复杂度为O(n2)。显示链表中的信息内容:voidDisplay(CLinkList*L,intn){inti;CLinkListp;p=(*L)->next;printf("\n显示链表内容\n");for(i=0;i<n;i++){printf("编号:%2d密码:%d\n",p->data,p->password); p=p->next;}}该算法的时间复杂度为O(n),空间复杂度为O(n2)。删除结点,完成出列功能:voidDelete_L(CLinkList*L,intn,intm){inti=0,j;CLinkListp,q;q=(*L);p=(*L)->next;printf("\n删除的顺序:\n");while(i<n){for(j=0;j<m-1;j++){q=p;p=p->next;}printf("编号:%d密码:%d\n",p->data,p->password);m=p->password;q->next=p->next;free(p);p=q->next;n--;}}该算法的时间复杂度为O(n2),空间复杂度为O(n2)。该设计的巧妙之处在于并不需要额外的空