数据结构 课程设计.doc

福建农林大学计算机与信息学院计算机类课程设计报告课程名称：算法与数据结构课程设计题目：约瑟夫环顺序表的实现姓 名：张三系：计算机科学与技术专 业：计算机科学与技术年 级：2009级学 号：091150001指导教师：宁正元职 称：教授2011年 8月20日福建农林大学计算机与信息学院计算机类课程设计结果评定评语：成绩：指导教师签字：任务下达日期：评定日期：目录1、课程设计目的12、课程设计要求13、课程设计方案14、课程设计内容24.1问题描述24.2系统运行环境24.3算法思想24.4算法实现24.5逻辑设计34.6详细设计（源程序）54.7程序调试与测试结果74.8调试分析95、总结10参考文献11约瑟夫环顺序表的实现1、课程设计目的 熟悉掌握线型表的基本操作在顺序表的实现的，其中以操作和应用作为重点。 利用顺序存储结构模拟此过程，按照出列的顺序输出各个数的编号。 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。 提高综合运用所学的理论知识和方法以及独立分析和解决问题的能力。2、课程设计要求 本程序中，初始密码和每个人的密码为19999，人数为130，先输入初始密码m，再输入人数n，接下来输入n个正整数，数与数之间用逗号隔开，作为这n个人的密码。 程序只需做出处理一个案例，即程序给出一个约瑟夫环的答案之后即可推出，如果用户有第二个案例，需再运行本程序。 程序应该以模拟约瑟夫环运行情况的方式求解，即不得采用公式计算等其他数学方式求解。3、课程设计方案本程序包含三个基本模块 主程序模块：其中又包括建立线性表和模拟约瑟夫环处理两大过程 线性表模块：实现线性表的抽象数据类型 元素结构单元模块：定义线性表每个元素的结构运用顺序表的数据结构，通过顺序表模拟围坐的一圈人，然后根据相应的密码进行报数，然后删除相应的节点。由键盘输入总人数，再依次输入每个人和密码建立人员表，再输入开始报数人的位置及初始报数上限，按照出列顺序输出每个人。4、课程设计内容4.1问题描述编号为1，2 n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从某一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。 4.2系统运行环境 操作系统：Windows XP 运行软件：VC+ 6.04.3算法思想算法思想是：从l至m对带头结点的线性表计数，到m时，输出该结点的编号值，将该结点的密码作为新的m值，再从该结点的下一个结点起重新自1起循环计数。如此下去，直到线性表空时过程结束。4.4算法实现 Status InitList(SqList &L) /初始化顺序表L Status ListInsert(SqList &L,int i,ElemType e) /在顺序表中第i个位置之前插入新的数据元素e Status ListDelete(SqList &L,int i,ElemType &e)/在顺序表中删除第i个元素，并用e返回其值（1）构造空的线性表（2）在空的线性表中插入元素（3）删除线性表中报m数算法具体步骤如下：输入-initList(L)-current=(current-1)+m)%ListLength(L)-断current=0若是：执行current=ListLength(L);S=ListDelete(L,current,e返回current=0再判断若否：执行“返回”4.5逻辑设计1、定义结构体定义一个结构体，里边定义两个元素：人的编号及其密码。Typedef struct nodeintnumber;/节点编号intpwd;/节点密码 ElemType;/节点类型typedef struct intlength;/顺序表当前长度intlistsize;/顺序表当前分配的存储容量ElemType*elem;/顺序表存储空间基地址SqList;/顺序表类型Status InitList(SqList &L)/初始化顺序表L L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem) return ERROR; L.length=0;/空表长度为0 L.listsize=LIST_INIT_SIZE;/初始存储容量 return OK;2、约瑟夫环输出Status ListInsert(SqList &L,int i,ElemType e)/在顺序表中第i个位置之前插入新的数据元素e ElemType *base,*q,*p; if(iL.length) return ERROR;/ i值不合法 if(L.length=L.listsize) if(!(base=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType) return ERROR;/存储分配失败 L.elem=base; /新基地址 L.listsize+=LISTINCREMENT; /增加存储容量 q=L.elem+i; /q为插入位置 for(p=L.elem+L.length;p=q;-p) /插入位置及之后的元素右移 *(p+1)=*p; *q=e; /插入e L.length+; /表长加1 return OK;Status ListDelete(SqList &L,int i,ElemType &e)/在顺序表中删除第i个元素，并用e返回其值 ElemType *p,*q; if(iL.length-1)return ERROR; / i值不合法 p=L.elem+i; / p为被删除元素的位置 e=*p; /被删除元素的值赋给e q=L.elem+L.length-1; / q为表尾元素的位置 for(+p;p=q;+p) /被删除元素之后的元素左移 *(p-1)=*p; L.length-; /表长减1 return OK;3、主函数在主程序中定义一个该结构体类型的线性表，来存储n个人的编号及其对应的密码。用户从键盘输入信息，包括输入人数n，初始m值，及n个人的密码。为了使程序更加规范，设定人数不多于30人，且其对应的密码必须为正整数。这样就需要在读取用户输入时进行判断，在输入数据错误应当有出错提示，然后退出。void main()ElemType temp;int i,num,m,k,p=0;SqList J;InitList(J);/初始化顺序表Jprintf(输入玩家人数:);/输入玩家人数scanf(%d,&num);printf(输入第1次的报数上限值m:);/输入第1次的报数上限值mscanf(%d,&m);for(i=0;i0)/循环至所有玩家出列 p-;/将指针p位置设置为当前报数位置之前for(i=0;im;i+)/报数m次找到出队玩家p=(p+1)%J.length;ListDelete(J,p,temp);/删除出队玩家的节点m=temp.pwd;/获取新的m值printf(输出出队玩家的编号%dn,temp.number);/输出出队玩家的编号/whileprintf(所有玩家出队结束n);/所有玩家出队结束4.6详细设计（源程序）#include#include #define ERROR 0/运行错误返回值#define OK 1/运行成功返回值#define LIST_INIT_SIZE 50/顺序表初始大小#define LISTINCREMENT 10/顺序表每次增加大小typedef int Status;/运行状态类型typedef struct intnumber;/节点编号intpwd;/节点密码 ElemType;/节点类型typedef struct intlength;/顺序表当前长度intlistsize;/顺序表当前分配的存储容量ElemType*elem;/顺序表存储空间基地址SqList;/顺序表类型Status InitList(SqList &L)/初始化顺序表L L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem) return ERROR; L.length=0;/空表长度为0 L.listsize=LIST_INIT_SIZE;/初始存储容量 return OK;Status ListInsert(SqList &L,int i,ElemType e)/在顺序表中第i个位置之前插入新的数据元素e ElemType *base,*q,*p; if(iL.length) return ERROR;/ i值不合法 if(L.length=L.listsize) if(!(base=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType) return ERROR;/存储分配失败 L.elem=base; /新基地址 L.listsize+=LISTINCREMENT; /增加存储容量 q=L.elem+i; /q为插入位置 for(p=L.elem+L.length;p=q;-p) /插入位置及之后的元素右移 *(p+1)=*p; *q=e; /插入e L.length+; /表长加1 return OK;Status ListDelete(SqList &L,int i,ElemType &e)/在顺序表中删除第i个元素，并用e返回其值 ElemType *p,*q; if(iL.length-1)return ERROR; / i值不合法 p=L.elem+i; / p为被删除元素的位置 e=*p; /被删除元素的值赋给e q=L.elem+L.length-1; / q为表尾元素的位置 for(+p;p=q;+p) /被删除元素之后的元素左移 *(p-1)=*p; L.length-; /表长减1 return OK;void main()ElemType temp;int i,num,m,k,p=0;SqList J;InitList(J);/初始化顺序表Jprintf(输入玩家人数:);/输入玩家人数scanf(%d,&num);printf(输入第1次的报数上限值m:);/输入第1次的报数上限值mscanf(%d,&m);for(i=0;i0)/循环至所有玩家出列 p-;/将指针p位置设置为当前报数位置之前for(i=0;im;i+)/报数m次找到出队玩家p=(p+1)%J.length;ListDelete(J,p,temp);/删除出队玩家的节点m=temp.pwd;/获取新的m值printf(输出出队玩家的编号%dn,temp.number);/输出出队玩家的编号/whileprintf(所有玩家出队结束n);/所有玩家出队结束4.7程序调试与测试结果1、输入玩家人数2、输入第1次的报数上限值3、分别输入各玩家的密码4、输出的结果4.8调试分析 1、当输入玩家人数为0时，会出现错误，所以再重新设计时加入了对空节点的处理。 在线性表节点的设计上，最初是仅包含密码和指针，但是后来考虑到链表节点删除时会带来一系列的编号变化，编号难以确定，所以节点设计上又加了一个编号。 在线性表的赋值操作时，原本是以一个不变的L作为头结点，但是这种赋值方法带来了诸多变量设计的问题，所以将L为节点，赋值完成后，再让L指向头结点。 程序原本是没有求节点个数的函数，但是在约瑟夫环的实现函数中，节点的个数时时影响着结果的判断，所以加入了该函数。 考虑到时间问题，密码采用对剩余节点取余来减少遍历次数。 程序大体完成时，却又在调试过程中发现出列次序总是错误的，才想到第一次指向时应该让变化的指针指向尾节点，这样可以减少当密码为1时程序的设计量。5、总结 在这次数据结构的课程设计中，让我进一步地了解顺序表的用法，也更清楚地明白关于约瑟夫环的一些内容。在设计过程中，重点的问题有两个，一个是约瑟夫环该怎么样去实现，还有就是每个人的秘密应该如何输入。起初，密码的输入是设计在主函数中去解决，最后在查阅资料和动手实践之后，决定将密码的输入放在顺序表的初始化过程中，这样的话，能够更条理清晰。 通过一周的课程设计之后，培养了我选用参考书，查阅手册及文献资料的能力，培养独立思考，深入研究，分析问题、解决问题的能力，提高综合运用本课程所学知识的能力，还对设计的基本过程的设计方法、步骤、思路、有一定的了解与认识，并对存储结构，比如线性表、链表、循环链表、树、图等存储结构，特别是对线性表理解的更深。也使我认识到数据结构这门课程是计算机程序设计的重要理论技术基础，在我们计算机专业的学习中占据着十分重要的地位。同时也使我知道，要学好这门课程，仅学习书本上的知识是不够的，还要有较强的实践能力。因为我们学习知识就是为了实践。而只有多实践，多编写程序，才能更好的理解与掌握书本上的东西。我学到了很多的东西，通过实际