括號匹配實驗報告

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

2、率。用一段簡短的代碼及說明論述你的應(yīng)用中主要的函數(shù)的主要處理部分。答：下面的代碼部分為Match函數(shù)中的主要處理部分，使用了兩個循環(huán)來處理輸入的表達(dá)式，第一個循環(huán)是用來從左到右掃描表達(dá)式遇到“(”或者“”就將括號入棧，第二個循環(huán)是用來掃描表達(dá)式，如果遇到“)”或“”就將其與棧頂?shù)睦ㄌ栠M(jìn)行匹配，如果匹配，就將棧頂?shù)淖罄ㄌ枏棾?，如果不匹配就將棧頂指針向下移動，直到所有的括號操作完成，如果棧為空，那么該表達(dá)式的括號是匹配的，否則括號不匹配。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)用中采用的是順序的還是鏈?zhǔn)降拇鎯Y(jié)構(gòu)？為什么要選用這種存儲結(jié)構(gòu)。答：我的應(yīng)用中采用的是順序的鏈?zhǔn)酱鎯Y(jié)構(gòu)，因為對于棧這種抽象的數(shù)據(jù)類型，有著“先進(jìn)后出”的特點(diǎn)，這種特性和表達(dá)式中括號匹配的過程相符合，因此我采用了這種存儲結(jié)構(gòu)。（5）源程序的大致的執(zhí)行過程是怎樣的？答：先用編譯器編寫一個.C的文件，然后編譯生成.Obj的文件，通過連接將目標(biāo)文件連接生成一個.exe文件，之后運(yùn)行文件就可以執(zhí)行了。六、附錄（1）如果你對這個實

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

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