数据结构和算法学习记录——线性表之单链表（下）-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁

SLTNode* CreateListNode(SLTDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

void SListPushFront(SLTNode ** pphead,SLTDataType x)
{
    SLTNode * newnode = CreateListNode(x);
 
    newnode->next = *pphead;
    *pphead = newnode;
}

void SListPopBack(SLTNode** pphead)
{
    //第一种情况
    if (*pphead == NULL)
    {
        return;
    }
    //或者-> /*assert(*pphead != NULL);*/
 
    //第二种情况
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
 
    //第三种情况
    else
    {
        SLTNode* prev = NULL;
        SLTNode* tail = *pphead;
        while (tail->next)
        {
            prev = tail;
            tail = tail->next;
        }
        free(tail);
        tail = NULL;
        prev->next = NULL;
    }
}

void SListPopFront(SLTNode ** pphead)
{
    assert(*pphead != NULL);
    
    SLTNode *next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
}

SLTNode* SListFind(SLTNode* phead,SLTDataType x)
{
    SLTNode* cur = phead;
    while(cur)
    {
        if(cur->data == x)
        {
            return cur;
        }
        else
        {
            cur = cur->next;
        }
    }
    return NULL;
}

//假设我们要查找头结点为plist的单链表中数据是2的结点，且不止一个。
SLTNode* pos = SListFind(plist,2);
int i = 1;
while(pos) //判断pos返回的值是否为NULL，为NULL则证明已找不到
{
    printf("第%d个pos结点：%p->%d\n",i++,pos,pos->data);
    pos = SListFind(pos->next,2);//在pos的下一个位置开始查找
}

//以之前的情景为例,我们把找到的2改为20
pos = SListFind(plist,2);
if(pos)
{
    pos->data = 20;
}

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    SLTNode* newnode = CreateListNode(x);
    if (*pphead == pos) //当要在第一个位置的前面插入数据时，则为头插
    {
        //用头插的思路来写即可
        newnode->next = *pphead;
        *pphead = newnode;
    }
    else 
    {
        //找到pos的前一个位置
        SLTNode* posPrev = *pphead;
        while (posPrev->next != pos)
        {
            posPrev = posPrev->next;
        }
        posPrev->next = newnode;
        newnode->next = pos;
    }
}

//在pos的后面插入，这个更适合用于单链表，效率也更高一些
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
    SLTNode* newnode = CreateListNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

void SListErase(SLTNode** pphead, SLTNode* pos)
{
    if (*pphead == pos)
    {
        //直接使用头删函数
        SListPopFront(pphead);
    }
    else
    {
        SLTNode* prev = *pphead;
        while (prev->next != pos)//与之前类似，找结点
        {
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

void SListEraseAfter(SLTNode* pos)
{
    assert(pos->next);
 
    SLTNode* next = pos->next;
    pos->next = next->next;
    free(next);
    //next = NULL;
}

void SListDestory(SLTNode** pphead)
{
    assert(pphead);
 
    SLTNode* cur = *pphead;
    while (cur)
    {
        SLTNode* next = cur->next;
        free(cur);
        cur = next;
    }
    *pphead = NULL;
}