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

/**
* 含头节点单链表定义及基本操作 
*/

//基本操作函数用到的状态码 
#define TRUE 1;
#define FALSE 0;
#define OK 1;
#define ERROR 0;
#define INFEASIBLE -1;  //当不可行时 
const int OVERFLOW = -2;    //当溢出时 

//Status是新定义的一种函数返回值类型，其值为int型，意义为函数结果 状态码 
typedef int Status; 
//定义一种 数据元素 类型,为表示方便，定义为char型 
typedef char ElemType;
//单链表定义 
typedef struct Lnode {
    ElemType data;        //数据域，这里是char类型变量 
    struct Lnode *next;        //指针域，结构体类型指针 
} Lnode, *LinkList;
/**
* 注：方式 Lnode* p 和 LinkList L 定义出的指针p、L类型等价，
* 但一般用前者定义指向元素节点的指针，用后者定义指向链表的指针 
*/


//基本操作1：单链表初始化 
Status InitList(LinkList *list) {
    (*list)=(LinkList)malloc(sizeof(Lnode));
    (*list)->next=NULL;
    return OK;
}

//基本操作2：判断单链表是否为空
int IsEmpty(LinkList list) {
    if(list->next){
        return FALSE;
    } else {
        return TRUE;
    }
} 

//基本操作3：单链表销毁
Status DestroyList(LinkList *list) {
    Lnode *p; //工作指针
    while(*list){
        p=(*list);
        (*list)=(*list)->next;
        free(p);
    } 
    return OK;
}

//基本操作4：单链表清空 
Status ClearList(LinkList *list) {
    Lnode *p,*q;
    p=(*list)->next; 
    
    //清空结点 
    while(p){
        q=p->next;
        p=NULL;
        p=q;
    }
    
    //清空头结点 
    (*list)->next=NULL;
    return OK;
}

//基本操作5：求单链表长
int GetLength(LinkList list){
    Lnode *p;
    int len=0;
    p = list->next;  //p先指向首元结点 
    while(p){
        len++;
        p=p->next; 
    } 
    return len;
} 

//基本操作6：根据结点索引i获取相应位置元素的内容 
Status GetElem(LinkList list,int i,ElemType *elem) {
    Lnode *p;  //工作指针 
    int j=0;  //计数器 
    p=list->next;  //p指向第一个结点 
    while(p&&j<i){
        p=p->next;
        j++;
    } 
    /**
    *正常情况下此时:j=i(到达目标点，找到)或者p->NULL(到达表尾，仍未找到); 但若i<1，此时i<j=1，也未找到;
    */
    if(!p||i<j) return ERROR;
    *elem=p->data;
    return OK;
}

//基本操作7：查找与目标元素值相同的元素结点，返回元素地址 ，若不存在，返回NULL地址
Lnode* LocateElemAddress(LinkList list,ElemType elem) {
    Lnode *p;
    p=list->next;
    while(p&&p->data!=elem){
        p=p->next;
    }
    return p;
}

//基本操作8：查找与目标元素值相同的元素结点，返回逻辑索引(1~n)，若不存在，返回0
int LocateElemIndex(LinkList list,ElemType elem) {
    Lnode *p;
    int j=1;
    p=list->next;
    while(p&&p->data!=elem) {
        j++;
        p=p->next;
    }
    if(p) return j;
    return 0;
}

//基本操作9：插入新元素数据到指定位置。(i为逻辑位置) 
Status ListInsert(LinkList *list,int i,ElemType elem){
    if(i<1) return ERROR; //插入位置序号小于1 
    Lnode *p;
    int j=0;  //计数器
    p=*list;
    //先找到第i-1个结点 
    while(p&&j<i-1){ 
        j++;
        p=p->next;
    } 
    //这里正常情况，j=i-1,p指向第i-1个结点；否则，j=表长+1,p->NULL 
    
    if(!p) return ERROR;
    
    //构造新结点 
    Lnode *new_node;
    new_node=(Lnode*)malloc(sizeof(Lnode));
    new_node->data= elem;
    //插入到链表 
    new_node->next=p->next;
    p->next=new_node;
    return OK;
} 

//基本操作10：删除链表第i个结点，被删除的结点数据保存在实参elem 
Status ListDelete(LinkList *list,int i,ElemType *elem) {
    Lnode *p,*q;
    int j=0;
    p=*list;
    while(p->next&&j<i-1){
        p=p->next;
        j++;
    }
    if(!(p->next)||j>i-1) return ERROR;  //删除位置不合理
    
    q=p->next; //q指向被删除的结点 
    
    //连接链表
    p->next=p->next->next;  //或者：p->next=q->next;
    
    //保存删除结点的数据
    *elem=q->data;
    
    //释放内存
    free(q);
    return OK;
}



//基本操作11：头插法建立链表，假设我们的数据保存在ElemType类型的数组中(且头结点已建立)。 
Status CreateList_H(LinkList *list,ElemType arrData[],int length) {
    int j;
    for(j=length-1;j>=0;j--){
        //新建结点 
        Lnode *node;
        node=(Lnode*)malloc(sizeof(Lnode));
        node->data=arrData[j];
        node->next=NULL;
        //插入为1号结点 
        node->next=(*list)->next;
        (*list)->next=node;
    }
    return OK;
}

