數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--約瑟夫環(huán)

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁數(shù)：14 大?。?.95MB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

已閱讀1頁，還剩13頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、　　題目一　　題目：約瑟夫環(huán)　　問題描述：　　編號(hào)是 1，2，……,n 的 n 個(gè)人按照順時(shí)針方向圍坐一圈，每個(gè)人持有一個(gè) 密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值 m,從

2、第一個(gè)人開始順時(shí)針方向自 1 開始順序報(bào)數(shù)，報(bào)到 m 時(shí)停止報(bào)數(shù)。報(bào) m 的人出列，將他的密碼作為新的 m 值，從他在順時(shí)針方向的下一個(gè)人開始重新從 1 報(bào)數(shù)，如此下去，直到所有人全部出列為止。設(shè)計(jì)一個(gè)程序來求出出列順序。 　　基本要求：　　利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個(gè)人的編號(hào)。

3、此題所用的循環(huán)鏈表中不需要“頭結(jié)點(diǎn)”，請(qǐng)注意空表和非空表的界限。　　測試數(shù)據(jù)：　　m 的初值為 20，n=7 ,7 個(gè)人的密碼依次為 3，1，7，2，4，8，4，首先 m的值為6 則正確的輸出應(yīng)該是6,1，4,7,2,3,5。　　要求：&

4、lt;/p>　　輸入數(shù)據(jù)：首先輸入待處理人員數(shù)及他們的密碼，然后輸入 m 的初值，建立單循環(huán)鏈表。 　　輸出形式：　　建立一個(gè)輸出函數(shù)，將正確的出列序列輸出。　　正文：

5、　　一：需求分析　　(1)輸入形式:　　首先輸入待處理人員數(shù)及他們的密碼，然后輸入 m 的初值，建立單循環(huán)鏈表。　　此程序設(shè)n<=30，所用的循環(huán)鏈表中不需要“頭結(jié)點(diǎn)”，請(qǐng)注意空表和非空表的界限。<p&

6、gt;　　輸出形式：　　建立一個(gè)輸出函數(shù)，將正確的出列序列輸出。　　程序所能得到的功能：　　提供用戶從鍵盤輸入，Joseph約瑟夫環(huán)的必要數(shù)據(jù)，并顯示出列順序。　　測試數(shù)據(jù)：

7、　　輸入207　　3 1 7 2 4 8 4　　輸出　　6 1 4 7 2 3 5　　二、概要設(shè)

8、計(jì)　　以單向循環(huán)鏈表實(shí)現(xiàn)該結(jié)構(gòu)。　　1. 抽象數(shù)據(jù)類型的定義為：　　ADT LNode　　{　　數(shù)據(jù)對(duì)象：D={ai | ai∈Cha

9、rSet，i= 1，2，…，n，n≥0}　　數(shù)據(jù)關(guān)系：R1={< ai-1 ，ai > | ai ∈D， I=2，…，n}　　基本操作：　　InitList(&L)　　操作結(jié)果：構(gòu)造一個(gè)最大長度ms內(nèi)容為空的有序表

10、L。　　ClearList(&L)　　初始條件：線性表L已經(jīng)存在。　　操作結(jié)果：將L重置為空表。　　EmptyList(L)　　初始條件：線性表L已經(jīng)存在。　　操作結(jié)果：若L為空表

11、返回TRUE，否則返回FALSE。　　ListLength(L)　　初始條件：線性表L已經(jīng)存在。　　操作結(jié)果：返回L中數(shù)據(jù)元素個(gè)數(shù)。　　GetElem(L, pos, &e)　　初始條件：線性表L已經(jīng)存在，1≤i≤List

12、Length(L)。　　操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值。　　LocateElem(L, e)　　初始條件：線性表L已經(jīng)存在。　　操作結(jié)果：返回L中第1個(gè)與e相同的元素的位序。若不存在返回0。　　ListInsert (L

13、, i, e)　　初始條件：線性表L已經(jīng)存在。　　操作結(jié)果：在L中的第i個(gè)元素的位置之前插入新元素 e,L的長度加1。ListDelete(L, pos, e)　　初始條件：線性表L已經(jīng)存在，1≤i≤ListLength(L)。　　操作結(jié)果：刪除L的第i個(gè)數(shù)據(jù)元素，并用e

14、返回其值，L的長度減1。　　ListTraverse(L)　　初始條件：線性表L已經(jīng)存在。　　操作結(jié)果：依次對(duì)L的每個(gè)數(shù)據(jù)元素進(jìn)行訪問。　　}ADT SqList　　本程序包含以下模塊：&

