含頭結(jié)點(diǎn)的單鏈表

1、 實(shí)習(xí)報(bào)告“含頭結(jié)點(diǎn)的單鏈表”演示程序 （1） 、程序的功能和特點(diǎn)主要實(shí)現(xiàn)的功能有：1.查找給定關(guān)鍵字的結(jié)點(diǎn)； 2.在單鏈表第l個(gè)結(jié)點(diǎn)位置插入一個(gè)新結(jié)點(diǎn)； 3.刪除第l個(gè)結(jié)點(diǎn)； 4.顯示全部鏈表； 5.求鏈表的長(zhǎng)度；（二）、程序的算法設(shè)計(jì) “比較”算法：1. 【邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)】邏輯結(jié)構(gòu)：每個(gè)元素之間是相鄰的；存儲(chǔ)結(jié)構(gòu)：元素存儲(chǔ)于任意的存儲(chǔ)單元中，可以是連續(xù)的，也可以是不 連續(xù)的；2.【基本操作設(shè)計(jì)】元素存儲(chǔ)域任意的存儲(chǔ)單元中，這時(shí)需要在存儲(chǔ)元素本身信息的同時(shí)，還要存儲(chǔ)下一個(gè)元素的位置。由此構(gòu)成一個(gè)鏈狀結(jié)構(gòu)，成為鏈表。將表示數(shù)據(jù)元素和下一個(gè)元素位置的結(jié)構(gòu)，如下所示：數(shù)據(jù)元素 指針域稱(chēng)為鏈

2、表的結(jié)點(diǎn)指針域用來(lái)存放下一個(gè)元素的地址，這樣就可以保證表的連續(xù)性3. 【算法設(shè)計(jì)】指向第一個(gè)結(jié)點(diǎn)查找給定關(guān)鍵字的結(jié)點(diǎn) 否不是當(dāng)前所查找的結(jié)點(diǎn)并且沒(méi)有到鏈尾null否是指針域！=null移動(dòng)指針，使其指向下一個(gè)元素是返回結(jié)點(diǎn)在單鏈表第l個(gè)結(jié)點(diǎn)位置插入一個(gè)新結(jié)點(diǎn)第l個(gè)結(jié)點(diǎn)，新結(jié)點(diǎn)id 建立新結(jié)點(diǎn)指針p后移l個(gè)結(jié)點(diǎn)把p之后鏈表接到新結(jié)點(diǎn)的后面把新結(jié)點(diǎn)接在p所指結(jié)點(diǎn)的后面刪除第l個(gè)結(jié)點(diǎn)是判斷鏈表是否為空否null使指針p指向所要?jiǎng)h結(jié)點(diǎn)的前驅(qū)指向要?jiǎng)h結(jié)點(diǎn)指向要?jiǎng)h結(jié)點(diǎn)的后驅(qū)4. 【高級(jí)語(yǔ)言代碼】 查找給定關(guān)鍵字的結(jié)點(diǎn)，返回結(jié)點(diǎn)linknodenode p=first; /指向第一結(jié)點(diǎn)/不是當(dāng)前結(jié)點(diǎn)并且沒(méi)有

3、到鏈尾while(p.idata!=id&&p.next!=null)p=p.next;if(p.next!=null) return p;else return null; 在單鏈表第l個(gè)結(jié)點(diǎn)位置插入一個(gè)新結(jié)點(diǎn)linknodenode newlinknodenode= new linknodenode(id,fd); /誕生新結(jié)點(diǎn)newlinknodenodeint i=1;linknodenode p=first; /指向第一結(jié)點(diǎn)/p指針后移l個(gè)結(jié)點(diǎn)while(p.next!=null && i+<l) p=p.next;newlinknodenode

4、.next=p.next; /把p之后的鏈表接在新結(jié)點(diǎn)的后面p.next=newlinknodenode; /把新結(jié)點(diǎn)接在p所指結(jié)點(diǎn)的后面return true;刪除第l個(gè)結(jié)點(diǎn)if(isempty() return null;linknodenode p=first; /指向第一個(gè)結(jié)點(diǎn)int i=1;while(p.next!=null && i+<l)p=p.next; /指向要?jiǎng)h結(jié)點(diǎn)的前驅(qū)linknodenode q=p.next; /指向要?jiǎng)h結(jié)點(diǎn)p.next=q.next; /p指向要?jiǎng)h結(jié)點(diǎn)的后繼return q; /返回已刪結(jié)點(diǎn)（三）、程序中類(lèi)的設(shè)計(jì) “l(fā)inkn

