拆分與約瑟夫問題

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

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

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

7、中所有負(fù)數(shù)，另外一個存放原鏈表中所有非負(fù)數(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é)點(diǎn)的鏈表個節(jié)點(diǎn)的鏈表 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; / 輸出負(fù)數(shù)鏈表輸出負(fù)數(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)鏈表 一般單鏈表的最后一個結(jié)點(diǎn)的指針為一般單鏈表的最后一個結(jié)點(diǎn)的指針為NULL。 如果將單鏈表的最后一個結(jié)點(diǎn)又指向了第一個如果將單鏈表的最后一個結(jié)點(diǎn)又指向了第一個 結(jié)點(diǎn)結(jié)點(diǎn)-形成形成循環(huán)鏈表循環(huán)鏈表 注意：注意：在循環(huán)鏈表中，沒有在循環(huán)鏈表中，沒有空的頭結(jié)點(diǎn)空的頭結(jié)點(diǎn)。 10.6 循環(huán)鏈表與約瑟夫問題循環(huán)鏈表與約瑟夫問題 head a2a1 a3 anan-1 循環(huán)鏈表循環(huán)鏈表的操作與的操作與單單鏈表操作的鏈表操作的不同點(diǎn)：不同點(diǎn)： 1、建立一個循環(huán)鏈表時，必須使其建立一個循環(huán)鏈表時，必須使其最后一個結(jié)點(diǎn)的指針指最后一個結(jié)點(diǎn)的指針指 向表頭結(jié)點(diǎn)向表

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

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

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

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

14、針域。被刪結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)）的指針域。 報(bào)數(shù)變量報(bào)數(shù)變量 s ：對結(jié)點(diǎn)進(jìn)行報(bào)數(shù)，如果報(bào)數(shù)對結(jié)點(diǎn)進(jìn)行報(bào)數(shù)，如果報(bào)數(shù)s=m，則刪，則刪 除除游動指針游動指針 p 所指的結(jié)點(diǎn)所指的結(jié)點(diǎn)。 約瑟夫環(huán)問題約瑟夫環(huán)問題-分析分析 3）循環(huán)執(zhí)行的次數(shù)（即循環(huán)條件）循環(huán)執(zhí)行的次數(shù)（即循環(huán)條件）可以通過可以通過計(jì)數(shù)計(jì)數(shù)來控來控 制，也可以通過對循環(huán)鏈表本身的判定來實(shí)現(xiàn)：制，也可以通過對循環(huán)鏈表本身的判定來實(shí)現(xiàn)： 若若通過通過計(jì)數(shù)判斷計(jì)數(shù)判斷-判斷循環(huán)鏈表是否只剩一個結(jié)點(diǎn)：判斷循環(huán)鏈表是否只剩一個結(jié)點(diǎn)： 如果只剩一個結(jié)點(diǎn)，則已刪除如果只剩一個結(jié)點(diǎ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)建順序建立無頭結(jié)點(diǎn)的鏈表順序建立無頭結(jié)點(diǎn)的鏈表 int i; struct monkey *p,*tail,*h; p=(struct monkey *)malloc(sizeof(struct

16、 monkey); p-num=1; p-next=NULL; / 第一個結(jié)點(diǎn)的生成第一個結(jié)點(diǎn)的生成 h=p; tail=p; /h、tail-均指向第一個結(jié)點(diǎn)均指向第一個結(jié)點(diǎn) for(i=2;inum=i; p-next=NULL; tail-next=p; tail=p; tail-next=h; / 最后一個結(jié)點(diǎn)的指針域指向第一個結(jié)點(diǎn)形成循環(huán)鏈表最后一個結(jié)點(diǎn)的指針域指向第一個結(jié)點(diǎn)形成循環(huán)鏈表 return h; int sel(struct monkey *h,int n,int m) / n只猴子報(bào)數(shù)只猴子報(bào)數(shù)m出圈出圈-返回猴王序號返回猴王序號 int s=0; / 猴子報(bào)數(shù)的計(jì)數(shù)變

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

18、即為留在圈內(nèi)的猴王序號圈內(nèi)的猴王序號 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; 如何通過鏈表本身判斷，圈內(nèi)剩余一個猴王？如何通過鏈表本身判斷，圈內(nèi)剩余一個猴王？ -當(dāng)循環(huán)鏈表只剩一個結(jié)點(diǎn)，此時循環(huán)鏈表結(jié)當(dāng)循環(huán)鏈表只剩一個結(jié)點(diǎn)，此時循環(huán)鏈表結(jié) 構(gòu)如下圖所示：構(gòu)如下圖所示： h i 基本特征是：基本特征是：q-next=q ; 此時：循環(huán)條件此時：循環(huán)條件while(cnn

19、ext!=q) 2056不敢死隊(duì)問題不敢死隊(duì)問題 #include /2056不敢死隊(duì)問題不敢死隊(duì)問題 #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)鏈表的第一個結(jié)點(diǎn)建立循環(huán)鏈表的第一個結(jié)點(diǎn) p-num=1; p-next=NULL; /第第1個結(jié)點(diǎn)是排長個結(jié)點(diǎn)是排長 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(