




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、數 據 結 構 基 礎 課 外 實 驗 指 導 書計算機學院2015年9月課外學時:16要求:完成4個課外實驗(實驗題目自選),填寫實驗報告注意:到教材科購買計算機學院上機實驗報告考核:實驗報告成績作為平時成績的一部分提交時間:第10周交給各班班長地點:鑒主1108一、上機實驗概述上機實驗是對學生的一種全面綜合訓練,是與課堂聽講、自學和練習相輔相成的必不可少的一個教學環節。通常,實驗題中的問題比平時的習題復雜得多,也更接近實際。實驗著眼于原理與應用的結合點,使讀者學會如何把書上學到的知識用于解決實際問題,培養軟件工作所需要的動手能力;另一方面,能使書上的知識變“活”,起到深化理解和靈活掌握教學
2、內容的目的。平時的練習較偏重于如何編寫功能單一的“小”算法,而實驗題是軟件設計的綜合訓練,包括問題分析、總體結構設計、用戶界面設計、程序設計基本技能和技巧,多人合作,以至一整套軟件工作規范的訓練和科學作風的培養。此外,還有很重要的一點是:機器是比任何教師都嚴厲的檢查者。每個實驗題采取了統一的格式,由問題描述、基本要求、測試數據、實現提示和選做內容五個部分組成。問題描述旨在為讀者建立問題提出的背景環境,指明問題“是什么”。基本要求則對問題進一步求精,劃出問題的邊界,指出具體的參量或前提條件,并規定該題的最低限度要求。測試數據部分旨在為檢查學生上機作業提供方便,在完成實驗題時應自己設計完整和嚴格的
3、測試方案,當數據輸入量較大時,提倡以文件形式向程序提供輸入數據。在實現提示部分,對實現中的難點及其解法思路等問題作了簡要提示。選做部分向那些尚有余力的讀者提出了更嚴峻的挑戰,同時也能開拓其他讀者的思路,在完成基本要求時力求避免就事論事的不良思想方法,盡可能尋求具有普遍意義的解法,使得程序結構合理,容易修改擴充。不難發現,這里與傳統的做法不同,題目設計得非常詳細。會不會限制讀者的想象力,影響創造力的培養呢?回答是:軟件發展的一條歷史經驗就是要限制程序設計者在某些方面的創造性,從而使其創造能力集中地用到特別需要創造性的環節之上。實驗題目本身就給出了問題說明和問題分解求精的范例,使讀者在無形中學會模
4、仿,它起到把讀者的思路引上正軌的作用,避免壞結構程序和壞習慣,同時也傳授了系統劃分方法和程序設計的一些具體技術,保證實現預定的訓練意圖,使某些難點和重點不會被繞過去,而且也便于教學檢查。題目的設計策略是:一方面使其難度和工作量都較大,另一方面給讀者提供的輔助和可以模仿的成份也較多。當然還應指出的是,提示的實現方法未必是最好的,讀者不應拘泥于此,而應努力開發更好的方法和結構。實驗要有嚴格的規范(見下一節)。一種普遍存在的錯誤觀念是,調試程序全憑運氣。學生花兩個小時的上機時間只找出一個錯誤,甚至一無所獲的情況是常見的。其原因在于,很多人只認識到找錯誤,而沒有認識到努力預先避免錯誤的重要性,也不知道
5、應該如何努力。實際上,結構不好、思路和概念不清的程序可能是根本無法調試正確的。嚴格按照實驗步驟規范進行實驗不但能有效地避免上述種種問題,更重要的是有利于培養軟件工作者不可缺少的科學工作方法和作風。二、實驗步驟隨之計算機性能的提高,它所面臨的軟件開發的復雜度也日趨增加。然而,編制一個10,000行的程序的難度絕不僅僅是一個5,000行的程序兩倍,因此軟件開發需要系統的方法。一種常用的軟件開發方法,是將軟件開發過程劃分為分析、設計、實現和維護四個階段。雖然數據結構課程中的實驗題的復雜度遠不如(從實際問題中提出來的)一個“真正的“軟件,但為了培養一個軟件工作者所應具備的科學工作的方法和作風,我們制訂
6、了如下所述完成實驗的五個步驟:(一) 問題分析和任務定義通常,實驗題目的陳述比較簡潔,或者說是有模棱兩可的含義。因此,在進行設計之前,首先應該充分地分析和理解問題,明確問題要求做什么?限制條件是什么。注意本步驟強調的是做什么?而不是怎么做。對問題的描述應避開算法和所涉及的數據類型,而是對所需完成的任務作出明確的回答。例如:輸入數據的類型、值的范圍以及輸入的形式;輸出數據的類型、值的范圍及輸出的形式;若是會話式的輸入,則結束標志是什么?是否接受非法的輸入?對非法輸入的回答方式是什么等。這一步還應該為調試程序準備好測試數據,包括合法的輸入數據和非法形式的輸入數據。(二) 數據類型和系統設計在設計這
7、一步驟中需分概要設計和詳細設計兩步實現。概要設計指的是,對問題描述中涉及的操作對象定義相應的數據類型,并按照以數據結構為中心的原則劃分模塊,定義主程序模塊和各抽象數據類型;詳細設計則為定義相應的存儲結構并寫出各函數的偽碼算法。在這個過程中,要綜合考慮系統功能,使得系統結構清晰、合理、簡單和易于調試,抽象數據類型的實現盡可能做到數據封裝,基本操作的規格說明盡可能明確具體。作為概要設計的結果,應寫出每個抽象數據類型的定義(包括數據結構的描述和每個基本操作的規格說明),各個主要模塊的算法,并畫出模塊之間的調用關系圖。詳細設計的結果是對數據結構和基本操作的規格說明作出進一步的求精,寫出數據存儲結構的類
8、型定義,按照算法書寫規范用類C語言寫出函數形式的算法框架。在求精的過程中,應盡量避免陷入語言細節,不必過早表述輔助數據結構和局部變量。(三) 編碼實現和靜態檢查編碼是把詳細設計的結果進一步求精為程序設計語言程序。程序的每行不要超過60個字符。每個函數體,即不計首部和規格說明部分,一般不要超過40行,最長不得超過60行,否則應該分割成較小的函數。要控制if語句連續嵌套的深度。如何編寫程序才能較快地完成調試是特別要注意的問題。對于編程很熟練的讀者,如果基于詳細設計的偽碼算法就能直接在鍵盤上輸入程序的話,則可以不必用筆在紙上寫出編碼,而將這一步的工作放在上機準備之后進行,即在上機調試之前直接用鍵盤輸
9、入。然而,不管你是否寫出編碼的程序,在上機之前,認真的靜態檢查是必不可少的。多數初學者在編好程序后處于以下兩種狀態之一:一種是對自己的“精心作品“的正確性確信不疑;另一種是認為上機前的任務已經完成,糾查錯誤是上機的工作。這兩種態度是極為有害的。事實上,非訓練有素的程序設計者編寫的程序長度超過50行時,極少不含有除語法錯誤以外的錯誤。上機動態調試決不能代替靜態檢查,否則調試效率將是極低的。靜態檢查主要有兩種方法,一是用一組測試數據手工執行程序(通常應先分模塊檢查);二是通過閱讀或給別人講解自己的程序而深入全面地理解程序邏輯,在這個過程中再加入一些注解和斷言。如果程序中邏輯概念清楚,后者將比前者有
10、效。(四)上機準備和上機調試上機準備包括以下幾個方面:(1) 高級語言文本(體現于編譯程序用戶手冊)的擴充和限制。例如,常用的BorlandC(C+)和MicrosoftC(C+)與標準C(C+)的差別,以及相互之間的差別。(2) 如果使用C或C+語言,要特別注意與教科書的類C語言之間的細微差別。(3) 熟悉機器的操作系統和語言集成環境的用戶手冊,尤其是最常用的命令操作,以便順利進行上機的基本活動。(4)掌握調試工具,考慮調試方案,設計測試數據并手工得出正確結果。上機調試程序時要帶一本高級語言教材或手冊。調試最好分模塊進行,自底向上,即先調試低層函數。必要時可以另寫一個調用驅動程序。這種表面上
11、麻煩的工作實際上可以大大降低調試所面臨的復雜性,提高調試工作效率。調試中遇到的各種異常現象往往是預料不到的,此時不應“冥思苦想” ,而應動手確定疑點,通過修改程序來證實它或繞過它。調試正確后,認真整理源程序及其注釋,印出帶有完整注釋的且格式良好的源程序清單和結果。(五)總結和整理實驗報告實驗一 線性表及其應用一、實驗目的1.熟悉C語言的上機環境,進一步掌握C語言的結構特點。2.掌握線性表的順序存儲結構的定義及C語言實現。3.掌握線性表在順序存儲結構即順序表中的各種基本操作。二、實驗內容 順序線性表的建立、插入及刪除。三、實驗步驟1.建立含n個數據元素的順序表并輸出該表中各元素的值及順序表的長度
12、。2.利用前面的實驗先建立一個順序表L=21,23,14,5,56,17,31,然后在第i個位置插入元素68。四、實現提示1.由于C語言的數組類型也有隨機存取的特點,一維數組的機內表示就是順序結構。因此,可用C語言的一維數組實現線性表的順序存儲。在此,我們利用C語言的結構體類型定義順序表:#define MAXSIZE 1024typedef int elemtype; /* 線性表中存放整型元素 */typedef struct elemtype vecMAXSIZE; int len
13、; /* 順序表的長度 */ sequenlist;將此結構定義放在一個頭文件sqlist.h里,可避免在后面的參考程序中代碼重復書寫,另外在該頭文件里給出順序表的建立及常量的定義。2. 注意如何取到第i個元素,在插入過程中注意溢出情況以及數組的下標與位序(順序表中元素的次序)的區別。五、思考與提高1. 如果按由表尾至表頭的次序輸入數據元素,應如何建立順序表。2. 在main函數里如果去掉L=&a語句,會出現什
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("本程序用來實現順序結構的線性表。n"); printf("可以實現查找、插入、刪除等操作。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語言的上機環境,進一步掌握C語言的結構特點。2.掌握線性表的鏈式存儲結構單鏈表的定義及C語言實現。3.掌握線性表在鏈式存儲結構單鏈表中的各種基本操作。二、實驗內容 鏈式線性表的建立、插入及刪除。三、實驗步驟建立一個帶頭結點的單鏈表,結點的值域為整型數據。要求將用戶輸入的數據按尾插入法來建立相應單鏈表。四、實現提示單鏈表的結點結構除
24、數據域外,還含有一個指針域。用C語言描述結點結構如下: typedef int elemtype;typedef struct node elemtype data; /數據域 struct node *next; /指針域 linklist; 注意結點的建立方法及構造新結點時指針的變化。構造一個結點需用到C語言的標準函數malloc(),如給指針變量p分配
25、一個結點的地址:p=(linklist *)malloc(sizeof(linklist);該語句的功能是申請分配一個類型為linklist的結點的地址空間,并將首地址存入指針變量p 中。當結點不需要時可以用標準函數free(p)釋放結點存儲空間,這時p為空值(NULL)。五、完整參考程序 1.鏈式線性表的建立、插入及刪除。#include <conio.h>#include <stdio.h>#include <stdlib.h>#define LEN sizeof(LNode) /定義LEN為一個節點的長度enum BOOLFalse,True; /定義
26、BOOL型typedef struct nodechar data; /數據域 struct node *next;/指向下一個節點的指針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("本程序實現鏈式結構的線性表的操作。n"); printf("可以進行插入,刪除,定位,查找等操作。n"); printf("請輸入初始時鏈表長度:"); /輸入生成單鏈表時的元素個數 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); /輸入要刪除的節點的位置 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");實驗三 棧的表示與實現一、實驗目的掌握棧的順序表示和實現二、實驗內容編寫一個程序實現順序棧的各種基本運算。三、實驗步驟1. 初始化順序棧2. 插入元素3. 刪除棧頂元素4. 取棧頂元素5. 遍歷順序棧6. 置空順序棧四、實現提示1. /*定義順序棧的存儲結構*/typedef struct ElemType stackMAXNUM; int top;SqStack; /*初始化順序棧函數*/void InitStack(SqStack *p) q=(SqStack*)ma
40、lloc(sizeof(SqStack) /*申請空間*/)/*入棧函數*/void Push(SqStack *p,ElemType x) if(p->top<MAXNUM-1) p->top=p->top+1; /*棧頂+1*/ p->stackp->top=x; /*數據入棧*/*出棧函數*/ElemType Pop(SqStack *p)x=p->stackp->top;
41、 /*將棧頂元素賦給x*/p->top=p->top-1; /*棧頂-1*/*獲取棧頂元素函數*/ElemType GetTop(SqStack *p) x=p->stackp->top;/*遍歷順序棧函數*/void OutStack(SqStack *p) for(i=p->top;i>=0;i-)printf("第%d個數據元素是:%6dn",i,p->stacki);/*置空順序棧函數*/void setEmpty(SqStack *p) p->top= -1;五、思考與提高1. 讀棧頂元素的算法與退棧頂元素的算法有何
42、區別?2. 如果一個程序中要用到兩個棧,為了不發生上溢錯誤,就必須給每個棧預先分配一個足夠大的存儲空間。若每個棧都預分配過大的存儲空間,勢必會造成系統空間緊張。如何解決這個問題?(1)鏈棧只有一個top指針,對于鏈隊列,為什么要設計一個頭指針和一個尾指針?(2)一個程序中如果要用到兩個棧時,可通過兩個棧共享一維數組來實現。即雙向棧共享鄰接空間。如果一個程序中要用到兩個隊列,能否實現?如何實現?六、完整參考程序 1. 棧的順序表示和實現#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("本程序實現順序結構的堆棧的操作。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("請輸入要入棧的元素(一個整數):");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);實驗四 隊列的表示與實現一、實驗目的掌握隊列的鏈式表示和實現二、實驗內容實現隊列的鏈式表示和實現。三、實驗步驟1. 初始化并建立鏈隊列2. 入鏈隊列3. 出鏈隊列4. 遍歷鏈隊列四、實現提示/*定義鏈隊列*/typedef struct Qnode ElemType data; struct Qnode *next;Qnodetype;typedef struct Qnodetype *front; Qnodetype *r
53、ear;Lqueue; /*初始化并建立鏈隊列函數*/void creat(Lqueue *q) h=(Qnodetype*)malloc(sizeof(Qnodetype); /*初始化申請空間*/ h->next=NULL; q->front=h; q->rear=h;for(i=1;i<=n;i+)*利用循環快速輸入數據*/
54、 scanf("%d",&x); Lappend(q,x); /*利用入鏈隊列函數快速輸入數據*/*入鏈隊列函數*/void Lappend(Lqueue *q,int x) s->data=x; s->next=NULL; q->rear->next=s; &
55、#160; q->rear=s;/*出鏈隊列函數*/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); /*釋放空間*/*遍歷鏈隊列函數*/void display(Lqueue *q) while(p!=NULL) /*利用條件判斷是否到隊尾*/ printf("%d->",p->data); p=p->next; 五、思考與提高一個程序中如果要
57、用到兩個棧時,可通過兩個棧共享一維數組來實現。即雙向棧共享鄰接空間。如果一個程序中要用到兩個隊列,能否實現?如何實現?六、完整參考程序 隊列的鏈式表示和實現#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 是函數的類型,其值是函數結果狀態代碼typedef int Status;/ElemType 是順序表數據元素類型,此程序定義為int型typedef int QElemType;/-單鏈隊列-隊列
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 煤炭制品企業市場競爭力提升策略與考核試卷
- 游樂設施施工法律法規知識考核試卷
- 電氣靜電及雷電安全防護技術考核試卷
- 稀土金屬冶煉工藝考核試卷
- 玻璃防眩光涂層開發考核試卷
- 礦山電氣系統設計與優化考核試卷
- 畜牧機械質量管理與可靠性考核試卷
- 海底古海洋學研究中心考核試卷
- 海上旅游目的地營銷策略考核試卷
- 遼寧省葫蘆島市高中名校2024-2025學年高三第10次統練數學試題含解析
- T-CTSS 3-2024 茶藝職業技能競賽技術規程
- 車隊運營中的司機管理策略研究
- 新生兒臍部出血的護理
- 實驗室的智能化設計與建設
- 《中國海洋大學》課件
- 排污許可管理培訓課件
- 《鹽津鋪子公司盈利能力探析實例報告(10000字論文)》
- 2025年中考語文課內名著閱讀專題復習:第10部 《水滸傳》課件
- 案例:中建八局綠色施工示范工程綠色施工(76P)
- 水產養殖技術培訓
- 2025年希望數學五年級培訓題(含答案)
評論
0/150
提交評論