《数据结构（C语言版） 》课程设计

《《数据结构（C语言版） 》课程设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、课程设计说明书设计题目：数据结构课程设计专业：信息与计算科学班级：2010级2班设计人：１００１０５１６２３山东科技大学2013年1月1日第31页课程设计任务书学院：信息学院专业：信息班级10-2姓名：一、课程设计题目：数据结构课程设计二、课程设计主要参考资料：（1）《数据结构（C语言版）》（2）网上查询三、课程设计应解决的主要问题：（1）约瑟夫环问题（2前缀算术表达式转换及表达式计算（3）矩阵乘法和加法算法的应用（4）有向无环图每个顶点出发的最短路径及其长度（5）2-路归并排序四、课程设计相关附

2、件（如图纸、软件等）：五、任务发出日期：课程设计完成日期：指导教师签字：系主任签字：第31页指导教师对课程设计的评语指导教师签字：年月日第31页设计1约瑟夫环问题一、需求分析（1）实现单循环链表的初始化。（2）理解约瑟夫环的定义，用循环找到每次报数人的序号和密码。（3）从单循环链表中删除节点，并判断链表空与非空的临界条件。问题描述设编号为1，2…，n(n>0)个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出一个报数上限值m，从第一人开始顺时针方向自1起顺序报数，报到m时停止报数，报

3、m的人出列，将他的密码作为新的m值，从他在顺指针方向上的下一个人起重新自1起顺序报数；下去，直到所有人全部出列为止。要求设计一个程序模拟此过程。二、总体设计及模块的划分主模块：Voidmain()接受命令；处理命令；模块一：定义单向循环链表的节点结构模块二：LinkListinit_clist()构造单向循环链表模块三：intCourse()模拟删除过程第31页三、详细设计（1）流程图：（2）主模块实现算法基本思想：在保证m大于0的前提下，从第一个结点开始，根据m找到循环链表第m个结点，读取下一个

4、出列人的序号，并读出第m个结点的密码作为新的报数上限，从此结点的下一个结点开始进行新的查找。通过指针依次删除出列人相应的节点，直到该链表中无节点，退出循环。（3）时间复杂度：O（n*m）第31页四、运行结果及分析（1）测试用例：（一般数据）（2）测试用例：（边界数据）当m=1，序号为1的人首先出列，模拟过程正确，出列手持密码为1，相邻的人出列，模拟过程正确。（3）测试用例：（错误数据）当输入初始密码m<1，给出重新输入提示。第31页五.附源程序#include#include

5、tdlib.h>#include#defineFALSE0#defineTRUE1typedefstructNode{intnum;//序号intcode;//密码structNode*next;}Node,*LinkList;LinkListinit_clist(LinkListL,intn){LinkListq,p;inti;q=(LinkList)malloc(sizeof(Node));L=q;q->num=1;//无头结点printf("TheNO1People'sc

6、odeis:");scanf("%d",&q->code);q->next=q;for(i=2;i<=n;i++){p=(LinkList)malloc(sizeof(Node));p->num=i;printf("TheNO%dPeople'scodeis:",i);scanf("%d",&p->code);p->next=q->next;q->next=p;q=p;}returnL;}intCourse(LinkListL,intn,intm){LinkListr,p,q,f;inti;whi

7、le(n>=1){if(m==1){q=L;f=L;1while(q->next!=L){q=q->next;}printf("%d",L->num);m=L->code;L=L->next;q->next=L;free(f);}else{p=L;for(i=1;inext;}printf("%d",p->num);m=p->code;r->next=p->next;L=p->next;free(p);}n--;}return0;}intmain(){intn,m

8、;//n为总人数LinkListL;printf("Pleaseinputthenumberofpeople:(n>0)");scanf("%d",&n);L=init_clist(L,n);printf("Pleaseinputthenumbermis:");scanf("%d",&m);if(!m){printf("Pleaseinputtherightnumberm(m>0)is:");scanf("%d",&m);printf("Thedequeueorderare: