数据结构之单链表头插法，尾插法

数据结构之单链表头插法，尾插法

单链表是线性表中的一种，单链表的头插法也称前插法。

链表也是线性表的一种，与顺序表不同的是，它在内存中不是连续存放的。在C语言中，链表是通过指针相关实现的。而单链表是链表的其中一种，关于单链表就是其节点中有数据域和只有一个指向下个节点的指针域。
创建单链表的方法有两种，分别是头插法和尾插法。

所谓头插法，就是按节点的逆序方法逐渐将结点插入到链表的头部。反之尾插法就是按节点的顺序逐渐将节点插入到链表的尾部。

相对来说，头插法要比尾插法算法简单，但是最后产生的链表是逆序的，即第一个输入的节点实际是链表的最后一个节点。

而为了习惯，通常用尾插法来创建链表。下面的代码就是实现了头插法和尾插法

创建头节点

//创建头结点
Node* Create_List ()
{
    //创建头结点
    Node* list = (Node*) malloc(sizeof(Node) / sizeof(char));


    if (NULL == list)   //检验创建是否成功
    {
        return FALSE;
    }

    list->next = NULL;  

    return list;
}

头插法

// 头插法
int Insert_Last (Node* h, LinkData data)
{
    // 判断数据传入是否正确
    if (NULL == h)
    {
        return FALSE;
    }
     // 创建新结点并判断创建是否成功
    Node* node = (Node*) malloc(sizeof(Node) / sizeof(char));
    if (NULL == node)
    {
        return FALSE;
    }

    // 给结点成员变量赋值
    node->data = data;
    node->next = h->next;   // 和头指针的不同：node->next = *h;

    // 让新结点变为链表的第一个节点
    h->next = node;

    return TRUE;
}

尾插法

//尾插
int Insert_Last(Node* h, LinkData data)
{
    if (NULL == h)
    {
        return FALSE;
    }
     // 创建新结点并判断创建是否成功
    Node* node = (Node*) malloc(sizeof(Node) / sizeof(char));
    if (NULL == node)
    {
        return FALSE;
    }

    // 给结点成员变量赋值
    node->data = data;
    node->next = NULL;

     // 让新结点变为链表的最后一个节点
    Node* tmp = h;
    while(tmp->next)
    {
        tmp = tmp->next;
    }
    //找到链表的尾节点并令尾节点指向node
    tmp->next = node;

    return TRUE;
}

扩充

中间插入

//中间插入法
int Insert_Pos(Node *h, int pos, LinkData data)
{
    //判断链表是否存在
    if (NULL == h)
    {
        return FALSE;
    }

    Node* tmp = h;
    int i;
    for (i = 0; i < pos - 1; i++)
    {
        if (NULL == tmp)
        {
            break;
        }
        tmp = tmp->next;
    }
    //判断tmp是否存在
    if (NULL == tmp)
    {
        printf ("插入位置越界");
        return FALSE;
    }

    Node* node = (Node*) malloc(sizeof(Node) / sizeof(char));
    if (NULL == node)
    {
        return FALSE;
    }

    node->data = data;
    node->next = tmp->next;
    tmp->next = node;

    return TRUE;    
}