【代码】链表

发表于 更新于 阅读次数：

前言

链表的Java实现

源代码

  • 基本类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package link;

public class Link {

    // 属性：链表的节点包含两部分数据域和指针域
    private int date;
    private Link next;
    
    // 方法
    public int getDate() {
        return date;
    }
    public void setDate(int date) {
        this.date = date;
    }
    public Link getNext() {
        return next;
    }
    public void setNext(Link next) {
        this.next = next;
    }
    
}
  • 基本操作类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
package link;
/**
 * 链表的基本操作（积木）
 */
public class LinkAlgorithm {

    // 链表的初始化：创建一个空的头节点
    public Link link_Ininal() {
        Link H = new Link();
        // 头节点是数据域不存储数据
        // 指针域的初始化状态
        H.setNext(null);
        return H;
    }

    // 创建新节点：输入x值，给x创建一个新的节点
    public Link link_New(int x) {
        Link p = new Link();
        p.setDate(x);
        p.setNext(null);
        return p;
    }

    // 取得某节点的后续节点
    public Link link_Getnext(Link p) {
        return p.getNext();
    }

    // 设置某节点的后续节点
    public void link_Setnext(Link p, Link q) {
        p.setNext(q);
    }
    
    // 输出链表
    public void link_Print(Link H) {
        Link p;
        p = H.getNext();
        while(p!=null) {
            System.out.println(p.getDate());
            // p向后走
            p = p.getNext();
        }
    }

    // 比较值：定位操作
    public Link link_Search(Link H, int x) {
        Link p;
        // p定位，定位在第一个数据节点
        p = H.getNext();
        while(p!=null) {
            if(p.getDate() == x) {
                break;
            }
            p = p.getNext();
        }
        // 找到和没找到两种情况的返回值：null没找到，非null找到了
        return p;
    }
    
    // 取得表尾节点
    public Link link_Getend(Link H) {
        Link p;
        // p的初始定位
        p = H;
        while(p.getNext()!=null) {
            p = p.getNext();
        }
        return p;
    }
    
    // 判断表空
    public boolean link_Null(Link H) {
        boolean f = false;
        if(H.getNext()==null) {
            f = true;
        }
        return f;
    }
    
    // 排序：变异版的冒泡排序
    public void link_Sort(Link H) {
        Link p,q;
        // 冒泡排序
        // pq两层循环的范围
        for(p = H.getNext(); p.getNext()!=null; p = p.getNext() ) {
            for(q = H.getNext(); q.getNext()!=null; q= q.getNext()) {
                if(q.getDate()>q.getNext().getDate()) {
                    // 值的交换操作
                    int t = q.getDate();
                    q.setDate(q.getNext().getDate());
                    q.getNext().setDate(t);
                }
            }
        }
    }
    
    // 返回某节点的数据
    public int link_Getdata(Link p) {
        return p.getDate();
    }
    
    
}
  • 菜单类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package link;
/**
 * 需要显示的菜单
 */
public class LinkMenu {
    void display()
    { 
        System.out.printf("|----------------------------------------------------------------------------|\n");
        System.out.printf("|------------------------------链表操作---------------------------------------|\n");
        System.out.printf("|----------------------------------------------------------------------------|\n");
        System.out.printf("|-----------  1.创建链表                                           -----------|\n");  
        System.out.printf("|-----------  2.输出链表内容                                       -----------|\n");    
        System.out.printf("|-----------  3.链表的定位插入                                     -----------|\n");
        System.out.printf("|-----------  4.链表中删除指定值的结点                              -----------|\n");
        System.out.printf("|-----------  5.有序插入                                           -----------|\n");
        System.out.printf("|-----------  6.排序                                               -----------|\n");
        System.out.printf("|-----------  7.逆序                                               -----------|\n");
        System.out.printf("|-----------  0.退出                                               -----------|\n");
        System.out.printf("|-----------  8.显示菜单                                           -----------|\n");
        System.out.printf("|-----------------------------------------------------------------------------|\n");
        System.out.printf("|-----------------------------------------------------------------------------|\n");
        System.out.printf("                          （谢谢使用本软件）\n");
        System.out.printf("请选择菜单中操作所对应的编号（1~12，0退出）：\n");

    }
    void found(){
        System.out.printf("|-----------------------------------------------------------------------------|\n");
        System.out.printf("|-----------  A.表头法创建链表                                      -----------|\n");                 
        System.out.printf("|-----------  B.表尾法创建链表                                      -----------|\n");    
        System.out.printf("|-----------------------------------------------------------------------------|\n");
    }

}
  • 解决实际问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
