c语言课件lec.ppt

Thank you!Q A * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Example : Joseph problem (约瑟夫问题). 这是十七世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个基督教徒和15个异教徒在海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一个圆圈，从第一个人开始依次报数，每数到第 9 个人就将他扔入大海，如此循环进行直到仅余 15 人为止。问怎样排法，才能使每次投入大海的都是异教徒。 * 题目中30个人围成一圈，因而启发我们用一个循环的链来表示。可以使用结构数组来构成一个循环链。 结构中有两个成员：其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。 从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。 * Example : Joseph problem (约瑟夫问题)(cont.) * 1 2 29 30 ….. Header pointer Head node 用链表的方法对约瑟夫问题进行编程 算法分析与设计 首先定义链表数据结构 struct node { int no; struct node * next; }; 期望建立的原始链表形式 main( ) { int i, k; struct node *head, *p, *q; head = (struct node *)malloc(sizeof(struct node)); head-no = -1; head-next = head; -1 1 2 29 30 ... head 表头 数据结点 数据结点 数据结点 数据结点 -1 head 表头 for ( i=30; i0; i-- ) { p = (struct node *)malloc(sizeof(struct node)); p-no = i; p-next = head-next; head-next = p; } 30 p x p 29 p while ( p-next != head ) // 遇到表头结点终止循环 p = p-next; -1 1 2 29 30 ... head 表头 数据结点 数据结点 数据结点 数据结点 -1 1 2 29 30 ... head 表头 数据结点 数据结点 数据结点 数据结点 p p-next = head-next; // p的指向要跳过表头节点 -1 1 2 29 30 ... head 表头 数据结点 数据结点 数据结点 数据结点 p p for ( i=0; i15; i++ ) // 15人出列 { for ( k=1 ; k9 ; k++ ) // 报数到 9 为止 p = p-next; q = p-next; // p的下一个结点出列 p-next = q-next; // 跳过要出列的结点 printf(%3d, q-no); // q 结点的编号 free(q); // 释放 q 结点 } -1 1 2 29 30 ... head 表头 数据结点 数据结点 数据结点 数据结点 p main( ) { int i, k; struct node *head, *p, *q; head = (struct node *)malloc(sizeof(struct node)); head-no = -1; head-next = head; for ( i=30; i0; i-- ) /* 生成循环链表 */ { p = (struct node *)malloc(sizeof(struct node)); p-next = head-next; p-no = i; head-next = p; } printf(\nThe original circle is :); while ( p-next != head ) /* 循环链跳过表头结点 */ p = p-next; p-next = head-next; /* p 指向 30 */ for ( i=0; i15; i++ ) { for ( k