2013年算法与数据结构文档

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

2、字符串，并按长度顺序，最短字符串优 先的原则输出它们。如果有若干字符串具有相同 的长度，就按字母顺序输出它们。跳马问题是要 求在64个国际象棋格子，任意位置放一个马，如 何不重复地把格子走完。约瑟夫（Joeph）问题 描述是：编号为1,2,n的n个人按顺时针方向 围坐一圈，每人持有一个密码（正整数）。一开 始任选一个正整数作为报数上限值m从第一个 人开始按顺时针方向自1开始顺序报数，报到m 时停止报数。报mi勺人出列，将他的密码作为新 的m值，从他在顺时针方向上的下一个人开始重 新从1报数，如此下去，直至所有人全部出列为 止。这些程序主要功能是加深我们对算法与数据 结构中存储，线性表和栈的理解

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

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

5、铺平道路， 了解 在软件开发中算法设计是很重要的。 本文只对这 三种算法加以说明和应用，在算法与数据结构中 对复杂的数据结构如二叉树、图、散结结构没有 加以说明和应用。希望读者在学习算法与数据结 构时对这些数据结构也要重视。为将来软件开发 打好基础。本文在写时由于时间紧迫，个人能力 有限难免会有一些错误，真诚地希望读者批评指1.2.第一章题目简介约瑟夫（Joeph）问题。是描述一种：编号为1,2,n的n个人按 顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一 个正整数作为报数上限值m从第一个人开始按顺时针方向自1开始 顺序报数，报到m寸停止报数。报m勺人出列，将他的密码作为新的m

6、值，从他在顺时针方向上的下一个人开始重新从 1报数，如此下去， 直至所有人全部出列为止。试设计一个程序求出出列顺序。最短字符串问题。编写一个程序，从输 入中读取字符串，并按长度顺序，最短字 符串优先的原则输出它们。如果有若干字 符串具有相同的长度，就按字母顺序输出 它们。跳马问题。要求在64个国际象棋格子， 任意位置放一个马，如何不重复地把格子第二章分析需求1 约瑟夫（Joeph）问题：该冋题适合米用循环单 链表（为了便于操作，可使其不带头结 点）存储相关数据。问题求解时，首先 从头指针顺序从1扫描到第m个结点， 取其密码作为新的报数上限 m,输出其 序号，删除该结点，然后从其后继结点 重复上

7、述动作，直到输出n个结点。2.最短字符串问题： 该问题通过输入一些字符 串，通过判断字符串的长短优先输出最 短的字符串，如果长度相同则按字母顺 序输出字符串。该程序采用数组的形式 来实现该问题。3. 跳马问题： 国际象棋中马采用“日”字 走法，对棋盘上任意一个马所在的结 点，它所能走的结点在一步之内有八种 情况，即假设马所在的坐标为（i , j ）, 那么它能走的八个坐标分别为（i+1， j+2），（ i+1，j-2），（ i+2,j-1），（i+2,j+1 ），（ i-2,j-1），（ i-2,j+1），（i-1,j-2），（ i-1,j+2 ），把这八个点个看做是（i , j ）的领接点，

8、以此类推 每个结点都有邻结点，所以可采用图的 深度遍历，以马所在的结点（i , j ）为 初始结点，对全图进行深度遍历，然后 按照遍历的顺序输出结点。第三章数据类型1. 约瑟夫(Joeph)问题创建节点Node链表都是由一个个结点组成，由于结点的不同，组成的链表也不同。 由于每一个结点有一个密码和一个序号，所以可以将结点结构体定义为 typedef struct josint order;int mima;struct jos *li nk;Node;2. 最短字符串问题最短字符串采用数组的形式进行输入和排序的， 通过子函数input(char *str1)进行输入的，通过子函数input(c

9、har *str2)对输入的字符串进行排序。#define Max 100/预设最大字符串个数#defi ne MaxSize 256int num; /全局变量nun表示输入字符串3. 跳马问题#defi neMAXNUM8/横纵格数最大值#defineINVALIDDIR-1/无路可走的情况#defi neMAXLEN64/棋盘总格数#defi neMAXDIR8/下一步可走的方向typedef structintx;/表示横坐标inty;/表示纵坐标intdirecti on;/表示移动方向HorsePoi nt;HorsePoi ntChessPathMAXLEN;/模拟路径栈intc

10、ount;/入栈结点个数intChessBoardMAXNUMMAXNUM;/标志棋盘数组1n23第四章各模块的流程图及伪码算法1.约瑟夫（Joeph）问题1.1约瑟夫循环流程图1.2伪码算法创建单循环链表创建一个空单循环链表，双向循环链表和每个结点包括两个域：元素域和指针域。形成单循环链表的原理：定义三个指针变量 head，p, q三指针开始全部指 向头结点，在插入操作开始后，head不变仍指向头结点，p指针在插入过程中始 终指向新插入的节点，而q指针紧随其后，用于将新插入的节点和前一个节点连 接起来，最后通过q指向头指针head，来完成环的操作。关键代码实现如下：p=(Node *)mal

