數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告順序表的創(chuàng)建遍歷及有序合并操作優(yōu)質(zhì)資料

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-順序表的創(chuàng)建遍歷及有序合并操作優(yōu)質(zhì)資料(可以直接使用，可編輯優(yōu)質(zhì)資料，歡迎下載）

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-順序表的創(chuàng)建、遍歷及有序合并操作數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-順序表的創(chuàng)建遍歷及有序合并操作優(yōu)質(zhì)資料(可以直接使用，可編輯優(yōu)質(zhì)資料，歡迎下載）二、實(shí)驗(yàn)內(nèi)容與步驟實(shí)現(xiàn)順序表的創(chuàng)建、遍歷及有序合并操作，基本數(shù)據(jù)結(jié)構(gòu)定義如下：typedefintElemType;#defineMAXSIZE100#defineFALSE0#defineTRUE1typedefstruct{ElemTypedata[MAXSIZE];intlength;}seqlist;創(chuàng)建順序表，遍歷順序表#include<stdio.h>#include<stdlib.h>#defineMAXSIZE100#defineIcreament20#defineFALSE0#defineTRUE1typedefintElemType;//用戶自定義數(shù)據(jù)元素類型//順序表結(jié)構(gòu)體的定義typedefstruct{ElemType*elem;//順序表的基地址intlength;//順序表的當(dāng)前長度intlistsize;//預(yù)設(shè)空間容量}SqList;//線性表的順序存儲(chǔ)結(jié)構(gòu)SqList*InitList()//創(chuàng)建空的順序表{SqList*L=(SqList*)malloc(sizeof(SqList));//定義順序表Lif(!L){printf("空間劃分失敗，程序退出\n");returnNULL;}L->elem=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));if(!L->elem){printf("空間劃分失敗，程序退出\n");returnNULL;}L->length=0;L->listsize=MAXSIZE;returnL;}intCreateList(SqList*L)//創(chuàng)建順序表（非空）{intnumber;//順序表中元素的個(gè)數(shù)inti;//循環(huán)變量printf("請(qǐng)輸入順序表中元素的個(gè)數(shù)：");scanf("%d",&number);if(number>MAXSIZE)//一定要判斷輸入的個(gè)數(shù)是否大于順序表的最大長度{printf("輸入個(gè)數(shù)大于順序表的長度\n");return0;}for(i=0;i<number;i++){printf("輸入第%d個(gè)數(shù):",i+1);scanf("%d",L->elem+i);//L->elem+i：每次的輸入都保存在順序表元素中的下一個(gè)地址，而不是一直放在元素的首地址}//給順序表中每個(gè)數(shù)據(jù)元素賦值L->length=number;//當(dāng)前順序表的長度return1;}voidprint(SqList*L)//遍歷順序表{inti; printf("\n開始遍歷順序表\n");for(i=0;i<L->length;i++){printf("%d",*(L->elem+i));//L->elem+i：和輸入是一個(gè)道理} printf("\n遍歷結(jié)束\n");printf("\n");}intmain(){SqList*L=InitList();//申請(qǐng)一個(gè)指向順序表的指針，并對(duì)其初始化if(!L)//判斷申請(qǐng)是否成功{printf("初始化線性表失敗\n");return1;}if(!CreateList(L))//判斷創(chuàng)建順序表是否成功{printf("創(chuàng)建順序表失敗\n");return1;}print(L);//打印順序表與上面遍歷順序表相對(duì)應(yīng)，若沒有就不遍歷free(L->elem);//釋放申請(qǐng)的順序表元素的內(nèi)存free(L);//釋放申請(qǐng)的順序表內(nèi)存return0;}表的有序合并#include<stdio.h>#include<stdlib.h>#defineMAXSIZE100typedefintElemType;//順序表結(jié)構(gòu)體的定義typedefstruct{ ElemTypedata[MAXSIZE]; intsize;}seqlist;//函數(shù)聲明voidinit(seqlist*slt);voiddisplay(seqlistslt);voidsort(seqlist*s);voidcombine(seqlist*s1,seqlist*s2,seqlist*s3);//順序表的初始化函數(shù)voidinit(seqlist*slt){ slt->size=0;}//順序表的顯示函數(shù)voiddisplay(seqlistslt){ inti; if(!slt.size) { printf("\n順序表為空"); } else {for(i=0;i<slt.size;i++) printf("\n%d\n",slt.data[i]); }}//順序表排序voidsort(seqlist*s){ inti; intj; inttemp; for(i=0;i<s->size-1;i++) { for(j=i+1;j<s->size;j++) { if(s->data[i]>=s->data[j]) { temp=s->data[i]; s->data[i]=s->data[j]; s->data[j]=temp; } } }}//兩個(gè)有序順序表連接函數(shù)voidcombine(seqlist*s1,seqlist*s2,seqlist*s3){ int i=0; intj=0; intk=0; while(i<s1->size&&j<s2->size) { if(s1->data[i]<=s2->data[j]) { s3->data[k]=s1->data[i]; i++; } else { s3->data[k]=s2->data[j]; j++; } k++; } if(i==s1->size) { while(j<s2->size) { s3->data[k]=s2->data[j]; k++; j++; } } if(j==s2->size) { while(i<s1->size) { s3->data[k]=s1->data[i]; k++; i++; } } s3->size=k;}//主函數(shù)intmain(){ inti; intj; intx; intn; seqlistlist1; seqlistlist2; seqlistlist3; init(&list1); printf("第一個(gè)順序表元素個(gè)數(shù)：\n"); scanf("%d",&n); printf("第一個(gè)順序表輸入：\n"); for(i=0;i<n;i++) { scanf("%d",&list1.data[i]); list1.size++; } sort(&list1);//第一個(gè)表排序 init(&list2); printf("第二個(gè)順序表元素個(gè)數(shù)：\n"); scanf("%d",&n); printf("第二個(gè)順序表輸入：\n"); for(i=0;i<n;i++) { scanf("%d",&list2.data[i]); list2.size++; } sort(&list2);//第二個(gè)表排序 init(&list3); combine(&list1,&list2,&list3); printf("表一與表二連接后:\n"); display(list3); return0;}洛陽理工學(xué)院實(shí)驗(yàn)報(bào)告系別計(jì)算機(jī)系班級(jí)學(xué)號(hào)姓名課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)日期11.7實(shí)驗(yàn)名稱鏈表的基本操作成績實(shí)驗(yàn)?zāi)康模菏煜ふ莆站€性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，掌握與應(yīng)用查找、插入、刪除等基本操作算法，訓(xùn)練和提高結(jié)構(gòu)化程序設(shè)計(jì)能力及程序調(diào)試能力。實(shí)驗(yàn)條件：計(jì)算機(jī)一臺(tái)，VisualC++6.0實(shí)驗(yàn)內(nèi)容：問題描述以單鏈表為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)以下基本操作：在第i個(gè)元素前插入一個(gè)新元素。查找值為x的某個(gè)元素。若成功，給出x在表中的位置；不成功給出提示信息。刪除第i個(gè)元素，若成功，給出提示信息并顯示被刪元素的值；不成功給出失敗的提示信息。數(shù)據(jù)結(jié)構(gòu)類型定義typedefstructLinkNode{ intValue; structLinkNode*Next;}Node,*LinkList;模塊劃分（1）初始化鏈表：voidInitList(LinkList*L);（2）創(chuàng)建鏈表:尾插法：intCreateFromTail(LinkListL);（3）在指定位置插入元素：intInsList(LinkListL,inti,inte);（4）在指定位置刪除元素：intDelList(LinkListL,inti,int*e);返回值說明：返回ERROR插入失敗，返回OK插入成功;（5）按位置查找鏈表元素：intGetList(LinkListL,inti,int*e);詳細(xì)設(shè)計(jì)voidinit_linklist(LinkList*l)/*對(duì)單鏈表進(jìn)行初始化*/{ *l=(LinkList)malloc(sizeof(Node));/*申請(qǐng)結(jié)點(diǎn)空間*/ (*l)->next=NULL;/*置為空表*/}voidCreateFromHead(LinkListL){ Node*s; char c; int flag=1; while(flag)/*flag初值為1，當(dāng)輸入"$"時(shí)，置flag為0，建表結(jié)束*/ { c=getchar(); if(c!='$') { s=(Node*)malloc(sizeof(Node));/*建立新結(jié)點(diǎn)s*/ s->data=c; s->next=L->next;/*將s結(jié)點(diǎn)插入表頭*/ L->next=s; } else flag=0; }}voidCreateFromTail(LinkListL){ Node*r,*s; charc; intflag=1;/*設(shè)置一個(gè)標(biāo)志，初值為1，當(dāng)輸入"$"時(shí)，flag為0，建表結(jié)束*/ r=L;/*r指針動(dòng)態(tài)指向鏈表的當(dāng)前表尾，以便于做尾插入，其初值指向頭結(jié)點(diǎn)*/ while(flag)/*循環(huán)輸入表中元素值，將建立新結(jié)點(diǎn)s插入表尾*/ { c=getchar(); if(c!='$') { s=(Node*)malloc(sizeof(Node)); s->data=c; r->next=s; r=s; } else { flag=0; r->next=NULL;/*將最后一個(gè)結(jié)點(diǎn)的next鏈域置為空，表示鏈表的結(jié)束*/ } }}Node*Get(LinkListL,inti)/*在帶頭結(jié)點(diǎn)的單鏈表L中查找第i個(gè)結(jié)點(diǎn)，若找到(1≤i≤n)，則返回該結(jié)點(diǎn)的存儲(chǔ)位置;否則返回NULL*/{ intj; Node*p; p=L; j=0;/*從頭結(jié)點(diǎn)開始掃描*/ while((p->next!=NULL)&&(j<i)) { p=p->next;/*掃描下一結(jié)點(diǎn)*/ j++;/*已掃描結(jié)點(diǎn)計(jì)數(shù)器*/ } if(i==j) returnp;/*找到了第i個(gè)結(jié)點(diǎn)*/ else returnNULL;/*找不到，i≤0或i>n*/}Node*Locate(LinkListL,ElemTypekey)/*在帶頭結(jié)點(diǎn)的單鏈表L中查找其結(jié)點(diǎn)值等于key的結(jié)點(diǎn)，若找到則返回該結(jié)點(diǎn)的位置p，否則返回NULL*/{ Node*p; p=L->next;/*從表中第一個(gè)結(jié)點(diǎn)開始*/ while(p!=NULL) { if(p->data!=key) p=p->next; else break;/*找到結(jié)點(diǎn)值=key時(shí)退出循環(huán)*/ } returnp;}intInsList(LinkListL,inti,ElemTypee)/*在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)位置插入值為e的新結(jié)點(diǎn)s*/{ Node*pre,*s; intk; pre=L; k=0;/*從"頭"開始，查找第i-1個(gè)結(jié)點(diǎn)*/ while(pre!=NULL&&k<i-1)/*表未查完且未查到第i-1個(gè)時(shí)重復(fù)，找到pre指向第i-1個(gè)*/ { pre=pre->next; k=k+1; } /*查找第i-1結(jié)點(diǎn)*/ if(!pre)/*如當(dāng)前位置pre為空表已找完還未數(shù)到第i個(gè)，說明插入位置不合理*/ { printf("插入位置不合理!"); returnERROR; } s=(Node*)malloc(sizeof(Node));/*申請(qǐng)一個(gè)新的結(jié)點(diǎn)S*/ s->data=e;/*值e置入s的數(shù)據(jù)域*/ s->next=pre->next; /*修改指針，完成插入操作*/ pre->next=s; returnOK;}intDelList(LinkListL,inti,ElemType*e)/*在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個(gè)元素，并將刪除的元素保存到變量*e中*/{ Node*pre,*r; intk; pre=L; k=0; while(pre->next!=NULL&&k<i-1) /*尋找被刪除結(jié)點(diǎn)i的前驅(qū)結(jié)點(diǎn)i-1使p指向它*/ { pre=pre->next; k=k+1; } /*查找第i-1個(gè)結(jié)點(diǎn)*/ if(!(pre->next))/*即while循環(huán)是因?yàn)閜->next=NULL或i<1而跳出的,而是因?yàn)闆]有找到合法的前驅(qū)位置，說明刪除位置i不合法。*/ { printf("刪除結(jié)點(diǎn)的位置i不合理!"); returnERROR; } r=pre->next; pre->next=pre->next->next;/*修改指針，刪除結(jié)點(diǎn)r*/ *e=r->data; free(r);/*釋放被刪除的結(jié)點(diǎn)所占的內(nèi)存空間*/ printf("成功刪除結(jié)點(diǎn)!"); returnOK;}int ListLength(LinkListL)/*求帶頭結(jié)點(diǎn)的單鏈表L的長度*/{ Node*p; intj; p=L->next; j=0;/*用來存放單鏈表的長度*/ while(p!=NULL) { p=p->next; j++; } returnj; /*j為求得的單鏈表長度*/}5.測試數(shù)據(jù)及結(jié)果實(shí)驗(yàn)總結(jié)：在調(diào)試的時(shí)候發(fā)現(xiàn)在頭插法的時(shí)候出現(xiàn)錯(cuò)誤，經(jīng)過邏輯思考與調(diào)試，發(fā)現(xiàn)錯(cuò)誤所在，并且更改。HUNAN課程實(shí)習(xí)報(bào)告題目：哈希表學(xué)生姓名唐鵬學(xué)生學(xué)號(hào)202108080216專業(yè)班級(jí)物聯(lián)2班指導(dǎo)老師吳帆2021年4月2日本程序來自于圖書館靠書名來檢索想要查找的書問題。本程序要求：（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ù)來說稱做同義詞。*綜上所述，根據(jù)散列函數(shù)H(key）和處理沖突的方法將一組關(guān)鍵字映象到一個(gè)有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“象”，作為這條記錄在表中的存儲(chǔ)位置，這種表便稱為散列表，這一映象過程稱為散列造表或散列，所得的存儲(chǔ)位置稱散列地址。這個(gè)現(xiàn)象也叫散列桶，在散列桶中，只能通過順序的方式來查找，一般只需要查找三次就可以找到?？茖W(xué)家計(jì)算過，當(dāng)負(fù)載因子(loadfactor)不超過75%，查找效率最高。*若對(duì)于關(guān)鍵字集合中的任一個(gè)關(guān)鍵字，經(jīng)散列函數(shù)映象到地址集合中任何一個(gè)地址的概率是相等的，則稱此類散列函數(shù)為均勻散列函數(shù)（UniformHashfunction），這就是使關(guān)鍵字經(jīng)過散列函數(shù)得到一個(gè)“隨機(jī)的地址”，從而減少?zèng)_突。程序設(shè)計(jì)流程程序思想哈希函數(shù)unsignedinthash_BKDE(char*str)生成映射地址，成為散列表的編號(hào)。哈希表HashTable::HashTable()通過數(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)//插入到哈希表{ unsignedintpo