线性表的双链表存储

数据结构 评论

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
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
#include <stdio.h>
#include <stdlib.h>

typedef int tElem;
typedef struct Node {
    tElem data;             // 数据域
    int index;              // 索引
    struct Node * prev;     // 前缀节点指针
    struct Node * next;     // 后缀节点指针
} Node,*pNode;


/*
 * 初始化
 * 步骤：
 *  为链表头结点申请空间
 *  头结点的前缀、后缀节点指针均指向 NULL
 *  头结点的索引值为 0
 *  返回链表
*/
pNode InitList(pNode list)
{
    list = (pNode) malloc(sizeof(Node));
    list->prev = NULL;
    list->next = NULL;
    list->index = 0;
    return list;
}


/*
 * 获取链表长度
 * 步骤：
 *  定义临时变量 item ，存放链表
 *  遍历链表，当 item.next == NULL 时，此时的 item 指的是链表的最后一个节点。
 *  最后一个节点的索引值就是链表的长度，返回长度。
*/
int ListEmpty(pNode list)
{
    pNode item = list;
    while (item->next != NULL)
    {
        item = item->next;
    }
    return item->index;
}


/*
 * 打印链表
 * 步骤：
 *  遍历链表，逐一输出。
*/
void ListTraverse(pNode list)
{
    pNode item = list->next;
    int count = 0;
    while (item != NULL)
    {
        count++;
        printf("链表的第 %d 个元素是 %d。\n",count,item->data);
        item = item->next;
    }
}


/*
 * 插入元素
 * 步骤：
 *  获取链表长度
 *  为新元素开一个空间存入变量 temp
 *  temp 的数据域为元素 e
 *  temp 的索引为当前长度 + 1
 *  item 的后缀节点指针指向 NULL
 *  遍历链表找到最后一个元素
 *  令最后一个元素的后缀节点指针指向 temp
 *  令 item 的前缀指针节点指向最后一个元素
 *  返回链表
*/
pNode ListInsert(pNode list,tElem e)
{
    int len = ListEmpty(list);
    pNode temp = (pNode) malloc(sizeof(Node));
    temp->data = e;
    temp->index = ++len;
    temp->next = NULL;

    pNode item = list;
    while (item->next != NULL)
    {
        item = item->next;
    }
    item->next = temp;
    temp->prev = item;

    return list;
}


/*
 * 判断元素 e 是否在链表中
*/
int ListIsIn(pNode list,tElem e)
{
    pNode item = list->next;
    while (item != NULL)
    {
        if(item->data == e)
        {
            return item->index;
        }
        item = item->next;
    }
    return 0;
}


/*
 * 获取元素 e 的前后节点元素
*/
void getElem(pNode list,tElem e)
{
    int index = ListIsIn(list,e);
    int len = ListEmpty(list);
    if(index == 1 && len == 1)
    {
        printf("元素 %d 是链表的唯一元素，无前后节点。\n",e);
        return;
    }

    if(index)
    {
        pNode item = list->next;
        while (item != NULL)
        {
            if(item->data == e)
            {
                pNode prev = item->prev;
                pNode next = item->next;

                if(index == 1 && len > 1)
                {
                    printf("元素 %d 是链表的第一个元素，无前节点，后节点元素为 %d。\n",e,next->data);
                    return;
                }
                if(index == len)
                {
                    printf("元素 %d 是链表的最后一个元素，无后节点，前节点元素为 %d。\n",e,prev->data);
                    return;
                }
                printf("元素 %d 的前节点元素是：%d，后节点元素是：%d。\n",e,prev->data,next->data);
            }
            item = item->next;
        }
    }
    else
    {
        printf("元素 %d 不在链表中！\n",e);
    }

}


/*
 * 删除元素 e
*/
pNode ListDelete(pNode list,tElem e)
{
    int index = ListIsIn(list,e);
    int len = ListEmpty(list);
    if(index)
    {
        pNode item = list->next;
        while (item != NULL)
        {
            if(item->data == e)
            {
                if(index == len)
                {
                    item->prev->next = NULL;
                }
                else
                {
                    item->prev->next = item->next;
                    item->next->prev = item->prev;
                }
            }
            item = item->next;
        }
    }
    else
    {
        printf("元素 %d 不在链表中！\n",e);
    }
}


/*
 * 清空链表
*/
pNode ClearList(pNode list)
{
    list->prev = NULL;
    list->next = NULL;
    return list;
}


/*
 * 销毁链表
*/
pNode DestroyList(pNode list)
{
    free(list);
    return list;
}

int main() {
    pNode list = NULL;

    // 初始化
    list = InitList(list);
    printf("初始化后，链表的长度为：%d\n\n",ListEmpty(list));

    // 插入
    list = ListInsert(list,10);
    list = ListInsert(list,20);
    list = ListInsert(list,30);
    list = ListInsert(list,40);

    // 打印链表
    ListTraverse(list);
    printf("\n");

    // 获取元素 e 的前后节点元素
    getElem(list,10);
    getElem(list,20);
    getElem(list,40);
    getElem(list,50);
    printf("\n");

    // 删除元素 e
    ListDelete(list,40);
    ListTraverse(list);
    printf("\n");

    list = ClearList(list);
    printf("清空链表后，链表的长度为：%d\n",ListEmpty(list));

    list = DestroyList(list);

    return 0;
}

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
package Linear;

public class Demo03 {
    public static void main(String[] args) {
        DoubleChain head = new DoubleChain();
        head.HeadInsert(20);
        head.HeadInsert(10);
        System.out.println("头插元素后：");
        head.printList();
        head.TailInsert(30);
        head.TailInsert(40);
        System.out.println("尾插元素后：");
        head.printList();
        head.SeekAdjoinElem(10);
        head.SeekAdjoinElem(40);
        head.DelItem(30);
        head.ClearList();
        System.out.println("销毁线性表后：");
        head.printList();
    }
}

