插入排序 链表 java_JAVA单链表(多项式)直接插入排序，大家看看我的怎么不行呢...
首先我不说你的算法有什么问题，我按照我的思路给你写了一个和你的差不多的算法，看了之后，如果你用心思考的话，或许就能看出你的算法问题出在哪里，为什么会进入无限循环。
为了你能够看得更明白，我就把所有的类都给你贴上，看了之后，相信你能够看出你写的算法错误的原因。
1.节点类如下：/**
* 多项式节点
* @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 "";
}
}
2.链表类如下：
/**
* 初始化链表
* @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 = currentNode.getNext();
}
sb.append(")");
return sb.toString();
}
}
3.核心算法类
/**
* 核心算法类
*
* @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));
}
}
总结
以上是生活随笔为你收集整理的插入排序 链表 java_JAVA单链表(多项式)直接插入排序，大家看看我的怎么不行呢...的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： mysql5.7.14 配置文件_mys
- 下一篇： java对象重用_JAVA：避免重复的创