论坛首页 → 综合技术论坛 →

链表的实现

浏览 3881 次
锁定老帖子 主题：链表的实现
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
  • sunxboy
  • 等级: 初级会员
  • 性别:
  • 文章: 106
  • 积分: 0
  • 来自: 武汉
   发表时间：2007-10-12  
java 代码
  1. /** 
  2.  *  
  3.  */  
  4. package link;  
  5.   
  6. /** 
  7.  * @author sunxboy 
  8.  * 
  9.  */  
  10. public class Node {  
  11.   
  12.     /** 
  13.      * 链表结构的特征： 
  14.      * 分二部分： 
  15.      * 第一部分为数据 
  16.      * 第二部分为地址，它指下一个节点 
  17.      */  
  18.     public int data;  
  19.     public Node next;  
  20.       
  21.     public Node(int data) {  
  22.         this.data=data;  
  23.     }  
  24. }  

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
java 代码
 
  1. /** 
  2.  * 数据结构之链表 
  3.  */  
  4. package link;  
  5.   
  6. /** 
  7.  * @author sunxboy
  8.  * 
  9.  */  
  10. public class LinkTable {  
  11.   
  12.     private Node head;  
  13.       
  14.     /** 
  15.      * 在链表的最前面插入一个值 
  16.      * @param data 要插的数据 
  17.      * @return 是否成功 
  18.      */  
  19.     public boolean insertFirst(int data) {  
  20.         Node node= new Node(data);  
  21.         if(isEmpty()) {  
  22.             head = node;  
  23.             return true;  
  24.         }  
  25.         //将新插入的数的地址指向原来的第一位数  
  26.         node.next = head;  
  27.         //更新插入值后的新链表的头  
  28.         head = node;  
  29.         return true;  
  30.     }  
  31.       
  32.     /** 
  33.      * 在链表的最末插入一个值 
  34.      * @param data 要插入的数据 
  35.      * @return 是否成功 
  36.      */  
  37.     public boolean insertLast(int data) {  
  38.         Node node = new Node(data);  
  39.         if(isEmpty()) {  
  40.             node = head;  
  41.             return true;  
  42.         }  
  43.         Node p = head;  
  44.         Node pre = head;  
  45.         //遍历整个链表,从而最终得到一个最后的节点  
  46.         while(!isEnd(p)) {  
  47.             // 在向后移动之前得到一个节点  
  48.             pre = p;  
  49.             // 逐次向后移动  
  50.             p = p.next;  
  51.         }  
  52.         // 将要插入的值插入到最后一个节点上  
  53.         pre.next = node;  
  54.         return false;  
  55.     }  
  56.       
  57.     /** 
  58.      * 在某节点前插入一新数据 
  59.      * @param oldData 原节点 
  60.      * @param newData 新节点 
  61.      * @return 是否插入成功 
  62.      */  
  63.     public boolean insert(int oldData,int newData) {  
  64.         Node preNode = find(oldData,true);  
  65.         if(preNode==null) {  
  66.             return false;  
  67.         }  
  68.         Node newNode = new Node(newData);  
  69.         if(preNode==head) {  
  70.             newNode.next=head;  
  71.             head = newNode;  
  72.         } else {  
  73.             Node pNode = preNode.next;  
  74.             newNode.next=pNode;  
  75.             preNode.next=newNode;  
  76.         }  
  77.           
  78.         return true;  
  79.     }  
  80.       
  81.     /** 
  82.      * 删除某一节点 
  83.      * @param data 节点数据 
  84.      * @return 是否删除成功 
  85.      */  
  86.     public boolean delete(int data) {  
  87.         if(isEmpty()) {  
  88.             return false;  
  89.         }  
  90.         Node preNode = find(data, true);  
  91.         if(preNode == head) {  
  92.             head = head.next;  
  93.         }else {  
  94.             Node pNode = preNode.next;  
  95.             preNode.next=pNode.next;  
  96.         }  
  97.         return true;  
  98.     }  
  99.       
  100.     /** 
  101.      * 将某节点数据更新为新的数据 
  102.      * @param oldData 
  103.      * @param newData 
  104.      * @return 
  105.      */  
  106.     public boolean update(int oldData,int newData) {  
  107.         Node pNode = find(oldData, false);  
  108.         if(pNode!=null) {  
  109.             pNode.data = newData;  
  110.             return true;  
  111.         }  
  112.         return false;  
  113.     }  
  114.       
  115.     /** 
  116.      * 查找数值为data的节点 
  117.      * @param flag 为false时表示返回要找数据的节点, 
  118.      *             为true时表示返回要找数据之前的节点 
  119.      * @param data 要查找的数值 
  120.      * @return  
  121.      */  
  122.     public Node find(int data,boolean flag) {  
  123.   
  124.         Node p = head;  
  125.         Node pre = head;  
  126.         while(!isEnd(p)&& p.data!= data) {  
  127.           
  128.             // 保存之前的信息  
  129.             pre = p;  
  130.             //逐次向后移动  
  131.             p = p.next;  
  132.         }  
  133.         if(isEnd(p)) {  
  134.             return null;  
  135.         }  
  136.         if(flag) return pre;  
  137.         else return p;  
  138.     }  
  139.       
  140.     /** 
  141.      * 链表是否为空 
  142.      * @return 
  143.      */  
  144.     public boolean isEmpty() {  
  145.         return head==null;  
  146.     }  
  147.       
  148.     /** 
  149.      * 此节点是否是最后一个节点 
  150.      * @param node 要判断的节点 
  151.      * @return 是否是最后一个节点 
  152.      */  
  153.     public boolean isEnd(Node node) {  
  154.         return node==null;  
  155.     }  
  156.       
  157.     /** 
  158.      * 显示链表所有节点信息 
  159.      * 
  160.      */  
  161.     public void display() {  
  162.         Node pNode = head;  
  163.         while(pNode!=null) {  
  164.             System.out.println(pNode.data);  
  165.             pNode = pNode.next;  
  166.         }  
  167.   
  168.     }  
  169.       
  170.     public static void main(String[] args) {  
  171.         LinkTable lt=new LinkTable();  
  172.         lt.insertFirst(1);  
  173.         lt.insertFirst(2);  
  174.         lt.insertFirst(3);  
  175.         lt.insertLast(4);  
  176.         lt.insertLast(5);  
  177.         lt.insertLast(6);  
  178.         lt.insert(4, -2);  
  179.         lt.delete(6);  
  180.         lt.delete(3);  
  181.         lt.delete(4);  
  182.         lt.update(1, 100000);  
  183.         lt.display();  
  184.     }  
  185. } 
返回顶楼
         
论坛首页 → 综合技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics