洛陽理工學院實驗報告

系別計算機系班級學號姓名

課程名稱數(shù)據(jù)結(jié)構(gòu)實驗日期11.7

實驗名稱鏈表的基本操作成績

實驗目的：

熟悉掌握線性表鏈式存儲結(jié)構(gòu)，掌握與應用查找、插入、刪除等基本操作

算法，訓練和提高結(jié)構(gòu)化程序設計能力及程序調(diào)試能力。

實驗條件：

計算機一臺，VisualC++6.0

實驗內(nèi)容：

1.問題描述

以單鏈表為存儲結(jié)構(gòu)實現(xiàn)以下基本操作：

(1)在第i個元素前插入一個新元素。

(2)查找值為x的某個元素。若成功，給出x在表中的位置；不成功給出

提醒信息。

(3)刪除第i個元素，若成功，給出提醒信息并顯示被刪元素的值；不成功

給出失敗的提醒信息。

2.數(shù)據(jù)結(jié)構(gòu)類型定義

typedefstructLinkNode

(

ointValue;

ostructLinkNode*Next;

}Node,*LinkList;

3.模塊劃分

(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);

4.具體設計

voidinit_1ink1ist(LinkList*1)/*對單鏈表進行初始化*/{

3*1=(LinkList)ma1loc(sizeof(Node))；/*申請結(jié)點空間*/

式*1)->next=NULL;/*置為空表*/

)

voidCreateFromHead(LinkListL)

(

Node*s;

?charc;

intf1ag=1;

while(flag)/*flag初值為1,當輸入〃$〃時，置flag為0,建表結(jié)束

c=getchar();

。if(c!=，$，)

。s=(Node)maHoc(sizeof(Node))；/*建立新結(jié)點s*/

8S-〉data=c；

bgs—>next=L->next；/*將s結(jié)點插入表頭*/

。此一>next=s;

。)

?else

。flag=0;

)

)

voidCreateFromTai1(LinkListL)

(

Node*r,*s;

ocharc;

intflag=1;/*設立一個標志，初值為1,當輸入"$"時，flag為

0,建表結(jié)束*/

°r=L;/*i'指針動態(tài)指向鏈表的當前表尾，以便于做尾插

入，其初值指向頭結(jié)點*/

while(flag)/*循環(huán)輸入表中元素值，將建立新結(jié)點s插入

表尾*/

。{

?c=getchar()；

。if(c!=，$')

00{

。s=(Node*)maHoc(sizeof(Node));

s->data=c;

ar->next=s;

gr=s；

。}

e1se

00{

flag=0;

。r—>next=NULL;/*將最后一個結(jié)點的next鏈域置為空，表達

鏈表的結(jié)束*/

)

Node*Get(LinkListL,inti)

/*在帶頭結(jié)點的單鏈表L中查找第i個結(jié)點，若找到(1WiWn),則返回該結(jié)

點的存儲位置；否則返回NULL*/

(

intj;

Node*p;

6P=L;

d=0；/*從頭結(jié)點開始掃描*/

while((p->next!=NULL)&&(j<i))

(

?p=p->next;/*掃描下一結(jié)點*/

。4++；/*已掃描結(jié)點計數(shù)器*/

)

if(i==j)

“returnp;/*找到了第i個結(jié)點*/

?else

returnNULL;/*找不到，iWO或i>n*/

Node*Locate(LinkListL,ElemTypekey)

/*在帶頭結(jié)點的單鏈表L中查找其結(jié)點值等于key的結(jié)點，若找到則返回該結(jié)

點的位置P,否則返回NULL*/

(

Node*p;

p=L->next；/*從表中第一個結(jié)點開始*/

。while(p!=NULL)

if(p->data!=key)

叩=p—>next;

ooe1se

。obreak；/*找到結(jié)點值=key時退出循環(huán)*/

e}

returnp；

y

intInsList(LinkListL,inti,ElemTypee)

/*在帶頭結(jié)點的單鏈表L中第i個位置插入值為e的新結(jié)點s*/

(

Node*pre,*s;

intk;

pre=L;

k=0;/*從〃頭〃開始，查找第i—1個結(jié)點*/

while(pre!=NULL&&k<iT)/*表未查完且未查到第i-1個時反

復，找到pre指向第iT個*/

opre=pre->next;

ok=k+l;

}。。，/*查找第iT結(jié)點*/

f(!pre)/*如當前位置Pre為空表已找完尚未數(shù)到第i個，說明插

入位置不合理*/

?(

。printf(“插入位置不合理！”);

oreturnERROR;

)

3s二(Node*)malloc(sizeof(Node))；/*申請一個新的結(jié)點S*/

?s->data=e；/*值e置入s的數(shù)據(jù)域*/

??s—>next=pre->next/*修改指針，完畢插入操作*/

pre—>next=s;

oreturn0K;

)

intDe1List(LinkListL,inti,ElemType*e)

/*在帶頭結(jié)點的單鏈表L中刪除第i個元素，并將刪除的元素保存到變量*e中

*/

(

Node*pre,*r;

ointk;

opre=L;

k=0;

while(pre->next!=NULL&&k<i-1)/*尋找被刪除結(jié)點i的前驅(qū)結(jié)

點i—l使P指向它*/

(

pre=pre—>next；

業(yè)=k+1；

“gg川/*查找第i-1個結(jié)點*/

。if(!(pre->next))/*即while循環(huán)是由于p->next=NULL或i<

1而跳出的，而是由于沒有找到合法的前驅(qū)位置，說明刪除位置i不合法。*/

“printf(〃刪除結(jié)點的位置i不合理！〃)；

turnERR0R;

r=pre->next;

叩re->next=pre->next->next；/*修改指針，刪除結(jié)點r*/

*e=r->data;

^free(r);/*釋放被刪除的結(jié)點所占的內(nèi)存空間*/

中rintf（〃成功刪除結(jié)點！”）；

returnOK;

)

intListLength(LinkListL)

/*求帶頭結(jié)點的單鏈表L的長度*/

(

Node*p；

°intj;

op=L