一、課程設(shè)計目的與任務(wù)
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計是為訓(xùn)練學(xué)生的數(shù)據(jù)組織能力和提高程序設(shè)計能力而設(shè)置的增強實踐能力的課程。目的：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程，旨在使學(xué)生學(xué)會分析研究數(shù)據(jù)對象的特性，學(xué)會數(shù)據(jù)的組織方法，以便選擇合適的數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)以及相應(yīng)操作，把現(xiàn)實世界中的問題轉(zhuǎn)換為計算機內(nèi)部的表示和處理，這就是一個良好的程序設(shè)計技能訓(xùn)練的過程。提高學(xué)生的程序設(shè)計能力、掌握基本知識、基本技能，提高算法設(shè)計質(zhì)量與程序設(shè)計素質(zhì)的培養(yǎng)就是本門課程的課程設(shè)計的目的。
任務(wù)：根據(jù)題目要求，完成算法設(shè)計與程序?qū)崿F(xiàn)，并按規(guī)定寫出課程設(shè)計報告。
二、課程設(shè)計的內(nèi)容與基本要求
設(shè)計題目：約瑟夫生死游戲
〔問題描述〕：約瑟夫生死游戲的大意是：30個旅客同乘一條船，因為嚴重超載，加上風(fēng)高浪大，危險萬分；因此船長告訴乘客，只有將全船一半的旅客投入海中，其余人才能幸免遇難。無奈，大家只得同意這種辦法，并議定30個人圍成一圈，由第一個人開始，依次報數(shù)，數(shù)到第9人，便把他投入大海中，然后從他的下一個人數(shù)起，數(shù)到第9人，再將他投入大海，如此循環(huán)，直到剩下15個乘客為止。問哪些位置是將被扔下大海的位置。
〔基本要求〕本游戲的數(shù)學(xué)建模如下：假設(shè)n個旅客排成一個環(huán)形，依次順序編號1，2，…，n。從某個指定的第j號開始，沿環(huán)計數(shù)，每數(shù)到第m個人就讓其出列，且從下一個人開始重新計數(shù)，繼續(xù)進行下去。這個過程一直進行到剩下k個旅客為止。
本游戲要求用戶輸入的內(nèi)容包括n,m,j,k的值.
本游戲要求輸出的內(nèi)容是包括
1. 離開旅客的序號；
2. 剩余旅客的序號；
〔提示〕根據(jù)上面的模型及輸入輸出參數(shù)分析，可以采用循環(huán)鏈表來進行算法實現(xiàn)。
具體要完成的任務(wù)是：
?? A. 編制完成上述問題的C語言程序、進行程序調(diào)試并能得出正確的運行結(jié)果。
?? B. 寫出規(guī)范的課程設(shè)計報告書；
三、學(xué)時分配進度安排
| 序號 |
設(shè)計內(nèi)容 |
所用時間 |
| 1 |
選題及調(diào)研 |
1天 |
| 2 |
功能及算法分析，編寫程序 |
3天 |
| 3 |
調(diào)試程序，運行系統(tǒng) |
3天 |
| 4 |
程序完成及撰寫報告 |
2天 |
| 5 |
答辯 |
1天 |
| 合??? 計 |
2周 |
|
四、課程設(shè)計考核及評分標準
1.設(shè)計報告要求
課程設(shè)計報告要求邏輯清晰、層次分明、書寫整潔。報告書應(yīng)包括設(shè)計題目、設(shè)計思想、系統(tǒng)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)說明及模塊算法說明、使用說明書、測試結(jié)果分析，附錄（程序清單）。設(shè)計報告須每人一份，獨立完成。
2.評分標準
課程設(shè)計考核將綜合考慮學(xué)生的系統(tǒng)設(shè)計方案、運行結(jié)果、課程設(shè)計報告書的質(zhì)量、態(tài)度、考勤、答辯情況等各因素。具體評分標準如下：?
| 評分標準 |
分值 |
| （1）設(shè)計方案正確，具有可行性、創(chuàng)新性； |
20分 |
| （2）系統(tǒng)開發(fā)效果較好； |
20分 |
| （3）課程設(shè)計報告書寫規(guī)范、質(zhì)量高； |
30分 |
| （4）課程設(shè)計答辯時，回答問題正確； |
20分 |
| （5）態(tài)度認真、刻苦鉆研、遵守紀律； |
10分 |
| 總分 |
100分 |
?? 注：成績等級：優(yōu)（90分—100分）、良（80分—89分）、中（70分—79分）、及格（60分—69分）、60分以下為不及格。
五、指導(dǎo)時間
| 周次 |
星期一 |
星期二 |
星期三 |
星期四 |
星期五 |
| 第16周 |
第3-4節(jié) |
第3-4節(jié) |
第1-2節(jié) |
???????????
| 周次 |
星期一 |
星期二 |
星期三 |
星期四 |
星期五 |
| 第17周 |
第1-4節(jié) |
第3-4節(jié) |
第3-4節(jié) |
第3-4節(jié) |
第1-4節(jié) |
???????????????????????????
目? 錄
1 設(shè)計題目....................................................................... 1
2 設(shè)計思想....................................................................... 1
3 系統(tǒng)結(jié)構(gòu)....................................................................... 1
4 數(shù)據(jù)結(jié)構(gòu)說明和模塊算法說明.................................... 1
5 使用說明書................................................................... 2
6 運行結(jié)果....................................................................... 2
7 測試過程及結(jié)果分析.................................................... 2
8 附錄：源程序清單....................................................... 2
課程設(shè)計成績評定表....................................................... 3
1.設(shè)計題目
約瑟夫問題
2.設(shè)計思想
結(jié)構(gòu)分析：由于需要不斷刪除元素，順序表刪除元素時間開銷過大，而且順序訪問到最后會出現(xiàn)越界問題，但設(shè)置循環(huán)鏈表可避免此問題，且鏈表刪除元素時間復(fù)雜度為O(1)，因此結(jié)構(gòu)上選擇鏈表
核心功能設(shè)計思路：核心功能即刪除元素的功能，由題可知刪除元素個數(shù)往往是過大的，所以利用遞歸調(diào)用刪除函數(shù)來實現(xiàn)
實現(xiàn)思路：
1.設(shè)置鏈表
2.初始化鏈表
3.用戶輸入游戲總?cè)藬?shù)，再輸入從第幾人開始游戲，每隔幾人使其出列，直至所剩多少人，每次數(shù)據(jù)要進行邏輯判斷，以防出現(xiàn)邏輯錯誤
4.然后通過尾插法創(chuàng)建鏈表，創(chuàng)建鏈表時需要將鏈表設(shè)置成循環(huán)鏈表
5.將鏈表當前所指位置調(diào)整為從第幾個人開始的位置，以方便刪除函數(shù)的設(shè)計
6.調(diào)用刪除函數(shù)，每次刪除一個元素，所剩元素的總數(shù)大于要求的所剩元素數(shù)量時，不斷刪除時不斷打印所刪除的元素，便不斷遞歸調(diào)用自身
7.刪除完元素后，此時所剩元素的總數(shù)便為輸入時的數(shù)量，執(zhí)行打印函數(shù)，遍歷現(xiàn)在的鏈表
3.系統(tǒng)結(jié)構(gòu)
|
執(zhí)行程序 |
|
輸入數(shù)據(jù) |
|
數(shù)據(jù)非法，return |
|
創(chuàng)建鏈表 |
|
數(shù)據(jù)合法，初始化 |
|
判斷數(shù)據(jù)合法性 |
|
判斷空間是否分配成功 |
|
空間不足，return |
|
將鏈表所指向的位置調(diào)整為正確位置 |
|
執(zhí)行刪除函數(shù) |
|
打印鏈表 |
|
程序結(jié)束 |
|
不斷打印刪除 |
|
鏈表元素數(shù)量>k |
|
是 |
|
否 |
|
遞歸調(diào)用 |
4.數(shù)據(jù)結(jié)構(gòu)說明和模塊算法說明
4.1鏈表結(jié)構(gòu)：
一個數(shù)據(jù)域，保存的是當前結(jié)點的編號，即本人編號，一個指針域，指向下一個人的結(jié)點，通過typedef添加了替換名LinkList
typedef struct LNode{
??? ElemType data;//數(shù)據(jù)域
??? struct LNode *next;//指針域
} LinkList;
4.2初始化單鏈表：
一個參數(shù)，即鏈表，將鏈表初始化，即L->next為NULL，空間不足時return，即分配失敗，初始化結(jié)束時輸出initList successfully
int InitList(LinkList *L){
??? // L=(LinkList *)malloc(sizeof(LinkList));
??? if (L==NULL) return 0;//分配失敗
??? L->next=NULL;//空表，類似于順序表n=0
??? printf("initList successfully\n");
}文章來源地址http://www.zghlxwxcb.cn/news/detail-833908.html
4.3尾插法創(chuàng)建鏈表：
尾插法創(chuàng)建鏈表，每次都是在鏈表末端插入元素，該函數(shù)有兩個參數(shù)，一是鏈表，二是創(chuàng)建多少個元素，創(chuàng)建多少個元素的數(shù)值如果低于0則會認為是非法操作，return，用的是while循環(huán)，條件是i<=k，i初值為1，同時設(shè)置該鏈表為循環(huán)鏈表，創(chuàng)建結(jié)束后打印Created successfully
int FootCreateList(LinkList *L,ElemType k){
??? //非法操作或創(chuàng)建失敗
??? if(k<0) return 0;
??? LinkList *temp,*LCopy;
??? LCopy=L;
??? int i=1;
??? while(i<=k){
??????? temp=(LinkList *)malloc(sizeof(LinkList));
??????? if(temp==NULL) return 0;
??????? temp->data=i;
??????? L->next=temp;
??????? L=L->next;//鏈表位置始終保持在最后
??????? i++;
??? }
??? L->next=LCopy->next;//尾結(jié)點連接頭結(jié)點后第一個元素結(jié)點
??? printf("Created successfully\n");
}
4.4打印操作：
該函數(shù)兩個參數(shù)，一是鏈表，二是該鏈表長度，會使用一個鏈表的副本temp來不斷遍歷，通過for循環(huán)來遍歷，每次都將打印temp->data，再使其指向下一結(jié)點temp=temp->next，打印結(jié)束后輸出print successfully
void PrintList(LinkList *L,ElemType k){
??? LinkList *temp=L;
??? temp=temp->next;//從頭結(jié)點指向首結(jié)點
??? for (int i = 0; i < k; ++i)
??? {
??????? printf("%d\n",temp->data);
??????? temp=temp->next;
??? }
??? printf("print successfully\n");
}
4.5刪除操作：
該函數(shù)有四個參數(shù)，鏈表，每隔幾人刪除一個，直至總?cè)藬?shù)所剩多少人，鏈表長度（即總?cè)藬?shù)），通過for循環(huán)遍歷到將要刪除的元素的前一個元素，此時跳出for循環(huán)，輸出將被刪除的元素L->next->data，修改當前元素指向的下一個元素為下下個元素，L->next=L->next->next，此時便刪除掉了當前元素
改進方向：未將當前元素下一結(jié)點的空間釋放，可能會造成空間的浪費，可以添加釋放結(jié)點語句
ElemType DeleteElemList(LinkList *L,int m,int k,int *n){
??? int i=1;
??? //從j位往后數(shù)m-1位，將要刪除元素的前一位
??? for (; i <= m-1; ++i)
??? {??
??????? L=L->next;
??? }
??? // printf("所刪元素為:%d \n",L->next->data);//輸出目標元素
??? L->next=L->next->next;//跳過目標元素
??? (*n)=(*n)-1;//長度減1
??? //未達到k人時不斷遞歸調(diào)用
??? if (k<(*n)) DeleteElemList( L, m, k , n);
???
}
4.6主函數(shù)：
創(chuàng)建鏈表，并為其分配空間，再輸入游戲總?cè)藬?shù)，從第幾人開始游戲，每隔幾個人使其出列，最終剩下多少人，其中設(shè)置了數(shù)值上的邏輯判斷，避免出現(xiàn)邏輯上的錯誤，首先初始化鏈表，當輸入總?cè)藬?shù)時便開始判斷該人數(shù)數(shù)量是否有問題，有問題則return，沒問題則創(chuàng)建長度為總?cè)藬?shù)數(shù)量的鏈表，鏈表數(shù)值為升序序列，其次輸入從第幾個人開始游戲，輸入后判斷是否符合邏輯，再者輸入每隔幾人使其出列，輸入判斷是否負荷邏輯，最后輸入游戲剩余人數(shù)，同樣判斷是否符合邏輯，邏輯判斷結(jié)束后，調(diào)整鏈表所指位置為剛開始指定從第幾個人開始的位置，調(diào)用刪除函數(shù)，參數(shù)為，該鏈表，每個幾個人使其出列再減一，直至所剩多少人，鏈表長度（即總?cè)藬?shù)）
int main()
{
??? //n人，從j開始計數(shù)，第m個人使其出列，直至所剩k人
??? int n,m,j,k;
??? LinkList *L;//聲明一個指向單鏈表的帶頭指針L
??? L=(LinkList *)malloc(sizeof(LinkList));
??? InitList(L);
??? //插入n元素，即n人
??? printf("輸入n人\n");
??? scanf("%d",&n);
??? if (n<1){
??????? printf("非法輸入");
??????? return 0;
??? }
??? //為鏈表創(chuàng)建n結(jié)點
??? FootCreateList(L,n);
??? //打印
??? // PrintList(L,n);
??? printf("從j開始計數(shù)\n");
??? scanf("%d",&j);
??? if (j>n){
??????? printf("非法輸入");
??????? return 0;
??? }
??? printf("第m個人使其出列\(zhòng)n");
??? scanf("%d",&m);
??? if (m>=n){
??????? printf("非法輸入");
??????? return 0;
??? }
??? printf("直至所剩k人\n");
??? scanf("%d",&k);
??? if (k>=n){
??????? printf("非法輸入");
??????? return 0;
??? }
??? //調(diào)整正確位置到j(luò)位
??? for (int i = 0; i < j; ++i)
??? {??
??????? L=L->next;//此時temp指到目標位置
??? }
??? //開始操作
??? DeleteElemList(L,m-1,k,&n);
??? // printf("最后的n為%d\n",n);
??? printf("所剩元素為\n");
??? PrintList(L,n);
??? return 0;文章來源：http://www.zghlxwxcb.cn/news/detail-833908.html
}
5.使用說明書
游戲步驟：
第一步：輸入總?cè)藬?shù)
第二步：輸入從第幾個人開始計數(shù)
第三步：輸入每隔幾個人使其出列
第四步：輸入直到總?cè)藬?shù)達到多少人時游戲結(jié)束
第五步：等待結(jié)果
游戲規(guī)則：
1.游戲總?cè)藬?shù)不允許低于一人
2.從第幾個人開始計數(shù)，這個人的序號不能超過總?cè)藬?shù)
3. 每隔幾個人使其出列，所隔人數(shù)不能超過或等于總?cè)藬?shù)
4.所剩總?cè)藬?shù)不能大于等于游戲開始時總?cè)藬?shù)
6.運行結(jié)果
題目所示數(shù)據(jù)結(jié)果（n=30，j=1，m=9，k=15）
結(jié)果分析：
輸入30，即總?cè)藬?shù)30，創(chuàng)建長度為30的循環(huán)鏈表，輸入1，即從第一個人開始計數(shù)，輸入9，即從第一個人開始，第九人出列，輸入15，即直至所剩15人游戲結(jié)束，之后將鏈表所指位置指向開始計數(shù)的那個人的位置，再調(diào)用刪除函數(shù)，所剩人數(shù)超過要求的人便不斷遞歸調(diào)用刪除函數(shù)，每一次所刪元素如下列所示
第一次所刪元素為:9
第二次所刪元素為:17
第三次所刪元素為:25
第四次所刪元素為:3
第五次所刪元素為:12
第六次所刪元素為:21
第七次所刪元素為:30
第八次所刪元素為:10
第九次所刪元素為:20
第十次所刪元素為:1
第十一次所刪元素為:13
第十二次所刪元素為:24
第十三次所刪元素為:6
第十四次所刪元素為:19
第十五次所刪元素為:4
7.測試過程及結(jié)果分析
非法數(shù)據(jù)測試（n=2，j=2，m=2）
邊界數(shù)據(jù)測試（n=2，j=1，m=1，k=2）
極限數(shù)據(jù)測試（計算量過大，并未立即得出結(jié)果）
8.附錄：源程序清單
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{
??? ElemType data;//數(shù)據(jù)域
??? struct LNode *next;//指針域
} LinkList;
//初始化單鏈表
int InitList(LinkList *L){
??? // L=(LinkList *)malloc(sizeof(LinkList));
??? if (L==NULL) return 0;//分配失敗
??? L->next=NULL;//空表，類似于順序表n=0
??? printf("initList successfully\n");
}
//頭插法創(chuàng)建鏈表
int HeadCreateList(LinkList *L,ElemType k){
??? if(k<1) return 0;
??? LinkList *temp;
??? if (temp==NULL) return 0;//分配失敗
??? int i=1;
??? while(i<=k){
??????? temp=(LinkList *)malloc(sizeof(LinkList));
??????? temp->data=i;//交替指向添加元素
??????? temp->next=L->next;//鏈表循環(huán)賦值
??????? L->next=temp;
??????? i++;
??? }
??? printf("Created successfully\n");
}
//尾插法創(chuàng)建鏈表
int FootCreateList(LinkList *L,ElemType k){
??? //非法操作或創(chuàng)建失敗
??? if(k<0) return 0;
??? LinkList *temp,*LCopy;
??? LCopy=L;
??? int i=1;
??? while(i<=k){
??????? temp=(LinkList *)malloc(sizeof(LinkList));
??????? if(temp==NULL) return 0;
??????? temp->data=i;
??????? L->next=temp;
??????? L=L->next;//鏈表位置始終保持在最后
??????? i++;
??? }
??? L->next=LCopy->next;//尾結(jié)點連接頭結(jié)點后第一個元素結(jié)點
??? printf("Created successfully\n");
}
//打印操作
void PrintList(LinkList *L,ElemType k){
??? LinkList *temp=L;
??? temp=temp->next;//從頭結(jié)點指向首結(jié)點
??? for (int i = 0; i < k; ++i)
??? {
??????? printf("%d\n",temp->data);
??????? temp=temp->next;
??? }
??? printf("print successfully\n");
}
//遞歸調(diào)用，每隔m個刪除一個，直至所剩k人
ElemType DeleteElemList(LinkList *L,int m,int k,int *n){
??? int i=1;
??? //從j位往后數(shù)m-1位，將要刪除元素的前一位
??? for (; i <= m-1; ++i)
??? {??
??????? L=L->next;
??? }
??? // printf("所刪元素為:%d \n",L->next->data);//輸出目標元素
??? L->next=L->next->next;//跳過目標元素
??? (*n)=(*n)-1;//長度減1
??? //未達到k人時不斷遞歸調(diào)用
??? if (k<(*n)) DeleteElemList( L, m, k , n);
???
}
int main()
{
??? //n人，從j開始計數(shù)，第m個人使其出列，直至所剩k人
??? int n,m,j,k;
??? LinkList *L;//聲明一個指向單鏈表的帶頭指針L
??? L=(LinkList *)malloc(sizeof(LinkList));
??? InitList(L);
??? //插入n元素，即n人
??? printf("輸入n人\n");
??? scanf("%d",&n);
??? if (n<1){
??????? printf("非法輸入");
??????? return 0;
??? }
??? //為鏈表創(chuàng)建n結(jié)點
??? FootCreateList(L,n);
??? //打印
??? // PrintList(L,n);
??? printf("從j開始計數(shù)\n");
??? scanf("%d",&j);
??? if (j>n){
??????? printf("非法輸入");
??????? return 0;
??? }
??? printf("第m個人使其出列\(zhòng)n");
??? scanf("%d",&m);
??? if (m>=n){
??????? printf("非法輸入");
??????? return 0;
??? }
??? printf("直至所剩k人\n");
??? scanf("%d",&k);
??? if (k>=n){
??????? printf("非法輸入");
??????? return 0;
??? }
??? //調(diào)整正確位置到j(luò)位
??? for (int i = 0; i < j; ++i)
??? {??
??????? L=L->next;//此時temp指到目標位置
??? }
??? //開始操作
??? DeleteElemList(L,m-1,k,&n);
??? // printf("最后的n為%d\n",n);
??? printf("所剩元素為\n");
??? PrintList(L,n);
??? return 0;
}
一、課程設(shè)計目的與任務(wù)
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計是為訓(xùn)練學(xué)生的數(shù)據(jù)組織能力和提高程序設(shè)計能力而設(shè)置的增強實踐能力的課程。目的：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程，旨在使學(xué)生學(xué)會分析研究數(shù)據(jù)對象的特性，學(xué)會數(shù)據(jù)的組織方法，以便選擇合適的數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)以及相應(yīng)操作，把現(xiàn)實世界中的問題轉(zhuǎn)換為計算機內(nèi)部的表示和處理，這就是一個良好的程序設(shè)計技能訓(xùn)練的過程。提高學(xué)生的程序設(shè)計能力、掌握基本知識、基本技能，提高算法設(shè)計質(zhì)量與程序設(shè)計素質(zhì)的培養(yǎng)就是本門課程的課程設(shè)計的目的。
任務(wù)：根據(jù)題目要求，完成算法設(shè)計與程序?qū)崿F(xiàn)，并按規(guī)定寫出課程設(shè)計報告。
二、課程設(shè)計的內(nèi)容與基本要求
設(shè)計題目：約瑟夫生死游戲
〔問題描述〕：約瑟夫生死游戲的大意是：30個旅客同乘一條船，因為嚴重超載，加上風(fēng)高浪大，危險萬分；因此船長告訴乘客，只有將全船一半的旅客投入海中，其余人才能幸免遇難。無奈，大家只得同意這種辦法，并議定30個人圍成一圈，由第一個人開始，依次報數(shù)，數(shù)到第9人，便把他投入大海中，然后從他的下一個人數(shù)起，數(shù)到第9人，再將他投入大海，如此循環(huán)，直到剩下15個乘客為止。問哪些位置是將被扔下大海的位置。
〔基本要求〕本游戲的數(shù)學(xué)建模如下：假設(shè)n個旅客排成一個環(huán)形，依次順序編號1，2，…，n。從某個指定的第j號開始，沿環(huán)計數(shù)，每數(shù)到第m個人就讓其出列，且從下一個人開始重新計數(shù)，繼續(xù)進行下去。這個過程一直進行到剩下k個旅客為止。
本游戲要求用戶輸入的內(nèi)容包括n,m,j,k的值.
本游戲要求輸出的內(nèi)容是包括
1. 離開旅客的序號；
2. 剩余旅客的序號；
〔提示〕根據(jù)上面的模型及輸入輸出參數(shù)分析，可以采用循環(huán)鏈表來進行算法實現(xiàn)。
具體要完成的任務(wù)是：
?? A. 編制完成上述問題的C語言程序、進行程序調(diào)試并能得出正確的運行結(jié)果。
?? B. 寫出規(guī)范的課程設(shè)計報告書；
三、學(xué)時分配進度安排
| 序號 |
設(shè)計內(nèi)容 |
所用時間 |
| 1 |
選題及調(diào)研 |
1天 |
| 2 |
功能及算法分析，編寫程序 |
3天 |
| 3 |
調(diào)試程序，運行系統(tǒng) |
3天 |
| 4 |
程序完成及撰寫報告 |
2天 |
| 5 |
答辯 |
1天 |
| 合??? 計 |
2周 |
|
四、課程設(shè)計考核及評分標準
1.設(shè)計報告要求
課程設(shè)計報告要求邏輯清晰、層次分明、書寫整潔。報告書應(yīng)包括設(shè)計題目、設(shè)計思想、系統(tǒng)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)說明及模塊算法說明、使用說明書、測試結(jié)果分析，附錄（程序清單）。設(shè)計報告須每人一份，獨立完成。
2.評分標準
課程設(shè)計考核將綜合考慮學(xué)生的系統(tǒng)設(shè)計方案、運行結(jié)果、課程設(shè)計報告書的質(zhì)量、態(tài)度、考勤、答辯情況等各因素。具體評分標準如下：?
| 評分標準 |
分值 |
| （1）設(shè)計方案正確，具有可行性、創(chuàng)新性； |
20分 |
| （2）系統(tǒng)開發(fā)效果較好； |
20分 |
| （3）課程設(shè)計報告書寫規(guī)范、質(zhì)量高； |
30分 |
| （4）課程設(shè)計答辯時，回答問題正確； |
20分 |
| （5）態(tài)度認真、刻苦鉆研、遵守紀律； |
10分 |
| 總分 |
100分 |
?? 注：成績等級：優(yōu)（90分—100分）、良（80分—89分）、中（70分—79分）、及格（60分—69分）、60分以下為不及格。
五、指導(dǎo)時間
| 周次 |
星期一 |
星期二 |
星期三 |
星期四 |
星期五 |
| 第16周 |
第3-4節(jié) |
第3-4節(jié) |
第1-2節(jié) |
???????????
| 周次 |
星期一 |
星期二 |
星期三 |
星期四 |
星期五 |
| 第17周 |
第1-4節(jié) |
第3-4節(jié) |
第3-4節(jié) |
第3-4節(jié) |
第1-4節(jié) |
???????????????????????????
目? 錄
1 設(shè)計題目....................................................................... 1
2 設(shè)計思想....................................................................... 1
3 系統(tǒng)結(jié)構(gòu)....................................................................... 1
4 數(shù)據(jù)結(jié)構(gòu)說明和模塊算法說明.................................... 1
5 使用說明書................................................................... 2
6 運行結(jié)果....................................................................... 2
7 測試過程及結(jié)果分析.................................................... 2
8 附錄：源程序清單....................................................... 2
課程設(shè)計成績評定表....................................................... 3
1.設(shè)計題目
約瑟夫問題
2.設(shè)計思想
結(jié)構(gòu)分析：由于需要不斷刪除元素，順序表刪除元素時間開銷過大，而且順序訪問到最后會出現(xiàn)越界問題，但設(shè)置循環(huán)鏈表可避免此問題，且鏈表刪除元素時間復(fù)雜度為O(1)，因此結(jié)構(gòu)上選擇鏈表
核心功能設(shè)計思路：核心功能即刪除元素的功能，由題可知刪除元素個數(shù)往往是過大的，所以利用遞歸調(diào)用刪除函數(shù)來實現(xiàn)
實現(xiàn)思路：
1.設(shè)置鏈表
2.初始化鏈表
3.用戶輸入游戲總?cè)藬?shù)，再輸入從第幾人開始游戲，每隔幾人使其出列，直至所剩多少人，每次數(shù)據(jù)要進行邏輯判斷，以防出現(xiàn)邏輯錯誤
4.然后通過尾插法創(chuàng)建鏈表，創(chuàng)建鏈表時需要將鏈表設(shè)置成循環(huán)鏈表
5.將鏈表當前所指位置調(diào)整為從第幾個人開始的位置，以方便刪除函數(shù)的設(shè)計
6.調(diào)用刪除函數(shù)，每次刪除一個元素，所剩元素的總數(shù)大于要求的所剩元素數(shù)量時，不斷刪除時不斷打印所刪除的元素，便不斷遞歸調(diào)用自身
7.刪除完元素后，此時所剩元素的總數(shù)便為輸入時的數(shù)量，執(zhí)行打印函數(shù)，遍歷現(xiàn)在的鏈表
3.系統(tǒng)結(jié)構(gòu)
|
執(zhí)行程序 |
|
輸入數(shù)據(jù) |
|
數(shù)據(jù)非法，return |
|
創(chuàng)建鏈表 |
|
數(shù)據(jù)合法，初始化 |
|
判斷數(shù)據(jù)合法性 |
|
判斷空間是否分配成功 |
|
空間不足，return |
|
將鏈表所指向的位置調(diào)整為正確位置 |
|
執(zhí)行刪除函數(shù) |
|
打印鏈表 |
|
程序結(jié)束 |
|
不斷打印刪除 |
|
鏈表元素數(shù)量>k |
|
是 |
|
否 |
|
遞歸調(diào)用 |
4.數(shù)據(jù)結(jié)構(gòu)說明和模塊算法說明
4.1鏈表結(jié)構(gòu)：
一個數(shù)據(jù)域，保存的是當前結(jié)點的編號，即本人編號，一個指針域，指向下一個人的結(jié)點，通過typedef添加了替換名LinkList
typedef struct LNode{
??? ElemType data;//數(shù)據(jù)域
??? struct LNode *next;//指針域
} LinkList;
4.2初始化單鏈表：
一個參數(shù)，即鏈表，將鏈表初始化，即L->next為NULL，空間不足時return，即分配失敗，初始化結(jié)束時輸出initList successfully
int InitList(LinkList *L){
??? // L=(LinkList *)malloc(sizeof(LinkList));
??? if (L==NULL) return 0;//分配失敗
??? L->next=NULL;//空表，類似于順序表n=0
??? printf("initList successfully\n");
}
4.3尾插法創(chuàng)建鏈表：
尾插法創(chuàng)建鏈表，每次都是在鏈表末端插入元素，該函數(shù)有兩個參數(shù)，一是鏈表，二是創(chuàng)建多少個元素，創(chuàng)建多少個元素的數(shù)值如果低于0則會認為是非法操作，return，用的是while循環(huán)，條件是i<=k，i初值為1，同時設(shè)置該鏈表為循環(huán)鏈表，創(chuàng)建結(jié)束后打印Created successfully
int FootCreateList(LinkList *L,ElemType k){
??? //非法操作或創(chuàng)建失敗
??? if(k<0) return 0;
??? LinkList *temp,*LCopy;
??? LCopy=L;
??? int i=1;
??? while(i<=k){
??????? temp=(LinkList *)malloc(sizeof(LinkList));
??????? if(temp==NULL) return 0;
??????? temp->data=i;
??????? L->next=temp;
??????? L=L->next;//鏈表位置始終保持在最后
??????? i++;
??? }
??? L->next=LCopy->next;//尾結(jié)點連接頭結(jié)點后第一個元素結(jié)點
??? printf("Created successfully\n");
}
4.4打印操作：
該函數(shù)兩個參數(shù)，一是鏈表，二是該鏈表長度，會使用一個鏈表的副本temp來不斷遍歷，通過for循環(huán)來遍歷，每次都將打印temp->data，再使其指向下一結(jié)點temp=temp->next，打印結(jié)束后輸出print successfully
void PrintList(LinkList *L,ElemType k){
??? LinkList *temp=L;
??? temp=temp->next;//從頭結(jié)點指向首結(jié)點
??? for (int i = 0; i < k; ++i)
??? {
??????? printf("%d\n",temp->data);
??????? temp=temp->next;
??? }
??? printf("print successfully\n");
}
4.5刪除操作：
該函數(shù)有四個參數(shù)，鏈表，每隔幾人刪除一個，直至總?cè)藬?shù)所剩多少人，鏈表長度（即總?cè)藬?shù)），通過for循環(huán)遍歷到將要刪除的元素的前一個元素，此時跳出for循環(huán)，輸出將被刪除的元素L->next->data，修改當前元素指向的下一個元素為下下個元素，L->next=L->next->next，此時便刪除掉了當前元素
改進方向：未將當前元素下一結(jié)點的空間釋放，可能會造成空間的浪費，可以添加釋放結(jié)點語句
ElemType DeleteElemList(LinkList *L,int m,int k,int *n){
??? int i=1;
??? //從j位往后數(shù)m-1位，將要刪除元素的前一位
??? for (; i <= m-1; ++i)
??? {??
??????? L=L->next;
??? }
??? // printf("所刪元素為:%d \n",L->next->data);//輸出目標元素
??? L->next=L->next->next;//跳過目標元素
??? (*n)=(*n)-1;//長度減1
??? //未達到k人時不斷遞歸調(diào)用
??? if (k<(*n)) DeleteElemList( L, m, k , n);
???
}
4.6主函數(shù)：
創(chuàng)建鏈表，并為其分配空間，再輸入游戲總?cè)藬?shù)，從第幾人開始游戲，每隔幾個人使其出列，最終剩下多少人，其中設(shè)置了數(shù)值上的邏輯判斷，避免出現(xiàn)邏輯上的錯誤，首先初始化鏈表，當輸入總?cè)藬?shù)時便開始判斷該人數(shù)數(shù)量是否有問題，有問題則return，沒問題則創(chuàng)建長度為總?cè)藬?shù)數(shù)量的鏈表，鏈表數(shù)值為升序序列，其次輸入從第幾個人開始游戲，輸入后判斷是否符合邏輯，再者輸入每隔幾人使其出列，輸入判斷是否負荷邏輯，最后輸入游戲剩余人數(shù)，同樣判斷是否符合邏輯，邏輯判斷結(jié)束后，調(diào)整鏈表所指位置為剛開始指定從第幾個人開始的位置，調(diào)用刪除函數(shù)，參數(shù)為，該鏈表，每個幾個人使其出列再減一，直至所剩多少人，鏈表長度（即總?cè)藬?shù)）
int main()
{
??? //n人，從j開始計數(shù)，第m個人使其出列，直至所剩k人
??? int n,m,j,k;
??? LinkList *L;//聲明一個指向單鏈表的帶頭指針L
??? L=(LinkList *)malloc(sizeof(LinkList));
??? InitList(L);
??? //插入n元素，即n人
??? printf("輸入n人\n");
??? scanf("%d",&n);
??? if (n<1){
??????? printf("非法輸入");
??????? return 0;
??? }
??? //為鏈表創(chuàng)建n結(jié)點
??? FootCreateList(L,n);
??? //打印
??? // PrintList(L,n);
??? printf("從j開始計數(shù)\n");
??? scanf("%d",&j);
??? if (j>n){
??????? printf("非法輸入");
??????? return 0;
??? }
??? printf("第m個人使其出列\(zhòng)n");
??? scanf("%d",&m);
??? if (m>=n){
??????? printf("非法輸入");
??????? return 0;
??? }
??? printf("直至所剩k人\n");
??? scanf("%d",&k);
??? if (k>=n){
??????? printf("非法輸入");
??????? return 0;
??? }
??? //調(diào)整正確位置到j(luò)位
??? for (int i = 0; i < j; ++i)
??? {??
??????? L=L->next;//此時temp指到目標位置
??? }
??? //開始操作
??? DeleteElemList(L,m-1,k,&n);
??? // printf("最后的n為%d\n",n);
??? printf("所剩元素為\n");
??? PrintList(L,n);
??? return 0;
}
5.使用說明書
游戲步驟：
第一步：輸入總?cè)藬?shù)
第二步：輸入從第幾個人開始計數(shù)
第三步：輸入每隔幾個人使其出列
第四步：輸入直到總?cè)藬?shù)達到多少人時游戲結(jié)束
第五步：等待結(jié)果
游戲規(guī)則：
1.游戲總?cè)藬?shù)不允許低于一人
2.從第幾個人開始計數(shù)，這個人的序號不能超過總?cè)藬?shù)
3. 每隔幾個人使其出列，所隔人數(shù)不能超過或等于總?cè)藬?shù)
4.所?？?cè)藬?shù)不能大于等于游戲開始時總?cè)藬?shù)
6.運行結(jié)果
題目所示數(shù)據(jù)結(jié)果（n=30，j=1，m=9，k=15）
結(jié)果分析：
輸入30，即總?cè)藬?shù)30，創(chuàng)建長度為30的循環(huán)鏈表，輸入1，即從第一個人開始計數(shù)，輸入9，即從第一個人開始，第九人出列，輸入15，即直至所剩15人游戲結(jié)束，之后將鏈表所指位置指向開始計數(shù)的那個人的位置，再調(diào)用刪除函數(shù)，所剩人數(shù)超過要求的人便不斷遞歸調(diào)用刪除函數(shù)，每一次所刪元素如下列所示
第一次所刪元素為:9
第二次所刪元素為:17
第三次所刪元素為:25
第四次所刪元素為:3
第五次所刪元素為:12
第六次所刪元素為:21
第七次所刪元素為:30
第八次所刪元素為:10
第九次所刪元素為:20
第十次所刪元素為:1
第十一次所刪元素為:13
第十二次所刪元素為:24
第十三次所刪元素為:6
第十四次所刪元素為:19
第十五次所刪元素為:4
7.測試過程及結(jié)果分析
非法數(shù)據(jù)測試（n=2，j=2，m=2）
邊界數(shù)據(jù)測試（n=2，j=1，m=1，k=2）
極限數(shù)據(jù)測試（計算量過大，并未立即得出結(jié)果）
8.附錄：源程序清單
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{
??? ElemType data;//數(shù)據(jù)域
??? struct LNode *next;//指針域
} LinkList;
//初始化單鏈表
int InitList(LinkList *L){
??? // L=(LinkList *)malloc(sizeof(LinkList));
??? if (L==NULL) return 0;//分配失敗
??? L->next=NULL;//空表，類似于順序表n=0
??? printf("initList successfully\n");
}
//頭插法創(chuàng)建鏈表
int HeadCreateList(LinkList *L,ElemType k){
??? if(k<1) return 0;
??? LinkList *temp;
??? if (temp==NULL) return 0;//分配失敗
??? int i=1;
??? while(i<=k){
??????? temp=(LinkList *)malloc(sizeof(LinkList));
??????? temp->data=i;//交替指向添加元素
??????? temp->next=L->next;//鏈表循環(huán)賦值
??????? L->next=temp;
??????? i++;
??? }
??? printf("Created successfully\n");
}
//尾插法創(chuàng)建鏈表
int FootCreateList(LinkList *L,ElemType k){
??? //非法操作或創(chuàng)建失敗
??? if(k<0) return 0;
??? LinkList *temp,*LCopy;
??? LCopy=L;
??? int i=1;
??? while(i<=k){
??????? temp=(LinkList *)malloc(sizeof(LinkList));
??????? if(temp==NULL) return 0;
??????? temp->data=i;
??????? L->next=temp;
??????? L=L->next;//鏈表位置始終保持在最后
??????? i++;
??? }
??? L->next=LCopy->next;//尾結(jié)點連接頭結(jié)點后第一個元素結(jié)點
??? printf("Created successfully\n");
}
//打印操作
void PrintList(LinkList *L,ElemType k){
??? LinkList *temp=L;
??? temp=temp->next;//從頭結(jié)點指向首結(jié)點
??? for (int i = 0; i < k; ++i)
??? {
??????? printf("%d\n",temp->data);
??????? temp=temp->next;
??? }
??? printf("print successfully\n");
}
//遞歸調(diào)用，每隔m個刪除一個，直至所剩k人
ElemType DeleteElemList(LinkList *L,int m,int k,int *n){
??? int i=1;
??? //從j位往后數(shù)m-1位，將要刪除元素的前一位
??? for (; i <= m-1; ++i)
??? {??
??????? L=L->next;
??? }
??? // printf("所刪元素為:%d \n",L->next->data);//輸出目標元素
??? L->next=L->next->next;//跳過目標元素
??? (*n)=(*n)-1;//長度減1
??? //未達到k人時不斷遞歸調(diào)用
??? if (k<(*n)) DeleteElemList( L, m, k , n);
???
}
int main()
{
??? //n人，從j開始計數(shù)，第m個人使其出列，直至所剩k人
??? int n,m,j,k;
??? LinkList *L;//聲明一個指向單鏈表的帶頭指針L
??? L=(LinkList *)malloc(sizeof(LinkList));
??? InitList(L);
??? //插入n元素，即n人
??? printf("輸入n人\n");
??? scanf("%d",&n);
??? if (n<1){
??????? printf("非法輸入");
??????? return 0;
??? }
??? //為鏈表創(chuàng)建n結(jié)點
??? FootCreateList(L,n);
??? //打印
??? // PrintList(L,n);
??? printf("從j開始計數(shù)\n");
??? scanf("%d",&j);
??? if (j>n){
??????? printf("非法輸入");
??????? return 0;
??? }
??? printf("第m個人使其出列\(zhòng)n");
??? scanf("%d",&m);
??? if (m>=n){
??????? printf("非法輸入");
??????? return 0;
??? }
??? printf("直至所剩k人\n");
??? scanf("%d",&k);
??? if (k>=n){
??????? printf("非法輸入");
??????? return 0;
??? }
??? //調(diào)整正確位置到j(luò)位
??? for (int i = 0; i < j; ++i)
??? {??
??????? L=L->next;//此時temp指到目標位置
??? }
??? //開始操作
??? DeleteElemList(L,m-1,k,&n);
??? // printf("最后的n為%d\n",n);
??? printf("所剩元素為\n");
??? PrintList(L,n);
??? return 0;
}
到了這里，關(guān)于一、課程設(shè)計目的與任務(wù)《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計是為訓(xùn)練學(xué)生的數(shù)據(jù)組織能力和提高程序設(shè)計能力而設(shè)置的增強實踐能力的課程。目的：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程，旨在使學(xué)生學(xué)會分析研究數(shù)據(jù)對象的特性，學(xué)會數(shù)據(jù)的組織方法，以的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
