C语言数据结构之单链表的查找和建立

什么是单链表？

单链表是一种常见的数据结构，是由若干个节点（Node）组成的链式结构，每个节点存储着链表中的元素和指向下一个节点的指针。

单链表的优点是插入、删除元素简单，但是查找元素比较困难。

在C语言中，我们可以使用结构体来定义一个节点：

struct ListNode {
    int val;
    struct ListNode *next;
};

其中，val存储着节点的值，next存储着指向下一个节点的指针。当next为NULL时，表示该节点为链表的最后一个节点。

单链表的建立

首先，我们需要定义一个头结点，头结点的作用是方便对链表的操作和遍历。头结点不存储任何值，其next指针指向第一个有效节点。

下面是一个简单的实现：

struct ListNode* createList(int nums[], int size) {
    struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode)); // 创建头结点
    head->next = NULL; // 初始化头结点
    struct ListNode *tail = head; // 定义链表的尾指针，方便链表的添加操作

    for (int i = 0; i < size; i++) {
        struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode)); // 创建一个新节点
        node->val = nums[i];
        node->next = NULL;
        tail->next = node; // 将新节点添加到链表尾部
        tail = node; // 更新链表的尾指针
    }

    return head;
}

示例：我们构建一个单链表1->2->3->4->5：

int nums[] = {1, 2, 3, 4, 5};
int size = sizeof(nums) / sizeof(nums[0]);

struct ListNode *head = createList(nums, size);

单链表的查找

顺序查找

顺序查找是比较简单的一种查找方式，从头结点开始遍历整个链表，直到找到待查找的元素或者遍历至链表末尾。

下面是顺序查找的实现代码：

struct ListNode *search(struct ListNode *head, int target) {
    struct ListNode *p = head->next;

    while (p) {
        if (p->val == target) {
            return p;
        }
        p = p->next;
    }

    return NULL;
}

示例：查找单链表中值为4的节点

struct ListNode *node = search(head, 4);
if (node) {
    printf("the node is %d\n", node->val);
} else {
    printf("the node is not found\n");
}

二分查找

由于单链表不支持随机访问，所以不适合使用二分查找进行查找操作。

总结

单链表是一种基础、常用的数据结构，掌握单链表的建立和查找操作对于进一步了解链表及其他数据结构有着重要的意义。在实现过程中需要留意指针的操作，确保链表的正确性和完整性。