线性表 | 希亚的西红柿のBlog

文章最后更新于 1414 天前，其中的信息可能已经过时。

本篇文章将详细讲述数据结构 线性表 章节的内容，~~没想到距离上次更新已经快两个礼拜了~~。

本教程编程语言采用 JAVA ,文章框架参考自 HUST数据结构PPT ,源码内容参考自 尚硅谷 JAVA 数据结构教程 。

线性表章节部分将简单讲述概念方面的问题，重点将放在具体的代码实现过程中。

线性表的定义

线性表的逻辑结构

线性表：由 $n(n≥0)$ 个数据元素 $(a_1,a_2,..., a_n)$ 构成的有限序列，记作: $L=(a_1,a_2,...,a_n)$ ， $a_1$ 称为首元素， $a_n$ 称为尾元素。
表长：线性表中数据元素的数目。
空表：不含数据元素的线性表。

在线性表 $L=(a_1,a_2,...,a_n)$ 中：

$a_{i-1}$ 是 $a_i$ 的直接前驱（1<i<=n）
$a_{i+1}$ 是 $a_i$ 的直接后继（1<=i<n）
$a_1$ 没有前驱， $a_n$ 没有后继, $a_i$ 有且仅有一个前驱和后继（1<i<n）

抽象数据类型线性表的定义

抽象类型的线性表主要定义几个属性和方法

InitList(&L) //构造空表 L。
LengthList(L) //求表 L 的长度
GetElem(L,i,&e) //取元素 ai,由 e 返回 ai
PriorElem(L,ce,&pre_e) //求 ce 的前驱,由 pre_e 返回
InsertElem(&L,i,e) //在元素 ai 之前插入新元素 e
DeleteElem(&L,i) //删除第 i 个元素
EmptyList(L) //判断 L 是否为空表

线性表的顺序表示（顺序存储结构）

顺序分配

