随笔 - 0  文章 - 3  trackbacks - 0
<2025年7月>
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

留言簿

文章档案(50)

搜索

  •  

最新评论


习题4:有La,Lb两个有序链表,将Lb链表插入La链表中去,


使之依然有序...


上次写的那个链表有问题,我又改进了一下,


其实这个问题并不难,


是我自己不够专心,并且一条路跑到黑,这样是做不出来的...


当专心思考一件事情的时候,效率会很高,


这是我所学到的...


java 代码




  1. class Node {   

  2.     int element;   

  3.     Node next;   

  4.     public Node(int i) {   

  5.         this(i, null);   

  6.     }   

  7.     public Node(int i, Node next) {   

  8.         this.element = i;   

  9.         this.next = next;   

  10.     }   

  11. }   

  12.   

  13. class LinkedList {   

  14.     public Node header;   

  15.     public LinkedList() {   

  16.         header = null;   

  17.     }   

  18.     public boolean isEmpty() {   

  19.         return header == null;   

  20.     }   

  21.     public void addtotail(int e) {   

  22.         if (!isEmpty()) {   

  23.             Node temp = header.next;   

  24.             if (temp == null) {   

  25.                 header.next = new Node(e);   

  26.             } else {   

  27.                 while (temp.next != null) {   

  28.                     temp = temp.next;   

  29.                 }   

  30.                 temp.next = new Node(e);   

  31.             }   

  32.         } else {   

  33.             header = new Node(e);   

  34.         }   

  35.     }   

  36.     public void printAll() {   

  37.         for (Node temp = header; temp != null; temp = temp.next) {   

  38.             System.out.print(temp.element + " ");   

  39.         }   

  40.     }   

  41.     public void insertA(LinkedList la, LinkedList lb) {   

  42.         Node heada = la.header;   

  43.         Node headb = lb.header;   

  44.         while(headb!=null){   

  45.             if(headb.element<la.header.element){   

  46.                 int i=headb.element;   

  47.                 Node node=new Node(i);   

  48.                 node.next=heada;   

  49.                 la.header=node;   

  50.                 headb=headb.next;   

  51.             }   

  52.             else{   

  53.                 heada=la.header;   

  54.                 while(headb.element>heada.next.element && heada.next.next!=null){   

  55.                     heada=heada.next;   

  56.                 }   

  57.                 if(heada.next.next!=null){   

  58.                     int i=headb.element;   

  59.                     Node node=new Node(i);   

  60.                     node.next=heada.next;   

  61.                     heada.next=node;   

  62.                     headb=headb.next;   

  63.                 }   

  64.                 else if(heada.next.next==null){   

  65.                     if(headb.element<=heada.next.element){   

  66.                         int i=headb.element;   

  67.                         Node node=new Node(i);   

  68.                         node.next=heada.next;   

  69.                         heada.next=node;   

  70.                         headb=headb.next;   

  71.                     }   

  72.                     else{   

  73.                         int i=headb.element;   

  74.                         Node node=new Node(i);   

  75.                         heada.next.next=node;   

  76.                         headb=headb.next;   

  77.                     }   

  78.                 }   

  79.             }   

  80.         }   

  81.         System.out.println();   

  82.         System.out.print("new list: ");   

  83.         la.printAll();   

  84.     }   

  85. }   

  86.   

  87. public class InsertListA {   

  88.   

  89.     public static void main(String args[]) {   

  90.         LinkedList La = new LinkedList();   

  91.         LinkedList Lb = new LinkedList();   

  92.         for (int i = 1; i < 35; i = i + 5) {   

  93.             La.addtotail(i);   

  94.         }   

  95.         System.out.print("List A: ");   

  96.         La.printAll();   

  97.         System.out.println();   

  98.         for (int i = 2; i < 20; i = i + 2) {   

  99.             Lb.addtotail(i);   

  100.         }   

  101.         System.out.print("List B: ");   

  102.         Lb.printAll();   

  103.         La.insertA(La, Lb);   

  104.            

  105.            

  106.   

  107.         LinkedList Lc = new LinkedList();   

  108.         LinkedList Ld = new LinkedList();   

  109.         for (int i = 1; i < 20; i = i + 2) {   

  110.             Lc.addtotail(i);   

  111.         }   

  112.         System.out.println();   

  113.         System.out.print("List C: ");   

  114.         Lc.printAll();   

  115.         for (int i = 4; i < 30; i = i + 5) {   

  116.             Ld.addtotail(i);   

  117.         }   

  118.         System.out.println();   

  119.         System.out.print("List D: ");   

  120.         Ld.printAll();   

  121.         Lc.insertA(Lc, Ld);   

  122.            

  123.         LinkedList Le=new LinkedList();   

  124.         LinkedList Lf=new LinkedList();   

  125.         for(int i=1; i<=19; i=i+2){   

  126.             Le.addtotail(i);   

  127.         }   

  128.         System.out.println();   

  129.         System.out.print("List E: ");   

  130.         Le.printAll();   

  131.         for(int i=4; i<=14; i=i+5){   

  132.             Lf.addtotail(i);   

  133.         }   

  134.         System.out.println();   

  135.         System.out.print("List F: ");   

  136.         Lf.printAll();   

  137.         Le.insertA(Le, Lf);   

  138.     }   

  139. }   



试验了很多个链表的插入,都没有问题.


运行结果:


List A: 1 6 11 16 21 26 31

List B: 2 4 6 8 10 12 14 16 18

new list: 1 2 4 6 6 8 10 11 12 14 16 16 18 21 26 31

List C: 1 3 5 7 9 11 13 15 17 19

List D: 4 9 14 19 24 29

new list: 1 3 4 5 7 9 9 11 13 14 15 17 19 19 24 29

List E: 1 3 5 7 9 11 13 15 17 19

List F: 4 9 14

new list: 1 3 4 5 7 9 9 11 13 14 15 17 19


链表的四个基本的问题都已经解决了,


还剩下一个实验....


 





评论也很精彩,请点击查看精彩评论。欢迎您也添加评论。查看详细 >>





JavaEye推荐
北京:优秀公司NHNChina招聘:WEB开发,系统管理,JAVA开发, DBA
广州:急招 JAVA开发经理/系统架构师(10-15K/月)也招聘java程序员
与Hibernate之父面对面-4月19日 Gavin King上海交流研讨会
高薪工作机会 美国法国上海 15-20k/月 J2EE SA



文章来源: http://xiaozhe.javaeye.com/blog/67133
posted on 2007-04-01 21:28 xiaozhe 阅读(89) 评论(0)  编辑  收藏

只有注册用户登录后才能发表评论。


网站导航: