链表练习

用链表实现简单的一串数，并进行操作

进行各种增删改查
逆向打印
不通过遍历来删除一个非尾节点
不通过遍历在一个借点钱插入一个节点
通过单链表实现约瑟夫环
逆置/反转单链表

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//定义一个类
typedef struct SListNode
{
    int data;
    struct SListNode *pNext;
}SList;
//初始化头部
void Init(SList **pphead)
{
    *pphead = NULL;
}
//输出链表
void Print(SList *pHead)
{
    assert(pHead);
    if(pHead == NULL)
    {
        printf("链表为空\n");
        return;
    }
    while(pHead != NULL)
    {
        printf("%d -> ",pHead->data);
        pHead = pHead->pNext;
    }
    printf("NULL\n");
}
//尾插
void SListPushBack(SList **ppHead, int data)
{
    SList *pNode; 
    SList *pNew = (SList *)malloc(sizeof(SList));
    if(*ppHead == NULL)
    {
        *ppHead = pNew;
        pNew->data = data;
        pNew->pNext = NULL;
        return;
    }
    pNode = *ppHead;
    while(pNode->pNext != NULL)
    {
        pNode = pNode->pNext;
    }
    pNode->pNext = pNew;
    pNew->data = data;
    pNew->pNext = NULL;
}
//头部插入
void SListPushFront(SList **ppHead, int data)
{
    SList *pNew = (SList *)malloc(sizeof(SList));
    if(*ppHead == NULL)
    {
        *ppHead = pNew;
        pNew->data = data;
        pNew->pNext = NULL;
        return;
    }
    pNew->pNext = *ppHead;
    pNew->data = data;
    *ppHead = pNew;
}
//尾删
void SListPopBack(SList **ppHead)
{
    SList *pHead = *ppHead;
    SList *pNode;
    if(*ppHead == NULL)
    {
        printf("链表为空\n");
        return;
    }
    if(pHead->pNext == NULL)
    {
        free(pHead);
        *ppHead = NULL;
        return;
    }
    while(pHead->pNext != NULL)
    {
        pNode = pHead;
        pHead = pHead->pNext;
    }
    free(pHead);
    pNode->pNext = NULL;
}
//头删
void SListPopFront(SList **ppHead)
{
    SList *pHead = *ppHead;
    if(pHead->pNext == NULL)
    {
        free(pHead);
        *ppHead = NULL;
        return;
    }
    *ppHead = pHead->pNext;
    free(pHead);
}
//随机插
void SListInsert(SList **ppHead, int x, int data)
{
    SList *pHead;
    SList *pNew = (SList *)malloc(sizeof(SList));
    pHead = *ppHead;
    if(pHead->data == x)
    {
        pNew->pNext = pHead;
        pNew->data = data;
        *ppHead = pNew;
        return;
    }
    while(pHead->pNext->data != x)
    {
        pHead = pHead->pNext;
    }
    pNew->pNext = pHead->pNext;
    pHead->pNext = pNew;
    pNew->data = data;
}
//按值删除所有
void SListRemoveAll(SList **ppHead, int data)
{
    SList *pNode = *ppHead;
    SList *pNode1;
    while(pNode->pNext != NULL)
    {
        if(pNode->pNext->data == data)
        {
            pNode1 = pNode->pNext;
            pNode->pNext = pNode1->pNext;
            free(pNode1);
        }else
        {
            pNode = pNode->pNext;
        }
    }
    if((*ppHead)->data == data)
    {
        SListPopFront(ppHead);
    }
}
//查找
SList *SListFind(SList *pHead, int data)
{
    SList *pNode = pHead;
    while(pNode != NULL)
    {
        if(pNode->data == data)
        {
            return pNode;
        }
        pNode = pNode->pNext;
    }
    return NULL;
}
//销毁
void SListDestroy(SList **ppHead)
{
    SList *pNode;
    assert(ppHead);
    while(*ppHead != NULL)
    {
        pNode = *ppHead;
        *ppHead = (*ppHead)->pNext;
        free(pNode);
    }
}

• 不通过遍历来删除一个非尾节点