15、lt;b>　?。?）主程序模塊：　　void main()　　{　　初始化；　　輸入數(shù)據(jù)；

16、　　執(zhí)行功能；　　顯示結(jié)果；　　}　?。?）各功能模塊——實(shí)現(xiàn)順序表的各項(xiàng)功能。　　各模塊的調(diào)用關(guān)系：

17、;　　↓　　三、詳細(xì)設(shè)計(jì)　　#include<stdio.h>　　#include<stdlib.h>　　typedef struct Node<

18、;/p>　　{　　int data;　　int password;　　struct Node *next;　　}Node, *LinkList;

19、　　void CreatLinkList(LinkList *L, int n)　　{　　Node *p, *q;　　int i;　　(*L) = (LinkList)mallo

20、c(sizeof(Node));　　if ((*L) == NULL)　　{　　printf("memory allocation failed, goodbye");　　exit(1);<

21、/b>　　}　　p = (*L);　　printf("請(qǐng)輸入第1個(gè)人的密碼:");　　scanf("%d",&(p->password)

22、);　　p->data = 1;　　for (i = 2; i <= n; i++)　　{　　q = (LinkList)malloc(sizeof(Node));　　if (q

23、== NULL)　　{　　printf("memory allocation failed, goodbye");　　exit(1);　　}

24、;　　printf("\n請(qǐng)輸入第%d個(gè)人的密碼:",i);　　scanf("%d",&(q->password));　　q->data = i;　　p->next = q;<

25、p>　　p = q;　　}　　p->next = (*L);}　　void Output(LinkList *L, int m, int n)　　{

26、;　　Node *p, *q;　　int i = 1;　　p = (*L);　　printf("輸出出對(duì)序列:");　　while (n)</b&g

27、t;　　{　　while (i != m)　　{　　q = p;　　p = p->next;

28、;　　i++;　　}　　printf("%-3d",p->data);　　m = p->password;　　q->next = p-&

29、gt;next;　　free(p);　　p = q->next;　　i = 1;　　n--;

30、　　}　　printf("\n");　　}　　int main(void)　　{　　LinkList L;<

31、/p>　　int n, m;　　printf("請(qǐng)輸入人數(shù):");　　scanf("%d", &n);　　getchar();　　CreatLinkList(

32、&L, n);　　printf("請(qǐng)輸入第一個(gè)報(bào)號(hào)數(shù):");　　scanf("%d",&m);　　Output(&L, m, n);　　system("pause");

33、　　return 0;　　}　　四、調(diào)試分析　　程序的編寫和調(diào)試基本正常。　　遇到的問題主要是：指針的指向的邊界問題。

34、;　　本實(shí)驗(yàn)采用數(shù)據(jù)抽象的與模塊化程序設(shè)計(jì)方法。思路清晰，實(shí)現(xiàn)時(shí)調(diào)試順利，各模塊具有很好的可重用性，得到了一次良好的程序設(shè)　　計(jì)訓(xùn)練。　　五、用戶使用說明　　如何使用，詳細(xì)步驟&

35、lt;/p>　　根據(jù)提示輸入人數(shù)和每個(gè)人的信息　　調(diào)試結(jié)果　　七：參考文獻(xiàn)　　1. 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu). 清華大學(xué)出版社, 2005.11　　2. 譚浩

36、強(qiáng). C語言程序設(shè)計(jì). 清華大學(xué)出版社, 2005.11　　3. 范輝. Visual C++程序設(shè)計(jì). 高等教育出版社　　題目二　　題目：哈夫曼編碼器　　問題描述：</b

37、>　　利用哈夫曼編碼進(jìn)行信息通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。試為這樣的信息傳輸寫一個(gè)哈夫曼編/譯碼系統(tǒng)。 　　基本要求：　　1）I：初始化（I

