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

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

已閱讀1頁，還剩23頁未讀，繼續(xù)免費閱讀

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

文檔簡介

1、　　電子與信息工程學(xué)院　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告　　( 2012——2013年度第一學(xué)期)　　課程名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 　　題目一：6.3“哈夫曼樹”的建立及其應(yīng)用

2、;　　題目二： 3.4.6括號匹配的檢驗 　　院系：計算機科學(xué)系 　　班級： 　　姓名： </p&g

3、t;　　學(xué) 號： 　　指導(dǎo)教師： 　　成績： 　　2012 年月日　　設(shè)計題目<

4、;一>： 6.3“哈夫曼樹”的建立及其應(yīng)用　　一、設(shè)計要求　　1．問題描述　　設(shè)有一段電文由字符集{A,B,C,D,E,F,G,H}組成，各字符在電文中出現(xiàn)的次數(shù)集為{5,29,7,8,14,23,3,11}，試設(shè)計各字符的哈

5、夫曼編碼。　　2．需求分析　　（1）設(shè)計哈夫曼樹。具體的構(gòu)造方法如下：以字符集{A,B,C,D,E,F,G,H}作為葉子結(jié)點，以各字符出現(xiàn)的次數(shù){5,29,7,8,14,23,3,11}作為各葉子結(jié)點的權(quán)值構(gòu)造一棵哈夫曼樹。　?。?）設(shè)計哈夫曼編碼。按照構(gòu)造出來的哈夫曼樹，規(guī)

6、定哈夫曼樹的左分支為0，右分支為1，則從根結(jié)點到每個葉子結(jié)點所經(jīng)過的分支對應(yīng)的0和1組成的序列便為該結(jié)點對應(yīng)字符的哈夫曼編碼。　　二、概要設(shè)計　　1．主界面設(shè)計　　運行界面如圖1所示：　　圖1哈夫

7、曼編碼主菜單　　2．存儲結(jié)構(gòu)設(shè)計　　對于哈夫曼編碼問題，希望在構(gòu)造哈夫曼樹的同時能方便地實現(xiàn)從雙親結(jié)點到左右孩子結(jié)點的操作，在進(jìn)行哈夫曼編碼時又要求能方便地實現(xiàn)從孩子結(jié)點到雙親結(jié)點的操作。因此，本程序選擇樹的雙親孩子表示法作為哈夫曼樹的存儲結(jié)構(gòu)，并加入了指示結(jié)點權(quán)值的信息。&

8、lt;b>　　3．系統(tǒng)功能設(shè)計　　本程序完成了從哈夫曼樹的構(gòu)造到實現(xiàn)并輸出哈夫曼編碼的過程，分別由兩個子程序完成，其設(shè)計如下：　?。?）選擇權(quán)值最小的樹。選擇權(quán)值最小的樹由函數(shù)Select（）實現(xiàn)。該功能按照哈夫曼樹的構(gòu)造步驟，在當(dāng)前已構(gòu)成的n(n>=2)棵二叉樹的集合中選取兩棵根結(jié)點權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二

9、叉樹。　?。?）哈夫曼編碼。哈夫曼編碼由函數(shù)HuffmanCoding( )實現(xiàn)。該功能首先調(diào)用函數(shù)Select（）實現(xiàn)哈夫曼樹的構(gòu)造，然后從葉子到根逆向根據(jù)哈夫曼編碼的要求，一次求出每個字符的哈夫曼編碼。　　三、模塊設(shè)計　　1．模塊設(shè)計

10、;　　本程序包含3個模塊：主程序模塊、哈夫曼編碼模塊和選擇模塊。其調(diào)用關(guān)系如圖2所示。　　圖2 模塊調(diào)用示意圖　　2．系統(tǒng)子程序及功能設(shè)計　　本程序共設(shè)置3個子程序，各子程序的函數(shù)名及功能說明如下。　　(1)void Select

