激情久久久_欧美视频区_成人av免费_不卡视频一二三区_欧美精品在欧美一区二区少妇_欧美一区二区三区的

服務器之家：專注于服務器技術及軟件下載分享
分類導航

PHP教程|ASP.NET教程|JAVA教程|ASP教程|

服務器之家 - 編程語言 - JAVA教程 - 簡單介紹線性表以及如何實現雙鏈表

簡單介紹線性表以及如何實現雙鏈表

2019-12-29 14:32sky544900373 JAVA教程

本文先介紹線性表的幾個基本組成部分：數組、單向鏈表、雙向鏈表；隨后給出雙向鏈表的C、C++和Java三種語言的實現,需要的朋友可以參考下

線性表是一種線性結構，它是具有相同類型的n(n≥0)個數據元素組成的有限序列。

一、數組
數組有上界和下界，數組的元素在上下界內是連續的。

存儲10,20,30,40,50的數組的示意圖如下：

簡單介紹線性表以及如何實現雙鏈表

數組的特點：數據是連續的；隨機訪問速度快。
數組中稍微復雜一點的是多維數組和動態數組。對于C語言而言，多維數組本質上也是通過一維數組實現的。至于動態數組，是指數組的容量能動態增長的數組；對于C語言而言，若要提供動態數組，需要手動實現；而對于C++而言，STL提供了Vector；對于Java而言，Collection集合中提供了ArrayList和Vector。

二、單向鏈表
單向鏈表(單鏈表)是鏈表的一種，它由節點組成，每個節點都包含下一個節點的指針。

單鏈表的示意圖如下：

簡單介紹線性表以及如何實現雙鏈表

表頭為空，表頭的后繼節點是"節點10"(數據為10的節點)，"節點10"的后繼節點是"節點20"(數據為10的節點)，...

 

單鏈表刪除節點

簡單介紹線性表以及如何實現雙鏈表

刪除"節點30"

刪除之前："節點20" 的后繼節點為"節點30"，而"節點30" 的后繼節點為"節點40"。
刪除之后："節點20" 的后繼節點為"節點40"。

單鏈表添加節點

簡單介紹線性表以及如何實現雙鏈表

在"節點10"與"節點20"之間添加"節點15"
添加之前："節點10" 的后繼節點為"節點20"。
添加之后："節點10" 的后繼節點為"節點15"，而"節點15" 的后繼節點為"節點20"。

單鏈表的特點是：節點的鏈接方向是單向的；相對于數組來說，單鏈表的的隨機訪問速度較慢，但是單鏈表刪除/添加數據的效率很高。

三、雙向鏈表
雙向鏈表(雙鏈表)是鏈表的一種。和單鏈表一樣，雙鏈表也是由節點組成，它的每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。一般我們都構造雙向循環鏈表。

雙鏈表的示意圖如下：
簡單介紹線性表以及如何實現雙鏈表

表頭為空，表頭的后繼節點為"節點10"(數據為10的節點)；"節點10"的后繼節點是"節點20"(數據為10的節點)，"節點20"的前繼節點是"節點10"；"節點20"的后繼節點是"節點30"，"節點30"的前繼節點是"節點20"；...；末尾節點的后繼節點是表頭。

雙鏈表刪除節點

簡單介紹線性表以及如何實現雙鏈表

刪除"節點30"
刪除之前："節點20"的后繼節點為"節點30"，"節點30" 的前繼節點為"節點20"。"節點30"的后繼節點為"節點40"，"節點40" 的前繼節點為"節點30"。
刪除之后："節點20"的后繼節點為"節點40"，"節點40" 的前繼節點為"節點20"。

雙鏈表添加節點

簡單介紹線性表以及如何實現雙鏈表

在"節點10"與"節點20"之間添加"節點15"
添加之前："節點10"的后繼節點為"節點20"，"節點20" 的前繼節點為"節點10"。
添加之后："節點10"的后繼節點為"節點15"，"節點15" 的前繼節點為"節點10"。"節點15"的后繼節點為"節點20"，"節點20" 的前繼節點為"節點15"。

 

