单链表入门（二）

电玩女神 2022-06-04 02:55 172阅读 0赞

上篇博文，介绍了线性表、单链表等概念。这篇博文，我们就写代码来实现**带头结点的非循环单链表**。

# 1.结点的定义 #

typedef int element_t;
    
    struct node
    {
        element_t data;    //数据域
        struct node *next; //指针域
    };
    
    typedef struct node node_t;

# 2.初始化 #

void list_init(node_t *head)
    {
        assert(head!=NULL);
        head->next = NULL;
    }

`head`是头结点的地址，下文同。

# 3.求链表的长度 #

/* 求链表中元素的个数，为空则返回0 */
    int list_length(node_t *head)
    {
        assert(head!=NULL);
    
        int count = 0;
        while(head->next != NULL)
        {
            head = head->next;
            ++count;
        }
        return count;
    }

# 4.判断链表是否为空 #

/* 判断链表是否为空， 为空返回1，不为空返回0 */
    int list_is_empty(node_t *head)
    {
        assert(head!=NULL); 
        return(head->next == NULL);
    }

# 5.插入结点 #

/* 把新结点插入到某个结点的后面，此函数主要被其他函数调用 */
    void insert_node(node_t *prev, node_t *new_node)
    {
        assert(prev!=NULL);
        assert(new_node!=NULL);
    
        new_node->next = prev->next;//图中第一步
        prev->next = new_node; //图中第二步
    }

这个函数表示把新结点`new_node`插入到结点`prev`的后面。  
对于初学者，可能不好理解，请看示意图：

![这里写图片描述][SouthEast]

![这里写图片描述][SouthEast 1]

/* 已知新结点的地址，把新结点插入链表头 */
    void list_insert_head(node_t *head, node_t *new_node)
    {
        insert_node(head,new_node);
    }

这种插入方法叫“头插法”。

/* 返回链表最后一个结点的地址，若链表为空，则返回头结点的地址 */
    node_t *list_get_last(node_t *head) 
    {
        assert(head!=NULL);
    
        while(head->next!=NULL)
            head = head->next;
        return head; 
    }

/* 已知新结点的地址，把新结点插入链表尾 */
    void list_insert_tail(node_t *head,node_t *new_node) 
    {
        node_t *prev = list_get_last(head);
        insert_node(prev,new_node);
    }

这种插入方法叫“尾插法”。

/* 向链表表头插入值为x的结点，成功返回0，失败返回-1 */
    int insert_element_head(node_t *head, element_t x)
    {
        assert(head!=NULL);
    
        node_t *new_node = (node_t *)malloc(sizeof(node_t));
        if(new_node==NULL)
        {
            printf("malloc failed\n");
            return -1;
        }
        new_node->data = x;
        list_insert_head(head,new_node);
        return 0;
    
    }
    /* 向链表末尾添加值为x的结点，成功返回0，失败返回-1 */
    int insert_element_tail(node_t *head, element_t x)
    {
        assert(head!=NULL);
    
        node_t *new_node = (node_t *)malloc(sizeof(node_t));
        if(new_node==NULL)
        {
            printf("malloc failed\n");
            return -1;
        }
        new_node->data = x;
        list_insert_tail(head,new_node);
        return 0;
    
    }

/* 返回第pos个结点的前一个结点的地址，失败则返回NULL */
    node_t* get_pos_prev_addr(node_t *head, int pos)
    {
        assert(head!=NULL);
        if(list_is_empty(head))
        {
            printf("the list is empty, get failed\n");
            return NULL;
        }
    
        int length = list_length(head);
        if( (pos<1) || (pos>length) )
        {
            printf("pos is out of range\n");
            return NULL;
        }
    
        int count = 0;
        node_t *cur = head->next;
        node_t *prev = head;
        while(cur != NULL)
        {
            ++count;
            if(count == pos)
                return prev;
    
            prev = cur;
            cur = cur->next;
        }
    }
    
    /* 在pos位置插入新元素x，例如pos=3,则新元素在第3个位置.操作成功返回0，失败返回负数 */
    int insert_element_to_pos(node_t *head, element_t x, int pos)
    {
        assert(head!=NULL);
    
        int length = list_length(head);
        if(length==0)
        {
            printf("the list is empty, insert failed\n");
            return -1;
        }
        if( (pos<1) || (pos >length) )
        {
            printf("pos is out of range\n");
            return -2;
        }
    
        node_t *new_node = (node_t *)malloc(sizeof(node_t));
        if(new_node==NULL)
        {
            printf("malloc failed\n");
            return -3;
        }
        new_node->data = x;
        node_t *prev = get_pos_prev_addr(head,pos);
        insert_node(prev,new_node);
    
        return 0;
    }

# 6.链表的遍历和安全遍历 #

/* 链表的遍历, todo参数由用户传入 */
    void list_for_each(node_t *head, void(*todo)(node_t *node))
    {
        assert(head != NULL);
        assert(todo != NULL);
    
        node_t *temp = head->next;
        while(temp != NULL)
        {
            todo(temp);
            temp = temp->next;
        }
    }
    
    /* 链表的安全遍历 */
    void list_for_each_safe(node_t *head, void(*todo)(node_t *node))
    {
        assert(head != NULL);
        assert(todo != NULL);
    
        node_t *cur = head->next;
        node_t *next;
        while(cur != NULL)
        {
            next = cur->next;
            todo(cur);
            cur = next;
        }
    }

# 7.链表的清空 #

void list_clear(node_t *head)
    {
        void(*todo)(node_t *node) = (void(*)(node_t *))free;
        list_for_each_safe(head,todo);
        list_init(head);
    }

