數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

1、 <<數(shù)據(jù)結(jié)構(gòu)>> 課 程 設(shè) 計班級:111004姓名:董麗美學(xué)號:111004122指導(dǎo)教師:史延新完成日期:2013 _07 _10題目一:約瑟夫環(huán)問題【問題描述】約瑟夫（Joseph）問題的一種描述是：編號為1,2，,n 的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m 的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人開始重新從1報數(shù)，如此下去，直至所有人全部出列為止。試設(shè)計一個程序求出列順序?！净疽蟆坷脝蜗蜓h(huán)鏈表存儲結(jié)構(gòu)模擬此

2、過程，按照出列的順序打印出各人的編號?！緶y試數(shù)據(jù)】m的初值為20；n=7,7個人的密碼依次為：3,1,7,2，4,8,4，首先m值為6（正確的出列順序應(yīng)為：6,1,4,7,2,3,5）一 .需求分析1用單循環(huán)鏈表存儲并遍歷及刪除節(jié)點的方法，計算并輸出約瑟夫環(huán)的問題。 2環(huán)中總?cè)藬?shù)和節(jié)點信息由用戶輸入，且均為正整數(shù)。 3在窗口界面輸出出列順序的編號。 二概要設(shè)計1.設(shè)定鏈表的抽象數(shù)據(jù)類型定義：ADT List數(shù)據(jù)對象：D=a(i)|a(i)Elemset,i=1,2,n,n>=0數(shù)據(jù)關(guān)系：R1=<a(i-1),a(i)>|a(i-1),a(i)D,

3、i=2,n基本操作：InitList(&L)操作結(jié)果：構(gòu)造一個空的線性表ListInsert(&L,i,e)初始條件：線性表L已經(jīng)存在。操作結(jié)果：在L中第i個位置之前插入新的數(shù)據(jù)元素 e,L的長度增加1。ListDelete(&L,i,&e)初始條件：線性表L已經(jīng)存在且非空，1<=i<=ListLength(L)。操作結(jié)果：刪除L的第i個數(shù)據(jù)元素，并用e返回其值，L的長度減1 。  2.算法的基本思想： 根據(jù)題目要求，采用單循環(huán)線性表的基本操作來實現(xiàn)約瑟夫環(huán)問題。首先根據(jù)所給信息生成鏈表節(jié)點并插入，根據(jù)節(jié)點記錄密碼及其所

4、在鏈表中的順序，由給出的初始訪問值進(jìn)行遍歷，當(dāng)變量i增量等于所給的值（即關(guān)鍵字）時，指針?biāo)傅墓?jié)點處的順序值即為所需輸出的順序號。每輸出一次順序號，將順序號所在的節(jié)點刪除，當(dāng)最后單循環(huán)鏈表的頭指針為空時，跳出循環(huán)。完成出列順序的打印。3.程序的流程:  程序由三個模塊組成：  1）輸入模塊：完成兩個正整數(shù)的輸入，存入變量n和m 中。  初始值:n=7;m=62）計算模塊：用循環(huán)的方式設(shè)計算法計算出依次輸出的序列數(shù)。 3）輸出模塊：屏幕上顯示依次被淘汰的人的編號。三詳細(xì)設(shè)計1.不帶頭結(jié)點單循環(huán)鏈表節(jié)點結(jié)構(gòu)體定義：ty

5、pedef struct NODEint code;/密碼int num; /在鏈表中順序號NODE *pnext;/節(jié)點指針NODE;typedef struct CIRCLE_LINK/循環(huán)鏈表NODE *front;NODE *rear;CIRCLE_LINK;2.源程序代碼：(運行環(huán)境：VC+ 6.0)#include "stdafx.h"#include<stdlib.h>#include<string.h>typedef struct NODEint code;int num;NODE *pnext;NODE;typedef struct

