【C语言数据结构】单链表

单链表是一种常见的数据结构，它由一组节点组成，每个节点包含两个信息：数据和指向下一个节点的指针。单链表的特点是数据元素的逻辑顺序与物理顺序不一定相同，数据元素对应的地址是通过指针相互连接而实现的。

单链表的实现方式是每个节点包含数据和指向下一个节点的指针，最后一个节点的指针指向空NULL。对于单链表的操作有：插入、删除、查找、遍历等。由于单链表的插入和删除只需要改变指针指向，所以效率很高。

在C语言中，实现单链表可以采用结构体和指针相结合的方式。例如：

typedef struct node 

{

    int data; //数据域

    struct node* next; //指针域

}Node;

Node* create() //创建空表

{

    Node* head;

    head = (Node*)malloc(sizeof(Node)); //申请头节点

    head->next = NULL; //指针域指向NULL

    return head;

}

void insert(Node* head,int x) //在表头插入数据x

{

    Node* p;

    p=(Node*)malloc(sizeof(Node)); //申请新节点

    p->data=x;

    p->next=head->next; //插在表头

    head->next=p;

}

void delete(Node* head,int x) //删除数据x

{

    Node *p, *pre;

    p = head->next;

    pre = head;

    while(p != NULL) //遍历链表

    {

        if(p->data == x)

        {

            pre->next = p->next; //修改指针

            free(p); //释放节点内存

            break;

        }

        pre = p;

        p = p->next;

    }

}

Node* find(Node* head,int x) //查找数据x

{

    Node* p;

    p=head->next;

    while(p != NULL)

    {

        if(p->data == x)

            return p;

        p=p->next;

    }

    return NULL;

}

void traverse(Node *head) //遍历链表

{

    Node *p;

    p = head->next;

    while(p != NULL)

    {

        printf("%d ", p->data); //输出数据

        p = p->next; //指向下一个节点

    }

}

void destroy(Node* head) //删除整个链表

{

    Node* p;

    while(head != NULL)

    {

        p = head;

        head = head->next;

        free(p);

    }

}

以上是单链表的基本操作，可以根据实际需求进行改变。同样的，单链表也有缺点，就是无法进行快速的逆向遍历。此外，由于每个节点都需要存储指针，空间开销较大。

总之，单链表是C语言中非常常见的数据结构，学好它对程序开发是非常有帮助的。