插入排序 链表 java_JAVA单链表(多项式)直接插入排序，大家看看我的怎么不行呢...
首先我不說(shuō)你的算法有什么問(wèn)題，我按照我的思路給你寫了一個(gè)和你的差不多的算法，看了之后，如果你用心思考的話，或許就能看出你的算法問(wèn)題出在哪里，為什么會(huì)進(jìn)入無(wú)限循環(huán)。
為了你能夠看得更明白，我就把所有的類都給你貼上，看了之后，相信你能夠看出你寫的算法錯(cuò)誤的原因。
1.節(jié)點(diǎn)類如下：/**
* 多項(xiàng)式節(jié)點(diǎn)
* @author zhq
*
*/
public class PolyNode {
private float coef; // 一元多項(xiàng)式項(xiàng)的系數(shù)
private int exp; // 一元多項(xiàng)式項(xiàng)的次數(shù)
private PolyNode next; // 指向下一個(gè)一元多項(xiàng)式結(jié)點(diǎn)
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 {
/**
* 時(shí)間復(fù)雜度O(n的平方)，空間復(fù)雜度O(n).n是節(jié)點(diǎn)的總數(shù)
*
* @param pl
* 待排序的鏈表多項(xiàng)式
* @return 有序的多項(xiàng)式(按次數(shù)從小到大)
*/
public static PolyList listInsertSort(PolyList pl) {
PolyNode headNode = pl.getHead();
// 指向表已經(jīng)排序的最后一個(gè)節(jié)點(diǎn)
PolyNode lastInOrder;
// 移動(dòng)到適當(dāng)位置的節(jié)點(diǎn)
PolyNode firstOutOfOrder;
// 當(dāng)前節(jié)點(diǎn)
PolyNode current;
// 該引用變量指向current的前一個(gè)節(jié)點(diǎn)
PolyNode trailCurrent;
if (headNode.getNext() == null)// 鏈表為空
System.out.println("Cannot sort an empty list");
else if (headNode.getNext().getNext() == null) {// 鏈表只有一個(gè)節(jié)點(diǎn)
System.out.println("The list is length 1. It is already in order");
} else {// 鏈表多于一個(gè)節(jié)點(diǎn)
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;
}
// 測(cè)試方法
public static void main(String[] args) {
/** 系數(shù) */
float[] cvs = { 1, 2, 3, 5, 10 };
/** 次數(shù) */
int[] evs = { 9, 8, 7, 10, 3 };
PolyList pl = new PolyList();
pl.init(cvs, evs);
System.out.println("排序前：" + pl);
System.out.println("排序后：" + listInsertSort(pl));
}
}
總結(jié)
以上是生活随笔為你收集整理的插入排序 链表 java_JAVA单链表(多项式)直接插入排序，大家看看我的怎么不行呢...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： mysql5.7.14 配置文件_mys
- 下一篇： java对象重用_JAVA：避免重复的创