单链表学习(三）

前几天分享了链表数据节点的创建和访问，今天分享关于计算链表数据节点的长度，然后在此基础上实现任意位置的插入新的数据节点。

void node_lenth(node *head)  //计算链表长度的函数，不管什么操作，都需要知道头节点的地址，因此需要传递头指针
{
    int n = 0;    //定义一个变量 n用来统计节点的长度
    node *p;   //定义结构体指针p,用来指向数据节点
    p = head->next;  //将P指向第一个数据节点
    while (p != NULL)  //直到数据节点的指针为NULL，就停止循环
    {
        n++;   //因为p在前面就指向了第一个数据节点，所以n++
        p = p->next;//移动P指针，判断后面是否还有数据节点
    }
         cout<<n<<endl；  ///输出链表的长度
}

在此基础上，我们可以实现在任意位置插入新的数据节点

思路就是定义一个变量用来统计链表的长度，当统计到我们想在后面插入新的数据节点的节点的时候，就可以插入了，然后退出循环，实现新的节点的插入。

具体代码如下：

void node_insert(node *head, int l)  //l用来指明需要在哪个数据节点后面插入新的节点
{
    int n=0;
    node *q,*p;  //q用来指向每一个数据节点，p用来实现新节点的创建
    q = head->next;  //q指向第一个数据节点
    while (q != NULL)
    {
        n++;
        if (n == l)  //当指明插入的L和n相等的时候，说明这里就是我们要插入的位置
        {
            p = (node *)malloc(sizeof(struct node));  //下面就开始创建插入
            cin >> p->a;
            p->next = q->next;
            q->next = p;
            break;   //插入成功后停止循环
        }
        q = q->next;
    }
}

因为q指针指向的第一个数据节点，
所以在插入新的节点的时候，只能在第一个数据节点一直到最后一个数据节点后面插入新的数据节点，不能再头节点后面插入新的数据节点

因此改进之后的代码如下：

void node_insert(node *head, int l)
{
    int n = 0;
    node *q, *p;
    q = head;   //q指向头节点，而不是指向第一个数据节点
    while (q!= NULL)
    {

        if (n == l)   //同样的判断是否找到插入的位置
        {
            p = (node *)malloc(sizeof(struct node));
            cin >> p->a;
            p->next = q->next;
            q->next = p;
            break;
        }
        n++;    //n++位置再判断的后面
        q = q->next;
    }
}

改进之后，就可以满足在头节点后面也能插入新的数据节点

今天分享了计算链表的长度和插入新的数据节点，后面会继续分享链表的基础算法。