欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java模擬有序鏈表數(shù)據(jù)結(jié)構(gòu)的示例

 更新時(shí)間:2016年04月18日 08:43:25   作者:匆忙擁擠repeat  
這篇文章主要介紹了Java模擬有序鏈表數(shù)據(jù)結(jié)構(gòu)的示例,包括一個(gè)反序的單鏈表結(jié)構(gòu)的例子,需要的朋友可以參考下

有序鏈表:
按關(guān)鍵值排序。刪除鏈頭時(shí),就刪除最小(/最大)的值,插入時(shí),搜索插入的位置。
插入時(shí)需要比較O(N),平均O(N/2),刪除最小(/最大)的在鏈頭的數(shù)據(jù)時(shí)效率為O(1),
如果一個(gè)應(yīng)用需要頻繁的存取(插入/查找/刪除)最小(/最大)的數(shù)據(jù)項(xiàng),那么有序鏈表是一個(gè)不錯(cuò)的選擇
優(yōu)先級(jí)隊(duì)列 可以使用有序鏈表來實(shí)現(xiàn)
有序鏈表的插入排序:
對(duì)一個(gè)無序數(shù)組,用有序鏈表來排序,比較的時(shí)間級(jí)還是O(N^2)
復(fù)制時(shí)間級(jí)為O(2*N),因?yàn)閺?fù)制的次數(shù)較少,第一次放進(jìn)鏈表數(shù)據(jù)移動(dòng)N次,再?gòu)逆湵韽?fù)制到數(shù)組,又是N次
每插入一個(gè)新的鏈結(jié)點(diǎn),不需要復(fù)制移動(dòng)數(shù)據(jù),只需要改變一兩個(gè)鏈結(jié)點(diǎn)的鏈域

import java.util.Arrays; 
import java.util.Random; 
 
/** 
 * 有序鏈表 對(duì)數(shù)組進(jìn)行插入排序 
 * @author stone 
 */ 
public class LinkedListInsertSort<T extends Comparable<T>> { 
   
  private Link<T> first;    //首結(jié)點(diǎn) 
  public LinkedListInsertSort() { 
     
  } 
   
  public boolean isEmpty() { 
    return first == null; 
  } 
   
  public void sortList(T[] ary) { 
    if (ary == null) { 
      return; 
    } 
    //將數(shù)組元素插入進(jìn)鏈表,以有序鏈表進(jìn)行排序 
    for (T data : ary) { 
      insert(data); 
    } 
    // 
     
  } 
   
  public void insert(T data) {// 插入 到 鏈頭, 以從小到大排序 
    Link<T> newLink = new Link<T>(data); 
    Link<T> current = first, previous = null; 
    while (current != null && data.compareTo(current.data) > 0) { 
      previous = current; 
      current = current.next; 
    } 
    if (previous == null) { 
      first = newLink; 
    } else { 
      previous.next = newLink; 
    } 
    newLink.next = current; 
  } 
   
  public Link<T> deleteFirst() {//刪除 鏈頭 
    Link<T> temp = first; 
    first = first.next; //變更首結(jié)點(diǎn),為下一結(jié)點(diǎn) 
    return temp; 
  } 
   
  public Link<T> find(T t) { 
    Link<T> find = first; 
    while (find != null) { 
      if (!find.data.equals(t)) { 
        find = find.next; 
      } else { 
        break; 
      } 
    } 
    return find; 
  } 
   
  public Link<T> delete(T t) { 
    if (isEmpty()) { 
      return null; 
    } else { 
      if (first.data.equals(t)) { 
        Link<T> temp = first; 
        first = first.next; //變更首結(jié)點(diǎn),為下一結(jié)點(diǎn) 
        return temp; 
      } 
    } 
    Link<T> p = first; 
    Link<T> q = first; 
    while (!p.data.equals(t)) { 
      if (p.next == null) {//表示到鏈尾還沒找到 
        return null; 
      } else { 
        q = p; 
        p = p.next; 
      } 
    } 
     
    q.next = p.next; 
    return p; 
  } 
   
  public void displayList() {//遍歷 
    System.out.println("List (first-->last):"); 
    Link<T> current = first; 
    while (current != null) { 
      current.displayLink(); 
      current = current.next; 
    } 
  } 
   
