線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu).doc

貴州大學(xué)實驗報告學(xué)院：計算機科學(xué)與信息學(xué)院 專業(yè)： 班級： 姓名學(xué)號實驗組實驗2實驗時間指導(dǎo)教師葉潔成績實驗項目名稱實驗二：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)實驗?zāi)康?. 熟練掌握線性表的基本操作在鏈?zhǔn)酱鎯ι系膶崿F(xiàn)；2. 以線性表的各種操作（建立、插入、刪除等）的實現(xiàn)為重點；3. 掌握線性表的動態(tài)分配順序存儲結(jié)構(gòu)的定義和基本操作的實現(xiàn)；實驗環(huán)境運行Microsoft Visual Studio 2010的微機一臺實驗內(nèi)容 1輸入一組整型數(shù)據(jù)，建立帶頭結(jié)點的單鏈表。2實現(xiàn)該線性表的刪除。3、實現(xiàn)該線性表的插入。4實現(xiàn)線形表中數(shù)據(jù)的顯示。5實現(xiàn)線性表數(shù)據(jù)的查找和定位5、編寫一個主函數(shù),調(diào)試上述算法。實驗數(shù)據(jù)1 未創(chuàng)建鏈表前選擇其它操作會提示操作失敗，選擇【1】創(chuàng)建鏈表，在創(chuàng)建鏈表時，鍵入“no”來結(jié)束輸入結(jié)點，如何先后鍵入-44，11，22，當(dāng)鍵入“no”時，退出錄入數(shù)據(jù).如圖2、 在選擇【2】查找元素操作時，又會產(chǎn)生3個子選項，輸入不合法的操作都會提示非法。選擇【1】按元素查找時，輸入相應(yīng)的元素，會顯示相應(yīng)的查找結(jié)果，選擇【2】按位置查找，鍵入位置值，會顯示相應(yīng)的查找結(jié)果，若位置值超出鏈表的長度則會查找失敗。選擇【3】退出查找并返回主菜單。3、 選擇【3】插入元素時，也會彈出3個子菜單，鍵入13之外的任何字符都會提示非法操作。選擇【1】按有序插入，若鍵入不任何非整型字符串都會提示非法并要求重新正確輸入?；虬从行虿迦?2，會插入11與22之間，即第3個位置。選擇【2】按位置插入，如在第5個位置插入45。如果選擇位置45會提示位置值無效，因為鏈表總結(jié)點數(shù)也只有5個。選擇【3】退出插入，則會退出插入并返回主菜單。具體操作實現(xiàn)如下：4、 選擇【4】刪除元素，則會生成3個了菜單。也只有輸入相應(yīng)的序號才能執(zhí)行相應(yīng)的功能，鍵入其它字符都會提示非法并要求重新輸入。如選擇【1】按元素刪除，要求輸入待刪除的元素，若鍵入非法數(shù)據(jù)則會提示非法，鍵入一個數(shù)后會查找到這個數(shù)據(jù)并刪除，若鍵入鏈表中不存在的數(shù)據(jù)則提示刪除失敗，執(zhí)行完后又跳回子菜單。如選擇【2】按位置刪除，輸入相應(yīng)的位置值，若位置值超出了鏈表的長度會提示錯誤信息，若位置在鏈表長度之內(nèi)，則會把相應(yīng)位置的元素刪除，選擇【3】退出刪除，則退出刪除并返回主菜單。刪除前,鏈表為：-44，11，12，22，12;刪除后為：-44，11，12。具體實現(xiàn)如圖：5、 選擇【5】顯示鏈表則會顯示當(dāng)前鏈表所有信息，包括每個結(jié)點中元素和鏈表結(jié)點數(shù)。如圖所示：6、 為了測試【6】排序鏈表的功能，因為現(xiàn)有的鏈表為-44，11，12有序鏈表。不妨先按位置插入幾個數(shù)使其成為無序表，再選擇【6】排序鏈表，排序前后如圖：7、 選擇【7】清空鏈表，則會清空當(dāng)前鏈表，清空鏈表后在再次創(chuàng)建一個鏈表前無法使用其它功能。具體實現(xiàn)如圖：八、在主菜單的8個選項中若鍵入18之外任何其它信息則會提示選擇的操作非法，并要求重新輸入。若選擇【8】退出系統(tǒng)，會出現(xiàn)，以保證不會因為意外操作面退出系統(tǒng)。選擇“n”則不會退出系統(tǒng)，選擇“y”則會退出系統(tǒng)。鍵入其它任何信息，則會提示操作非法，并要求重新選擇。具體功能實現(xiàn)如圖：實驗總結(jié) 1.雖然實驗要求在主函數(shù)中實現(xiàn)對各種功能函數(shù)的調(diào)用，但考慮到可能會在主函數(shù)中實現(xiàn)其實現(xiàn)其它功能，所有在寫程序并沒有把調(diào)用寫在主函數(shù)中，而是統(tǒng)一寫在void Menu( )函數(shù)中，再由主函數(shù)調(diào)用這個Menu函數(shù)，以實現(xiàn)對鏈表相應(yīng)的操作。 2.為提高本程序的健壯性，在寫程序時，我用到了int atoi(char *p)函數(shù)來將輸入的合法的字符串轉(zhuǎn)化成整型數(shù)據(jù)。由于鍵入整型數(shù)據(jù)地方很多，所以編寫了int JudgeData()函數(shù)，在每次要輸入數(shù)據(jù)的地方都調(diào)用這個函數(shù)來判斷輸入數(shù)據(jù)的合法性;同樣在選擇相應(yīng)操作時，我也相應(yīng)地編寫了char JudgeOperation( )函數(shù)以判斷選擇操作的合法性，在每處需要選擇相應(yīng)操作的地方都調(diào)用這個函數(shù)來判斷選擇操作的合法性。利用這兩個函數(shù)大大提高了程序的健壯性，解決了實驗一中的輸入不合法類型數(shù)據(jù)會進入死循環(huán)的現(xiàn)象。3.通過本次實驗讓我對鏈表的創(chuàng)建、插入、刪除、清空、排序等操作都有了進一步的了解和深入的認(rèn)識。4.本次實驗和實驗一和實驗二比，在健壯性上有很大的提高，并且由于對char JudgeOperation( )和int JudgeData()的反復(fù)調(diào)用，節(jié)省了不少代碼。5.和實驗一相比，由于本次實驗在輸入數(shù)據(jù)的地方調(diào)用了int JudgeData()函數(shù)，因此只能將ElemType定義為int型，若定義為char類型，則運行程序不會產(chǎn)生預(yù)期的效果。這一點還望老師指正！指導(dǎo)教師意見簽名： 年 月 日程序清單如下：/ 實驗二-鏈表.cpp : 定義控制臺應(yīng)用程序的入口點。/#include stdafx.h#include#include#includeusing namespace std;typedef int ElemType;struct LNodeElemType data;LNode* next;/初始化鏈表void InitList(LNode* &HL)HL-next =NULL;/判斷輸入的數(shù)據(jù)是否為整型int JudgeData()char c100;Judge:cinc;if(strcmp(c,no)=0)return(-879);else if(c0=-|c0=0&c0=9)for(int i=1;ci!=0;i+)if(ci9)cout您輸入的數(shù)據(jù)非法！endl;cout請重新輸入合法類型數(shù)據(jù)： ;goto Judge;return atoi(c);elsecout您輸入的數(shù)據(jù)非法！endl;coutc;if(strlen(c)=1)if(c08)cout您輸入的操作不合法！請重新選擇：;goto judge;elsecout您輸入的操作不合法！請重新選擇：;goto judge;return (c0);/為鏈表錄入數(shù)據(jù)void InputList(LNode* &HL)int i=0;LNode* ap,*cp;ap=HL;while(1)i+;cout（如數(shù)據(jù)已錄入完畢，請輸入“no”）請輸入第 i 個數(shù)據(jù)： ;ElemType item=JudgeData(); if(item=-879)cout您錄入 i-1 個數(shù)據(jù)完畢！next =cp;cp-data =item;ap=cp;ap-next=NULL;/顯示鏈表所有信息void DisplayList(LNode* HL)int i=0;LNode* cp=HL-next;while(cp!=NULL)i+;coutdatanext;coutendl;cout鏈表中共有 i 個元素！next;if(pos-1)cout位置值無效，查找失?。ext!=NULL)pos+;cp=cp-next;else if(pos=0)pos=1;while(cp!=NULL)if(cp-data=item)break;elsepos+;cp=cp-next;if(cp=NULL)cout沒有找到您想要查找的元素！next;i+;if(cp=NULL)cout您輸入的位置值已超過鏈表的總長度，查找失?。ndl;return;cout查找成功！您所查找的元素 data 在鏈表第 pos 個位置！next;ap=HL;if(pos-1)cout位置值無效，插入失?。ext;else if(pos=0)pos=1;while(cp!=NULL)if(item data) break;elseap=cp;cp=cp-next;pos+;elseint i=0;while(cp!=NULL)i+;if(i=pos) break;elseap=cp;cp=cp-next;if(i+1pos)cout位置值超出鏈表的長度，插入失?。ata=item;if(pos=1)HL-next=tp;tp-next=cp;elseap-next=tp;tp-next=cp;cout插入成功！您已成功把元素 item 插入到第 pos 個位置！next;ap=HL;if(pos-1)cout您輸入的位置值無效，刪除失敗！next!=NULL)pos+;ap=cp;cp=cp-next;else if(pos=0)pos=1;while(cp!=NULL)if(cp-data=item) break;elsepos+;ap=cp;cp=cp-next;if(cp=NULL)cout沒有找到您要刪除的元素，刪除失?。ext;if(cp=NULL)cout您輸入的位置值已超過鏈表的長度，刪除失??！next=cp-next;elseap-next=cp-next;ElemType tem=cp-data;delete cp;cout刪除成功！您所要刪除的元素 tem 已從鏈表中第 pos 個位置刪除！next;if(HL-next=NULL)cout鏈表未創(chuàng)建或已被清空！next;delete tem;HL-next=NULL;cout清空鏈表成功！next;tem-next=NULL;while(cp!=NULL)InsertList(tem,cp-data,0);cp=cp-next;EmptyList(HL);cout鏈表更新成功！排序后鏈表如下：endl;HL=tem;/操作菜單void Menu()LNode* h;h=new LNode;InitList(h);ElemType item;int pos;menu:cout歡迎進入鏈表管理系統(tǒng)：endl;cout 1.創(chuàng)建鏈表endl;cout 2.查找元素endl;cout 3.插入元素endl;cout 4.刪除元素endl;cout 5.顯示鏈表endl;cout 6.排序鏈表endl;cout 7.清空鏈表endl;cout 8.退出系統(tǒng)endl;cout請選擇您想要執(zhí)行的操作：;switch(JudgeOperation()case 1:InputList(h);coutnext=NULL)cout鏈表未創(chuàng)建，查找失敗！endlendl;goto menu;Find:cout查找操作有：1.根據(jù)元素查找位置endl;cout 2.根據(jù)位置查找元素endl;cout 3.退出查找操作endl;cout請選擇相應(yīng)的查找操作：;switch(JudgeOperation()case 1:cout請輸入你要查找的元素： ;item=JudgeData();FindList(h,item,0);goto Find;case 2:cout請輸入您要查找的位置(查看尾元素請鍵入-1)： ;pos=JudgeData();FindList(h,0,pos);goto Find;case 3:coutendl;goto menu;default :cout您選擇的操作非法！next=NULL)cout鏈表未創(chuàng)建，插入失??！endlendl;goto menu;Insert:cout插入操作有：1.按有序插入endl;cout 2.按位置插入endl;cout 3.退出插入操作endl;cout請選擇相應(yīng)的操作： ;switch(JudgeOperation()case 1:cout請輸入要插入的元素： ;item=JudgeData();InsertList(h,item,0);goto Insert;case 2:cout請輸入要插入的位置： ;pos=JudgeData();cout請輸入要插入的元素（在末尾插入請鍵入-1）： ;item=JudgeData();InsertList(h,item,pos);goto Insert;case 3:coutendl;goto menu;default:cout您選擇的操作非法！next=NULL)cout鏈表未創(chuàng)建，刪除失??！endlendl;goto menu;Delete:cout刪除操作有：1.按元素刪除endl;cout 2.按位置刪除endl;cout 3.退出刪除操作endl;cout請選擇相應(yīng)的操作： ;switch(JudgeOperation()case 1:cout請輸入您想要刪除的元素：; item=JudgeData();DeleteList(h,item,0);goto Delete;case 2:cout請輸入您想要刪除元素的位置（刪除末尾元素請鍵入-1）： ;pos=JudgeData();DeleteList(h,0,pos);goto Delete;case 3:coutendl;goto menu;default:cout您選擇的操作非法！next=NULL)cout鏈表未創(chuàng)建，請先創(chuàng)建！endlendl;goto menu;DisplayList(h);coutnext=NULL)cout鏈表未創(chuàng)建，排序失??！endlendl;goto menu;SortList(h);Disp