數(shù)據(jù)結(jié)構(gòu)驗(yàn)證性實(shí)驗(yàn)指導(dǎo)書(2015)

1、數(shù) 據(jù) 結(jié) 構(gòu) 基 礎(chǔ) 課 外 實(shí) 驗(yàn) 指 導(dǎo) 書計(jì)算機(jī)學(xué)院2015年9月課外學(xué)時(shí)：16要求：完成4個(gè)課外實(shí)驗(yàn)（實(shí)驗(yàn)題目自選），填寫實(shí)驗(yàn)報(bào)告注意：到教材科購買計(jì)算機(jī)學(xué)院上機(jī)實(shí)驗(yàn)報(bào)告考核：實(shí)驗(yàn)報(bào)告成績作為平時(shí)成績的一部分提交時(shí)間：第10周交給各班班長地點(diǎn)：鑒主1108一、上機(jī)實(shí)驗(yàn)概述上機(jī)實(shí)驗(yàn)是對(duì)學(xué)生的一種全面綜合訓(xùn)練，是與課堂聽講、自學(xué)和練習(xí)相輔相成的必不可少的一個(gè)教學(xué)環(huán)節(jié)。通常，實(shí)驗(yàn)題中的問題比平時(shí)的習(xí)題復(fù)雜得多，也更接近實(shí)際。實(shí)驗(yàn)著眼于原理與應(yīng)用的結(jié)合點(diǎn)，使讀者學(xué)會(huì)如何把書上學(xué)到的知識(shí)用于解決實(shí)際問題，培養(yǎng)軟件工作所需要的動(dòng)手能力；另一方面，能使書上的知識(shí)變“活”，起到深化理解和靈活掌握教學(xué)

2、內(nèi)容的目的。平時(shí)的練習(xí)較偏重于如何編寫功能單一的“小”算法，而實(shí)驗(yàn)題是軟件設(shè)計(jì)的綜合訓(xùn)練，包括問題分析、總體結(jié)構(gòu)設(shè)計(jì)、用戶界面設(shè)計(jì)、程序設(shè)計(jì)基本技能和技巧，多人合作，以至一整套軟件工作規(guī)范的訓(xùn)練和科學(xué)作風(fēng)的培養(yǎng)。此外，還有很重要的一點(diǎn)是:機(jī)器是比任何教師都嚴(yán)厲的檢查者。每個(gè)實(shí)驗(yàn)題采取了統(tǒng)一的格式，由問題描述、基本要求、測試數(shù)據(jù)、實(shí)現(xiàn)提示和選做內(nèi)容五個(gè)部分組成。問題描述旨在為讀者建立問題提出的背景環(huán)境，指明問題“是什么”?；疽髣t對(duì)問題進(jìn)一步求精，劃出問題的邊界，指出具體的參量或前提條件，并規(guī)定該題的最低限度要求。測試數(shù)據(jù)部分旨在為檢查學(xué)生上機(jī)作業(yè)提供方便，在完成實(shí)驗(yàn)題時(shí)應(yīng)自己設(shè)計(jì)完整和嚴(yán)格的

3、測試方案，當(dāng)數(shù)據(jù)輸入量較大時(shí)，提倡以文件形式向程序提供輸入數(shù)據(jù)。在實(shí)現(xiàn)提示部分，對(duì)實(shí)現(xiàn)中的難點(diǎn)及其解法思路等問題作了簡要提示。選做部分向那些尚有余力的讀者提出了更嚴(yán)峻的挑戰(zhàn)，同時(shí)也能開拓其他讀者的思路，在完成基本要求時(shí)力求避免就事論事的不良思想方法，盡可能尋求具有普遍意義的解法，使得程序結(jié)構(gòu)合理，容易修改擴(kuò)充。不難發(fā)現(xiàn)，這里與傳統(tǒng)的做法不同，題目設(shè)計(jì)得非常詳細(xì)。會(huì)不會(huì)限制讀者的想象力，影響創(chuàng)造力的培養(yǎng)呢？回答是：軟件發(fā)展的一條歷史經(jīng)驗(yàn)就是要限制程序設(shè)計(jì)者在某些方面的創(chuàng)造性，從而使其創(chuàng)造能力集中地用到特別需要?jiǎng)?chuàng)造性的環(huán)節(jié)之上。實(shí)驗(yàn)題目本身就給出了問題說明和問題分解求精的范例，使讀者在無形中學(xué)會(huì)模