定义：将线性表中的数据元素依次存放到计算机存储器中一组地址连续的存储单元中, 这种分配方式称为顺序分配或顺序映像。由此得到的存储结构称为顺序存储结构或向量(一维数组）。
线性表的几个参数
- a:首元素的地址。
- sizeof(a[0]):线性表元素所占的储存空间的大小。
- sizeof(a[n]):线性表的长度。

寻址公式

顺序储存方式的地址查询与数组类似，故不再赘述，感兴趣的读者可以自己查询相关资料。

顺序储存结构的评价

是一种随机存取结构，存取任何元素的时间是一个常数，速度快。
结构简单，逻辑上相邻的元素在物理上也是相邻的。
不使用指针，节省存储空间。

稀疏数组的实现

书写思路： 二维数组转稀疏数组:
1. 遍历原始二维数组得到，有效数字的个数sum。
2. 创建稀疏数组int[sum+1][3]。
3. 记录chessRow和chessCol以及有效数字count。
4. 遍历数组,为稀疏数组sparseArr赋值。
5. 返回稀疏数组。

稀疏数组转二维数组: 1. 创建原有大小的二维数组。 2. 将稀疏数组中的有效数字返回到原来的二维数组中。 3. 返回原来的二维矩阵。

代码实现:

查看代码实现

编写函数

1
package DataStructure;
2

3
public class SparseArray {
4
 // 主函数：负责打印原始数组，转换后的稀疏数组，以及在转换回来的二维数组
5
 public static void main(String[] args) {
6
     int[][] chessArr = new int[11][11];
7
     chessArr[1][2] = 1;
8
     chessArr[2][3] = 2;
9
     chessArr[5][5] = 5;
10
     System.out.println("Raw array preview:");
11
     printChessArray(chessArr);
12

13
     int[][] sparseArr = chessToSparse(chessArr);
14
     System.out.println("chessArray to sparseArray:");
15
     printChessArray(sparseArr);
16

17
     int[][] chessArr2 = sparseToChess(sparseArr);
18
     System.out.println("sparseArray to chessArray:");
19
     printChessArray(chessArr2);
20
 }
21

22
 // 二维数组转稀疏数组：
23
 // 1. 记录有效数字的个数sum
24
 // 2. 创建稀疏数组int[sum+1][3]
25
 // 3. 记录chessRow和chessCol以及有效数字count
26
 // 4. 遍历数组,为稀疏数组sparseArr赋值
27
 // 5. 返回稀疏数组
28
 private static int[][] chessToSparse(int[][] chessArr) {
29
     int sum = 0;
30
     for (int[] row : chessArr) {
31
         for (int chess : row) {
32
             if (chess != 0) {
33
                 sum++;
34
             }
35
         }
36
     }
37
     int[][] sparseArr = new int[sum + 1][3];
38
     int chessRow = chessArr.length;
39
     int chessCol = 0;
40
     int count = 0;
41
     for (int i = 0; i < chessArr.length; i++) {
42
         int[] rows = chessArr[i];
43
         if (chessCol == 0) {
44
             chessCol = rows.length;
45
         }
46
         for (int j = 0; j < rows.length; j++) {
47
             int chess = rows[j];
48
             if (chess == 0) {
49
                 continue;
50
             }
51
             count++;
52
             sparseArr[count][0] = i;
53
             sparseArr[count][1] = j;
54
             sparseArr[count][2] = chess;
55
         }
56
     }
57
     sparseArr[0][0] = chessRow;
58
     sparseArr[0][1] = chessCol;
59
     sparseArr[0][2] = sum;
60
     return sparseArr;
61
 }
62

63
 /*
64
  * 1. 创建原有大小的二维数组
65
  * 2. 将稀疏数组中的有效数字返回到原来的二维数组中
66
  * 3. 返回原来的二维矩阵
67
  */
68
 private static int[][] sparseToChess(int[][] sparseArr) {
69
     int[][] chessArr = new int[sparseArr[0][0]][sparseArr[0][1]];
70
     for (int i = 1; i < sparseArr.length; i++) {
71
         int[] rows = sparseArr[i];
72
         chessArr[rows[0]][rows[1]] = rows[2];
73
     }
74
     return chessArr;
75
 }
76

77
 /*
78
  * 通过两个for循环每行循环打印输出
79
  */
80
 public static void printChessArray(int[][] chessArr) {
81
     for (int[] row : chessArr) {
82
         for (int data : row) {
83
             System.out.printf("%-2d\t", data);
84
         }
85
         System.out.println("");
86
     }
87
 }
88
}

输出结果

1
Raw array preview:
2
0       0       0       0       0       0       0       0       0       0       0
3
0       0       1       0       0       0       0       0       0       0       0
4
0       0       0       2       0       0       0       0       0       0       0
5
0       0       0       0       0       0       0       0       0       0       0
6
0       0       0       0       0       0       0       0       0       0       0
7
0       0       0       0       0       5       0       0       0       0       0
8
0       0       0       0       0       0       0       0       0       0       0
9
0       0       0       0       0       0       0       0       0       0       0
10
0       0       0       0       0       0       0       0       0       0       0
11
0       0       0       0       0       0       0       0       0       0       0
12
0       0       0       0       0       0       0       0       0       0       0
13
chessArray to sparseArray:
14
11      11      3
15
1       2       1
16
2       3       2
17
5       5       5
18
sparseArray to chessArray:
19
0       0       0       0       0       0       0       0       0       0       0
20
0       0       1       0       0       0       0       0       0       0       0
21
0       0       0       2       0       0       0       0       0       0       0
22
0       0       0       0       0       0       0       0       0       0       0
23
0       0       0       0       0       0       0       0       0       0       0
24
0       0       0       0       0       5       0       0       0       0       0
25
0       0       0       0       0       0       0       0       0       0       0
26
0       0       0       0       0       0       0       0       0       0       0
27
0       0       0       0       0       0       0       0       0       0       0
28
0       0       0       0       0       0       0       0       0       0       0
29
0       0       0       0       0       0       0       0       0       0       0

线性表的链式存储结构

基本概念

链表是以节点的方式来存储，是 链式存储。
每个节点包含 data 域、next 域，next 域指向下一个节点。
链表还分：带头节点、不带头节点，根据实际需求来确定。
链表的各个节点不一定是连续存储。

单链表

单链表的一般形式

单链表的代码实现(考虑一个这样的场景使用带头单链表实现P5R Phantom Thieves的成员管理)

查看代码实现

完成对怪盗团成员的增删查改操作。
第一种方法：在添加成员时,直接添加到链表的尾部。
第二种方法：在添加成员时,根据序号将成员添加到指定的位置，如果有这个序号，则添加失败并给出提示。

构造链表节点的类

1
// 构造链表中的一个节点
2
class HeroNode {
3
 // 定义4个基本属性
4
 public int no; // 序号
5
 public String name; // 名字
6
 public String nickName; // 代号
7
 public HeroNode next; // 指针域
8

9
 // 书写构造函数
10
 public HeroNode(int no, String name, String nickName) {
11
     this.no = no;
12
     this.name = name;
13
     this.nickName = nickName;
14
 }
15

16
 // 为方便重新打印重写toString函数
17
 @Override
18
 public String toString() {
19
     return "HeroNode{" +
20
             "no=" + no +
21
             ", name='" + name + '\'' +
22
             ", nickName='" + nickName + '\'' +
23
             '}';
24
 }
25
}

单链表反转思路
1. 定义一个新的reverseHead节点。
2. 从原链表中依次取出节点，并始终添加到reverseHead的第一个节点。 next = cur.next; cur.next = reverseHead.next; reverseHead.next = cur; cur = next;
3. 将head节点的next指向reverseHead节点的next。

构造链表类

1
// 单向链表节点的书写
2
class SingleLinkedList {
3
 // 创建一个头节点
4
 private HeroNode head = new HeroNode(0, "", "");
5

6
 // 添加节点，将新加入的元素添加至链表的最后
7

8
 public void add(HeroNode node) {
9
     HeroNode temp = head;
10
     while (true) {
11
         if (temp.next == null) {
12
             break;
13
         }
14
         temp = temp.next;
15
     }
16
     temp.next = node;
17
 }
18

19
 // 打印链表中的数据
20
 public void list() {
21
     if (head.next == null) {
22
         System.out.println("The linked list is empty!");
23
         return;
24
     }
25
     HeroNode temp = head.next;
26
     while (true) {
27
         if (temp == null) {
28
             break;
29
         }
30
         System.out.println(temp);
31
         temp = temp.next;
32
     }
33
 }
34

35
 // 有序插入元素
36
 public void addByOrder(HeroNode node) {
37
     // 分为节点为空 大于 相等三种情况来书写函数
38
     HeroNode temp = head; // 此处temp为辅助变量存放在栈中，指向堆空间的head
39
     boolean exist = false;
40
     while (true) {
41
         if (temp.next == null) {
42
             break;
43
         }
44
         if (temp.next.no > node.no) {
45
             break;
46
         }
47
         if (temp.next.no == node.no) {
48
             exist = true;
49
             break;
50
         }
51
         temp = temp.next;
52
     }
53
     if (exist) {
54
         System.out.printf("The phantom thief number %d to be inserted already exists and can't be added! \n",
55
                 node.no);
56
         return;
57
     }
58
     node.next = temp.next;
59
     temp.next = node;
60
 }
61

62
 // 书写更新链表数据函数
63
 public void update(HeroNode newNode) {
64
     // 分为空和相等来区分计算
65
     if (head.next == null) {
66
         System.out.println("The linked list is empty!");
67
         return;
68
     }
69
     HeroNode temp = head.next;
70
     boolean exist = false;
71
     while (true) {
72
         if (temp == null) {
73
             System.out.println("The linked list is empty!");
74
             return;
75
         }
76
         if (temp.no == newNode.no) {
77
             exist = true;
78
             break;
79
         }
80
         temp = temp.next;
81
     }
82
     if (exist) {
83
         temp.name = newNode.name;
84
         temp.nickName = newNode.nickName;
85
     } else {
86
         System.out.printf("Phantom thief with number %d not found", newNode.no);
87
     }
88
 }
89

90
 // 删除节点操作
91
 public void delete(int no) {
92
     if (head.next == null) {
93
         System.out.println("The linked list is empty!");
94
         return;
95
     }
96
     HeroNode temp = head;
97
     boolean exist = false; // 是否找到要删除的节点
98
     while (true) {
99
         if (temp.next == null) {
100
             break;
101
         }
102
         if (temp.next.no == no) {
103
             exist = true;
104
             break;
105
         }
106
         temp = temp.next;
107
     }
108
     if (!exist) {
109
         System.out.printf("Phantom thief with number %d not found! \n", no);
110
         return;
111
     }
112
     // 删除操作
113
     temp.next = temp.next.next;
114
 }
115

116
 // 统计有效节点的个数，即遍历链表
117
 public int length() {
118
     HeroNode temp = head.next;
119
     int num = 0;
120
     if (head.next == null) {
121
         return 0;
122
     }
123
     while (temp != null) {
124
         num++;
125
         temp = temp.next;
126
     }
127
     return num;
128
 }
129

130
 // 查找单链表中的倒数第k个节点
131
 public HeroNode findLastIndexNode(int index) {
132
     // 通过size与index的大小来判断
133
     int size = length();
134
     if (size == 0) {
135
         return null;
136
     }
137
     if (index <= 0 || index > size) {
138
         return null;
139
     }
140
     HeroNode cur = head.next;
141
     for (int i = 0; i < size - index; i++) {
142
         cur = cur.next;
143
     }
144
     return cur;
145
 }
146

147
 // 单链表的反转
148
 public void reverse() {
149
     // 始终添加到第一个节点
150
     if (head.next == null) {
151
         return;
152
     }
153
     HeroNode cur = head.next;
154
     HeroNode next = null;
155
     HeroNode reverseHead = new HeroNode(0, "", "");
156

157
     while (cur != null) {
158
         next = cur.next; // 储存下一个元素的指针
159
         cur.next = reverseHead.next;
160
         reverseHead.next = cur;
161
         cur = next;
162
     }
163
     head.next = reverseHead.next;
164
 }
165

166
 public void reversePrint() {
167
     if (head.next == null) {
168
         System.out.println("The Linked List is Empty!");
169
         return;
170
     }
171

172
     Stack<HeroNode> stack = new Stack<>();
173
     HeroNode cur = head.next;
174
     // 遍历原链表，入栈
175
     while (cur != null) {
176
         stack.push(cur);
177
         cur = cur.next;
178
     }
179
     // 打印栈
180
     while (!stack.empty()) {
181
         System.out.println(stack.pop());
182
     }
183
 }
184
}

测试函数

1
 public static void main(String[] args) {
2
     SingleLinkedListDemo singleLinkedListDemo = new SingleLinkedListDemo();
3
     singleLinkedListDemo.test1();
4
     singleLinkedListDemo.test2();
5
 }
6

7
 public void test1() {
8
     HeroNode hero1 = new HeroNode(1, "Amamiya Ren", "Joker");
9
     HeroNode hero2 = new HeroNode(2, "Ryuji Sakamoto", "Skull");
10
     HeroNode hero3 = new HeroNode(3, "Anne Takamaki", "Panther");
11
     HeroNode hero4 = new HeroNode(4, "Yusuke Kitagawa", "Fox");
12
     SingleLinkedList singleLinkedList = new SingleLinkedList();
13
     singleLinkedList.add(hero1);
14
     singleLinkedList.add(hero2);
15
     singleLinkedList.add(hero3);
16
     singleLinkedList.add(hero4);
17
     singleLinkedList.list();
18
 }
19

20
 public void test2() {
21
     HeroNode hero1 = new HeroNode(1, "Amamiya Ren", "Joker");
22
     HeroNode hero2 = new HeroNode(2, "Ryuji Sakamoto", "Skull");
23
     HeroNode hero3 = new HeroNode(3, "Anne Takamaki", "Panther");
24
     HeroNode hero4 = new HeroNode(4, "Yusuke Kitagawa", "Fox");
25

26
     SingleLinkedList singleLinkedList = new SingleLinkedList();
27

28
     singleLinkedList.addByOrder(hero4); // 添加顺序提前
29
     singleLinkedList.addByOrder(hero2);
30
     singleLinkedList.addByOrder(hero1);
31
     singleLinkedList.addByOrder(hero3);
32
     singleLinkedList.addByOrder(hero3);
33
     singleLinkedList.list();
34
 }
35

36
 private SingleLinkedList singleLinkedList;
37

38
 @Before
39
 public void before() {
40
     HeroNode hero1 = new HeroNode(1, "Amamiya Ren", "Joker");
41
     HeroNode hero2 = new HeroNode(2, "Ryuji Sakamoto", "Skull");
42
     HeroNode hero3 = new HeroNode(3, "Anne Takamaki", "Panther");
43
     HeroNode hero4 = new HeroNode(4, "Yusuke Kitagawa", "Fox");
44

45
     singleLinkedList = new SingleLinkedList();
46

47
     singleLinkedList.addByOrder(hero4); // 添加顺序提前
48
     singleLinkedList.addByOrder(hero2);
49
     singleLinkedList.addByOrder(hero1);
50
     singleLinkedList.addByOrder(hero3);
51
 }
52

53
 @Test
54
 public void updateTest() {
55
     // 测试修改
56
     System.out.println("Before update:");
57
     singleLinkedList.list();
58
     HeroNode hero4New = new HeroNode(4, "Yusuke Kitagawa-Test", "Fox-Test");
59
     singleLinkedList.update(hero4New);
60

61
     System.out.println("After update:");
62
     singleLinkedList.list();
63
 }
64

65
 @Test
66
 public void deleteTest() {
67
     System.out.println("Before deletion:");
68
     singleLinkedList.list();
69
     singleLinkedList.delete(1);
70
     singleLinkedList.delete(4);
71
     System.out.println("After deletion:");
72
     singleLinkedList.list();
73
 }
74

75
 @Test
76
 public void lengthTest() {
77
     System.out.println(singleLinkedList.length());
78
     singleLinkedList.delete(1);
79
     System.out.println(singleLinkedList.length());
80
 }
81

82
 @Test
83
 public void findLastIndexNodeTest() {
84
     singleLinkedList.list();
85
     System.out.println("Search Test");
86
     HeroNode lastIndexNode = singleLinkedList.findLastIndexNode(1);
87
     System.out.println("Find the 1st last " + lastIndexNode);
88
     lastIndexNode = singleLinkedList.findLastIndexNode(4);
89
     System.out.println("Find the 4th last " + lastIndexNode);
90
     lastIndexNode = singleLinkedList.findLastIndexNode(2);
91
     System.out.println("Find the 2nd last " + lastIndexNode);
92
     lastIndexNode = singleLinkedList.findLastIndexNode(5);
93
     System.out.println("Find the 5th last " + lastIndexNode);
94
 }
95

96
 @Test
97
 public void reverseTest() {
98
     System.out.println("Before reversal:");
99
     singleLinkedList.list();
100

101
     singleLinkedList.reverse();
102

103
     System.out.println("After reversal:");
104
     singleLinkedList.list();
105
 }
106

107
 @Test
108
 public void reversePrintTest() {
109
     System.out.println("The data of the linked list:");
110
     singleLinkedList.list();
111
     System.out.println("Print in reverse order:");
112
     singleLinkedList.reversePrint();
113
 }

输出结果

1
Test1:
2
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
3
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
4
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
5
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}
6

