当前位置：首页 > news >正文

数据结构：链表链表按结点中第j个数据属性排序(冒泡排序法)

news 来源：原创 2024/5/2 9:01:46

创建结点类，链表类，测试类

 1 import java.lang.Object;
 2 //结点node=数据date+指针pointer
 3 public class Node {
 4     Object iprop;
 5     public Object getIprop(int i){
 6     switch(i){
 7     case 1:iprop=num;break;
 8     case 2:iprop=name;break;
 9     case 3:iprop=score;break;
10     }
11     return iprop;
12     }
13    //数据data
14     Object num,name,score;
15     //指针pointer
16     Node next;
17     public Node(Object obj1,Object obj2,Object obj3){
18         num=obj1;
19         name=obj2;
20         score=obj3;
21     }
22     public Node(){
23     
24     }
25 }

View Code

  1 //链表List=头结点head+尾结点tail+链表名Lname
  2 public class List {
  3 
  4     // 头结点head
  5     Node head;
  6     // 尾结点tail
  7     Node tail;
  8     // 链表名Lname
  9     String Lname;
 10     int length=0;
 11 
 12     // 初始化链表时，里面没有结点，为空链表
 13     public List(String str) {
 14         head = tail = null;
 15         Lname = str;
 16     }
 17 
 18     public List() {
 19         head = tail = null;
 20         Lname = "List";
 21     }
 22 
 23     // 头插法
 24     public List appendToFront(Node n) {
 25         
 26         if(this.head==null){
 27            head=tail=n;
 28            length++;
 29            //n.next=null;
 30         }else{
 31             
 32             n.next=head;
 33             head=n;
 34             length++;
 35         }
 36         return this;
 37 
 38     }
 39 
 40     // 尾插法
 41     public List appendToTail(Node n) {
 42         //
 43         if(head!=null){
 44            tail.next=n;
 45            tail=n;
 46         }else{
 47             head=tail=n;
 48             //n.next=null;
 49         }
 50         return this;
 51 
 52     }
 53 
 54     // 插入结点到第i个结点之后
 55     public void insert(Node n, int i) {
 56 
 57     }
 58 
 59     // 插入结点到第j个data为obj的结点之后
 60     public void insert(Node n, Object obj, int i) {
 61 
 62     }
 63 
 64     // 遍历链表
 65     public void visitAll() {
 66        //创建pointer p
 67        Node p=new Node();
 68        //拿到头结点的引用
 69        p=head;
 70        //顺序拿到结点做展示
 71        for(;p!=null;){
 72            System.out.println("num:"+p.num+"name:"+p.name+"score:"+p.score);
 73            p=p.next;
 74        }
 75     }
 76 
 77     // 拿到第i个结点
 78     public Node getNode(int i) {
 79         //定义浏览指针p
 80         Node p=new Node();
 81         
 82         //定义循环参数j
 83         int j=1;
 84         
 85         //循环结点
 86         p=this.head;
 87         if(p!=null)
 88         for(;j<i;j++){
 89             
 90             p=p.next;
 91             if(p==null){System.out.println("p==null遍历结束，无此结点");break;}
 92             
 93         }
 94         return p;
 95     }
 96 
 97     // 拿到第j个data为obj的结点
 98     public Node getNode(Object obj, int j) {
 99         //拿到头结点的引用
100         Node p=head;
101         //循环数据并比较data
102             for(;p!=null;){
103                 
104                 for(int i=0;i<j;i++){
105                 Object prop=p.getIprop(j);    
106                 if(prop!=null&&prop.equals(obj)) {return p;}
107                 }
108                 p=p.next;
109             }
110         return p;
111     }
112 
113     // 删除第i个结点
114     public void delete(int i) {
115         //找到i结点
116 
117     }
118 
119     // 删除第j个data为obj的结点
120     public void delete(Object obj, int j) {
121 
122     }
123 
124     // 删除全部
125     public void deleteAll() {
126 
127     }
128     // 链表的排序:list中的node按第j个data的值进行排序
129     // >>直接插入法
130     public List listSort(int j){
131         
132         //循环当前链表的结点对象，找到第j个data值
133         Node p=head;//想象head 下标为0,head.next依次类推
134         int[] datas=new int[this.length];
135         for(int i=0;p!=null;i++){
136             Object prop=p.getIprop(j);//
137             if(prop!=null){
138                 System.out.println("循环到下标为"+i+"的结点");
139                 datas[i]=Integer.parseInt(prop.toString());
140                 
141             }
142             p=p.next;
143         }
144         //冒泡排序
145         Node pre=null;
146         
147         for(int i=0;i<datas.length-1;i++){
148             pre=null;
149             p=head;
150             
151             for(int k=0;k<datas.length-i-1;k++){
152                 
153                 
154                 if(datas[k]>datas[k+1]){
155                     
156                     int temp=datas[k];
157                     datas[k]=datas[k+1];
158                     datas[k+1]=temp;
159                     
160                     
161                     Node tempNode=p.next.next;
162                     
163                     pre.next=p.next;
164                     p.next.next=p;
165                     p.next=tempNode;
166                     
167                     pre=pre.next;
168                     
169                 }else{
170                 //拿到前驱结点
171                 pre=p;
172                 p=p.next;
173                 }
174             }
175         }
176         
177         return this;
178     }
179     public static void main(String[] arg){
180         int[] datas={4,2,5,6,7,3,1,0,9,8};
181         //冒泡排序法
182         for(int i=0;i<datas.length-1;i++){
183             for(int j=0;j<datas.length-(i+1);j++){
184                 if(datas[j]>datas[j+1]){
185                     int temp=datas[j];
186                     datas[j]=datas[j+1];
187                     datas[j+1]=temp;
188                 }
189             }
190         }
191         for(int i=0;i<datas.length;i++){
192         System.out.println(datas[i]);}
193     }
194 
195     
196 }

View Code

 1 public class TestList {
 2     public static void main(String[] arg){
 3         Node n0=new Node(125,"n0","91");
 4         Node n1=new Node(123,"n1","98");
 5         Node n2=new Node(121,"n2","99");
 6         Node n3=new Node(125,"n3","96");
 7         Node n4=new Node(125,"n4","95");
 8         Node n5=new Node(125,"n5","97");
 9         Node n6=new Node(125,"n6","93");
10         Node n7=new Node(125,"n7","94");
11         Node n8=new Node(125,"n8","92");
12         Node n9=new Node(125,"n9","90");
13         
14         
15         List f1=new List("f1List");
16         //头插法
17         f1.appendToFront(n0).appendToFront(n1).appendToFront(n2).appendToFront(n3)
18         .appendToFront(n4).appendToFront(n5).appendToFront(n6).appendToFront(n7)
19         .appendToFront(n8).appendToFront(n9);
20         
21         
22         //拿到排好序的链表f2;
23         f1.listSort(3).visitAll();
24         
25         
26         
27         
28     }
29 
30 }