下面介紹雙鏈表的實現，分別介紹C/C++/Java三種實現。

1. C實現雙鏈表

實現代碼
雙向鏈表頭文件(double_link.h)

 

?
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
#ifndef _DOUBLE_LINK_H
#define _DOUBLE_LINK_H
// 新建“雙向鏈表”。成功，返回表頭；否則，返回NULL
extern int create_dlink();
// 撤銷“雙向鏈表”。成功，返回0；否則，返回-1
extern int destroy_dlink();
// “雙向鏈表是否為空”。為空的話返回1；否則，返回0。
extern int dlink_is_empty();
// 返回“雙向鏈表的大小”
extern int dlink_size();
// 獲取“雙向鏈表中第index位置的元素”。成功，返回節點指針；否則，返回NULL。
extern void* dlink_get(int index);
// 獲取“雙向鏈表中第1個元素”。成功，返回節點指針；否則，返回NULL。
extern void* dlink_get_first();
// 獲取“雙向鏈表中最后1個元素”。成功，返回節點指針；否則，返回NULL。
extern void* dlink_get_last();
// 將“value”插入到index位置。成功，返回0；否則，返回-1。
extern int dlink_insert(int index, void *pval);
// 將“value”插入到表頭位置。成功，返回0；否則，返回-1。
extern int dlink_insert_first(void *pval);
// 將“value”插入到末尾位置。成功，返回0；否則，返回-1。
extern int dlink_append_last(void *pval);
// 刪除“雙向鏈表中index位置的節點”。成功，返回0；否則，返回-1
extern int dlink_delete(int index);
// 刪除第一個節點。成功，返回0；否則，返回-1
extern int dlink_delete_first();
// 刪除組后一個節點。成功，返回0；否則，返回-1
extern int dlink_delete_last();
#endif

雙向鏈表實現文件(double_link.c)

 

