計算機與信息技術(shù)學院綜合性、設(shè)計性實驗報告

專業(yè)：網(wǎng)絡(luò)工程年級/班級：大二2023—2023學年第

一學期

課程名稱數(shù)據(jù)結(jié)構(gòu)指導教師李四

學號姓名16083240XX張三

項目名稱單鏈表的基本操作實驗類型綜合性/設(shè)計性

實驗時間2023.10.3實驗地點216機房

一、實驗?zāi)康?/p>

(1)熟悉順序表的創(chuàng)建、取值、查找、插入、刪除等算法,模塊化程序設(shè)計方法.

二、實驗儀器或設(shè)備

(1)硬件設(shè)備:CPU為Pentium4以上的計算機，內(nèi)存2G以上

(2)配置軟件：MicrosoftWindows7與VC++6.0

三、總體設(shè)計(設(shè)計原理、設(shè)計方案及流程等)

設(shè)計原理：

單鏈表屬于線性表，線性表的存儲結(jié)構(gòu)的特點是：用一組任意存儲單元存儲

線性表的數(shù)據(jù)元素，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的。因此,

對于某個元素來說,不僅需要存儲其自身的信息，還需要存儲一個指示其直

接后繼的信息。

設(shè)計方案：

采用模塊化設(shè)計的方法，設(shè)計各個程序段,最終通過主函數(shù)實現(xiàn)各個程序段

的功能。設(shè)計時，需要考慮用戶輸入非法數(shù)值，所以要在程序中寫入說可以

解決非法數(shù)值的代碼。

設(shè)計流程：

1.引入所需的頭文獻；

2.定義狀態(tài)值；

3.寫入順序表的各種操作的代碼；

寫入主函數(shù)，分別調(diào)用各個函數(shù)。在調(diào)用函數(shù)時，采用if結(jié)構(gòu)進行判斷輸

入值是否非法，從而執(zhí)行相應(yīng)的程序

四、實驗環(huán)節(jié)(涉及重要環(huán)節(jié)、代碼分析等)

#include<stdio.h>//EOF(="Z或F6),NULL

#include<std1ib.h>//srand(),rand(),exit(n)

#inc1ude<malloc.h>//malloc(),alloc(),rea1loc()等

#include<limits.h>//INTMAX等

#include<string.h>

#include<ctype.h>

#inc1ude<math.h>//floor(),cei1(),abs()

#inc1ude<iostream.h>//cout,cin

#include<time.h>//c1ock(),CLKTCK,c1ock_t

#defineTRUE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineINFEASIBLE-1

#defineOVERFLOW-2

typedefintStatus;//Status是函數(shù)的類型,

〃其值是函數(shù)結(jié)果狀態(tài)代碼,如oK等

typedefintElemType;

typedefstructLNode

[

oE1emTypedata;〃結(jié)點的數(shù)據(jù)域

ostructLNode*next；〃結(jié)點的指針域

}LNode,*LinkList;//LinkList為指向結(jié)構(gòu)體LNode的指針類

型

//初始化單鏈表

算法環(huán)節(jié)：

1.生成新結(jié)點作為頭結(jié)點，用頭指針L指向頭結(jié)點.

2.頭結(jié)點的指針域置空。

StatusInitList_L(LinkList&L)

(

?L=newLNode;〃生成新結(jié)點作為頭結(jié)點，用頭指針L指向頭結(jié)點；

L->next=NULL;。//頭結(jié)點的指針域置空

returnOK;

)

//單鏈表的取值

算法環(huán)節(jié)：

1.用指針P指首元結(jié)點,用j做計數(shù)器初值賦為1.

2.從首元結(jié)點開始依次順著鏈域next向下訪問，只要指向當前結(jié)點的指針p不為空

(NULL),并且沒有到達序號為i的結(jié)點,則循環(huán)執(zhí)行以下操作：

P指向下一結(jié)點；

計數(shù)器j相應(yīng)加1;

3.退出循環(huán)時，假如指針P為空，或者計數(shù)器j大于i,說明指定的序號i值不合法(i

大于表長n或i小于等于0),取值失敗返回ERROR,否則取值成功,此時j=i時，p所指

的結(jié)點就是要找的第i個結(jié)點，用參數(shù)e保存當前結(jié)點的數(shù)據(jù)域,返回0K。

StatusGetElem_L(LinkListL,inti,ElemType&e)

