C语言实现单链表

发表于

单链表常规操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
c复制代码/********************* 单链表的常规操作 ****************************/

LinkList CreateHeadListH();            // 头插法创建单链表
LinkList CreateHeadListT();            // 尾插法创建单链表
int      ListEmpty();                  // 单链表判空
int      ListLength();                 // 求单链表长度
void     Travel();                     // 遍历单链表
int      InsertNode();                 // 插入结点
int      DeleteNode();                 // 删除结点
ElemType GetElem();                    // 按址查值
int      GetLocate();                  // 按值查址
int      RemoveRepeat();               // 去除重复的值

/*****************************************************************/

定义单链表结构体

单链表是由多个结点链接组成，它的每个结点包含两个域，一个数据域和一个链接域(地址域)。

单链表

  • 数据域 data 用来存放具体的数据。
  • 地址域 next 用来存放下一个节点的位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
c复制代码#include "stdio.h"
#include "malloc.h"


#define TRUE  1
#define FALSE 0

typedef int ElemType;        // 单链表存储元素的数据类型

// 定义单链表结构体
typedef struct Node(){
    ElemType data;            // 单链表结点数据域
    struct Node *next;        // 单链表结点地址域（指向下一个结点）
}*LinkList, Node;

构造单链表

头插法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
c复制代码/*
 *    头插法创建单链表(带头结点)
 *    datas 接收数组，用于赋值链表的结点数据
 *    len datas数组的长度，便于遍历
*/
LinkList CreateHeadListH(ElemType *datas, int len){
    // 创建头结点
    LinkList head, new_node;
    head = (LinkList)malloc(sizeof(Node));
    // head -> data = len;    // 可以把链表长度存在头结点的数据域中
    head -> next = NULL;

    // 分配新节点并用头插法链接起来
    for(int i=0;i<len;i++){
        new_node = (LinkList)malloc(sizeof(Node));
        new_node -> data = datas[i];
        new_node -> next = head -> next;
        head -> next = new_node;
    }
    return head;
}

头插法构造单链表时一直往单链表的头部插入结点。

尾插法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
c复制代码/*
 *    尾插法创建单链表(带头结点)
 *    datas 接收数组，用于赋值链表的结点数据
 *    len datas数组的长度，便于遍历
*/
LinkList CreateHeadListT(ElemType *datas, int len){
    // 创建头结点
    LinkList head, p, new_node;
    head = (LinkList)malloc(sizeof(Node));
    head -> next = NULL;
    p = head;

    // 分配新节点并用尾插法链接起来
    for(int i=0;i<len;i++){
        new_node = (LinkList)malloc(sizeof(Node));
        new_node -> data = datas[i];
        new_node -> next = NULL;
        p -> next = new_node;
        p = new_node;
    }
    return head;
}

尾插法构造单链表时一直往单链表的尾部插入结点。

单链表的头尾插法详解

为了不让文章篇幅过长，关于单链表头尾插法的更多具体内容请观看我的另一篇博客 单链表的头尾插法详解

单链表判空

1
2
3
4
5
6
7
c复制代码/*
 *    单链表判空
 *    list 接收单链表
*/
int ListEmpty(LinkList list){
    return (list == NULL || list -> next == NULL);
}

计算单链表长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
c复制代码/*
 *    计算单链表的长度
 *    list 接收单链表
*/
int ListLength(LinkList list){
    LinkList p = list;
    int len = 0;
    if(ListEmpty(list)){
        return len;
    }
    p = p -> next;
    while(p != NULL){
        len ++;
        p = p -> next;
    }
    return len;
}

遍历单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
c复制代码/*
 * 遍历单链表
 * list 单链表
*/
void Travel(LinkList list){
    LinkList p = list;
    if(!ListEmpty(list)){    // 单链表非空情况下才遍历
        p = p -> next;        // 因为带头结点单链表所以要先走一步
        while(p != NULL){
            printf("%d\t", p -> data);
            p = p -> next;
        }
        printf("\n");
    }
}