11、(HuffmanTree &HT,int m,int *s1,int *s2)　　//選擇權(quán)值最小的兩個結(jié)點　　(2)void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)　　//構(gòu)造哈夫曼編碼&

12、lt;/b>　　(3)void main( ) //主函數(shù)。輸入結(jié)點個數(shù)及權(quán)值，調(diào)用哈夫曼編碼模塊函數(shù)　　3．函數(shù)主要調(diào)用關(guān)系圖 　　本程序3個子程序之間的主要調(diào)用關(guān)系如圖3所示。 　　圖中數(shù)字是各函數(shù)的編號

13、 　　圖3系統(tǒng)函數(shù)調(diào)用關(guān)系圖　　四、詳細(xì)設(shè)計　　1．?dāng)?shù)據(jù)類型定義　　typedef struct　　{<

14、/p>　　unsigned int weight; //用來存放各個結(jié)點的權(quán)值　　unsigned int parent, lchild, rchild; //指向雙親、孩子結(jié)點的指針　　}HTNode, *HuffmanTree; //

15、動態(tài)分配數(shù)組存儲哈夫曼樹　　typedef char * * HuffmanCode; //動態(tài)分配數(shù)組存儲哈夫曼編碼表　　2．系統(tǒng)主要子程序詳細(xì)設(shè)計　　哈夫曼編碼模塊設(shè)計分兩步：首先構(gòu)造哈夫曼樹，然后完成哈夫曼編碼。　　void Huffma

16、nCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)　　{//w存放n個字符的權(quán)值（均>0)，構(gòu)造哈夫曼樹HT并求出n個字符的哈夫曼編碼HC　　int i,j,m,s1,s2,start;　　char *cd;</

17、b>　　unsigned int c,f;　　if (n<=1) return;　　m = 2 * n - 1;　　HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); //0號單元未用

18、　　for (i=1;i<=n;i++) //葉子結(jié)點初始化并放入1-n號單元　　{　　HT[i].weight=w[i];　　HT[i].parent=0;　　HT[i].lchi

19、ld=0;　　HT[i].rchild=0;　　}　　for (i=n+1; i<=m;i++) //非葉子結(jié)點初始化　　{　　HT

20、[i].weight=0;　　HT[i].parent=0;　　HT[i].lchild=0;　　HT[i].rchild=0;　　}　　printf("\n哈夫曼樹的構(gòu)造過程如下所

21、示:\n");　　printf("HT初態(tài):\n 結(jié)點 weight parent lchild rchild");　　for (i=1;i<=m;i++) //完成構(gòu)造哈夫曼樹算法的第1個步驟　　printf("\n%4d%8d%8d%8d

22、%8d",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);　　printf(" 按任意鍵，繼續(xù) ...");　　getch();　　//創(chuàng)建哈夫曼樹HT<

23、;p>　　for (i=n+1;i<=m;i++)　　{　　Select (HT,i-1,&s1,&s2); 　　//在HT[1..i-1]中選擇parent為0且weight最小的兩個結(jié)點　　HT[s

24、1].parent=i;HT[s2].parent=i;　　HT[i].lchild=s1;HT[i].rchild=s2;　　//將選取根結(jié)點權(quán)值最小的樹作為左右子樹　　HT[i].weight=HT[s1].weight+HT[s2].weight;　　//置新二叉樹

25、的根結(jié)點權(quán)值為其左、右子樹根結(jié)點之和　　printf("\nselect:s1=%d s2=%d\n",s1,s2);　　//根結(jié)點權(quán)值最小的樹在HT中的位置　　printf(" 結(jié)點 weight parent lchild rchild");

26、　　for (j=1;j<=i;j++)　　//輸出選取根結(jié)點權(quán)值最小樹的過程　　printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,HT[j].parent,HT

27、 [j].lchild,HT[j].rchild);　　printf(" 按任意鍵，繼續(xù) ...");　　getch();　　}　　printf(&q

28、uot;\n%d個字符的哈夫曼編碼如下:\n",n);　　//從葉子到根逆向求每個字符的哈夫曼編碼　　HC=(HuffmanCode)malloc((n+1)*sizeof(char *));//分配n個編碼的頭指針　　cd = (char * )malloc(n*sizeof(char));

29、 //分配求編碼的工作空間　　cd[n-1] = '\0'; //編碼結(jié)束符　　for (i=1;i<=n;i++) //逐個字符求哈夫曼編碼　　{<

30、/b>　　start =n-1; //編碼結(jié)束符位置　　for (c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) 　　//葉子結(jié)點到根逆向求編碼

31、if (HT[f].lchild==c) cd[--start] ='0';　　else cd[--start] = '1';　　HC[i] = (char *)malloc((n-start)*sizeof(char));　　//為第i個字符編碼分配空間

32、　　strcpy(HC[i], &cd[start]); //從cd復(fù)制編碼（串）到HC　　}　　free(cd); //釋放工作空間　　for(i=1;i<=n;i++

33、)　　printf("<%2d>編碼:%s\n",HT[i].weight,HC[i]);　　}//HuffmanCoding　　五、測試分析　　根據(jù)設(shè)計要求中的問題描述分別輸入字符的個數(shù)和對應(yīng)的權(quán)值，