?
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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
#include <stdio.h>
#include <malloc.h>
/**
* C 語言實現的雙向鏈表，能存儲任意數據。
*
* @author skywang
* @date 2013/11/07
*/
// 雙向鏈表節點
typedef struct tag_node
{
struct tag_node *prev;
struct tag_node *next;
void* p;
}node;
// 表頭。注意，表頭不存放元素值！！！
static node *phead=NULL;
// 節點個數。
static int count=0;
// 新建“節點”。成功，返回節點指針；否則，返回NULL。
static node* create_node(void *pval)
{
node *pnode=NULL;
pnode = (node *)malloc(sizeof(node));
if (!pnode)
{
printf("create node error!\n");
return NULL;
}
// 默認的，pnode的前一節點和后一節點都指向它自身
pnode->prev = pnode->next = pnode;
// 節點的值為pval
pnode->p = pval;
return pnode;
}
// 新建“雙向鏈表”。成功，返回0；否則，返回-1。
int create_dlink()
{
// 創建表頭
phead = create_node(NULL);
if (!phead)
return -1;
// 設置“節點個數”為0
count = 0;
return 0;
}
// “雙向鏈表是否為空”
int dlink_is_empty()
{
return count == 0;
}
// 返回“雙向鏈表的大小”
int dlink_size() {
return count;
}
// 獲取“雙向鏈表中第index位置的節點”
static node* get_node(int index)
{
if (index<0 || index>=count)
{
printf("%s failed! index out of bound!\n", __func__);
return NULL;
}
// 正向查找
if (index <= (count/2))
{
int i=0;
node *pnode=phead->next;
while ((i++) < index)
pnode = pnode->next;
return pnode;
}
// 反向查找
int j=0;
int rindex = count - index - 1;
node *rnode=phead->prev;
while ((j++) < rindex)
rnode = rnode->prev;
return rnode;
}
// 獲取“第一個節點”
static node* get_first_node()
{
return get_node(0);
}
// 獲取“最后一個節點”
static node* get_last_node()
{
return get_node(count-1);
}
// 獲取“雙向鏈表中第index位置的元素”。成功，返回節點值；否則，返回-1。
void* dlink_get(int index)
{
node *pindex=get_node(index);
if (!pindex)
{
printf("%s failed!\n", __func__);
return NULL;
}
return pindex->p;
}
// 獲取“雙向鏈表中第1個元素的值”
void* dlink_get_first()
{
return dlink_get(0);
}
// 獲取“雙向鏈表中最后1個元素的值”
void* dlink_get_last()
{
return dlink_get(count-1);
}
// 將“pval”插入到index位置。成功，返回0；否則，返回-1。
int dlink_insert(int index, void* pval)
{
// 插入表頭
if (index==0)
return dlink_insert_first(pval);
// 獲取要插入的位置對應的節點
node *pindex=get_node(index);
if (!pindex)
return -1;
// 創建“節點”
node *pnode=create_node(pval);
if (!pnode)
return -1;
pnode->prev = pindex->prev;
pnode->next = pindex;
pindex->prev->next = pnode;
pindex->prev = pnode;
// 節點個數+1
count++;
return 0;
}
// 將“pval”插入到表頭位置
int dlink_insert_first(void *pval)
{
node *pnode=create_node(pval);
if (!pnode)
return -1;
pnode->prev = phead;
pnode->next = phead->next;
phead->next->prev = pnode;
phead->next = pnode;
count++;
return 0;
}
// 將“pval”插入到末尾位置
int dlink_append_last(void *pval)
{
node *pnode=create_node(pval);
if (!pnode)
return -1;
 
pnode->next = phead;
pnode->prev = phead->prev;
phead->prev->next = pnode;
phead->prev = pnode;
count++;
return 0;
}
// 刪除“雙向鏈表中index位置的節點”。成功，返回0；否則，返回-1。
int dlink_delete(int index)
{
node *pindex=get_node(index);
if (!pindex)
{
printf("%s failed! the index in out of bound!\n", __func__);
return -1;
}
pindex->next->prev = pindex->prev;
pindex->prev->next = pindex->next;
free(pindex);
count--;
return 0;
}
// 刪除第一個節點
int dlink_delete_first()
{
return dlink_delete(0);
}
// 刪除組后一個節點
int dlink_delete_last()
{
return dlink_delete(count-1);
}
// 撤銷“雙向鏈表”。成功，返回0；否則，返回-1。
int destroy_dlink()
{
if (!phead)
{
printf("%s failed! dlink is null!\n", __func__);
return -1;
}
node *pnode=phead->next;
node *ptmp=NULL;
while(pnode != phead)
{
ptmp = pnode;
pnode = pnode->next;
free(ptmp);
}
free(phead);
phead = NULL;
count = 0;
return 0;
}

雙向鏈表測試程序(dlink_test.c)

 