单链表头、尾插法构造效果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
c复制代码int main(int argc, char const *argv[])
{
    int datas[] = {2, 4, 6, 8, 10};
    // 动态计算datas数组的长度
    // 数组长度 = 数组的总空间大小 / 数组中每个元素所占空间大小
    int len = sizeof(datas) / sizeof(datas[0]);

    printf("头插法构造单链表\n");
    LinkList list_h = CreateHeadListH(datas, len);
    printf("ListEmpty():%d\n", ListEmpty(list_h));        // 判空
    printf("ListLength():%d\n", ListLength(list_h));    // 求长
    printf("Travel():");                                
    Travel(list_h);                                        // 遍历

    printf("\n尾插法构造单链表\n");
    LinkList list_t = CreateHeadListT(datas, len);
    printf("ListEmpty():%d\n", ListEmpty(list_t));
    printf("ListLength():%d\n", ListLength(list_t));
    printf("Travel():");
    Travel(list_t);
    return 0;
}

因为数组是在连续的地址上存储元素，所以可以动态的计算数组的长度，方便遍历。

输入结果如下：

1
2
3
4
5
6
7
8
9
10
11
C复制代码头插法构造单链表
ListEmpty():0
ListLength():5
Travel():10     8       6       4       2

尾插法构造单链表
ListEmpty():0
ListLength():5
Travel():2      4       6       8       10

请按任意键继续. . .

单链表指定位置插入结点

代码实现

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
c复制代码/*
 * 单链表指定位置插入结点
 * list 单链表
 * data 要插入的结点的数据
 * pos  结点插入的位置（逻辑位置（1,2,3,...））
*/
int InsertNode(LinkList list, ElemType data, int pos){
    LinkList p = list, new_node;
    if(ListEmpty(list)){
        printf("空单链表\n");
        return FALSE;
    }

    // 判断插入位置是否合理
    if(pos <= 0 || pos > ListLength(list) + 1){
        printf("插入位置不合理\n");
        return FALSE;
    }
     
    // 寻找到要插入位置的前一个结点
    for(int i = 0; i < pos - 1 && p != NULL; i++){
        p = p -> next;
    }

    // 准备新结点
    new_node = (LinkList)malloc(sizeof(Node));
    new_node -> data = data;

    // 此时p就是要插入位置的前一个结点，p -> next就是要插入位置的结点
    new_node -> next = p -> next;    
    p -> next = new_node;
    return TRUE;
}

详细图解

假设原单链表为：head --> 2 --> 6 ,要插入的结点值为 4，插入位置为 2。

图解单链表插入_01

只需找要插入位置的前一个结点就行，因为插入位置的前一个结点的地址域保存着要插入位置的结点。

此时找到的结点是 new_code1，而 new_code1 -> next 就是结点 new_code2 。

所以我们只要

1
2
c复制代码new_code3 -> next = new_code1 -> next;
new_code1 -> next = new_code3;

先让待插入结点的地址域指向插入位置的结点

后让插入位置的前一个结点的地址域指向待插入结点。

单链表插入图解_02

1, 2, 3代表单链表结点位置

①，②，③代表插入操作的执行步骤顺序

注意：千万不能先让插入位置的前一个结点的地址域指向待插入结点，后让待插入结点的地址域指向插入位置的结点

1
2
3
c复制代码new_code1 -> next = new_code3;
// 此时new_code1 -> next 等于 new_code3, now_code3 -> next = new_code3 没有达到链接
new_code3 -> next = new_code1 -> next;

单链表指定位置删除结点

代码实现

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
c复制代码/*
 * 单链表指定位置删除结点
 * list 单链表
 * *val 用来存储删除结点的数据
 * pos  结点删除的位置（逻辑位置（1,2,3,...））
*/
int DeleteNode(LinkList list, ElemType *val, int pos){
    LinkList p = list, r;
    if(ListEmpty(list)){
        printf("空单链表\n");
        return FALSE;
    }

    // 判断删除位置是否合理
    if(pos <= 0 || pos > ListLength(list)){
        printf("删除位置不合理\n");
        return FALSE;
    }

    // 寻找到要删除结点的前一个位置
    for(int i = 0; i < pos - 1 && p != NULL; i++){
        p = p -> next;
    }

    r = p -> next;            // 记录要删除的结点
    *val = r -> data;        // 把删除结点的数据利用指针返回去
    p -> next = r -> next;    // 把链表重新链接起来
    free(r);                // 释放删除结点的资源
    return TRUE;
}

详细图解

假设原单链表为：head --> 2 --> 4 --> 6 ,删除第 2 个结点。

单链表删除节点图解_01

还是跟插入一样只需找要删除位置的前一个结点就行。

