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

//初始分配量
#define LIST_SIZE 100

//分配增量
#define LIST_INCREMENT 10

#define ERROR -1

typedef int elemType;

typedef int Status;

//定义静态顺序表
//用‘.’访问变量
typedef struct {
    
    elemType elem[LIST_SIZE];
    int length;
    
}SqList;

//定义动态顺序表
//用‘->’访问变量
typedef struct {
    
    elemType *elem;      //存储空间基地址
    int length;
    int listsize;
    
}MutableSqList;

//结点和单链表的定义
typedef struct LNode{
    
    elemType data;               //数据域
    struct LNode *next;     //指针域
    
}LNode, *LinkList;

//双向链表的定义
typedef struct DulNode{
    
    elemType data;               //数据域
    struct DulNode *prior;  //指向前驱的指针
    struct DulNode *next;   //指向后继的指针
    
}DulNode, *DulLinkList;

//初始化动态顺序表
int initList(MutableSqList *L);

//在顺序表中查找某元素，若没有返回-1，若有则返回当前下标
int locateElem(SqList L, elemType x);

//顺序表插入元素
Status listInsert_musq(MutableSqList *L, int i, elemType e);

//顺序表删除某个元素，并将其返回
Status listDelete(MutableSqList *L, int i, elemType *e);

//初始化单链表
LinkList initLinkList(LNode *L);

//遍历单链表
int printLinkList(LNode *L);

//单链表中取第i个数据
Status getElem(LNode *L, int i, elemType *e);

//单链表中插入数据元素
Status listInsert_ln(LNode *L, int i, elemType e);

//在单链表中删除某一元素
Status listDelete_ln(LNode *L, int i, elemType *e);

//重置为新表
Status listClear_ln(LNode *L);

//求链表长度
int lengthLinkList(LNode *L);

//构造单链表的两个方法：头插法和尾插法。其中尾插法又分为无头结点以及带头结点
//头插法
LinkList listCreate_ln_front(LNode *L);

//尾插法--无头结点
LinkList listCreate_ln_latter_no(LNode *L);

//尾插法--带头结点
LinkList listCreate_ln_latter_yes(LNode *L);

#include "ListAPI.h"

int initList(MutableSqList *L) {
    
    L -> elem = (int *)malloc(LIST_SIZE * sizeof(int));
    
    if (!L -> elem) {
        return  ERROR;
    }
    
    L -> length = 0;
    L -> listsize = LIST_SIZE;
    
    return 0;
}

int locateElem(SqList L, elemType x) {
    
    int i = 0;
    
    while (i <= L.length && L.elem[i] != x) {
        i++;
    }
    
    if (i > L.length) {
        return ERROR;
    } else
        return i;
    
}

Status listInsert_musq(MutableSqList *L, int i, elemType e) {
    //在线性表第i个位置插入新元素e
    
    //检查插入位置是否合法
    if (i < 1 || i > L ->length) {
        return ERROR;
    }
    
    elemType *q = &L -> elem[i - 1];
    elemType *p = &L -> elem[L -> length - 1];
    
    //元素右移
    for (; p >= q; --p) {
        *(p + 1) = *p;
    }
    
    *q = e;
    ++L -> length;//表长加一
    
    if (L -> length > L -> listsize) {
        return ERROR;
    }
    
    return 1;
}

Status listDelete(MutableSqList *L, int i, elemType *e) {
    
    if (i < 1 || i > L -> length) {
        return ERROR;
    }
    
    elemType *p = &L -> elem[i - 1];
    e = p;
    elemType *q = &L -> elem[L -> length - 1];
    
    for (++p; p <= q; --q) {
        *(p - 1) = *p;
    }
    
    --L -> length;
    
    return *e;
}

LinkList initLinkList(LNode *L) {
    
    L = (LNode *)malloc(sizeof(LNode));
    if (!L) {
        printf("Error");
    }
    (L) -> next = NULL;
    return L;
}