?
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
#include <stdio.h>
#include "double_link.h"
/**
* C 語言實現的雙向鏈表的測試程序。
*
* (01) int_test()
* 演示向雙向鏈表操作“int數據”。
* (02) string_test()
* 演示向雙向鏈表操作“字符串數據”。
* (03) object_test()
* 演示向雙向鏈表操作“對象”。
*
* @author skywang
* @date 2013/11/07
*/
// 雙向鏈表操作int數據
void int_test()
{
int iarr[4] = {10, 20, 30, 40};
printf("\n----%s----\n", __func__);
create_dlink(); // 創建雙向鏈表
dlink_insert(0, &iarr[0]); // 向雙向鏈表的表頭插入數據
dlink_insert(0, &iarr[1]); // 向雙向鏈表的表頭插入數據
dlink_insert(0, &iarr[2]); // 向雙向鏈表的表頭插入數據
printf("dlink_is_empty()=%d\n", dlink_is_empty()); // 雙向鏈表是否為空
printf("dlink_size()=%d\n", dlink_size()); // 雙向鏈表的大小
// 打印雙向鏈表中的全部數據
int i;
int *p;
int sz = dlink_size();
for (i=0; i<sz; i++)
{
p = (int *)dlink_get(i);
printf("dlink_get(%d)=%d\n", i, *p);
}
destroy_dlink();
}
void string_test()
{
char* sarr[4] = {"ten", "twenty", "thirty", "forty"};
printf("\n----%s----\n", __func__);
create_dlink(); // 創建雙向鏈表
dlink_insert(0, sarr[0]); // 向雙向鏈表的表頭插入數據
dlink_insert(0, sarr[1]); // 向雙向鏈表的表頭插入數據
dlink_insert(0, sarr[2]); // 向雙向鏈表的表頭插入數據
printf("dlink_is_empty()=%d\n", dlink_is_empty()); // 雙向鏈表是否為空
printf("dlink_size()=%d\n", dlink_size()); // 雙向鏈表的大小
// 打印雙向鏈表中的全部數據
int i;
char *p;
int sz = dlink_size();
for (i=0; i<sz; i++)
{
p = (char *)dlink_get(i);
printf("dlink_get(%d)=%s\n", i, p);
}
destroy_dlink();
}
typedef struct tag_stu
{
int id;
char name[20];
}stu;
static stu arr_stu[] =
{
{10, "sky"},
{20, "jody"},
{30, "vic"},
{40, "dan"},
};
#define ARR_STU_SIZE ( (sizeof(arr_stu)) / (sizeof(arr_stu[0])) )
void object_test()
{
printf("\n----%s----\n", __func__);
create_dlink(); // 創建雙向鏈表
dlink_insert(0, &arr_stu[0]); // 向雙向鏈表的表頭插入數據
dlink_insert(0, &arr_stu[1]); // 向雙向鏈表的表頭插入數據
dlink_insert(0, &arr_stu[2]); // 向雙向鏈表的表頭插入數據
printf("dlink_is_empty()=%d\n", dlink_is_empty()); // 雙向鏈表是否為空
printf("dlink_size()=%d\n", dlink_size()); // 雙向鏈表的大小
// 打印雙向鏈表中的全部數據
int i;
int sz = dlink_size();
stu *p;
for (i=0; i<sz; i++)
{
p = (stu *)dlink_get(i);
printf("dlink_get(%d)=[%d, %s]\n", i, p->id, p->name);
}
destroy_dlink();
}
int main()
{
int_test(); // 演示向雙向鏈表操作“int數據”。
string_test(); // 演示向雙向鏈表操作“字符串數據”。
object_test(); // 演示向雙向鏈表操作“對象”。
return 0;
}

運行結果

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
----int_test----
dlink_is_empty()=0
dlink_size()=3
dlink_get(0)=30
dlink_get(1)=20
dlink_get(2)=10
----string_test----
dlink_is_empty()=0
dlink_size()=3
dlink_get(0)=thirty
dlink_get(1)=twenty
dlink_get(2)=ten
----object_test----
dlink_is_empty()=0
dlink_size()=3
dlink_get(0)=[30, vic]
dlink_get(1)=[20, jody]
dlink_get(2)=[10, sky]

 

2. C++實現雙鏈表

實現代碼
雙向鏈表文件(DoubleLink.h)

 

