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

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

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

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

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

文檔簡(jiǎn)介

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

2、;　　題目二： 3.4.6括號(hào)匹配的檢驗(yàn) 　　院系：計(jì)算機(jī)科學(xué)系 　　班級(jí)： 　　姓名： </p&g

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

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

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

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

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

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

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

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

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

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

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

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

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

16、nCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)　　{//w存放n個(gè)字符的權(quán)值（均>0)，構(gòu)造哈夫曼樹HT并求出n個(gè)字符的哈夫曼編碼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號(hào)單元未用

18、　　for (i=1;i<=n;i++) //葉子結(jié)點(diǎn)初始化并放入1-n號(hào)單元　　{　　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é)點(diǎn)初始化　　{　　HT

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

21、示:\n");　　printf("HT初態(tài):\n 結(jié)點(diǎn) weight parent lchild rchild");　　for (i=1;i<=m;i++) //完成構(gòu)造哈夫曼樹算法的第1個(gè)步驟　　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最小的兩個(gè)結(jié)點(diǎn)　　HT[s

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

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

26、　　for (j=1;j<=i;j++)　　//輸出選取根結(jié)點(diǎn)權(quán)值最小樹的過(guò)程　　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個(gè)字符的哈夫曼編碼如下:\n",n);　　//從葉子到根逆向求每個(gè)字符的哈夫曼編碼　　HC=(HuffmanCode)malloc((n+1)*sizeof(char *));//分配n個(gè)編碼的頭指針　　cd = (char * )malloc(n*sizeof(char));

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

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

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

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　　五、測(cè)試分析　　根據(jù)設(shè)計(jì)要求中的問(wèn)題描述分別輸入字符的個(gè)數(shù)和對(duì)應(yīng)的權(quán)值，

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

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

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

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

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

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

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

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

42、 //動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹　　typedef char * * HuffmanCode; //動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表　　//1.選擇權(quán)值最小的兩個(gè)結(jié)點(diǎn)　　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最小的兩個(gè)結(jié)點(diǎn)　　{　　if(

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

45、;i++) //parent為0且weight最小的兩個(gè)結(jié)點(diǎn)，第一個(gè)序號(hào)為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最小的兩個(gè)結(jié)點(diǎn)　　{　　if(HT[i].parent == 0 &&i!=(*s1))　　{　　min

48、 = i;i = m+1;　　}　　}　　for(i=1;i<=m;i++) //parent為0且weight最小的兩個(gè)結(jié)點(diǎn)，第二個(gè)序號(hào)為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個(gè)字符的權(quán)值（均>0)，構(gòu)造哈夫曼樹HT并求出n個(gè)字符的哈夫曼編碼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、號(hào)單元未用　　for (i=1;i<=n;i++) //葉子結(jié)點(diǎn)初始化并放入1-n號(hào)單元　　{　　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é)點(diǎn)初始化　　{

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

56、;\n哈夫曼樹的構(gòu)造過(guò)程如下所示:\n");　　printf("HT初態(tài):\n 結(jié)點(diǎn) weight parent lchild rchild");　　for (i=1;i<=m;i++) //完成構(gòu)造哈夫曼樹算法的第1個(gè)步驟　　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最小的兩個(gè)結(jié)點(diǎn)

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

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

61、ot;);　　for (j=1;j<=i;j++)　　//輸出選取根結(jié)點(diǎn)權(quán)值最小樹的過(guò)程　　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個(gè)字符的哈夫曼編碼如下:\n",n);　　//從葉子到根逆向求每個(gè)字符的哈夫曼編碼　　HC=(HuffmanCode)malloc((n+1)*sizeof(char *));//分配n個(gè)編碼的頭指針　　cd = (char * )malloc(n*size

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

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

66、>　　if (HT[f].lchild==c) cd[--start] ='0';　　else cd[--start] = '1';　　HC[i] = (char *)malloc((n-start)*sizeof(char));　　//為第i個(gè)字符編碼分配空間</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; //編碼個(gè)數(shù)及權(quán)值　　printf("請(qǐng)輸入需要哈夫曼編碼的字符個(gè)數(shù):");　　scanf("%d",&n);　　w=(int *)malloc((n+1

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

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

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

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

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

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

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

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

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

80、tack(SqStack &S)　　初始條件：棧指針已存在　　操作結(jié)果：定義空棧并分配存儲(chǔ)空間，成功返回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)　　初始條件：空棧已存在，括號(hào)串非空　　操作結(jié)果：輸出括號(hào)串是否匹配

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

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

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)//檢驗(yàn)括號(hào)匹配　　(6)void main( ) //主函數(shù)。輸入括號(hào)序列，調(diào)用棧操作模塊函數(shù)　　3．函數(shù)主要調(diào)用關(guān)系圖　　本程序6個(gè)子程序之間的主要調(diào)用關(guān)系如圖3所示。　　圖3 系統(tǒng)函數(shù)調(diào)用關(guān)系圖</p&

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

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

89、S)//創(chuàng)建空堆棧,棧頂指針和棧底指針相等時(shí),棧為空　　{ 　　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)　　{ //棧滿,追加存儲(chǔ)空間 　　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)//檢驗(yàn)括號(hào)匹配　　{ 　　int i=0,flag1=0,flag2;　　Elem e; 　　while(str[i]!='\0') //括號(hào)序列不為空</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("此串括號(hào)匹配不合法\n");　　return OK;　　}　　五、測(cè)試分析　　程序的測(cè)試分析如圖4所示。

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

105、/p>　　七、調(diào)試報(bào)告　　以前做實(shí)驗(yàn)題目的時(shí)候總是感覺(jué)很難，因?yàn)楦揪筒恢缽哪睦镩_始。這次課程設(shè)計(jì)讓我對(duì)編程有了新的認(rèn)識(shí)。　　拿到題目的時(shí)候也是很困惑，后來(lái)看了很多有關(guān)的例子，仔細(xì)看了書上關(guān)于棧的算法的知識(shí)，覺(jué)得就是上課講到的一些內(nèi)容，不是題目難，是自己先把自己嚇住了。

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

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

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

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

110、edef int Status;　　Status CreatStack(SqStack &S)//創(chuàng)建空堆棧,棧頂指針和棧底指針相等時(shí),棧為空　　{ 　　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)　　{ //棧滿,追加存儲(chǔ)空間 　　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)//檢驗(yàn)括號(hào)匹配　　{ 　　int i=0,flag1=0,flag2;　　Elem e;

118、;　　while(str[i]!='\0') //括號(hào)序列不為空　　{ 　　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("此串括號(hào)匹配不合法\n");　　return OK;　　}　　void main(){

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

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

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

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

溫馨提示

1. 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫(kù)僅提供信息存儲(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)告 (2)

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載