拆分与约瑟夫问题

1、程序设计基础程序设计基础B B 张立红张立红 1340533045913405330459（8802888028） 办公室：办公室：9-5019-501 第第10章章 链链 表表 主要内容主要内容 动态内存分配动态内存分配 链表的概念、操作以及基本应用。链表的概念、操作以及基本应用。 10.5.3 单链表的拆分单链表的拆分 单链表的拆分单链表的拆分是将一个单链表拆分成几个是将一个单链表拆分成几个 小的链表。小的链表。 单链表的拆分是一个建立多个子链表的过单链表的拆分是一个建立多个子链表的过 程，程，建子链表的过程可以根据题目的要求建子链表的过程可以根据题目的要求 选择顺序或逆序的方式，选择顺序

2、或逆序的方式，结点来源于原始结点来源于原始 大链表。大链表。 单链表的拆分过程：单链表的拆分过程： 1）为各个子链表为各个子链表分别建立各自只包含头结点分别建立各自只包含头结点的空链表。的空链表。 2）依次访问原始链表中的每一个结点，根据结点的特征，确依次访问原始链表中的每一个结点，根据结点的特征，确 定将该结点插入哪个子链表。定将该结点插入哪个子链表。 3）当原始链表访问结束后，所有的结点也分别插入到的子链）当原始链表访问结束后，所有的结点也分别插入到的子链 表上。表上。 -一一个单链表个单链表-拆分成了几个子链表。拆分成了几个子链表。 例例12：一个带头结点的单链表存放了一批整数值，一个带