此时找到的结点是 new_code1，而 new_code1 -> next 就是结点 new_code2 ，就是要删除的结点。

1
2
3
c复制代码r = new_code1 - > next;                
new_code1 -> next = r -> next;        // new_code1 -> next = new_code2 -> next;
free(r);

先让变量 r 等于要删除的结点 ,

r = new_code1 - > next; --> r = new_code2;

后让删除位置的前一个结点的地址域指向要删除结点的后一个结点。

1
2
3
4
5
c复制代码new_code1 -> next = r -> next;            // 此时r -> next 等于 new_code2
            ↓↓     
new_code1 -> next = new_code2 -> next;    // new_code2 -> next 等于 new_code3
            ↓↓
new_code1 -> next = new_code3;

最后释放删除结点空间 free(r)

单链表删除节点图解_02

删除第二个位置节点后的单链表：head --> 2 --> 6

按址求值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
c复制代码/*
 *    根据指定位置求结点的值(没有找到返回 0 )
 *    list 单链表
 *    pos  结点位置（逻辑位置（1,2,3,...））
*/
ElemType GetElem(LinkList list, int pos){
    LinkList p = list;
    if(ListEmpty(list)){
        printf("空单链表\n");
        return FALSE;
    }
    if(pos <= 0 || pos > ListLength(list)){
        printf("位置不合理\n");
        return FALSE;
    }

    for(int i = 0; i < pos && p !=NULL; i++){
        p = p -> next;
    }
    return p -> data;
}

按值求址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
c复制代码/*
 *    根据指定的值寻找结点的位置
 *    (如果有多个值相同返回第一个找到的结点的位置, 没找到则返回 0)
 *    list 单链表
 *  data 要查找的值
*/
int GetLocate(LinkList list, ElemType data){
    LinkList p = list;
    int pos = 0;
    if(ListEmpty(list)){
        return FALSE;
    }
    p = p -> next;
    while(p != NULL){
        pos ++;
        if(p -> data == data){
            return pos;
        }
        p = p -> next;
    }
    return FALSE;
}

单链表去重

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
c复制代码/*
 *    去除单链表中重复的值（重复的值只保留一个）
 *    list 单链表
 *  返回值：对单链表进行了去重操作返回 1，否则返回 0
*/
int RemoveRepeat(LinkList list){
    LinkList p = list, q, r;
    int flag = 0;
    if(ListEmpty(list)){
        return FALSE;
    }

    p = p -> next;

    while(p != NULL){
        q = p;
        while(q != NULL && q -> next != NULL){
            if(p -> data == q -> next -> data){
                r = q -> next;    // 记录值相同的结点
                q -> next = r -> next;
                free(r);
                flag = 1;
            }else{
                q = q -> next;
            }
        }
        p = p -> next;
    }
    return flag;
}

原理就是每次拿没有比较过的结点跟单例表中的每一个结点进行比较，遇到相同的就删除其中一个结点。

例如：单链表序列为 2 4 2 8 8 6 6 8 12

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
c复制代码首先拿第一个结点 2 跟单链表的其他结点比较
2      4       2       8       8       6       6       8       12
↑
                        ↓↓
遇到相同的就删除
2      4       8       8       6       6       8       12
    
                        
2比完了一轮去重了2，然后用第二个结点 4 跟单链表的其他没有比较过的结点比较
2      4       8       8       6       6       8       12  
         ↑ 
                        ↓↓
2      4       8       8       6       6       8       12 
                        
                        
4比完了一轮去重了4，然后用第三个结点 8 跟单链表的其他没有比较过的结点比较
2      4       8       8       6       6       8       12 
               ↑
                        ↓↓
2      4       8       6       6       12
    
循环类推
2      4       8       6       6       12
                       ↑
                    ↓↓
2      4       8        6       12 
    
最后一步    
2      4       8        6       12
                                ↑
                ↓↓
2      4       8        6       12

看看去重效果

1
2
3
4
5
6
7
c复制代码去重前的单链表
ListLength():9
Travel():2      4       2       8       8       6       6       8       12

去重后的单链表
ListLength():5
Travel():2      4       8       6       12

源代码

源代码已上传到 GitHub Data-Structure-of-C，欢迎大家来访。

✍ 码字不易，万水千山总是情，点赞再走行不行，还望各位大侠多多支持❤️

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%