34、程序運行得到圖4的開始界面。　　圖4哈夫曼編碼程序開始界面　　構(gòu)造哈夫曼樹的過程如圖（5~ 12）所示。　　圖5　　圖6　　圖7<

35、/b>　　圖8　　圖9　　圖10　　圖11　　圖12&

36、lt;/b>　　構(gòu)造哈夫曼編碼如圖13所示。　　圖13 哈夫曼編碼　　六、用戶手冊 　　（1）本程序執(zhí)行文件為“哈夫曼樹的建立及其應(yīng)用.exe”。

37、?。?）進(jìn)入本程序之后，分別輸入哈夫曼編碼字符的個數(shù)和對應(yīng)的權(quán)值。　　（3）隨即顯示哈夫曼樹的構(gòu)造過程，最終顯示出對應(yīng)權(quán)值的哈夫曼編碼。　　七、調(diào)試報告　　此次課程設(shè)計主要是了解哈夫曼樹的設(shè)計，并學(xué)會哈夫曼編碼的設(shè)計。通過這次課程設(shè)計，我學(xué)到了課本上以外的許多知識，學(xué)會了樹相

38、關(guān)的基礎(chǔ)知識，受益匪淺。　　《數(shù)據(jù)結(jié)構(gòu)》是一門實踐性較強的課程，為了學(xué)好這門課程，必須在掌握理論知識的同時，加強上機實踐。其次是，根據(jù)實際問題的需要，對各個方面的優(yōu)缺點加以綜合平衡，從中選擇比較適宜的實現(xiàn)方法。比如在選擇數(shù)據(jù)結(jié)構(gòu)的時候，就要求從時間性能和空間性能去考慮，從而使得能編寫出更加實用和高效的代碼，而要做到這點，就要求對知識點很熟悉。　　在這次課

39、程設(shè)計中曾遇到了不少問題，比如輸入整型變量的時候，沒有辦法限制其不能輸入字符型，還有類型必須前后匹配等等。使我明白了理論與實際相結(jié)合的重要性，使我更深刻地意識到：掌握了好的理論并不一定能馬上將其運用到自己的程序中，而只有通過不斷地學(xué)習(xí)和實踐，不斷地運用它，才能熟能生巧！　　八、程序清單　　#include <s

40、tdio.h>　　#include <malloc.h>　　#include <string.h>　　#include <conio.h>　　typedef struct