7
Test2:
8
The phantom thief number 3 to be inserted already exists and can't be added!
9
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
10
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
11
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
12
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}
13

14
updateTest:
15
Before update:
16
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
17
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
18
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
19
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}
20
After update:
21
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
22
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
23
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
24
HeroNode{no=4, name='Yusuke Kitagawa-Test', nickName='Fox-Test'}
25

26
deleteTest:
27
Before deletion:
28
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
29
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
30
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
31
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}
32
After deletion:
33
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
34
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
35

36
lengthTest:
37
4
38
3
39

40
findLastIndexNodeTest:
41
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
42
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
43
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
44
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}
45
Search Test
46
Find the 1st last HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}
47
Find the 4th last HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
48
Find the 2nd last HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
49
Find the 5th last null
50

51
reverseTest:
52
Before reversal:
53
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
54
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
55
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
56
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}
57
After reversal:
58
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}
59
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
60
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
61
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
62

63
reversePrintTest:
64
The data of the linked list:
65
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
66
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
67
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
68
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}
69
Print in reverse order:
70
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}
71
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
72
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
73
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}

双向链表

双向链表节点定义与单向链表大致相同，只不过多了一个指向前一个节点的指针域。

双向链表相关函数的实现思路基本实现思路与单向链表相同，可在前者的基础上作出修改

