C/C++数据结构篇Ⅰ---带头节点的单向链表

链表的概念这里就不细说了，我们直接来看基于链表的基本操作。
这里介绍一种比较常用的链表->带头结点的单向链表。
包括链表的创建、打印、增、删、改、查。
一般建立链表时，需要几个结点我们就创建几个，但如果在我们实际需要的结点最前面再加一个首结点(假的首结点)，这样在之后的操作中就会方便很多。

#include 

using namespace std;

#define OPERAEALL 1 //操作所有
#define OPERAEONE 0 //操作一次

typedef int custom; //结点数据域类型

//链表结点
typedef struct listnode
{
    custom elem; //数据域
    struct listnode *next; //指向下一个结点
} NODE;

//链表头结点
typedef struct listhead
{
    int number; //有效结点数量
    NODE *first; //指向第一个有效结点
    NODE *last; //指向最后一个有效结点
} HEAD;

HEAD * create_head_node(); //创建头节点
bool printf_list(HEAD *htr); //打印一个链表
HEAD * add_node(HEAD *htr); //增加结点
HEAD * delete_node(HEAD *htr); //删除结点
HEAD * modifly_node(HEAD *htr); //修改结点
HEAD * find_node(HEAD *htr); //查找结点

int main()
{
    
    return 0;
}

HEAD * create_head_node()
{
    HEAD *htr = new HEAD;
    NODE *ntr = new NODE; //为了方便之后的操作，创建头结点的时候，就让他指向一个无效链表结点，这个结点的数据域是无效的
                            //它是指向链表真正的第一个结点的结点。
    htr->first = ntr;
    htr->last = ntr;
    htr->number = 0; //指向的是无效结点，所以有效结点数还是0

    ntr->elem = -1;
    ntr->next = nullptr;
    return htr;
}

bool printf_list(HEAD *htr)
{
    if((nullptr == htr) || (0 == htr->number))
        return false;
    NODE *ntr = htr->first->next;
    cout << "list:" << endl;
    while(ntr){
        if(ntr->next)
            cout << ntr->elem <<"->";
        else
            cout << ntr->elem;
        ntr = ntr->next;
    }
    cout << endl;
    return true;
}


HEAD * add_node(HEAD *htr)
{
    if(nullptr == htr)
        return htr;
    int flag = 0;
    int num;
    while(1){
        cout << "输入1增加结点、输入0结束增加" << endl;
        cin >> flag;
        if(0 == flag)
            break;
        cout << "输入增加结点的数据域" << endl;
        cin >> num;
        NODE *ntr = new NODE;
        ntr->elem = num;
        ntr->next = nullptr;

        htr->last->next = ntr;
        htr->last = ntr;
        ++ htr->number; //注意更新头节点信息
    }
    return htr;
}

HEAD * delete_node(HEAD *htr)
{
    if((nullptr == htr) || (0 == htr->number))
        return htr;
    
    int flag = 0;
    int num = 0;
    while(1){
        cout << "输入0结束删除，输入其他进行删除操作" << endl;
        cin >> num;
        if(0 == num)
            return htr;
        cout << "请输入需要删除结点的数据域" << endl;
        cin >> num;

        cout << "输入1删除全部，输入0删除一个" << endl;
        cin >> flag ;
        if(1 == flag)
            flag = OPERAEALL;
        else if(0 == flag)
            flag = OPERAEONE;

        //开始删除
        NODE *ltr = htr->first;
        NODE *rtr = ltr->next;
        
        while(rtr){
            if((rtr == htr->last) && (rtr->elem == num)){   //最后一个结点
                htr->last = ltr;
                ltr->next = nullptr;
                delete rtr;
                rtr = nullptr; //防止野指针
                -- htr->number;
                break;
            } 
            else if(rtr->elem == num){ //中间结点
                ltr->next = rtr->next;
                rtr->next = nullptr;
                delete rtr;
                rtr = ltr->next;
                -- htr->number;
                if(OPERAEONE == flag)
                    break;
            }
            else{ //此结点不是目标结点，辅助指针下移一位
                ltr = rtr;
                rtr = rtr->next;
            }
        }
        cout << "删除后链表为：" << endl;
        printf_list(htr);
    }
    return htr;
}

HEAD * modifly_node(HEAD *htr)
{
    if((nullptr == htr) || (0 == htr->number))
        return htr;
    
    int num_old = 0;
    int num_new = 0;
    int flag = 0;

    while(1){
        cout << "输入0结束修改，输入其他进行修改" << endl;
        cin >> flag;
        if(0 == flag)
            break;
        cout << "输入需要更改的数据域" << endl;
        cin >> num_old;
        cout << "输入更改为的数据域" << endl;
        cin >> num_new;
        cout << "输入1全部更改，输入其他只改一个" << endl;
        cin >> flag;
        if(1 == flag)
            flag = OPERAEALL;
        else
            flag = OPERAEONE;

        //开始修改
        NODE *rtr = htr->first->next;    

        while(rtr){
            if(rtr->elem == num_old){
                rtr->elem = num_new;
                if(OPERAEONE == flag)
                    break;
            }
            rtr = rtr->next;
        }
        cout << "修改后链表为：" << endl;
        printf_list(htr);
    }
    return htr;
}

HEAD * find_node(HEAD *htr)
{
    if((nullptr == htr) || (0 == htr->number))
        return htr;
    
    int flag = 0;
    int find_num = 0;
    int num = 0;

    NODE *rtr = htr->first->next;
    while(1){
        cout << "输入0结束查找，输入其他进行查找" << endl;
        cin >> flag;
        if(0 == flag)
            return htr;
        cout << "输入你要查找的数据域" << endl;
        cin >> num;

        while(rtr){
            if(rtr->elem == num)
                ++ find_num;
            rtr = rtr->next;
        }
        cout << "找到了" << find_num << "个这样的结点" << endl;
        find_num = 0;
    }
    return htr;
}