?
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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
#ifndef DOUBLE_LINK_HXX
#define DOUBLE_LINK_HXX
#include <iostream>
using namespace std;
template<class T>
struct DNode
{
public:
T value;
DNode *prev;
DNode *next;
public:
DNode() { }
DNode(T t, DNode *prev, DNode *next) {
this->value = t;
this->prev = prev;
this->next = next;
}
};
template<class T>
class DoubleLink
{
public:
DoubleLink();
~DoubleLink();
int size();
int is_empty();
T get(int index);
T get_first();
T get_last();
int insert(int index, T t);
int insert_first(T t);
int append_last(T t);
int del(int index);
int delete_first();
int delete_last();
private:
int count;
DNode<T> *phead;
private:
DNode<T> *get_node(int index);
};
template<class T>
DoubleLink<T>::DoubleLink() : count(0)
{
// 創建“表頭”。注意：表頭沒有存儲數據！
phead = new DNode<T>();
phead->prev = phead->next = phead;
// 設置鏈表計數為0
//count = 0;
}
// 析構函數
template<class T>
DoubleLink<T>::~DoubleLink()
{
// 刪除所有的節點
DNode<T>* ptmp;
DNode<T>* pnode = phead->next;
while (pnode != phead)
{
ptmp = pnode;
pnode=pnode->next;
delete ptmp;
}
// 刪除"表頭"
delete phead;
phead = NULL;
}
// 返回節點數目
template<class T>
int DoubleLink<T>::size()
{
return count;
}
// 返回鏈表是否為空
template<class T>
int DoubleLink<T>::is_empty()
{
return count==0;
}
// 獲取第index位置的節點
template<class T>
DNode<T>* DoubleLink<T>::get_node(int index)
{
// 判斷參數有效性
if (index<0 || index>=count)
{
cout << "get node failed! the index in out of bound!" << endl;
return NULL;
}
// 正向查找
if (index <= count/2)
{
int i=0;
DNode<T>* pindex = phead->next;
while (i++ < index) {
pindex = pindex->next;
}
return pindex;
}
// 反向查找
int j=0;
int rindex = count - index -1;
DNode<T>* prindex = phead->prev;
while (j++ < rindex) {
prindex = prindex->prev;
}
return prindex;
}
// 獲取第index位置的節點的值
template<class T>
T DoubleLink<T>::get(int index)
{
return get_node(index)->value;
}
// 獲取第1個節點的值
template<class T>
T DoubleLink<T>::get_first()
{
return get_node(0)->value;
}
// 獲取最后一個節點的值
template<class T>
T DoubleLink<T>::get_last()
{
return get_node(count-1)->value;
}
// 將節點插入到第index位置之前
template<class T>
int DoubleLink<T>::insert(int index, T t)
{
if (index == 0)
return insert_first(t);
DNode<T>* pindex = get_node(index);
DNode<T>* pnode = new DNode<T>(t, pindex->prev, pindex);
pindex->prev->next = pnode;
pindex->prev = pnode;
count++;
return 0;
}
// 將節點插入第一個節點處。
template<class T>
int DoubleLink<T>::insert_first(T t)
{
DNode<T>* pnode = new DNode<T>(t, phead, phead->next);
phead->next->prev = pnode;
phead->next = pnode;
count++;
return 0;
}
// 將節點追加到鏈表的末尾
template<class T>
int DoubleLink<T>::append_last(T t)
{
DNode<T>* pnode = new DNode<T>(t, phead->prev, phead);
phead->prev->next = pnode;
phead->prev = pnode;
count++;
return 0;
}
// 刪除index位置的節點
template<class T>
int DoubleLink<T>::del(int index)
{
DNode<T>* pindex = get_node(index);
pindex->next->prev = pindex->prev;
pindex->prev->next = pindex->next;
delete pindex;
count--;
return 0;
}
// 刪除第一個節點
template<class T>
int DoubleLink<T>::delete_first()
{
return del(0);
}
// 刪除最后一個節點
template<class T>
int DoubleLink<T>::delete_last()
{
return del(count-1);
}
#endif

雙向鏈表測試文件(DlinkTest.cpp)

 

 

