JAVA单链表(多项式)直接插入排序，大家看看我的怎么不行呢

Question

目的就是按照结点的exp域值排序，从小到大

1.首先是结点类如下：

[code="java"]
public class PolyNode {
private float coef; // 一元多项式项的系数
private int exp; // 一元多项式项的次数
private PolyNode next; // 指向下一个一元多项式结点

public PolyNode(float coef, int exp) {
    this.coef = coef;
    this.exp = exp;
    next = null;
}

public float getCoef() {
    return coef;
}

public void setCoef(float coef) {
    this.coef = coef;
}

public int getExp() {
    return exp;
}

public void setExp(int exp) {
    this.exp = exp;
}

public PolyNode getNext() {
    return next;
}

public void setNext(PolyNode next) {
    this.next = next;
}

}
[/code]

2.下面是链表类如下：

[code="java"]
public class PolyList {
public PolyNode head;

public PolyList() {
    head = new PolyNode(-10001.0f, -10001);
}
   //初始化链表
public void init(float[] cvs, int[] evs) {
    PolyNode newNode, node = head;
    for (int i = 0; i < evs.length; i++) {
        newNode = new PolyNode(cvs[i], evs[i]);
        newNode.setNext(node.getNext());
        node.setNext(newNode);
        node = node.getNext();
    }
}

}
[/code]

3.下面是我的代码，大家帮忙看看为什么不对，谢谢了，我写了很久都不正确

[code="java"]
/**
* 多项式按exp数据域值从小到大顺序排列。
*
* @param l
*/
public static PolyList listInsertSort_PL(PolyList l) {
PolyNode p = l.head;
PolyList l2 = new PolyList();
PolyNode q = l2.head;
q.setNext(p.getNext());
//int i = 1;
while (p.getNext() != null) {
System.out.println(p.getNext().getExp() + " out");
PolyNode s = p.getNext();
while (q.getNext() != null) {
System.out.println("in " + q.getExp()+" "+s.getExp());
if (s.getExp() < q.getNext().getExp()) {
System.out.println(q.getNext().getExp()+" insert now!");
s.setNext(q.getNext());
q.setNext(s);
break;
}
System.out.println(q.getNext().getExp());
q = q.getNext();
}
q.setNext(s);
p = p.getNext();
}

    return l2;
}
     //测试方法
     public static void main(String[] args) {
    int[] evs = { 9, 8, 7 };
    float[] cvs = { 1, 2, 3 };
    PolyList l = new PolyList();
    l.init(cvs, evs);
    PolyList pls = Test04.listInsertSort_PL(l);
    PolyNode pl = pls.head;
    System.out.print("result : ");
    while (pl.getNext() != null) {
        System.out.print(pl.getNext().getExp() + " ");
        pl = pl.getNext();
    }
}

[/code]

请大家指教！

Answer 1

[size=medium][color=red]首先我不说你的算法有什么问题，我按照我的思路给你写了一个和你的差不多的算法，看了之后，如果你用心思考的话，或许就能看出你的算法问题出在哪里，为什么会进入无限循环。[/color][/size]

为了你能够看得更明白，我就把所有的类都给你贴上，看了之后，相信你能够看出你写的算法错误的原因。

1.节点类如下：

[code="java"]/**

• 多项式节点

• @author zhq
  *
  */
  public class PolyNode {
  private float coef; // 一元多项式项的系数
  private int exp; // 一元多项式项的次数
  private PolyNode next; // 指向下一个一元多项式结点

  public PolyNode(float coef, int exp) {
  this.coef = coef;
  this.exp = exp;
  next = null;
  }

  public float getCoef() {
  return coef;
  }

  public void setCoef(float coef) {
  this.coef = coef;
  }

  public int getExp() {
  return exp;
  }

  public void setExp(int exp) {
  this.exp = exp;
  }

  public PolyNode getNext() {
  return next;
  }

  public void setNext(PolyNode next) {
  this.next = next;
  }

  public String toString() {
  return "<" + coef + ":" + exp + ">";
  }
  }[/code]

2.链表类如下：
[code="java"]/**

• 初始化链表

• @author zhq
  *
  */
  public class PolyList {

  private PolyNode head, newNode;

  public PolyList() {
  head = new PolyNode(-10001.0f, 10001);
  }

  // 初始化链表
  public void init(float[] cvs, int[] evs) {
  PolyNode currentNode = head.getNext();
  for (int i = 0; i < evs.length; i++) {
  newNode = new PolyNode(cvs[i], evs[i]);
  if (currentNode == null) {
  currentNode = newNode;
  head.setNext(currentNode);
  } else {
  currentNode.setNext(newNode);
  currentNode = newNode;
  }
  }
  }

  public PolyNode getHead() {
  return head;
  }

  public void setHead(PolyNode head) {
  this.head = head;
  }

  public String toString() {
  StringBuilder sb = new StringBuilder();
  PolyNode currentNode = head;
  sb.append("(");
  while (currentNode != null) {

      sb.append("<" + currentNode.getCoef() + ":" + currentNode.getExp()
              + ">");
      currentNode = currentNode.getNext();
  }
  
  sb.append(")");
  return sb.toString();
  

  }
  }[/code]

3.核心算法类

[code="java"]/**

• 核心算法类
• @author zhq

• /
  public class Demo {
  /*

  • 时间复杂度O(n的平方)，空间复杂度O(n).n是节点的总数
  • @param pl
  • 待排序的链表多项式
  • @return 有序的多项式（按次数从小到大） */ public static PolyList listInsertSort(PolyList pl) { PolyNode headNode = pl.getHead(); // 指向表已经排序的最后一个节点 PolyNode lastInOrder; // 移动到适当位置的节点 PolyNode firstOutOfOrder; // 当前节点 PolyNode current; // 该引用变量指向current的前一个节点 PolyNode trailCurrent; if (headNode.getNext() == null)// 链表为空 System.out.println("Cannot sort an empty list"); else if (headNode.getNext().getNext() == null) {// 链表只有一个节点 System.out.println("The list is length 1. It is already in order"); } else {// 链表多于一个节点 lastInOrder = headNode.getNext(); while (lastInOrder.getNext() != null) { firstOutOfOrder = lastInOrder.getNext(); if (firstOutOfOrder.getExp() < lastInOrder.getExp()) { lastInOrder.setNext(firstOutOfOrder.getNext()); firstOutOfOrder.setNext(headNode.getNext()); headNode.setNext(firstOutOfOrder); } else { trailCurrent = headNode; current = headNode.getNext(); while (current.getExp() < firstOutOfOrder.getExp()) { trailCurrent = current; current = current.getNext(); } if (current != firstOutOfOrder) { lastInOrder.setNext(firstOutOfOrder.getNext()); firstOutOfOrder.setNext(current); trailCurrent.setNext(firstOutOfOrder); } else { lastInOrder = lastInOrder.getNext(); } } } } return pl; }

  // 测试方法
  public static void main(String[] args) {
  /** 系数 /
  float[] cvs = { 1, 2, 3, 5, 10 };
  /* 次数 */
  int[] evs = { 9, 8, 7, 10, 3 };
  PolyList pl = new PolyList();
  pl.init(cvs, evs);
  System.out.println("排序前：" + pl);
  System.out.println("排序后：" + listInsertSort(pl));
  }
  }[/code]