数据结构：单链表

链表是一种常见的基础数据结构，结构体指针在这里得到了充分的利用。链表可以动态的进行存储分配，也就是说，链表是一个功能极为强大的数组，他可以在节点中定义多种数据类型，还可以根据需要随意增添，删除，插入节点。链表都有一个头指针，一般以head来表示，存放的是一个地址。

单链表具有以下特点：

• 单个结点创建非常方便，普通的线性内存通常在创建的时候就需要设定数据的大小
• 结点的删除非常方便，不需要像线性结构那样移动剩下的数据
• 结点的访问方便，可以通过循环或者递归的方法访问到任意数据，但是平均的访问效率低于线性表

单链表的创建

typedef struct linklist
{
    /*数据域*/
    int number;
    /*指针域*/
    struct linklist * next;
}LINKLIST;

链表中的节点分为两类，头结点和一般节点，头结点是没有数据域的。链表中每个节点都分为两部分，一个数据域，一个是指针域。

单链表的初始化

LINKLIST *init_list(int n)
{
    int i;
    LINKLIST *head,*node,*end;
    head = (LINKLIST*)malloc(sizeof(LINKLIST));
    end = head;
    for (i = 0; i < n; i++)
    {
        node = (LINKLIST*)malloc(sizeof(LINKLIST));
        scanf("%d",&node->number);
        end->next = node;
        end = node;
    }
    end->next = NULL;
    return head;
}

初始化时，首先创建一个头结点，接着创建对应数量的一般节点，把指针域的指针指向下一个节点并填充数据域，然后将最后一个节点指向NULL。

增加节点

void add_node(LINKLIST *list, int n)
{
    LINKLIST *temp = list;
    LINKLIST *in;
    int i = 0;
    if (temp == NULL)
    {
        printf("list is empty!\n");
        return;
    }

    while (i < (n-1) && temp != NULL)
    {
        i++;
        temp = temp->next;
    }

    if (temp != NULL)
    {
        in = (LINKLIST*)malloc(sizeof(LINKLIST));
        scanf("%d",&in->number);
        in->next = temp->next;
        temp->next = in;
    }
    else
    {
        printf("The %d node is empty,list has %d node\n",n,i);
    }
}

增加节点时首先判断链表是否为空（在C/C++中使用指针前进行合法性判断是一个非常好的编程习惯），然后遍历找到目标位置的前一个节点，将新结点添加到它的后面。

删除节点

void del_node(LINKLIST *list, int n)
{
    LINKLIST *temp = list;
    LINKLIST *out;
    int i = 0;
    if (temp == NULL)
    {
        printf("list is empty!\n");
        return;
    }

    while (i < (n-1) && temp != NULL)
    {
        i++;
        temp = temp->next;
    }

    if (temp != NULL)
    {
        out = temp->next;
        temp->next = out->next;
        out->next = NULL;
        free(out);
    }
    else
    {
        printf("The %d node is empty,list has %d node\n",n,i);
    }
}

删除节点和添加节点差不多，找到目标节点的前一个节点，使其指针域指向目标节点的后面的节点，然后使用free()释放目标节点的空间。

修改节点

void modify_num(LINKLIST *list,int n)
{
    LINKLIST *temp = list;
    int i = 0;
    if (temp == NULL)
    {
        printf("list is empty!");
        return;
    }

    while (i < n && temp != NULL)
    {
        i++;
        temp = temp->next;
    }

    if (temp != NULL)
    {
        scanf("%d",&temp->number);
    }
    else
    {
        printf("the %d node is empty!\n",n);
    }


}

修改节点只需要遍历找到目标节点，修改它的数据域。

输出单链表

void printf_list(LINKLIST *list)
{
    LINKLIST *temp = list;
    if (temp == NULL)
    {
        printf("list is empty!");
        return;
    }

    temp = temp->next;
    while (temp != NULL)
    {
        printf("list number:%d\n",temp->number);
        temp = temp->next;
    }
}

输出单链表很简单，遍历输出数据域即可。