數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)

第5頁共5頁數(shù)據(jù)構(gòu)造實(shí)驗(yàn)實(shí)驗(yàn)一、約瑟夫環(huán)問題實(shí)驗(yàn)?zāi)康?〕掌握線性表的存儲(chǔ)構(gòu)造；2〕學(xué)會(huì)利用線性表解決實(shí)際問題。實(shí)驗(yàn)內(nèi)容編號(hào)為1，2，┅，n的n個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)密碼〔正整數(shù)〕。一開場任選一個(gè)密碼m，從第一個(gè)人開場按順時(shí)針方向自1開場順序報(bào)數(shù)，報(bào)到m時(shí)停頓報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向上的下一個(gè)人開場重新從1順序報(bào)數(shù)，如此下去，直到所有人全部出列為止。實(shí)驗(yàn)要求1〕建立模型模擬約瑟夫環(huán)問題，確定存儲(chǔ)構(gòu)造，用單鏈表實(shí)現(xiàn)；2〕輸入m的初值，人數(shù)n，輸入每個(gè)人的密碼；出圈的順序請(qǐng)依次輸出。數(shù)據(jù)構(gòu)造分析^p由于約瑟夫環(huán)問題本身具有循環(huán)性質(zhì)，考慮采用循環(huán)鏈表。鏈表的每個(gè)結(jié)點(diǎn)有兩個(gè)域，分別是序號(hào)和其所持有的密碼。建立單鏈表后，根據(jù)算法找到相應(yīng)的結(jié)點(diǎn)，對(duì)找到的結(jié)點(diǎn)進(jìn)展輸出，并把該結(jié)點(diǎn)從鏈表中刪除，再釋放該結(jié)點(diǎn)空間。實(shí)驗(yàn)程序#include//實(shí)驗(yàn)數(shù)據(jù):總?cè)藬?shù)：6初始密碼：18個(gè)人密碼：2,1,4,2,4,8#include//出圈順序：6,3,2,4,1,5typedefstructLNode{intid,password;structLNode*next;}LNode,*LinkList;voidmain{intn,m,e,i,Flag=1;LinkListL,p,q,s;printf(“請(qǐng)輸入總?cè)藬?shù)n：n”);scanf(“%d”,&n);printf(“請(qǐng)輸入初始密碼m：n”);scanf(“%d”,&m);for(i=1;i1鏈接結(jié)點(diǎn)printf(“請(qǐng)輸入第%d個(gè)人的密碼：n”,i);scanf(“%d”,&e);s->id=i;s->passwoed=e;p->next=s;p=s;}s->next=L;//構(gòu)成循環(huán)鏈表p=q=L;//約瑟夫環(huán)問題報(bào)數(shù)，依次出列while(Flag){printf(“出圈順序依次為：n”);for(i=1;inext;}//搜索第m個(gè)人if(p==q)Flag=0;//表示全部查找完畢s=p;//找到第m個(gè)人出列q->next=p->next;p=p->next;//指出下一次第一個(gè)要報(bào)數(shù)的人m=s->password;//更新m值printf(“第%d個(gè)人出列，密碼：%dn”,s->id,s->password);free(s);}}實(shí)驗(yàn)二、數(shù)制轉(zhuǎn)換和漢諾塔實(shí)驗(yàn)?zāi)康?〕掌握棧的邏輯構(gòu)造和物理存儲(chǔ)構(gòu)造；2〕學(xué)會(huì)利用棧的特點(diǎn)解決實(shí)際問題。實(shí)驗(yàn)內(nèi)容1〕將一個(gè)非負(fù)的十進(jìn)制數(shù)n轉(zhuǎn)換成d〔范圍2~36〕進(jìn)制數(shù)。2〕實(shí)現(xiàn)m〔不超過10〕層的三柱漢諾塔挪動(dòng)方案。實(shí)驗(yàn)要求1〕輸入n和d，確定存儲(chǔ)構(gòu)造，輸出d進(jìn)制數(shù)，大于10的數(shù)，用對(duì)應(yīng)的英文字母表示；2〕輸入m值，輸出漢諾塔挪動(dòng)步驟。數(shù)據(jù)構(gòu)造分析^p上述兩個(gè)問題，可以利用棧的后進(jìn)先出特性解決，用遞歸法來編寫程序。實(shí)驗(yàn)程序#includevoidconversion(intn,intd)//十進(jìn)制轉(zhuǎn)換為d進(jìn)制{if(nvoidhanoi(intm,charx,chary,charz)//漢諾塔，將塔座x上m個(gè)圓盤按規(guī)那么，{//通過塔座y，搬動(dòng)到塔座z。if(n==1)printf(“把%d號(hào)圓盤從塔座%c移到塔座%cn”,1,x,z);else{hanoi(n-1,x,z,y);printf(“把%d號(hào)圓盤從塔座%c移到塔座%cn”,n,x,z);hanoi(n-1,y,x,z);}}voidmain{intm;charx=?X?,y=?Y?,z=?Z?;printf(“請(qǐng)輸入漢諾塔圓盤數(shù)目，不超過10n”);scanf(“%d”,&m);hanoi(m,x,y,z);}實(shí)驗(yàn)三、串的形式匹配實(shí)驗(yàn)?zāi)康?〕熟悉和理解串的邏輯構(gòu)造和物理存儲(chǔ)構(gòu)造；2〕學(xué)會(huì)利用KMP算法驗(yàn)證字符串的形式匹配。實(shí)驗(yàn)內(nèi)容輸入主串S和形式串T，用堆分配存儲(chǔ)方式存儲(chǔ)串，并將串S和串T輸出；然后計(jì)算形式串T的next函數(shù)，并將計(jì)算結(jié)果輸出；最后進(jìn)展形式匹配，輸出從主串S的第1個(gè)字符起，主串S和形式串T首次匹配的字符位置。實(shí)驗(yàn)要求1〕輸入主串S和形式串T；2〕采用克努特—莫里斯—普拉特〔簡稱KMP算法〕，實(shí)現(xiàn)形式匹配。數(shù)據(jù)構(gòu)造分析^p當(dāng)主串S中第i個(gè)字符與形式串T中第j個(gè)字符“失配”時(shí)，考慮主串中第i個(gè)字符〔i指針不回溯〕應(yīng)與形式串T中哪個(gè)字符比擬。通過對(duì)形式匹配過程特點(diǎn)的分析^p，對(duì)形式串T構(gòu)造next函數(shù)，設(shè)形式串中某個(gè)字符的next函數(shù)值為k，那么當(dāng)“失配”發(fā)生時(shí)，匹配僅需從形式中第k個(gè)字符與主串S中第i個(gè)字符比擬起繼續(xù)進(jìn)展。實(shí)驗(yàn)程序#include#includeintIndex_KMP(char*S,char*T,intpos){inti,j,next[20];i=0;j=-1;next[0]=0;while(istrlen(T))returni-strlen(T);elsereturn-1;//匹配成功，返回位置；否那么返回-1}voidmain{charS[100],T[20];intpos;printf(