数据结构【单链表基本操作】

包含单链表的创建、遍历、反转（指针替换、递归）、排序、插入、删除

// list_2.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include "pch.h"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

using namespace std;

typedef struct  Node
{
    int nData;    //数据域
    Node* pNext;  //指针域 指向下一个与自身类型相同的节点
}*PNODE;

PNODE create_list();  //创建链表
void traverse_list(const PNODE pHead);  //遍历链表
void inversion_list(PNODE pHead); //反转链表
bool isEmpty_list(const PNODE pHead); //判断链表是否为空
PNODE inversion_list2(PNODE pHead);
void insert_list(PNODE pHead, int nPos, int nValue);
int getListLen(const PNODE pHead);
void delete_list(PNODE pHead, int nPos, int * nValue);
void sort_list(PNODE pHead);

//链表插入元素
void insert_list(PNODE pHead, int nPos, int nValue)
{
    int nListLen = getListLen(pHead);
    if (nPos < 1 || nPos > nListLen + 1)
    {
        return;
    }

    int i = 1;
    PNODE pNode = pHead->pNext;
    
    while (nullptr != pNode && i < nPos - 1)
    {
        pNode = pNode->pNext;
        ++i;
    }

    PNODE pInsertNode = (PNODE)malloc(sizeof(Node));
    pInsertNode->nData = nValue;

    PNODE pTempNode = pNode->pNext;
    pNode->pNext = pInsertNode;
    pInsertNode->pNext = pTempNode;
}

//获取链表个数
int getListLen(const PNODE pHead)
{
    int nLen = 0;
    PNODE pNode = pHead->pNext;//计算长度不算头节点
    while (nullptr != pNode)
    {
        pNode = pNode->pNext;
        ++nLen;
    }

    return nLen;
}

//删除链表元素
void delete_list(PNODE pHead, int nPos, int * nValue)
{
    if (isEmpty_list(pHead) || nPos < 1 || nPos > getListLen(pHead))
    {
        return;
    }

    int i = 1;
    PNODE pNode = pHead->pNext;

    while (nullptr != pNode && i < nPos - 1)
    {
        pNode = pNode->pNext;
        ++i;
    }

    PNODE pDeleteNode = pNode->pNext;
    *nValue = pDeleteNode->nData;

    PNODE pTempNode = pDeleteNode->pNext;

    //让链表连起来
    pNode->pNext = pTempNode;

    free(pDeleteNode);
}

//冒泡,只替换数据
void sort_list(PNODE pHead)
{
    //链表为空或者只有一个有效节点不排序
    if (isEmpty_list(pHead) || nullptr == pHead->pNext->pNext)
    {
        return;
    }

    PNODE pNode = pHead->pNext;
    for (; nullptr != pNode; pNode = pNode->pNext)
    {
        PNODE pNode2 = pNode->pNext;
        for (;nullptr != pNode2 && pNode != pNode2; pNode2 = pNode2->pNext)
        {
            if (pNode->nData > pNode2->nData)
            {
                int nValue = pNode->nData;
                pNode->nData = pNode2->nData;
                pNode2->nData = nValue;
            }
        }
    }
}

//递归反转链表
PNODE inversion_list2(PNODE pHead)
{
    if (nullptr == pHead || nullptr == pHead->pNext)
    {
        return pHead;
    }
    else
    {
        PNODE pTemp = inversion_list2(pHead->pNext);
        pHead->pNext->pNext = pHead; // 让最后一个节点指回去，这里形成了链表循环
        pHead->pNext = nullptr; //这里断开后，节点刚好反转

        return pTemp;
    }
}

int main()
{
    PNODE pHead = create_list();
    if (nullptr == pHead)
    {
        exit(-1);
    }

    sort_list(pHead);

    traverse_list(pHead);

    inversion_list(pHead);

    traverse_list(pHead);

    PNODE pTempNode = inversion_list2(pHead->pNext);
    pHead->pNext = pTempNode;
    traverse_list(pHead);

    insert_list(pHead, 6, 66);
    traverse_list(pHead);

    int nDeleteValue = 0;
    delete_list(pHead, 4, &nDeleteValue);

    cout << "删除的元素为：" << nDeleteValue << endl;
    traverse_list(pHead);
}

//创建非循环单向链表
PNODE create_list()
{
    int nNodeLen = 0;
    cout << "请输入创建链表的个数:";
    cin >> nNodeLen;

    if (0 == nNodeLen)
    {
        return nullptr;
    }

    //先创建头节点
    PNODE pHead = (PNODE)malloc(sizeof(Node));
    if (nullptr == pHead)
    {
        return nullptr;
    }
    //让头结点的指针域初始化为空
    pHead->pNext = nullptr;

    //定义临时节点，永远指向最后一个节点
    PNODE pTempNode = pHead;

    for (int i = 1; i <= nNodeLen; i++)
    {
        int nValue = 0;
        printf_s("请输入第%d个节点的值:", i);
        cin >> nValue;

        //创建新节点
        PNODE pNewNode = (PNODE)malloc(sizeof(Node));
        //判断内存是否申请成功
        if (nullptr == pNewNode)
        {
            return nullptr;
        }

        //给节点赋值
        pNewNode->nData = nValue;
        pNewNode->pNext = nullptr;

        //把新节点挂在尾结点上
        pTempNode->pNext = pNewNode;

        //让临时节点指向新的尾结点
        pTempNode = pNewNode;
    }

    return pHead;
}

//遍历链表
void traverse_list(const PNODE pHead)
{
    //先从头节点的指针域获取到首节点
    PNODE pTraverseNode = pHead->pNext;

    while (nullptr != pTraverseNode)
    {
        cout << pTraverseNode->nData;
        cout << "\t";
        //把当前节点的下一个节点地址赋值给pTraverseNode
        pTraverseNode = pTraverseNode->pNext;
    }

    cout << endl;

    return;
}

void inversion_list(PNODE pHead)
{
    if (isEmpty_list(pHead) || nullptr == pHead->pNext->pNext)
    {
        return;
    }

    PNODE pPrevtNode = pHead->pNext;
    PNODE pCurrentNode = pPrevtNode->pNext;
    pPrevtNode->pNext = nullptr;
    
    while (nullptr != pCurrentNode)
    {
        PNODE pTempNode = pCurrentNode->pNext;
        pCurrentNode->pNext = pPrevtNode;

        pPrevtNode = pCurrentNode;
        pCurrentNode = pTempNode;
    }

    pHead->pNext = pPrevtNode;

    return;
}

bool isEmpty_list(const PNODE pHead)
{
    //如果头节点的指针域指向的内容为空，那么就是空链表
    if (nullptr == pHead->pNext)
    {
        return true;
    }

    return false;
}