5、odelist”類(lèi)：1. 【邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)】邏輯結(jié)構(gòu)：每個(gè)元素之間是相鄰的；存儲(chǔ)結(jié)構(gòu)：元素存儲(chǔ)于任意的存儲(chǔ)單元中，可以是連續(xù)的，也可以是不 連續(xù)的；2. 【主要成員變量說(shuō)明】 public linknode first; /單鏈表的頭指針【主要成員方法說(shuō)明】 查找給定關(guān)鍵字的結(jié)點(diǎn)，返回結(jié)點(diǎn) public linknode linknodefind(int id) 在單鏈表第l個(gè)結(jié)點(diǎn)位置插入一個(gè)新結(jié)點(diǎn)public boolean insertwhere(int l,int id) 刪除第l個(gè)結(jié)點(diǎn)public linknode deletewhere(int l)顯示全部鏈表public vo

6、id listdisplay()返回鏈表長(zhǎng)度（結(jié)點(diǎn)數(shù)）public int listlength()4. 【高級(jí)語(yǔ)言代碼】 鏈表的結(jié)點(diǎn)類(lèi)class linknodepublic int idata; /數(shù)據(jù)域（結(jié)點(diǎn)關(guān)鍵字）public linknode next; /指針域（指向下一結(jié)點(diǎn)）public linknode() /頭結(jié)點(diǎn)構(gòu)造方法idata=-1;/數(shù)據(jù)域賦值/指針域自動(dòng)初始化為nullpublic linknode(int id) /結(jié)點(diǎn)構(gòu)造方法idata=id; /數(shù)據(jù)域賦值public void linknodedisplay() /顯示自身的數(shù)據(jù)域system.out.pri

7、ntln(""+idata+""); 單鏈表類(lèi)class linknodelist public linknode first; /單鏈表的頭指針public linknodelist () /構(gòu)造方法first=new linknode(); /空單鏈表，頭指針指向頭結(jié)點(diǎn)public boolean isempty() /單鏈表是否為空return (first.next=null); /頭結(jié)點(diǎn)的指針為空/查找給定關(guān)鍵字的結(jié)點(diǎn)，返回結(jié)點(diǎn)public linknode linknodefind(int id) linknode p=first; /指向第

8、一結(jié)點(diǎn)/不是當(dāng)前結(jié)點(diǎn)并且沒(méi)有到鏈尾while(p.idata!=id&&p.next!=null)p=p.next;if(p.next!=null) return p;else return null; /在單鏈表第l個(gè)結(jié)點(diǎn)位置插入一個(gè)新結(jié)點(diǎn)public boolean insertwhere(int l,int id) linknode newlinknode= new linknode(id); /誕生新結(jié)點(diǎn)newlinknodeint i=1;linknode p=first; /指向第一結(jié)點(diǎn)/p指針后移l個(gè)結(jié)點(diǎn)while(p.next!=null &&

9、i+<l) p=p.next;newlinknode.next=p.next; /把p之后的鏈表接在新結(jié)點(diǎn)的后面p.next=newlinknode; /把新結(jié)點(diǎn)接在p所指結(jié)點(diǎn)的后面return true;/刪除第l個(gè)結(jié)點(diǎn)public linknode deletewhere(int l) if(isempty() return null;linknode p=first; /指向第一個(gè)結(jié)點(diǎn)int i=1;while(p.next!=null && i+<l)p=p.next; /指向要?jiǎng)h結(jié)點(diǎn)的前驅(qū)linknode q=p.next; /指向要?jiǎng)h結(jié)點(diǎn)p.next=q

10、.next; /p指向要?jiǎng)h結(jié)點(diǎn)的后繼return q; /返回已刪結(jié)點(diǎn)/顯示全部鏈表public void listdisplay() linknode p=first.next; /指向第一個(gè)結(jié)點(diǎn)system.out.println("顯示鏈表：從前到后");while(p!=null) p.linknodedisplay(); /顯示結(jié)點(diǎn)p=p.next;system.out.println("*");/返回鏈表長(zhǎng)度（結(jié)點(diǎn)數(shù)）public int listlength() linknode p=first.next; /指向頭結(jié)點(diǎn)int i=0;wh

11、ile(p!=null)p=p.next;i+;return i;/置鏈表為空表public void makeempty() first.next=null; public static void main(string args) linknodelist s1=new linknodelist(); /空鏈表誕生s1.insertwhere(1,12); /從指定位置插入結(jié)點(diǎn)s1.insertwhere(2,34);s1.insertwhere(3,53);s1.insertwhere(4,32);s1.insertwhere(3,76);s1.listdisplay();s1.deletewhere(4); /刪除第4個(gè)結(jié)點(diǎn)s1.listdi