實訓(xùn)-鏈表及其運算

1、實訓(xùn)-鏈表及其運算數(shù) 據(jù) 結(jié) 構(gòu)實驗內(nèi)容與上機指導(dǎo)實訓(xùn)-鏈表及其運算一、實驗?zāi)康?. 掌握鏈表存儲結(jié)構(gòu)的特點2. 熟練掌握單鏈表的基本運算3. 掌握循環(huán)鏈表和雙鏈表的特點和基本運算二、實驗內(nèi)容1. 建立一個單鏈表，顯示鏈表中每個結(jié)點的數(shù)據(jù)，并做刪除和插入處理。實驗說明(1) 建立鏈表是從無到有地建立起一個鏈表，即一個一個地輸入各結(jié)點數(shù)據(jù)，并建立起前后相互鏈接的關(guān)系。實驗內(nèi)容與上機指導(dǎo)(2) 顯示鏈表是將鏈表中各結(jié)點的數(shù)據(jù)依次顯示。設(shè)一個指針變量p，先指向第1個結(jié)點，顯示p所指的結(jié)點，然后p后一個結(jié)點再顯示之，直到鏈表尾結(jié)點。(3) 刪除鏈表中的結(jié)點是從p指向第1個結(jié)點開始，檢查該結(jié)點的數(shù)據(jù)是否

2、等于要刪除的數(shù)據(jù)，如果相等就將該結(jié)點刪除，如不相等，則將p后移一個結(jié)點，如此進行下去，直到表尾為止。(4) 插入結(jié)點是將一個結(jié)點插入到已知的鏈表中，且保持結(jié)點的數(shù)據(jù)按原來的遞增次序排列。 2. 建立一個雙鏈表，從鏈?zhǔn)组_始，順序顯示鏈表中的所有結(jié)點的數(shù)據(jù)，然后從鏈尾開始，反序顯示鏈表中所有結(jié)點的數(shù)據(jù)，最后將一個新的結(jié)點插入到鏈表中。實驗內(nèi)容與上機指導(dǎo)實驗說明(1)設(shè)雙向鏈表的類型定義如下: struct chn struct chn *prior; struct chn *next; char data100;prior是指向直接前趨結(jié)點的指針，next是指向直接后繼結(jié)點的指針。結(jié)點的數(shù)據(jù)域為字

3、符串。實驗內(nèi)容與上機指導(dǎo)(2) 建立雙鏈表時，用到復(fù)制字符串庫函數(shù)： strcpy(char *destin, char *source); 該函數(shù)的功能是將字符串source的內(nèi)容復(fù)制到字符型數(shù)組destin中。在本程序中應(yīng)用此函數(shù)是將輸入到字符數(shù)組buf中的字符串復(fù)制到雙鏈表一個結(jié)點的數(shù)據(jù)域中。(3) 通過向后指針next，可以從鏈?zhǔn)紫蚝箜樞蝻@示鏈表中各結(jié)點的數(shù)據(jù)；通過向前指針prior可以從鏈尾反序顯示鏈表中各結(jié)點的數(shù)據(jù)。(4) 修改向前、向后指針可以實現(xiàn)從雙鏈表中刪除和插入結(jié)點。設(shè)該雙鏈表沒有空表頭結(jié)點，即其鏈?zhǔn)捉Y(jié)點的prior域為NULL，其鏈尾結(jié)點的next域為NULL。 實驗內(nèi)容與上機指導(dǎo)3. 建立如圖所示的循環(huán)鏈表，編寫一個程序?qū)⑺屑^方向取反。實驗內(nèi)容與上機指導(dǎo)實驗說明(1) 因為此鏈表為循環(huán)鏈表，所以建此鏈表時最后一個結(jié)點的指針域不能是p-next=NULL，而是指向第一個結(jié)點，即p-next=head;p=head;(2) 為了將鏈表的所有箭頭取反，需從頭開始掃描單鏈表，將第一個結(jié)點的next域指向最后一個結(jié)點，將第二個結(jié)點的next域指向第一個結(jié)點，將第三個結(jié)點的next域指向第二個結(jié)點，直到最后一個結(jié)點用head指向它。(3) 判定最后一個結(jié)