4、仿，它起到把讀者的思路引上正軌的作用，避免壞結(jié)構(gòu)程序和壞習(xí)慣，同時(shí)也傳授了系統(tǒng)劃分方法和程序設(shè)計(jì)的一些具體技術(shù)，保證實(shí)現(xiàn)預(yù)定的訓(xùn)練意圖，使某些難點(diǎn)和重點(diǎn)不會(huì)被繞過去，而且也便于教學(xué)檢查。題目的設(shè)計(jì)策略是：一方面使其難度和工作量都較大，另一方面給讀者提供的輔助和可以模仿的成份也較多。當(dāng)然還應(yīng)指出的是，提示的實(shí)現(xiàn)方法未必是最好的，讀者不應(yīng)拘泥于此，而應(yīng)努力開發(fā)更好的方法和結(jié)構(gòu)。實(shí)驗(yàn)要有嚴(yán)格的規(guī)范(見下一節(jié))。一種普遍存在的錯(cuò)誤觀念是，調(diào)試程序全憑運(yùn)氣。學(xué)生花兩個(gè)小時(shí)的上機(jī)時(shí)間只找出一個(gè)錯(cuò)誤，甚至一無所獲的情況是常見的。其原因在于，很多人只認(rèn)識(shí)到找錯(cuò)誤，而沒有認(rèn)識(shí)到努力預(yù)先避免錯(cuò)誤的重要性，也不知道

5、應(yīng)該如何努力。實(shí)際上，結(jié)構(gòu)不好、思路和概念不清的程序可能是根本無法調(diào)試正確的。嚴(yán)格按照實(shí)驗(yàn)步驟規(guī)范進(jìn)行實(shí)驗(yàn)不但能有效地避免上述種種問題，更重要的是有利于培養(yǎng)軟件工作者不可缺少的科學(xué)工作方法和作風(fēng)。二、實(shí)驗(yàn)步驟隨之計(jì)算機(jī)性能的提高，它所面臨的軟件開發(fā)的復(fù)雜度也日趨增加。然而，編制一個(gè)10，000行的程序的難度絕不僅僅是一個(gè)5，000行的程序兩倍，因此軟件開發(fā)需要系統(tǒng)的方法。一種常用的軟件開發(fā)方法，是將軟件開發(fā)過程劃分為分析、設(shè)計(jì)、實(shí)現(xiàn)和維護(hù)四個(gè)階段。雖然數(shù)據(jù)結(jié)構(gòu)課程中的實(shí)驗(yàn)題的復(fù)雜度遠(yuǎn)不如(從實(shí)際問題中提出來的)一個(gè)“真正的“軟件，但為了培養(yǎng)一個(gè)軟件工作者所應(yīng)具備的科學(xué)工作的方法和作風(fēng)，我們制訂

6、了如下所述完成實(shí)驗(yàn)的五個(gè)步驟:(一) 問題分析和任務(wù)定義通常，實(shí)驗(yàn)題目的陳述比較簡潔，或者說是有模棱兩可的含義。因此，在進(jìn)行設(shè)計(jì)之前，首先應(yīng)該充分地分析和理解問題，明確問題要求做什么?限制條件是什么。注意本步驟強(qiáng)調(diào)的是做什么?而不是怎么做。對(duì)問題的描述應(yīng)避開算法和所涉及的數(shù)據(jù)類型，而是對(duì)所需完成的任務(wù)作出明確的回答。例如:輸入數(shù)據(jù)的類型、值的范圍以及輸入的形式；輸出數(shù)據(jù)的類型、值的范圍及輸出的形式；若是會(huì)話式的輸入，則結(jié)束標(biāo)志是什么?是否接受非法的輸入?對(duì)非法輸入的回答方式是什么等。這一步還應(yīng)該為調(diào)試程序準(zhǔn)備好測試數(shù)據(jù)，包括合法的輸入數(shù)據(jù)和非法形式的輸入數(shù)據(jù)。(二) 數(shù)據(jù)類型和系統(tǒng)設(shè)計(jì)在設(shè)計(jì)這

7、一步驟中需分概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)兩步實(shí)現(xiàn)。概要設(shè)計(jì)指的是，對(duì)問題描述中涉及的操作對(duì)象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型；詳細(xì)設(shè)計(jì)則為定義相應(yīng)的存儲(chǔ)結(jié)構(gòu)并寫出各函數(shù)的偽碼算法。在這個(gè)過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試，抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。作為概要設(shè)計(jì)的結(jié)果，應(yīng)寫出每個(gè)抽象數(shù)據(jù)類型的定義(包括數(shù)據(jù)結(jié)構(gòu)的描述和每個(gè)基本操作的規(guī)格說明)，各個(gè)主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖。詳細(xì)設(shè)計(jì)的結(jié)果是對(duì)數(shù)據(jù)結(jié)構(gòu)和基本操作的規(guī)格說明作出進(jìn)一步的求精，寫出數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的類

