4.若已搜索到表尾（p->next == NULL），仍未找到待删除节点，则显示“未找到”，注意：节点被删除后，只是将它从链表中断开而已，它仍占用着内存，必须释放其所占的内存，否则将出现内存泄漏
（头结点不是头指针，注意两者区别）
8、头节点和头指针
头指针存储的是头节点内存的首地址，头结点的数据域可以存储如链表长度等附加信息，也可以不存储任何信息
值得注意的是：
1.无论链表是否为空，头指针均不为空。头指针是链表的必要元素
2.链表可以没有头节点，但不能没有头指针，头指针是链表的必要元素
3.记得使用free释放内存
单向链表的删除操作实现
struct link *DeleteNode (struct link *head, int nodeData)
{
struct link *p = head, *pr = head;
if (head == NULL)
{
printf("Linked table is empty!\n");
return 0;
}
while (nodeData != p->data && p->next != NULL)
{
pr = p; /* pr保存当前节点 */
p = p->next; /* p指向当前节点的下一节点 */
}
if (nodeData == p->data)
{
if (p == head) /* 如果待删除为头节点 （注意头指针和头结点的区别）*/
{
head = p->next;
}
else /* 如果待删除不是头节点 */
{
pr->next = p->next;
}
free(p); /* 释放已删除节点的内存 */
}
else /* 未发现节点值为nodeData的节点 */
{
printf("This Node has not been found");
}
return head;
}
9、单向链表的插入
向链表中插入一个新的节点时，首先由新建一个节点，将其指针域赋值为空指针（p->next = NULL），然后在链表中寻找适当的位置执行节点的插入操作，
此时需要考虑以下四种情况：
1.若原链表为空，则将新节点p作为头节点，让head指向新节点p（head = p）
2.若原链表为非空，则按节点值的大小（假设节点值已按升序排序）确定插入新节点的位置，若在头节点前插入新节点，则将新节点的指针域指向原链表的头节点（p->next = head），且让head指向新节点（head =p）
3.若在链表中间插入新节点，则将新节点的指针域之下一节点（p->next = pr -> next），且让前一节点的指针域指向新节点（pr->next = p）
4.若在表尾插入新节点，则末节点指针域指向新节点（p->next = p）
单向链表的插入操作实现
/* 函数功能：向单向链表中插入数据 按升序排列*/
struct link *InsertNode(struct link *head, int nodeData)
{
struct link *p = head, *pr = head, *temp = NULL;
p = (struct link *)malloc(sizeof(struct link));
if (p == NULL)
{
printf("No enough meomory!\n");
exit(0);
}
p->next = NULL; /* 待插入节点指针域赋值为空指针 */
p->data = nodeData;
if (head == NULL) /* 若原链表为空 */
{
head = p; /* 插入节点作头结点 */
}
else /* 原链表不为空 */
{
while (pr->data < nodeData && pr->next != NULL)
{
temp = pr; /* 保存当前节点的指针 */
pr = pr->next; /* pr指向当前节点的下一节点 */
}
if (pr->data >= nodeData)
{
if (pr == head) /* 在头节点前插入新节点 */
{
p->next = head; /* 新节点指针域指向原链表头结点 */
head = p; /* 头指针指向新节点 */
}
else
{
pr = temp;
p->next = pr->next; /* 新节点指针域指向下一节点 */
pr->next = p; /* 让前一节点指针域指向新节点 */
}
}
else /* 若在表尾插入新节点 */
{
pr->next = p; /* 末节点指针域指向新节点*/
}
}
return head;
}
（编译器：Microsoft Visual C++ 2010 Express）