1、數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)joseph環(huán)152208100066張小蓮目錄需求分析-03算法分析-04該單循環(huán)鏈表的邏輯結(jié)構(gòu)-04刪除出列的結(jié)點(diǎn)-04判斷是否所有人全部出列-04算法設(shè)計(jì)-05PersonList結(jié)構(gòu)體-05CreateList函數(shù)-05Exports函數(shù)-05完整代碼-07結(jié)果說明-09總結(jié)-10 需求分析 編號(hào)是1，2，,n的n個(gè)人按照順時(shí)針方向圍坐一圈，每個(gè)人只有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m，從第一個(gè)人開始順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直到所

2、有人全部出列為止。設(shè)計(jì)一個(gè)程序來求出出列順序。算法分析1. 該單循環(huán)鏈表的邏輯結(jié)構(gòu)由于題目要求“從第一個(gè)人開始順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去”，隊(duì)伍中編號(hào)最大的人報(bào)數(shù)完畢后編號(hào)最小的人應(yīng)緊接著報(bào)數(shù)，所以創(chuàng)建鏈表時(shí)鏈表中最后一個(gè)結(jié)點(diǎn)的next指針直接指向首結(jié)點(diǎn)而不是頭結(jié)點(diǎn)比較合適。該單循環(huán)鏈表的邏輯結(jié)構(gòu)如下：2. 刪除出列的結(jié)點(diǎn)某結(jié)點(diǎn)出列后，應(yīng)將該結(jié)點(diǎn)從單循環(huán)鏈表里刪除，則需要找到該結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，并由p指向它，通過修改指針域使結(jié)點(diǎn)p的直接后繼為s的直接后繼，即p->next=s-&

3、gt;next。當(dāng)m=1時(shí)，即將出列的結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)就是還未進(jìn)行移動(dòng)的當(dāng)前的s指針指向的結(jié)點(diǎn)。當(dāng)要?jiǎng)h除的結(jié)點(diǎn)恰好為head指向的結(jié)點(diǎn)時(shí)，刪除前應(yīng)修改head指向的結(jié)點(diǎn)為s->next。3. 判斷是否所有人全部出列由于結(jié)點(diǎn)出列后的刪除操作，整個(gè)單循環(huán)鏈表的表長是逐漸縮短的，直至單鏈表只剩下頭結(jié)點(diǎn)和首結(jié)點(diǎn)：此時(shí)已經(jīng)無法在進(jìn)行刪除結(jié)點(diǎn)操作，因?yàn)樵摻Y(jié)點(diǎn)的直接后繼就是自己。但實(shí)際上，當(dāng)只剩下一個(gè)人時(shí)無論m為何值此人直接出列就可以了。也就是說，當(dāng)鏈表里只剩下最后一個(gè)結(jié)點(diǎn)時(shí)已經(jīng)不必進(jìn)行刪除操作，直接輸出該結(jié)點(diǎn)的編號(hào)即可。 于是問題就轉(zhuǎn)化成如何判斷鏈表里只剩最后一個(gè)結(jié)點(diǎn)，判斷head->next