8、型定義，按照算法書寫規(guī)范用類C語言寫出函數(shù)形式的算法框架。在求精的過程中，應(yīng)盡量避免陷入語言細(xì)節(jié)，不必過早表述輔助數(shù)據(jù)結(jié)構(gòu)和局部變量。(三) 編碼實(shí)現(xiàn)和靜態(tài)檢查編碼是把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語言程序。程序的每行不要超過60個(gè)字符。每個(gè)函數(shù)體，即不計(jì)首部和規(guī)格說明部分，一般不要超過40行，最長不得超過60行，否則應(yīng)該分割成較小的函數(shù)。要控制if語句連續(xù)嵌套的深度。如何編寫程序才能較快地完成調(diào)試是特別要注意的問題。對(duì)于編程很熟練的讀者，如果基于詳細(xì)設(shè)計(jì)的偽碼算法就能直接在鍵盤上輸入程序的話，則可以不必用筆在紙上寫出編碼，而將這一步的工作放在上機(jī)準(zhǔn)備之后進(jìn)行，即在上機(jī)調(diào)試之前直接用鍵盤輸

9、入。然而，不管你是否寫出編碼的程序，在上機(jī)之前，認(rèn)真的靜態(tài)檢查是必不可少的。多數(shù)初學(xué)者在編好程序后處于以下兩種狀態(tài)之一：一種是對(duì)自己的“精心作品“的正確性確信不疑；另一種是認(rèn)為上機(jī)前的任務(wù)已經(jīng)完成，糾查錯(cuò)誤是上機(jī)的工作。這兩種態(tài)度是極為有害的。事實(shí)上，非訓(xùn)練有素的程序設(shè)計(jì)者編寫的程序長度超過50行時(shí)，極少不含有除語法錯(cuò)誤以外的錯(cuò)誤。上機(jī)動(dòng)態(tài)調(diào)試決不能代替靜態(tài)檢查，否則調(diào)試效率將是極低的。靜態(tài)檢查主要有兩種方法，一是用一組測試數(shù)據(jù)手工執(zhí)行程序(通常應(yīng)先分模塊檢查)；二是通過閱讀或給別人講解自己的程序而深入全面地理解程序邏輯，在這個(gè)過程中再加入一些注解和斷言。如果程序中邏輯概念清楚，后者將比前者有

10、效。(四)上機(jī)準(zhǔn)備和上機(jī)調(diào)試上機(jī)準(zhǔn)備包括以下幾個(gè)方面：(1) 高級(jí)語言文本(體現(xiàn)于編譯程序用戶手冊)的擴(kuò)充和限制。例如，常用的BorlandC(C+)和MicrosoftC(C+)與標(biāo)準(zhǔn)C(C+)的差別，以及相互之間的差別。(2) 如果使用C或C+語言，要特別注意與教科書的類C語言之間的細(xì)微差別。(3) 熟悉機(jī)器的操作系統(tǒng)和語言集成環(huán)境的用戶手冊，尤其是最常用的命令操作，以便順利進(jìn)行上機(jī)的基本活動(dòng)。(4)掌握調(diào)試工具，考慮調(diào)試方案，設(shè)計(jì)測試數(shù)據(jù)并手工得出正確結(jié)果。上機(jī)調(diào)試程序時(shí)要帶一本高級(jí)語言教材或手冊。調(diào)試最好分模塊進(jìn)行，自底向上，即先調(diào)試低層函數(shù)。必要時(shí)可以另寫一個(gè)調(diào)用驅(qū)動(dòng)程序。這種表面上

11、麻煩的工作實(shí)際上可以大大降低調(diào)試所面臨的復(fù)雜性，提高調(diào)試工作效率。調(diào)試中遇到的各種異?，F(xiàn)象往往是預(yù)料不到的，此時(shí)不應(yīng)“冥思苦想” ，而應(yīng)動(dòng)手確定疑點(diǎn)，通過修改程序來證實(shí)它或繞過它。調(diào)試正確后，認(rèn)真整理源程序及其注釋，印出帶有完整注釋的且格式良好的源程序清單和結(jié)果。(五)總結(jié)和整理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)一 線性表及其應(yīng)用一、實(shí)驗(yàn)?zāi)康?.熟悉C語言的上機(jī)環(huán)境，進(jìn)一步掌握C語言的結(jié)構(gòu)特點(diǎn)。2.掌握線性表的順序存儲(chǔ)結(jié)構(gòu)的定義及C語言實(shí)現(xiàn)。3.掌握線性表在順序存儲(chǔ)結(jié)構(gòu)即順序表中的各種基本操作。二、實(shí)驗(yàn)內(nèi)容 順序線性表的建立、插入及刪除。三、實(shí)驗(yàn)步驟1.建立含n個(gè)數(shù)據(jù)元素的順序表并輸出該表中各元素的值及順序表的長度

