拆分與約瑟夫問題

1、程序設計基礎程序設計基礎B B 張立紅張立紅 1340533045913405330459（8802888028） 辦公室：辦公室：9-5019-501 第第10章章 鏈鏈 表表 主要內容主要內容 動態(tài)內存分配動態(tài)內存分配 鏈表的概念、操作以及基本應用。鏈表的概念、操作以及基本應用。 10.5.3 單鏈表的拆分單鏈表的拆分 單鏈表的拆分單鏈表的拆分是將一個單鏈表拆分成幾個是將一個單鏈表拆分成幾個 小的鏈表。小的鏈表。 單鏈表的拆分是一個建立多個子鏈表的過單鏈表的拆分是一個建立多個子鏈表的過 程，程，建子鏈表的過程可以根據(jù)題目的要求建子鏈表的過程可以根據(jù)題目的要求 選擇順序或逆序的方式，選擇順序

2、或逆序的方式，結點來源于原始結點來源于原始 大鏈表。大鏈表。 單鏈表的拆分過程：單鏈表的拆分過程： 1）為各個子鏈表為各個子鏈表分別建立各自只包含頭結點分別建立各自只包含頭結點的空鏈表。的空鏈表。 2）依次訪問原始鏈表中的每一個結點，根據(jù)結點的特征，確依次訪問原始鏈表中的每一個結點，根據(jù)結點的特征，確 定將該結點插入哪個子鏈表。定將該結點插入哪個子鏈表。 3）當原始鏈表訪問結束后，所有的結點也分別插入到的子鏈）當原始鏈表訪問結束后，所有的結點也分別插入到的子鏈 表上。表上。 -一一個單鏈表個單鏈表-拆分成了幾個子鏈表。拆分成了幾個子鏈表。 例例12：一個帶頭結點的單鏈表存放了一批整數(shù)值，一個帶

3、頭結點的單鏈表存放了一批整數(shù)值， 其中有負整數(shù)、其中有負整數(shù)、非非負整數(shù)。負整數(shù)。 要求：要求：將鏈表拆分成兩個子鏈表。將鏈表拆分成兩個子鏈表。 一個存放原鏈表中所有負數(shù)。一個存放原鏈表中所有負數(shù)。 一個存放原鏈表中所有一個存放原鏈表中所有非非負數(shù)。負數(shù)。 單鏈表的拆分過程：單鏈表的拆分過程： -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：一個帶頭結點的單鏈表存放了一批整數(shù)值，其中有負整：一個帶頭結點的單鏈表存放了一批整數(shù)值，其中有負整 數(shù)也有非負整數(shù)，要求將其拆分成兩個子鏈表，一個存放原鏈數(shù)也有非負整數(shù)，要求將其拆分成兩個子鏈表，一個存放原鏈 表中所有負數(shù)，另外一個存放原鏈表中所有非負數(shù)。表

7、中所有負數(shù)，另外一個存放原鏈表中所有非負數(shù)。-閱讀閱讀 #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個節(jié)點的鏈表個節(jié)點的鏈表 h2=split(h1); /h1鏈表拆分偉個鏈表鏈表拆分偉個鏈表h1、h2 p=h1-next; / 輸出正數(shù)鏈表輸出正數(shù)鏈表 while (p!=NULL) printf(%d ,p-data); p=p-next; printf(n); p=h2-next; / 輸出負數(shù)鏈表輸出負數(shù)鏈表 while (p!=NULL) printf(%d ,p-data); p=p-next; printf(n); return 0; 例例12 （續(xù)（續(xù)） head a2a1 a3

9、 anan-1 p 10.6.1 循環(huán)鏈表循環(huán)鏈表 一般單鏈表的最后一個結點的指針為一般單鏈表的最后一個結點的指針為NULL。 如果將單鏈表的最后一個結點又指向了第一個如果將單鏈表的最后一個結點又指向了第一個 結點結點-形成形成循環(huán)鏈表循環(huán)鏈表 注意：注意：在循環(huán)鏈表中，沒有在循環(huán)鏈表中，沒有空的頭結點空的頭結點。 10.6 循環(huán)鏈表與約瑟夫問題循環(huán)鏈表與約瑟夫問題 head a2a1 a3 anan-1 循環(huán)鏈表循環(huán)鏈表的操作與的操作與單單鏈表操作的鏈表操作的不同點：不同點： 1、建立一個循環(huán)鏈表時，必須使其建立一個循環(huán)鏈表時，必須使其最后一個結點的指針指最后一個結點的指針指 向表頭結點向表

10、頭結點-此情況還適用于在最后一個結點后插入此情況還適用于在最后一個結點后插入/刪刪 除一個結點。除一個結點。 2、循環(huán)鏈表判斷是否到表尾的條件：循環(huán)鏈表判斷是否到表尾的條件：判斷該結點判斷該結點指針域的指針域的 值值是否是表頭結點是否是表頭結點-當當指針域指針域值等于表頭指針時值等于表頭指針時-已到已到 表尾。表尾。 單鏈表判斷是否到表尾：單鏈表判斷是否到表尾：判斷判斷指針域值指針域值是否為是否為NULL。 10.6.2 約瑟夫問題約瑟夫問題-1197 約瑟夫問題的描述有多種方式，約瑟夫問題的描述有多種方式，“猴子選大王猴子選大王”是其是其 中典型的代表之一。中典型的代表之一。 問題描述：問題

11、描述： 1）n只猴子圍成一圈，順時針方向從只猴子圍成一圈，順時針方向從 1 到到 n 編號；編號； 2）從從1號開始沿順時針方向讓猴子從號開始沿順時針方向讓猴子從1、2、m 依次報數(shù)，凡報到依次報數(shù)，凡報到 m 的猴子，都讓其出圈，取消候的猴子，都讓其出圈，取消候 選資格；選資格； 3）再按順時針方向逐一讓報出再按順時針方向逐一讓報出 m 者出圈。者出圈。 結果：最后剩下一個就是猴王。結果：最后剩下一個就是猴王。 1# 2# 3# 4# 5# 6# 7# 8# 起始位置起始位置 例如：有例如：有n=8只猴子，只猴子， 數(shù)到數(shù)到 m=3 出圈。出圈。 出圈順序：出圈順序：3 615284 猴王猴

12、王 1、需要重復對猴子群體進行報數(shù)。需要重復對猴子群體進行報數(shù)。 2、在報數(shù)過程中要對滿足出圈條件的猴子進行出圈在報數(shù)過程中要對滿足出圈條件的猴子進行出圈 操作。操作。 3、用循環(huán)鏈表來進行模擬：用循環(huán)鏈表來進行模擬： 方便循環(huán)訪問。方便循環(huán)訪問。 容易實施出圈（即刪除）操作。容易實施出圈（即刪除）操作。 約瑟夫環(huán)問題約瑟夫環(huán)問題-分析分析 h 21 3 nn-1 1）結點數(shù)據(jù)域：）結點數(shù)據(jù)域：存放猴子在圈中的初始序號存放猴子在圈中的初始序號 。 結點指針域：結點指針域：指向下一個猴子指向下一個猴子-完成結點的鏈接。完成結點的鏈接。 結點定義如下：結點定義如下： struct monkey i

13、nt num; struct mon *next; ; 約瑟夫環(huán)問題約瑟夫環(huán)問題-分析分析 2）變量定義：）變量定義： 游動指針游動指針 p：對鏈表對鏈表從第一個結點從第一個結點開始逐個循環(huán)訪問時，開始逐個循環(huán)訪問時， p 指向當前正在被訪問的結點。指向當前正在被訪問的結點。 計數(shù)變量計數(shù)變量cn ：用于統(tǒng)計出圈的猴子數(shù)目用于統(tǒng)計出圈的猴子數(shù)目 -循環(huán)鏈表中被刪除的結點數(shù)目。循環(huán)鏈表中被刪除的結點數(shù)目。 跟隨指針跟隨指針q：q指向指向當前結點的當前結點的前驅結點前驅結點。 要刪除當前結點時，必須修改要刪除當前結點時，必須修改跟隨指針跟隨指針q 所指結點（即所指結點（即 被刪結點的前驅結點）的指

