单向链表
单向链表是指存放链表的结点中只有一个指针，指向它的下一个结点，而链表中最后一个结点的next指针为NULL。链表中的第一个结点，我们把它叫做头结点。只要知道了链表的头结点，就可以通过next指针，遍历整个链表。因此，一般在函数中，我们使用头结点来代表整个链表，将头结点传参给函数。
单向链表的存储结构：
typedef struct _node
{
int val;//值域，可以增加更多的值域，这里仅以int类型为代表
struct _node *next;//指针域，指向下一个结点，最后一个结点指向NULL
}Node, *PNode;
2.1.1 创建
如下图所示，在创建链表过程中，将新分配的一个链表结点插入到已知的链表中，可以分为两种情况：从头部插入和从尾部插入。
//从头部插入创建链表算法
node *create_linklist_head()
{
node *h = NULL;
while(1)
{
node *p = (node*)malloc(sizeof(node));
if(p==NULL)
{
return h;
}
memset(p,0,sizeof(node));
printf("Please input a data\n");
scanf_s("%d",&p->value);
p->next = NULL;
if(h==NULL) //如果头结点指针为空，表明这是创建的第一个结点
{
h=p;
}
else
{
p->next = h;
h=p;
}
if(p->value==0)
{
break;
}
}
return h;
}
//从尾部插入链表算法
node *create_linklist_tail()
{
node *h=NULL;
while(1)
{
node *p = (node *)malloc(sizeof(node));
if(p==NULL)
{
return h;
}
memset(p,0,sizeof(node));
printf("Please input a data\n");
scanf_s("%d",&p->value);
p->next = NULL;
if(h==NULL) //如果头结点指针为空，表明这是创建的第一个结点
{
h=p;
}
else
{
node *q=h;//需要从头部遍历到尾部
while(q->next)
{
q=q->next;
}
q->next =p;//q为尾部，q->next=p，将新建结点设置为尾部
p->next = NULL;
}
if(p->value==0)//输入为零，则停止创建链表
{
break;
}
}
return h;
}
2.1.2 插入
创建链表的算法中已经演示了如何从链表的头部和尾部插入链表结点。那么如何将链表结点插入到某个指定的结点之后呢？其实很简单，如下图所示：
让新建结点的next指针指向q的下一个结点，然后再让q的next指针指向p即可。
p->next=q->next;
q->next=p;
2.1.3 删除
如下图所示，在单向链表中要删除一个结点p，首先要通过遍历，找到它的上一个结点q，然后将q的next指针指向p->next，然后即可将p删掉。
void del_list_node(node **h,int value)
{
if(h==NULL)
{
return;
}
node *p = *h;
node *q=NULL;
while(p)
{
if(p->value==value)
{
if(p==*h)
{
*h=(*h)->next;
free(p);
return;
}
else
{
q->next=p->next;
free(p);
return;
}
}
q=p;
p = p->next;
}
}
2.1.4 遍历
所谓对一种数据结构的遍历，是指对其中每个元素访问一次且仅访问一次。由于在链表里，有next指针指向下一个结点，而最后一个结点的next指针为NULL，因此可以通过头结点利用next指针遍历整个链表：
void traverse_list(node *h)
{
node *p = h;
while(p)
{
printf("%d ",p->value);
p=p->next;
}
printf("\n");
}
2.1.5 销毁
销毁链表就是将链表中每个结点都删除掉。这个过程其实也是在遍历链表的时候可以完成的。参考下面的代码：
void destroy_list(node *h)
{
node *p =h;
while(p)
{
node *q=p;//先用q保存这个待删除的结点
p=p->next;//p指向下一个结点
free(q);//现在可以删除q了
}
}