12、。2.利用前面的實(shí)驗(yàn)先建立一個(gè)順序表L=21，23，14，5，56，17，31，然后在第i個(gè)位置插入元素68。四、實(shí)現(xiàn)提示1.由于C語言的數(shù)組類型也有隨機(jī)存取的特點(diǎn)，一維數(shù)組的機(jī)內(nèi)表示就是順序結(jié)構(gòu)。因此，可用C語言的一維數(shù)組實(shí)現(xiàn)線性表的順序存儲(chǔ)。在此，我們利用C語言的結(jié)構(gòu)體類型定義順序表：#define MAXSIZE  1024typedef  int  elemtype;    /*  線性表中存放整型元素  */typedef struct elemtype vecMAXSIZE;  int len

13、;             /*  順序表的長度  */ sequenlist;將此結(jié)構(gòu)定義放在一個(gè)頭文件sqlist.h里，可避免在后面的參考程序中代碼重復(fù)書寫，另外在該頭文件里給出順序表的建立及常量的定義。2. 注意如何取到第i個(gè)元素，在插入過程中注意溢出情況以及數(shù)組的下標(biāo)與位序（順序表中元素的次序）的區(qū)別。五、思考與提高1. 如果按由表尾至表頭的次序輸入數(shù)據(jù)元素，應(yīng)如何建立順序表。2. 在main函數(shù)里如果去掉L=&a語句，會(huì)出現(xiàn)什

14、么結(jié)果？六、完整參考程序 1.順序線性表的建立、插入及刪除。#include <stdio.h>#include <conio.h>#define MAX 30 /定義線性表的最大長度enum BOOLFalse,True; /定義BOOL型typedef struct char elemMAX; /線性表 int last; /last指示當(dāng)前線性表的長度sqlist;void initial(sqlist &); /初始化線性表BOOL insert(sqlist &,int,char); /在線性表中插入元素BOOL del(sqlist&

15、,int,char &); /在線性表中刪除元素int locate(sqlist,char); /在線性表中定位元素void print(sqlist); /顯示線性表中所有元素void main()sqlist S; /S為一線性表 int loc,flag=1; char j,ch; BOOL temp;printf("本程序用來實(shí)現(xiàn)順序結(jié)構(gòu)的線性表。n"); printf("可以實(shí)現(xiàn)查找、插入、刪除等操作。n"); initial(S); /初始化線性表 while(flag) printf("請(qǐng)選擇:n"); pri

16、ntf("1.顯示所有元素n"); printf("2.插入一個(gè)元素n"); printf("3.刪除一個(gè)元素n"); printf("4.查找一個(gè)元素n"); printf("5.退出程序 n"); scanf(" %c",&j); switch(j)case '1':print(S); break; /顯示所有元素 case '2':printf("請(qǐng)輸入要插入的元素(一個(gè)字符)和插入位置:n"); printf

