第一部分 线性表的链式存储(二)

/程序前边定义的结构、数据类型与（一）中相同

/*初始化*/
void InitList(pLinkList L)
{
    L = NULL;
}

/*重置为空表*/
void ClearList(pLinkList L)
{
    pLinkList p;
    while(p)
    {
        p = L;
        L = p->next;
        free(p);
    }
}

/*判断是否为空表*/
Status ListEmpty(pLinkList L)
{
    if(L)
        return FALSE;
    else
        return TRUE;
}

/*返回数据元素的个数*/
int ListLength(pLinkList L)
{
    int i = 0;
    pLinkList p = L;
    while(p)
    {
        i++;
        p = p->next;
    }
    return i;
}

/*当第i个元素存在时，赋值给e,并返回OK，否则返回ERROR*/
Status GetElem(pLinkList L,int i,elemtype *e)
{
    int j = 1;
    pLinkList p;
    while(j<i && p)
    {
        p = p->next;
        j++;
    }
    if(i == j && p)
    {
        *e = p->data;
        return OK;
    }
    return ERROR;
}

/*返回链表中第一个与e满足compare关系的数据元素的为序*/
int LocateElem(pLinkList L,elemtype e,Status(*compare)(elemtype,elemtype))
{ // 对比：

    int i = 1; // int i =0;

    pLinkList p = L; // pLinkList p =L;

    while(p && !compare(p->data,e)) // while(p)

    { // { i++;

        i++; // if(compare(p->next,e))

        p = p->next; // return i;

    } // p = p->next;

    if(p) // }

        return i; // return 0;

    return 0;
}

/*在不带头结点的单链表中第i个位置之前插入元素e*/
//一下是《数据结构算法解析》高一凡著，清华出版 31页原程序

//发现错误没？

Status ListInsert(pLinkList L,int i,elemtype e)
{
    int j = 1;
    pLinkList s,p=L;
    if(i<1)
        return ERROR;
    s = (pLinkList)malloc(sizeof(LinkList));
    s->data = e;
    if(i == 1)//i=1时特殊处理。

    {
        s->next = L;
        L = s;
    }
    else
    {
        while(p&&j<i-1) //寻找第i-1个结点

        {
            j++;
            p = p->next;
        }
        if(!p)
            return ERROR;
        s->next = p->next;
        p->next = s;
    }
    return OK;
}
/*逻辑没问题，问题出在我们新手使用指针都很容易忽视的问题，就是存在内存泄漏的隐患！
看来编书人也忽视了，当i大于表长加1时，直接return返回函数了，别忘了我们的指针s已经指向了一块分配过大小的内存上，
函数结束s的生命周期结束了，但是那块分配过的内存却与世长辞了。
解决办法很简单，在执行return ERROR;之前先执行free(s)就可以了，或者干脆在真要插入结点了之前建立新节点。*/