自己做的约瑟夫实验c++数据结构实验.doc

数据结构实验报告 实验名称： 实验1 线性表及其应用 实验目的：通过上机实验，掌握单链表的描述及其操作实现，加深理解线性表的逻辑、物理结构。 实验内容：（3选1）内容1：制作体育彩票的选号器；内容2：约瑟夫（Joseph）环问题；内容3：多项式的表示和相加。 实验要求：1）在C++系统中编程实现；2）至少实现三种以上操作算法； 3）写出算法设计的基本原理或画出流程图；4）算法实现代码简洁明了；关键语句要有注释；5）给出调试和测试结果；6）完成实验报告。 实验步骤： (1)算法设计 求解约瑟夫问题最直观(但非最高效)的方法就是直接模拟。借助循环链表(或者数组模拟的循环链表)来表示约瑟夫环，然后就模拟数数过程，当数到m时就将该元素从循环链表中删除，直到循环链表中只剩一个元素为止！算法设计流程图如图1所示。 图1 约瑟夫问题算法设计流程图 (2) 算法实现 using namespace std; typedef struct LNode //定义结构体 { int data; //data用来存储人的序号， int data1； //data1用来存储人的密码 struct LNode *next; }; lnode,*linklist; //定义结点 void initlist(linklist l,int n) //参数n传递人数 { int i; l=(linklist)malloc(sizeof(lnode)); //创建一个带头结点的链表 cinl-data; l-data1=1; l-next=l; lnode *p,*q; q=l; for(int i=0;i(n-1);i++) { p=(linklist)malloc(sizeof(lnode)); cinp-data; p-data1=(i+2); q-next=p; q=p; } if(n1) p-next=l; } void delet(lnode *p) //传递报数上限值和人数 { lnode *q; q=p; while(q-next!=p) //用一个while搜索循环链表 q=q-next; q-next=q-next-next; //删除结点 free(p); //释放动态申请的结点空间 } 实验结果: 程序执行结果如图2所示。 图2 约瑟夫程序执行结果 实验体会: 通过数据结构课程实验使更进一步了解数据结构的算法设计思想及实现方法, 并对在不同存储结构上实现不同的运算方法和技巧有所体会,从而达到锻炼理论与实践相结合的能力