数据结构——双链表和循环链表

发表于 | 分类于 | 评论数：

摘要：由于太久没有复习数据结构了，导致该忘的都忘了，所以在这里记录重新学习数据结构的笔记，以备以后查看。

双链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

存储结构

1
2
3
4
5
typedef struct DLNode{
    ElemType data;
    struct DLNode *prior;   //指向前驱的指针
    struct DLNode *next;    //指向后继的指针
}DLNode;

与单链表的区别就是定义了一个指向前驱的指针。

初始化结点

1
2
3
4
5
6
7
8
DLNode *create_node(ElemType data)
{
    DLNode *ret = (DLNode*)malloc(sizeof(DLNode));
    ret->data = data;
    ret->prior = NULL;
    ret->next = NULL;
    return ret;
}

尾插法创建双链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
DLNode *create_link_tail(DLNode *L,ElemType data[],int n)
{
    DLNode *s,*r;
    int i;
    L = create_node(NULL);
    r = L;
    for(i = 0;i < n ; i++){
        s = create_node(data[i]);
        s->prior = r;
        r->next = s;
        r = r->next;
    }
    r->next = NULL;
    return L;
}

查找结点某个位置的指针

1
2
3
4
5
6
7
8
9
10
11
12
//查找某个位置的结点的指针
DLNode *find_elem_node(DLNode *L,int p)
{
    int i,count = 0;
    DLNode *ret = L->next;
    if(p<0 || p > link_length(L))
        return 0;
    for(i = 1;i< p ; i++){
        ret = ret->next;
    }
    return ret; //这样写如果未找到也会返回NULL
}

在某个结点后面插入结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//在某个结点后面插入结点
int insert_elem(DLNode *L,ElemType data,int index)
{
    DLNode *s,*p;
    if(index < 0|| index>link_length(L))
        return 0;
    p = find_elem_node(L,index);
    s = create_node(data);
    if(index != link_length(L)){
        s->next = p->next;
        s->prior = p;
        p->next = s;
        s->next->prior = s;
    }
    else{
        p->next = s;
        s->prior=p;
    }
    return 1;
}

此处记得判断是否是最后一个结点插入。

删除结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//删除某个结点并返回
DLNode *delete_node(DLNode *L,int index)
{
    DLNode *ret;
    if(index < 0|| index>link_length(L))
        return 0;
    ret = find_elem_node(L,index);
    if(index != link_length(L)){
        ret->next->prior = ret->prior;
        ret->prior->next = ret->next;
    }
    else{
        ret->prior->next = NULL;
    }
    return ret;
}

获取链表长度

1
2
3
4
5
6
7
8
9
int link_length(DLNode *L)
{
    int count = 0;
    while(L->next){
        count++;
        L = L ->next;
    }
    return count;
}

打印双链表

1
2
3
4
5
6
7
8
int printf_link(DLNode *L)
{
    while(L->next){
        L = L ->next;
        printf("%3d",L->data);
    }
    printf("\n\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
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
//定义双链表的节点类型
typedef struct DLNode{
    ElemType data;
    struct DLNode *prior;   //指向前驱的指针
    struct DLNode *next;    //指向后继的指针
}DLNode;

DLNode *create_node(ElemType data)
{
    DLNode *ret = (DLNode*)malloc(sizeof(DLNode));
    ret->data = data;
    ret->prior = NULL;
    ret->next = NULL;
    return ret;
}
//尾插法
DLNode *create_link_tail(DLNode *L,ElemType data[],int n)
{
    DLNode *s,*r;
    int i;
    L = create_node(NULL);
    r = L;
    for(i = 0;i < n ; i++){
        s = create_node(data[i]);
        s->prior = r;
        r->next = s;
        r = r->next;
    }
    r->next = NULL;
    return L;
}

//查找某个位置的结点的指针
DLNode *find_elem_node(DLNode *L,int p)
{
    int i,count = 0;
    DLNode *ret = L->next;
    if(p<0 || p > link_length(L))
        return 0;
    for(i = 1;i< p ; i++){
        ret = ret->next;
    }
    return ret; //这样写如果未找到也会返回NULL
}

//在某个结点后面插入结点
int insert_elem(DLNode *L,ElemType data,int index)
{
    DLNode *s,*p;
    if(index < 0|| index>link_length(L))
        return 0;
    p = find_elem_node(L,index);
    s = create_node(data);
    if(index != link_length(L)){
        s->next = p->next;
        s->prior = p;
        p->next = s;
        s->next->prior = s;
    }
    else{
        p->next = s;
        s->prior=p;
    }
    return 1;
}
//删除某个结点并返回
DLNode *delete_node(DLNode *L,int index)
{
    DLNode *ret;
    if(index < 0|| index>link_length(L))
        return 0;
    ret = find_elem_node(L,index);
    if(index != link_length(L)){
        ret->next->prior = ret->prior;
        ret->prior->next = ret->next;
    }
    else{
        ret->prior->next = NULL;
    }
    return ret;
}
//双链表长度
int link_length(DLNode *L)
{
    int count = 0;
    while(L->next){
        count++;
        L = L ->next;
    }
    return count;
}
//打印双链表
int printf_link(DLNode *L)
{
    while(L->next){
        L = L ->next;
        printf("%3d",L->data);
    }
    printf("\n\n");
}

int main()
{
    DLNode *A;
    DLNode *local;
    int i;
    ElemType data1[] = {1,2,3,4,5};
    //尾插法
    A = create_link_tail(A,data1,5);
    printf_link(A);
    //长度
    printf("A链表长度为：%d.\n\n",link_length(A));
    //查找结点
    local = find_elem_node(A,2);
    printf("查找到第2位结点为：%d.\n\n",local->data);
    //指定结点后插入元素
    insert_elem(A,6,5);
    printf_link(A);
    //删除某个结点
    local = delete_node(A,6);
    printf("删除的结点为：%d\n\n",local->data);
    printf_link(A);

    return 0;
}

循环链表

循环单链表和循环双链表是由对应的单链表和双链表改造而来，只需要在终点结点和头结点间建立联系即可。循环单链表终端结点的next结点指针指向头结点。循环双链表终端结点的next指针指向表头结点，头节点的prior指针指向表尾节点即可。

tips：

如果P指针沿着循环链表行走，则判断p走到尾节点的条件是p->next == head。循环链表的操作均与非循环链表类似。

相关文章
-------　本文结束　　感谢您的阅读　-------