数据结构与算法④(第二章下)链表概念+单链表的实现

 
#pragma once
 
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int SLNDataType;
 
typedef struct SlistNode          //single单一的  node节点
{
    SLNDataType data;
    struct SlistNode* next;
}SLNode;
 
void SListPrint(SLNode* phead);
void SListPushBack(SLNode** pphead, SLNDataType x);
void SListPushFront(SLNode** pphead, SLNDataType x);
SLNode* CreateNewNode(SLNDataType x);
void SListPopBack(SLNode** pphead);
void SListPopFront(SLNode** pphead);
SLNode* SListFind(SLNode* phead, SLNDataType x);
void SListInsert(SLNode** pphead, SLNode* pos, SLNDataType x);
void SListInsertAfter(SLNode* pos, SLNDataType x);
void SListEarse(SLNode** pphead, SLNode* pos);
void SListEarseAfter(SLNode* pos);
void SListDestroy(SLNode** pphead);

 
#include"SList.h"
 
void SListPrint(SLNode* phead)
{
    SLNode* cur = phead;
    while (cur != NULL)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}
 
void SListPushBack(SLNode** pphead, SLNDataType x)
{
    SLNode* NewNode = CreateNewNode(x);
 
    if (*pphead == NULL)
    {
        *pphead = NewNode;
    }
    else
    {
        SLNode* tail = *pphead;//tail 尾巴
        while (tail->next != NULL)//找到尾节点
        {
            tail = tail->next;
        }
        tail->next = NewNode;
    }
}
 
SLNode* CreateNewNode(SLNDataType x)
{
    SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));
    if (NewNode == NULL)
    {
        printf("malloc failed!\n");
        exit(-1);
    }
    NewNode->data = x;
    NewNode->next = NULL;
    return NewNode;
}
 
void SListPushFront(SLNode** pphead, SLNDataType x)
{
    SLNode* NewNode = CreateNewNode(x);
 
    NewNode->next = *pphead;
    *pphead = NewNode;
}
 
void SListPopBack(SLNode** pphead)
{
    assert(*pphead != NULL);
    if ((*pphead)->next == NULL)//如果只有一个节点
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        SLNode* tail = *pphead;
        while (tail->next->next)
        {
            tail = tail->next;
        }
        free(tail->next);
        tail->next = NULL;
    }
}
 
void SListPopFront(SLNode** pphead)
{
    assert(*pphead != NULL);
 
    SLNode* begin = *pphead;
    *pphead = (*pphead)->next;
    free(begin);
    begin = NULL;
}
 
SLNode* SListFind(SLNode* phead, SLNDataType x)
{
    SLNode* cur = phead;
    while (cur != NULL)
    {
        if (cur->data == x)
        {
            return cur;
        }
        else
        {
            cur = cur->next;
        }
    }
    return NULL;
}
 
void SListInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{
    SLNode* NewNode = CreateNewNode(x);
    if (*pphead == pos)
    {
        NewNode->next = *pphead;
        *pphead = NewNode;
    }
    else
    {
        SLNode* posPrev = *pphead;
        while (posPrev->next != pos)
        {
            posPrev = posPrev->next;
        }
        posPrev->next = NewNode;
        NewNode->next = pos;
    }
}
 
void SListInsertAfter(SLNode* pos, SLNDataType x)
{
    assert(pos != NULL);
    SLNode* NewNode = CreateNewNode(x);
    NewNode->next = pos->next;
    pos->next = NewNode;
    //和前面对比，单链表的缺陷是要找pos的前一个要从头往后找
}
 
void SListEarse(SLNode** pphead, SLNode* pos)
{
    assert(*pphead != NULL);
    assert(pos != NULL);
    if (*pphead == pos)//如果是头删
    {
        *pphead = pos->next;
        free(pos);
        pos = NULL;
    }
    else
    {
        SLNode* posPrev = *pphead;
        while (posPrev->next != pos)
        {
            posPrev = posPrev->next;
        }
        posPrev->next = pos->next;
        free(pos);
        pos = NULL;//可以不写，形参不会改变实参，这个野指针会被栈帧销毁，但是个好习惯emm
    }
}
 
void SListEarseAfter(SLNode* pos)
{
    //1 2 3 4
    assert(pos != NULL);
    assert(pos->next != NULL);
    SLNode* posAfter= pos->next;
    pos->next = posAfter->next;
    free(posAfter);
    posAfter = NULL;//可以不写，形参不会改变实参，这个野指针会被栈帧销毁
}
 
void SListDestroy(SLNode** pphead)
{
    assert(pphead);
    SLNode* cur = *pphead;
    while (cur)
    {
        SLNode* next = cur->next;
        free(cur);
        cur = next;
    }
    *pphead = NULL;
}

 
#pragma once
 
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int SLNDataType;
 
typedef struct SlistNode          //single单一的  node节点
{
    SLNDataType data;
    struct SlistNode* next;
}SLNode;
 
void SListPrint(SLNode* phead);
void SListPushBack(SLNode** pphead, SLNDataType x);
void SListPushFront(SLNode** pphead, SLNDataType x);
SLNode* CreateNewNode(SLNDataType x);
void SListPopBack(SLNode** pphead);
void SListPopFront(SLNode** pphead);
SLNode* SListFind(SLNode* phead, SLNDataType x);
void SListInsert(SLNode** pphead, SLNode* pos, SLNDataType x);
void SListInsertAfter(SLNode* pos, SLNDataType x);
void SListEarse(SLNode** pphead, SLNode* pos);
void SListEarseAfter(SLNode* pos);
void SListDestroy(SLNode** pphead);