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

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

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

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

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

文檔簡介

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

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

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

4、;一>： 6.3“哈夫曼樹”的建立及其應用　　一、設(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．需求分析　?。?）設(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)過的分支對應的0和1組成的序列便為該結(jié)點對應字符的哈夫曼編碼。　　二、概要設(shè)計　　1．主界面設(shè)計　　運行界面如圖1所示：　　圖1哈夫

7、曼編碼主菜單　　2．存儲結(jié)構(gòu)設(shè)計　　對于哈夫曼編碼問題，希望在構(gòu)造哈夫曼樹的同時能方便地實現(xiàn)從雙親結(jié)點到左右孩子結(jié)點的操作，在進行哈夫曼編碼時又要求能方便地實現(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)造步驟，在當前已構(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)系圖　　四、詳細設(shè)計　　1．數(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)主要子程序詳細設(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復制編碼（串）到HC　　}　　free(cd); //釋放工作空間　　for(i=1;i<=n;i++

33、)　　printf("<%2d>編碼:%s\n",HT[i].weight,HC[i]);　　}//HuffmanCoding　　五、測試分析　　根據(jù)設(shè)計要求中的問題描述分別輸入字符的個數(shù)和對應的權(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 哈夫曼編碼　　六、用戶手冊 　?。?）本程序執(zhí)行文件為“哈夫曼樹的建立及其應用.exe”。

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

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

39、程設(shè)計中曾遇到了不少問題，比如輸入整型變量的時候，沒有辦法限制其不能輸入字符型，還有類型必須前后匹配等等。使我明白了理論與實際相結(jié)合的重要性，使我更深刻地意識到：掌握了好的理論并不一定能馬上將其運用到自己的程序中，而只有通過不斷地學習和實踐，不斷地運用它，才能熟能生巧！　　八、程序清單　　#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復制編碼（串）到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è)表達式中允許有兩種括號：圓括號和方括號，其

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

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

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

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

78、;p>　　圖1 括號匹配的檢驗主菜單　　2．存儲結(jié)構(gòu)設(shè)計　　對于括號匹配的檢驗問題，希望在輸入一個括號序列后，程序能檢測出該括號序列是否匹配，則設(shè)置一個棧來實現(xià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)//進棧　　(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;　　四、詳細設(shè)計　　1．數(shù)據(jù)類型定義　　typedef struct{ 　　Elem *base; //棧底指針　　Elem *top; //棧頂指針 </p&g

88、t;　　int size; //當前已分配的存儲空間　　}SqStack;　　typedef int Status;　　2．系統(tǒng)主要子程序詳細設(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)//進棧　　{ </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、'進棧 　　case '[':Push(S,'[');　　break; //'['進棧　　case ')':{Pop(S,e); 　　if(e!='(')

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

100、;　　if(e!='[') 　　flag1=1; //出棧，判斷是否為[''，不是則用flag1標記為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”。　?。?）進入本程序之后，輸入要匹配的括號序列。　?。?）顯示“匹配”或“此串括號匹配不合法”。<

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

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

107、知識性。我將在以后的日子里繼續(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; //當前已分配的存儲空間　　}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)//進棧　　{ 　　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; //'('進棧 　　case '[':Push(S,'[');　　break; //'['進棧　　case ')&

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

121、　　case ']':{Pop(S,e);　　if(e!='[') 　　flag1=1; //出棧，判斷是否為[''，不是則用flag1標記為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)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載