C 语言实现单向链表

单向链表是链表的一种。链表由节点所构成，节点内含一个指向下一个节点的指针，节点依次链接成为链表。
因此，链表这种数据结构通常在物理内存上是不连续的。链表的通常含有一个头节点，头节点不存放实际的值，它含有一个指针，指向存放元素的第一个节点

1. 头结点没有前驱
2. 尾节点没有后继
3. 其他节点有唯一的前驱和后继

#include <stdio.h>
#include <stdlib.h>

// 数据类型
typedef struct node
{
    int data;
    struct node *next;
}linkNode, *link;

// 创建链表
link createList()
{
    int number;
    link head, p, r;
    head = (link)malloc((sizeof(linkNode)));
    head->next = NULL; // 头结点指针设为 null
    number = scanf("%d", &number);
    r = head;
    while (number != -1) {
        p = (link)malloc((sizeof(linkNode)));
        p->data = number;
        r->next = p;
        r = p;
        scanf("%d", &number);
    }
    r->next = NULL;
    return head;
}

// 查找
link getLink(link head, int index)
{
    int j = -1;
    if (index < 0)
        return NULL;
    link p = head;  // 处理时候使用的头节点
    while (p->next && j < index) {
        
        p = p->next;
        j ++;
    }
    if (j == index) {
        return p;
    }   
    return NULL;
}

// 定位元素
link locateLink(link head, int value)
{
    link p = head->next;
    while (p) {
        if (p->data == value) {
            return p;
        }
        p = p->next;
    }
    return NULL;
}

// 插入元素
void insertLink(link head, int index, int value)
{
    // 判断 index 是否为0, 0-插入到 head 后面,否则，找到 index - 1 节点
    link p, locate;
    if (index == 0) {
        locate = head;
    } else {
        locate = getLink(head, (index - 1));
    }
    if (locate) {
        p = (link)malloc(sizeof(linkNode));
        p->data = value;
        p->next = locate->next;
        locate->next = p;
    } else {
        printf("error\n");
    }
}

// 删除节点
void deleteLink(link head, int index)
{
    link p, locate;
    if (index == 0) {
        locate = head;
    } else {
        locate = getLink(head, (index - 1));
    }

    if (locate && locate->next) {
        p = locate->next;
        locate->next = p->next;
        free(p);
        return;
    }
    printf("not found!\n");
}

// 打印链表
void printLink(link head)
{
    link tmp;
    tmp = head;
    while (tmp->next != NULL) {
        printf("%d\n", tmp->next->data);
        tmp = tmp->next;
    }
}


int main(int argc, char const *argv[])
{
    // printf("%lu\n", sizeof(linkNode));
    link head = createList();
    // printLink(head);
    /*link get = getLink(head, 2);
    if (get != NULL) {
        printf("%d\n", get->data);
    }

    link locate = locateLink(head, 5);
    if (locate != NULL) {
        printf("5 is exist!\n");
    }*/

    printf("************\n");
    printLink(head);
    insertLink(head, 2, 10);
    // deleteLink(head, 2);
    printf("############\n");
    printLink(head);
    return 0;
}

©版权声明：原创作品，允许转载，转载时请务必以超链接形式标明文章 原始出处 & 作者信息。

End