// Created by 15267 on 2021/9/26.
// 数据结构-单链表的基本操作-尾插法

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

typedef struct LNode{
    int data;
    struct LNode *next;

}LNode,*LinkList;

int length; // 单链表长度
LNode * r;// 定义尾指针
void InitList(LinkList &L); // 初始化链表
bool tailInsert(LinkList &L, int value); // 尾插法
void PrintList(LinkList L); // 遍历
LNode *GetElem(LinkList L, int loc); // 按位获取结点
LNode *LocateElem(LinkList L, int e); // 按值获取结点
bool insert(LinkList &L, int value, int loc); // 按位插入
bool delNode(LinkList &L, int loc); // 按位删除结点

int main(){
    LNode *L;
    InitList(L); // 初始化线性表
    int opt = 0; // 操作
    while(opt != 7){
        int value = -1; // 值初始化
        int loc = -1; // 下标初始化
        printf("请选择你要执行的操作:\n1.尾插\n2.遍历\n3.按位获取节点\n4.按值获取结点\n5.按位插入结点\n6.按位删除结点\n7.退出\n");
        cin >> opt;
        LNode *n;
        switch(opt){
            case 1: //插入
                cin >> value;
                tailInsert(L,value);
                break;
            case 2: //遍历所有元素
                PrintList(L);
                break;
            case 3: //按位获取结点
                cin >> loc;
                n = GetElem(L,loc);
                cout << "获取到的值为:" << n->data << endl;
                break;
            case 4: //按位获取结点
                cin >> value;
                n = LocateElem(L,value);
                if(n != NULL){
                    cout << "获取到的值为:" << n->data << endl;
                }
                break;
            case 5: //按位插入结点
                cin >> value >> loc;
                insert(L,value,loc);
                break;
            case 6: //按位删除结点
                cin >> loc;
                delNode(L,loc);
                break;
        }
    }
    cout << "退出成功";
    return 0;
}

// 初始化链表
void InitList(LinkList &L){
    L = (LNode*) malloc(sizeof (LNode)); // 分配存储空间
    L->next = NULL; // 尾结点初始指向NULL
    r = L; // 令尾指针指向L;
    length = 0; // 链表初始长度为0
}

// 尾插法
bool tailInsert(LinkList &L, int value){
    LNode *v;
    v = (LNode*) malloc(sizeof (LNode));
    if(v == NULL){
        cout << "插入节点失败"<< endl;
        return false;
    }
    r->next = v;
    v->data = value;
    r = v;
    r->next = NULL;
    PrintList(L);
    length ++;
    return true;
}

// 按位获取节点
LNode *GetElem(LinkList L, int loc){
    while(loc --){
        L = L->next;
    }
    return L;
}

// 按位插入结点
bool insert(LinkList &L, int value, int loc){
    LNode *v = (LNode*)malloc(sizeof(LNode));
    if(loc > length + 1){
        cout << "传入下标有误" << endl;
        return false;
    }
    LNode *t = GetElem(L,loc-1); // 获取插入位置的前驱结点
    v->next = t->next;
    t->next = v;
    v->data = value;
    cout << "插入成功"<<endl;
    length ++;
    PrintList(L);
    return true;
}

// 按位删除结点
bool delNode(LinkList &L, int loc){
    if(loc > length){
        cout << "该下标不存在"<< endl;
        return false;
    }
    LNode *n = GetElem(L,loc-1); // 获取要删除结点的前驱结点
    LNode *q = n->next; // 获取要删除的结点
    n->next = q->next; // 将n的后驱改为要删除结点的后驱
    free(q); // 释放存储空间
    cout << "删除成功" << endl;
    PrintList(L);
}

// 按值获取结点
LNode *LocateElem(LinkList L, int e){
    while(L != NULL){
        if(L->data == e){
            return L;
        }
        L = L->next;
    }
    cout<< "没有找到该值" << endl;
    return NULL;
}
// 遍历
void PrintList(LinkList L){
    cout << "遍历的结果为:" <<endl;
    if(L->next != NULL){
        L = L->next;
    }
    while(L != NULL){
        cout << L->data << " ";
        L = L->next;
    }
    cout << endl;
}