?
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
#include <iostream>
#include "DoubleLink.h"
using namespace std;
// 雙向鏈表操作int數據
void int_test()
{
int iarr[4] = {10, 20, 30, 40};
cout << "\n----int_test----" << endl;
// 創建雙向鏈表
DoubleLink<int>* pdlink = new DoubleLink<int>();
pdlink->insert(0, 20); // 將 20 插入到第一個位置
pdlink->append_last(10); // 將 10 追加到鏈表末尾
pdlink->insert_first(30); // 將 30 插入到第一個位置
// 雙向鏈表是否為空
cout << "is_empty()=" << pdlink->is_empty() <<endl;
// 雙向鏈表的大小
cout << "size()=" << pdlink->size() <<endl;
// 打印雙向鏈表中的全部數據
int sz = pdlink->size();
for (int i=0; i<sz; i++)
cout << "pdlink("<<i<<")=" << pdlink->get(i) <<endl;
}
void string_test()
{
string sarr[4] = {"ten", "twenty", "thirty", "forty"};
cout << "\n----string_test----" << endl;
// 創建雙向鏈表
DoubleLink<string>* pdlink = new DoubleLink<string>();
pdlink->insert(0, sarr[1]); // 將 sarr中第2個元素 插入到第一個位置
pdlink->append_last(sarr[0]); // 將 sarr中第1個元素 追加到鏈表末尾
pdlink->insert_first(sarr[2]); // 將 sarr中第3個元素 插入到第一個位置
// 雙向鏈表是否為空
cout << "is_empty()=" << pdlink->is_empty() <<endl;
// 雙向鏈表的大小
cout << "size()=" << pdlink->size() <<endl;
// 打印雙向鏈表中的全部數據
int sz = pdlink->size();
for (int i=0; i<sz; i++)
cout << "pdlink("<<i<<")=" << pdlink->get(i) <<endl;
}
struct stu
{
int id;
char name[20];
};
static stu arr_stu[] =
{
{10, "sky"},
{20, "jody"},
{30, "vic"},
{40, "dan"},
};
#define ARR_STU_SIZE ( (sizeof(arr_stu)) / (sizeof(arr_stu[0])) )
void object_test()
{
cout << "\n----object_test----" << endl;
// 創建雙向鏈表
DoubleLink<stu>* pdlink = new DoubleLink<stu>();
pdlink->insert(0, arr_stu[1]); // 將 arr_stu中第2個元素 插入到第一個位置
pdlink->append_last(arr_stu[0]); // 將 arr_stu中第1個元素 追加到鏈表末尾
pdlink->insert_first(arr_stu[2]); // 將 arr_stu中第3個元素 插入到第一個位置
// 雙向鏈表是否為空
cout << "is_empty()=" << pdlink->is_empty() <<endl;
// 雙向鏈表的大小
cout << "size()=" << pdlink->size() <<endl;
// 打印雙向鏈表中的全部數據
int sz = pdlink->size();
struct stu p;
for (int i=0; i<sz; i++)
{
p = pdlink->get(i);
cout << "pdlink("<<i<<")=[" << p.id << ", " << p.name <<"]" <<endl;
}
}
int main()
{
int_test(); // 演示向雙向鏈表操作“int數據”。
string_test(); // 演示向雙向鏈表操作“字符串數據”。
object_test(); // 演示向雙向鏈表操作“對象”。
return 0;
}

示例說明

在上面的示例中，我將雙向鏈表的"聲明"和"實現"都放在頭文件中。而編程規范告誡我們：將類的聲明和實現分離，在頭文件(.h文件或.hpp)中盡量只包含聲明，而在實現文件(.cpp文件)中負責實現！
那么為什么要這么做呢？這是因為，在雙向鏈表的實現中，采用了模板；而C++編譯器不支持對模板的分離式編譯！簡單點說，如果在DoubleLink.h中聲明，而在DoubleLink.cpp中進行實現的話；當我們在其他類中創建DoubleLink的對象時，會編譯出錯。具體原因，可以參考"為什么C++編譯器不能支持對模板的分離式編譯"。

運行結果

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
----int_test----
is_empty()=0
size()=3
pdlink(0)=30
pdlink(1)=20
pdlink(2)=10
----string_test----
is_empty()=0
size()=3
pdlink(0)=thirty
pdlink(1)=twenty
pdlink(2)=ten
----object_test----
is_empty()=0
size()=3
pdlink(0)=[30, vic]
pdlink(1)=[20, jody]
pdlink(2)=[10, sky]

 

3. Java實現雙鏈表

實現代碼
雙鏈表類(DoubleLink.java)

 