11、loc(sizeof(Node);q-li nk=p; p-order=i+1; p-mima=si+1;q=p;2.最短字符串问题2.1字符串的输入代码通过建立数组str1,当字符串的格数小于 宏定义中num时，可以输入一些字符串。具体 代码如下：int in put(char *str1)int coun t=0;char tempMaxSize;printf(输入字符串个数);sea nf(%d,&n um);while(co untn um)printf( 输入第 %(个 ,count+1); if(sca nf(%s,temp)&tempO!=O)str1co un t=(char*

12、)malloc(sizeof(temp);strcpy(str1co un t,temp);coun t+;puts( 输入完毕！);return 1;2.2字符串的排序代码当输入字符串时，调用函数sort() 进行排 序，更具字符串的长短进行排序。如果字符串长 度相同时，可以更具字母优先进行排序，具体代 码如下：int sort(char *str2)inf匸 charCDmp-Maxsizeb forTToxnum二+) forjll.+An u m=+) 宀 if(sfr-en(sfr2 曰)Asfr-en(sfr2 曰) 宀sfrcpy(CDmpsfr2 曰= sf rcpy (sf

13、r2ssf r2 曰 * sfrcpy(sfr2=LCDmp= if(sfr-en(sfr2 曰HHsfr-en(sfr2 曰) if(sfrcmp(sfr2 目 sfr2 曰Ao) 宀sfrcpy(CDmpsfr2 曰)- Sfrcpy(sfr2ssfr2 曰 X sfrcpy(sfr2=LCDmp=return 1;3.跳马问题3.1棋盘初始化伪码棋盘初始化的数组,通过建立Initiai() 函数。将 马没有在棋盘上走过的位置初始化为0，用ChessBoardij=0; 表示。其代码如下： void In itial()/棋盘初始化的数组int i,j;for(i=0;iMAXNUM;i+

14、)for(j=0;jMAXNUM;j+)ChessBoardij=0; /棋盘格均初始化为0,表示没有走过for(i=0;iMAXLEN;i+)ChessPathi.x=0;ChessPathj.y=0;ChessPathi.directio n=INVALIDDIR;cou nt=0;/栈中最初没有元素第五章函数的调用关系图进入主函数main()输入 调用子函数 Node输出出列第六章测试结果1. 约瑟夫问题1. 实验用例初值：8人数(n) =5各自密码：12 4 3 5 62. 测试结果(1 )输入人数(2)输入各自的密码出列顺序2. 最短字符串问题2.1 使用例子输入字符串 qwert

15、qwsacde asnde toubo 排序后 asnde qwert toubo qwsacde2.2 测试结果(1)主菜单(2)输入字符串3. 跳马问题(1) 输入初始值2 , 40, 0(2) 测试结果原程序1.约瑟夫问题#in clude #in clude typedef struct josint order;int mima;struct jos *li nk; Node;Node *creat(i nt n) Node *p,*q,*head;int i,s100;/输入各自的密码prin tf(请输入各自的密码：“)；for(i=1;iorder=1;head-mima=s1

16、;q=head;for(i=1;ili nk=p;p-order=i+1;p-mima=si+1;q=p; /将新结点插在链表的尾部p-li nk=head;/首位相接构成循环单链表retur n head;void mai n() Node *head,*q,*p;int i,m, n,cou nt=1,t=O,del1OO; printf( 请输入人数(n) sca nf(%d,&n);head=creat (n);p=head;q=head;printf( 请输入初值(m):); sca nf(%d,&m);for(i=1;ili nk; coun t+;deli=p-order;m=p

17、-mima; q-lin k=p-li nk;free(p);p=q-li nk;coun t=1;prin tf(出列顺序为：n);if(n=1)prin tf(%d,1);elsefor(i=1;i=n ;i+)prin tf(%dn,deli);2.最短字符串问题#in clude#in clude#in clude#define Max 100/预设最大字符串个数#defi ne MaxSize 256int num; /全局变量nun表示输入字符串个 数/字符串输入函数in t in put(char *str1)int coun t=0;char tempMaxSize;print

18、f(输入字符串个数);sca nf(%d,&n um);while(co untn um)printf(输入第 %(个 ,cou nt+1);if(sca nf(%s,temp)&temp0!=0) str1co un t=(char *)malloc(sizeof(temp);strcpy(str1co un t,temp);coun t+;puts(输入完毕！ ”)；return 1;/字符串排序函数int sort(char *str2)int i,j;char tempMaxSize;for(i=0;i num-1;i+)for(j=i+1;j nu m;j+)if(strle n(s

19、tr2j)strle n(str2i)strcpy(temp,str2j); strcpy(str2j,str2i);strcpy(str2i,temp);if(strle n(str2j)=strle n(str2i) if(strcmp(str2j,str2i)0) strcpy(temp,str2j); strcpy(str2j,str2i);strcpy(str2i,temp);puts(排序完毕！ ”)；return 1;/字符串显示函数void show(char *str)int i;for(i=O;i nu m;i+) puts(stri);void menu()puts(”=

20、 =);puts(=最短字符串问题=);puts(1、输入字符串);puts(、2、排序字符串);puts(.3、输出字符串);puts();4、退出puts(=);int mai n()int key,flag1=0,flag2=0;char *str1Max;whilesystem(cls); / 清屏fflush(stdi n);menu();printf( 请选择(1/2/3 ): n);sca nf(%d,&key);if(key=1)flag仁 in put(str1);else if(key=2)if(flag1) flag2=sort(str1);elseputs(没有字符串！

21、请选择1、输入字符串！ ”)；else if(key=3)if(flag1=1 &flag2=0)puts(“输入的字符串为：”)； show(str1);else if(flag1=1 &flag2=1)puts（排序后的字符串为：）;show(strl);elseputs(”没有字符串！请选择1、输入字 符串！ ”)；else if(key=4)return 0;elseprintf( 对不起，没有这个选项!n); system(pause); / 暂停3.跳马问题#in clude#in clude#defi ne MAXNUM 8/横纵格数最大值#define INVALIDDIR -

22、 1/无路可走的情况#defi ne MAXLEN 64/棋盘总格数#defi ne MAXDIR 8/下一步可走的方向typedef structint x;/表示横坐标int y;/表示纵坐标int directi on;/表示移动方向HorsePoi nt;HorsePo int ChessPathMAXLEN;/模拟路径栈int count;/入栈结点个数int ChessBoardMAXNUMMAXNUM; /标志棋盘数组void In itial()/棋盘初始化的数组int i,j;for(i=O;iMAXNUM;i+)for(j=0;jMAXNUM;j+)ChessBoardij

23、=0; /棋盘格均初始化为0,表示没有走过for(i=0;i=MAXNUM|posit on .y=MAXNUM|posit on .x0|posito n.ydirectio n=pare nt-directio n+;/上一结点能走的方向for(i=pare nt-directio n;ix+tryxi;/试探新结点的可走方向n ewpo in t.y=pare nt-y+tryyi;if(n ewpoi nt.xvMAXNUM&n ewpoi nt.x=0&ne wpoi nt.yvMAXNUM&n ewpoi nt.y=0&ChessBoar dn ewpoi nt.x newpoi

24、nt.y=O)pare nt-directio n=i;/上一结点可走的方向ChessBoard newpoi nt.x newpoi nt.y=1;/标记已走过retur n n ewpo int;paren t-directio n=INVALIDDIR;retur n n ewpo int;voidCalcPoi nt(HorsePoi nthh )/计算路径函数HorsePo int n posit on;HorsePoi nt *pposit on;In itial();/调用初始化函数pposit on=&hh;/调用输入初始点函数PushStack(*ppositon);whil

25、e(!(cou nt=0|cou nt=MAXLEN)/当路径栈不满或不空时ppositon=&ChessPathcount-1;/指针指向栈n positon=GetNewPoi nt(ppositon);/产生新的结点if(pposit on-directio n!=INVALIDDIR)/可以往下走ChessPathco un t-1.directio n=pposit on- directi on;PushStack(nposit on);elsePopStack();voidPrin tChess()/以8*8矩阵的形式输出运行结果int i,j;intstateMAXNUMMAXN

26、UM;stateij为棋盘上(i,j )点被踏过的次序intstep=0;/行走初始化HorsePo int posit on;cou nt=MAXLEN;if(cou nt=MAXLEN)/当棋盘全部走过时for(i=O;iMAXLEN;i+)step+;posit on=ChessPathi;stateposito n.xposit on .y=step;for(i=0;iMAXNUM;i+)prin tf(tt);for(j=0;jMAXNUM;j+)if(stateij10) prin tf();prin tf(%6d,stateij);/按顺序输出马踏过的点prin tf(n);pr

27、in tf(n);elseprintf(tt 此时不能踏遍棋盘上所有 点!n);int main (i nt argc,char *argv)HorsePo int h;h=Getl nitPoi nt();CalcPoi nt(h);Prin tChess();return 0;设计总结数据结构是计算机程序设计的重要理论技术基础，它是计算机科学的核心 课程。随着高级语言的发展，数据结构在计算机的研究和应用中已展现出强大 的生命力，它兼顾了诸多高级语言的特点，是一种典型的结构化程序设计语言, 它处理能力强，使用灵活方便，应用面广，具有良好的可移植性。紧张的三周课设就这样结束了，通过这三周的实践学习，不仅使我们巩固 了以前的知识并在此基础上还对数据结构的特点和算法有了更深的了解，使我 们在这门课程的实际应用上也有了一个提高。首先这