双向链表的代码实现

查看代码实现

函数编写

1
package DataStructure.DoubleLinkedListPackage;
2

3
class HeroNode {
4
 // 基本的元素与构造元素与单链表基本相同，主要多了一个pre域
5
 public int no;
6
 public String name;
7
 public String nickName;
8
 public HeroNode next;
9
 public HeroNode pre;
10

11
 public HeroNode(int no, String name, String nickName) {
12
     this.no = no;
13
     this.name = name;
14
     this.nickName = nickName;
15
 }
16

17
 // 重写函数也基本一致
18
 @Override
19
 public String toString() {
20
     return "HeroNode{" +
21
             "no=" + no +
22
             ", name='" + name + '\'' +
23
             ", nickName='" + nickName + '\'' +
24
             '}';
25
 }
26
}
27

28
// 对双向链表类进行编写
29
public class DoubleLinkedList {
30
 // 同样的，初始化一个最初的节点
31
 private HeroNode head = new HeroNode(0, "", "");
32

33
 // 将节点添加到链表的尾部
34
 public void add(HeroNode node) {
35
     HeroNode temp = head;
36
     while (temp.next != null) {
37
         temp = temp.next;
38
     }
39
     temp.next = node;
40
     node.pre = temp;
41
 }
42

43
 // 修改值的函数，与单向链表基本相同
44
 public void update(HeroNode newNode) {
45
     if (head.next == null) {
46
         System.out.println("The linked list is empty!");
47
         return;
48
     }
49

50
     HeroNode temp = head;
51
     boolean exist = false;
52
     while (true) {
53
         if (temp.next == null) {
54
             break;
55
         }
56
         if (temp.no == newNode.no) {
57
             exist = true;
58
             break;
59
         }
60
         temp = temp.next;
61
     }
62
     if (exist) {
63
         temp.name = newNode.name;
64
         temp.nickName = newNode.nickName;
65
     } else {
66
         System.out.printf("no element found with number: %d !", newNode.no);
67
     }
68
 }
69

70
 // 删除函数与单向链表的思路基本相同，需要注意删除的操作以及最后一位元素的删除处理
71
 public void delete(int no) {
72
     if (head.next == null) {
73
         System.out.println("The linked list is empty!");
74
         return;
75
     }
76

77
     HeroNode temp = head.next;
78
     boolean exist = false;
79
     while (true) {
80
         if (temp.next == null) {
81
             break;
82
         }
83
         if (temp.no == no) {
84
             exist = true;
85
             break;
86
         }
87
         temp = temp.next;
88
     }
89
     if (!exist) {
90
         System.out.printf("no element found with number: %d !", no);
91
         return;
92
     }
93
     if (temp.next != null) {
94
         temp.next.pre = temp.pre;
95
     }
96
     temp.pre.next = temp.next;
97
 }
98

99
 // 打印链表
100
 public void print() {
101
     if (head.next == null) {
102
         System.out.println("The linked list is empty!");
103
         return;
104
     }
105
     HeroNode cur = head.next;
106
     while (cur != null) {
107
         System.out.println(cur);
108
         cur = cur.next;
109
     }
110
 }
111

112
 // 按序添加
113
 public void addByOrder(HeroNode node) {
114
     HeroNode temp = head;
115
     boolean exist = false; // 添加的节点是否已经在链表中存在
116

117
     while (true) {
118
         // 已到列表尾部
119
         if (temp.next == null) {
120
             break;
121
         }
122
         // 已找到
123
         if (temp.next.no > node.no) {
124
             break;
125
         }
126

127
         // 已存在该编号
128
         if (temp.next.no == node.no) {
129
             exist = true;
130
             break;
131
         }
132
         temp = temp.next;
133
     }
134
     if (exist) {
135
         System.out.printf("The phantom thief number %d to be inserted already exists and can't be added! \n", node.no);
136
         return;
137
     }
138

139
     // 把节点插入到 temp 和 temp.next 之间
140
     // temp -> node -> temp.next
141
     node.next = temp.next;
142
     temp.next = node;
143
     node.pre = temp.next.pre;
144
     temp.next.pre = node;
145
 }
146
}