41、　　{　　unsigned int weight; //用來存放各個結(jié)點的權(quán)值　　unsigned int parent,lchild,rchild; //指向雙親、孩子結(jié)點的指針　　}HTNode, *HuffmanTree;

42、 //動態(tài)分配數(shù)組存儲哈夫曼樹　　typedef char * * HuffmanCode; //動態(tài)分配數(shù)組存儲哈夫曼編碼表　　//1.選擇權(quán)值最小的兩個結(jié)點　　void Select(HuffmanTree &HT,int m,int *s1,int *s2)

43、　　{　　int i,min;　　for(i=1;i<=m;i++) //在HT[1..i-1]中選擇parent為0且weight最小的兩個結(jié)點　　{　　if(

44、HT[i].parent==0)　　{　　min = i;i=m+1;　　}　　}　　for(i=1;i<=m

45、;i++) //parent為0且weight最小的兩個結(jié)點，第一個序號為s1　　{　　if(HT[i].parent == 0)　　{　　if(HT[i].weight < HT[mi

46、n].weight)　　min = i;　　}　　}　　*s1 = min;　　for(i=1; i<=m;i

47、++) //在HT[1..i-1]中選擇parent為0且weight最小的兩個結(jié)點　　{　　if(HT[i].parent == 0 &&i!=(*s1))　　{　　min

48、 = i;i = m+1;　　}　　}　　for(i=1;i<=m;i++) //parent為0且weight最小的兩個結(jié)點，第二個序號為s2　　{</b&g

49、t;　　if(HT[i].parent == 0 &&i!=(*s1))　　{　　if(HT[i].weight < HT[min].weight)　　min = i;<

50、;/p>　　}　　}　　*s2 = min;　　}//Select　　//2.構(gòu)造哈夫曼編碼<p&g

51、t;　　void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)　　{//w存放n個字符的權(quán)值（均>0)，構(gòu)造哈夫曼樹HT并求出n個字符的哈夫曼編碼HC　　int i,j,m,s1,s2,start;

52、　char *cd;　　unsigned int c,f;　　if (n<=1) return;　　m = 2 * n - 1;　　HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); //0

53、號單元未用　　for (i=1;i<=n;i++) //葉子結(jié)點初始化并放入1-n號單元　　{　　HT[i].weight=w[i];　　HT[i].parent=0;<p&

54、gt;　　HT[i].lchild=0;　　HT[i].rchild=0;　　}　　for (i=n+1; i<=m;i++) //非葉子結(jié)點初始化　　{

55、　　HT[i].weight=0;　　HT[i].parent=0;　　HT[i].lchild=0;　　HT[i].rchild=0;　　}　　printf("

56、;\n哈夫曼樹的構(gòu)造過程如下所示:\n");　　printf("HT初態(tài):\n 結(jié)點 weight parent lchild rchild");　　for (i=1;i<=m;i++) //完成構(gòu)造哈夫曼樹算法的第1個步驟　　printf("

57、;\n%4d%8d%8d%8d%8d",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);　　printf(" 按任意鍵，繼續(xù) ...");　　getch();　　//創(chuàng)建哈夫曼樹HT

58、　　for (i=n+1;i<=m;i++)　　{　　Select (HT,i-1,&s1,&s2); 　　//在HT[1..i-1]中選擇parent為0且weight最小的兩個結(jié)點

59、　　HT[s1].parent=i;HT[s2].parent=i;　　HT[i].lchild=s1;HT[i].rchild=s2;　　//將選取根結(jié)點權(quán)值最小的樹作為左右子樹　　HT[i].weight=HT[s1].weight+HT[s2].weight;<

60、;p>　　//置新二叉樹的根結(jié)點權(quán)值為其左、右子樹根結(jié)點之和　　printf("\nselect:s1=%d s2=%d\n",s1,s2);　　//根結(jié)點權(quán)值最小的樹在HT中的位置　　printf(" 結(jié)點 weight parent lchild rchild&qu

61、ot;);　　for (j=1;j<=i;j++)　　//輸出選取根結(jié)點權(quán)值最小樹的過程　　printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,HT[j].parent,HT

62、 [j].lchild,HT[j].rchild);　　printf(" 按任意鍵，繼續(xù) ...");　　getch();　　}<p

