线性表的双链表

双链表的定义

typedef struct DNode {
    int data;
    struct DNode *prior, *next;
} DNode, *DLinkList;
1
2
3
4

双链表的初始化

bool InitDLinkList(DLinkList &L) {
    L = (DNode *) malloc(sizeof(DNode));
    if (L == NULL) return false;
    L->prior = NULL;
    L->next = NULL;
    return true;
}
1
2
3
4
5
6
7

双链表的判空操作

bool Empty(DLinkList L) {
    return L->next == NULL;
}
1
2
3

双链表的建立

头插法

DLinkList HeadInsert(DLinkList &L) {
    InitDLinkList(L);
    int x;
    scanf("%d", &x);
    while (x != 9999) {
        DNode *s = (DNode *) malloc(sizeof(DNode));
        s->data = x;
        if (L->next == NULL) {	//判断是否还有其他结点
            s->next = NULL;
            L->next = s;
            s->prior = L;
        } else {
            s->next = L->next;
            L->next->prior = s;

            L->next = s;
            s->prior = L;
        }
        scanf("%d", &x);
    }
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

尾插法

DLinkList TailInsert(DLinkList &L) {
    InitDLinkList(L);
    DNode *r = L;
    int x;
    scanf("%d", &x);
    while (x != 9999) {
        DNode *s = (DNode *) malloc(sizeof(DNode));
        s->data = x;
        s->next = NULL;
        s->prior = r;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

双链表的插入

尾插法

//尾插法插入
void TailInsertList(DLinkList &L, int i, int e) {
    DNode *p = GetElem(L, i);
    //printf("第%d位序的值 = %d\n", i, p->data);
    DNode *s = (DNode *) malloc(sizeof(DNode));
    s->data = e;  //赋值给新的s结点
    s->next = p->next;
    if (p->next != NULL)
        p->next->prior = s;

    p->next = s;
    s->prior = p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

双链表的查找

按位查找

DNode *GetElem(DLinkList L, int i) {
    int j = 1;
    DNode *p = L->next;
    if (i == 0)return L;
    if (i < 1)return NULL;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    return p;
}
1
2
3
4
5
6
7
8
9
10
11

按值查找

DNode *LocateElem(DLinkList L, int x) {
    DNode *p = L->next;
    while (p && p->data != x) {
        p = p->next;
    }
    return p;
}
1
2
3
4
5
6
7

双链表的删除

//删除p结点的后继节点
bool DeleteNextDNode(DLinkList &L, int i) {
    DNode *p = GetElem(L, i-1);
    DNode *q = p->next;
    printf("p=%d\n", q->data);
    if (q == NULL) return false;
    p->next = q->next;
    if (p->next != NULL)
        q->next->prior = p;
    free(q);
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12

双链表的遍历

void PrintList(DLinkList L) {
    DNode *p = L->next;
    while (p) {
        printf("%d\t", p->data);
        p = p->next;
    }
    printf("\n");
}
1
2
3
4
5
6
7
8

注意

在按位序查找的值中, i 为第几个位序

插入(尾插)操作中, 插入在位序给 i 的后面, GetElem(L, i);

删除(尾删)操作中, 删除位序为 i 的值, 即要找到位序 i-1 的结点,GetElem(L, i-1);

需特别注意临界值的情况 ! ! !

完整代码

/**
 * @Author JiaHaoHao
 * @Date 2022/07/01 17:18
 * @ClassName: test12
 * @Description: 双链表(带头结点)
 */
#include "stdio.h"
#include "stdlib.h"

typedef struct DNode {
    int data;
    struct DNode *prior, *next;
} DNode, *DLinkList;

//初始化
bool InitDLinkList(DLinkList &L) {
    L = (DNode *) malloc(sizeof(DNode));
    if (L == NULL) return false;
    L->prior = NULL;
    L->next = NULL;
    return true;
}

//判断是否为空
bool Empty(DLinkList L) {
    return L->next == NULL;
}

//在p结点之后插入s结点
bool InsertNextDNode(DNode *p) {
    DNode *s = (DNode *) malloc(sizeof(DNode));
    s->next = p->next;
    if (p->next != NULL)
        p->next->prior = s;

    s->prior = p;
    p->next = s;
}

//头插法建立双链表
DLinkList HeadInsert(DLinkList &L) {
    InitDLinkList(L);
    int x;
    scanf("%d", &x);
    while (x != 9999) {
        DNode *s = (DNode *) malloc(sizeof(DNode));
        s->data = x;
        if (L->next == NULL) {  //判断是否还有其他结点
            s->next = NULL;
            L->next = s;
            s->prior = L;
        } else {
            s->next = L->next;
            L->next->prior = s;

            L->next = s;
            s->prior = L;
        }
        scanf("%d", &x);
    }
    return L;
}

//尾插法建立双链表
DLinkList TailInsert(DLinkList &L) {
    InitDLinkList(L);
    DNode *r = L;
    int x;
    scanf("%d", &x);
    while (x != 9999) {
        DNode *s = (DNode *) malloc(sizeof(DNode));
        s->data = x;
        s->next = NULL;
        s->prior = r;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    return L;
}

//遍历操作
void PrintList(DLinkList L) {
    DNode *p = L->next;
    while (p) {
        printf("%d\t", p->data);
        p = p->next;
    }
    printf("\n");
}

//按值查找
DNode *LocateElem(DLinkList L, int x) {
    DNode *p = L->next;
    while (p && p->data != x) {
        p = p->next;
    }
    return p;
}

//按位查找
DNode *GetElem(DLinkList L, int i) {
    int j = 1;
    DNode *p = L->next;
    if (i == 0)return L;
    if (i < 1)return NULL;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

//尾插法插入
void TailInsertList(DLinkList &L, int i, int e) {
    DNode *p = GetElem(L, i);
    printf("第%d位序的值 = %d\n", i, p->data);
    DNode *s = (DNode *) malloc(sizeof(DNode));
    s->data = e;  //赋值给新的s结点
    s->next = p->next;
    if (p->next != NULL)
        p->next->prior = s;

    p->next = s;
    s->prior = p;
}

//删除p结点的后继节点
bool DeleteNextDNode(DLinkList &L, int i) {
    DNode *p = GetElem(L, i - 1);
    DNode *q = p->next;
    printf("p=%d\n", q->data);
    if (q == NULL) return false;
    p->next = q->next;
    if (p->next != NULL)
        q->next->prior = p;
    free(q);
    return true;
}

int main() {
    DLinkList L;

//    HeadInsert(L);  //头插
    TailInsert(L);  //尾插

    PrintList(L);

    //printf("位序查找: %d\n", GetElem(L, 1));
    //("数值查找: %d\n", LocateElem(L, 1));

    //DeleteNextDNode(L, 4);    //删除操作

    TailInsertList(L, 3, 8);

    PrintList(L);

    return 0;
}
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