首页 > 代码库 > 单链表一[带头节点链表]

单链表一[带头节点链表]

单链表实现分带头节点链表和不带头节点链表:

使用头文件如下:

struct LinkNode
{
    void *x; 
    struct LinkNode *next;
};

一,带头节点的链表:

1,链表创建

    程序说明:

    1)函数调用形式:szyu_link_create0("AA", "BB", NULL);其中NULL结尾是在for循环的判断结束条件为x == NULL。使用NULL可以是for循环正常退出

    2)程序先创建头节点head,并初始化head节点

    3)声明指向尾节点的last,并用head进行初始化。

    4)for循环中第一次使用的x是入参中的x。

    5)初始化新增节点,并将尾节点的next指针指向新增节点。并将尾节点指向新增节点

    6)使用了va_start()记得结尾使用va_end()

    7)新增第一个节点时使用last->next = node。此时的last和head是相等的。相当于head->next = node。

struct LinkNode
*szyu_link_create0(void *x, ...)
{
    struct LinkNode *head = NULL;
    head = (struct LinkNode *)malloc(sizeof(struct LinkNode));
    if ( head == NULL )
    {   
        return head;
    }   

    head->next = NULL;

    struct LinkNode *last = head;

    va_list args;
    va_start(args, x); 

    for ( ; x ; x = va_arg(args, void *) )
    {   
        struct LinkNode *node = NULL;
        node = (struct LinkNode *)malloc(sizeof(struct LinkNode));
        if ( node == NULL )
        {   
            return head;
        }

        node->x = x;
        node->next = NULL;
        
        last->next = node;
        last = node;
    }
    va_end(args);

    return head;
}

2,链表插入

    程序说明:

    1)key < 1保证插入的下标不能出现比一小;key - 1 > len保证在链表最后面能插入节点。

    2)cnt = 1而不是0是保证节点停留在插入位置的前一节点。

    3)添加节点到相应的位置即可。

struct LinkNode
*szyu_link_insert0(struct LinkNode *head, void *x, int key)
{
    if ( head == NULL )
    {
        return head;
    }

    int len = szyu_link_length(head);
    if ( key < 1 || key - 1 > len )
    {
        return head;
    }

    struct LinkNode *insert = head;

    int cnt = 1;
    for ( ; cnt < key; cnt++ )
    {
        insert = insert->next;
    }

    struct LinkNode *node = NULL;
    node = (struct LinkNode *)malloc(sizeof(struct LinkNode));
    if ( node == NULL )
    {                                                                                     
        return head;
    }

    node->x = x;
    node->next = insert->next;

    insert->next = node;

    return head;
}

3,链表长度获取

    程序说明:

    1)过掉头节点,再开始获取长度。

int
szyu_link_length(struct LinkNode *head)
{
    if ( head == NULL )
    {
        return 0;
    }

    struct LinkNode *plen = head->next;

    int length = 0;
    for ( ; plen != NULL; plen = plen->next )
    {
        length++;
    }

    return length;
}

4,链表打印:

    程序说明:

    1)如果链表为空,获取只有头节点,则直接返回。

    2)输出时,由于结构体存的void *,故输出需进行类型转换才行。

void
szyu_link_print0(struct LinkNode *head)
{
    if ( head == NULL || head->next == NULL )
    {
        return;
    }

    struct LinkNode *print = head->next;
    int len;
    for ( len = 0; print != NULL; print = print->next )
    {
        printf("%s ", (char *)print->x);
    }

    printf("\n");
}


单链表一[带头节点链表]