//基本操作12：尾插法建立链表。 
Status CreateList_R(LinkList *list,ElemType arrData[],int length) {
    int j;
    Lnode *r;    //尾指针
    r=*list;
    for(j=0;j<length;j++) {
        Lnode *node;
        node=(Lnode*)malloc(sizeof(Lnode));
        node->data=arrData[j];
        node->next=NULL;
        
        r->next=node;  //node插入到表尾 
        r=node;  //r指向尾结点 
    }
    return OK; 
} 

//基本操作13：链表元素遍历输出  
Status ListTraverse(LinkList list) {
    Lnode *p;
    p=list;
    int j=0;
    printf("逻辑索引：    结点数据：\n");
    while(p->next){
        j++;
        p=p->next;
        printf(" %d          %c\n",j,p->data);
    }
    return OK;
}


int main(void){
    //定义一个链表(用指针list1表示一个链表) 
    LinkList list1;
    
    //链表初始化 
    Status initResultCode=InitList(&list1);
    printf("list1初始化结果：%d\n",initResultCode); 
    
    //给链表添加结点 (下面将用函数实现：头插法、尾插法) 
    //结点初始化
    Lnode *node1,*node2,*node3;
    node1=(Lnode*)malloc(sizeof(Lnode));
    node2=(Lnode*)malloc(sizeof(Lnode));
    node3=(Lnode*)malloc(sizeof(Lnode));
    node1->data='Y';
    node2->data='C';
    node3->data='L';
    node1->next=NULL;
    node2->next=NULL;
    node3->next=NULL;
    //结点连接 
    list1->next=node1;
    node1->next=node2;
    node2->next=node3;
    node3->next=NULL;
    //打印初始结点 
    printf("结点1的值：%c\n",list1->next->data); 
    printf("结点2的值：%c\n",list1->next->next->data); 
    printf("结点3的值：%c\n",list1->next->next->next->data); 
    
    
    //为空？
    /*
    int isNull=IsEmpty(list1); 
    printf("为空？：%d\n",isNull);
    */
    
    //销毁
    /*
    Status destroyResultCode = DestroyList(&list1); 
    printf("销毁结果状态码为：%d\n",destroyResultCode); //1 
    //测试 
    //printf("销毁后结点1的值：%c\n",list1->next->data); //Nothing
    */
    
    //清空
    /* 
    Status clearResultCode = ClearList(&list1);
    //测试 
    printf("清空结果状态码为%d\n",clearResultCode); //1 
    //printf("清空后结点1的值：%c\n",list1->next->data); //Nothing
    */ 
    
    
    //获得表长
    /*
    int listLength = GetLength(list1);
    printf("表长：%d\n",listLength); 
    */
    
    //用 中间元素elemx 保存索引到的元素的值
    /*
    ElemType elemx;
    Status getElemResult = GetElem(list1,3,&elemx);
    printf("得到元素？：%d\n",getElemResult);
    printf("得到元素值：%c\n",elemx);
    */
    
    
    //查找元素结点，返回元素地址
    /*
    ElemType elemTarget1='L';
    Lnode *address = LocateElemAddress(list1,elemTarget1); 
    printf("查找到元素的地址：0x%p\n",address);
    */
    
    
    //查找元素结点，返回元素逻辑索引
    /*
    ElemType elemTarget2='L';
    int index=LocateElemIndex(list1,elemTarget2);
    printf("查找到元素的索引：%d\n",index);
    */
    
    
    //插入
    /* 
    ElemType elemInserted='T';
    Status insertResultCode = ListInsert(&list1,2,elemInserted);
    printf("插入结果状态码：%d\n",insertResultCode);
    //遍历测试 
    ListTraverse(list1);
    */ 
    
    
    //删除结点，保存到删除的数据
    /*
    ElemType deletedElem;
    Status deleteResultCode=ListDelete(&list1,2,&deletedElem);
    printf("删除结果状态码：%d\n",deleteResultCode);
    printf("被删除结点的数据：%c\n",deletedElem);
    //遍历测试 
    ListTraverse(list1);
    */
    
    
    
    /**
    * 链表的建立：头插法、尾插法。 
    */ 
    //产生数据并保存到数组 
    ElemType data1='A',data2='B',data3='C',data4='D',data5='E',data6='F';
    ElemType waitInserted[]={
        data1,
        data2,
        data3,
        data4,
        data5,
        data6,
    };
    //获得数组长度 
    int arrLength=sizeof(waitInserted)/sizeof(waitInserted[0]);
    
    //头插法建立链表 
    /* 
    LinkList list2;        //定义新链表 
    InitList(&list2);    //链表初始化，建立头结点 
    //由数组数据建立链表 
    Status createListResult1 = CreateList_H(&list2,waitInserted,arrLength); 
    printf("建表结果状态码：%d\n",createListResult1);
    //遍历测试 
    ListTraverse(list2);
    */ 
    
    //尾插法建立链表 
    /*
    LinkList list3;        //定义新链表 
    InitList(&list3);    //链表初始化，建立头结点 
    //由数组数据建立链表 
    Status createListResult2 = CreateList_R(&list3,waitInserted,arrLength); 
    printf("建表结果状态码：%d\n",createListResult2);
    //遍历测试 
    ListTraverse(list3);
    */
    
    printf("\nEND!");
    return 0;
}