63、>　　printf("\n%d個字符的哈夫曼編碼如下:\n",n);　　//從葉子到根逆向求每個字符的哈夫曼編碼　　HC=(HuffmanCode)malloc((n+1)*sizeof(char *));//分配n個編碼的頭指針　　cd = (char * )malloc(n*size

64、of(char)); //分配求編碼的工作空間　　cd[n-1] = '\0'; //編碼結(jié)束符　　for (i=1;i<=n;i++) //逐個字符求哈夫曼編碼<b&g

65、t;　　{　　start =n-1; //編碼結(jié)束符位置　　for (c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) 　　//葉子結(jié)點到根逆向求編碼<p

66、>　　if (HT[f].lchild==c) cd[--start] ='0';　　else cd[--start] = '1';　　HC[i] = (char *)malloc((n-start)*sizeof(char));　　//為第i個字符編碼分配空間</p

67、>　　strcpy(HC[i], &cd[start]); //從cd復(fù)制編碼（串）到HC　　}　　free(cd); //釋放工作空間　　for(i=1;i<=n;

68、i++)　　printf("<%2d>編碼:%s\n",HT[i].weight,HC[i]);　　}//HuffmanCoding　　//3.主函數(shù)　　void main()&

69、lt;p>　　{　　HuffmanTree myHuffmanTree;　　HuffmanCode myHuffmanCode;　　int *w,i;

70、;　　int n, wei; //編碼個數(shù)及權(quán)值　　printf("請輸入需要哈夫曼編碼的字符個數(shù):");　　scanf("%d",&n);　　w=(int *)malloc((n+1

71、) *sizeof(int));　　for(i=1;i<=n;i++)　　{　　printf("請輸入第%d字符的權(quán)值:",i);　　fflush(stdin);

72、scanf("%d",&wei);　　w[i]=wei;　　}　　HuffmanCoding(myHuffmanTree,myHuffmanCode,w,n);<

73、b>　　}　　設(shè)計題目<二>： 3.4.6括號匹配的檢驗 　　一、設(shè)計要求　　1．問題描述　　假設(shè)表達(dá)式中允許有兩種括號：圓括號和方括號，其