  public void displayListReverse() {//反序遍歷 
    Link<T> p = first, q = first.next, t; 
    while (q != null) {//指針反向,遍歷的數(shù)據(jù)順序向后 
      t = q.next; //no3 
      if (p == first) {// 當(dāng)為原來的頭時(shí),頭的.next應(yīng)該置空 
        p.next = null; 
      } 
      q.next = p;// no3 -> no1 pointer reverse 
      p = q; //start is reverse 
      q = t; //no3 start 
    } 
    //上面循環(huán)中的if里,把first.next 置空了, 而當(dāng)q為null不執(zhí)行循環(huán)時(shí),p就為原來的最且一個(gè)數(shù)據(jù)項(xiàng),反轉(zhuǎn)后把p賦給first 
    first = p;  
    displayList(); 
  } 
   
  class Link<T> {//鏈結(jié)點(diǎn) 
    T data;   //數(shù)據(jù)域 
    Link<T> next; //后繼指針,結(jié)點(diǎn)    鏈域 
    Link(T data) { 
      this.data = data; 
    } 
    void displayLink() { 
      System.out.println("the data is " + data.toString()); 
    } 
  } 
   
  public static void main(String[] args) { 
    LinkedListInsertSort<Integer> list = new LinkedListInsertSort<Integer>(); 
    Random random = new Random(); 
    int len = 5; 
    Integer[] ary = new Integer[len]; 
    for (int i = 0; i < len; i++) { 
      ary[i] = random.nextInt(1000); 
    } 
    System.out.println("----排序前----"); 
    System.out.println(Arrays.toString(ary)); 
    System.out.println("----鏈表排序后----"); 
    list.sortList(ary); 
    list.displayList(); 
  } 
} 


打印

----排序前---- 
[595, 725, 310, 702, 444] 
----鏈表排序后---- 
List (first-->last): 
the data is 310 
the data is 444 
the data is 595 
the data is 702 
the data is 725 

單鏈表反序:

public class SingleLinkedListReverse { 
   
  public static void main(String[] args) { 
    Node head = new Node(0); 
    Node temp = null; 
    Node cur = null; 
     
    for (int i = 1; i <= 10; i++) { 
      temp = new Node(i); 
      if (i == 1) { 
        head.setNext(temp); 
      } else { 
        cur.setNext(temp); 
      } 
      cur = temp; 
    }//10.next = null; 
     
    Node h = head; 
    while (h != null) { 
      System.out.print(h.getData() + "\t"); 
      h = h.getNext(); 
    } 
    System.out.println(); 
     
    //反轉(zhuǎn)1 
//   h = Node.reverse1(head); 
//   while (h != null) { 
//     System.out.print(h.getData() + "\t"); 
//     h = h.getNext(); 
//   } 
     
    //反轉(zhuǎn)2 
    h = Node.reverse1(head); 
    while (h != null) { 
      System.out.print(h.getData() + "\t"); 
      h = h.getNext(); 
    } 
     
     
  } 
} 
 
/* 
 * 單鏈表的每個(gè)節(jié)點(diǎn)都含有指向下一個(gè)節(jié)點(diǎn)屬性 
 */ 
class Node { 
  Object data;//數(shù)據(jù)對(duì)象  
  Node next; //下一節(jié)點(diǎn) 
   
  Node(Object d) { 
    this.data = d; 
  } 
  Node(Object d, Node n) { 
    this.data = d; 
    this.next = n; 
  } 
  public Object getData() { 
    return data; 
  } 
  public void setData(Object data) { 
    this.data = data; 
  } 
  public Node getNext() { 
    return next; 
  } 
  public void setNext(Node next) { 
    this.next = next; 
  } 
  //方法1 head被重置 
  static Node reverse1(Node head) { 
 
    Node p = null; //反轉(zhuǎn)后新的 頭 
    Node q = head; 
    //輪換結(jié)果:012,123,234,.... 10 null null 
    while (head.next != null) { 
      p = head.next;   // 第1個(gè) 換成第2個(gè) 這時(shí)p表示原始序列頭中的next 
      head.next = p.next; // 第2個(gè) 換成第3個(gè) 
      p.next = q;     //已經(jīng)跑到第1位置的原第2個(gè)的下一個(gè) 就要變成 原第1個(gè) 
      q = p;       //新的第1個(gè) 要變成 當(dāng)前第一個(gè) 
    } 
    return p; 
     
  } 
  //方法2 head沒重置 
  static Node reverse2(Node head) { 
    //將中間節(jié)點(diǎn)的指針指向前一個(gè)節(jié)點(diǎn)之后仍然可以繼續(xù)向后遍歷鏈表 
    Node p1 = head, p2 = head.next, p3; // 前 中 后 
    //輪換結(jié)果 :012, 123, 234, 345, 456.... 9 10 null 
    while (p2 != null) { 
      p3 = p2.next;  
      p2.next = p1; //指向后 變 指向前 
      p1 = p2;   //2、3向前挪 
      p2 = p3; 
    } 
    head.next = null;//head沒變,當(dāng)輸出到0時(shí),再請(qǐng)求0.next 為1 
    return p1; 
  } 
} 

