實踐教學
蘭州理工大學
計算機與通訊學院
2023年春季學期
演算法與資料結構課程設計
題目1： 跳馬問題
題目2： 約瑟夫問題
題目3： 最短字串
專業班級： 11級電腦科學與技術2班
姓名王軍
學號11240222
指導教師王燕
成績目錄
摘要 2
序言 3
第一章題目簡介 4
第二章分析需求 5
第三章資料型別 6
第四章各模組的流程圖及偽碼演算法 8
第五章函式的呼叫關係圖 12
第六章測試結果 14
原程式 22
設計總結 33
參考文獻 34
致謝 35
摘要本程式主要解決最短字串問題,跳馬問題,約瑟夫(joeph)問題。最短字串問題是從輸入中讀取字串，並按長度順序，最短字串優先的原則輸出它們。如果有若干字串具有相同的長度，就按字母順序輸出它們。
跳馬問題是要求在64個西洋棋格仔,任意位置放乙個馬,如何不重複地把格仔走完。約瑟夫（joeph）問題描述是：編號為1,2,…,n的n個人按順時針方向圍坐一圈，每人持有乙個密碼（正整數）。
一開始任選乙個正整數作為報數上限值m，從第乙個人開始按順時針方向自1開始順序報數，報到m時停止報數。報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下乙個人開始重新從1報數，如此下去，直至所有人全部出列為止。這些程式主要功能是加深我們對演算法與資料結構中儲存，線性表和棧的理解。
讓我們對演算法與資料結構有個更深刻的認識。
關鍵詞：最短字元跳馬約瑟夫
演算法與資料結構在電腦科學與技術中，尤其是在計算機軟體設計中有舉足輕重的重要作用。在幾乎所有的計算機軟體系統中，如作業系統、資料庫系統、編譯系統、計算機網路技術、軟體工程等都要用到演算法與資料結構的知識。演算法與資料結構已經成為電腦科學與技術專業和其他與軟體有關專業的重要的專業基礎課。
本文通過約瑟夫（joeph）問題，最短字串問題，跳馬問題加深我們對演算法與資料結構的認識及學習演算法與資料結構的重要性。本文通過這三個簡單程式介紹鏈式儲存中單鏈表迴圈以及線性表中棧的應用和陣列的應用。通過對跳馬問題研究，可以加深我們對棧中棧的初始化，入棧，出棧的理解。
知道棧在演算法與資料結構中的重要性。讓我們在學習演算法與資料結構時對棧有乙個清晰的認識，以便與為今後的軟體開發打好基礎。約瑟夫(joeph)問題採用單鏈表迴圈結構，表中所有結點被鏈在乙個環上。
因為從表中任何乙個結點出發均可訪問到表中的其他結點。約瑟夫（joeph）問題是單鏈表迴圈最好的展現。讓我們知道在資料處理過程中迴圈的重要性，在儲存過程中空間的節約有著重要作用。
最短字串問題採用陣列的方式建立起來的。
通過本文三個簡單而具有代表性的程式，讓我知道迴圈單鏈表，棧，陣列在演算法與資料結構重要性。也給我們在今後的學習中鋪平道路，了解在軟體開發中演算法設計是很重要的。本文只對這三種演算法加以說明和應用，在演算法與資料結構中對複雜的資料結構如二叉樹、圖、散結結構沒有加以說明和應用。
希望讀者在學習演算法與資料結構時對這些資料結構也要重視。為將來軟體開發打好基礎。本文在寫時由於時間緊迫，個人能力有限難免會有一些錯誤，真誠地希望讀者批評指正。
1. 約瑟夫（joeph）問題。是描述一種：
編號為1,2,…,n的n個人按順時針方向圍坐一圈，每人持有乙個密碼（正整數）。一開始任選乙個正整數作為報數上限值m，從第乙個人開始按順時針方向自1開始順序報數，報到m時停止報數。報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下乙個人開始重新從1報數，如此下去，直至所有人全部出列為止。
試設計乙個程式求出出列順序。
2. 最短字串問題。編寫乙個程式，從輸入中讀取字串，並按長度順序，最短字串優先的原則輸出它們。如果有若干字串具有相同的長度，就按字母順序輸出它們。
3. 跳馬問題。要求在64個西洋棋格仔,任意位置放乙個馬,如何不重複地把格仔走完。
1． 約瑟夫（joeph）問題：該問題適合採用迴圈單鏈表（為了便於操作，可使其不帶頭結點）儲存相關資料。問題求解時，首先從頭指標順序從1掃瞄到第 m 個結點，取其密碼作為新的報數上限 m，輸出其序號，刪除該結點，然後從其後繼結點重複上述動作，直到輸出 n 個結點。
2． 最短字串問題：該問題通過輸入一些字串，通過判斷字串的長短優先輸出最短的字串，如果長度相同則按字母順序輸出字串。該程式採用陣列的形式來實現該問題。
3． 跳馬問題：西洋棋中馬採用「日」字走法，對棋盤上任意乙個馬所在的結點，它所能走的結點在一步之內有八種情況，即假設馬所在的座標為（i，j），那麼它能走的八個座標分別為（i+1，j+2），（i+1，j-2），（i+2,j-1），（i+2,j+1），（i-2,j-1），（i-2,j+1），（i-1,j-2），（i-1,j+2），把這八個點個看做是（i，j）的領接點，以此類推每個結點都有鄰結點，所以可採用圖的深度遍歷，以馬所在的結點（i，j）為初始結點，對全圖進行深度遍歷，然後按照遍歷的順序輸出結點。
1.約瑟夫（joeph）問題
建立節點node
鍊錶都是由乙個個結點組成，由於結點的不同，組成的鍊錶也不同。
由於每乙個結點有乙個密碼和乙個序號，所以可以將結點結構體定義為
typedef struct jos
node;
2.最短字串問題
最短字串採用陣列的形式進行輸入和排序的，通過子函式input(char *str1)進行輸入的，通過子函式input(char *str2)對輸入的字串進行排序。
#define max 100預設最大字串個數
#define maxsize 256
int num全域性變數num表示輸入字串
3.跳馬問題
#define maxnum 8橫縱格數最大值
#define invaliddir - 1無路可走的情況
#define maxlen 64棋盤總格數
#define maxdir 8下一步可走的方向
typedef struct
horsepoint;
horsepoint chesspath[maxlen模擬路徑棧
int count入棧結點個數
int chessboard[maxnum][maxnum標誌棋盤陣列
1.約瑟夫（joeph）問題
1.1 約瑟夫迴圈流程圖
圖 1
1.2 偽碼演算法
建立單迴圈鍊錶
建立乙個空單迴圈鍊錶，雙向迴圈鍊錶和每個結點包括兩個域:元素域和指標域。形成單迴圈鍊錶的原理：
定義三個指標變數head，p, q三指標開始全部指向頭結點，在插入操作開始後，head不變仍指向頭結點，p指標在插入過程中始終指向新插入的節點，而q指標緊隨其後，用於將新插入的節點和前乙個節點連線起來，最後通過q指向頭指標head，來完成環的操作。
關鍵**實現如下：
p=(node *)malloc(sizeof(node));
q->link=p;
p->order=i+1;
p->mima=s[i+1];
q=p;
2.最短字串問題
2.1 字串的輸入**
通過建立陣列str1,當字串的格數小於巨集定義中 num 時，可以輸入一些字串。具體**如下：
int input(char *str1)
count++;
}puts("輸入完畢！");
return 1;
}2.2 字串的排序**
當輸入字串時，呼叫函式 sort() 進行排序，更具字串的長短進行排序。如果字串長度相同時，可以更具字母優先進行排序，具體**如下：
int sort(char *str2)
if(strlen(str2[j])==strlen(str2[i]))
if(strcmp(str2[j],str2[i])<0)
演算法與資料結構
演算法 是按部就班地解決某個問題的方法，是對特定問題求解步驟的一種描述。偽碼語言是一種包括高階程式語言的3種基本控制結構 順序 選擇和迴圈 和自然語言成分的 物件導向 的語言。演算法的特徵 1 可行性 一是演算法中的每個步驟必須是能實現的 二是演算法執行的結果要能達到預期的目的。2 確定性 演算法的...
資料結構與演算法
課程設計報告 目錄一 問題描述1 二 資料結構1 三 演算法設計思想及流程圖1 四 源程式2 五 測試情況6 參考文獻6 一 問題描述 計算表示式的值 問題描述 對於給定的乙個表示式，表示式中可以包括常數 算術執行符和括號，編寫程式計算表示式的值。基本要求 從鍵盤輸入乙個正確的中綴表示式，將中綴表示...
資料結構與演算法信
美國uiuc大學博士生梅俏竹 資料結構是美國所有一流計算機系的本科核心課程之一，上承計算引論與初級程式設計，下啟高階演算法和計算理論，向來是計算機本科教學的重中之重。我在北大上過的諸多本科基礎課中，無論從課程內容和老師教學下的功夫來看，張銘老師的 資料結構與演算法 課程都是首屈一指的。可以說，將北大...