算法与数据结构课程设计--线性表的操作及其应用

《算法与数据结构课程设计--线性表的操作及其应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、线性表的操作及其应用一、问题描述线性表、队列是一种常用的数据结构，有顺序和链式两种存储结构，在实际中应用十分广泛，而链表又分为单链表和循环链表，队列又分为链式队列和循环队列。这些数据结构都可用来解决约瑟夫环问题。约瑟夫环问题是算法设计中的一个经典问题，是顺序编号的一组n个人围坐一圈，从第1个人按一定方向顺序报数，在报到m时该人出列，然后按相同方法继续报数，直到所有人出列。设计算法求约瑟夫环中人员的出列顺序。二、基本要求1、选择合适的存储结构，建立线性表；2、利用顺序存储结构求解约瑟夫环问题；3、利用单链表和循环链表分别求解约瑟夫环问题；4、

2、利用队列求解约瑟夫环问题。三、测试数据约瑟夫环的测试数据为7，报数为1至3。四、算法思想由于用到四种不同的存储结构，它们的算法思想依次是：1、首先建立一个顺序表模拟整个约瑟夫环，手动输入顺序表长（即参加约瑟夫循环的人数）和循环的次数和表元素。用已经输出总人数和顺序表长作比较，作为外层循环条件。并对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查顺序表此次是不是我们设立的标记，如果不是则循环次数加1，当达到要求的循环次数时就将循环次数设置为0，输出该元素到屏幕并将总输出元素加1。每次外循环我们都会移到表的下一个位置，作为新的判断条件

3、，每次报到表尾的时候，我们都将重新设置到表尾，作为下次循环的表元素。2、首先采用链式循环链表建立整个约瑟夫环，手动输入第一次的循环次数和每个人所持下一个循环次数。设立判断指针指向表头，并将该指针是否为空作为外层循环条件。做一个内层循环，将判断指针移动到循环要输出的数，并设立一个前指针指向该指针的前一个位置，输出该元素后，将循环次数重新赋值成该元素。接着判断前指针和判断指针比较，如果相等说明整个表已经输出完毕，否则将删除该位置的元素。3、用链式队列建立循环约瑟夫环，手动输入人数，第一次的循环次数和每个人所持下一个循环次数。并将每一个元素依次入

4、队列，根据第一次循环次数，建立一个for循环，每一次循环都出队列，如果达到要求的循环次数就输出，否则进队列，这样这个数字就出现在队尾。第一个数输出后，以队列的非空作为循环条件，判断方式如上。4、wilyes11收集博客(与学习无关)：http://blog.sina.com.cn/u/1810231802用循环队列建立约瑟夫环，将1-7个元素依次进入循环队列，以队列的长度作为与已输出的元素作为判断条件，对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查该该位置的元素是不是我们设立的标记-1，如果不是则循环次数加1，将队首指针移到队

5、列的下一个元素，结束此次循环，当达到要求的循环次数时就将重新循环次数设置为0，输出该元素到屏幕并将总输出元素加1。五、模块划分1、voidInitQueue(SqQueue*Q)初始化循环队列2、voidDestroyQueue(SqQueue*Q)销毁循环队列3、voidClearQueue(SqQueue*Q)清空循环队列4、intQueueEmpty(SqQueueQ)判断空队列5、intQueueLength(SqQueueQ)求循环队列长度6、voidGetHead(SqQueueQ,ElemType*e)取队头元素7、intEn

6、Queue(SqQueue*Q,ElemTypee)入队列8、intDeQueue(SqQueue*Q,ElemType*e)出队列9、voidQueueTraverse(SqQueueQ)遍历循环队列并输出元素10、voidInitQueue(LQueue*Q)初始化队列11、voidDestroyQueue(LQueue*Q)销毁队列12、voidClearQueue(LQueue*Q)清空队列13、intQueueEmpty(LQueueQ)判断空队列14、intQueueLength(LQueueQ)求队列长度15、ElemType

7、GetHead(LQueueQ,ElemType*e)取队头元素16、voidEnQueue(LQueue*Q,ElemTypee)入队列17、voidDeQueue(LQueue*Q,ElemType*e)出队列18、voidQueueTraverse(LQueueQ)遍历队列并输出元素19、voidjoseffer(intn)约瑟夫环20、intCreateList(LinkList&L,intn)建立顺序链表wilyes11收集博客(与学习无关)：http://blog.sina.com.cn/u/181023180221、voidj

8、osephus_clist(LinkList&L,intm)顺序链表解决约瑟夫环22、voidInitList(SqList*L)初始化链表23、voidysf1()链表解决约瑟