测试用例

1
package DataStructure.DoubleLinkedListPackage;
2

3
import org.junit.Before;
4
import org.junit.Test;
5

6
/**
7
* 双向链表测试
8
*/
9
public class DoubleLinkedListTest {
10
 DoubleLinkedList doubleLinkedList;
11

12
 @Before
13
 public void before() {
14
     HeroNode hero1 = new HeroNode(1, "Amamiya Ren", "Joker");
15
     HeroNode hero2 = new HeroNode(2, "Ryuji Sakamoto", "Skull");
16
     HeroNode hero3 = new HeroNode(3, "Anne Takamaki", "Panther");
17
     HeroNode hero4 = new HeroNode(4, "Yusuke Kitagawa", "Fox");
18

19
     // 测试新增
20
     doubleLinkedList = new DoubleLinkedList();
21
     doubleLinkedList.add(hero1);
22
     doubleLinkedList.add(hero4);
23
     doubleLinkedList.add(hero2);
24
     doubleLinkedList.add(hero3);
25
 }
26

27
 @Test
28
 public void addTest() {
29
     // before 中已测试
30
 }
31

32
 /**
33
  * 更新测试
34
  */
35
 @Test
36
 public void updateTest() {
37
     System.out.println("Before update:");
38
     doubleLinkedList.print();
39
     HeroNode hero4New = new HeroNode(4, "Yusuke Kitagawa-Test", "Fox-Test");
40
     doubleLinkedList.update(hero4New);
41
     System.out.println("After update:");
42
     doubleLinkedList.print();
43
 }
44

45
 /**
46
  * 删除测试
47
  */
48
 @Test
49
 public void deleteTest() {
50
     System.out.println("Before deletion:");
51
     doubleLinkedList.print();
52
     doubleLinkedList.delete(1);
53
     doubleLinkedList.delete(4);
54
     doubleLinkedList.delete(3);
55
     System.out.println("After deletion:");
56
     doubleLinkedList.print();
57
 }
58
 @Test
59
 public void addByOrderTest() {
60
     HeroNode hero1 = new HeroNode(1, "Amamiya Ren", "Joker");
61
     HeroNode hero2 = new HeroNode(2, "Ryuji Sakamoto", "Skull");
62
     HeroNode hero3 = new HeroNode(3, "Anne Takamaki", "Panther");
63
     HeroNode hero4 = new HeroNode(4, "Yusuke Kitagawa", "Fox");
64

65
     // 测试新增
66
     doubleLinkedList = new DoubleLinkedList();
67
     doubleLinkedList.addByOrder(hero1);
68
     doubleLinkedList.addByOrder(hero4);
69
     doubleLinkedList.addByOrder(hero2);
70
     doubleLinkedList.addByOrder(hero3);
71
     doubleLinkedList.addByOrder(hero3);
72
     doubleLinkedList.print();
73

74
 }
75
}