4、是否與head相等可以解決問題。算法設(shè)計(jì)1. PersonList結(jié)構(gòu)體每個(gè)結(jié)點(diǎn)包含編號(hào)，密碼以及指向下一個(gè)結(jié)點(diǎn)的指針域三個(gè)數(shù)據(jù)。typedef struct nodeint password; /密碼int number; /編號(hào)struct node *next; /指針域 PersonList;2. CreateList函數(shù)該函數(shù)的功能是建立單循環(huán)鏈表，并從鍵盤讀入每個(gè)編號(hào)的密碼，入口參數(shù)n為單循環(huán)鏈表所包含的結(jié)點(diǎn)的個(gè)數(shù)，函數(shù)返回一個(gè)PersonList類型的指針。PersonList *CreateList(int n)PersonList *head,*s,*r;head=(Pers

5、onList *) malloc(sizeof(PersonList);head->next=NULL; head->number=1;printf("請輸入編號(hào)為1的人的密碼："); scanf("%d",&head->password); /從鍵盤中讀取編號(hào)為1的人的密碼getchar(); /接收回車r=head; for(int i=2;i<=n;i+)s=(PersonList *) malloc(sizeof(PersonList);s->next=NULL;s->number=i;printf(&

6、quot;請輸入編號(hào)為%d的人的密碼：",i);scanf("%d",&s->password); /從鍵盤讀入每個(gè)編號(hào)的密碼getchar(); /接收回車r->next=s; /插入新結(jié)點(diǎn)r=s; /將尾指針指向新結(jié)點(diǎn)r->next=head; /將最后一個(gè)結(jié)點(diǎn)的指針域指向首結(jié)點(diǎn)return head;3. Exports函數(shù)該函數(shù)的功能是模擬出列的過程，并按照出列的順序輸出每個(gè)人的編號(hào)，入口參數(shù)head為單循環(huán)鏈表，入口參數(shù)m為初始報(bào)數(shù)上限值。void Exports(PersonList *head,int m)PersonLis

7、t *s,*p;s=head; m=m-1;printf("出列順序?yàn)?"); while(head!=head->next) /當(dāng)鏈表里有一個(gè)以上的結(jié)點(diǎn)時(shí)if(m!=1) /若m=1可跳過for循環(huán) for(int i=1;i<=m-1;i+) /報(bào)數(shù)直到第m-1個(gè)結(jié)點(diǎn)s=s->next;p=s; /p指向第m-1個(gè)結(jié)點(diǎn)s=s->next; /s指向第m個(gè)結(jié)點(diǎn)printf("%4d",s->number); /輸出第m個(gè)結(jié)點(diǎn)的編號(hào)m=s->password; /將第m個(gè)結(jié)點(diǎn)的密碼作為新的m值 if(s=head) /

8、若要?jiǎng)h除的結(jié)點(diǎn)恰好是首結(jié)點(diǎn)，移動(dòng)head指針head=s->next;p->next=s->next; /刪除第m個(gè)結(jié)點(diǎn)s=p; /s指向報(bào)數(shù)1結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，為下一次報(bào)數(shù)做準(zhǔn)備 printf("%4d",s->number); /輸出鏈表里剩下的唯一一個(gè)結(jié)點(diǎn)完整代碼#include <stdio.h>#include <stdlib.h>typedef struct nodeint password;int number;struct node *next; PersonList;PersonList *CreateLis

9、t(int n)PersonList *head,*s,*r;head=(PersonList *) malloc(sizeof(PersonList);head->next=NULL; head->number=1;printf("請輸入編號(hào)為1的人的密碼：");scanf("%d",&head->password);getchar();r=head; for(int i=2;i<=n;i+)s=(PersonList *) malloc(sizeof(PersonList);s->next=NULL;s->

10、number=i;printf("請輸入編號(hào)為%d的人的密碼：",i);scanf("%d",&s->password);getchar();r->next=s;r=s;r->next=head;return head;void Exports(PersonList *head,int m)PersonList *s,*p;s=head;m-;printf("出列順序?yàn)?"); while(head->next!=head)if(m!=1) for(int i=1;i<=m-1;i+)s=s-&g

11、t;next;p=s;s=s->next;printf("%4d",s->number);m=s->password;if(s=head)head=s->next;p->next=s->next;s=p;printf("%4d",s->number);void main()int m,n;printf("請輸入報(bào)數(shù)上限值：");scanf("%d",&m);printf("請輸入?yún)⒓訄?bào)數(shù)的人數(shù)：");scanf("%d",&n);PersonList *q=CreateList(n);Exports(q,m);printf("n");結(jié)果說明第一輪報(bào)數(shù) m=7 編號(hào)為7的人出列第二輪報(bào)數(shù) m=4 編號(hào)為1的人出列第三輪報(bào)數(shù) m=5 編號(hào)為6的人出列第四輪報(bào)數(shù) m=4 編號(hào)為2的人出列第