单链表的节点插入、遍历、删除、逆序
创建一个链表的节点结构体
struct node
{
int date; //有效数据
struct node *pNext; //指向下一个节点（结构体）的指针
}；
struct node的理解：结构体节点模型
为链表节点申请内存（将指针指向绑定的内存）：
struct node*p=(struct node *)malloc(sizeof(struct node));
/***************************************************************************************************/
两个概念：头指针、头节点
头指针（指向头节点）：一个普通指针，数据类型是struct node*，用于链接后面所有的节点
头节点：存放链表节点个数。。。，打印数据时，要注意是普通节点数据还是头节点数据（关键看当前指针位置）
void bianli1(struct node*pH)
{
struct node *p = pH; // p走到头节点（循环初始化）
printf("-----------开始遍历-----------\n");
while (NULL != p->pNext) // 是不是最后一个节点（循环判断），只能走到倒数第二个节点，此节点（指向最后一个节点）的指针为NULL，不符合条件，退出
{
printf("node data: %d.\n", p->data);
p = p->pNext; // 走到下一个节点（循环增量）
}
printf("node data: %d.\n", p->data); //最后一个节点的打印
printf("-------------完了-------------\n");
}
void bianli2(struct node*pH)
{
struct node *p = pH;
printf("-----------开始遍历-----------\n");
while (NULL != p->pNext) // 找到倒数第二个节点指针
{
p = p->pNext; //在找到倒数第二个节点指针时，先p = p->pNext;后printf能够打印出最后一个节点数据
printf("node data: %d.\n", p->data);
}
printf("-------------完了-------------\n");
}
总结：比较bianli1与bianli2的区别，bianli1能够打印节点个数、节点遍历；bianli2能够节点遍历；注意p = p->pNext和printf顺序不同，对当前打印结果的区别
/**************************创建一个结构体节点*********************************/
struct Node *pHeader;
/*****************************第一个结构体节点******************************/
struct Node *mynode=(struct Node *)malloc(sizeof(struct Node));
if(NULL==mynode)
{
printf("malloc error\n");
exit(1);
}
mynode->data=1;
pHeader=mynode; //头指针指向第一个节点指针mynode
/*******************针对上面的改进：创建节点的代码封装函数******************/
structnode* creat_note(int date) //date作为数据的传入
{
struct node *p=(struct node*)malloc(sizeof(struct node));//
if (NULL==p)
{
printf("malloc error.\n");
return NULL;
}
bzero(p,sizeof(struct node));
p->date=date;
p->pNext=NULL;
return p; //p为返回值，用来返回新建节点结构体的指针
}
/***********************节点的右插入函数***********************************/
void insert_tail(struct Node *pHeader,struct Node *new)
{
struct Node *p=pHeader;
if(NULL!=p->pNext)
{
p=p->pNext;
}
p->pNext=new; //在节点链末尾加入一个新节点
}
struct Node *pHeader=node_creat(3);//这里需要先指向一个非空的节点
insert_tail(pHeader,node_creat(1)); //node_creat(1)的返回值（节点结构体指针），作为函数的输入，并挂接在链表末尾
/*************************************删除节点*******************************************/
void delete_node(struct node *pH, int data)
{
struct node *p = pH;
struct node *prev=NULL;
printf("-----------开始遍历-----------\n");
while (NULL != p->pNext) // 是不是最后一个节点
{
prev=p; //保存上一个节点
p = p->pNext;
if(((p->data)==data)&&(NULL==(p->pNext))) //尾节点
{
prev->pNext=NULL;
free(p);
}
if(((p->data)==data)&&(NULL!=p)) //非尾节点
{
prev->pNext = p->pNext; // 要删除的节点的前一个节点和它的后一个节点相连，这样就把要删除的节点给摘出来了
free(p);
}
}
}
/********************************单链表的逆序******************************************/
void reverse_linkedlist(struct node *pH)
{
struct node *p = pH->pNext; // pH指向头节点，p指向第1个有效节点
struct node *pBack; // 保存当前节点的后一个节点地址
// 当链表没有有效节点或者只有一个有效节点时，逆序不用做任何操作
if ((NULL ==p) || (NULL == p->pNext))
return;
// 当链表有1个及1个以上节点时才需要真正进行逆序操作
while (NULL != p->pNext) // 是不是最后一个节点
{
// 原链表中第一个有效节点将是逆序后新链表的尾节点，尾节点的pNext指向NULL
pBack = p->pNext; // 保存p节点后面一个节点地址
if (p == pH->pNext)
{
// 原链表第一个有效节点p->pNext = NULL
p->pNext = NULL;
}
else
{
// 原链表的非第1个有效节点
p->pNext = pH->pNext;
}
pH->pNext = p;
//p = p->pNext; // 这样已经不行了，因为p->pNext已经被改过了
p = pBack; // 走到下一个节点
}
// 循环结束后，最后一个节点仍然缺失
insert_head(pH, p);
}