输出结果

1
Before update:
2
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
3
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}
4
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
5
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
6
After update:
7
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
8
HeroNode{no=4, name='Yusuke Kitagawa-Test', nickName='Fox-Test'}
9
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
10
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
11

12

13
Before deletion:
14
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
15
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}
16
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
17
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
18
no element found with number: 3 !After deletion:
19
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
20
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
21

22

23
The phantom thief number 3 to be inserted already exists and can't be added!
24
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
25
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
26
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
27
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}

循环链表

循环链表的讲解将与约瑟夫问题结合实现

实现基本思路
1. 先构成一个有n个节点的单循环链表。
2. 然后由k节点起从1开始计数。
3. 计数到m时，对应节点从链表中删除，然后从下一个节点又从1开始计数

代码实现

查看代码实现

函数编写

1
package DataStructure;
2

3
// 构造孩子节点
4
class Boy {
5
 int no;
6
 Boy next;
7

8
 public Boy(int no) {
9
     this.no = no;
10
 }
11
}
12

13
public class CircleSingleLinkedList {
14
 Boy first = null;
15

16
 /*
17
  * 添加节点
18
  * 1. 检查num的输入是否在1及以上
19
  * 2. 通过cur指针循环前移，创建环形单链表
20
  * 3. 第一个节点为空的时候需要特殊考虑
21
  * 4. 添加节点的顺序为：cur指向boy,boy指向first,cur指针指向boy
22
  */
23
 public void add(int num) {
24
     if (num < 1) {
25
         System.out.println("Please input a number greater than 1! ");
26
         return;
27
     }
28
     Boy cur = null;
29
     for (int i = 1; i <= num; i++) {
30
         Boy boy = new Boy(i);
31
         if (first == null) {
32
             first = boy;
33
             boy.next = first;
34
             cur = first;
35
             continue;
36
         }
37
         cur.next = boy;
38
         boy.next = first;
39
         cur = boy;
40
     }
41
 }
42

43
 /**
44
  * 打印队列
45
  */
46
 public void print() {
47
     if (first == null) {
48
         System.out.println("Queue empty!");
49
         return;
50
     }
51
     Boy cur = first;
52
     while (true) {
53
         System.out.printf("Child number %d \n", cur.no);
54
         cur = cur.next;
55
         // 如果和 first 一致，则标识已经走了一圈了
56
         if (cur == first) {
57
             return;
58
         }
59
     }
60
 }
61

62
 public void countBoy(int startNo, int countNum, int nums) {
63
     // 进行一个数据校验
64
     if (first == null || // 环形队列没有构建
65
             countNum < 1 || // 每次至少数 1 下
66
             startNo > nums // 开始小孩不能大于参与游戏的人数
67
     ) {
68
         System.out.println("The parameter is incorrect.Please re-enter it!");
69
     }
70
     // 1. 初始化辅助变量到 first 的后面
71
     Boy helper = first;
72
     // 当 helper.next = first 时，就说明已经定位了
73
     while (helper.next != first) {
74
         helper = helper.next;
75
     }
76

77
     // 2. 定位 first 和 helper 在 startNo 位置
78
     // first 初始在最开始，移动到 startNo 位置
79
     for (int i = 0; i < startNo - 1; i++) {
80
         helper = first;
81
         first = first.next;
82
     }
83

84
     // 为了测试方便，这里添加一个日志输出
85
     System.out.printf("Localize: %d \n", startNo);
86
     print();
87

88
     // 3. 开始报数 和 出圈
89
     while (true) {
90
         // 当队列中只剩下一个人的时候，跳出循环，因为最后一个必然是他自己出队列
91
         if (helper == first) {
92
             break;
93
         }
94
         // 报数：每次报数 m-1
95
         for (int i = 0; i < countNum - 1; i++) {
96
             // 因为 helper 永远在 first 后面，只要在 first 移动时，指向 first 原来所在的位置即可
97
             helper = first;
98
             first = first.next;
99
         }
100
         // 出圈
101
         System.out.printf("The number of the child out of the circle %d \n", first.no);
102
         first = first.next; // first 重置为下一次报数的小孩节点上
103
         helper.next = first; // helper 重置为下一次报数的小孩节点上
104
     }
105
     System.out.printf("The number of the last child left %d \n", first.no);
106
 }
107
}

