//#include <stdio.h>             // c 库
#include <stdlib.h>                //maclloc 库
#include <iostream>                // c++ 库

// 有本句 ，下面cout 前面可以没有  std::
using namespace std;

typedef char ElemType;  //元素数据 以字符型为例


// 定义单链表节点类型
typedef struct LNode {
    ElemType data;   //ElemType 数组，使用动态初始化
    struct LNode* next;
}LNode, * LinkList;


// 1 初始化，创建头节点
bool InitList(LinkList& L) {
    L = (LNode*)malloc(sizeof(LNode));   //申请内存，地址赋给头节点, L带出去指代链表 
    //L=new Lnode;
    L->next = NULL;        // 因为L是指针类型，对内部成员访问采用 L->  
                        // L->next 头节点成员，存放下一个节点的地址，可以代表下一个节点
    return 1;
}


// 增1 头插法建立单链表
bool HeadInsert(LinkList& L) { //  l是对指针的引用
    ElemType x; //输入元素
    LNode* s; //节点类型指针，指向新申请的空间，即新插入的元素

    //输入数据，并插入链表
    cin >> x;

    while (x != 'z') {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;    //新节点的下一个 变为 头节点的下一个
        L->next = s;        //头节点下一个变为新插入的节点

        //输入数据，并插入链表
        cin >> x;
    }
    return L;
}

// 增2 尾插法建立单链表
LinkList TailInsert(LinkList& L) {

    LNode* s, * r = L;
    ElemType x;
    cin >> x;
    while (x != 'z') {
        s = new LNode;
        s->data = x;
        r->next = s;
        r = s;
        cin >> x;
    }
    r->next = NULL;
    return L;
}


//查1 求链表长度
int Length(LinkList L) {

    LNode* p = L;
    int j = 0;
    while (p->next != NULL)
    {
        j++;
        p = p->next;
    }
    return j;
}

//查2 遍历
bool TraveList(LinkList L) {
    LNode* p = L->next; //p 和头节点的next 都指向第一个真节点
    while (p) {
        cout << p->data << " ";
        p = p->next;
    }
    return 1;
}

//查3 按序号查找，返回指针
LNode* GetElem(LinkList L, int j) {
    if (j == 0)
        return L;

    LNode* p = L->next;
    int i = 1;
    while (p && (i < j)) {
        p = p->next;
        i++;
    }
    return p;
}

//查4 按值查找，返回指针
LNode* LocateElem(LinkList L, ElemType e) {
    LNode* p = L->next;
    while (p && (p->data != e))
        p = p->next;
    return p;
}

// 删1 删表
bool DestroyList(LinkList& L) {
    LNode* p;
    while (L->next)
    {
        p = L;
        L = L->next;
        free(p);
    }
    return    1;
}

// 删2 删第i个元素
bool DelElem(LinkList& L, int i, ElemType &c)
{
    LNode* p = GetElem(L, i - 1);    //指针p指向第i-1个元素
    LNode* q = p->next;                //指针q指向第i个元素 ,这指针不能少

    if (p) {
        c = p->next->data;
        p->next = p->next->next;
        free(q);
        return 1;
    }
    else return 0;
}


//改1    位置i前插元素
bool FInsElem(LinkList& L, int i, ElemType& c) {
    LNode* s = new LNode;
    LNode* p = GetElem(L, i-1);

    s->data = c;
    s->next = p->next;
    p->next = s;
    return 1;
}




//改2   位置i后插元素
bool BInsElem(LinkList& L, int i, ElemType& c) {
    LNode* s = new LNode;
    LNode* p = GetElem(L, i - 1);

    s->data = c;
    s->next = p->next;
    p->next = s;

    // cout << s->data << s->next->data;

    ElemType temp;
    temp = s->data;
    s->data = s->next->data;
    s->next->data = temp;

    //cout << s->data << s->next->data;

    return 1;
}



int main()
{
    cout << endl << "输入元素（以z结尾）: " << endl;
    //定义
    LinkList L;
    InitList(L);

    //头插法
    TailInsert(L);



    ////按序号查找
    //int no;
    //cout << endl << "输入要查找的元素的序号: " << endl;
    //cin >> no;
    // 
    //LNode* find = GetElem(L, no);
    //cout << endl;
    //cout << "第" << no << " 个元素是" << find->data << endl;

    ////查值查找
    //char e;
    //cout << endl << "输入要查找的元素: " << endl;
    //cin >> e;
    //LNode* find2 = LocateElem(L, e);
    //cout << "要查找的元素是  " << find2->data;

    //////删除元素
    //int d2;
    //ElemType c;
    //cout << endl << "输入要删除的元素序号：" << endl ;
    //cin >> d2;
    //DelElem(L, d2, c);
    //cout << endl << "删除的元素是：" << c << endl;

    ////  i 位置插入元素 ，i位置后移
    //int in1;
    //ElemType el1;
    //cout << endl << "输入要插入位置和元素" << endl;
    //cin >> in1 >> el1;
    //FInsElem(L, in1,el1);


    //  i 位置前插入元素 ，i位置不变
    int in2;
    ElemType el2;
    cout << endl << "输入要插入位置和元素" << endl;
    cin >> in2 >> el2;
    BInsElem(L, in2, el2);
    

    //求长度
    int l = Length(L);
    cout << endl << "共" << l << "个元素" << endl;
    //输出
    cout << "---------------遍历如下--------------- " << endl;
    TraveList(L);

    ////按值查找   

    ////销毁
    int d1 = DestroyList(L);
    if (d1)
        cout << endl << endl << "SqList has been Destroyed! " << endl;

    //输出
    cout << endl << "---------------遍历如下---------------" << endl;
    TraveList(L);

}