74、嵌套的順序隨意，即(()[ ])或[([ ] [ ])]等為正確格式，[( ])或((( ]均為不正確的格式。檢驗括號是否匹配的方法可用“期待的緊迫程度”這個概念來描述。例如：考慮下列的括號序列：　　[　(　[　]　[　]　)　]　　1　2　3　4　5　6　7　8　　當(dāng)計算機接受了第1個括號以后，他期待著與其匹配

75、的第8個括號的出現(xiàn)，然而等來的卻是第2個括號，此時第1個括號“[”只能暫時靠邊，而迫切等待與第2個括號相匹配的第7個括號“）”的出現(xiàn)，類似的，因只等來了第3個括號“[”，此時，其期待的緊迫程度較第2個括號更緊迫，則第2個括號只能靠邊，讓位于第3個括號，顯然第3個括號的期待緊迫程度高于第2個括號，而第2個括號的期待緊迫程度高于第1個括號；在接受了第4個括號之后，第3個括號的期待得到了滿足，消解之后，第2個括號的期待匹配就成了最急迫的任務(wù)

76、了，…… ，依次類推。可見這個處理過程正好和棧的特點相吻合。　　2．需求分析　　輸入的形式和輸入值的范圍：從鍵盤上以字符串的形式輸入括號序列。　　輸出的形式：括號匹配或是括號不匹配。　　程序所能達(dá)到的功能：檢驗括號是否匹配。</

77、p>　　測試數(shù)據(jù)：輸入（[ ]（）），結(jié)果“匹配”，　　輸入 [（（）]，結(jié)果“此串括號匹配不合法”　　二、概要設(shè)計　　1．主界面設(shè)計　　運行界面如圖1所示：<

78、;p>　　圖1 括號匹配的檢驗主菜單　　2．存儲結(jié)構(gòu)設(shè)計　　對于括號匹配的檢驗問題，希望在輸入一個括號序列后，程序能檢測出該括號序列是否匹配，則設(shè)置一個棧來實現(xiàn)。當(dāng)遇到 ( 或 [ 時進(jìn)棧，遇到 ) 或 ] 時出棧進(jìn)行匹配檢驗，如果出現(xiàn)不匹配的情況立即結(jié)束，否則繼續(xù)取下一個字符。如果沒有遇到不匹配的情況，最后判

79、斷棧是否為空，棧為空，括號匹配,否則不匹配。　　3．系統(tǒng)功能設(shè)計　　本程序完成了輸入括號序列后檢驗括號序列是否匹配，定義棧結(jié)構(gòu)和判斷棧的情況有以下說明：　　typedef struct{ }定義棧結(jié)構(gòu)體　　Status CreatS

80、tack(SqStack &S)　　初始條件：棧指針已存在　　操作結(jié)果：定義空棧并分配存儲空間，成功返回ok　　Status StackEmpty(SqStack S)　　初始條件：棧已存在<p&

81、gt;　　操作結(jié)果：判斷是否為空，是返回ok　　Status Push(SqStack &S,Elem e)　　初始條件：棧已存在，e已知　　操作結(jié)果：將e壓入棧中，成功返回ok　　Status Pop(SqStack &S,Elem &e)<

82、;/p>　　初始條件：棧非空，棧頂元素等于e　　操作結(jié)果：棧頂元素出棧　　Status Bracket(SqStack &S,char *str)　　初始條件：空棧已存在，括號串非空　　操作結(jié)果：輸出括號串是否匹配

83、　　void main()　　操作結(jié)果：在屏幕上顯示操作菜單　　三、模塊設(shè)計　　1．模塊設(shè)計 　　本程序包含2個模塊：主程序模塊和棧操作模塊。其調(diào)用關(guān)系如圖2所示。</

84、p>　　圖2 模塊調(diào)用示意圖　　2．系統(tǒng)子程序及功能設(shè)計　　本程序共設(shè)置6個子程序，各子程序的函數(shù)名及功能說明如下。　　(1)Status CreatStack(SqStack &S)//創(chuàng)建空堆棧,棧頂指針和棧底指針相等時,棧為空

85、　(2)Status StackEmpty(SqStack S)//堆棧是否為空　　(3)Status Push(SqStack &S,Elem e)//進(jìn)棧　　(4)Status Pop(SqStack &S,Elem &e)//出棧　　(5)Status Bracket(SqStack

86、 &S,char *str)//檢驗括號匹配　　(6)void main( ) //主函數(shù)。輸入括號序列，調(diào)用棧操作模塊函數(shù)　　3．函數(shù)主要調(diào)用關(guān)系圖　　本程序6個子程序之間的主要調(diào)用關(guān)系如圖3所示。　　圖3 系統(tǒng)函數(shù)調(diào)用關(guān)系圖</p&

87、gt;　　四、詳細(xì)設(shè)計　　1．?dāng)?shù)據(jù)類型定義　　typedef struct{ 　　Elem *base; //棧底指針　　Elem *top; //棧頂指針 </p&g

88、t;　　int size; //當(dāng)前已分配的存儲空間　　}SqStack;　　typedef int Status;　　2．系統(tǒng)主要子程序詳細(xì)設(shè)計　　Status CreatStack(SqStack &

89、S)//創(chuàng)建空堆棧,棧頂指針和棧底指針相等時,棧為空　　{ 　　S.base=(Elem *)malloc(STACK_SIZE*sizeof(Elem)); 　　S.top=S.base; S.size=STACK_SIZE; return OK;&

90、lt;p>　　} //棧頂指針和棧底指針相等,創(chuàng)建空堆棧　　Status StackEmpty(SqStack S) //堆棧是否為空　　{ 　　if(S.top!=S.base) 　　return ER