Status getElem(LNode *L, int i, elemType *e){
    //L是带头结点链表的头指针，e为取得的元素
    
    LNode *p = L -> next;
    int j = 1;//计数器
    
    while (p && j < i) {
        p = p -> next;
        ++j;
    }
    
    if (!p || j > i) {
        return ERROR;
    }
    
    e = &p -> data;
    
    return *e;
}

Status listInsert_ln(LNode *L, int i, elemType e) {
    //L是带头结点链表的头指针，在第i个结点之前插入新的元素
    //此算法为后插结点
    
    LNode *p = L;
    int j = 0;
    
    while (p && j < i) {
        p = p -> next;
        ++j;
    }
    
    if (!p || j > i) {
        return ERROR;
    }
    
    //建立新的结点
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (!s) {
        return ERROR;
    }
    s -> data = e;  //建立新的结点
    s -> next = p -> next;
    //“-> next”在赋值号右侧出现，可理解为指针域
    //“-> next”在赋值号左侧出现，可理解为地址
    p -> next = s;
    
    /**
     *  此算法为前插结点
     
     LNode *q = L;
     while (q -> next < p) {
     q = q -> next;
     }
     s -> next = q -> next;
     q -> next = s;
     
     */
    
    
    return 0;
}

Status listDelete_ln(LNode *L, int i, elemType *e) {
    //L是带头结点链表的头指针，在第i个结点之前删除元素，并将删除元素返回
    
    LNode *p = L;
    int j = 0;
    
    while (p -> next && j < i-1) {
        p = p -> next;
        ++j;
    }
    
    if (!(p -> next) || j > i-1) {
        return ERROR;
    }
    
    LNode *q = p -> next;
    p -> next = q -> next;
    *e = q -> data;
    free(q);
    
    return *e;
}

Status listClear_ln(LNode *L) {
    
    while ((L) -> next) {
        LNode *p = (L) -> next;
        (L) -> next = p -> next;
        free(p);
    }
    
    return 0;
}

LinkList listCreate_ln_front(LNode *L) {
    //从表尾到表头逆向建立单链表L，每次均在头结点之后插入元素
    LNode *s;elemType x;
    L=(LNode *)malloc(sizeof(LNode));  //创建头结点
    L->next=NULL;  //初始为空链表
    scanf("%c", &x);  //输入结点的值
    while(x!='\n') {  //输入 9999 表示结束
        s=(LNode*)malloc(sizeof(LNode) );  //创建新结点
        s->data=x;
        s->next=L->next;
        L->next=s;  //将新结点插入表中，L为头指针
        scanf ("%c", &x);
    }  //while 结束
    return L;
}

LinkList listCreate_ln_latter_no(LNode *L) {
    //无头结点的单链表
    LNode *L = NULL;
    LNode *s, *r = NULL;
    int x;
    
    while ((scanf("%d", &x))) {
        
        s = (LNode *)malloc(sizeof(LNode));
        s -> data = x;
        
        if (L == NULL) {
            L = s;
        } else {
            L -> next = s;
        }
        
        r = s;
    }
    
    if (r != NULL) {
        r -> next = NULL;//将最后一个结点的指针域设为空
    }
    
    return L;
}

LinkList listCreate_ln_latter_yes(LNode *L) {
    //有头结点的单链表
    
    //从表头到表尾正向建立单链表L,每次均在表尾插入元素
    elemType x;  // 设元素类型为整型
    L=(LinkList)malloc(sizeof(LNode));
    LNode *s, *r=L;  //r 为表尾指针
    scanf ("%c", &x);  //输入结点的值
    while (x!='\n') {  //输入 9999 表示结束
        s=(LNode *)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;  //r指向新的表尾结点
        scanf ("%c", &x);
    }
    r->next = NULL;  //尾结点指针置空
    return L;

}

int printLinkList(LNode *L) {
     LNode *p = L -> next;
    while (p != NULL) {
        printf("%d\t", p -> data);
        p = p -> next;
    }
    printf("\n");
}

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

#include "ListAPI.h"
int main(int argc, const char * argv[]) {
	//以初始化单链表为例
	LNode *L;
	...
	...
	...
	return 0;
	//在运行插入删除操作时要手动管理链表长度
}