?
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
/**
* Java 實現的雙向鏈表。
* 注：java自帶的集合包中有實現雙向鏈表，路徑是:java.util.LinkedList
*
* @author skywang
* @date 2013/11/07
*/
public class DoubleLink<T> {
// 表頭
private DNode<T> mHead;
// 節點個數
private int mCount;
// 雙向鏈表“節點”對應的結構體
private class DNode<T> {
public DNode prev;
public DNode next;
public T value;
public DNode(T value, DNode prev, DNode next) {
this.value = value;
this.prev = prev;
this.next = next;
}
}
// 構造函數
public DoubleLink() {
// 創建“表頭”。注意：表頭沒有存儲數據！
mHead = new DNode<T>(null, null, null);
mHead.prev = mHead.next = mHead;
// 初始化“節點個數”為0
mCount = 0;
}
// 返回節點數目
public int size() {
return mCount;
}
// 返回鏈表是否為空
public boolean isEmpty() {
return mCount==0;
}
// 獲取第index位置的節點
private DNode<T> getNode(int index) {
if (index<0 || index>=mCount)
throw new IndexOutOfBoundsException();
// 正向查找
if (index <= mCount/2) {
DNode<T> node = mHead.next;
for (int i=0; i<index; i++)
node = node.next;
return node;
}
// 反向查找
DNode<T> rnode = mHead.prev;
int rindex = mCount - index -1;
for (int j=0; j<rindex; j++)
rnode = rnode.prev;
return rnode;
}
// 獲取第index位置的節點的值
public T get(int index) {
return getNode(index).value;
}
// 獲取第1個節點的值
public T getFirst() {
return getNode(0).value;
}
// 獲取最后一個節點的值
public T getLast() {
return getNode(mCount-1).value;
}
// 將節點插入到第index位置之前
public void insert(int index, T t) {
if (index==0) {
DNode<T> node = new DNode<T>(t, mHead, mHead.next);
mHead.next.prev = node;
mHead.next = node;
mCount++;
return ;
}
DNode<T> inode = getNode(index);
DNode<T> tnode = new DNode<T>(t, inode.prev, inode);
inode.prev.next = tnode;
inode.next = tnode;
mCount++;
return ;
}
// 將節點插入第一個節點處。
public void insertFirst(T t) {
insert(0, t);
}
// 將節點追加到鏈表的末尾
public void appendLast(T t) {
DNode<T> node = new DNode<T>(t, mHead.prev, mHead);
mHead.prev.next = node;
mHead.prev = node;
mCount++;
}
// 刪除index位置的節點
public void del(int index) {
DNode<T> inode = getNode(index);
inode.prev.next = inode.next;
inode.next.prev = inode.prev;
inode = null;
mCount--;
}
// 刪除第一個節點
public void deleteFirst() {
del(0);
}
// 刪除最后一個節點
public void deleteLast() {
del(mCount-1);
}
}

測試程序(DlinkTest.java)

 