38、nitialization）。從終端讀入字符集大小 n，以及 n 個(gè)字符和 n 個(gè)權(quán) 值，建立哈夫曼樹，并將它存于文件 hfmTree 中。輸出哈夫曼樹，及各字符對(duì)應(yīng)的編碼。 　　2）E：編碼（Encoding）與譯碼（Decoding）。編碼（Encoding）。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件 htmTree 中讀入），對(duì)文件 ToBeTran 中的正文進(jìn)行編碼，然后將

39、結(jié)果存入文件 CodeFile 中。　　3）D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件 CodeFile 中的代碼進(jìn)行譯碼，結(jié)果存入文件 TextFile 中。 　　4）P：印代碼文件（Print）。將文件 CodeFile 以緊湊格式顯示在終端上，每行 50 個(gè)代碼。同時(shí)將此字符形式的編碼寫入文件 CodePrint 中。 <

40、;/p>　　5）T：印哈夫曼樹（Tree Printing）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件 TreePrint 中。 　　測試數(shù)據(jù)：　　(1) 利用教科書例6-2中的數(shù)據(jù)調(diào)試程序。<p

41、>　　(2) 用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。　　正文：　　需求分析　　輸入形式:&l

42、t;/p>　　程序的輸入，包含輸入的數(shù)據(jù)格式和說明: there are three students(char 型) 　　輸出形式：　　程序輸出的形式：1)統(tǒng)計(jì)字符出現(xiàn)次數(shù)并輸出 ;2) 根據(jù)字符出現(xiàn)次數(shù)求出哈夫曼編碼并輸出（根據(jù)算法差異得到的編碼可能不同，但應(yīng)具有兩個(gè)特征，一是編碼長

43、度應(yīng)與表中相同，二是編碼應(yīng)該是前綴編碼）;3) 以樹的形式輸出哈夫曼樹 .　　程序所能達(dá)到的功能：　　1）I：初始化（Initialization）。從終端讀入字符集大小 n，以及 n 個(gè)字符和 n 個(gè)權(quán) 值，建立哈夫曼樹，并將它存于文件 hfmTree 中。輸出哈夫曼樹，及各字符對(duì)應(yīng)的編碼。 2）W：輸入（Input）。從終端讀入需要編碼的字符串

44、s，將字符串 s 存入文件 Tobetran.txt 中。 3）E：編碼（Encoding）與譯碼（Decoding）。編碼（Encoding）。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件 htmTree 中讀入），對(duì)文件 ToBeTran 中的正文進(jìn)行編碼，然后將結(jié)果存入文件 CodeFile 中。譯碼（Decoding）。利用已建好的哈夫曼樹將文件 CodeFile 中的代碼進(jìn)行譯碼，結(jié)果存入文件 TextFile

45、中。印代碼文件（Print）。將文件 CodeFile 以緊湊格式顯示在終端上，每行 50 個(gè)代碼。同時(shí)將此字符形式的編碼寫入文件 CodePrint 中。 4）T：印哈夫曼樹（Tree Printing）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫　　測試數(shù)據(jù)：

46、;　　概要設(shè)計(jì)　　ADT {　　數(shù)據(jù)對(duì)象V: V是具有不同權(quán)值的字符集。　　基本操作P:　　InitCode(HTCode *Hr,int &n)&l

47、t;/p>　　初始化：建立Hr　　操作結(jié)果：存儲(chǔ)n個(gè)編碼字符、權(quán)值。　　Select(Huffmantree &Ht,int end,int *s1,int *s2)　　初始化：HT為建好的哈夫曼樹，end為開始查找的位置，s1,s2為最小

48、的兩個(gè)數(shù)。　　操作結(jié)果：從剩下的數(shù)種尋找到兩個(gè)最小的數(shù)，返回其值。　　InitHfmtree(Huffmantree &Ht,HTCode Hr[],int &n)　　初始化：建立哈夫曼樹Ht　　操作結(jié)果：對(duì)傳入的字符進(jìn)行編碼存入Hr中

49、　　Encoding(HTCode *Hr,int n)　　初始化：Hr已經(jīng)存儲(chǔ)編碼、字符　　操作結(jié)果：從Hr中獲取字符以及編碼進(jìn)行輸出　　Decoding(HTCode *Hr,int n)　　初始化：Hr已經(jīng)存儲(chǔ)編碼、字符

50、　　操作結(jié)果：從Hr中獲取編碼的字符進(jìn)行輸出　　TreePrint(Huffmantree &Ht,HTCode Hr[],int n)　　初始化：哈夫曼樹Ht，存儲(chǔ)信息Hr　　操作結(jié)果：打印哈夫曼樹的各個(gè)結(jié)點(diǎn)　　}</b

