实验一 线性表的基本操作实现及其应用(6)

int Data; Link*next;

}; Link *Creat(int n) {

Link *head,*s,*r; head=new Link; r=head;

for (int i=0;i

s=new Link;

cin>>s->Data; r->next=s; r=s;

r->next=head->next; }

(二) “约瑟夫环”的操作模块； Link* Jose(Link*p,int m)

return head;

{ } (三) 主程序

int main() {

cout<<\请输入Jose环中人数：\ int n,m;

cin>>n;

cout<<\请输入每个人手中的序号：\ Link*head=Creat(n); int s=m; if (p==p->next)

return p;//递归出口即循环链表只剩下一个结点，将该结点指针返回

Link*q=NULL;//指针q用来保存删除结点的前驱 for (int j=1;j

q=p; p=p->next;

} //查找要删除结点 q->next=p->next; //删除节点 cout<Data<<\ \ //输出结点序号 Jose(p->next,s);//递归调用

}

cout<<\请输入报数的数值\ cin>>m;

Link*p=head->next; cout<

cout<<\离开的序号依次是：\ Link*Result=Jose(p,m); cout<Data<

测试数据

调分

试析

1、早期程序只写了约瑟夫环的实现部分，没有对输入数据进行筛选，调试的时候会经常出错。比如是输入字母，或者输入0，大于32767溢出； 2、早期的循环过程中没有进行优化，导致循环次数过多，浪费时间；

3、为了输出时美观，分别在input和main函数主体内做了两次，输入非零的判断，浪费了资源； 4、算法的时空分析

为了限制在输入过程中不会上溢，只在输入中限定为四个不全为零的数字，但是做的是do……while循环，复杂度为o（1）;

当n大于1时：

在数据输入中，链表的创建是for循环，时间复杂度为o（n-1） 在约瑟夫环实现程序中，为for循环。时间复杂度为o（m%n -1） 当n=1时，复杂度为o（1）。

实验心得

1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。 2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。

3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。

4、通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库实验一 线性表的基本操作实现及其应用(6)在线全文阅读。