17、("格式：字符，位置；例如:a,2n"); scanf(" %c,%d",&ch,&loc); /輸入要插入的元素和插入的位置 temp=insert(S,loc,ch); /插入 if(temp=False) printf("插入失敗!n"); /插入失敗 else printf("插入成功!n"); print(S); /插入成功 break; case '3':printf("請(qǐng)輸入要?jiǎng)h除元素的位置:"); scanf("%d",&

18、;loc); /輸入要?jiǎng)h除的元素的位置 temp=del(S,loc,ch); /刪除 if(temp=True) printf("刪除了一個(gè)元素:%cn",ch); /刪除成功 else printf("該元素不存在!n"); /刪除失敗 print(S); break; case '4':printf("請(qǐng)輸入要查找的元素:"); scanf(" %c",&ch); /輸入要查找的元素 loc=locate(S,ch); /定位 if(loc!=-1) printf("該元素所

19、在位置:%dn",loc+1); /顯示該元素位置 else printf("%c 不存在!n",ch);/當(dāng)前元素不存在 break; default:flag=0;printf("程序結(jié)束，按任意鍵退出!n"); getch();void initial(sqlist &v)/初始化線性表 int i; printf("請(qǐng)輸入初始線性表長度：n="); /輸入線性表初始化時(shí)的長度 scanf("%d",&v.last); printf("請(qǐng)輸入從1到%d的各元素(字符)，例如

20、:abcdefgn",v.last); getchar(); for(i=0;i<v.last;i+) scanf("%c",&v.elemi); /輸入線性表的各元素BOOL insert(sqlist &v,int loc,char ch) /插入一個(gè)元素，成功返回True，失敗返回False int i; if(loc<1)|(loc>v.last+1) printf("插入位置不合理!n"); /位置不合理 return False; else if(v.last>=MAX) /線性表已滿 pri

21、ntf("線性表已滿!n"); return False; else for(i=v.last-1;i>=loc-1;i-) v.elemi+1=v.elemi;/其后元素依次后移 v.elemloc-1=ch; /插入元素 v.last+; /線性表長度加一 return True; BOOL del(sqlist &v,int loc,char &ch) /刪除一個(gè)元素，成功返回True，并用ch返回該元素值，失敗返回False int j; if(loc<1|loc>v.last) /刪除位置不合理 return False; els

22、e ch=v.elemloc-1; /ch取得該元素值 for(j=loc-1;j<v.last-1;j+) v.elemj=v.elemj+1; /其后元素依次前移 v.last-; /線性表長度減一 return True; int locate(sqlist v,char ch)/在線性表中查找ch的位置，成功返回其位置，失敗返回-1 int i=0; while(i<v.last&&v.elemi!=ch) i+; /當(dāng)前位置后移，直到找到為止 if(v.elemi=ch) /找到當(dāng)前元素 return i; else return(-1);void pri

23、nt(sqlist v) /顯示當(dāng)前線性表所有元素int i; for(i=0;i<v.last;i+) printf("%c ",v.elemi); printf("n"); 實(shí)驗(yàn)二 線性表及其應(yīng)用一、實(shí)驗(yàn)?zāi)康?.熟悉C語言的上機(jī)環(huán)境，進(jìn)一步掌握C語言的結(jié)構(gòu)特點(diǎn)。2.掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)單鏈表的定義及C語言實(shí)現(xiàn)。3.掌握線性表在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)單鏈表中的各種基本操作。二、實(shí)驗(yàn)內(nèi)容 鏈?zhǔn)骄€性表的建立、插入及刪除。三、實(shí)驗(yàn)步驟建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)的值域?yàn)檎蛿?shù)據(jù)。要求將用戶輸入的數(shù)據(jù)按尾插入法來建立相應(yīng)單鏈表。四、實(shí)現(xiàn)提示單鏈表的結(jié)點(diǎn)結(jié)構(gòu)除

24、數(shù)據(jù)域外，還含有一個(gè)指針域。用C語言描述結(jié)點(diǎn)結(jié)構(gòu)如下：    typedef int elemtype;typedef struct node    elemtype data;   /數(shù)據(jù)域      struct node *next; /指針域     linklist;    注意結(jié)點(diǎn)的建立方法及構(gòu)造新結(jié)點(diǎn)時(shí)指針的變化。構(gòu)造一個(gè)結(jié)點(diǎn)需用到C語言的標(biāo)準(zhǔn)函數(shù)malloc()，如給指針變量p分配

25、一個(gè)結(jié)點(diǎn)的地址：p=(linklist *)malloc(sizeof(linklist);該語句的功能是申請(qǐng)分配一個(gè)類型為linklist的結(jié)點(diǎn)的地址空間，并將首地址存入指針變量p 中。當(dāng)結(jié)點(diǎn)不需要時(shí)可以用標(biāo)準(zhǔn)函數(shù)free(p)釋放結(jié)點(diǎn)存儲(chǔ)空間，這時(shí)p為空值（NULL）。五、完整參考程序 1.鏈?zhǔn)骄€性表的建立、插入及刪除。#include <conio.h>#include <stdio.h>#include <stdlib.h>#define LEN sizeof(LNode) /定義LEN為一個(gè)節(jié)點(diǎn)的長度enum BOOLFalse,True; /定義

26、BOOL型typedef struct nodechar data; /數(shù)據(jù)域 struct node *next;/指向下一個(gè)節(jié)點(diǎn)的指針LNode,*LinkList;void CreatList(LinkList &,int); /生成一個(gè)單鏈表BOOL ListInsert(LinkList &,int,char); /在單鏈表中插入一個(gè)元素BOOL ListDelete(LinkList &,int,char &); /在單鏈表中刪除一個(gè)元素BOOL ListFind_keyword(LinkList,char,int &); /按關(guān)鍵字查找一個(gè)

