[数据结构与算法]关于单链表及其常用操作的简单实现

一、结构体定义

1.结构体包含一个数值域和一个指针域

在使用我们创建的节点之前我们要在堆区来开辟一块内存来存放这个节点的相关信息。

2.上面两种方式均可以实现上述的开辟内存功能

二、常用函数的实现

1.首先是创建链表，也就是初始化链表的过程
第一种是头插法：

void CreateLinkHead(LinkPtr* L, int len)    {
    LinkPtr p;
    *L = new Node;
    (*L)->next = NULL;
    for (int i = 0; i < len; ++i)   {
        p = new Node;
        p->data = 104 - i;
        p->next = (*L)->next;
        (*L)->next = p;
    }
}

第二种是尾插法：

void CreateLinkTail(LinkPtr* L, int len)    {
    *L = new Node;
    LinkPtr p, r = *L;
    for (int i = 0; i < len; ++i)   {
        p = new Node;
        p->data = 101 + i;
        r->next = p;
        r = p;
    }

    r->next = NULL; 
}

这里的初始化并不是必须的。

2.获取元素

status GetElem(LinkPtr L, int pos, elemType* e)    {
    if (pos < 1)    {
        return ERROR;
    }
    LinkPtr p = L->next;
    int i = 1;

    for ( ; i < pos && p; ++i)    {
        p = p->next;
    }

    if (!p || i > pos)    {
        return ERROR;
    }
    *e = p->data;

    return OK;
}

3.插入和删除（这也是链表相对与普通数组的优势所在）

status InsertElem(LinkPtr L, int pos, elemType e)    {
    if (pos < 1)    {
        return ERROR;
    }

    LinkPtr p = L;
    int i = 1;

    for ( ; p && i < pos; ++i)    {
        p = p->next;
    }

    if (!p || i > pos)    {
        return ERROR;
    }

    LinkPtr s = new Node;
    s->data = e;
    s->next = p->next;
    p->next = s;

    return OK;
}

status DeleteElem(LinkPtr L, int pos, elemType* e)    {
    if (pos < 1)    {
        return ERROR;
    }
    LinkPtr p = L, q;
    int i = 1;
    for ( ; i < pos && p->next; ++i)    {
        p = p->next;
    }

    if (!(p->next) || i > pos)    {
        return ERROR;
    }

    q = p->next;
    p->next = q->next;
    *e = q->data;

    delete q;
    q = NULL;
    return OK;
}

4.最后再看一下整表删除（当你的链表废弃了，你肯定不想一个一个手动释放内存）：

status ClearLink(LinkPtr* L)    {
    LinkPtr p = (*L)->next, q;
    while (p)   {
        q = p->next;
        delete p;
        p = q;
    }
    (*L)->next = NULL;

    return OK;
}