敢死队问题说明书.doc

目 录 摘要 1 前言 2 正文 3 1．采用类c语言定义相关的数据类型 3 2.各模块的伪码算法 4 3.函数的关系调用图 8 4.调试分析 13 5.测试结果 14 6.源代码(带注释) 16 总结 23 参考文献 24 致谢 25 附件I部分源代码: 26 摘要 敢死队问题是二战时期攻城方为了突破桥对面敌人的碉堡而产生的一类问题，它和我们所说的约瑟夫换问题有一定的联系，或者应该说是有点儿类似，从根本上讲就是从围成一圈的人（数字），按照一定的规则由某一个数开始，以一定的基数为一个密码，顺序性的取出密码的终结者，而后以终结者以后的第一人（数字）并且以当前刚刚跳出的终结者所给与的密码为基数，再一次开始顺序性取出。。。。。 关键字：单循环链表，循环队列，线性表,C语言。 前言 数据结构是研究数据元素之间的逻辑关系的一门课程，以及数据元素及其关系在计算机中的存储表示和对这些数据所施加的运算。该课程设计的目的是通过课程设计的综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课程的主要内容。 本次课程设计的内容是敢死队问题，循环链表是一种首尾相接链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活。队列是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出的特性。而敢死队问题就是对子类问题的先进性的应用，通过这个设计事例，我们有理由相信至此以后，我们对循环链表和循环队列的理解将会是更上一层楼。 通过该课程设计，能运用所学知识，能上机解决一些实际问题，了解并初步掌握设计、实现较大程序的完整过程，包括系统分析、编码设计、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。 正文 1．采用类c语言定义相关的数据类型 a.循环单链表存储结构 typedef struct node { int data; struct node *next; }LNode;/* 定义结点类型 */ b.线性表存储结构 #define LIST_INIT_SIZE 100 #define LISTINCCREMENT 10 #define OK 1 #define ERROR 0 typedef int ElemType; typedef struct KList /*定义数据结构体类型*/ { ElemType *elem; /*存储空间基址*/ int length; /*当前长度*/ int listsize; /*当前分配的存储容量(以sizeof(ElemType)为单位)*/ }SqList; c.循环队列存储结构 #define QueueSize 1000 //假定预分配的队列空间最多为1000个元素 typedef struct{ int data[QueueSize]; int front; int rear; int count; //计数器，记录队中元素总数 }CirQueue; 2.各模块的伪码算法 创建循环链表: LNode* CREAT(int n) /* 创建循环链表 */ { LNode *s,*q,*T; int i; if(n!=0) { T=q=(LNode *)malloc(sizeof(LNode)); q-data=1;/* 生成第一个结点并使其data值为1 */ for(i=2;i=n;i++) { s=(LNode *)malloc(sizeof(LNode)); q-next=s; q-next-data=i;/*赋值*/ q=q-next; } q-next=T; } return T; } 链表的删除: DELETE (LNode* T,int m)/* 链表的删除 */ { LNode *a;int i; while (T-next!=T) { for (i=1;im-1;i++)/*查找要删除结点的前一结点*/ T=T-next; a=T-next; T-next=a-next; free(a); T=T-next; } printf(\n); return (T-data); } 创建线性表: int InitList_Sq( SqLis