|
|
楼主 |
发表于 2021-7-31 16:50:28
|
显示全部楼层
public class ArraySort {
public static void main(String[] args)
{
int[] data1 = { 4,2,6,8,1,0,2,6,5,4,1};
Arrays.sort(data1);
for (int i:data1 ) {
System.out.println(i);
}
//上面是一个默认的简单的数组排序，可以看出，值相同的排在一起了，如果除了要排序之外，还需要获得对应的序号怎么办？？？针对这种情况，我写了本实验代码,当有了本代码之后，再做排序取序号将会很容易
//如果使用了java8的新特性，比如stream则有可能性能不是很好，还是要从最基础的java语法角度来处理可能性能更高些
Student[] studentsraw = { new Student("zs", 10),new Student("lisi",11),new Student("wangwu", 9),
new Student("zs", 10),new Student("lisi",11),new Student("wangwu", 9),
new Student("zs", 10),new Student("lisi",11),new Student("wangwu", 9),
new Student("zs", 10),new Student("lisi",11),new Student("wangwu", 9)};
int index = 0;
for (Student s:studentsraw ) {
Unit unit = new Unit(index++,s);
append(unit);
}
List<Unit> all = getall();
for (Unit u:all ) {
System.out.println(u.getIndex()+" : " + u.getStudent().getName() +"--->"+u.getStudent().getAge());
}
}
private static int size;
private static Node<Node<Unit>> nodeHead ,nodeTail;
private static void append(Unit unit) {
if(nodeHead == null) {
nodeHead = new Node<>();
Node<Unit> data = new Node<>();
data.data = unit;
nodeHead.data = data;
nodeTail = nodeHead;
size++;
return;
}
//查整个node有没有这个数据
Node<Unit> ret = searchnNodeReturData(unit);
if(ret == null) {
//说明没有这个数据 nodetail之后放入
Node<Node<Unit>> newNode = new Node<>();
Node<Unit> newdata = new Node<>();
newdata.data = unit;
newNode.data = newdata;
newNode.pre = nodeTail; //新node的pre指向原nodetail
nodeTail.next = newNode; //原nodetail的next指向新node
nodeTail = newNode;//让nodeTail始终指向最后一个node
}
else {
//说明有这个数据，需要放入DATA双链中
Node<Unit> newdata = new Node<>();
newdata.data = unit;
Node<Unit> tmpdata = ret;
while(true) {
if(ret.next == null){
ret.next = newdata;//最后一个node的next要指向新数据
newdata.pre = ret;//新数据的pre要指向原最后一个node
break;
}
ret = ret.next;
}
}
size++;
}
/**
* 将所有的Unit全部返回
* @return
*/
private static List<Unit> getall() {
if(nodeHead==null)
return null;
List<Unit> unitList = new ArrayList<>();
for(Node<Node<Unit>> tmp = nodeHead;tmp != null;tmp = tmp.next) {
for(Node<Unit> tmpdata = tmp.data; tmpdata != null; tmpdata = tmpdata.next) {
unitList.add(tmpdata.data);
}
}
return unitList;
}
private static List<Unit> getFirst() {
if(nodeHead==null)
return null;
List<Unit> firstList = new ArrayList<>();
for(Node<Unit> data = nodeHead.data;data != null;data = data.next) {
firstList.add(data.data);
}
return firstList;
}
private static List<Unit> getLast() {
if(nodeTail == null)
return null;
List<Unit> lastList = new ArrayList<>();
for(Node<Unit> data = nodeTail.data;data != null;data = data.next) {
lastList.add(data.data);
}
return lastList;
}
private static int deleunitdata(Unit unit) { //有可能有相同值的数据，只有unit中除了数据之外还有index，所以参数只能是unit
//index和realdata都相同的则删除
if((nodeHead==null) || (nodeHead.data == null) || (unit == null)) //表示是空链或unit为空
return -1;
int offset = 0;
for(Node<Node<Unit>> tmphead = nodeHead;tmphead != null;tmphead = tmphead.next) {
if(tmphead.data.data.compareTo(unit.getStudent()) == 0) {
offset = 0;
for(Node<Unit> tmpdata = tmphead.data; tmpdata != null; tmpdata = tmpdata.next) {
if(tmpdata.data.getIndex() == unit.getIndex()) { //还要判断index是否相同
if(offset == 0) { //头部 nodeTail要不要考虑？？？
Node<Node<Unit>> pre = tmphead.pre;
Node<Node<Unit>> next = tmphead.next;
if(tmpdata.next == null) { //只有这一个节点，没有重复的数据 ,本Node<Node<Unit>>删除掉，调整双链相关指针
if((tmphead.data.data.getIndex() == nodeTail.data.data.getIndex()) &&
(tmphead.data.data.getStudent().compareTo(nodeTail.data.data.getStudent()) == 0)){
pre.next= next;//next此时就是null
nodeTail = pre;//nodeTail要前移
}
else {
pre.next= next;
next.pre = pre;
}
}
else { //有多个节点的重复数据
Node<Unit> newdatanode = tmpdata.next; //不可能是空即尾部
newdatanode.pre = null;//由原来的pre变成null，因为现在为首部了
Node<Node<Unit>> curNode = new Node<>();
curNode.data = newdatanode;
if((tmphead.data.data.getIndex() == nodeTail.data.data.getIndex()) &&
(tmphead.data.data.getStudent().compareTo(nodeTail.data.data.getStudent()) == 0)){
nodeTail = curNode; //nodeTail调整为新节点
pre.next = curNode;
curNode.pre = pre;
}
else {
//下面四句让双链指针再次建立联系
pre.next = curNode;//指向删除的节点，现在要指向新创建的节点
curNode.pre = pre;
curNode.next = next;//新节点的next指向被删除节点的next
next.pre = curNode;
}
}
}
else { //找到节点时不是头部，是中间的某个节点 不用考虑nodeTail
Node<Unit> pre = tmpdata.pre;
Node<Unit> next = tmpdata.next;
pre.next = next;
if(tmpdata.next != null) { //不是最后一个
next.pre = pre;
}
}
return 0;
}
offset++;
}
}
}
return -1;
}
/**
* 查找某个node的data中的数据数量，0表示空,返回值表示下次插入数据的"offset"，也就是当前data中数据的数量
* @param data 每个node的data其实是一个双向链表，只存head,所以调用此函数时data参数必须是node的data也就是双链的head
* @return
*/
private static int getDataLastPosition(Node<Unit> data) { //数据值都是相同的，只是找一个位置而已
if((data==null) || (data.data == null)) //表示是空链 或unit为空
return 0;
int position = 0;
do {
position++;
data = data.next;
}while (data.next != null);
return position;
}
/**
* 在node中查找数据，找到则返回node的data节点即重复数据双向链的头，没找到则返回null
* @param unit
* @return
*/
private static Node<Unit> searchnNodeReturData(Unit unit) { //java方法重载不能以返回值类型来区分
if((nodeHead==null) || (nodeHead.data == null) || (unit == null)) //表示是空链或unit为空
return null;
for(Node<Node<Unit>> tmphead = nodeHead;tmphead != null;tmphead = tmphead.next) {
if(tmphead.data.data.compareTo(unit.getStudent()) == 0)
return tmphead.data;
}
return null;
}
/**
* 查找整个Node中是否有数据unit，找到则返回true，没找到返回false
* @param unit
* @return
*/
private static boolean searchNode(Unit unit) {
if((unit == null) || (nodeHead == null)) {
return false;
}
for(Node<Node<Unit>> tmphead = nodeHead;tmphead != null;tmphead = tmphead.next) {
if(tmphead.data.data.compareTo(unit.getStudent()) == 0)
return true;
}
return false;
}
}
|
|
[复制链接]
发表于 2021-7-31 16:48:27
发表于 2021-7-31 17:02:10