单链表（带头结点）C++面向过程实现

#include<stdio.h>
#include<stdlib.h>

/*
1、带头结点的链表：头节点本身不存元素数据，但头节点的next指针指向第一个节点；
2、若带头结点，则头指针指向头节点（换句话说：头指针等于头节点的地址）。
*/

/*
链表带头结点的优势：
1、第一个位置插入和删除更方便；
2、统一空链表和非空链表的处理：当链表为空时，不带头结点链表的头指针为NULL，
而带头结点链表的头指针仍然为指向节点的指针，无需特殊操作。
*/

typedef struct listNode
{
    //头节点的data数据存链表的长度
    int nodeData;
    struct listNode* nextNode; //Attention nextNode !!! 
}listNode, * singleLinkList;
//listNode强调单个节点，singleLinkList强调链表本身。

bool initLinkList(singleLinkList& myList);

//头插法添加元素
void addAfterHead(singleLinkList& myList, int myData);
//尾插法添加元素
void addAfterTail(singleLinkList& myList, int myData);

//此处的myTarget是位序，是从1开始的，不是从0开始的索引！！！
listNode* getNode(const singleLinkList& myList, int myTarget);

bool insertNode(singleLinkList& myList, int myTarget, int myNodeData);
bool removeNode(singleLinkList& myList, int myTarget, int& myNodeData);

//链表逆序处理
void reverseList(singleLinkList& myList);

//链表元素显示
void displayLinkList(const singleLinkList& myList);

int main()
{
    singleLinkList myListA;
    initLinkList(myListA);
    printf("Add after tail : \n");  
    for(int i = 1; i <= 10; i++)
    {
        addAfterTail(myListA, i*i);
    }
    displayLinkList(myListA);
    
    reverseList(myListA);
    printf("After reversing : \n");
    displayLinkList(myListA);
    
    return 0;
}

bool initLinkList(singleLinkList& myList)
{
    //注意：表达式本身是有值的！！！
    if((myList = (listNode*)(malloc(sizeof(listNode)))))
    {
        myList->nodeData = 0;
        myList->nextNode = NULL;
        myList->nodeData = 0;
        return true;
    }
    else
    {
        myList = NULL;
        printf("Failed to construct !\n");
        return false;
    }
}

listNode* getNode(const singleLinkList& myList, int myTarget)
{
    /*
    可以执行此操作的条件：
    1、目标位序没有超过链表的范围；
    2、若目标位序为头节点，即 myTarget = 0，则返回头节点。
    */
    
    if((0 <= myTarget) && (myTarget <= myList->nodeData))
    {
        listNode* myNode = myList;
        int i = 0;
        while(i != myTarget)
        {
            myNode = myNode->nextNode;
            i += 1;
        }
        
        return myNode;
    }
    else
    {
        printf("Your target is out of range !!!\n");
        return NULL;
    }
}

bool insertNode(singleLinkList& myList, int myTarget, int myNodeData)
{
    /*
    执行插入操作的条件：
    1、目标位置的上一个位置在链表的范围内（包括头指针）;
    2、插入元素后，将链表长度+1。
    */
    if(getNode(myList, myTarget -1))
    {
        listNode* LA;
        initLinkList(LA);
        LA->nextNode = getNode(myList, myTarget -1)->nextNode;
        LA->nodeData = myNodeData;
        getNode(myList, myTarget -1)->nextNode = LA;
        myList->nodeData += 1;
        return true;
    }
    else
    {
        printf("Your target is out of range !!!\n");
        return false;
    }
}

bool removeNode(singleLinkList& myList, int myTarget, int& myNodeData)
{
    /*
    执行删除元素的条件是：
    1、链表不为空；
    2、（且）删除目标的上一个位置在链表范围内（包括头节点）；
    3、执行一次删除操作，链表长度-1。
    */
    if((getNode(myList, myTarget-1)))
    {
        myNodeData = getNode(myList, myTarget-1)->nextNode->nodeData;
        getNode(myList, myTarget-1)->nextNode = getNode(myList, myTarget-1)->nextNode->nextNode;
        free(getNode(myList, myTarget-1));
        myList->nodeData -= 1;
        return true;
    }
    else
    {
        printf("Your target is out of range !!!\n");
        return false;
    }
}

void displayLinkList(const singleLinkList& myList)
{   
    if(myList->nodeData != 0)
    {
        listNode* LA = myList->nextNode;
        int i = 1;
        while(i <= myList->nodeData)
        {
            printf("listNode %d is %d , its address is %d , and its next address is %d .\n", i, LA->nodeData, LA, LA->nextNode);
            LA = LA->nextNode;
            i += 1;
        }
        printf("\n");
    }
    else
    {
        printf("Your linkList is empty !!!\n");
    }
}

void addAfterHead(singleLinkList& myList, int myData)
{
    listNode* myFirstNode;
    initLinkList(myFirstNode);
    myFirstNode->nextNode = myList->nextNode;
    myFirstNode->nodeData = myData;
    myList->nextNode = myFirstNode;
    myList->nodeData += 1;
}

void addAfterTail(singleLinkList& myList, int myData)
{
    listNode* myLastNode;
    initLinkList(myLastNode);
    
    listNode* myNode;
    initLinkList(myNode);
    myNode = myList;
    
    while(myNode->nextNode != NULL)
    {
        myNode = myNode->nextNode;
    }
    myLastNode->nodeData = myData;
    myLastNode->nextNode = NULL;
    myNode->nextNode = myLastNode;
    myList->nodeData += 1;
}

void reverseList(singleLinkList& myList)
{
    if(myList->nodeData > 0)
    {
        listNode* myNode;
        initLinkList(myNode);
    
        myNode = myList->nextNode;
    
        singleLinkList myListA;
        initLinkList(myListA);
    
        int i = 1;
        while(i <= myList-> nodeData)
        {
            //借助头插法可以实现链表逆序
            addAfterHead(myListA, myNode->nodeData);
            myNode = myNode->nextNode;
            i += 1;
        }
        myList = myListA;
    
        free(myNode);
        free(myListA);  
    }
    else
    {
        printf("Your list is empty !!!\n");
        return;
    }   
}