3、头结点的单链表存放了一批整数值， 其中有负整数、其中有负整数、非非负整数。负整数。 要求：要求：将链表拆分成两个子链表。将链表拆分成两个子链表。 一个存放原链表中所有负数。一个存放原链表中所有负数。 一个存放原链表中所有一个存放原链表中所有非非负数。负数。 单链表的拆分过程：单链表的拆分过程： -5109-712 head1 -8 head2=(struct node *) malloc (sizeof(struct node); head2-next=NULL; p=head1-next; head1-next=NULL; q=p-next; head2 p q 单链表的拆分过程：单链表的拆

4、分过程： -5109-712 head1 -8 if (p-data=0) p-next=head1-next; head1-next=p; head2 p q p=q; if (q!=NULL) q=q-next; if (p-data=0) 单链表的拆分过程：单链表的拆分过程： -5109-712 head1 -8 if(p-data=0) p-next=head1-next; head1-next=p; else p-next=head2-next; head2-next=p; head2 pq p=q; if (q!=NULL) q=q-next; 单链表的拆分过程：单链表的拆分过程：

5、 -5109-712 head1 -8 if(p-data=0) p-next=head1-next;head1-next=p; else p-next=head2-next; head2-next=p; head2 p q struct node *split(struct node *head1) /链表拆分链表拆分 struct node * head2,* p,* q; head2=(struct node *) malloc (sizeof(struct node); head2-next=NULL;p=head1-next; head1-next=NULL;q=p-next; wh

6、ile(p!=NULL) if (p-data=0) p-next=head1-next; head1-next=p; else p-next=head2-next; head2-next=p; p=q; if (q!=NULL) q=q-next; return (head2); /返回一个新链表的头指针返回一个新链表的头指针 例例12：一个带头结点的单链表存放了一批整数值，其中有负整：一个带头结点的单链表存放了一批整数值，其中有负整 数也有非负整数，要求将其拆分成两个子链表，一个存放原链数也有非负整数，要求将其拆分成两个子链表，一个存放原链 表中所有负数，另外一个存放原链表中所有非负数。表

7、中所有负数，另外一个存放原链表中所有非负数。-阅读阅读 #include #include struct node int data; struct node *next; ; struct node * create(int n) / 顺序建链表顺序建链表 struct node * h,* tail,* p; int i; h=(struct node *)malloc(sizeof(struct node); h-next=NULL; tail=h; for(i=1;idata); p-next=NULL; tail-next=p; tail=p; return (h); int mai

8、n() struct node *h1,*h2,*p; h1=create(10);/建立建立10个节点的链表个节点的链表 h2=split(h1); /h1链表拆分伟个链表链表拆分伟个链表h1、h2 p=h1-next; / 输出正数链表输出正数链表 while (p!=NULL) printf(%d ,p-data); p=p-next; printf(n); p=h2-next; / 输出负数链表输出负数链表 while (p!=NULL) printf(%d ,p-data); p=p-next; printf(n); return 0; 例例12 （续（续） head a2a1 a3

9、 anan-1 p 10.6.1 循环链表循环链表 一般单链表的最后一个结点的指针为一般单链表的最后一个结点的指针为NULL。 如果将单链表的最后一个结点又指向了第一个如果将单链表的最后一个结点又指向了第一个 结点结点-形成形成循环链表循环链表 注意：注意：在循环链表中，没有在循环链表中，没有空的头结点空的头结点。 10.6 循环链表与约瑟夫问题循环链表与约瑟夫问题 head a2a1 a3 anan-1 循环链表循环链表的操作与的操作与单单链表操作的链表操作的不同点：不同点： 1、建立一个循环链表时，必须使其建立一个循环链表时，必须使其最后一个结点的指针指最后一个结点的指针指 向表头结点向表

10、头结点-此情况还适用于在最后一个结点后插入此情况还适用于在最后一个结点后插入/删删 除一个结点。除一个结点。 2、循环链表判断是否到表尾的条件：循环链表判断是否到表尾的条件：判断该结点判断该结点指针域的指针域的 值值是否是表头结点是否是表头结点-当当指针域指针域值等于表头指针时值等于表头指针时-已到已到 表尾。表尾。 单链表判断是否到表尾：单链表判断是否到表尾：判断判断指针域值指针域值是否为是否为NULL。 10.6.2 约瑟夫问题约瑟夫问题-1197 约瑟夫问题的描述有多种方式，约瑟夫问题的描述有多种方式，“猴子选大王猴子选大王”是其是其 中典型的代表之一。中典型的代表之一。 问题描述：问题

11、描述： 1）n只猴子围成一圈，顺时针方向从只猴子围成一圈，顺时针方向从 1 到到 n 编号；编号； 2）从从1号开始沿顺时针方向让猴子从号开始沿顺时针方向让猴子从1、2、m 依次报数，凡报到依次报数，凡报到 m 的猴子，都让其出圈，取消候的猴子，都让其出圈，取消候 选资格；选资格； 3）再按顺时针方向逐一让报出再按顺时针方向逐一让报出 m 者出圈。者出圈。 结果：最后剩下一个就是猴王。结果：最后剩下一个就是猴王。 1# 2# 3# 4# 5# 6# 7# 8# 起始位置起始位置 例如：有例如：有n=8只猴子，只猴子， 数到数到 m=3 出圈。出圈。 出圈顺序：出圈顺序：3 615284 猴王猴

12、王 1、需要重复对猴子群体进行报数。需要重复对猴子群体进行报数。 2、在报数过程中要对满足出圈条件的猴子进行出圈在报数过程中要对满足出圈条件的猴子进行出圈 操作。操作。 3、用循环链表来进行模拟：用循环链表来进行模拟： 方便循环访问。方便循环访问。 容易实施出圈（即删除）操作。容易实施出圈（即删除）操作。 约瑟夫环问题约瑟夫环问题-分析分析 h 21 3 nn-1 1）结点数据域：）结点数据域：存放猴子在圈中的初始序号存放猴子在圈中的初始序号 。 结点指针域：结点指针域：指向下一个猴子指向下一个猴子-完成结点的链接。完成结点的链接。 结点定义如下：结点定义如下： struct monkey i

13、nt num; struct mon *next; ; 约瑟夫环问题约瑟夫环问题-分析分析 2）变量定义：）变量定义： 游动指针游动指针 p：对链表对链表从第一个结点从第一个结点开始逐个循环访问时，开始逐个循环访问时， p 指向当前正在被访问的结点。指向当前正在被访问的结点。 计数变量计数变量cn ：用于统计出圈的猴子数目用于统计出圈的猴子数目 -循环链表中被删除的结点数目。循环链表中被删除的结点数目。 跟随指针跟随指针q：q指向指向当前结点的当前结点的前驱结点前驱结点。 要删除当前结点时，必须修改要删除当前结点时，必须修改跟随指针跟随指针q 所指结点（即所指结点（即 被删结点的前驱结点）的指

14、针域。被删结点的前驱结点）的指针域。 报数变量报数变量 s ：对结点进行报数，如果报数对结点进行报数，如果报数s=m，则删，则删 除除游动指针游动指针 p 所指的结点所指的结点。 约瑟夫环问题约瑟夫环问题-分析分析 3）循环执行的次数（即循环条件）循环执行的次数（即循环条件）可以通过可以通过计数计数来控来控 制，也可以通过对循环链表本身的判定来实现：制，也可以通过对循环链表本身的判定来实现： 若若通过通过计数判断计数判断-判断循环链表是否只剩一个结点：判断循环链表是否只剩一个结点： 如果只剩一个结点，则已删除如果只剩一个结点，则已删除n-1个，剩余是猴王，个，剩余是猴王， 停止循环。停止循环。

15、 否则，表示还未找到猴王，需要继续循环。否则，表示还未找到猴王，需要继续循环。 约瑟夫环问题约瑟夫环问题-分析分析 1197-约瑟夫问题约瑟夫问题 #include /用循环链表完成约瑟夫问题用循环链表完成约瑟夫问题 #include struct monkey int num; struct monkey *next; struct monkey *creat(int n) / 循环链表创建循环链表创建顺序建立无头结点的链表顺序建立无头结点的链表 int i; struct monkey *p,*tail,*h; p=(struct monkey *)malloc(sizeof(struct

16、 monkey); p-num=1; p-next=NULL; / 第一个结点的生成第一个结点的生成 h=p; tail=p; /h、tail-均指向第一个结点均指向第一个结点 for(i=2;inum=i; p-next=NULL; tail-next=p; tail=p; tail-next=h; / 最后一个结点的指针域指向第一个结点形成循环链表最后一个结点的指针域指向第一个结点形成循环链表 return h; int sel(struct monkey *h,int n,int m) / n只猴子报数只猴子报数m出圈出圈-返回猴王序号返回猴王序号 int s=0; / 猴子报数的计数变

17、量猴子报数的计数变量 int cn=0; /统计出圈猴子的数目统计出圈猴子的数目 struct monkey *p,*q; / 分别指向当前结点及其前驱结点的指针分别指向当前结点及其前驱结点的指针 q=h; while(q-next!=h) q=q-next; / 前驱指针前驱指针 q 指向尾结点指向尾结点 while(cnnext;s+; if (s=m) / 找到一个被删结点，完成删除、计数找到一个被删结点，完成删除、计数 q-next=p-next; cn+; free(p); s=0; else q=p; return q-num; / 最后一个结点的数据域即为留在最后一个结点的数据域

18、即为留在圈内的猴王序号圈内的猴王序号 int main() /1197-用循环链表完成约瑟夫问题用循环链表完成约瑟夫问题 int n,m; struct monkey *head; scanf(%d%d, head=creat(n); printf(%dn,sel(head,n,m); return 0; 如何通过链表本身判断，圈内剩余一个猴王？如何通过链表本身判断，圈内剩余一个猴王？ -当循环链表只剩一个结点，此时循环链表结当循环链表只剩一个结点，此时循环链表结 构如下图所示：构如下图所示： h i 基本特征是：基本特征是：q-next=q ; 此时：循环条件此时：循环条件while(cnn

19、ext!=q) 2056不敢死队问题不敢死队问题 #include /2056不敢死队问题不敢死队问题 #include struct person int num; struct person *next; struct person *creat(int m) /建立循环链表建立循环链表 int i; struct person *p,*tail,*head; p=(struct person *)malloc(sizeof(struct person); /建立循环链表的第一个结点建立循环链表的第一个结点 p-num=1; p-next=NULL; /第第1个结点是排长个结点是排长 head=p; tail=p; for(i=2;inum=i; tail-next=p; tail=p; p-next=NULL; tail-next=head; /形成循环链表形成循环链表 return head; void del(