class DoubleChain {
    int val;
    DoubleChain prev;
    DoubleChain next;

    // 构造函数
    public DoubleChain() {}
    public DoubleChain(int val, DoubleChain prev) {
        this.val = val;
        this.prev = prev;
    }
    public DoubleChain(int val, DoubleChain prev, DoubleChain next) {
        this.val = val;
        this.prev = prev;
        this.next = next;
    }

    // 头插元素
    public void HeadInsert(int e) {
        DoubleChain temp = new DoubleChain(e,this,this.next);
        this.next = temp;
        if (temp.next != null) temp.next.prev = temp;
    }

    // 尾插元素
    public void TailInsert(int e) {
        DoubleChain item = this;
        while (item.next != null) {
            item = item.next;
        }
        item.next = new DoubleChain(e,item);
    }

    // 打印线性表
    public void printList() {
        DoubleChain item = this.next;
        if (item == null) {
            System.out.println("------ 线性表为空 ------");
            return;
        }
        int count = 0;
        while (item != null) {
            System.out.printf("\t线性表的第 %d 个元素是 %d\n",count,item.val);
            count++;
            item = item.next;
        }
    }

    // 返回元素所在节点
    public DoubleChain WhetherExist(int e) {
        DoubleChain item = this.next;
        while (item != null) {
            if(item.val == e) break;
            item = item.next;
        }
        return item;
    }

    // 查找相邻元素
    public void SeekAdjoinElem(int e) {
        DoubleChain item = this.WhetherExist(e);
        if(item == null) System.out.printf("元素 %d 不在线性表中\n",e);
        else {
            if (item.prev == this) {
                System.out.printf("元素 %d 是线性表的第一个元素，无前一个元素\n",e);
            } else System.out.printf("元素 %d 前一个元素是 %d\n",e,item.prev.val);
            if (item.next == null) {
                System.out.printf("元素 %d 是线性表的最后一个元素，无后一个元素\n",e);
            } else System.out.printf("元素 %d 后一个元素是 %d\n",e,item.next.val);
        }
    }

    // 删除元素
    public void DelItem(int e) {
        DoubleChain item = this.WhetherExist(e);
        if(item == null) System.out.printf("元素 %d 不在线性表中\n",e);
        else {
            item.prev.next = item.next;
            item.next.prev = item.prev;
            System.out.println("删除元素后：");
            this.printList();
        }
    }

    // 销毁线性表
    public void ClearList() {
        this.next = null;
        this.prev = null;
    }
}

JavaScript 实现

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
// 结构体的构造函数
function ListNode(val, prev, next) {
    this.val = val || 0;
    this.prev = prev || null;
    this.next = next || null;
}

// 线性表变量(头节点)
let head;

/**
 * @description: 头插入法
 * @param {*} e 元素
 */
const HeadInsert = (e) => {
    let temp = new ListNode(e, head, head.next);
    head.next = temp;
    temp.next ? temp.next.prev = temp : '';
}

/**
 * @description: 尾插入法
 * @param {*} e 元素
 */
const TailInsert = (e) => {
    let temp = new ListNode(e);
    let item = head;
    while (item.next) item = item.next;
    item.next = temp;
    temp.prev = item;
}

/**
 * @description: 遍历线性表
 */
const ErgodicList = () => {
    let count = 0;
    let item = head.next;
    while (item) {
        count++;
        console.log(`\t线性表的第 ${count} 个元素是 ${item.val}`);
        item = item.next;
    }
}

/**
 * @description: 判断元素是否在线性表中
 * @param {*} e 元素
 * @return {*} 状态 0-不存在，1-存在
 */
const WhetherExist = (e) => {
    let index = 0;
    let item = head.next;
    while (item) {
        if (item.val === e) {
            index = 1;
            break;
        }
        item = item.next;
    }
    return index;
}

/**
 * @description: 查找前后元素
 * @param {*} e 元素
 */
const SeekAdjoinElem = (e) => {
    if (WhetherExist(e)) {
        let item = head.next;
        while (item) {
            if (item.val === e) break;
            item = item.next;
        }
        if (item.prev === head) console.log(`元素 ${e} 是线性表第一个元素，无前一个元素`);
        else console.log(`元素 ${e} 的前一个元素是 ${item.prev.val}`);
        if (!item.next) console.log(`元素 ${e} 是线性表最后一个元素，无后一个元素`);
        else console.log(`元素 ${e} 的后一个元素是 ${item.next.val}`);
    } else console.log(`元素 ${e} 不在线性表中`);
}

/**
 * @description: 删除元素 e
 * @param {*} e 元素
 */
const DelItem = (e) => {
    if (WhetherExist(e)) {
        let item = head;
        while (item) {
            if (item.val === e) break;
            item = item.next;
        }
        item.prev.next = item.next;
        item.next.prev = item.prev;
        return 1;
    } else {
        console.log(`元素 ${e} 不在线性表中`);
        return;
    }
}

/**
 * @description: 清空线性表
 */
const ClearList = () => {
    head.next = null;
    head.prev = null;
}

const main = () => {
    head = new ListNode();
    HeadInsert(20);
    HeadInsert(10);
    console.log("头插入元素后：", head);

    TailInsert(30);
    TailInsert(40);
    console.log("尾插入元素后：", head);

    console.log("打印线性表：");
    ErgodicList();

    let eItem = 20;
    SeekAdjoinElem(eItem);

    console.log(`删除元素 ${eItem} 后：`);
    DelItem(eItem) ? ErgodicList() : '';

    // ClearList();
    // console.log("清空元素后：",head);

}

main();

iGmaStation wide Engineer

程码开发