51、>　　詳細(xì)設(shè)計(jì)　　#include <dos.h>　　#include <conio.h>　　#include <stdio.h>　　#include

52、 <stdlib.h>　　#include <string.h>　　typedef struct　　{　　float weight; //結(jié)點(diǎn)權(quán)值　　unsigned

53、int parent,lchild,rchild; //結(jié)點(diǎn)的父指針，左右孩子指針　　}HTNode,*HuffmanTree; //動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹　　typedef char **HuffmanCode; //動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表　　void CreateHuffmanTree(Huffman

54、Tree &,float*,int ); //生成哈夫曼樹　　void HuffmanCoding(HuffmanTree,HuffmanCode &,int ); //對(duì)哈夫曼樹進(jìn)行編碼　　void PrintHuffmanCode(HuffmanCode,float*,int); //顯示哈夫曼編碼<p&

55、gt;　　void Select(HuffmanTree,int,int&,int&); //在數(shù)組中尋找權(quán)值最小的兩個(gè)結(jié)點(diǎn)　　void main()　　{　　HuffmanTree HT; //哈夫曼樹HT　　Huf

56、fmanCode HC; //哈夫曼編碼表HC　　int n,i; //n是哈夫曼樹葉子結(jié)點(diǎn)數(shù)　　float *w; //w存放葉子結(jié)點(diǎn)權(quán)值　　char j='y';　　while(j!='N'&&j!='n'

57、;)　　{　　printf("請(qǐng)輸入字符數(shù)目:");　　scanf("%d",&n); //輸入字符數(shù)目　　if(n<=1) </p&g

58、t;　　{　　printf("該數(shù)不合理!\n");continue;　　}　　w=(float*)malloc(n*sizeof(unsigned int)); //開辟空間存放權(quán)值</p

59、>　　printf("請(qǐng)輸入各字符出現(xiàn)的次數(shù)/權(quán)值:\n");　　for(i=0;i<n;i++) scanf("%f",&w[i]); //輸入各字符出現(xiàn)的次數(shù)/權(quán)值　　CreateHuffmanTree(HT,w,n); //生成哈夫曼樹<

60、p>　　HuffmanCoding(HT,HC,n); //進(jìn)行哈夫曼編碼　　PrintHuffmanCode(HC,w,n); //顯示哈夫曼編碼　　printf("哈夫曼樹構(gòu)造完畢!");　　scanf(" %c",&j);<

61、p>　　}　　}　　void CreateHuffmanTree(HuffmanTree &HT,float *w,int n)　　{//w存放n個(gè)結(jié)點(diǎn)的權(quán)值，將構(gòu)造一棵哈夫曼樹HT

62、　　int i,m;　　int s1,s2;　　HuffmanTree p;　　if(n<=1) return;　　m=2*n-1; //n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹，有2*n-1個(gè)結(jié)點(diǎn)　　H

63、T=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //開辟2*n各結(jié)點(diǎn)空間　　for(p=HT+1,i=1;i<=n;++i,++p,++w) //進(jìn)行初始化　　{　　p->weight=*w;<

64、;p>　　p->parent=0;　　p->lchild=0;　　p->rchild=0;　　}　　for(;i<=m;++i,++p)　　{&

65、lt;/b>　　p->weight=0;　　p->parent=0;　　p->lchild=0;　　p->rchild=0;　　}<

66、p>　　for(i=n+1;i<=m;++i) //建哈夫曼樹　　{　　Select(HT,i-1,s1,s2); 　　//從HT[1...i-1]中選擇parent為0且weight最小的兩個(gè)結(jié)點(diǎn)，其序號(hào)分別為s1和s2<p&g