14、針域。被刪結點的前驅結點）的指針域。 報數(shù)變量報數(shù)變量 s ：對結點進行報數(shù)，如果報數(shù)對結點進行報數(shù)，如果報數(shù)s=m，則刪，則刪 除除游動指針游動指針 p 所指的結點所指的結點。 約瑟夫環(huán)問題約瑟夫環(huán)問題-分析分析 3）循環(huán)執(zhí)行的次數(shù)（即循環(huán)條件）循環(huán)執(zhí)行的次數(shù)（即循環(huán)條件）可以通過可以通過計數(shù)計數(shù)來控來控 制，也可以通過對循環(huán)鏈表本身的判定來實現(xiàn)：制，也可以通過對循環(huán)鏈表本身的判定來實現(xiàn)： 若若通過通過計數(shù)判斷計數(shù)判斷-判斷循環(huán)鏈表是否只剩一個結點：判斷循環(huán)鏈表是否只剩一個結點： 如果只剩一個結點，則已刪除如果只剩一個結點，則已刪除n-1個，剩余是猴王，個，剩余是猴王， 停止循環(huán)。停止循環(huán)。

15、 否則，表示還未找到猴王，需要繼續(xù)循環(huán)。否則，表示還未找到猴王，需要繼續(xù)循環(huán)。 約瑟夫環(huán)問題約瑟夫環(huán)問題-分析分析 1197-約瑟夫問題約瑟夫問題 #include /用循環(huán)鏈表完成約瑟夫問題用循環(huán)鏈表完成約瑟夫問題 #include struct monkey int num; struct monkey *next; struct monkey *creat(int n) / 循環(huán)鏈表創(chuàng)建循環(huán)鏈表創(chuàng)建順序建立無頭結點的鏈表順序建立無頭結點的鏈表 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; / 最后一個結點的指針域指向第一個結點形成循環(huán)鏈表最后一個結點的指針域指向第一個結點形成循環(huán)鏈表 return h; int sel(struct monkey *h,int n,int m) / n只猴子報數(shù)只猴子報數(shù)m出圈出圈-返回猴王序號返回猴王序號 int s=0; / 猴子報數(shù)的計數(shù)變

17、量猴子報數(shù)的計數(shù)變量 int cn=0; /統(tǒng)計出圈猴子的數(shù)目統(tǒng)計出圈猴子的數(shù)目 struct monkey *p,*q; / 分別指向當前結點及其前驅結點的指針分別指向當前結點及其前驅結點的指針 q=h; while(q-next!=h) q=q-next; / 前驅指針前驅指針 q 指向尾結點指向尾結點 while(cnnext;s+; if (s=m) / 找到一個被刪結點，完成刪除、計數(shù)找到一個被刪結點，完成刪除、計數(shù) q-next=p-next; cn+; free(p); s=0; else q=p; return q-num; / 最后一個結點的數(shù)據(jù)域即為留在最后一個結點的數(shù)據(jù)域

18、即為留在圈內的猴王序號圈內的猴王序號 int main() /1197-用循環(huán)鏈表完成約瑟夫問題用循環(huán)鏈表完成約瑟夫問題 int n,m; struct monkey *head; scanf(%d%d, head=creat(n); printf(%dn,sel(head,n,m); return 0; 如何通過鏈表本身判斷，圈內剩余一個猴王？如何通過鏈表本身判斷，圈內剩余一個猴王？ -當循環(huán)鏈表只剩一個結點，此時循環(huán)鏈表結當循環(huán)鏈表只剩一個結點，此時循環(huán)鏈表結 構如下圖所示：構如下圖所示： h i 基本特征是：基本特征是：q-next=q ; 此時：循環(huán)條件此時：循環(huán)條件while(cnn

19、ext!=q) 2056不敢死隊問題不敢死隊問題 #include /2056不敢死隊問題不敢死隊問題 #include struct person int num; struct person *next; struct person *creat(int m) /建立循環(huán)鏈表建立循環(huán)鏈表 int i; struct person *p,*tail,*head; p=(struct person *)malloc(sizeof(struct person); /建立循環(huán)鏈表的第一個結點建立循環(huán)鏈表的第一個結點 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; /形成循環(huán)鏈表形成循環(huán)鏈表 return head; void del(