單鏈表實(shí)驗(yàn)報(bào)告優(yōu)質(zhì)資料(可以直接使用，可編輯優(yōu)質(zhì)資料，歡迎下載）

計(jì)算機(jī)與信息技術(shù)學(xué)院綜合性、設(shè)計(jì)性實(shí)驗(yàn)報(bào)告單鏈表實(shí)驗(yàn)報(bào)告優(yōu)質(zhì)資料(可以直接使用，可編輯優(yōu)質(zhì)資料，歡迎下載）專業(yè)：網(wǎng)絡(luò)工程年級(jí)/班級(jí)：大二2021—2021學(xué)年第一學(xué)期課程名稱數(shù)據(jù)結(jié)構(gòu)指導(dǎo)教師李四學(xué)號(hào)姓名16083240XX張三項(xiàng)目名稱單鏈表的基本操作實(shí)驗(yàn)類型綜合性/設(shè)計(jì)性實(shí)驗(yàn)時(shí)間實(shí)驗(yàn)地點(diǎn)216機(jī)房實(shí)驗(yàn)?zāi)康模?）熟悉順序表的創(chuàng)建、取值、查找、插入、刪除等算法，模塊化程序設(shè)計(jì)方法。實(shí)驗(yàn)儀器或設(shè)備（1）硬件設(shè)備：CPU為Pentium4以上的計(jì)算機(jī)，內(nèi)存2G以上（2）配置軟件：MicrosoftWindows7與VC++6.0總體設(shè)計(jì)（設(shè)計(jì)原理、設(shè)計(jì)方案及流程等）設(shè)計(jì)原理：?jiǎn)捂湵韺儆诰€性表，線性表的存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是：用一組任意存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。因此，對(duì)于某個(gè)元素來(lái)說(shuō)，不僅需要存儲(chǔ)其本身的信息，還需要存儲(chǔ)一個(gè)指示其直接后繼的信息。設(shè)計(jì)方案：采用模塊化設(shè)計(jì)的方法，設(shè)計(jì)各個(gè)程序段，最終通過(guò)主函數(shù)實(shí)現(xiàn)各個(gè)程序段的功能。設(shè)計(jì)時(shí)，需要考慮用戶輸入非法數(shù)值，所以要在程序中寫入說(shuō)可以處理非法數(shù)值的代碼。設(shè)計(jì)流程：引入所需的頭文件；定義狀態(tài)值；寫入順序表的各種操作的代碼；寫入主函數(shù)，分別調(diào)用各個(gè)函數(shù)。在調(diào)用函數(shù)時(shí)，采用if結(jié)構(gòu)進(jìn)行判斷輸入值是否非法，從而執(zhí)行相應(yīng)的程序?qū)嶒?yàn)步驟（包括主要步驟、代碼分析等）#include<stdio.h>//EOF(=^Z或F6),NULL#include<stdlib.h>//srand(),rand(),exit(n)#include<malloc.h>//malloc(),alloc(),realloc()等#include<limits.h>//INT_MAX等#include<string.h>#include<ctype.h>#include<math.h>//floor(),ceil(),abs()#include<iostream.h>//cout,cin#include<time.h>//clock(),CLK_TCK,clock_t#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;//Status是函數(shù)的類型,//其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等typedefintElemType;typedefstructLNode{ElemTypedata;//結(jié)點(diǎn)的數(shù)據(jù)域structLNode*next;//結(jié)點(diǎn)的指針域}LNode,*LinkList;//LinkList為指向結(jié)構(gòu)體LNode的指針類型//初始化單鏈表算法步驟：生成新結(jié)點(diǎn)作為頭結(jié)點(diǎn)，用頭指針L指向頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的指針域置空。StatusInitList_L(LinkList&L){ L=newLNode; //生成新結(jié)點(diǎn)作為頭結(jié)點(diǎn)，用頭指針L指向頭結(jié)點(diǎn)； L->next=NULL; //頭結(jié)點(diǎn)的指針域置空returnOK;}//單鏈表的取值算法步驟：用指針P指首元結(jié)點(diǎn)，用j做計(jì)數(shù)器初值賦為1.從首元結(jié)點(diǎn)開始依次順著鏈域next向下訪問(wèn)，只要指向當(dāng)前結(jié)點(diǎn)的指針p不為空（NULL），并且沒有到達(dá)序號(hào)為i的結(jié)點(diǎn)，則循環(huán)執(zhí)行以下操作：P指向下一結(jié)點(diǎn)；計(jì)數(shù)器j相應(yīng)加1；3.退出循環(huán)時(shí)，如果指針p為空，或者計(jì)數(shù)器j大于i，說(shuō)明指定的序號(hào)i值不合法（i大于表長(zhǎng)n或i小于等于0），取值失敗返回ERROR，否則取值成功，此時(shí)j=i時(shí)，p所指的結(jié)點(diǎn)就是要找的第i個(gè)結(jié)點(diǎn)，用參數(shù)e保存當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域，返回OK。StatusGetElem_L(LinkListL,inti,ElemType&e){LinkListp;intj; p=L->next; j=1;while(p&&j<i) { p=p->next; ++j; }if(!p||j>i)returnERROR; e=p->data;returnOK;}//單鏈表的按值查找算法步驟：用指針p指首元結(jié)點(diǎn)。從首元結(jié)點(diǎn)開始依次順著鏈域next向下查找，只要指向當(dāng)前結(jié)點(diǎn)的指針p不為空，并且p所指結(jié)點(diǎn)的數(shù)據(jù)域不等于給定值e，則循環(huán)執(zhí)行以下操作：p指向下一個(gè)結(jié)點(diǎn)。返回p。若查找成功，p此時(shí)即為結(jié)點(diǎn)的地址值，若查找失敗，p的值即為NULL。intLocateElem_L(LinkListL,ElemTypee){LinkListp;intj; p=L->next; j=1;while(p&&p->data!=e) { p=p->next;j++; }if(p)returnj;elsereturn0;}//單鏈表的插入算法步驟：查找結(jié)點(diǎn)ai-1并由指針p指向該結(jié)點(diǎn)。生成一個(gè)新結(jié)點(diǎn)*s。將新結(jié)點(diǎn)*s的數(shù)據(jù)域置為e。將新結(jié)點(diǎn)*s的指針域指向結(jié)點(diǎn)ai。將結(jié)點(diǎn)*p的指針域指向新結(jié)點(diǎn)*s。StatusListInsert_L(LinkList&L,inti,ElemTypee){LinkListp=L,s;intj=0;while(p&&(j<i-1)) { p=p->next; ++j; }if(!p||j>i-1) {returnERROR; } s=newLNode;s->data=e;s->next=p->next;p->next=s;returnOK;}//單鏈表的刪除查找結(jié)點(diǎn)ai-1并由指針p指向該結(jié)點(diǎn)。臨時(shí)保存待刪除結(jié)點(diǎn)ai的地址在q中，以備釋放。將結(jié)點(diǎn)*p的指針域指向ai的直接后繼結(jié)點(diǎn)。釋放結(jié)點(diǎn)ai的空間。StatusListDelete_L(LinkList&L,inti){LinkListp=L,q;intj=0;while((p->next)&&(j<i-1)) { p=p->next; ++j; }if((!p->next)||(j>i-1)) {returnERROR; } q=p->next;p->next=q->next;deleteq;returnOK;}//單鏈表的輸出算法步驟：將指針p指向L的next域。輸出p指針的數(shù)據(jù)。將指針p后移。循環(huán)第2,3步，直到p指針為空（NULL）。voidListPrint_L(LinkListL){LinkListp; p=L->next;do {printf("%5d",p->data); p=p->next;}while(p);}voidmain(){inti,n,e;LinkListL;if(InitList_L(L));printf("單鏈表創(chuàng)建成功！\n");printf("請(qǐng)輸入您要輸入的數(shù)據(jù)個(gè)數(shù)n:\n");scanf("%d",&n);printf("請(qǐng)輸入您要輸入的數(shù)據(jù)：\n");for(i=1;i<=n;i++) {scanf("%d",&e);ListInsert_L(L,i,e); }printf("當(dāng)前單鏈表的內(nèi)容為：\n");ListPrint_L(L);printf("\n");printf("請(qǐng)輸入您要插入的數(shù)據(jù)e及其位置i，使用空格鍵隔開:\n");scanf("%d%d",&e,&i);if(ListInsert_L(L,i,e)) {printf("當(dāng)前單鏈表的內(nèi)容為：\n");ListPrint_L(L); }else {printf("i值越界！\n"); }printf("\n");printf("請(qǐng)輸入您要取的數(shù)據(jù)序號(hào)：\n");scanf("%d",&i);if(GetElem_L(L,i,e)) {printf("第%d位數(shù)據(jù)的值為:%d\n",i,e); }else {printf("i值越界！\n"); }printf("請(qǐng)輸入要查找的數(shù)據(jù)值：\n");scanf("%d",&e);if(!LocateElem_L(L,e)) {printf("查無(wú)此值!\n"); }else {printf("數(shù)據(jù)%d在%d號(hào)位置\n",e,LocateElem_L(L,e)); }printf("請(qǐng)輸入要?jiǎng)h除的數(shù)據(jù)的序號(hào)：\n");scanf("%d",&i);if(ListDelete_L(L,i)) {printf("刪除后單鏈表的內(nèi)容為：\n");ListPrint_L(L); }else {printf("輸入有誤！"); }printf("\n");}結(jié)果分析與總結(jié)圖1結(jié)果分析：如圖1所示，輸入正確數(shù)據(jù)時(shí)，程序各個(gè)功能執(zhí)行正常。設(shè)置輸入數(shù)據(jù)個(gè)數(shù)為5，可以輸入5個(gè)數(shù)據(jù)，按回車后，可以顯示我們當(dāng)前單鏈表中的數(shù)據(jù)內(nèi)容。繼續(xù)輸入下一指令：輸入要插入的數(shù)據(jù)及位置，使用空格鍵隔開，回車后，可以看到已經(jīng)成功插入。繼續(xù)輸入所取的數(shù)據(jù)序號(hào)，可以查找該數(shù)據(jù)的值。輸入要查找的數(shù)據(jù)，可以返回該數(shù)據(jù)的位置。輸入要?jiǎng)h除的數(shù)據(jù)，可以返回刪除該元素后的單鏈表的內(nèi)容?？偨Y(jié)：在單鏈表中，對(duì)數(shù)據(jù)元素ai來(lái)說(shuō)，除了存儲(chǔ)其本身的信息之外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息。這兩部分信息組成數(shù)據(jù)元素ai的存儲(chǔ)映像，稱為結(jié)點(diǎn)。它包括兩個(gè)域；其中存儲(chǔ)數(shù)據(jù)元素的域稱為數(shù)據(jù)域；存儲(chǔ)直接后繼的域稱為指針域。教師簽名：年月日HUNAN課程實(shí)習(xí)報(bào)告題目：哈希表學(xué)生姓名唐鵬學(xué)生學(xué)號(hào)202108080216專業(yè)班級(jí)物聯(lián)2班指導(dǎo)老師吳帆2021年4月2日本程序來(lái)自于圖書館靠書名來(lái)檢索想要查找的書問(wèn)題。本程序要求：（1）根據(jù)輸入建立圖書名稱表，采用創(chuàng)建散列表實(shí)現(xiàn)。（2）建散列表后，如果想要查找的數(shù)據(jù)在散列表中輸出yes否則輸出no。結(jié)構(gòu)中存在關(guān)鍵字和K相等的記錄，則必定存儲(chǔ)在f(K）的位置上。由此，不需比較便可直接取得所查記錄。這個(gè)對(duì)應(yīng)關(guān)系f稱為散列函數(shù)(Hashfunction），按這個(gè)思想建立的表為散列表。*對(duì)不同的關(guān)鍵字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2），這種現(xiàn)象稱沖突。具有相同函數(shù)值的關(guān)鍵字對(duì)該散列函數(shù)來(lái)說(shuō)稱做同義詞。*綜上所述，根據(jù)散列函數(shù)H(key）和處理沖突的方法將一組關(guān)鍵字映象到一個(gè)有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“象”，作為這條記錄在表中的存儲(chǔ)位置，這種表便稱為散列表，這一映象過(guò)程稱為散列造表或散列，所得的存儲(chǔ)位置稱散列地址。這個(gè)現(xiàn)象也叫散列桶，在散列桶中，只能通過(guò)順序的方式來(lái)查找，一般只需要查找三次就可以找到。科學(xué)家計(jì)算過(guò)，當(dāng)負(fù)載因子(loadfactor)不超過(guò)75%，查找效率最高。*若對(duì)于關(guān)鍵字集合中的任一個(gè)關(guān)鍵字，經(jīng)散列函數(shù)映象到地址集合中任何一個(gè)地址的概率是相等的，則稱此類散列函數(shù)為均勻散列函數(shù)（UniformHashfunction），這就是使關(guān)鍵字經(jīng)過(guò)散列函數(shù)得到一個(gè)“隨機(jī)的地址”，從而減少?zèng)_突。程序設(shè)計(jì)流程程序思想哈希函數(shù)unsignedinthash_BKDE(char*str)生成映射地址，成為散列表的編號(hào)。哈希表HashTable::HashTable()通過(guò)數(shù)組儲(chǔ)存元素插入函數(shù)voidHashTable::insert(char*c)插入字符串，先計(jì)算要插入字符串生成的映射地址，然后在相應(yīng)的地址插入，如果沒有空位查找空位插入。查找函數(shù)boolHashTable::find(char*c)進(jìn)行查找，先計(jì)算要生成字符串的地址，再到散列表中進(jìn)行查找比較。主函數(shù)main（）輸入：輸入散列表內(nèi)容和要查找的數(shù)據(jù)個(gè)數(shù)和數(shù)據(jù)輸出模塊：散列表查找的結(jié)果。建散列表并查找：建立散列表并遞歸查找流程圖三.實(shí)驗(yàn)源程序：#include<iostream>#include<cstdlib>#include<ctime>usingnamespacestd;unsignedinthash_BKDE(char*str)//哈希函數(shù)，題目給出{//初始種子seed可取31131131313131131313etc.. unsignedintseed=131; unsignedinthash=0; while(*str) { hash=hash*seed+(*str++); } return(hash&0x7FFFFFFF);}doublek=(double)(rand()%999)/1000;//隨機(jī)生成小數(shù)隨機(jī)數(shù)0<k<1unsignedinthash_rand(unsignedintvalue)//value<2^32，將轉(zhuǎn)化地址轉(zhuǎn)化為seed{ doublea=k*value; doublen=(a-(int)a)*64;//取小數(shù)部分與2^5相乘 unsignedintseed=(int)n; returnseed;}unsignedintHash(char*str)//生成最終的地址映射即計(jì)算散列地址位置{ returnhash_rand(hash_BKDE(str));}classHashTable//哈希表類{public:HashTable();~HashTable();voidinsert(char*c);boolfind(char*c);private:char**Arr;//二維數(shù)組用于保存字符串書名intArrSize;//散列表單元個(gè)數(shù)在此為2^15=32768};HashTable::HashTable(){ ArrSize=32768; Arr=newchar*[64]; for(inti=0;i<64;i++) { Arr[i]=newchar[100]; Arr[i]=NULL; }}HashTable::~HashTable(){ for(inti=0;i<64;i++) delete[]Arr[i]; delete[]Arr;}voidHashTable::insert(char*c)//插入到哈希表{ unsignedintpos=Hash(c);//計(jì)算散列地址位置 while(Arr[pos]!=NULL) pos=(pos+1);//解決沖突的辦法，尋找空位，向后面挪動(dòng)一個(gè) Arr[pos]=c;//插入存儲(chǔ)}boolHashTable::find(char*c)//查找{ unsignedintpos=Hash(c);//計(jì)算散列地址 while(Arr[pos]!=NULL)//非空時(shí)進(jìn)行查找比較 { if(Arr[pos]==c)returntrue; pos=(pos+1);//尋找下一地址，如果運(yùn)行這一步，這說(shuō)明之前產(chǎn)生了沖突 } returnfalse;}intmain(){ boola[20]; char*c1=newchar[100]; HashTableH; cout<<"輸入字符串個(gè)數(shù)n：\n"; intn; cin>>n; cout<<"輸入n個(gè)字符串：\n"; for(inti=1;i<=n;i++) { cin>>c1; H.insert(c1);//直接插入到散列表的數(shù)組中 } cout<<"輸入待查的字符串個(gè)數(shù)m：\n"; intm; cin>>m; cout<<"輸入要查找的字符串:"<<endl; for(intj=0;j<m;j++) { cin>>c1; a[j]=H.find(c1);//bool量 } cout<<"查找結(jié)果(yes表示存在，no表示不存在)：\n"; for(intk=0;k<m;k++) if(a[k]) cout<<"yes\n"; else cout<<"No\n"; return0;}四、實(shí)驗(yàn)截圖五、實(shí)驗(yàn)感想本次