【正文】 《應用數(shù)據(jù)結構》實驗指導書課程編號：課程名稱：應用數(shù)據(jù)結構/Applied Data Structure實驗學時：16適應專業(yè)：工科類承擔實驗室：管理學院實驗中心一、實驗目的和任務1．實驗教學的目的 本課程的教學要求之一是訓練學生進行復雜程序設計的技能和培養(yǎng)良好程序設計的習慣，其重要程度絕不亞于知識傳授。實驗的作用在于幫助學生深入理解教材內容，鞏固基本概念，促使學生在動手過程中進一步體會C語言中數(shù)據(jù)結構的運用技巧，并鍛煉學生在調試過程中分析和發(fā)現(xiàn)問題的能力。2．實驗教學的要求學生應掌握C語言基本編程能力并運用數(shù)據(jù)結構的原理和方法解決具體問題。除按時上機外，學生應具備構造算法并用程序實現(xiàn)的能力；在程序調試過程中，學生應能正確解讀程序的錯誤提示并找到有效的解決辦法。此外，規(guī)范書寫算法也是一個值得高度重視的問題，教師有責任在教學過程中提醒學生，避免形成一系列難以糾正且貽害無窮的程序設計壞習慣。此外，本門課程設計的算法比較多，要求教師熟練掌握C語言和數(shù)據(jù)結構各類算法，并能準確理解和回答學生提出的編程問題。二、實驗項目及學時分配序號實 驗 項 目 名 稱實驗學時實驗類型開出要求1線性數(shù)據(jù)結構算法驗證4驗證及演示必做2非線性數(shù)據(jù)結構算法驗證4驗證及演示必做3查找及排序4驗證及演示必做4綜合算法設計4綜合必做三、參考資料李業(yè)麗、鄭良斌編著，數(shù)據(jù)結構（C）實驗教程，北京理工大學出版社，2005年12月出版嚴蔚敏，吳偉民編著，數(shù)據(jù)結構習題集（C語言版），清華大學出版社，1999年2月出版。四、單項實驗的內容和要求（包括實驗所用的主要儀器設備，實驗所需主要耗材）實驗一 線性數(shù)據(jù)結構算法驗證1．實驗目的與意義1) 熟悉C語言的上機環(huán)境，進一步掌握C語言的結構特點2) 掌握線性表的順序存儲結構的定義及C語言實現(xiàn)3) 掌握線性表的鏈式存儲結構——單鏈表的定義及C語言實現(xiàn)4) 掌握線性表在順序存儲結構——即順序表中的各種基本操作5) 掌握線性表在鏈式存儲結構——單鏈表中的各種基本操作6) 掌握棧的順序表示和實現(xiàn)7) 掌握棧的鏈式表示和實現(xiàn)8) 掌握隊列順序表示和實現(xiàn)9) 掌握隊列鏈式表示和實現(xiàn)2．基本原理和方法本實驗涉及各類線性數(shù)據(jù)結構——線性表、棧和隊列等。單鏈表的各種操作，包括單鏈表的建立，結點的查找、插入、刪除等基本運算。鏈表中插入結點的指針變化和刪除p所指結點的指針變化參見講義。棧的順序存儲結構簡稱為順序棧，它是運算受限的順序表。對于順序棧，入棧時，首先判斷棧是否為滿，棧滿的條件為ptop==MAXNUM1，棧滿時，不能入棧；否則出現(xiàn)空間溢出，引起錯誤，這種現(xiàn)象稱為上溢。出棧和讀棧頂元素操作，先判棧是否為空，為空時不能操作，否則產(chǎn)生錯誤。通常棧空作為一種控制轉移的條件。注意：① 順序棧中元素用向量存放。② 棧底位置是固定不變的，可設置在向量兩端的任意一個端點。③ 棧頂位置是隨著進棧和退棧操作而變化的，用一個整型量top（通常稱top為棧頂指針）來指示當前棧頂位置。隊列的順序存儲結構稱為順序隊列，順序隊列實際上是運算受限的順序表。入隊時，將新元素插入rear所指的位置，然后將rear加1，出隊時，刪去front所指的元素，然后將front加1并返回被刪除元素。順序隊列中的溢出現(xiàn)象：① “下溢”現(xiàn)象。當隊列為空時，做出隊運算產(chǎn)生的溢出現(xiàn)象?！跋乱纭笔钦，F(xiàn)象，常用作程序控制轉移的條件。② “真上溢”現(xiàn)象。當隊列滿時，做進找運算產(chǎn)生空間溢出的現(xiàn)象?！罢嫔弦纭笔且环N出錯狀態(tài)，應設法避免。③ “假上溢”現(xiàn)象。由于入隊和出隊操作中，頭尾指針只增加不減小，致使被刪元素的空間永遠無法重新利用。當隊列中實際的元素個數(shù)遠遠小于向量空聞的規(guī)模時，也可能由于尾指針己超越向量空間的上界而不能做入隊操作。該現(xiàn)象稱為“假上溢”現(xiàn)象。3．主要儀器設備及耗材安裝有Turbo C++ ，無耗材要求。4．實驗方案或技術路線本實驗含有三部分內容——線性表、棧和隊列。A．線性表部分采取建立學生成績表的方法實現(xiàn)。即建立學生成績單鏈表，鏈表中每個結點由4個域組成，分別為：學號、姓名、成績、存放下一個結點地址的next域、要求完成的四項功能可寫成四個函數(shù)，登記學生成績對應建立學生單鏈表的功能，后三個功能分別對應單鏈表的查詢、插入與刪除三大基本操作。該系統(tǒng)中的數(shù)據(jù)采用線性表中的鏈式存儲結構即單鏈表來存儲，用結構體類型定義每個學生記錄，故該單鏈表中每個結點的結構可描述為：define MAXLEN 100typedef struct node{ int num；//學號 char name[MAXLEN]；//姓名 float score；//成績 struct node *next。 }linklist。B．棧部分此部分的算法獨立性較強，因此可直接采用教材或講義上的算法實現(xiàn)，但教材或講義上的算法并非可執(zhí)行的算法，故學生須自行進行算法上的轉換。C．隊列部分本實驗主要由教師課堂演示，以一個具體的實例——機場事件模擬來實現(xiàn)。5．實驗內容及步驟A．線性表部分——學生成績管理是學校教務管理的重要組成部分，其處理信息量很大，本實驗是對學生的成績管理作一個簡單的模擬，用菜單選擇操作方式完成下列功能：① 登記學生成績② 查詢學生成績③ 插入學生成績④ 刪除學生成績【參考程序】/**/includeincludeincludedefine MAXLEN 100typedef struct node{ int num。 char name[MAXLEN]。 int score。 struct node *next。 }list。/**/includelist *create(){ list *head, *p, *r。 int i, n。 head=(list *)malloc(sizeof(list))。 headnext=NULL。 r=head。 printf(請輸入學生人數(shù):\n)。 scanf(%d,amp。n)。 for(i=l。 i=n。 i++) { p=(list *)malloc(sizeof(list))。 printf(輸入學生的學號:\n)。 scanf(%d, amp。pnum)。 printf(輸入學生的姓名:\n)。 scanf(%s, pname)。 printf(輸人李生的成績:\n)。 scanf(%d, amp。pscore)。 pnext=NULL。 rnext=p。 r=rnext。 } return(head)。}/**/list *insert(list *h){ list *p,*q,*r,*head。 head=r=h。 p=hnext。 q=(list *)malloc(sizeof(list))。 printf(輸入待插入學生的學號:\n)。 scanf(%d,amp。qnum)。 printf(輸入姓名:\n)。 scanf(%s, qname)。 printf(輸入成績:\n)。 scanf(%d, amp。qscore)。 qnext=NULL。 while(p) { r=p。 p=pnext。 } rnext=q。 r=rnext。 return(head)。}/**/void find(list *h){ int k。 list *p。 p=hnext。 printf(輸入要查找學生的學號:\n)。 scanf(%d, amp。k)。 while(pamp。amp。pnum!=k) p=pnext。 if(p) { printf(學號\t姓名\t成績\n)。 printf(%d\t%s\t%d\n,pnum,pname,pscore)。 } else printf(沒找到!\n)。}/**/list *del(list *h){ int k。 list *p, *q。 q=h。 p=hnext。 printf(請輸入待刪除學生的學號:\n)。 scanf(%d,amp。k)。 while(pamp。amp。pnum!=k) { q=p。 p=pnext。 } if(p) { qnext=pnext。 free(p)。 } else printf(沒有這個學生成績，無法刪除!\n)。 return(h)。}/**/void output(list *h){ list *p。 p=hnext。 while(p!=NULL) { printf(學號\t姓名\t成績\t\n)。 printf(%d\t%s\t%d\n,pnum,pname,pscore)。 p=pnext。 }}/*以下是主程序*/includeincludeincludeincludeincludemain(){ list *p。 int k。 /*控制循環(huán)的標志*/ while(1) { printf( \n)。 printf( | 學生成績管理 |\n)。 printf( |＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿|\n)。 printf( | |\n)。 printf( | |\n)。 printf( | 3:插入成績 |\n)。 printf( | |\n)。 printf( | |\n)。 printf( | |\n)。 printf( \n)。 printf( 請輸入你的選擇\n)。 scanf(%d,amp。k)。 switch(k) { case 1: p=create()。 break。 case 2: find(p)。 break。 case 3: p=insert(p)。 break。 case 4: p=del(p)。 break。 case 5: output(p)。 break。 case 0: exit(0)。 default: printf(選擇錯誤，重新開始!\n)。 } }}B．棧部分——編寫一個程序實現(xiàn)順序棧的各種基本運算，并在此基礎上設計一個主程序，完成如下功能：① 初始化順序棧② 插入元素③ 刪除棧頂元素④ 取棧頂元⑤ 遍歷順序棧⑥ 置空順序?！緟⒖汲绦颉縤ncludeincludedefine MAXNUM 20define ElemType int/*定義順序棧的存儲結構*/typedef struct{ ElemType stack[MAXNUM]。 int top。 }SqStack。/*初始化順序棧*/void InitStack(SqStack *p){ if(!p) printf(Error)。 ptop=l。}/*入棧*/void Push(SqStack *p, ElemType x){ if(ptopMAXNUM1) pstack[++ptop]=x。 else printf(Overflow!\n)。}/*出棧*/ElemType Pop(SqStack *p){ ElemType x。 if(ptop!=O) { x=pstack[ptop]。 printf(棧頂元%d已經(jīng)被刪除！\n, pstack[ptop])。 ptop=。 return(x)。 } else { printf(Underflow!\n)。 return(0)。 }}/*獲取棧頂元素*/ElemType GetTop(SqStack *p){ if(ptop!=0) return (pstack[ptop])。 else { printf(Underflow!\n)。 return(0)。 }}/*遍歷順序棧*/void OutStack(SqStack *p){ int i。 printf(\n)。 if(ptop0) printf(這是一個空棧！\n)。 for(i=ptop。 i=O。 i) printf(第%d個數(shù)據(jù)是：%6d\n, i, p