單鏈表的實現(xiàn)實驗報告

竭誠為您提供優(yōu)質(zhì)文檔/雙擊可除單鏈表的實現(xiàn)實驗報告

篇一：單鏈表的實驗報告

遼寧工程技術(shù)大學(xué)上機實驗報告

篇二：單鏈表實驗報告

實驗一線性表基本操作的編程實現(xiàn)

--線性表在鏈表存儲下的主要操作實現(xiàn)

班級:T523-1姓名:王娟學(xué)號:33完成日期:20XX.04.04地點:5502學(xué)時:2學(xué)時

一、需求分析

【實驗?zāi)康摹?/p>

通過本次實驗，對課堂上線性表的知識進(jìn)行鞏固，進(jìn)一步熟悉線性表的

鏈接存儲及相應(yīng)的基本操作；并熟練掌握Vc++6.0操作平臺，學(xué)會調(diào)試程序，以及編寫電子實驗報告

【實驗要求】

編寫線性表的基本操作，有構(gòu)造線性表，線性表的遍歷，插入，刪除，

查找，求表長等基本功能，在此基礎(chǔ)上能夠加入Dos下的圖形界面以及學(xué)會文件的操作等功能，為以后的學(xué)習(xí)打下基礎(chǔ)。

【實驗任務(wù)】

(1).線性表基本操作的編程實現(xiàn)，掌握線性表的建立、遍歷、插入、刪除等基本操作的編程實現(xiàn)，也可以進(jìn)一步編程實現(xiàn)查找、逆序、排序等操作，存儲結(jié)構(gòu)可以在順序結(jié)構(gòu)或鏈表結(jié)構(gòu)中任選，可以完成部分主要功能，也可以用菜單進(jìn)行管理完成大部分功能。還鼓勵學(xué)生利用基本操作進(jìn)行一些更實際的應(yīng)用型程序設(shè)計。

(2).用菜單管理，把線性表的順序存儲和鏈表存儲的數(shù)據(jù)插入、刪除運算

(:單鏈表的實現(xiàn)實驗報告)進(jìn)行程序?qū)崿F(xiàn)。建議實現(xiàn)鍵盤數(shù)據(jù)輸入實現(xiàn)改實驗的通用性。為了體現(xiàn)功能的正常性，至少要編制遍歷數(shù)據(jù)的函數(shù).

(3).注意事項:開發(fā)語言使用c++，盡量使用面向?qū)ο蟮乃枷牒蛯崿F(xiàn)方法，可以改編成應(yīng)用軟件.

【實驗類型】

驗證型實驗

二、概要設(shè)計

需要實現(xiàn)線性表的以下功能:

1、創(chuàng)建單鏈表

2、刪除鏈表中的某個結(jié)點

3、輸出單鏈表(遍歷)

4、釋放結(jié)點所占空間

5、查找第i個結(jié)點

6、插入一個結(jié)點

7、求鏈表的長度

二、詳細(xì)設(shè)計

(1).數(shù)據(jù)結(jié)構(gòu)

線性表的線性結(jié)構(gòu)覺決定了它的性質(zhì)：數(shù)據(jù)元素之間是一種線性關(guān)系，數(shù)據(jù)元素

一個接一個的排列，除了最后一個數(shù)據(jù)，其他的數(shù)據(jù)面臨的下一個數(shù)據(jù)有且僅有一個。

(2).存儲結(jié)構(gòu)

單鏈表采用一個結(jié)點存放一個數(shù)據(jù)元素，每個結(jié)點除了包括存放數(shù)據(jù)元素值的數(shù)據(jù)域（data）外，還包括指向下一個元素的存儲位置的指針域(next)。最后一個結(jié)點的指針域為空。

(3).算法分析（函數(shù)功能的實現(xiàn)）

a.創(chuàng)建鏈表

創(chuàng)建鏈表的過程實際相當(dāng)于申請了一個一個的節(jié)點，將這些節(jié)點用一種關(guān)系連接起來。本程序沒有空置的頭結(jié)點。創(chuàng)建的過程中分別對頭結(jié)點和非頭結(jié)點進(jìn)行不同的處理。

(1).創(chuàng)建的過程

nodetype*create()//建立單鏈表,由用戶輸入各節(jié)data域之值{

elemtyped;

nodetype*h=nuLL,*s,*t;

inti=1;

coutwhile(1)

{

coutcin>>d;

if(d==0)break;//以0表示輸入結(jié)束

if(i==1)//建立第一個節(jié)點

{

h=newnodetype;

h->data=d;

h->next=nuLL;

t=h;

}

else//建立其于節(jié)點

{

s=newnodetype;

s->data=d;

s->next=nuLL;

t->next=s;

t=s;//t始終指向生成的單鏈表最后一結(jié)點

}

i++;

}

return(h);

}

b．插入函數(shù)

鏈表的插入分為往前插和往后插兩種操作，此程序采用了往后插的方法，同時實現(xiàn)了從鍵盤輸入數(shù)據(jù)的功能。也考慮了特殊情況即鏈表的溢出，對此首先進(jìn)行了判斷，保證了程序的安全性和健壯性。在此過程中調(diào)用了另一函數(shù)find()；

nodetype*ins(nodetype*h,inti,elemtypex)//在第i個節(jié)點后插入

data域為x的節(jié)點

{

nodetype*p,*s;

s=newnodetype;//建結(jié)點s

s->data=x;

s->next=nuLL;

if(i==0)//插入到第一個位置

{

s->next=h;

h=s;

}

else

{

p=find(h,i);//查找第i個節(jié)點,并由p指向該節(jié)點if(p!=nuLL)

{

s->next=p->next;

p->next=s;

}

else

cout}

returnh;

}

c.刪除函數(shù)

對于刪除，和插入一樣也要通過改鏈來實現(xiàn)，不過在單鏈表中，當(dāng)一個指針指向某一個節(jié)點時，是不能刪除它的，因為地址存放在上一個節(jié)點的鏈域中，所以必須啟動一個尾隨指針。同插入一樣，是刪除某個結(jié)點后的數(shù)，也調(diào)用了find（）；函數(shù)，由于插入和刪除類似所以不附上原程序。

d.輸出函數(shù)(遍歷)

采用while循環(huán)輸出單鏈表的內(nèi)容，用到了p1=p1->next以及輸出函數(shù)cout信息；輸出前同樣對鏈表是否為空進(jìn)行了判斷,該函數(shù)比較簡單，相應(yīng)操作如下：

if(p==nuLL