非循环单链表（下）

（昨天是第一次在blog平台上发文，因为快过0点了，文章写的比较匆促，今天把非循环单链表的部分全部写完）

获取第一个包含指定数据元素的结点地址

node *getElem_Data(node *l, int data) {
    node *s = l;
    s = s->next;
    while (s != NULL) {
        if (s->data == data) break;
        s = s->next;
    }
    return s;
}

链表从表头开端，顺次向后遍历（即指针s从表头出发，向后顺次指向各个结点）。假如s指向的结点的数据元素与该函数的参数data相同，则退出循环（中止遍历），让指针s停留在该结点。最终，函数回来指针s所指向的结点的地址。

刺进结点

node *insertElem_Back(node *&l, node *s, int pos) {
    node *r = getElem_Pos(l, pos);
    s->next = r->next;
    r->next = s;
    return l;
}

这是一个简略后插结点操作的实现，l为要进行操作的链表的表头，s为要刺进的结点，pos为要刺进到链表中的方位。（在本函数中，咱们直接调用了上篇文章所写的获取指定方位结点地址的函数，详见上篇文章）结点r为该链表的第pos个数据结点，咱们即将刺进的结点s的next指针指向结点r的next指针（即让s指向r的下一个结点），把结点r的next指针指向s，最终回来链表表头l的地址。

删去结点（指定方位）

node *deleteElem_Pos(node *&l, int pos) {
    node *r = getElem_Pos(l, pos - 1);
    node *s = r->next;
    r->next = s->next;
    free(s);
    return l;
}

（和上面的刺进结点一样，这儿直接调用了上一篇文章所写的函数）

咱们在找到链表l中的第（pos-1）个结点r后，设结点s为r的下一个结点，之后让结点r的next指针指向s的next指针指向的结点（即让结点r指向下下个结点），之后释放掉结点s的内存空间，最终回来链表表头i的地址。

删去结点（指定结点）

node *deleteElem_Node(node *&l, node *s) {
    node *r = s->next;
    s->data = r->data;
    s->next = r->next;
    free(r);
    return l;
}

这次是直接把所要删去的结点s的地址在函数的参数中给出，那么，如安在没有前驱结点的情况下，删去该结点呢？咱们只需要，让该结点s的数据元素data和结点s的下一个结点的数据元素相同即可，并且让结点s指向下下个结点，释放结点s的下一个结点的内存空间，即可得到和删去指定结点s同样的作用。

这种办法的优点在于时刻复杂度低，没有顺次遍向来寻觅前驱结点的进程，时刻复杂度由o(n)变为o(1)。

但是，这种办法只适用于链表中间，假如要删去的链表结点为该链表的最终一个结点，则无法运用该办法，需要从头寻觅结点s的前驱结点，然后进行删去操作。

遍历元素并显现

void display(node *&l) {
    node *s = l->next;
    while (s != NULL && s != l) {
        cout << s->data << " ";
        s = s->next;
    }
    if (s == NULL) cout << "单链表" << endl;
    if (s == l) cout << "循环单链表" << endl;
}

这个的实现就比较简略，直接从表头顺次遍历结点并输出每个结点拥有的数据元素即可。

这儿加了一个功能，就是可以经过指针s最终指向的方位来判别该单链表对错循环单链表仍是循环单链表。假如最终结点s为NULL，那么就对错循环单链表；假如为表头结点l，则为循环单链表。

链表表长

int length(node *l) {
    int n = 0;
    node *s = l->next;
    while (s != NULL && s != l) {
        n++;
        s = s->next;
    }
    return n;
}

设一个整型变量n=0，链表从表头结点l开端遍历，每经过一个结点i+1，知道结点s的next指针指向NULL或表头后中止，函数回来n的值。

总结

以上就对错循环单链表的介绍基本操作，这是萌新第一次写blog，基本上就是作为一个自己学习进程傍边的整理和总结。之后每学习到一些新东西，都会在掘金平台上进行弥补。