C语言之双向链表

C语言之双向链表

双向链表的创建和遍历

#include 
#include

//定义结点结构体
typedef struct student
{
    //数据域
    int num;//学号
    int score;//分数
    char name[20];//姓名

    //指针域
    struct student *front;//保存上一个结点的地址
    struct student *next;//保存下一个结点的地址
}STU;

//创建链表
void double_link_creat_head(STU **p_head,STU *p_new)
{
    STU *p_mov=*p_head;
    if(*p_head==NULL) //当第一次加入链表为空时，head执行p_new
    {
        *p_head = p_new;
        p_new->front = NULL;
        p_new->next = NULL;
    }
    else//第二次及以后加入链表
    {
        while(p_mov->next!=NULL)
        {
            p_mov=p_mov->next; //找到原有链表的最后一个节点
        }

        p_mov->next = p_new; //将新申请的节点加入链表
        p_new->front = p_mov;
        p_new->next = NULL;
    }
}

//链表的遍历
void double_link_print(STU *head)
{
    STU *pb;
    pb=head;
    while(pb->next!=NULL)
    {
        printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name);
        pb=pb->next;
    }
    printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name);

    printf("***********************\n");

    while(pb!=NULL)
    {
        printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name);
        pb=pb->front;
    }
}

int main()
{
    STU *head=NULL,*p_new=NULL;
    int num,i;
    printf("请输入链表初始个数:\n");
    scanf("%d",&num);
    for(i=0;inum,&p_new->score,p_new->name);
        double_link_creat_head(&head,p_new); //将新节点加入链表
    }
    double_link_print(head);
    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

双向链表节点的删除

如果链表为空，则不需要删除
如果删除第一个结点，则保存链表首地址的指针保存后一个结点的地址，并且让这个结点的front保存NULL
如果删除最后一个结点，只需要让最后一个结点的前一个结点的next保存NULL即可
如果删除中间结点，则让中间结点的前后两个结点的指针域分别保存对方的地址即可

//双向链表的删除
void double_link_delete_num(STU **p_head,int num)
{
    STU *pb,*pf;
    pb=*p_head;
    if(*p_head==NULL)//链表为空，不需要删除
    {
        printf("链表为空，没有您要删除的节点\n");
        return ;
    }
    while((pb->num != num) && (pb->next != NULL) )
    {
        pb=pb->next;
    }
    if(pb->num == num)//找到了一个节点的num和num相同，删除pb指向的节点
    {
        if(pb == *p_head)//找到的节点是头节点
        {
            if((*p_head)->next==NULL)//只有一个节点的情况
            {
                *p_head=pb->next;
            }
            else//有多个节点的情况
            {
                *p_head = pb->next;//main函数中的head指向下个节点
                (*p_head)->front=NULL;
            }
        }
        else//要删的节点是其他节点
        {
            if(pb->next!=NULL)//删除中间节点
            {
                pf=pb->front;//让pf指向找到的节点的前一个节点
                pf->next=pb->next; //前一个结点的next保存后一个结点的地址
                (pb->next)->front=pf; //后一个结点的front保存前一个结点的地址
            }
            else//删除尾节点
            {
                pf=pb->front;
                pf->next=NULL;
            }
        }
        free(pb);//释放找到的节点
    }
    else//没找到
    {
        printf("没有您要删除的节点\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

双向链表插入节点

//双向链表的插入
void double_link_insert_num(STU **p_head,STU *p_new)
{
    STU *pb,*pf;
    pb=*p_head;
    if(*p_head == NULL)//链表为空，新来的节点就是头节点
    {
        *p_head=p_new;
        p_new->front=NULL;
        p_new->next=NULL;
        return ;
    }

    while((p_new->num >= pb->num) && (pb->next!=NULL) )
    {
        pb=pb->next ;
    }

    if(p_new->num < pb->num)//找到了一个pb的num比新来的节点的num大，插在pb前边
    {
        if(pb==*p_head)//找到的节点是头节点，插在头节点的前边
        {
            p_new->next=*p_head; //新插入的结点的next保存之前头结点的地址
            (*p_head)->front=p_new; //之前头结点的front保存新插入的结点的地址
            p_new->front=NULL; //新插入的结点的front保存NULL
            *p_head=p_new; //让原本保存链表首地址的指针保存新插入结点的地址
        }
        else
        {
            pf=pb->front;//pf指向 找到节点的前一个节点
            p_new->next=pb;
            p_new->front=pf;
            pf->next=p_new;
            pb->front=p_new;
        }
    }
    else//所有pb指向节点的num都比p_new指向的节点的num小，插在最后
    {
        pb->next=p_new;
        p_new->front=pb;
        p_new->next=NULL;
    }
}
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

总结

#include 
#include

//定义结点结构体
typedef struct student
{
    //数据域
    int num;//学号
    int score;//分数
    char name[20];//姓名

    //指针域
    struct student *front;//保存上一个结点的地址
    struct student *next;//保存下一个结点的地址
}STU;

//创建链表
void double_link_creat_head(STU **p_head,STU *p_new)
{
    STU *p_mov=*p_head;
    if(*p_head==NULL) //当第一次加入链表为空时，head执行p_new
    {
        *p_head = p_new;
        p_new->front = NULL;
        p_new->next = NULL;
    }
    else//第二次及以后加入链表
    {
        while(p_mov->next!=NULL)
        {
            p_mov=p_mov->next; //找到原有链表的最后一个节点
        }

        p_mov->next = p_new; //将新申请的节点加入链表
        p_new->front = p_mov;
        p_new->next = NULL;
    }
}

//链表的遍历
void double_link_print(STU *head)
{
    STU *pb;
    pb=head;
    while(pb->next!=NULL)
    {
        printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name);
        pb=pb->next;
    }
    printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name);

    printf("***********************\n");

    while(pb!=NULL)
    {
        printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name);
        pb=pb->front;
    }
}

