欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C语言回顾--简单的单向链表头插法和尾差法编程

程序员文章站 2022-03-09 15:18:43
...

------------------------------------------------------------------------------------------------

前言:

准备笔试题绕不开数据结构,因此最近重新复习关于链表的编程包含单向链表双向链表,以及介绍在制作单向链表中用到的头插法和尾差法;

------------------------------------------------------------------------------------------------

单向链表:

结构体定义:

typedef struct _st_node   //定义结构体,并且结构体中包含指向下一个节点结构体指针
{
    int                     data;
    struct _st_node         *next;
}st_node;

头插法的核心思想:

C语言回顾--简单的单向链表头插法和尾差法编程

在不考虑刚开始创建第一个节点,和最后一个节点的处理:只需要一个指针Head即可完成;

newnode->next = head;
head = newnode;

而单单只靠for循环和带入上述代码是无法创建一个完整的链表:临界处:创建第一个节点,新的节点直接接在Head后面即可,最后一个新节点则需要将结构体内的next指向NULL;

附上完整的头插法代码:

st_node *head_insert(int n)    //返回值为st_node *类型
{
    st_node         *head = NULL;
    st_node         *new_node;
    int             i;

    for(i = 0; i < n ; i++)
    {
        new_node =(st_node *) malloc(sizeof(st_node));
        if(NULL == new_node)
        {
            printf("Malloc failure\n");
            exit(-1);
        }    
        
        new_node->data = i+1;
        new_node->next = NULL;    //创建一个节点的同时将next指向NULL

        if( NULL == head )    //插入第一个节点时
        {   
            head = new_node;
            printf("Add head node [%d]\n",new_node->data);
        }
        else                    //非临界插入
        {
            new_node->next = head;
            head = new_node;
            printf("Add new node [%d]\n",new_node->data);
        }
    }
    return head;
}

尾差法的核心思想:

同样,在不考虑刚开始创建第一个节点,和最后一个节点的处理:此时需要2个指针Head和tail来完成,这个tail指针在其中的作用就是每添加一个节点,tail指针就往后移动一个节点:

C语言回顾--简单的单向链表头插法和尾差法编程

tail->next = new_node;
tail = new_node;

跟头插法相同,考虑临界点:新节点接在Head的后面同时,也将tail指针指向新节点:

附上代码:

st_node *tail_insert(int n)
{
    st_node             *head = NULL;
    st_node             *new_node,*tail;
    int                 i;

    for( i=0 ;i < n ; i++)
    {
        new_node = (st_node *)malloc(sizeof(st_node));
        
        new_node->data = i+1;
        new_node->next = NULL;
        
        if(NULL == head)
        {
            head = new_node;     
            tail = head;
            printf("Add head node [%d]\n",new_node->data);
        }
        else
        {
            tail->next = new_node;
            tail = new_node;
            printf("Add new node [%d]\n",new_node->data);
        }
    }
    return head;
}

附上完整的程序,包括遍历链表和销毁链表:

/*********************************************************************************
 *      Copyright:  (C) 2018 guozhihao
 *                  All rights reserved.
 *
 *       Filename:  link.c
 *    Description:  This file 
 *                 
 *        Version:  1.0.5(08/23/2018)
 *         Author:  Guozhihao <aaa@qq.com>
 *      ChangeLog:  4, Release initial version on "08/23/2018 15:04:18 PM"
 *                 
 ********************************************************************************/
#include <stdio.h>
#include <stdlib.h>

typedef struct _st_node
{
    int                     data;
    struct _st_node         *next;
}st_node;

st_node *head_insert(int n);
st_node *tail_insert(int n);
void travel_list(st_node *head, int (*func_ptr)(st_node *node));    //函数的第二个参数为函数指针
int print_data(st_node *node);
int print_total(st_node *node);
void destory_list(st_node *head);  

int main (int argc, char **argv)
{
    st_node        *head = NULL;
    int             i; 

    /* head insert */
 
    head_insert(head,10);

    
    /* tail insert */

    //head = tail_insert(10);


    travel_list(head,print_data);
    //travel_list(head,print_total);
    
    destory_list(head);  

    return 0;
} /* ----- End of main() ----- */

int print_data(st_node *node)
{
    printf("node [%d] node adress :%p\n",node->data,node);
}

int print_total(st_node *node)
{
    static int     total = 0;
    
    total += node->data;

    printf("total: %d\n",total); 
}

void travel_list(st_node *head,int (*func_ptr)(st_node *node))
{
    st_node          *node;

    node = head;

    while( node != NULL )
    {
        func_ptr(node);
        node = node->next;
    }
    
    return ;
}

void destory_list(st_node *head)  
{
    st_node         *node;

    do
    {
        node = head;
        head = head->next;
        printf("free node [%d] node adress :%p\n",node->data,node);

        free(node);
    
    }while(head != NULL);
}

st_node *head_insert(int n)
{
    st_node         *head = NULL;
    st_node         *new_node;
    int             i;

    for(i = 0; i < n ; i++)
    { 
        new_node =(st_node *) malloc(sizeof(st_node));
        if(NULL == new_node)
        {
            printf("Malloc failure\n"); 
            exit(-1);
        }    
        
        new_node->data = i+1;
        new_node->next = NULL;

        if( NULL == head )
        {   
            head = new_node;
            printf("Add head node [%d]\n",new_node->data);
        }
        else
        {
            new_node->next = head;
            head = new_node;
            printf("Add new node [%d]\n",new_node->data);
        }
    }
    return head;
}
st_node *tail_insert(int n)
{
    st_node             *head = NULL;
    st_node             *new_node,*tail;
    int                 i;

    for( i=0 ;i < n ; i++)
    {
        new_node = (st_node *)malloc(sizeof(st_node));
        
        new_node->data = i+1;
        new_node->next = NULL;
        
        if(NULL == head)
        {
            head = new_node;     
            tail = head;
            printf("Add head node [%d]\n",new_node->data);
        }
        else
        {
            tail->next = new_node;
            tail = new_node;
            printf("Add new node [%d]\n",new_node->data);
        }
    }
    return head;
}

程序运行结果:

[aaa@qq.com C6]$ ./a.out 
Add head node [1]
Add new node [2]
Add new node [3]
Add new node [4]
Add new node [5]
Add new node [6]
Add new node [7]
Add new node [8]
Add new node [9]
Add new node [10]
node [1] node adress :0xa0c010
node [2] node adress :0xa0c030
node [3] node adress :0xa0c050
node [4] node adress :0xa0c070
node [5] node adress :0xa0c090
node [6] node adress :0xa0c0b0
node [7] node adress :0xa0c0d0
node [8] node adress :0xa0c0f0
node [9] node adress :0xa0c110
node [10] node adress :0xa0c130
free node [1] node adress :0xa0c010
free node [2] node adress :0xa0c030
free node [3] node adress :0xa0c050
free node [4] node adress :0xa0c070
free node [5] node adress :0xa0c090
free node [6] node adress :0xa0c0b0
free node [7] node adress :0xa0c0d0
free node [8] node adress :0xa0c0f0
free node [9] node adress :0xa0c110
free node [10] node adress :0xa0c130