6、 CIRCLE_LINKNODE *front;NODE *rear;CIRCLE_LINK;bool init_circle_link(CIRCLE_LINK *link)*link=(CIRCLE_LINK *)malloc(sizeof(CIRCLE_LINK);if(NULL=*link)return false;(*link)->front=NULL;(*link)->rear=NULL;return true;bool insert_circle_link_end(CIRCLE_LINK *link,int code,int num) NODE *curt=NULL;

7、curt=(NODE*)malloc(sizeof(NODE); if(NULL=curt) return false; curt->num=num;curt->code=code;if(NULL=link->front)link->front=curt;link->rear=link->front;link->rear->pnext=link->front;elsecurt->pnext=link->rear->pnext;link->rear->pnext=curt;link->rear=curt;r

8、eturn true;void delete_node(CIRCLE_LINK *link,NODE *pcurt)NODE *ptem=link->front;NODE *prear=link->rear;while(true)if(link->front=link->rear&&link->front=pcurt)/刪除鏈表中唯一的一個節(jié)點link->front=NULL;link->rear=NULL;break;if(link->front=pcurt)/刪除頭結(jié)點link->front=link->front

9、->pnext;link->rear->pnext=link->front;free(pcurt);pcurt=NULL;break;ptem=ptem->pnext;if(ptem->pnext=pcurt&&pcurt->pnext=link->front)/刪除尾節(jié)點ptem->pnext=link->front;link->rear=ptem;free(pcurt);pcurt=NULL;break;if(ptem->pnext=pcurt)/刪除中間節(jié)點ptem->pnext=pcurt-&

10、gt;pnext;free(pcurt);pcurt=NULL;break;void find_key(CIRCLE_LINK *link,int key)NODE *pcurt=link->front;NODE *ptem=NULL;int i=1;printf("輸出序列為:n");while(link->front!=NULL)for(;i<key;)i+;pcurt=pcurt->pnext;i=1;printf("%dn",pcurt->num);key=pcurt->code;ptem=pcurt;pcur

11、t=pcurt->pnext;delete_node( link,ptem);int main(int argc, char* argv)int i=0;int n=0;int num=1;int code=0;int key=0;CIRCLE_LINK *link=NULL;init_circle_link(&link);printf("請輸入總?cè)藬?shù):");scanf("%d",&n);getchar();for(i=0;i<n;i+)printf("請輸入第%d個人的密碼:",num);scanf(&q

12、uot;%d",&code);getchar();insert_circle_link_end(link,code,num);num+;printf("請輸入初值（關(guān)鍵字）:");scanf("%d",&key);printf(".n");getchar();find_key(link,key); return 0;3. 輸出結(jié)果及輸出界面：四.調(diào)試分析1.調(diào)試過程中出現(xiàn)scanf語句后，不加getchar();使緩沖區(qū)出空格未被讀取，不能繼續(xù)調(diào)試及運行。經(jīng)分析并修改后正確。2.對循環(huán)的退出條件。五.用戶使用

13、說明1.用戶可根據(jù)需求進(jìn)行客戶端窗口的數(shù)據(jù)信息的輸入，從而的到所需求的輸出結(jié)果。六.測試結(jié)果1.根據(jù)所給測試數(shù)據(jù)可知，測試結(jié)果正確，及所編寫程序代碼正確。七.參考文獻(xiàn)1.數(shù)據(jù)結(jié)構(gòu)C語言版 嚴(yán)蔚敏 吳偉民 清華大學(xué)出版社2.數(shù)據(jù)結(jié)構(gòu)題集C語言版 嚴(yán)蔚敏 吳偉民 清華大學(xué)出版社3.C語言程序設(shè)計 譚浩強 清華大學(xué)出版社題目二:圖遍歷的演示【問題描述】很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。試寫一個程序，演示在連通的無向圖上訪問全部結(jié)點的操作?！净疽蟆恳脏徑佣嘀乇頌榇鎯Y(jié)構(gòu)，實現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結(jié)點為起點，分別輸出每種遍歷下的結(jié)點訪問序列和相應(yīng)生成樹的邊

14、集?！緶y試數(shù)據(jù)】交通網(wǎng)例圖所示：一 .需求分析根據(jù)節(jié)點數(shù)組進(jìn)行邊信息存儲，進(jìn)行兩種方式的遍歷。二概要設(shè)計1.圖的存儲 本課題要求采取鄰接表的存儲結(jié)構(gòu)。鄰接表是一種鏈?zhǔn)降拇鎯Y(jié)構(gòu)，在鄰接表中，對圖中每個頂點建立一個單鏈表，第i個單鏈表中的結(jié)點表示依附于頂點Vi的邊（對有向圖是以頂點Vi為尾的?。?。每個結(jié)點由3個域組成，其中鄰接點域（adjvex）指示與頂點Vi鄰接的點在圖中的位置，鏈域（nextarc）指示下一條2.邊或弧的結(jié)點；數(shù)據(jù)域（info）存儲和邊或弧相關(guān)的信息，如權(quán)值等。 所以一開始必須先定義鄰接表的邊結(jié)點類型以及鄰接表類型，并對鄰接表進(jìn)行初始化，然后根據(jù)所輸入的相

15、關(guān)信息，包括圖的頂點數(shù)、邊數(shù)、是否為有向，以及各條邊的起點與終點序號，建立圖的鄰接表。此時要分兩種情況：有向圖與無向圖。對于無向圖，一條邊的兩的個頂點，互為鄰接點，所以在存儲時，應(yīng)向起點的單鏈表表頭插入一邊結(jié)點，即終點。同時將終點的單鏈表表頭插入一邊結(jié)點，即起點。對于有向圖，只能向起點的單鏈表的表頭插入一個邊結(jié)點，即終點。但不能反過來。至于鄰接表的輸出，由于不了解C+中的繪圖操作，故采用for語句輸出各結(jié)點，并配合一些符號完成鄰接表的輸出。 圖的遍歷 3.圖的深度優(yōu)先遍歷 假設(shè)初始狀態(tài)是圖中所有頂點未曾被訪問，深度優(yōu)先遍歷可以從圖的初始點出發(fā)，訪問初始點，然后依次

16、從v未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點都被訪問到；若此時仍有頂點未被訪問到，則從另一個未被訪問的頂點出發(fā)，重復(fù)上述過程，直至所有點都被訪問到為止。這是一個遞歸的過程。所以在實現(xiàn)深度優(yōu)先遍歷的過程中必須遞歸調(diào)用深度優(yōu)先搜索函數(shù)。而且在深度優(yōu)先搜索函數(shù)中必須設(shè)一標(biāo)志數(shù)組以標(biāo)記結(jié)點是否被訪問。 具體過程應(yīng)為：先訪問初始點Vi，并標(biāo)志其已被訪問。此時定義一指向邊結(jié)點的指針p，并建立一個while（）循環(huán)，以指針?biāo)笇ο蟛粸榭諡榭刂茥l件，當(dāng)Vi的鄰接點未被訪問時，遞歸調(diào)用深度優(yōu)先遍歷函數(shù)訪問之。然后將p指針指向下一個邊結(jié)點。這樣就可以完成圖的深度優(yōu)先遍歷了。&

17、#160;4.圖的廣度優(yōu)先遍歷 廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷的過程。假設(shè)從圖中某頂點v出發(fā)，在訪問了v之后訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點的鄰接點”被訪問，直到圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中尙有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復(fù)上述過程，直到圖中所有頂點都被訪問到為止。換句話說，廣度優(yōu)先搜索遍歷圖的過程是以v為起始點，由近及遠(yuǎn)，依次訪問和v有路徑相通且路徑長度為1，2，的頂點。 所以要實現(xiàn)算法必須先建立一個元素類型為整形的空隊列，并定義隊首與隊尾指針，同時也要定義一個標(biāo)志數(shù)組以

18、標(biāo)記結(jié)點是否被訪問。同樣，也是從初始點出發(fā)開始訪問，訪問初始點，標(biāo)志其已被訪問，并將其入隊。當(dāng)隊列非空時進(jìn)行循環(huán)處理。當(dāng)結(jié)點被訪問時對其進(jìn)行標(biāo)志，并入隊列。通過while（）循環(huán)，并以是否被訪問為控制條件，訪問所有結(jié)點，完成圖的廣度優(yōu)先遍歷。結(jié)點坐標(biāo)信息：struct node int vertex; /輸入頂點 struct node *nextnode; /指向下一節(jié)點; typedef struct node *graph; /圖形的結(jié)構(gòu)新形態(tài)struct node head61; /圖形頂點結(jié)構(gòu)數(shù)組  三詳細(xì)設(shè)計程序主體部分主要包括兩大部分，一是遍歷算法部分；另一部分是對演示

19、圖的處理。遍歷算法部分主要包括了，鄰接多重表構(gòu)造的無向圖的初始化、深度遍歷和廣度遍歷1、深度遍歷 函數(shù)名稱： void dfs(int current)  函數(shù)功能：實現(xiàn)一張無向圖從一個指定結(jié)點的深度搜索遍歷，并輸出結(jié)點序號函數(shù)參數(shù)： int v 開始的結(jié)點 具體代碼：2、廣度遍歷 函數(shù)名稱：void bfs(int current)   函數(shù)功能：實現(xiàn)一張無向圖從一個指定結(jié)點的廣度度搜索遍歷，并輸出結(jié)點序號； 函數(shù)參數(shù)： int v開始的結(jié)點，

20、返回參數(shù)為void 具體代碼：3、圖的創(chuàng)建和初始化 函數(shù)名稱：void creategraph(int *node,int num) 函數(shù)功能：創(chuàng)建一張固定結(jié)點和邊數(shù)的無向圖，邊與結(jié)點的關(guān)系是從文件中讀取 函數(shù)參數(shù)：形參為空，返回也為void 具體代碼：void creategraph(int *node,int num) graph newnode; /新頂點指標(biāo) graph ptr; int from; /邊線的起點 int to; /邊線的終點 int i; for ( i = 0; i < num; i+ ) /讀取邊線的回路 f

21、rom = nodei*2; /邊線的起點 to = nodei*2+1; /邊線的終點 newnode = ( graph ) malloc(sizeof(struct node); newnode->vertex = to; /建立頂點內(nèi)容 newnode->nextnode = NULL; /設(shè)定指標(biāo)初值 ptr = &(headfrom); /頂點位置 while ( ptr->nextnode != NULL ) /遍歷至鏈表尾 ptr = ptr->nextnode; /下一個頂點 ptr->nextnode = newnode; /插入結(jié)尾

22、4、初始化頂點坐標(biāo) 數(shù)組名稱：int node602 數(shù)組功能：此為頂點坐標(biāo)，主要用來讀取存儲在文件中的各個頂點坐標(biāo)信息 具體代碼：int node602 = 1, 10, 10, 1, 2, 10, 10, 2, 2, 3, 3, 2, 3, 4, 4, 3, 3, 12, 12, 3, 4, 13, 13, 4,4, 5, 5, 4, 5, 6, 6, 5,5, 7, 7, 5, 7, 8, 8, 7, 9, 10, 10, 9, 10, 11, 11, 10, 11, 14, 14, 11, 11, 12, 12, 11, 12, 15, 15, 12, 1

23、2, 13, 13, 12, 13, 16, 16, 13, 14, 17, 17, 14, 14, 18, 18, 14, 15, 19, 19, 15, 16, 20, 20, 16, 17, 18, 18, 17, 18, 23, 23, 18, 18, 19, 19, 18, 19, 23, 23, 19, 19, 24, 24, 19, 19, 20, 20, 19, 20, 21, 21, 20, 22, 23, 23, 22, 24, 25, 25,24 ;源程序代碼：#include "stdafx.h"#include <stdio.h>#in

24、clude <stdlib.h>#include<malloc.h> #include<conio.h> #include<string.h> #include<malloc.h> #define MAXQUEUE 70 /最大頂點個數(shù) struct node int vertex; /輸入頂點 struct node *nextnode; /指向下一節(jié)點; typedef struct node *graph; /圖形的結(jié)構(gòu)新形態(tài)struct node head61; /圖形頂點結(jié)構(gòu)數(shù)組 int visited61; /遍歷記錄數(shù)組

25、int queueMAXQUEUE; /佇列的最大容量int front = -1; /佇列的前端int rear = -1; /佇列的后端void creategraph(int *node,int num) graph newnode; /新頂點指標(biāo) graph ptr; int from; /邊線的起點 int to; /邊線的終點 int i; for ( i = 0; i < num; i+ ) /讀取邊線的回路 from = nodei*2; /邊線的起點 to = nodei*2+1; /邊線的終點 newnode = ( graph ) malloc(sizeof(str

26、uct node); newnode->vertex = to; /建立頂點內(nèi)容 newnode->nextnode = NULL; /設(shè)定指標(biāo)初值 ptr = &(headfrom); /頂點位置 while ( ptr->nextnode != NULL ) /遍歷至鏈表尾 ptr = ptr->nextnode; /下一個頂點 ptr->nextnode = newnode; /插入結(jié)尾 int enqueue(int value) if ( rear >= MAXQUEUE ) /檢查佇列是否全滿 return -1; /無法存入 rear+

27、; /后端指標(biāo)往前移 queuerear = value; /存入佇列 return 0; int dequeue() if ( front = rear ) /檢查佇列是否為空 return -1; / 無法取出 front+; / 前端指標(biāo)往前移 return queuefront; /佇列取出 /* 廣度優(yōu)先 */ void bfs(int current) graph ptr; enqueue(current); /將頂點存入佇列 visitedcurrent = 1; /記錄已遍歷過 printf("%d ",current); / 印出遍歷頂點值 while (

28、 front != rear ) /佇列是否為空 current = dequeue(); /將頂點從佇列中取出 ptr = headcurrent.nextnode; /頂點位置 while ( ptr != NULL ) /遍歷至鏈表尾 if ( visitedptr->vertex = 0 ) /如果沒遍歷過 enqueue(ptr->vertex); /遞回遍歷呼叫 visitedptr->vertex = 1; /記錄已遍歷過 printf("%d ",ptr->vertex); ptr = ptr->nextnode; /下一個頂點

29、 /* 深度優(yōu)先 */void dfs(int current) graph ptr; visitedcurrent = 1; /記錄已遍歷過 printf("%d ",current); /印出遍歷頂點值 ptr = headcurrent.nextnode; /頂點位置 while ( ptr != NULL ) /遍歷至鏈表尾 if ( visitedptr->vertex = 0 ) /如果沒遍歷過 dfs(ptr->vertex); /遞回遍歷呼叫 ptr = ptr->nextnode; /下一個頂點 /* 將遍歷內(nèi)容印出. */int mai

30、n(int argc, char* argv) /clrscr(); system("cls"); while(1) char c,a; graph ptr; int i; int node602 = 1, 10, 10, 1, 2, 10, 10, 2, 2, 3, 3, 2, 3, 4, 4, 3, 3, 12, 12, 3, 4, 13, 13, 4,4, 5, 5, 4, 5, 6, 6, 5,5, 7, 7, 5, 7, 8, 8, 7, 9, 10, 10, 9, 10, 11, 11, 10, 11, 14, 14, 11, 11, 12, 12, 11, 1

31、2, 15, 15, 12, 12, 13, 13, 12, 13, 16, 16, 13, 14, 17, 17, 14, 14, 18, 18, 14, 15, 19, 19, 15, 16, 20, 20, 16, 17, 18, 18, 17, 18, 23, 23, 18, 18, 19, 19, 18, 19, 23, 23, 19, 19, 24, 24, 19, 19, 20, 20, 19, 20, 21, 21, 20, 22, 23, 23, 22, 24, 25, 25,24 ; system("cls"); printf("nnn&quo

32、t;); printf("/* funcotion：Traversing Graph algorithm display */n"); printf(" Depth_First Search and Breadth_First Search? Y/N?n"); c=getchar(); if(c!='y'&&'Y') exit(0); system("cls"); printf("nn"); printf("please notice the followi

33、ng cities code:nn"); printf("1:烏魯木齊; 2:呼和浩特; 3:北京; 4:天津; 5:沈陽; n"); printf("6:大連; 7:長春; 8:哈爾濱; 9:西寧; 10:蘭州;n"); printf("11:西安; 12:鄭州; 13:徐州; 14:成都; 15:武漢; n"); printf("16:上海; 17:昆明; 18:貴陽; 19:株州; 20:南昌;n"); printf("21:福州; 22:南寧; 23:柳州; 24:廣州; 25:深圳.n

34、"); getchar(); for (i=1;i<=25;i+ ) headi.vertex=i; headi.nextnode=NULL; visitedi=0; / creategraph(node,60); creategraph(&node00,60); printf("圖 形 的 鄰 接 鏈 表 內(nèi) 容:n"); for (i=1;i<=25;i+) if(i%3=0)printf("n"); printf("頂點%d=>",headi.vertex); ptr=headi.nextno

35、de; while(ptr!=NULL) printf("%d ",ptr->vertex); ptr=ptr->nextnode; printf("nn"); printf("please you choose your operationn"); printf("1、if Breadth_Searching ,please input :'g'或'G'n"); printf("2、if Depth_Searching ,please input:'s

36、'或'S'n"); c=getchar(); switch(c) case'g': case'G': printf("nplesae input the first vex:n"); scanf("%d",&i); printf("nn"); printf("please notice all cities code:nn"); printf("1:烏魯木齊; 2:呼和浩特; 3:北京; 4:天津; 5:沈陽; n"); printf("6:大連; 7:長春; 8:哈爾濱; 9:西寧; 10:蘭州;n")