洛陽理工學(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)名稱鏈表的基本操作成績(jī)實(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)類型定義typedefstructLinkNodedintVa1ue;ostructLinkNode*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);.具體設(shè)計(jì)voidinit_1ink1ist(LinkList*1)/*對(duì)單鏈表進(jìn)行初始化*/{(LinkList)malloc(sizeof(Node))；/*申請(qǐng)結(jié)點(diǎn)空間*/式*1)->next=NULL;/*置為空表*/}voidCreateFromHead(LinkListL)(Node*s;?>charc;intf1ag=1;while(flag)/*flag初值為1,當(dāng)輸入〃$〃時(shí)，置flag為0,建表結(jié)束*/c=getchar();。if(c!='$')°{3s=(Node*)ma1loc(sizeof(Node))；/*建立新結(jié)點(diǎn)s*/8S->data=c；。。。s—>next=L->next；/*將s結(jié)點(diǎn)插入表頭*/［一>next=s;}oelseflag=0;))voidCreateFromTai1(LinkListL)(Node*r,*s;0charc;ntflag=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!='$')oo{。s=(Node*)maHoc(sizeof(Node));s->data=c;。。r->next=s;。。r=s；0}e1seg{flag=0;3r—>next=NULL;/*將最后一個(gè)結(jié)點(diǎn)的next鏈域置為空，表達(dá)鏈表的結(jié)束*/。))}Node*Get(LinkListL,inti)/*在帶頭結(jié)點(diǎn)的單鏈表L中查找第i個(gè)結(jié)點(diǎn)，若找到(1WiWn),則返回該結(jié)點(diǎn)的存儲(chǔ)位置；否則返回NULL*/(intj;Node*p;°P=L;°j=0；/*從頭結(jié)點(diǎn)開始掃描*/while((p->next!=NULL)&&(j<i))(wp=p->next;/大掃描下一結(jié)點(diǎn)*/gj++;/*己掃描結(jié)點(diǎn)計(jì)數(shù)器*/)if(i==j)?oreturnp;/*找到了第i個(gè)結(jié)點(diǎn)*/?elsereturnNULL;/*找不到，iWO或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)開始*/owhile(p!=NULL)if(p->data!=key)叩=p—>next;e1se。obreak；/*找到結(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—l個(gè)結(jié)點(diǎn)*/while(pre!=NULL&&kVi-1)/*表未查完且未查到第i-l個(gè)時(shí)反復(fù)，找到pre指向第i-1個(gè)*/。｛*pre=pre->next;ok=k+l;｝。。。/*查找第i-1結(jié)點(diǎn)*/oif(!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ù)域*/as—>next=pre->next/*修改指針，完畢插入操作*/pre—>next=s;oreturn0K;)intDe1List(LinkListL,inti,ElemType*e)/*在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個(gè)元素，并將刪除的元素保存到變量*e中*/(Node*pre,*r;??intk;opre=L;k=0;while(pre->next!=NULL&&k<i-1)/*尋找被刪除結(jié)點(diǎn)i的前驅(qū)結(jié)點(diǎn)i-1使p指向它*/(pre=pre—>next；ok=k+1；。｝gg"*查找第i-1個(gè)結(jié)點(diǎn)*/0if(!(pre->next))/*即while循環(huán)是由于p->next=NULL或i<I而跳出的，而是由于沒有找到合法的前驅(qū)位置，說明刪除位置i不合法。*/。｛-printf(〃刪除結(jié)點(diǎn)的位置i不合理！〃)；^returnERR0R;r=pre->next;叩re->next=pre->next->next；/*修改指針，刪除結(jié)點(diǎn)r*/*e=r->data;ree(r);/*釋放被刪除的結(jié)點(diǎn)所占的內(nèi)存空間*/

oprintf（〃成功刪除結(jié)點(diǎn)!”）;returnOK;}intListLength(LinkListL)/*求帶頭結(jié)點(diǎn)的單鏈表L的長(zhǎng)度*/(Node*p；ftintj;?p=L->next;j=0；/*用來存放單鏈表的長(zhǎng)度*/hi1e(p!=NULL){。叩二p—>next;gj++；Jreturnj；。/*j為求得的單鏈表長(zhǎng)度*/}5.測(cè)試數(shù)據(jù)及結(jié)果*SJL先后入查找3、冊(cè)?。莩?。、否找3、刪除。、<<endlWiH作怦一W1的泊入入，作謨當(dāng)痣2源雪。請(qǐng).A.插3-*SJL先后入查找3、冊(cè)?。莩?。、否找3、刪除。、<<endlWiH作怦一W1的泊入入，作謨當(dāng)痣2源雪。請(qǐng).A.插3-.?中?I警6肝BF選吉4前入一串單字行數(shù)據(jù).；G?BVx當(dāng)前轉(zhuǎn)性表為:%%金叁蚩的蜂作:1、以T吉束！插入2、查找3、刪除。、退出摹的理18葷塾F的入入線餐鬻5詵語雪。語的在歲杳甥9的￡8^翼您拿治軍>二641時(shí)5選H文壇3、冊(cè)”除。、：艮中退出退出請(qǐng)輸入一串單字符數(shù)據(jù)，以M結(jié)束！56789*