括號匹配實驗報告

1、 五、實驗結(jié)果總結(jié)回答以下問題：你的測試充分嗎？為什么？你是怎樣考慮的？答：我認為我的測試充分，因為我的表達式是隨機給出的，這樣選擇的數(shù)據(jù)具有隨機性，具有很強的代表性，并且每次的結(jié)果正確，因此我認為我的測試比較充分。為什么你要選用?；蜿犃谢蜃址驍?shù)組等抽象數(shù)據(jù)類型作為你應(yīng)用的數(shù)據(jù)結(jié)構(gòu)？答：我使用了棧這種抽象數(shù)據(jù)類型作為我應(yīng)用的數(shù)據(jù)結(jié)構(gòu)，棧是一個只能訪問表的尾端數(shù)據(jù)的數(shù)據(jù)集合，是一種在表的一端進行插入和刪除操作的線性表，數(shù)據(jù)具有“先進后出”的特點，而這種特點和括號匹配中檢驗括號的“期限待的極限程度”這個特點相符合，因此選用棧這種數(shù)據(jù)結(jié)構(gòu)可以簡化程序，更好的理解和實現(xiàn)程序，提高了程序運行的時間效

2、率。用一段簡短的代碼及說明論述你的應(yīng)用中主要的函數(shù)的主要處理部分。答：下面的代碼部分為Match函數(shù)中的主要處理部分，使用了兩個循環(huán)來處理輸入的表達式，第一個循環(huán)是用來從左到右掃描表達式遇到“(”或者“”就將括號入棧，第二個循環(huán)是用來掃描表達式，如果遇到“)”或“”就將其與棧頂?shù)睦ㄌ栠M行匹配，如果匹配，就將棧頂?shù)淖罄ㄌ枏棾?，如果不匹配就將棧頂指針向下移動，直到所有的括號操作完成，如果棧為空，那么該表達式的括號是匹配的，否則括號不匹配。j=strlen(str);for(i=0;ij;i+)if(stri=(|stri=)push(s,str);for(i=0;ij;i+)if(stri=)if

3、(*s-top=()pop(s，&t);elsestop=s-top-1;if(stri=)if(*stop二二)pop(s，&t);elsestop=stop1;（4）你的應(yīng)用中采用的是順序的還是鏈式的存儲結(jié)構(gòu)？為什么要選用這種存儲結(jié)構(gòu)。答：我的應(yīng)用中采用的是順序的鏈式存儲結(jié)構(gòu)，因為對于棧這種抽象的數(shù)據(jù)類型，有著“先進后出”的特點，這種特性和表達式中括號匹配的過程相符合，因此我采用了這種存儲結(jié)構(gòu)。（5）源程序的大致的執(zhí)行過程是怎樣的？答：先用編譯器編寫一個.C的文件，然后編譯生成.Obj的文件，通過連接將目標文件連接生成一個.exe文件，之后運行文件就可以執(zhí)行了。六、附錄（1）如果你對這個實

4、驗還有其他的解決方案或設(shè)想，或?qū)ξ覀兊膶嶒灧桨赣惺裁匆庖?，請在此描述。這次實驗提高了我對數(shù)據(jù)結(jié)構(gòu)中堆棧、隊列的理解，提高了我的編程能力，學校以后可以增加實驗課的課時，這樣我們可以更大程度的提高自己的編程能力。另外對于本實驗，我覺得我們還可以使用鏈表完成，鏈表中每個結(jié)點存儲的數(shù)據(jù)項內(nèi)容為括號，從左導(dǎo)游掃描表達式，將所有的括號按照掃描的順序存成鏈表這種數(shù)據(jù)結(jié)構(gòu)之后，可以將第一個結(jié)點的內(nèi)容和最后一個結(jié)點的內(nèi)容比較，如果匹配則比較第二個和倒數(shù)第二個，以此類推。否則輸出括號不匹配。（2）實驗參考的資料數(shù)據(jù)結(jié)構(gòu)（第二版）閆玉寶編著清華大學出版社思考題（a）棧和隊列在計算機系統(tǒng)中有哪些應(yīng)用？寫出你知道的系統(tǒng)

5、中，這兩種抽象數(shù)據(jù)類型的應(yīng)用。答：在計算機系統(tǒng)中，使用棧的應(yīng)用有表達式的計算，迷宮以及括號匹配等。使用隊列的應(yīng)用有打印文檔，售票系統(tǒng)，解決主機與外部設(shè)備之間速度不匹配問題，解決多用戶引起的資源競爭問題等（b）在程序調(diào)用的時侯，需要進行函數(shù)的切換，你認為函數(shù)在進行切換時系統(tǒng)要做那些工作？答：對于函數(shù)的切換，主要是一個壓棧的過程，先以一種約定的方式把參數(shù)壓棧，然后根據(jù)函數(shù)地址調(diào)用函數(shù)，函數(shù)執(zhí)行后根據(jù)約定的方式出棧取得參數(shù)。選作：查詢以下內(nèi)容的有關(guān)知識a）函數(shù)調(diào)用、返回時，系統(tǒng)對棧進行的操作。答：函數(shù)調(diào)用時指令指針中的地址加1，指向函數(shù)調(diào)用后的下一條指令。這個地址隨后被放入堆棧，它將作為函數(shù)返回時的返回地址。在堆棧中為所聲明的返回值類型開辟空間。此時當前的堆棧棧頂被記錄下來并存入一個稱為棧幀的特殊指針中，從現(xiàn)在開始到函數(shù)返回之前加入堆棧的任何數(shù)據(jù)都將被視為函數(shù)的局部變量。之后函數(shù)將所有形參放入堆棧，開始執(zhí)行指令指針中的指令。局部變量按其定義的方式壓入堆棧。當函數(shù)準備返回時，返回值放入之前開辟的內(nèi)存中，隨后堆棧指針指向棧幀指針，從而彈出被調(diào)函數(shù)的所有局部變量。b）堆的管理都要做那些工作？具體怎樣做的？答：最小堆，將所有數(shù)據(jù)序列按完全