《數據結構》實驗指導

實驗二：單鏈表的存儲及操作

一'實驗目的

1、掌握單鏈表抽象數據類型的定義。

2、掌握單鏈表的存儲實現。

3、掌握單鏈表的操作算法實現。

4、了解單鏈表的應用。

二'實驗學時

2學時

三'實驗類型

驗證性實驗

四、實驗需求

1、硬件

每位學生配備計算機一臺；

2、軟件

WindowsXP/Windows7操作系統；開發工具軟件：MicrosoftVisualStudio2010。

五'實驗理論與預備知識

1、數據結構的基本概念

2、順序存儲結構的特點

3、線性表的特點和基本運算

4、線性表順序存儲結構下的操作算法

六'實驗任務

1、單鏈表抽象數據類型的代碼實現

2、編寫應用程序，用相關數據驗證運算算法

七、實驗內容及步驟

1、任務一：有一個單鏈表對象L,設計一個算法查找最后一個值為x的結點的邏輯序號。并分

析算法的時間和空間復雜度。

實驗步驟：

(1)啟動VisualStudio2010,創建窗體應用程序。

(2)增加單鏈表類，代碼參考如下:

publicclassLinkList〃定義單鏈表結點類

(

publicstringdata;〃存放數據元素

publicLinkListnext;〃指向下一個結點的字段

);

classLinkListClass

publicLinkListhead=newLinkListQ;〃單鏈表頭結點

//---------單鏈表的基本運算算法--------------------

publicvoidCreateListF(string[]split)〃頭插法建立單鏈表

(

LinkLists;

inti;

=null;〃將頭結點的next字段置為null

for(i=0;i<h;i++)//循環建立數據結點

(

s=newLinkList();

s.data=split[i];〃創建數據結點s

s.next=;//將s結點插入到開始結點之前，頭結點之后

)

publicvoidCreateListR(string[]split)//尾插法建立單鏈表

(

LinkLists,r;

inti;

r=head;//r始終指向尾結點，開始時指向頭結點

for(i=0;i<h;i++)〃循環建立數據結點

(

s=newLinkList();

s.data=split[i];〃創建數據結點s

r.next=s;〃將s結點插入r結點之后

r=s;

)

r.next=null;//將尾結點的next字段置為null

publicstringDispList()〃將單鏈表所有結點值構成一個字符串返回

stringstr=

LinkListp;

P=；〃p指向開始結點

if(p==null)str="空串”；

while(p!=null)//p不為null,輸出p結點的data字段

(

str+=p.data+””；

p=p.next;//p移向下一個結點

)

returnstr;

}

publiciniListLength()〃求單鏈表數據結點個數

(

intn=0;

LinkListp;

p=head;//p指向頭結點,n置為0（即頭結點的序號為0）

while(p.next!=null)

(

n++;

p=p.next;

)

return(n);〃循環結束,p指向尾結點,其序號n為結點個數

)

publicboolGetElem(inti,refstringe)〃求單鏈表中某個數據元素值

(

intj=0;

LinkListp;

p=head;//p指向頭結點,j置為0（即頭結點的序號為0）

while(j<i&&p!=null)〃找第i個結點p

(

j++;

p=p.next;

)

if(p==null)〃不存在第i個數據結點，返回false

returnfalse;

else〃存在第i個數據結點，返回true

(

e=p.data;

returntrue;

)

)

publicintLocateElem(stringe)〃按元素值查找

inti=1;

LinkListp;

p=;〃p指向開始結點,i置為1(即開始結點的序號為1)

while(p!=null&&p.data!=e)〃查找data值為e的結點，其序號為i

(

p=p.next;

i++；

)

if(p==null)〃不存在元素值為e的結點，返回0

return(0);

else〃存在元素值為e的結點，返回其邏輯序號i

return(i);

)

publicboolListlnsert(inti,stringe)//插入數據元素

(

intj=0;

LinkLists,p;

if(i<1)//i<l時i錯誤，返回false

returnfolse;

p=head;〃p指向頭結點,j置為0(即頭結點的序號為0)

while(j<i-1&&P!=null)〃查找第i-1個結點

(

j++；

p=p.next;

)

if(p==null)〃未找到第i-1個結點，返回false

returnfalse;

else〃找到第i-1個結點p,插入新結點并返回true

(

s=newLinkList();

s.data=e;〃創建新結點s,其data字段置為e

s.next=p.next;〃將s結點插入到p結點之后

p.next=s;

returntrue;

)

)

publicboolListDelete(inti,refstringe)〃刪除數據元素

(

intj=O;

LinkListq,p;

if(i<1)//i<l時i錯誤，返回false

returnfalse;

p=head;//p指向頭結點,j置為0(即頭結點的序號為0)

while(j<i-1&&p!=null)〃查找第i-1個結點

j++；

p=p.next;

)

if(p==null)〃未找到第i-1個結點，返回false

returnfalse;

else//找到第i-1個結點p

(

q=p.next;//q指向第i個結點

if(q==null)〃若不存在第i個結點，返回false

returnfalse;

e=q.data;

p.next=q.next;〃從單鏈表中刪除q結點

q=null;〃釋放q結點

returntrue;〃返回true表示成功刪除第i個結點

)

)

publicintFindlast(LinkListClassL,stringx)

(

LinkListp=L.;

inti=OJ=i;

while(p!=null)

i++；

if(p.data==x)

j二i；

p=p.next;

)

returnj;

)

(3)設計窗體，界面參考如下:

(4)編寫窗體中按鈕等控件的代碼，調用單鏈表類，參考如下:

LinkListClassL=newLinkListClassO;//單鏈表L

privatevoidForml_Load(objectsender,EventArgse)

{

="2,34,5,6,2,3,8"；

)

privatevoidbuttonl_Click(objectsender,EventArgse)

(

stringstr=,Trim();

if(str==

=”操作提示:必須輸入元素”；

else

(

string[]split=(newChai?口{