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

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

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

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

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

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

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

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

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

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

10、.next; /p指向要刪結(jié)點的后繼return q; /返回已刪結(jié)點/顯示全部鏈表public void listdisplay() linknode p=first.next; /指向第一個結(jié)點system.out.println("顯示鏈表：從前到后");while(p!=null) p.linknodedisplay(); /顯示結(jié)點p=p.next;system.out.println("*");/返回鏈表長度（結(jié)點數(shù)）public int listlength() linknode p=first.next; /指向頭結(jié)點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é)點s1.insertwhere(2,34);s1.insertwhere(3,53);s1.insertwhere(4,32);s1.insertwhere(3,76);s1.listdisplay();s1.deletewhere(4); /刪除第4個結(jié)點s1.listdi