27、元素BOOL ListFind_order(LinkList,char &,int); /按序號(hào)查找一個(gè)元素void ListPrint(LinkList); /顯示單鏈表所有元素void main()LinkList L; BOOL temp; int num,loc,flag=1; char j,ch; printf("本程序?qū)崿F(xiàn)鏈?zhǔn)浇Y(jié)構(gòu)的線性表的操作。n"); printf("可以進(jìn)行插入，刪除，定位，查找等操作。n"); printf("請(qǐng)輸入初始時(shí)鏈表長度:"); /輸入生成單鏈表時(shí)的元素個(gè)數(shù) scanf("

28、;%d",&num); CreatList(L,num); /生成單鏈表 ListPrint(L); while(flag) printf("請(qǐng)選擇:n"); printf("1.顯示所有元素n"); /顯示鏈表元素 printf("2.插入一個(gè)元素n"); /插入鏈表元素 printf("3.刪除一個(gè)元素n"); /刪除鏈表元素 printf("4.按關(guān)鍵字查找元素n"); /按關(guān)鍵字查找 printf("5.按序號(hào)查找元素n"); /按序號(hào)查找 prin

29、tf("6.退出程序 n"); /退出 scanf(" %c",&j); switch(j)case '1':ListPrint(L); break; case '2':printf("請(qǐng)輸入元素(一個(gè)字符)和要插入的位置:n"); printf("格式:字符，位置；例如:a,3n"); scanf(" %c,%d",&ch,&loc); /輸入要插入的元素和要插入的位置 temp=ListInsert(L,loc,ch); /插入 if(

30、temp=False) printf("插入失敗!n"); /插入失敗 else printf("插入成功!n"); /成功插入 ListPrint(L); break; case '3':printf("請(qǐng)輸入要?jiǎng)h除的元素所在位置:"); scanf("%d",&loc); /輸入要?jiǎng)h除的節(jié)點(diǎn)的位置 temp=ListDelete(L,loc,ch); /刪除 if(temp=False) printf("刪除失敗!n"); /刪除失敗 else printf(&quo

31、t;成功刪除了一個(gè)元素:%cn",ch); /刪除成功，顯示該元素 ListPrint(L); break; case '4':if(L->next=NULL) /鏈表為空 printf("鏈表為空!n"); elseprintf("請(qǐng)輸入要查找的元素(一個(gè)字符):"); scanf(" %c",&ch); /輸入要查找的元素 temp=ListFind_keyword(L,ch,loc); /按關(guān)鍵字查找 if(temp=False) printf("沒有找到該元素!n")

32、; /查找失敗 else printf("該元素在鏈表的第%d個(gè)位置。n",loc); /成功查找，顯示該元素位置 break; case '5':if(L->next=NULL) /鏈表為空 printf("鏈表為空!n"); elseprintf("請(qǐng)輸入要查找的位置:"); scanf("%d",&loc); /輸入要查找的元素的位置 temp=ListFind_order(L,ch,loc); /按序號(hào)查找 if(temp=False) printf("該位置不存在!

33、n"); /查找失敗 else printf("第%d個(gè)元素是：%cn",loc,ch); /成功查找，顯示該元素 break; default:flag=0;printf("程序結(jié)束，按任意鍵退出!n"); getch();void CreatList(LinkList &v,int n)/生成一個(gè)帶頭結(jié)點(diǎn)的有n個(gè)元素的單鏈表 int i; LinkList p; v=(LinkList)malloc(LEN); /生成頭結(jié)點(diǎn) v->next=NULL; printf("請(qǐng)輸入%d個(gè)字符：例如：abcdefgn&quo

34、t;,n); getchar(); for(i=n;i>0;-i) p=(LinkList)malloc(LEN); /生成新結(jié)點(diǎn) scanf("%c",&p->data); p->next=v->next; v->next=p; BOOL ListInsert(LinkList &v,int i,char e)/在單鏈表的第i各位置插入元素e，成功返回True，失敗返回False LinkList p,s; int j=0; p=v; while(p&&j<i-1) p=p->next;+j; /查

35、找第i-1個(gè)元素的位置 if(!p|j>i-1) return False; /沒有找到 s=(LinkList)malloc(LEN); /生成一個(gè)新結(jié)點(diǎn) s->data=e; s->next=p->next; /將新結(jié)點(diǎn)插入到單鏈表中 p->next=s; return True;BOOL ListDelete(LinkList &v,int i,char &e)/在單鏈表中刪除第i個(gè)元素，成功刪除返回True，并用e返回該元素值，失敗返回False LinkList p,q; int j=0; p=v; while(p->next&am

36、p;&j<i-1) /查找第i-1個(gè)元素位置 p=p->next;+j; if(!(p->next)|j>i-1) return False; /查找失敗 q=p->next;p->next=q->next; /刪除該元素 e=q->data; /e取得該元素值 free(q); /釋放該元素空間 return True;BOOL ListFind_keyword(LinkList v,char e,int &i)/在單鏈表中查找關(guān)鍵字為e的元素，成功返回True,并用i返回該元素位置， /失敗返回False i=1; LinkL

37、ist p; p=v->next; while(p->data!=e)&&(p->next!=NULL)/p指針指向下一個(gè)，直到 p=p->next; i+; /找到或到鏈表尾為止 if(p->data!=e) /該元素在鏈表中不存在 return False; else return True;BOOL ListFind_order(LinkList v,char &e,int i)/在單鏈表中查找第i個(gè)元素，成功返回True，并用e返回該元素值， /失敗返回False LinkList p; int j=0; p=v; while(p-

38、>next&&j<i) /移動(dòng)指針，直到找到第i個(gè)元素 p=p->next;+j; if(j!=i) return False; /查找失敗 else e=p->data; /查找成功，用e取得該元素值 return True; void ListPrint(LinkList v) /顯示鏈表所有元素 LinkList q; q=v->next; printf("鏈表所有元素:"); while(q!=NULL) printf("%c ",q->data);q=q->next; printf(&q

39、uot;n");實(shí)驗(yàn)三 棧的表示與實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康恼莆諚５捻樞虮硎竞蛯?shí)現(xiàn)二、實(shí)驗(yàn)內(nèi)容編寫一個(gè)程序?qū)崿F(xiàn)順序棧的各種基本運(yùn)算。三、實(shí)驗(yàn)步驟1. 初始化順序棧2. 插入元素3. 刪除棧頂元素4. 取棧頂元素5. 遍歷順序棧6. 置空順序棧四、實(shí)現(xiàn)提示1. /*定義順序棧的存儲(chǔ)結(jié)構(gòu)*/typedef struct      ElemType stackMAXNUM;     int top;SqStack; /*初始化順序棧函數(shù)*/void InitStack(SqStack *p) q=(SqStack*)ma

40、lloc(sizeof(SqStack) /*申請(qǐng)空間*/)/*入棧函數(shù)*/void Push(SqStack *p,ElemType x) if(p->top<MAXNUM-1)     p->top=p->top+1;     /*棧頂+1*/      p->stackp->top=x;   /*數(shù)據(jù)入棧*/*出棧函數(shù)*/ElemType Pop(SqStack *p)x=p->stackp->top;

41、 /*將棧頂元素賦給x*/p->top=p->top-1; /*棧頂-1*/*獲取棧頂元素函數(shù)*/ElemType GetTop(SqStack *p) x=p->stackp->top;/*遍歷順序棧函數(shù)*/void OutStack(SqStack *p) for(i=p->top;i>=0;i-)printf("第%d個(gè)數(shù)據(jù)元素是：%6dn",i,p->stacki);/*置空順序棧函數(shù)*/void setEmpty(SqStack *p) p->top= -1;五、思考與提高1. 讀棧頂元素的算法與退棧頂元素的算法有何

42、區(qū)別？2. 如果一個(gè)程序中要用到兩個(gè)棧，為了不發(fā)生上溢錯(cuò)誤，就必須給每個(gè)棧預(yù)先分配一個(gè)足夠大的存儲(chǔ)空間。若每個(gè)棧都預(yù)分配過大的存儲(chǔ)空間，勢必會(huì)造成系統(tǒng)空間緊張。如何解決這個(gè)問題？（1）鏈棧只有一個(gè)top指針，對(duì)于鏈隊(duì)列，為什么要設(shè)計(jì)一個(gè)頭指針和一個(gè)尾指針？（2）一個(gè)程序中如果要用到兩個(gè)棧時(shí)，可通過兩個(gè)棧共享一維數(shù)組來實(shí)現(xiàn)。即雙向棧共享鄰接空間。如果一個(gè)程序中要用到兩個(gè)隊(duì)列，能否實(shí)現(xiàn)？如何實(shí)現(xiàn)？六、完整參考程序 1. 棧的順序表示和實(shí)現(xiàn)#include <stdio.h>#include <stdlib.h>#include <conio.h>#define

43、TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int SElemType;/- 棧的順序存儲(chǔ)表示 -#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;Status InitStack(SqStack &S);St

44、atus DestroyStack(SqStack &S);Status StackDisplay(SqStack &S);Status GetTop(SqStack S,SElemType &e);Status Push(SqStack &S,SElemType e);Status Pop(SqStack &S,SElemType &e);Status StackEmpty(SqStack S);Status InitStack(SqStack &S)/構(gòu)造一個(gè)空棧SS.base = (SElemType *) malloc(STACK

45、_INIT_SIZE*sizeof(SElemType);if(!S.base) exit(OVERFLOW); /存儲(chǔ)分配失效S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;/InitStackStatus DestroyStack(SqStack &S)/銷毀棧Sif(S.base) free(S.base);S.top = S.base = NULL;return OK;/InitStackStatus StackDisplay(SqStack &S)/顯示棧SSElemType * p=S.base;int

46、i = 0;if(S.base = S.top) printf("堆棧已空!n"); return OK;while( p < S.top)printf("%d:%d",+i,*p+);printf("n");return OK;/StackDisplayStatus GetTop(SqStack S,SElemType &e) /若棧不空，則用e返回S的棧頂元素，/并返回OK；否則返回ERRORif(S.top=S.base) return ERROR;e=*(S.top-1);return OK;/GetTopSta

47、tus Push(SqStack &S,SElemType e)/插入元素e為新的棧頂元素if(S.top-S.base>=S.stacksize)/棧滿，追加存儲(chǔ)空間S.base=(SElemType*) realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if( ! S.base ) exit(OVERFLOW);/存儲(chǔ)分配失敗S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;* S.top + = e;return OK;/PushSt

48、atus Pop(SqStack &S,SElemType &e)/若棧不為空，則刪除S的棧頂元素，/用e返回其值，并返回OK；否則返回ERROR if (S.top = S.base) return ERROR; e = * -S.top; return OK;/PopStatus StackEmpty(SqStack S)/若S為空棧，則返回TRUE，否則返回FALSE。if(S.top = S.base) return TRUE;else return FALSE;/ StackEmptyvoid main()SqStack St;Status temp;int flag

49、=1,ch;int e;printf("本程序?qū)崿F(xiàn)順序結(jié)構(gòu)的堆棧的操作。n");printf("可以進(jìn)行入棧，出棧，取棧頂元素等操作。n");InitStack(St); /初始化堆棧Stwhile(flag)printf("請(qǐng)選擇:n");printf("1.顯示棧中所有元素 n");printf("2.入棧 n");printf("3.出棧 n");printf("4.取棧頂元素 n");printf("5.退出程序 n");sca

50、nf("%d",&ch);switch(ch)case 1:StackDisplay(St);break;case 2:printf("請(qǐng)輸入要入棧的元素(一個(gè)整數(shù)):");scanf("%d",&e); /輸入要入棧的元素temp=Push(St,e); /入棧if(temp!=OK) printf("堆棧已滿!入棧失敗!n");else printf("成功入棧!n"); /成功入棧StackDisplay(St);break;case 3:temp=Pop(St,e); /

51、出棧if(temp=ERROR) printf("堆棧已空!n"); else printf("成功出棧一個(gè)元素:%dn",e); /成功出棧StackDisplay(St);break;case 4:temp=GetTop(St,e); /取得棧頂元素if(temp=ERROR) printf("堆棧已空!n");else printf("棧頂元素是:%dn",e); /顯示棧頂元素break;default:flag=0;printf("程序結(jié)束，按任意鍵退出!n");getch();Des

52、troyStack(St);實(shí)驗(yàn)四 隊(duì)列的表示與實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康恼莆贞?duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)二、實(shí)驗(yàn)內(nèi)容實(shí)現(xiàn)隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)。三、實(shí)驗(yàn)步驟1. 初始化并建立鏈隊(duì)列2. 入鏈隊(duì)列3. 出鏈隊(duì)列4. 遍歷鏈隊(duì)列四、實(shí)現(xiàn)提示/*定義鏈隊(duì)列*/typedef struct Qnode   ElemType data;     struct Qnode *next;Qnodetype;typedef struct   Qnodetype *front;     Qnodetype *r

53、ear;Lqueue; /*初始化并建立鏈隊(duì)列函數(shù)*/void creat(Lqueue *q)    h=(Qnodetype*)malloc(sizeof(Qnodetype); /*初始化申請(qǐng)空間*/     h->next=NULL;     q->front=h;     q->rear=h;for(i=1;i<=n;i+)*利用循環(huán)快速輸入數(shù)據(jù)*/       

54、   scanf("%d",&x);            Lappend(q,x);   /*利用入鏈隊(duì)列函數(shù)快速輸入數(shù)據(jù)*/*入鏈隊(duì)列函數(shù)*/void Lappend(Lqueue *q,int x) s->data=x;     s->next=NULL;     q->rear->next=s; &

55、#160;   q->rear=s;/*出鏈隊(duì)列函數(shù)*/ElemType Ldelete(Lqueue *q) p=q->front->next;     q->front->next=p->next;     if(p->next=NULL)     q->rear=q->front;     x=p->data;   

56、60; free(p); /*釋放空間*/*遍歷鏈隊(duì)列函數(shù)*/void display(Lqueue *q) while(p!=NULL)  /*利用條件判斷是否到隊(duì)尾*/          printf("%d->",p->data);            p=p->next;     五、思考與提高一個(gè)程序中如果要

57、用到兩個(gè)棧時(shí)，可通過兩個(gè)棧共享一維數(shù)組來實(shí)現(xiàn)。即雙向棧共享鄰接空間。如果一個(gè)程序中要用到兩個(gè)隊(duì)列，能否實(shí)現(xiàn)？如何實(shí)現(xiàn)？六、完整參考程序 隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)#include <conio.h>#include <stdio.h>#include <stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2/Status 是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼typedef int Status;/ElemType 是順序表數(shù)據(jù)元素類型,此程序定義為int型typedef int QElemType;/-單鏈隊(duì)列-隊(duì)列