91、ROR; //棧頂指針和棧底指針不相等，則返回ERROR　　return OK; 　　}　　Status Push(SqStack &S,Elem e)//進(jìn)棧　　{ </b

92、>　　if(S.top-S.base>=S.size)　　{ //棧滿,追加存儲空間 　　S.base=(Elem *)realloc(S.base,(S.size+STACK_INC)*sizeof(Elem));　　S.top=S.base+S.size

93、; S.size+=STACK_INC;　　} 　　*S.top=e; //將e賦給棧頂指針　　S.top+=1; //棧頂指針向上移加1　　return OK;}

94、;　　Status Pop(SqStack &S,Elem &e)//出棧　　{ 　　if(S.top==S.base) 　　return ERROR; //判斷棧是否為空，空則返回ERROR　　S.

95、top-=1; //否則棧頂指針下移減1　　e=*S.top; //將站頂元素賦給e　　return OK;　　}　　Status Bracket(SqStack &S,char *

96、str)//檢驗括號匹配　　{ 　　int i=0,flag1=0,flag2;　　Elem e; 　　while(str[i]!='\0') //括號序列不為空</p

97、>　　{ 　　switch(str[i])　　{ 　　case '(':Push(S,'(');　　break; //'(

98、'進(jìn)棧 　　case '[':Push(S,'[');　　break; //'['進(jìn)棧　　case ')':{Pop(S,e); 　　if(e!='(')

99、　　flag1=1; //出棧，判斷是否為'('，不是則用flag1標(biāo)記為1　　break;　　} 　　case ']':{Pop(S,e);

100、;　　if(e!='[') 　　flag1=1; //出棧，判斷是否為[''，不是則用flag1標(biāo)記為1　　break;　　} 　　default: brea

101、k; 　　} 　　if(flag1) 　　break; //出現(xiàn)不匹配，立即結(jié)束循環(huán) 　　i++; 　　} &l

102、t;/p>　　flag2=StackEmpty(S); //flag2判斷堆棧是否為空 　　if(!flag1 && flag2) 　　printf("匹配\n");　　else <

103、p>　　printf("此串括號匹配不合法\n");　　return OK;　　}　　五、測試分析　　程序的測試分析如圖4所示。

104、　　圖4 程序運行圖　　六、用戶手冊 　　（1）本程序執(zhí)行文件為“括號匹配的檢驗.exe”。　?。?）進(jìn)入本程序之后，輸入要匹配的括號序列。　?。?）顯示“匹配”或“此串括號匹配不合法”。<

105、/p>　　七、調(diào)試報告　　以前做實驗題目的時候總是感覺很難，因為根本就不知道從哪里開始。這次課程設(shè)計讓我對編程有了新的認(rèn)識。　　拿到題目的時候也是很困惑，后來看了很多有關(guān)的例子，仔細(xì)看了書上關(guān)于棧的算法的知識，覺得就是上課講到的一些內(nèi)容，不是題目難，是自己先把自己嚇住了。

106、;　　后來，參照書上的諸多例子，一個模塊一個模塊的編寫，調(diào)試，一個功能一個功能去完善。發(fā)現(xiàn)越做越順利，加上以前的實驗中對于改錯的經(jīng)驗積累和幾個學(xué)得不錯的同學(xué)的幫助，我的程序中的錯誤也一個一個的順利解決。　　再后來，等我的程序完全做好以后，我竟然可以獨立的幫同學(xué)修改一些以前根本不知所以然的錯誤，其實，從這次實驗中我認(rèn)識到，我要學(xué)習(xí)的還有很多，編程有很多的樂趣也有很多的技巧性和

107、知識性。我將在以后的日子里繼續(xù)認(rèn)真的學(xué)習(xí)知識，積累經(jīng)驗，讓自己的編程能力提高。　　八、程序清單　　#include <stdio.h>　　#include <malloc.h>　　#define OK 1<

108、;/p>　　#define ERROR 0 //定義順序堆棧　　#define STACK_SIZE 100 //存儲空間初始分配量　　#define STACK_INC 10 //存儲空間分配增量　　typedef char Elem;

109、typedef struct{ 　　Elem *base; //棧底指針　　Elem *top; //棧頂指針 　　int size; //當(dāng)前已分配的存儲空間　　}SqStack;　　typ

110、edef int Status;　　Status CreatStack(SqStack &S)//創(chuàng)建空堆棧,棧頂指針和棧底指針相等時,棧為空　　{ 　　S.base=(Elem *)malloc(STACK_SIZE*sizeof(Elem));

111、;　　S.top=S.base; S.size=STACK_SIZE; return OK;　　} //棧頂指針和棧底指針相等,創(chuàng)建空堆棧　　Status StackEmpty(SqStack S) //堆棧是否為空　　{ <

112、;/p>　　if(S.top!=S.base) 　　return ERROR; //棧頂指針和棧底指針不相等，則返回ERROR　　return OK; 　　}　　Status P

113、ush(SqStack &S,Elem e)//進(jìn)棧　　{ 　　if(S.top-S.base>=S.size)　　{ //棧滿,追加存儲空間 　　S.base=(Elem *)realloc(S.base,(S.si

114、ze+STACK_INC)*sizeof(Elem));　　S.top=S.base+S.size; S.size+=STACK_INC;　　} 　　*S.top=e; //將e賦給棧頂指針　　S.top+=1;