测试用例

1
package DataStructure;
2

3
import org.junit.Test;
4

5
public class JosepfuTest {
6
 @Test
7
 public void addTest() {
8
     CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
9
     circleSingleLinkedList.add(5);
10
     circleSingleLinkedList.print();
11
 }
12

13
 @Test
14
 public void countBoy() {
15
     CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
16
     circleSingleLinkedList.add(5);
17
     System.out.println("Build Circle Queue:");
18
     circleSingleLinkedList.print();
19

20
     // 开始玩游戏
21
     // 正确的输出顺序为：2、4、1、5、3
22
     circleSingleLinkedList.countBoy(1, 2, 5);
23
 }
24
}

输出结果

1
Child number 1
2
Child number 2
3
Child number 3
4
Child number 4
5
Child number 5
6

7
Build Circle Queue:
8
Child number 1
9
Child number 2
10
Child number 3
11
Child number 4
12
Child number 5
13
Localize: 1
14
Child number 1
15
Child number 2
16
Child number 3
17
Child number 4
18
Child number 5

评论加载中…

线性表的定义

线性表的逻辑结构

抽象数据类型线性表的定义

线性表的顺序表示（顺序存储结构）

顺序分配

寻址公式

顺序储存结构的评价

稀疏数组的实现

线性表的链式存储结构

基本概念

单链表

双向链表

循环链表

相关推荐

评论