//双向链表的删除
void double_link_delete_num(STU **p_head,int num)
{
    STU *pb,*pf;
    pb=*p_head;
    if(*p_head==NULL)//链表为空，不需要删除
    {
        printf("链表为空，没有您要删除的节点\n");
        return ;
    }
    while((pb->num != num) && (pb->next != NULL) )
    {
        pb=pb->next;
    }
    if(pb->num == num)//找到了一个节点的num和num相同，删除pb指向的节点
    {
        if(pb == *p_head)//找到的节点是头节点
        {
            if((*p_head)->next==NULL)//只有一个节点的情况
            {
                *p_head=pb->next;
            }
            else//有多个节点的情况
            {
                *p_head = pb->next;//main函数中的head指向下个节点
                (*p_head)->front=NULL;
            }
        }
        else//要删的节点是其他节点
        {
            if(pb->next!=NULL)//删除中间节点
            {
                pf=pb->front;//让pf指向找到的节点的前一个节点
                pf->next=pb->next; //前一个结点的next保存后一个结点的地址
                (pb->next)->front=pf; //后一个结点的front保存前一个结点的地址
            }
            else//删除尾节点
            {
                pf=pb->front;
                pf->next=NULL;
            }
        }
        free(pb);//释放找到的节点
    }
    else//没找到
    {
        printf("没有您要删除的节点\n");
    }
}

//双向链表的插入
void double_link_insert_num(STU **p_head,STU *p_new)
{
    STU *pb,*pf;
    pb=*p_head;
    if(*p_head == NULL)//链表为空，新来的节点就是头节点
    {
        *p_head=p_new;
        p_new->front=NULL;
        p_new->next=NULL;
        return ;
    }

    while((p_new->num >= pb->num) && (pb->next!=NULL) )
    {
        pb=pb->next ;
    }

    if(p_new->num < pb->num)//找到了一个pb的num比新来的节点的num大，插在pb前边
    {
        if(pb==*p_head)//找到的节点是头节点，插在头节点的前边
        {
            p_new->next=*p_head; //新插入的结点的next保存之前头结点的地址
            (*p_head)->front=p_new; //之前头结点的front保存新插入的结点的地址
            p_new->front=NULL; //新插入的结点的front保存NULL
            *p_head=p_new; //让原本保存链表首地址的指针保存新插入结点的地址
        }
        else
        {
            pf=pb->front;//pf指向 找到节点的前一个节点
            p_new->next=pb;
            p_new->front=pf;
            pf->next=p_new;
            pb->front=p_new;
        }
    }
    else//所有pb指向节点的num都比p_new指向的节点的num小，插在最后
    {
        pb->next=p_new;
        p_new->front=pb;
        p_new->next=NULL;
    }
}

int main()
{
    STU *head=NULL,*p_new=NULL;
    int num,i;
    printf("请输入链表初始个数:\n");
    scanf("%d",&num);
    for(i=0;inum,&p_new->score,p_new->name);
        double_link_creat_head(&head,p_new); //将新节点加入链表
    }
    double_link_print(head);
#if 0
    printf("请输入您要删除的节点的num\n");
    scanf("%d",&num);
    double_link_delete_num(&head,num);
    double_link_print(head);
#endif
    while(1)
    {
        p_new=(STU*)malloc(sizeof(STU));//申请一个新节点
        printf("请输入您要插入的节点的num score name\n");
        scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name);
        double_link_insert_num(&head,p_new);
        double_link_print(head);
    }
    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
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