115、 //棧頂指針向上移加1　　return OK;}　　Status Pop(SqStack &S,Elem &e)//出棧　　{ 　　if(S.top==S.base) <

116、p>　　return ERROR; //判斷棧是否為空，空則返回ERROR　　S.top-=1; //否則棧頂指針下移減1　　e=*S.top; //將站頂元素賦給e　　return OK;

117、}　　Status Bracket(SqStack &S,char *str)//檢驗括號匹配　　{ 　　int i=0,flag1=0,flag2;　　Elem e;

118、;　　while(str[i]!='\0') //括號序列不為空　　{ 　　switch(str[i])　　{ 　　case

119、9;(':Push(S,'(');　　break; //'('進(jìn)棧 　　case '[':Push(S,'[');　　break; //'['進(jìn)棧　　case ')&

120、#39;:{Pop(S,e); 　　if(e!='(') 　　flag1=1; //出棧，判斷是否為'('，不是則用flag1標(biāo)記為1　　break;　　}

121、　　case ']':{Pop(S,e);　　if(e!='[') 　　flag1=1; //出棧，判斷是否為[''，不是則用flag1標(biāo)記為1　　break;

122、　　} 　　default: break; 　　} 　　if(flag1) 　　break; //出現(xiàn)不匹配，立即結(jié)束循環(huán) &l

123、t;b>　　i++; 　　} 　　flag2=StackEmpty(S); //flag2判斷堆棧是否為空 　　if(!flag1 && flag2) 　　printf("匹配\n&

124、quot;);　　else 　　printf("此串括號匹配不合法\n");　　return OK;　　}　　void main(){

125、 //主函數(shù)　　char temp,flag='y'; 　　while(flag=='y'){　　char str[255];　　SqStack S;　　printf("請輸入要匹配

126、的括號序列:\n");　　scanf("%s",str); 　　scanf("%c",&temp); //接受輸入的回車鍵　　CreatStack(S); 　　Bracket(S,str);

127、　　printf("您想再試一次嗎(按y繼續(xù)): ");　　scanf("%c",&flag);　　printf("\n"); 　　} 　　prin

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

溫馨提示

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

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載