相關(guān)文章

  • java高級(jí)排序之希爾排序

    java高級(jí)排序之希爾排序

    這篇文章主要介紹了java高級(jí)排序之希爾排序 ,需要的朋友可以參考下
    2015-04-04
  • Java中List分片的5種方法小結(jié)

    Java中List分片的5種方法小結(jié)

    本文主要介紹了Java中List分片的5種方法小結(jié),文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-11-11
  • spring的事務(wù)傳播屬性REQUIRED_NESTED原理

    spring的事務(wù)傳播屬性REQUIRED_NESTED原理

    這篇文章主要介紹了spring的事務(wù)傳播屬性REQUIRED_NESTED原理,在spring中,要想使用事務(wù)中的回滾點(diǎn),可以使用傳播屬性NESTED,需要的朋友可以參考下
    2023-05-05
  • Java設(shè)計(jì)模式編程中的責(zé)任鏈模式使用示例

    Java設(shè)計(jì)模式編程中的責(zé)任鏈模式使用示例

    這篇文章主要介紹了Java設(shè)計(jì)模式編程中的責(zé)任鏈模式使用示例,責(zé)任鏈模式可以避免很多請(qǐng)求的發(fā)送者和接收者之間的耦合關(guān)系,需要的朋友可以參考下
    2016-05-05
  • Java中判斷字符串是否相等的實(shí)現(xiàn)

    Java中判斷字符串是否相等的實(shí)現(xiàn)

    這篇文章主要介紹了Java中判斷字符串是否相等的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2021-01-01
  • MyBatis-Plus實(shí)現(xiàn)條件查詢的三種格式例舉詳解

    MyBatis-Plus實(shí)現(xiàn)條件查詢的三種格式例舉詳解

    本文主要介紹了MyBatis-Plus三中條件查詢格式的示例,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2022-08-08
  • Java中類的加載順序剖析(常用于面試題)

    Java中類的加載順序剖析(常用于面試題)

    這篇文章主要介紹了Java中類的加載順序剖析(常用于面試題),本文直接給出代碼實(shí)例和運(yùn)行結(jié)果,給后給出了加載過程總結(jié),需要的朋友可以參考下
    2015-03-03
  • 解決IDEA中 Ctrl+ALT+V這個(gè)快捷鍵無法使用的情況

    解決IDEA中 Ctrl+ALT+V這個(gè)快捷鍵無法使用的情況

    這篇文章主要介紹了解決IDEA中 Ctrl+ALT+V這個(gè)快捷鍵無法使用的情況,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
    2021-02-02
  • Springboot vue導(dǎo)出功能實(shí)現(xiàn)代碼

    Springboot vue導(dǎo)出功能實(shí)現(xiàn)代碼

    這篇文章主要介紹了Springboot vue導(dǎo)出功能實(shí)現(xiàn)代碼,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-04-04
  • SpringBoot整合SpringSecurity認(rèn)證與授權(quán)

    SpringBoot整合SpringSecurity認(rèn)證與授權(quán)

    在項(xiàng)目開發(fā)中,權(quán)限認(rèn)證是很重要的,尤其是一些管理類的系統(tǒng),對(duì)于權(quán)限要求更為嚴(yán)格,本文主要介紹了SpringBoot整合SpringSecurity認(rèn)證與授權(quán),感興趣的可以了解一下
    2023-11-11

最新評(píng)論