`(void(*)(node_t *))free`表示把free进行强制类型转换，转换成`void(*)(node_t *)`类型的指针。  
此函数执行后，所有结点的空间被释放，只剩下头结点，成为一个空链表。

# 8.链表的销毁 #

void list_destroy(node_t *head)
    {
        list_clear(head);
        free(head);
    }

此函数执行后，所有结点的空间被释放，包括头结点。销毁后，链表就不复存在了。

# 9.链表的创建 #

链表的创建有很多种方法，可以头插，也可以尾插，这里仅举一例。

/* 从控制台创建链表，输入负数则停止。成功则返回头结点的地址，失败则返回NULL*/
    node_t *list_create(void)
    {
        node_t *head = (node_t *)malloc(sizeof(node_t));
        if(head==NULL)
        {
            printf("malloc failed\n");
            return NULL;
        }
    
        list_init(head); // 初始化头结点
    
        int data;
        printf("please input the number, negative will quite\n");
        scanf("%d", &data);
    
        while(data>=0)
        {
            node_t *new_node = (node_t *)malloc(sizeof(node_t));
            if(new_node==NULL)
            {
                printf("malloc failed\n");
                list_destroy(head);  //释放空间
                return NULL;
            }
            new_node->data = data;
            list_insert_head(head,new_node); //这句话也可以换成 list_insert_tail(head,new_node);
    
            printf("please input the number, negative will quite\n");
            scanf("%d", &data);
        }
    
        return head;
    }

# 10.返回某个结点的地址或者值 #

/* 返回第pos个结点的地址（从1开始数），失败则返回NULL */
    
    node_t* get_pos_addr(node_t *head, int pos)
    {
        assert(head!=NULL);
    
        int length = list_length(head); 
        if(length==0)
        {
            printf("the list is empty, get failed\n");
            return NULL;
        }   
        if( (pos<1) || (pos>length) )
        {
            printf("pos is out of range\n");
            return NULL;
        }
    
        int count = 0;
        node_t *cur = head->next;
        while(cur != NULL)
        {
            ++count;
            if(count == pos)
            {
                return cur;
            }
    
            cur = cur->next;
        }
    }
    
    /* 返回第pos个结点的值（由输出型参数value指示），成功返回值为0，失败返回值为-1 */
    int get_pos_element(node_t *head, int pos, element_t *value)
    {
        node_t *p_node = get_pos_addr(head,pos);
        if(p_node)
        {
            *value = p_node->data;
            return 0;
        }
        else
        {
            return -1; //failed
        }
    
    }

需要强调的是，参数`value`是输出型参数，第pos个结点的值由此指针指向。

# 11.查找 #

/* 查找具有给定值的第一个元素，成功则返回该结点的地址，失败返回NULL*/
    node_t *find_element_pos(node_t *head, element_t x)
    {
        assert(head!=NULL);
        if(list_is_empty(head))
            return NULL;
    
        node_t *temp = head->next;
        while(temp!=NULL)
        {
            if(temp->data == x)
                return temp;
    
            temp = temp->next;
        }
    
        return NULL;
    }

/* 查找具有给定值的第一个元素，成功则返回该结点的前一个结点的地址，失败返回NULL*/
    node_t *find_element_prev_pos(node_t *head, element_t x)
    {
        assert(head!=NULL);
        if(list_is_empty(head))
            return NULL;
    
        node_t *temp = head->next;
        node_t *prev = head;
        while(temp!=NULL)
        {
            if(temp->data == x)
                return prev;
    
            prev = temp;
            temp = temp->next;
    
        }
    
        return NULL;
    }

# 12.修改结点的值 #

/* 把第pos个结点的值修改为x,成功则返回0，失败返回-1 */
    int modify_element(node_t *head, int pos, element_t x)
    {
        node_t *p_node = get_pos_addr(head,pos);
        if(p_node)
        {
            p_node->data = x;
            return 0;
        }
        else
        {
            return -1; //failed
        }
    
    }

# 13.删除结点 #

/* 已知某结点的地址为prev，删除它后面的那个结点, 此函数主要被其他函数调用 */
    void delete_post_node(node_t *prev)
    {
        assert(prev->next != NULL);
    
        node_t *node_del = prev->next;
        prev->next = node_del->next;
        free(node_del);
    }

/* 删除第pos个结点，此结点的值由value指向。删除成功返回0，失败返回-1 */
    int delete_pos_node(node_t *head, int pos, element_t *value)
    {
    
        int length = list_length(head); 
        if(length==0)
        {
            printf("the list is empty, get failed\n");
            return -1;
        }
        if( (pos<1) || (pos >length) )
        {
            printf("pos is out of range\n");
            return -2;
        }
    
        node_t *prev = get_pos_prev_addr(head,pos);
        *value = prev->next->data;
        delete_post_node(prev);
        return 0;
    }
    
    /* 删除表头结点，此结点的值由value指向。删除成功返回0，失败返回-1 */
    int delete_from_head(node_t *head, element_t *value)
    {
        return delete_pos_node(head,1,value);   
    }
    
    /* 删除表尾结点，此结点的值由value指向。删除成功返回0，失败返回-1 */
    int delete_from_tail(node_t *head, element_t *value)
    {
        int length = list_length(head); 
        return delete_pos_node(head,length,value);
    }
    
    /* 删除值为x的第一个结点，成功返回0，失败返回负数 */
    int delete_element(node_t *head, element_t x)
    {
        assert(head!=NULL);
        node_t *prev = find_element_prev_pos(head,x);
        if(prev)
        {
            delete_post_node(prev);
            return 0;
        }
        else
        {
            return -1;
        }
    }

【完】

[SouthEast]: /images/20220604/75800d22ef114ed19c2f3d2feaa41b58.png
[SouthEast 1]: /images/20220604/e570121e686240aca60d8545227d9123.png