67、t;　　HT[s1].parent=i; HT[s2].parent=i; //修改s1和s2結(jié)點(diǎn)的父指針parent　　HT[i].lchild=s1; HT[i].rchild=s2; //修改i結(jié)點(diǎn)的左右孩子指針　　HT[i].weight=HT[s1].weight+HT[s2].weight; //修改權(quán)值<p&g

68、t;　　}　　}　　void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n)　　{//將有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹HT進(jìn)行編碼，所編的碼存放在HC中&

69、lt;p>　　//方法是從葉子到根逆向求每個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼　　int i,c,f,start;　　char *cd;　　HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); //分配n個(gè)編碼的頭指針向量

70、　　cd=(char *)malloc(n*sizeof(char)); //開辟一個(gè)求編碼的工作空間　　cd[n-1]='\0'; //編碼結(jié)束符　　for(i=1;i<=n;++i) //逐個(gè)地求哈夫曼編碼　　{

71、　　start=n-1; //編碼結(jié)束位置　　for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) //從葉子到根逆向求編碼　　if(HT[f].lchild==c) cd[--start]='0'; //若是左孩子編為'0'<p

72、>　　else cd[--start]='1'; //若是右孩子編為'1' 　　HC[i]=(char *)malloc((n-start)*sizeof(char)); //為第i個(gè)編碼分配空間　　strcpy(HC[i],&cd[start]); //將編碼從cd復(fù)制到HC中&

73、lt;p>　　}　　free(cd); //釋放工作空間　　}　　void PrintHuffmanCode(HuffmanCode HC,float *w,int n)　　{//顯示有n個(gè)

74、葉子結(jié)點(diǎn)的哈夫曼樹的編碼表　　int i;　　printf("HuffmanCode is :\n");　　for(i=1;i<=n;i++)　　{

75、　　printf(" %3d---",w[i-1])　　puts(HC[i]);　　}　　printf("\n");　　}</p&

76、gt;　　void Select(HuffmanTree HT,int t,int&s1,int&s2)　　{//在HT[1...t]中選擇parent不為0且權(quán)值最小的兩個(gè)結(jié)點(diǎn)，其序號(hào)分別為s1和s2 　　int i,m,n;　　m=n=10000; </p&

77、gt;　　for(i=1;i<=t;i++)　　{　　if(HT[i].parent==0&&(HT[i].weight<m||HT[i].weight<n))　　if(m<n)

78、;　　{　　n=HT[i].weight;s2=i;　　}　　else 　　{

79、　　m=HT[i].weight;s1=i;　　}　　}　　if(s1>s2) //s1放較小的序號(hào)　　{&l

80、t;/p>　　i=s1;s1=s2;s2=i;　　}　　}　　調(diào)試分析　　（1）．問題 1：輸入數(shù)據(jù)以存入文件的功能總是出現(xiàn)錯(cuò)誤文

81、檔。解決辦法：將文件有關(guān)程序全部刪除，重新編寫。 　?。?）．問題 2:有時(shí)程序運(yùn)行錯(cuò)誤，是因?yàn)樯偌恿死ㄌ?hào)造成的。解決辦法：仔細(xì)檢查程序。 　?。?）．問題 3：在主函數(shù)中調(diào)用各函數(shù)時(shí)，機(jī)器總有認(rèn)為是語法錯(cuò)誤。解決辦法:仔細(xì)檢查，發(fā)現(xiàn)是漏寫了函數(shù)類型，對(duì)函數(shù)聲明應(yīng)與函數(shù)定義的類型一致。 　　用

82、戶使用說明　　請(qǐng)根據(jù)提示一次輸入字符數(shù)目和個(gè)字符數(shù)出現(xiàn)的次數(shù)/權(quán)值，最終得到輸出結(jié)果正如測試結(jié)果里面所示。　　測試結(jié)果　　七、參考文獻(xiàn)　　1. 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)

眾賞文庫> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--約瑟夫環(huán)

文檔簡介

溫馨提示

最新文檔

評(píng)論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--約瑟夫環(huán)

文檔簡介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載