?
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
/**
* Java 實現的雙向鏈表。
* 注：java自帶的集合包中有實現雙向鏈表，路徑是:java.util.LinkedList
*
* @author skywang
* @date 2013/11/07
*/
public class DlinkTest {
// 雙向鏈表操作int數據
private static void int_test() {
int[] iarr = {10, 20, 30, 40};
System.out.println("\n----int_test----");
// 創建雙向鏈表
DoubleLink<Integer> dlink = new DoubleLink<Integer>();
dlink.insert(0, 20); // 將 20 插入到第一個位置
dlink.appendLast(10); // 將 10 追加到鏈表末尾
dlink.insertFirst(30); // 將 30 插入到第一個位置
// 雙向鏈表是否為空
System.out.printf("isEmpty()=%b\n", dlink.isEmpty());
// 雙向鏈表的大小
System.out.printf("size()=%d\n", dlink.size());
// 打印出全部的節點
for (int i=0; i<dlink.size(); i++)
System.out.println("dlink("+i+")="+ dlink.get(i));
}
private static void string_test() {
String[] sarr = {"ten", "twenty", "thirty", "forty"};
System.out.println("\n----string_test----");
// 創建雙向鏈表
DoubleLink<String> dlink = new DoubleLink<String>();
dlink.insert(0, sarr[1]); // 將 sarr中第2個元素 插入到第一個位置
dlink.appendLast(sarr[0]); // 將 sarr中第1個元素 追加到鏈表末尾
dlink.insertFirst(sarr[2]); // 將 sarr中第3個元素 插入到第一個位置
// 雙向鏈表是否為空
System.out.printf("isEmpty()=%b\n", dlink.isEmpty());
// 雙向鏈表的大小
System.out.printf("size()=%d\n", dlink.size());
// 打印出全部的節點
for (int i=0; i<dlink.size(); i++)
System.out.println("dlink("+i+")="+ dlink.get(i));
}
// 內部類
private static class Student {
private int id;
private String name;
public Student(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "["+id+", "+name+"]";
}
}
private static Student[] students = new Student[]{
new Student(10, "sky"),
new Student(20, "jody"),
new Student(30, "vic"),
new Student(40, "dan"),
};
private static void object_test() {
System.out.println("\n----object_test----");
// 創建雙向鏈表
DoubleLink<Student> dlink = new DoubleLink<Student>();
dlink.insert(0, students[1]); // 將 students中第2個元素 插入到第一個位置
dlink.appendLast(students[0]); // 將 students中第1個元素 追加到鏈表末尾
dlink.insertFirst(students[2]); // 將 students中第3個元素 插入到第一個位置
// 雙向鏈表是否為空
System.out.printf("isEmpty()=%b\n", dlink.isEmpty());
// 雙向鏈表的大小
System.out.printf("size()=%d\n", dlink.size());
// 打印出全部的節點
for (int i=0; i<dlink.size(); i++) {
System.out.println("dlink("+i+")="+ dlink.get(i));
}
}
 
public static void main(String[] args) {
int_test(); // 演示向雙向鏈表操作“int數據”。
string_test(); // 演示向雙向鏈表操作“字符串數據”。
object_test(); // 演示向雙向鏈表操作“對象”。
}
}

運行結果

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
----int_test----
isEmpty()=false
size()=3
dlink(0)=30
dlink(1)=20
dlink(2)=10
----string_test----
isEmpty()=false
size()=3
dlink(0)=thirty
dlink(1)=twenty
dlink(2)=ten
----object_test----
isEmpty()=false
size()=3
dlink(0)=[30, vic]
dlink(1)=[20, jody]
dlink(2)=[10, sky]

以上就是本文的全部內容，希望大家能夠理解，對大家有所幫助。

延伸 · 閱讀

精彩推薦
主站蜘蛛池模板： 久久国产精品久久久久久 | 亚洲最新色 | 欧美成人精品一区 | 久久sp | 视频一区二区三区免费观看 | 操操插插 | 日本羞羞的午夜电视剧 | 一级成人毛片 | 欧美激情区 | 爱操av| 最污网站 | 久久久久久久久久网 | 国产亚洲精品久久久闺蜜 | 性欧美在线视频 | 狠狠干b| www.精品视频 | 一边吃奶一边插下面 | 国产午夜精品一区二区三区四区 | 91午夜视频 | 毛片视频网站在线观看 | 色av成人天堂桃色av | 92看片淫黄大片一级 | 青草久久av | 午夜小视频免费观看 | 宅男噜噜噜66一区二区 | www.热 | 激情在线免费观看 | 国产精品一区二区x88av | 久久久久国产成人精品亚洲午夜 | 精品一二三区视频 | 久久久久久久久久综合 | 欧美日韩激情 | 九一免费在线观看 | 黄色片免费看网站 | 久久久久日本精品一区二区三区 | a级黄色片视频 | 免费国产一级淫片 | 毛片成人网 | 久久国产精品久久精品国产演员表 | 色淫影院 | 国产精品免费观在线 |