2.1单链表

￡神魔★判官ぃ 2024-04-08 09:13 64阅读 0赞

## 单链表的节点 ##

![gbhy65redc][]

> 如图所示，单链表的节点分为数据域和指针域，可以将它们视为一个整体，称之为节点，稍后我们会用结构体来表示节点。  
> **数据域**，顾名思义，就是存放数据的地方。  
> **指针域**，是用来存放指针变量的地方，指针指向下一个节点的地址。

## 单链表的表示 ##

> 单链表是线性表的链式表示和实现。把节点链接起来，就形成了单链表。

![de4r5tgvfc][]

## 定义表示节点的结构体 ##

如何用C语言描述节点？这里我们用到了struct。

struct node {
        
        /* 后继节点 */
        struct node *next;
        /* 值 */
        int data;
    };

首先我们定义了一个结构体，结构体的标记为node。  
其次，它具有两个属性，一个是int类型的data，也就是上文提到的数据域。还一个是指针域。

##### 如何理解struct node \*next呢？ #####

要知道，指针域是存放指针变量的，这个变量名叫做 next,又因为这个指针是指向下一个节点的地址的，换句话说，这个指针指向的是一个我们定义的用来表示节点的结构体。所以这个指针变量的类型为 struct node。星号\*表示它是指针变量。所以合起来就是struct node \*next。  
最后，为了方便，我们可以使用typedef关键字为struct node取一个别名。

typedef struct node {
        
        /* 后继节点 */
        struct node *next;
        /* 值 */
        int data;
    }list;

这样，在后面的代码书写中, list就等价于struct node了。  
比如我们使用这个结构体创建一个新的节点， list \*new\_node就等价于struct node \*new\_node。

## 单链表的创建 ##

list * create_list()
    {
        
        /* 创建一个新的节点，由于使用了typedef关键字，此处 node *head与struct node *head等价    */
        list *head = (list *)malloc(sizeof(list));
        if(head==NULL) return NULL;
        /* 初始化节点 */
        head->data = 0; // 头结点数据域，我们用来表示链表长度
        head->next = NULL; 
        return head;
    }

![de4rde3dcuh7][]  
此函数会创建一个单链表，并返回头指针。  
头指针是指向头结点地址的指针，和节点中指向下一个节点的指针是相同类型。  
首先，我们用malloc函数开辟了一块list大小的内存，并返回了指向该内存块首地址的指针，同时将此指针赋值给头指针变量。  
接着，判断此指针是否为空，为空，则说明内存申请失败（一般不会)。  
然后，对该节点进行初始化。  
最后，函数返回头指针，结束。

**为什么设置头节点？**

头节点的数据域一般无意义，这里为了方便后面的插入和删除操作而设置，头节点并非链表所必须。  
头节点后面的第一个元素节点，称为首元节点。

## 单链表的插入 ##

试想如下情况，一个新的节点n，要插入到x节点后。  
![d3erdfchju8][]  
图中虚线表示断开连接，下同。  
按照一般思路可能是:

x->next = n;
    n->next = x->next;

显然，这是错误的，因为执行x->next = n之后，n->next = x->next等价于n->next = n ，所以正确的做法应该是这样；

n->next = x->next;
    x->next = n;

> 完整版插入函数：  
> 插入函数接受三个参数，被插入节点的链表的指针head，新结点的数据data，和要插入的位置pos;

list * list_insert_node(list *head, int data, int pos)
    {
           
        int i;
        list *curr = head;
    
        /* 如果要插入的位置比链表长，则属于非法操作 */
        if(pos > curr->data) return NULL;
    
        /* 创建一个节点，并初始化 */
        list *node = (list *)malloc(sizeof(list));
        if(node==NULL) return NULL;
        node->data = data;
        node->next = NULL;
    
        /* 遍历链表，找到要插入的位置 */
        for(i=0;i<pos;i++){
        
            curr = curr->next;
        }
    
        /* 插入 */
        node->next = curr->next;
        curr->next = node;
    
        /* 链表长度+1 */
        head->data++;
        return head;
    }

**可以在main函数中调用测试：**

list *l = create_list();
    printf("当前链表长度：%d\n", l->data);
    list_insert_node(l, 1, 0);
    printf("当前链表长度：%d\n", l->data);

**使用gcc编译:**

gcc -fsanitize=address -fno-omit-frame-pointer  -g linked_list.c  && ./a.out

输出正常且无内存报错信息：

当前链表长度：0
    当前链表长度：1

## 单链表的遍历 ##

较为简单，不再解释

/* 打印链表数据，但不包括头结点的数据*/
    void print_list(list *head)
    {
        
        list *curr = head->next;
        while (curr)
        {
        
            printf("%d \t", curr->data);
            curr = curr->next;
        }
        printf("\n");
    }

## 单链表的删除 ##

![mki876tb8ujn][]

> 假设要删除head后的节点，那么直接让head->next = head->next->next即可，但不要忘记释放被删除的节点。  
> 基于此思路：

list *list_delete_data(list *head, int pos)
    {
        
        int i;
        list *curr = head;
    
        /* 如果要删除的位置比链表长，则属于非法操作 */
        if(pos > curr->data) return NULL;
    
        /* 遍历链表，找到要删除的节点的前一个节点的指针 */
        for(i=0;i<pos;i++){
        
            curr = curr->next;
        }
        // 临时记录将被删除的节点
        list *temp = curr->next;
        // 删除节点
        curr->next = curr->next->next;
        
        //释放掉被删除节点的内存
        free(temp);
        head->data--;
        return head;
    }

## 单链表的测试 ##

这样，一个基础的链表就写好了，可以在main函数中测试。

int main()
    {
        
        int i;
        list *l = create_list();
        // 多次插入数据
        for(i=0;i<5;i++){
        
            list_insert_node(l, i, 0);
            print_list(l);
        }
        list_delete_data(l, 0);
        print_list(l);
        return 0;
    }

编译与输出：

# gcc -fsanitize=address -fno-omit-frame-pointer  -g linked_list.c  && ./a.out
    0 
    1       0 
    2       1       0 
    3       2       1       0 
    4       3       2       1       0 
    3       2       1       0

[gbhy65redc]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/c208218a3d0741d89fd4726bc6350e86.jpeg
[de4r5tgvfc]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/1ba8458bac6e4d9a9a1bce896f137c98.jpeg
[de4rde3dcuh7]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/6468de12814340d1ab3ce7c96f59a197.jpeg
[d3erdfchju8]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/26643fda92ec45d88cd15b96d6ce083b.jpeg
[mki876tb8ujn]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/719616ad563447a8b0eb844810aafaeb.jpeg