單鏈表的存儲(chǔ)與操作成績(jī)?cè)u(píng)閱人重慶郵電大學(xué)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告班級(jí)：1301416姓名：陳昊學(xué)號(hào)：2014214156指導(dǎo)老師：夏晨洋課程名稱：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)時(shí)間：2015年10月26日-2015年11月2日實(shí)驗(yàn)地點(diǎn)：數(shù)字圖書館負(fù)一樓b132實(shí)驗(yàn)二單鏈表的存儲(chǔ)與操作一、實(shí)驗(yàn)?zāi)康?.理解線性表的邏輯結(jié)構(gòu)；2.理解單鏈表的存儲(chǔ)結(jié)構(gòu)特點(diǎn)，掌握單鏈表的存儲(chǔ)分配要點(diǎn)；3.掌握單鏈表的基本操作及實(shí)現(xiàn)，并能正確分析其時(shí)間復(fù)雜度。二、主要數(shù)據(jù)結(jié)構(gòu)描述linklist;//建立只有頭結(jié)點(diǎn)的空鏈表linklist（ta[]，intn）;//建立有n個(gè)元素的單鏈表~linklist;//析構(gòu)函數(shù)intlength;//求單鏈表的長(zhǎng)度tget（inti）;//取單鏈表中第i個(gè)結(jié)點(diǎn)的元素值intlocate（tx）;//求單鏈表中值為x的元素序號(hào)voidinsert（inti，tx）;//在單鏈表中第i個(gè)位置插入元素值為x的結(jié)點(diǎn)tdelete（inti）;//在單鏈表中刪除第i個(gè)結(jié)點(diǎn)voidprintlist;//遍歷單鏈表，按序號(hào)依次輸出各元素node*first;//單鏈表的頭指針在單鏈表中，需要有構(gòu)造函數(shù)用來構(gòu)造整個(gè)單鏈表。需要析構(gòu)函數(shù)來刪除整個(gè)單鏈表。需要一個(gè)length函數(shù)來求單鏈表的長(zhǎng)度。需要一個(gè)取值函數(shù)get，傳入節(jié)點(diǎn)的編號(hào)，返回節(jié)點(diǎn)的值。需要一個(gè)求序號(hào)的函數(shù)，傳入數(shù)據(jù)的值，返回?cái)?shù)據(jù)對(duì)應(yīng)的編號(hào)，即在單鏈表中的位置。需要一個(gè)插入函數(shù)，用來在特定的位置插入一個(gè)節(jié)點(diǎn)用來存儲(chǔ)新數(shù)據(jù)。需要一個(gè)刪除函數(shù)，用來刪除某個(gè)節(jié)點(diǎn)，并將該節(jié)點(diǎn)兩端的節(jié)點(diǎn)連起來。需要一個(gè)遍歷函數(shù)，用以遍歷單鏈表。三、算法的基本思想描述1.按位置/值查找。按位置和按值查找的思路大體相同，需要一個(gè)工作指針來對(duì)整個(gè)鏈表進(jìn)行遍歷，如果所遇到的編號(hào)或值與想要的一致，便會(huì)把工作指針的信息返回。此函數(shù)只需對(duì)鏈表遍歷一次，所以平均時(shí)間復(fù)雜度為o（n）；2.在位置i插入一個(gè)數(shù)據(jù)元素。此函數(shù)可以大體分成兩個(gè)部分。第一個(gè)部分是遍歷，尋找到要插入的位置，這個(gè)與上面的方法相同。第二個(gè)部分是插入，要先申請(qǐng)一個(gè)新節(jié)點(diǎn)s，在讓s的指針域等于前一個(gè)節(jié)點(diǎn)p的指針域，最后讓p的指針域等于s。此函數(shù)只需對(duì)鏈表遍歷一次，所以平均時(shí)間復(fù)雜度為o（n）；3.刪除位置i的數(shù)據(jù)元素。刪除函數(shù)也有兩個(gè)部分，第一個(gè)與插入相同，第二個(gè)先要暫存被刪節(jié)點(diǎn)，用以返回，再讓前一個(gè)節(jié)點(diǎn)的指針域等于后一個(gè)節(jié)點(diǎn)，最后刪除被刪節(jié)點(diǎn)。此函數(shù)只需對(duì)鏈表遍歷一次，所以平均時(shí)間復(fù)雜度為o（n）；4.初始化單鏈表（有參）：有前插法和尾插法，實(shí)際上都是在鏈表的后面再添加一個(gè)新節(jié)點(diǎn)，所以時(shí)間復(fù)雜度為o（n）；5.遍歷單鏈表、求單鏈表長(zhǎng)度、銷毀單鏈表。這三個(gè)函數(shù)都是要遍歷單鏈表，所以時(shí)間復(fù)雜度為o（n）。四、運(yùn)行的結(jié)果截圖五、實(shí)驗(yàn)體會(huì)和收獲通過這次試驗(yàn)，我熟悉了如何取單鏈表中第i個(gè)結(jié)點(diǎn)的元素值，如何按位查找位置為i的元素并輸出值，如何構(gòu)建一個(gè)單鏈表?？傊@次試驗(yàn)然我熟悉了很多單鏈表的操作。六、程序清單。linklist.hlinklist.cpp單鏈表的存儲(chǔ)與操作.doc免費(fèi)為全國(guó)范文類知名網(wǎng)站，下載全文稍作修改便可使用，即刻完成寫稿任務(wù)。支付6元已有11人下載下載這篇word文檔單鏈