package link;

import java.util.Scanner;

import line.LineMenu;

public class LinkTest {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        LinkAlgorithm A = new LinkAlgorithm();
        Link Head = A.link_Ininal();
        int N;
        // 加载菜单
        LinkMenu M = new LinkMenu();
        M.display();
        while(true) {
            System.out.println("请输入您操作的序号：");
            N = sc.nextInt();
            switch(N) {
            case 1:
                // 菜单1链表的创建
                M.found();
                // 子菜单
                char c;
                System.out.println("请选择您创建链表的方法对应的字母");
                c = sc.next().charAt(0);
                switch(c) {
                case 'a':
                case 'A':
                    // 表头法创建链表
                    int x;
                    Link p;
                    System.out.println("请输入数据（0结束）：");
                    x = sc.nextInt();
                    while(x!=0) {
                        // 把x封装成节点
                        p = A.link_New(x);
                        // 把新节点连接到Head后边：分两步
                        // 1步先让p连接Head后边的节点
                        A.link_Setnext(p, A.link_Getnext(Head));
                        // 2Head连接新节点p
                        A.link_Setnext(Head, p);
                        System.out.println("请输入数据（0结束）：");
                        x = sc.nextInt();
                    }
                    A.link_Print(Head);
                    break;
                case 'b':
                case 'B':
                    // 表尾法创建链表
                    System.out.println("请输入数据（0结束）：");
                    x = sc.nextInt();
                    Link q;
                    // 定位表尾节点
                    p = A.link_Getend(Head);
                    while(x!=0) {
                        // 给x封装成新的节点
                        q = A.link_New(x);
                        // 1p连接新节点
                        A.link_Setnext(p, q);
                        // 2p向后走，定位新表尾节点
                        p = A.link_Getnext(p);
                        System.out.println("请输入数据（0结束）：");
                        x = sc.nextInt();
                    }
                    A.link_Print(Head);
                    break;
                default:
                    return;
                }
                break;
            case 2:
                A.link_Print(Head);
                break;
            case 3:
                // 实现链表的定位插入
                System.out.println("请输入要插入的值：");
                int value = sc.nextInt();
                System.out.println("将该值插入到哪个值后：");
                int num = sc.nextInt();
                Link o = A.link_New(value);
                Link p = A.link_Search(Head, num);
                A.link_Setnext(o, p.getNext());
                A.link_Setnext(p, o);
                
                break;
            case 4:
                // 实现定位删除
                System.out.println("请输入要删除的值：");
                int x = sc.nextInt();
                Link q;
                // 定位查找，需要q、p一前一后向后走
                p = A.link_Getnext(Head);
                q = Head;
                while(p!=null) {
                    if(A.link_Getdata(p)==x) {
                        break;
                    }
                    // p、q同时向后走
                    q = p;
                    p = A.link_Getnext(p);
                }
                // 有两种结果
                if(p!=null) {
                    // 让q的next绕过p为p的下一个节点
                    A.link_Setnext(q, A.link_Getnext(p));
                }else {
                    System.out.println("没有找到");
                }
                break;
            case 7:
                // 逆序
                // 已经有一个待逆序待链表Head
                // 逆序
                // 新建一个新的链表头节点
                Link Head1 = A.link_Ininal();
                // 循环实现
                    // 从旧的链表截取第一个数据节点p
                    // 把截取的p节点采用表头插入法插入到新头节点后边
                while(A.link_Getnext(Head)!=null) {
                    // p指向要截取到节点
                    p = A.link_Getnext(Head);
                    // head绕过p节点指向p的下一个节点
                    A.link_Setnext(Head, A.link_Getnext(p));
                    // p指向head1节点的next节点
                    A.link_Setnext(p, A.link_Getnext(Head1));
                    A.link_Setnext(Head1, p);
                    
                }
                A.link_Print(Head1);
                break;
            default:
                return;
            }
        }
        
    }
}

完成