(

?LinkListp;

?intj；

0p=L->next;

?j=l;

while(p&&j<i)

(

p=p->next;

。++j；

if(!PIj>i)returnERROR；

。e=p->data；

?returnOK;

}

//單鏈表的按值查找

算法環(huán)節(jié)：

1.用指針p指首元結(jié)點。

2.從首元結(jié)點開始依次順著鏈域next向下查找，只要指向當前結(jié)點的指針p不為空，

并且P所指結(jié)點的數(shù)據(jù)域不等于給定值e,則循環(huán)執(zhí)行以下操作:p指向下一個結(jié)點。

3.返回p。若查找成功,p此時即為結(jié)點的地址值,若查找失敗,p的值即為NULL。

intLocateElemL(LinkListL,ElemTypee)

(

LinkListp;

?intj;

p=L->next；

?j=1；

while(p&&p->data!=e)

p=p—>next;

?j++;

)

?if(p)returnj;

oelsereturn0；

)

//單鏈表的插入

算法環(huán)節(jié)：

1.查找結(jié)點a一并由指針p指向該結(jié)點。

2.生成一個新結(jié)點*s。

3.將新結(jié)點*s的數(shù)據(jù)域置為e。

4.將新結(jié)點*s的指針域指向結(jié)點a,。

5.將結(jié)點*p的指針域指向新結(jié)點*s。

StatusListInsert_L(LinkList&L,inti,E1emTypee)

(

LinkListp=L,s;

?intj=0;

while(p&&(j<i-1))

°{

p=p->next;

。++j；

°)

if(!p||j>i-D

(

returnERROR;

}

s=newLNode；

s->data=e；

s->next=p->next;

op—>next=s;

oreturnOK；

)

//單鏈表的刪除

1.查找結(jié)點a-并由指針p指向該結(jié)點。

2.臨時保存待刪除結(jié)點a,的地址在q中，以備釋放。

3.將結(jié)點*P的指針域指向ai的直接后繼結(jié)點。

4.釋放結(jié)點ai的空間。

StatusListDelete—L(LinkList&L,inti)

(

LinkListp=L,q；

intj=0;

while((p->next)&&(j<i-1))

8P=p->next;

s++j；

}

if((!P->next)||(j>i-1))

returnERROR;

)

%二p->next;

?p->next=q->next；

deleteq;

?returnOK;

)

〃單鏈表的輸出

算法環(huán)節(jié)：

1.將指針P指向L的next域。

2.輸出p指針的數(shù)據(jù)。

3.將指針p后移。

4.循環(huán)第2,3步,直到P指針為空(NULL)o

voidListPrint_L(LinkListL)

{

<>LinkListp;

op=L—>next;

do

oprintf(〃％5d〃，p->data);

p=p->next；

}whi1e(p);

)

voidmain()

I

。inti,n,e;

*>LinkListL;

if(InitList_L(L));

printf(M單鏈表創(chuàng)建成功！\n〃);

printf(〃請輸入您要輸入的數(shù)據(jù)個數(shù)n:\n")；

oscanf(〃%d〃，&n);

printf(〃請輸入您要輸入的數(shù)據(jù)：\n〃)；

ofor(i=l;i<=n;i++)

(

?>scanf(〃％d〃，&e);

istlnsert_L(L,i,e);

}

個rintf(〃當前單鏈表的內(nèi)容為：\n〃)；

oListPrint_L(L);

oprintf(〃\n");

printf(〃請輸入您要插入的數(shù)據(jù)e及其位置i,使用空格鍵隔開:\n〃)；

scanf(，z%d%d",&e,&i);

?if(Listlnsert_L(L,i,e))

printf(〃當前單鏈表的內(nèi)容為：\n〃)；

gListPrint—L(L)；

°}

else

。printf(，zi值越界!\n〃)；

°)

叩rintf(〃\n〃)；

叩rintf(〃請輸入您要取的數(shù)據(jù)序號：\n〃)；

oscanf(〃％d〃，&i);

oif(GetE1em_L(L,i,e))

-printf(〃第%d位數(shù)據(jù)的值為:%d\n〃，i,e);

else

printf(”i值越界!\n〃)；

0}

oprintf(〃請輸入要查找的數(shù)據(jù)值:\n");

oscanf("%d/z,&e);

if(!LocateE1em_L(L,e))

0(

。printf("查無此值!\n〃);

<>else

。{

*?printf(〃數(shù)據(jù)%d在%(1號位置\n〃，e,LocateElem_L(L,e));

}

oprintf(”請輸入要刪除的數(shù)據(jù)的序號:\n〃)；

oscanf("%d〃，&i);

0if(ListDelete_L(L,i))