//删除一个无头单链表的非尾节点（不能遍历链表）
void DelSList(SList **ppHead,int data)
{
    SList *pHead = *ppHead;
    assert(ppHead);
    while(pHead->data != data)
    {
        pHead = pHead->pNext;
    }
    while(pHead->pNext->pNext != NULL)
    {
        pHead->data = pHead->pNext->data;
        pHead = pHead->pNext;
    }
    pHead->data = pHead->pNext->data;
    free(pHead->pNext);
    pHead->pNext = NULL;
}

• 反转链表

//反转链表
void SListRever(SList **ppHead)
{
    SList *p1,*p2,*p3;
    assert(ppHead);
    p1 = NULL;
    p2 = *ppHead;
    p3 = p2->pNext;
    while(p2 != NULL)
    {
        p2->pNext = p1;
        p1 = p2;
        p2 = p3;
        if(p3 != NULL)
        {
            p3 = p3->pNext;
        }
    }
    *ppHead = p1;
}

• 不通过遍历在一个借点钱插入一个节点

//在无头单链表的一个节点前插入一个节点（不能遍历链表）
void InsertNoFirstNode(SList **ppPos, int data)
{
    SList *pPos = *ppPos;
    SList *pNode;
    assert(ppPos);
    if(*ppPos == NULL)
    {
        SListPushBack(ppPos, data);
        return;
    }
    pNode = (SList *)malloc(sizeof(SList));
    pNode->data = data;
    pNode->pNext = NULL;

    pNode->pNext = pPos->pNext;
    pPos->pNext = pNode;
    pNode->data = pPos->data;
    pPos->data = data;
}

• 单链表实现约瑟夫环

//单链表实现约瑟夫环
void SListJosephCircle(SList **ppHead, int n)
{
    SList *pHead = *ppHead;
    SList *pNode;
    int i;
    while(pHead->pNext != NULL)
    {
        pHead = pHead->pNext;
    }
    pHead->pNext = *ppHead;
    pHead = *ppHead;
    while(pHead->pNext != pHead)
    {
        i = n;
        while((--i)>0)
        {
            pNode = pHead;
            pHead = pHead->pNext;
        }

        pNode->pNext = pHead->pNext;
        free(pHead);

        pHead = pNode->pNext;
    }
    pHead->pNext = NULL;
    *ppHead = pHead;
}

• 逆向打印

//逆向打印链表
void PrintFail(SList *pHead)
{
    if(pHead == NULL)
    {
        return;
    }
    else
    {
        PrintFail(pHead->pNext);
        printf("->%d",pHead->data);

    }
}

• 主函数部分

int main()
{
    SList *pHead;
    SList *pNode;
    //初始化头部
    Init(&pHead);
    //尾部插入
    SListPushBack(&pHead, 1);
    SListPushBack(&pHead, 2);
    SListPushBack(&pHead, 3);
    //头部插入
    SListPushFront(&pHead, 5);
    SListPushFront(&pHead, 6);
    SListPushFront(&pHead, 8);
    //尾删
    SListPopBack(&pHead);
    //头删
    SListPopFront(&pHead);
    //插入
    SListInsert(&pHead, 5, 4);
    SListInsert(&pHead, 6, 2);
    SListInsert(&pHead, 2, 8);


    //按值删除所有
    //SListRemoveAll(&pHead, 2);
    //SListRemoveAll(&pHead, 8);
    //查找
    pNode = SListFind(pHead, 6);
    //printf("%d\n",pNode->data);


    //销毁
    //SListDestroy(&pHead);

    //删除一个无头单链表的非尾节点（不能遍历链表）
    DelSList(&pHead,1);

    //在无头单链表的一个节点前插入一个节点（不能遍历链表）
    InsertNoFirstNode(&pNode, 9);

    //翻转链表
    //SListRever(&pHead);

    //单链表实现约瑟夫环
    ////SListJosephCircle(&pHead,3);

    //输出
    Print(pHead);

    //逆向打印
    PrintFail(pHead);
    return 0;
}

进行链表相关操作，假如感觉很难的话，建议还是多画图，把每个节点的信息都划出来，这样就会很容易理解。

遇到不会的一通乱画，就会其八九了。