2013年算法与数据结构文档

《2013年算法与数据结构文档》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.....*******************实践教学*******************兰州理工大学计算机与通信学院2013年春季学期算法与数据结构课程设计题目1：跳马问题题目2：约瑟夫问题题目3：最短字符串专业班级：11级计算机科学与技术2班姓名：王军学号：11240222指导教师：王燕成绩：学习参考.....目录摘要2序言3第一章题目简介4第二章分析需求5第三章数据类型6第四章各模块的流程图及伪码算法8第五章函数的调用关系图12第六章测试结果14原程序22设计总结33参考文献34致谢35学习参考.....摘要本程序主要解决最短字符串问题,跳马问题,

2、约瑟夫(Joeph)问题。最短字符串问题是从输入中读取字符串，并按长度顺序，最短字符串优先的原则输出它们。如果有若干字符串具有相同的长度，就按字母顺序输出它们。跳马问题是要求在64个国际象棋格子,任意位置放一个马,如何不重复地把格子走完。约瑟夫（Joeph）问题描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止

3、。这些程序主要功能是加深我们对算法与数据结构中存储，线性表和栈的理解。让我们对算法与数据结构有个更深刻的认识。关键词：最短字符跳马约瑟夫学习参考.....序言算法与数据结构在计算机科学与技术中，尤其是在计算机软件设计中有举足轻重的重要作用。在几乎所有的计算机软件系统中，如操作系统、数据库系统、编译系统、计算机网络技术、软件工程等都要用到算法与数据结构的知识。算法与数据结构已经成为计算机科学与技术专业和其他与软件有关专业的重要的专业基础课。本文通过约瑟夫（Joeph）问题，最短字符串问题，跳马问题加深我们对算法与数据结构的认识及学习算法与数据结构的重要性。本文

4、通过这三个简单程序介绍链式存储中单链表循环以及线性表中栈的应用和数组的应用。通过对跳马问题研究，可以加深我们对栈中栈的初始化，入栈，出栈的理解。知道栈在算法与数据结构中的重要性。让我们在学习算法与数据结构时对栈有一个清晰的认识，以便与为今后的软件开发打好基础。约瑟夫(Joeph)问题采用单链表循环结构，表中所有结点被链在一个环上。因为从表中任何一个结点出发均可访问到表中的其他结点。约瑟夫（Joeph）问题是单链表循环最好的展现。让我们知道在数据处理过程中循环的重要性，在存储过程中空间的节约有着重要作用。最短字符串问题采用数组的方式建立起来的。通过本文三个简单

5、而具有代表性的程序，让我知道循环单链表，栈，数组在算法与数据结构重要性。也给我们在今后的学习中铺平道路，了解在软件开发中算法设计是很重要的。本文只对这三种算法加以说明和应用，在算法与数据结构中对复杂的数据结构如二叉树、图、散结结构没有加以说明和应用。希望读者在学习算法与数据结构时对这些数据结构也要重视。为将来软件开发打好基础。本文在写时由于时间紧迫，个人能力有限难免会有一些错误，真诚地希望读者批评指正。学习参考.....第一章题目简介1.约瑟夫（Joeph）问题。是描述一种：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始

6、任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。2.最短字符串问题。编写一个程序，从输入中读取字符串，并按长度顺序，最短字符串优先的原则输出它们。如果有若干字符串具有相同的长度，就按字母顺序输出它们。3.跳马问题。要求在64个国际象棋格子,任意位置放一个马,如何不重复地把格子走完。学习参考.....第二章分析需求1．约瑟夫（Joeph）问题：该问题适合采用循环单链表（为

7、了便于操作，可使其不带头结点）存储相关数据。问题求解时，首先从头指针顺序从1扫描到第m个结点，取其密码作为新的报数上限m，输出其序号，删除该结点，然后从其后继结点重复上述动作，直到输出n个结点。2．最短字符串问题：该问题通过输入一些字符串，通过判断字符串的长短优先输出最短的字符串，如果长度相同则按字母顺序输出字符串。该程序采用数组的形式来实现该问题。3．跳马问题：国际象棋中马采用“日”字走法，对棋盘上任意一个马所在的结点，它所能走的结点在一步之内有八种情况，即假设马所在的坐标为（i，j），那么它能走的八个坐标分别为（i+1，j+2），（i+1，j-2），（i

8、+2,j-1），（i+2,j+1），（i-2,j-1