数据结构课程设计报告.doc

数据结构课程设计报告目录散列表的设计与实现3（一）设计内容简介3（二）算法设计说明4（三）测试结果8迷宫9（一）设计题目：迷宫9（二）需求分析：9（三）概要设计：9（四）详细设计11（五）调试分析、测试结果14（六）设计心得体会15猴子选大王20（一）设计题目：猴子选大王20（二）需求分析：20（三）概要设计：20（四）详细设计：21（五）调试分析、测试结果24（六）设计心得体会25（七）附录25基数排序27（一）设计题目：基数排序27（二）需求分析：27（三）概要设计：27（四）详细设计：27（五）调试分析、测试结果:30（六）附录:31校园导游咨询：34（一）设计题目:校园导游咨询34（三）概要设计：35（四）详细设计：35（五）调试分析、测试结果：39（六）设计心得体会：41（七）附源码：41艺术品搬来搬去45（一）设计内容简介：45（二）算法设计说明：46（三） 测试结果：47（四）分析与探讨48大数运算48（一）设计内容简介48（二）算法设计说明：49（三）测试结果52灾区救灾53（一）设计内容简介：53（二）算法设计说明：54（三）测试结果：5556（四）分析与探讨56最小生成树56（一）设计题目：最小生成树56（二）需求分析：56（三）概要设计：57（四）详细设计：57（五） 调试分析，测试结果：59（六） 设计心得体会:59（七）附录:60散列表的设计与实现（一）设计内容简介题目：散列表的设计与实现任务：设计散列表实现电话号码查找系统。要求：（1) 设每个记录有下列数据项：用户名、电话号码、地址；（2) 从键盘输入各记录，以用户名（汉语拼音形式）为关键字建立散列表；（3) 采用一定的方法解决冲突；（4) 查找并显示给定电话号码的记录； （二）算法设计说明在设计和实现哈希表时需要用到哈希函数，这是本次的重点，其他的输入和查找可以通过以前学到的顺序存储结构的相关知识进行解决。先看一下哈希函数的设计和实现，由于定义的名字是20个字符，则在输入后可以很容易知道它的第一个字母的相对应的阿克什码，利用阿克什码%哈希表的长度就应该得到它的位置。然而对于一些数据可能会有发生一些冲突，这就需要我们解决冲突，对于这个冲突我是将待处理的冲突记录后移一位，若还冲突则还后移直到有空位或者记录满为止。再看一下按照电话号码查找时，由于不是按照电话号码排序进行的在查找电话号码时只能是从头到尾进行逐一检查对比，若对应的电话号码相同则输出其他的信息，直到最后仍没有则输出相关提示信息。其相应的数据结构如下：typedef char keytype20;typedef structkeytype name;/姓名int teleno; /电话号码char address100;/家庭住址rectype;/记录的类型typedef structrectype recordm;/哈希表中有m个记录int flagm;/标记，若有记录则标记为1，否则为0int currentsize;/当前哈希表中已被占用的个数hashitem;其中调用的相关函数：inithash(h);/初始化哈希表，将记录清空inputrecord(h);/想哈希表中输入记录信息，需要调用到上述哈希处理printrecord(h);/输出已经输入的信息findrecord(h);/根据电话号码查找记录saverecord(h);/保存输入到程序中的记录到当前文件夹中对于整程序则有如下流程图：在输入信息时为了解决冲突，需要设计一个哈希函数，下面是我自己设计的哈希函数：bool hash(hashitem &h,rectype inrecord)int key=(int)inr0%m;while(true)if (h.flagkey=0)/如果原记录不存在，则进行赋值h.flagkey=1;h.recordkey=inrecord;return true; else/原记录存在/if(h.recordkey.teleno=inrecord.teleno)if(strcmp(h.recordk,inr)=0)cout哈希表中记录h.recordk已存在了endl;return false;elsekey+;/coutjkjk;考虑到没有输入数据时，不能进行查找和输出，所以要在调用检查这种情况，这样就可以避免不必要的错误。if(h.currentsize=0)cout记录为空，请输如信息endl;return false;输入数据时也需要考虑是否已经输入过，为了解决这个问题，在调用进行哈希处理时就需要在附加在已经发生冲突的位置进行比较，若有相同记录则输入过则给予相关提示。（三）测试结果 在没有输入任何数据的情况下，会有提示信息按照电话号码查找相关记录（四）分析与探讨在设计哈希表时考虑到便捷和操作的方便（因为输入姓名时必须至少输入一个字母），利用首字母的阿克什码，然而这样的发生冲突的概率会很大，这就需要一个更不易发生冲突的哈希函数，其中一种哈希函数，就是将姓名的每个字符的阿克什码的值相加在进行处理，这样较我的方法更科学，也更不易发生冲突。 对于一个好的哈希函数在时间和空间复杂度上不是很高，同时发生冲突的机会较少，这样的函数才是一个真正的好函数。迷宫 （一）设计题目：迷宫（二）需求分析：任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；（三）概要设计： 在迷宫设计中，由于不能使用递归则可以借助栈来实现在迷宫中的前进和后退。同时在还需要设计迷宫的大小、迷宫的出入口、根据输入的入口来寻找迷宫的出口，并把路径输出来。在这个编程中由于不知道所走路劲步数，所以采用了链式栈实现每一步的移动，若找到出路则前进否则返回下一步改变方向来实现相关的移动，所以栈在其间起到了工具作用。在设计迷宫大小和出入口时，采用的是根据操作者实现的，但迷宫的具体路障和通道是随机实现的。当然，重点是如何从出口来找出口。求迷宫的一条通路的伪码如下：设当前初始位置为出口：do 若当前位置可通，则 将该位置插入到栈顶；/纳入路径 若该位置为出口位置。则结束当前程序；/求得的路径放在栈中 否则切换当前位置的东临位置（即向右）为新的当前的位置； 否则 若栈不为空且栈顶元素尚有其他位置未被探索，则设定新的当前位置为沿着顺时针旋转得到的栈顶位置的下一个临快； 若栈不为空且栈顶位置的四周均不通 则删去栈顶元素；/后退一步，从路径中删去该通块 若栈不空，则重新测试新的栈顶位置，直到找到一个可通的相邻块或出栈至栈空； /否则while(栈不为空)本程序的模块 主程序从main()函数中进行，包括输入迷宫的大小等信息，然后调用迷宫模块，在迷宫模块中也调用了栈的模块。栈模块实现栈抽象数据类型迷宫模块实现迷宫抽象数据类型各模块之间的关系如下： 主程序模块 迷宫模块栈模块（四）详细设计 1坐标的位置类型： typedef struct int r; int c;postype;2.迷宫类型：typedef structint col,row;/迷宫的大小int arrranglerangle; /0表示障碍，1表示是可走的通道，-1表示外界的围墙 /2表示已经走过， 3表示已经知道其不能通过mazetype;void initmaze(mazetype &m,int col,int row)/按照用户的输入的行数row和列数col列的二维数组（元素值为1或0）/设置迷宫的错初值，加上边缘的一圈的值 void printmaze(mazetype m)/根据已经进行二维数组的标记值来输出迷宫（或者其通路）bool pass(mazetype m,postype pos)/求解迷宫m中，从start到end的一条路径/若存在则返回true，否则返回falsestack s;initstack(s);postype curpos=start;/设置当前坐标为入口位置；int curstep=1; /当前的步数bool find=false; /是否找到出口elemtype e;do if(pass(m,curpos)/如果当前位置可以通过（不是障碍物且未曾留下足迹） footprint(m,curpos);/在当前位置标记为2 e.step=1; e.seat=curpos; e.di=1;/初始化为向东临位置移动（即向右） push(s,e);/将已经周的的放入栈中 if(curpos.c=end.c&curpos.r=end.r)/如果找到了出口则终止，并返回true find=true; return find; else/在其东临位置上移动，当前步数加一 curpos=nextpos(curpos,1); curstep+; else/当前位置不能通过 if(!stackempty(s) pop(s,e);/将已经走过的最近位置弹出，数据保存在e中 while(e.di=4&!(stackempty(s)/当方向改变一周后仍不能找到可通过的路径 markprint(m,e.seat);/留下不能通过的标记 pop(s,e);/删除站定元素 curstep-; /while if(e.di4)/不能通过则改变方向 e.di+;/方向顺时针改变一下 push(s,e); curpos = nextpos(e.seat,e.di); /求下一个节点 /if /if /elsewhile(!stackempty(s)&!find);/(!stackempty(s)&!find);/当栈不为空且没有找到出口return false;/没有找到出口则返回false 从入口口到出口的查找的流程图（五）调试分析、测试结果 （1）由于是不确定的步骤，采用的是易于操作的链式栈，这样就不免了时间和空间的浪费。 （2）对于设计迷宫，可能会觉得会很繁琐，刚开始也是自己设计迷宫图，但由于是随机设定迷宫的大小这就需要利用随机数来设计一个迷宫图。而利用%运算则可以解决这个问题，因为在设置迷宫数组时，1就代表通道，而0就是障碍，随意一个随机数%2得到的就是0或者1就可以自由设计迷宫了。 （3）来利用到进出栈时为计算进出栈的情况，特设定了curstep来调试程序的执行。那下面就介绍一下设计的迷宫界面情况： （六）设计心得体会 在知识方面,在设计迷宫时需要用到一些基本的如栈的相关信息，来解决不能使用递归的问题，递归在使用过程中虽然简介但不易理解通过栈的使用来加强我们对递归的使用。 在对问题的理解上我们通过对相关知识的理解和认识，来解决一些实际问题。附： *迷宫的相关信息*/#define rangle 100typedef structint col,row;/int arrranglerangle; /0表示障碍，1表示是可走的通道，-1表示外界的围墙 /2表示已经走过， 3表示已经知道其不能通过mazetype;void initmaze(mazetype &m,int col,int row)/按照用户的输入的行数row和列数col列的二维数组（元素值为1或0）/设置迷宫的错初值，加上边缘的一圈的值m.col=col;m.row=row;int i;/根据随机产生数进行初始化这个二维数组for(i=1;im.row+2;i+)for(int j=1;jm.col+2;j+)/srand(time(0);int n=rand()%101+100;m.arrij=n%2;/得到的值是1或者0，即恰好是路或是通道/围墙的标记for(i=0;im.col+2;i+)m.arr0i=-1;m.arrm.row+1i=-1;for(i=0;im.row+2;i+)m.arri0=-1;m.arrim.col+1=-1;void printmaze(mazetype m)/根据已经进行二维数组的标记值来输出迷宫（或者其通路）int i,j;for(i = 0; i m.row+2; i+) for(j = 0; j m.col+2; j+) if(m.arrij = 0) cout; /障碍，在dos界面上是白色的else if(m.arrij =-1)cout;/围墙else if(m.arrij =2)cout; else cout ; coutn; bool pass(mazetype m,postype pos)/若在迷宫m中，当前位置pos不是障碍物0，不是围墙-1，以前没有经过2且不是不可通过3 则可以通过，并返回trueif(m.arrpos.rpos.c!=0&m.arrpos.rpos.c!=-1&m.arrpos.rpos.c!=2&m.arrpos.rpos.c!=2&m.arrpos.rpos.c!=3)return true;else return false;void footprint(mazetype &m,postype pos)/在迷宫中的pos的位置留下足迹，证明已经经过这个位置m.arrpos.rpos.c=2;void markprint(mazetype &m,postype pos)/在迷宫的pos位置，留下不能通过的标记m.arrpos.rpos.c=3;postype nextpos(postype curpos, int dir) /根据不同的方向来进行移动postype returnpos; switch (dir) case 1:/向右 returnpos.r=curpos.r; returnpos.c=curpos.c+1; break; case 2:/向下 returnpos.r=curpos.r+1; returnpos.c=curpos.c; break; case 3:/向左 returnpos.r=curpos.r; returnpos.c=curpos.c-1; break; case 4:/向上 returnpos.r=curpos.r-1; returnpos.c=curpos.c; break; return returnpos;void main()mazetype m;int col,row;postype start,end;loop:coutrow;coutcol;initmaze(m,col,row);cout迷宫图：n;printmaze(m);coutstart.rstart.c;coutend.rend.c;if(start.rm.row|start.cm.col|start.r=0|start.c=0|end.rm.row|end.cm.col|end.r=0|end.c=0)/查看输入数据的准确性cout输出有误！n;else if(mazepath(m,start,end)/若找到了相关路径则输出路径信息printmaze(m);else /如果没有找到相关路径则输出提示信息cout没有可通的出路n;char ch;coutch;if(ch=y|ch=y)goto loop;else if (ch=n|ch=n)return ;猴子选大王（一）设计题目：猴子选大王（二）需求分析：任务：一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求：（注：分别顺序存储结构和链式存储实现）输入数据：输入m,n。 m,n 为整数，nm ? 1 : i+1);（m表示猴子的个数），这样首尾便可以相连，对于已经出列的猴子还要给予标记，另外需要借助一个计时器来表示间隔数，在经过已经出列的的猴子时不予计数。2 链式存储结构链式结构的约瑟夫环是通过创建循环链表来实现的，直至只剩下一个猴子时就输出有关猴子的信息。链式约瑟夫可以动态分配结点，同时可以较容易地实现循环结构，在每次猴子出列时就把这个结点给删除了，这样在数间隔数时就不用再进行计数。主程序所以总程序的控制流程图为： 顺序存储结构链式存储结构退出 （四）详细设计： 顺序存储： typedef struct int no;/序号int flag;/标记 1表示尚未出圈 0表示已经出圈monkey2; 其流程图：链式存储结构：typedef struct nodeint no;node *next;monkey,list;采用链式存储结构时可以利用循环链表，这样就可以很容易实现约瑟夫环。猴子选大王的关键函数如下：node* creat(int m)/创建一个含有m个结点的循环链表，使得第m个的next指针指向第一个void trave(node *p,int n)/在循环链表中报 n 的猴子出列,直至最后一个被输出int i;node *q=p; /cout出列顺序：next!=p)/当循环链表不是只剩下一个结点for (i=1;inext;if (p-next!=p) /不是只剩下一个时q=p-next;/coutnonext=q-next;i+;delete q;p=p-next;/whilecoutn最终的猴王：nonext!=p) 。输入猴子的总数和间隔数，最后输出最后的大王的序号。（六）设计心得体会猴子选大王就是约瑟夫环的应用的实例，且是必须用两种存储结构。在利用顺序存储时可以借助辅助结构体标记每一个猴子的序号和是否出列，然后按照while(jm ? 1 : i+1);j+=jophusi.flag; /若已出圈则 +0 就意味着跳过来实现循环。这样就可以很容易来将数组循环化。（七）附录利用顺序存储结构void monkeyarray() int i,j,n,m;coutm;monkey2 *jophus=new monkey2m+1;/动态分配m+1个数for( i=1;i=m;i+)jophusi.no=i;jophusi.flag=1;int space;coutspace;i=1,j=1,n=0;/i=1表示从第一个开始报数，j=1表示默认 /cout出圈序列为:endl;while(true)while(jm ? 1 : i+1);j+=jophusi.flag; /若已出圈则 +0 就意味着跳过/cout jophusi.no;jophusi.flag=0;/出圈就标记一下n+;/用于标记出圈猴子的个数/if(n%10=0) coutendl;/每10个一行if (n=m)cout最终选出的大王为：jophusi.noendl;break;j=0;coutendl;基数排序（一）设计题目：基数排序（二）需求分析：假设有n个待排序记录，记录ri的关键字为keyi, keyi由d位十进制数字组成，即keyi=ki1 ki2 ki3 kid ,试分别采用链式存储结构和顺序存储结构实现基数排序。（提示：为提高基数排序效率，采用顺序储结构的方式可以仿造稀疏矩阵转置中的交换方法实现。（三）概要设计：基数排序是一种对多关键字的排序，是先从最低位的关键字开始的进行排序，再将，然后在对高一位的进行排序，依次重复，直至到最高位即可，这样便成了一个有序序列。这个程序又有分三个模块：链式基数排序、顺序结构基数排序和主程序。（四）详细设计：基数排序就是在对数字排序时，先将数字低位对齐，再在每个相同位置对应的数字进行分配，如571第一轮先将它放在第一个的桶里，第二次分配时将他放在第七个捅里，这样只是分配，还需要按照将每个桶进行收集，这就是基数排序的基本思想。链式存储题目要求要顺序存储和链式存储两种结构来实现，链式存储采用静态链表，这样既节省空间，在时间上提高了效率。typedef struct int data; /数据，如571 datatype keysmax_num_of_key; /每个数据的所有关键字，571的5，7，1 int next; /next指什么？好纠结的问题 slcell; /静态链表的节点类型typedef struct sllist slcell *r; /静态链表的可利用空间，r0为头结点 int recnum; /静态链表的当前长度 int keynum; /当前数据的关键字个数sllist, * sllist; /静态链表类型typedef int arrtyperadix; /指针数组类型，声明两个指针数组，一个头指针，一个尾指针void creatlist(sllist &sll) /向程序中输入数字，根据这些数字确定关键字的长度和个数，同时创建一个静态链表void distribute(slcell *r, int i, arrtype front, arrtype end) /对静态链表记录第i个关键字进行分配 /静态链表l的r域中记录已按(keys0.keysi-1有序)。 /本算法按第i个关键字keysi建立radix个子表，使同一子表中记录的keysi相同。/front0.radix-1和end0.radix-1分别指向各子表中第一个和最后一个记录。void collect(slcell *r, int i, arrtype front, arrtype end)/本算法按keysi自小到大地将f0.radix-1所指各子表依次链接成为一个链表，收集各个子表，使静态链表有一定的顺序顺序存储结构： 和静态链表不同，用顺序存储的时候可以便于进行数据收集和查找，但没有链表那样移动记录时快捷。typedef struct int data; /数据，如571datatype keysmax_num_of_key; /每个数据的所有关键字，571的5，7，1 cell; typedef structcell band50;int size;row;/0-9的分组时的结构typedef struct cell *r; /可利用空间，r0为头结点 int recnum; /数组的当前长度 int keynum; /当前数据的关键字个数list, *list; /一系列的关键字存放的数组void creatlista(list &sll) /和链式基数排序一样需要进行创建一个存放所有输入信息的数组void arraydist(list &l ,int i,row *r) /将记录的第i个关键字进行比较，分配到向量r里面void arraycollect(list &l,int i,row *r) /将r的数据收集到数组l中 无论是顺序存储结构还是链式存储结构都需要判断关键字的最大长度和个数，我们可以根据输入的数字来确定关键字的长度和个数，可以先将输入的数字当作字符来处理其长度，再将这些字符转换为数字。 cout输入要进行排序的数据:str;/str是char*length=strlen(str);length=(lengthstrlen(str)?length:strlen(str);/求关键字最长值key=atoi(str);/将数字字符转换为数字（五）调试分析、测试结果:操作界面（以0作为数据输入结束的标志）在设计顺序存储结构时，可以按照链式基数排序的思想进行操作，在分配分组时，采用的结构体row会有一定的局限性，可以通过动态分配来实现。（六）附录:typedef struct int data; /数据，如571 datatype keysmax_num_of_key; /每个数据的所有关键字，571的5，7，1 int next; /next指什么？好纠结的问题 slcell; /静态链表的节点类型typedef struct sllist slcell *r; /静态链表的可利用空间，r0为头结点 int recnum; /静态链表的当前长度 int keynum; /当前数据的关键字个数sllist, * sllist; /静态链表类型typedef int arrtyperadix; /指针数组类型，声明两个指针数组，一个头指针，一个尾指针void creatlist(sllist &sll)/first creat a sllist when we input some nunbers int key, i=1,j,length;char str100; cout输入要进行排序的数据:str;length=strlen(str);/coutlengthri.data = key; for(j = 1; j keynum; j+)/将各位上的数据转化为数组中的元素 sll-ri.keysj = key % 10; key=key / 10; sll-ri-1.next=i+; cinstr;length=(lengthstrlen(str)?length:strlen(str);key=atoi(str); coutlengthkeynum=length; sll-recnum = i-1;/从一开始的 sll-rsll-recnum.next=0;/r0相当于头结点void print(sllist &sll) for(int p=sll-r0.next; p; p=sll-rp.next) coutrp.data ; coutendl;void distribute(slcell *r, int i, arrtype front, arrtype end) /静态链表l的r域中记录已按(keys0.keysi-1有序)。 /本算法按第i个关键字keysi建立radix个子表，使同一子表中记录的keysi相同。 /front0.radix-1和end0.radix-1分别指向各子表中第一个和最后一个记录。 for(int j=0; jradix; +j) frontj = 0; /各子表初始化为空表 for(int p=r0.next; p; p=rp.next) j=rp.keysi; /映射第i个关键字 if(!frontj) frontj = p; /若frontj为空，则把记录连接到frontj的头指针上 else rendj.next = p; /若frontj的头指针已经连接过了，说明已j为关键字的数据已经有了，/这时把上一个以j为关键字的数据指向当前的这个数，即下标为p的数据 endj = p; /尾指针重新指到每次更新的数据上 /distributevoid collect(slcell *r, int i, arrtype front, arrtype end) /本算法按keysi自小到大地将f0.radix-1所指各子表依次链接成为一个链表 for(int j=0; !frontj; j+); /找到第一个不为空的子表 r0.next=frontj; /重整静态链表 int k=endj; /k为当前子表的尾指针for(+j; jr=(slcell *)malloc(max_space*sizeof(slcell); sll-recnum=0; sll-keynum=10; creatlist(sll); cout排序前:endl; print(sll); arrtype front,end; for(int i = 1; i keynum; i+) /按lsd法对各关键字进行分配和收集 distribute(sll-r, i,front,end); /第i趟分配 collect(sll-r, i,front,end); /第i趟收集 /cout第i分配和收集:endl; cout排序后：v的路径。 首先引进一个辅助向量d，它的分量di表示当前找到的从始点v到终点vi的最短路径的长度。它的初态为：若从v到vi有弧则di为弧上的权值，否则di为，显然，长度为： dj=mindi|viv的路径就是从v出发的长度最小的路径，此路径为（v，vi）。 下一条最短路径（v，vk）的最短路径可能是直接两点间的，也可可能是（v，vj，vk）。 当然加入了点vk后可能使得v到其他点的路径变短这就还需要我们进行调整了。 综上所述，可以确定这个程序的伪码为：void shortestpath_dij(school sh,int v0,int pmax_scenic,int d) 初始化各个v0到各个顶点的路径，若和v0不相连则为，否则为其权值清空v0到各个顶点的路径for（）/当小于学校景点数,求v0到其他各个顶点的最短路径 当前所知离v0顶点最近距离的顶点vi 标记一下vi代表着已经被访问了 pi记录当前的结点的顺序 如果加入vi后，v0-vi-vj的距离小于v0-vj的距离，则调整v0到vj的距离,对未被访问的结点执行这个判断。其详细代码如下：void shortestpath_dij(school sh,int v0,int pmax_scenic,int d) /用迪杰斯特拉算法求有向网g的v