數(shù)據(jù)結構驗證性實驗指導書(2015)

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

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

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

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

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

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

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

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

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

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

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

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

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

14、么結果？六、完整參考程序 1.順序線性表的建立、插入及刪除。#include <stdio.h>#include <conio.h>#define MAX 30 /定義線性表的最大長度enum BOOLFalse,True; /定義BOOL型typedef struct char elemMAX; /線性表 int last; /last指示當前線性表的長度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("本程序用來實現(xiàn)順序結構的線性表。n"); printf("可以實現(xiàn)查找、插入、刪除等操作。n"); initial(S); /初始化線性表 while(flag) printf("請選擇:n"); pri

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

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

19、在位置:%dn",loc+1); /顯示該元素位置 else printf("%c 不存在!n",ch);/當前元素不存在 break; default:flag=0;printf("程序結束，按任意鍵退出!n"); getch();void initial(sqlist &v)/初始化線性表 int i; printf("請輸入初始線性表長度：n="); /輸入線性表初始化時的長度 scanf("%d",&v.last); printf("請輸入從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) /插入一個元素，成功返回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) /刪除一個元素，成功返回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+; /當前位置后移，直到找到為止 if(v.elemi=ch) /找到當前元素 return i; else return(-1);void pri

23、nt(sqlist v) /顯示當前線性表所有元素int i; for(i=0;i<v.last;i+) printf("%c ",v.elemi); printf("n"); 實驗二 線性表及其應用一、實驗目的1.熟悉C語言的上機環(huán)境，進一步掌握C語言的結構特點。2.掌握線性表的鏈式存儲結構單鏈表的定義及C語言實現(xiàn)。3.掌握線性表在鏈式存儲結構單鏈表中的各種基本操作。二、實驗內(nèi)容 鏈式線性表的建立、插入及刪除。三、實驗步驟建立一個帶頭結點的單鏈表，結點的值域為整型數(shù)據(jù)。要求將用戶輸入的數(shù)據(jù)按尾插入法來建立相應單鏈表。四、實現(xiàn)提示單鏈表的結點結構除

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

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

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

27、元素BOOL ListFind_order(LinkList,char &,int); /按序號查找一個元素void ListPrint(LinkList); /顯示單鏈表所有元素void main()LinkList L; BOOL temp; int num,loc,flag=1; char j,ch; printf("本程序實現(xiàn)鏈式結構的線性表的操作。n"); printf("可以進行插入，刪除，定位，查找等操作。n"); printf("請輸入初始時鏈表長度:"); /輸入生成單鏈表時的元素個數(shù) scanf("

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

29、tf("6.退出程序 n"); /退出 scanf(" %c",&j); switch(j)case '1':ListPrint(L); break; case '2':printf("請輸入元素(一個字符)和要插入的位置: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("請輸入要刪除的元素所在位置:"); scanf("%d",&loc); /輸入要刪除的節(jié)點的位置 temp=ListDelete(L,loc,ch); /刪除 if(temp=False) printf("刪除失敗!n"); /刪除失敗 else printf(&quo

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

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

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

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

36、p;&j<i-1) /查找第i-1個元素位置 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)/在單鏈表中查找關鍵字為e的元素，成功返回True,并用i返回該元素位置， /失敗返回False i=1; LinkL

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

38、>next&&j<i) /移動指針，直到找到第i個元素 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");實驗三 棧的表示與實現(xiàn)一、實驗目的掌握棧的順序表示和實現(xiàn)二、實驗內(nèi)容編寫一個程序實現(xiàn)順序棧的各種基本運算。三、實驗步驟1. 初始化順序棧2. 插入元素3. 刪除棧頂元素4. 取棧頂元素5. 遍歷順序棧6. 置空順序棧四、實現(xiàn)提示1. /*定義順序棧的存儲結構*/typedef struct      ElemType stackMAXNUM;     int top;SqStack; /*初始化順序棧函數(shù)*/void InitStack(SqStack *p) q=(SqStack*)ma

40、lloc(sizeof(SqStack) /*申請空間*/)/*入棧函數(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個數(shù)據(jù)元素是：%6dn",i,p->stacki);/*置空順序棧函數(shù)*/void setEmpty(SqStack *p) p->top= -1;五、思考與提高1. 讀棧頂元素的算法與退棧頂元素的算法有何

42、區(qū)別？2. 如果一個程序中要用到兩個棧，為了不發(fā)生上溢錯誤，就必須給每個棧預先分配一個足夠大的存儲空間。若每個棧都預分配過大的存儲空間，勢必會造成系統(tǒng)空間緊張。如何解決這個問題？（1）鏈棧只有一個top指針，對于鏈隊列，為什么要設計一個頭指針和一個尾指針？（2）一個程序中如果要用到兩個棧時，可通過兩個棧共享一維數(shù)組來實現(xiàn)。即雙向棧共享鄰接空間。如果一個程序中要用到兩個隊列，能否實現(xiàn)？如何實現(xiàn)？六、完整參考程序 1. 棧的順序表示和實現(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;/- 棧的順序存儲表示 -#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)/構造一個空棧SS.base = (SElemType *) malloc(STACK

45、_INIT_SIZE*sizeof(SElemType);if(!S.base) exit(OVERFLOW); /存儲分配失效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)/棧滿，追加存儲空間S.base=(SElemType*) realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if( ! S.base ) exit(OVERFLOW);/存儲分配失敗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("本程序實現(xiàn)順序結構的堆棧的操作。n");printf("可以進行入棧，出棧，取棧頂元素等操作。n");InitStack(St); /初始化堆棧Stwhile(flag)printf("請選擇: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("請輸入要入棧的元素(一個整數(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("成功出棧一個元素:%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("程序結束，按任意鍵退出!n");getch();Des

52、troyStack(St);實驗四 隊列的表示與實現(xiàn)一、實驗目的掌握隊列的鏈式表示和實現(xiàn)二、實驗內(nèi)容實現(xiàn)隊列的鏈式表示和實現(xiàn)。三、實驗步驟1. 初始化并建立鏈隊列2. 入鏈隊列3. 出鏈隊列4. 遍歷鏈隊列四、實現(xiàn)提示/*定義鏈隊列*/typedef struct Qnode   ElemType data;     struct Qnode *next;Qnodetype;typedef struct   Qnodetype *front;     Qnodetype *r

53、ear;Lqueue; /*初始化并建立鏈隊列函數(shù)*/void creat(Lqueue *q)    h=(Qnodetype*)malloc(sizeof(Qnodetype); /*初始化申請空間*/     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);   /*利用入鏈隊列函數(shù)快速輸入數(shù)據(jù)*/*入鏈隊列函數(shù)*/void Lappend(Lqueue *q,int x) s->data=x;     s->next=NULL;     q->rear->next=s; &

55、#160;   q->rear=s;/*出鏈隊列函數(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); /*釋放空間*/*遍歷鏈隊列函數(shù)*/void display(Lqueue *q) while(p!=NULL)  /*利用條件判斷是否到隊尾*/          printf("%d->",p->data);            p=p->next;     五、思考與提高一個程序中如果要

57、用到兩個棧時，可通過兩個棧共享一維數(shù)組來實現(xiàn)。即雙向棧共享鄰接空間。如果一個程序中要用到兩個隊列，能否實現(xiàn)？如何實現(xiàn)？六、完整參考程序 隊列的鏈式表示和實現(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ù)結果狀態(tài)代碼typedef int Status;/ElemType 是順序表數(shù)據(jù)元素類型,此程序定義為int型typedef int QElemType;/-單鏈隊列-隊列