下载文档原格式
约瑟夫环实验报告总结【篇一：约瑟夫环实验报告】实验报告课程名称：数据结构实验名称：顺序表和链表的应用实验编号：实验一指导教师：一、实验目的（1）掌握线性表的基本操作（插入、删除、查找）以及线性表合并等运算在顺序存储结构、链式存储结构上的实现。
重点掌握链式存储结构实现的各种操作。
（2）掌握线性表的链式存储结构的应用。
二、实验内容与实验步骤（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值相等，则删除这个结点，并且输出此时该结点的编号和密码，实现出列的功能。
（3）简短明确地写出实验所采用的存储结构，并加以说明。
该实验我主要采用的是线性表的链式存储结构，首先定义了链表的结构，其中包括data项和password项，分别存储每个人的编号和所持密码，还声明了指向下一个结点的指针，该指针可以连接各个结点，并且将最后一个结点的指针指向第一个结点使之成为一个循环链表。
三、实验环境操作系统：windows 7调试软件名称：vc++版本号：6.0上机地点：综合楼311四、实验过程与分析（1）主要的函数或操作内部的主要算法，分析这个算法的时、空复杂度，并说明设计的巧班级：学号：姓名：组号：实验成绩：批阅教师签字：实验日期：实验时间：妙之处。
数据结构(线性表)习题与答案数据结构(线性表)习题与答案1. 线性表的定义线性表是一种常用的数据结构，它由一系列元素组成，并且每个元素具有前驱和后继关系。
线性表可以通过顺序存储或链式存储来实现。
2. 线性表的实现方式2.1 顺序存储顺序存储是利用数组来实现线性表的一种方式。
数组的每个元素可以存储一个数据项，通过下标可以快速访问和操作其中的元素。
2.2 链式存储链式存储是通过节点之间的指针关联来实现线性表的一种方式。
每个节点包含数据域和指针域，指针域指向下一个节点。
3. 线性表的基本操作3.1 初始化线性表初始化线性表需要给表头节点分配内存空间，并将头节点的指针域置为空。
3.2 插入元素在线性表的某个位置插入元素，需要先找到插入位置的前一个节点，然后将新节点插入到该位置。
调整节点之间的指针关联即可完成插入操作。
3.3 删除元素删除线性表中的某个元素，需要找到待删除元素的前一个节点，然后将该节点的指针指向待删除节点的下一个节点，释放待删除节点的内存空间即可。
3.4 查找元素查找线性表中某个元素的位置，可以从表头节点开始逐个比较节点的数据域，直到找到目标元素或者遍历结束。
4. 线性表的习题与答案4.1 习题1已知线性表L中的元素按非递减顺序排列，设计一个算法，将元素x插入到L中，保持L的有序性。
解答：1) 从表头节点开始，顺序遍历节点的数据域，找到第一个大于等于x的节点的前一个节点，记为p。
2) 创建新的节点node，将x赋值给node的数据域。
3) 将node的指针域指向p的下一个节点。
4) 将p的指针域指向node。
5) 插入完成。
4.2 习题2已知线性表L中的元素按递减顺序排列，设计一个算法，删除L中所有大于x的元素。
解答：1) 从表头节点开始，顺序遍历节点的数据域，找到第一个小于等于x的节点的前一个节点，记为p。
2) 将p的指针域指向p的下一个节点，删除p的后继节点。
3) 重复执行步骤2，直到遍历结束。
【例2.5】假设有n（n>1）个线性表顺序地存放在顺序表S[1..m]中，令F[i]和R[i]指示第i个（1≤i≤n）表的第1个元素和最后1个元素在S中的位置，并设定R[i]<F[i+1]，F[n+1]=m+1，如图2.2所示。
试写出实现下列要求的算法：（1）在第i个表中的第j项后面插入1个元素，仅当整个[1..m]空间填满时，不允许进行插入操作。
（2）删除第i个表中的第j个元素，要求在删除第j个元素后，该表仍为顺序存储的线性表。
【解】本题实质上是将n个线性表（长度可能不相同）放在一个连续空间（长度为m），来解决这些线性表的插入和删除问题。
（1）的算法如下：void ins(i，j，x){int p，k;if (R[n]==m)cout << "上溢" << endl;else{for (p=n;p>=i+1;p--) //将i+1到n的线性表后移一个元素{for (k=R[p];k>=F[p];k--) //将第p个线性表后移一个元素S[k+1]=S[k];R[p]++;F[p]++; //第p个线性表的首尾元素位置均增1}for (p=R[i];p>=j+1;p--)//将第i个线性表中的第j个位置起的元素均后移S[p+1]=S[p];S[p]=x; //在第i个线性表的第j个位置处存放xR[p]++; //第p个线性表的R[p]增1}}（2）的算法如下：void del(i，j){for (p=F[i]+j-1;p<=m;p++) //元素前移覆盖要删除的元素S[p]=S[p+1];for (p=i;p<=n;p++) //第i个及以后的线性表的R[i]值减1R[p]--;for (p=i+1;p<=n;p++) //第i＋1个及以后的线性表的F[i]值减1F[p]--;}【例2.6】设A=(a1，a2，⋯，a m)和B=(b1，b2，⋯，b n)均为顺序表。
第二部分课后习题第1章绪论1．简述数据与数据元素的关系与区别。
答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。
数据元素是数据的基本单位，是数据的个体。
数据与元素之间的关系是元素与集合之间的关系。
2．数据结构和数据类型有什么区别？答：数据结构是互相之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。
而数据类型是一个值的集合和定义在这个集合上的一组运算的总称，如C语言中的int数据类型是由-32768~32767（16位机）的整数和+、-、*、/、%等运算符组成。
3．设3个表示算法频度的函数f、g和h分别为：f（n）=100n3+n2+1000g（n）=25n3+5000n2h（n）=n1.5+5000nlog2n求它们对应的时间复杂度。
答：f（n）=100n3+n2+1000=O（n3），g（n）=25n3+5000n2=O（n3），当n→∞时，√n>log2n，所以h（n）=n1.5+5000nlog2n=O（n1.5）。
4．用C／C++语言描述下列算法，并给出算法的时间复杂度。
（1）求一个n阶方阵的所有元素之和。
（2）对于输入的任意三个整数，将它们按从小到大的顺序输出。
（3）对于输入的任意n个整数，输出其中的最大和最小元素。
答：（1）算法如下：本算法的时间复杂度为O（n2）。
（2）算法如下：本算法的时间复杂度为O（1）。
（3）算法如下：本算法的时间复杂度为O（n）。
5．设n为正整数，给出下列各种算法关于n的时间复杂度。
（1）（2）（3）答：（1）设while循环语句执行次数为T（n），则：（2）算法中的基本运算语句是if（b[k]>b[j]）k=j，其执行次数T（n）为：（3）设while循环语句执行次数为T（n），则：则6．有以下递归算法用于对数组a[i．．j]的元素进行归并排序：求mergesort（a，0，n－1）的时间复杂度。
第二题：建立一个线性链表，其元素值为：包括学号、姓名、性别、年龄等信息。
并依次从键盘输入（输入时要有相应的提示）以输入0结束，然后依次输出线性链表中的各元素值。
#include"stdlib.h"#include"stdio.h"#define null 0#define size 40struct node{char num[6];char name[8];char sex[2];int age;struct node * next;};void main (){int x;struct node * head;struct node * p,* q;head=(struct node *)malloc(size); p=head;printf("if exit:pleas into '0' "); scanf("%d",&x);while (x!=0){q=(struct node *)malloc(size); printf("num\n");scanf("%s",q->num);printf("name\n");scanf("%s",q->name);printf("sex\n");scanf("%s",q->sex);printf("age\n");scanf("%d",&q->age);p->next=q;p=q;printf("if exit:pleas into '0' ");scanf("%d",&x);}p->next=null;p=head;printf("\n num name sex age \n"); while (p!=null){printf("%8s%8s%6s%6d\n",p->num,p->name,p->sex,p->age); p=p->next;}}void main (){int x,iage,find=0;struct node * head;struct node * p,* q,*pt;head=(struct node *)malloc(size); p=head;printf("if exit:pleas into '0' "); scanf("%d",&x);while (x!=0){q=(struct node *)malloc(size);printf("num\n");scanf("%s",q->num);printf("name\n");scanf("%s",q->name);printf("sex\n");scanf("%s",q->sex);printf("age\n");scanf("%d",&q->age);p->next=q;p=q;printf("if exit:pleas into '0' ");scanf("%d",&x);}p->next=null;p=head;printf("\n num name sex age \n"); while (p!=null){printf("%8s%8s%6s%6d\n",p->num,p->name,p->sex,p->age);p=p->next;}printf("pleas into age :\n"); scanf("%d",&iage);pt=head;p=pt;pt=pt->next;while (pt!=null){if(pt->age==iage){p->next=pt->next;find=1;}elsep=pt;pt=pt->next;}if(find==0)printf("no find %d ",iage);elsep=head;printf("\n num name sex age \n"); while (p!=null){printf("%8s%8s",p->num,p->name);printf("%8s%5d\n",p->sex,p->age);p=p->next;}}第四题：现在假设有两个多项式a(x)=7x^8+6x^5+12x^2-9；b(x)=3x^11+10x^8+8x^2编写一个程序将这两个多项式相加，输出两个多项式及相加的结果#include<stdio.h>#include<stdlib.h>typedef struct polynode{int coef;int exp;struct polynode *next;}PNode;PNode *Creat_Linkst(int n);void PolyAdd(PNode *pa,PNode *pb);void Print_Linkst(PNode *H);main(){PNode *HA,*HB;int la,lb;printf("enter la,lb:");scanf("%d,%d",&la,&lb);printf("\ncreat HA\n");HA=Creat_Linkst(la); printf("A(x)=");Print_Linkst(HA);printf("\ncreat HB\n");HB=Creat_Linkst(lb); printf("B(x)=");Print_Linkst(HB); PolyAdd(HA,HB);printf("\nA(x)+B(x)=");Print_Linkst(HA); }PNode *Creat_Linkst(int n){PNode *head,*p,*s;int i;head=(PNode*)malloc(sizeof(PNode)); head->next=NULL;p=head;printf("enter coef,exp:\n");for(i=1;i<=n;++i){s=(PNode *)malloc(sizeof(PNode));scanf("%d,%d",&s->coef,&s->exp);s->next=NULL;p->next=s;p=s;}return(head);}void PolyAdd(PNode *pa,PNode *pb) {PNode *pre,*qa,*qb,*q;int sum;pre=pa;qa=pa->next;qb=pb->next;while(qa&&qb){if(qa->exp==qb->exp){sum=qa->coef+qb->coef;if(sum){qa->coef=sum;pre=qa;}else{pre->next=qa->next;free(qa);}qa=pre->next;q=qb;qb=qb->next;free(q);}}if(qb)pre->next=qb;free(pb);}void Print_Linkst(PNode *H){PNode *p;p=H->next;while(p->next){printf("%d^%d+",p->coef,p->exp);p=p->next;}if(p->exp)printf("%d^%d+",p->coef,p->exp);else printf("%d\n",p->coef);}。
实验题目一一、单链表基本运算【问题描述】设计并实现线性表的单链表存储和运算。
【基本要求】实现单链表的插入、删除和遍历运算，每种操作用一个函数实现。
插入操作：将一个新元素插入表中指定序号的位置。
删除操作：将指定序号的元素从表中删除。
遍历操作：从表头按次序输入所有元素的值，若是空表，则输出信息“empty list!”。
【实现提示】程序运行时，首先在main函数中创建空的、带头结点的单链表。
然后多次调用实现插入操作的函数（每次都将元素在序号1位置上插入），将元素依次插入表中，最后调用实现遍历操作的函数输出所有元素。
之后再多次调用实现删除操作的函数将表还原为空表（每次都删除第1个元素，每删除一个元素后，将表中剩余元素都输出一次）。
【测试数据】输入数据：1 2 3 4 5 0（为0时结束，0不存入链表）第一次输出：5 4 3 2 1第二次输出：4 3 2 1第三次输出：3 2 1第四次输出：2 1第五次输出：1第六次输出：empty list!二、约瑟夫环问题【问题描述】编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。
现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。
报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开始，重新从1开始报数，如此下去，直至所有的人全部出列为止。
【基本要求】利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
【测试数据】M的初始值为20；n等于7，7个人的密码依次为：3，1，7，2，4，8，4。
输出为：6，1，4，7，2，3，5【实现提示】程序运行时，首先要求用户指定初始报数上限值，然后读取各人的密码。
可设n≤30。
此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。
【选作内容】用顺序存储结构实现该题目。
三、一元多项式相加、减运算器【问题描述】设计一个一元稀疏多项式简单计算器。
《数据结构》课程实习题目实习一1、编写一个读入一个字符串，把它存入一个链表，并按相反的次序打印的程序。
2、设有一个单位的人员工资，有如下信息：name、department、base pay、allowance、total。
现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的base pay增加100元，增加后将工资数据显示于屏幕(每行1人)。
请编写能够完成上述工作的程序。
实习二1、试用分别用线性表的向量存储结构和链表存储结构来实现约瑟夫(Josephu)问题。
约瑟夫问题如下：设有n个人围坐圆桌周围。
从某个位置上的人开始从1报数，数到m的人便出列，下一个人(第m+1个)又从1报数开始，数到m的人便是第2个出列的人，依次类推，直到最后一个人出列为止，这样就可以得到一个人员排列的新次序。
例如，n=8,m=4,从第1个人数起，得到的新次序为48521376.实习三编写建立一个由单链表组织存储的整数序列的程序，链表中每个结点存储一个整型数值，以此为基础完成将整数b插入到该链表中第一个数值为a的结点之前的程序。
实习四采用llink-rlink方式存储二叉排序树，编写能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中序遍历结果的程序。
实习五对于给定的一个工程施工图，该图以边为单位从键盘输入，编写能够找出该图的关键路径的程序。
实习六假设有一个数据类型为整型的一维数组A，A 中的数据元素呈无序状态，编写一个采用堆排序法将A中的数据元素按由小到大进行排序的程序。
《数据结构》答案（答案仅供参考）实验一1、编写一个读入一个字符串，把它存入一个链表，并按相反的次序打印的程序。
#include<stdio.h>#include<malloc.h>{char ch;struct str *next;};void main(){char tem;struct str *p,*h,*s;h=malloc(sizeof(struct str));h->next=NULL;if(h!=NULL){printf("请输入一个字符：");//scanf("%c",&tem);tem=getchar();h->ch=tem;while(tem!='$'){printf("请继续输入：");s=malloc(sizeof(struct str));if(s!=NULL){tem=getchar();//scanf("%c",&tem);s->ch=tem;}if(tem=='$')free(s);else{if(h->next==NULL)h->next=s;elsep->next=s;p=s;}}p->next=NULL;}printf("字符串逆序输出为：\n");while(h->next!='\0'){p=h;while(p->next!='\0'){p=p->next;}printf("%c",p->ch);s->next='\0';}printf("%c",h->ch);printf("\n");}2、设有一个单位的人员工资，有如下信息：name、department、 base pay、allowance、total。
第二部分数据结构概述数据结构是计算机专业基础课程之一，是十分重要的核心课程。
计算机的所有系统软件和应用软件都要用到各种类型的数据结构。
要想更好运用计算机来解决实际问题，仅仅学习计算机语言而缺乏数据结构知识是远远不够的，瑞士著名的计算机专家沃思(N.Writh)曾经说过：“算法+数据结构=程序”。
可见有了程序设计的基本知识，掌握了一种程序设计语言，并不一定就能设计出比较好的程序，解决比较复杂的实际问题，还必须掌握数据结构及算法设计的基本知识。
数据（Data）数据是信息的载体。
它能够被计算机识别、存储和加工处理，是计算机程序加工的"原料"。
随着计算机应用领域的扩大，数据的范畴包括：整数、实数、字符串、图像和声音等。
数据元素（Data Element）数据元素是数据的基本单位。
数据元素也称元素、结点、顶点、记录。
一个数据元素可以由若干个数据项（也称为字段、域、属性）组成。
数据项是具有独立含义的最小标识单位。
为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。
【例1.1】学生成绩表，见下表。
注意：在表中指出数据元素、数据项、开始结点和终端结点等概念数据结构（Data Structure）数据结构指的是数据之间的相互关系，即数据的组织形式。
1．数据结构一般包括以下三方面内容：①数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）；数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。
数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构(Storage Structure)数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。
对机器语言而言，存储结构是具体的。
一般，只在高级语言的层次上讨论存储结构。
③数据的运算，即对数据施加的操作。
数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。
