#include<stdio.h>

#define OK 1
#define ERROR 0

typedef int Status;
typedef int ElemType;
typedef struct LinkList
{
    ElemType data;
    struct Node* next; //由于是順序執(zhí)行，所以這里還不能使用簡(jiǎn)化后的類型名
} Node, LinkList, *LinkListPtr;

/**
 * 創(chuàng)建具有n個(gè)結(jié)點(diǎn)的單鏈表
 * 鏈表的結(jié)點(diǎn)是根據(jù)需要一個(gè)一個(gè)動(dòng)態(tài)生成，鏈接到原有的鏈表上，可采用尾插法后頭插法，這里使用頭插法，即插入頭結(jié)點(diǎn)之后成為第一個(gè)結(jié)點(diǎn)
 */
LinkListPtr create_head(int n)
{
    /*
        返回類型為指針類型，這里就不能用參數(shù)來(lái)放返回結(jié)果了，
        因?yàn)殒湵淼氖椎刂肥窃趧?chuàng)建的時(shí)候動(dòng)態(tài)分配的，
        在main函數(shù)中調(diào)用時(shí)&Node的地址值跟創(chuàng)建好之后的地址值是不同的
    */
    LinkListPtr list, node;
    ElemType data;
    int i;

    list = (LinkListPtr)malloc(sizeof(Node)); //生成頭結(jié)點(diǎn)
    list->next = NULL;
     printf("請(qǐng)輸入結(jié)點(diǎn)數(shù)據(jù)值\n");
    for(i = 0; i < n; i++)
    {
        node = (LinkListPtr)malloc(sizeof(Node)); //生成新結(jié)點(diǎn)
        scanf("%d", &data);
        node->data = data;
        node->next = list->next;
        list->next = node;
    }
    return list;
}

/**
 * 尾插法創(chuàng)建鏈表
 */
LinkListPtr create_tail(int n) {
    LinkListPtr list, node, p;
    ElemType data;
    int i;

    list = (LinkListPtr)malloc(sizeof(Node)); //生成頭結(jié)點(diǎn)
    list->next = NULL;
    p = list;
    printf("請(qǐng)輸入結(jié)點(diǎn)數(shù)據(jù)值\n");
    for(i = 0; i < n; i++) { //生成新結(jié)點(diǎn)
        node = (LinkListPtr) malloc(sizeof(Node));
        scanf("%d", &data);
        node->data =data;
        //指針移動(dòng)到最后一個(gè)結(jié)點(diǎn)
        while(p->next) {
            p = p->next;
        }
        //修改指針，插入新結(jié)點(diǎn)
        node->next = NULL;
        p->next = node;
    }
    return list;
}

/**
 * 插入數(shù)據(jù)到指定位置
 */
Status insertLinkList(LinkListPtr linkListPtr, ElemType e, int pos)
{
    LinkListPtr p = linkListPtr;
    int i = 0;

    while(i < pos-1 && p) { //移動(dòng)到第pos-1個(gè)結(jié)點(diǎn)
        p = p->next;
        i++;
    }
    if(!p || i > pos) {
        printf("第%d個(gè)元素不存在\n", pos);
        return ERROR;
    }
    //為新結(jié)點(diǎn)分配空間，賦值，修改后繼指針和第pos-1個(gè)結(jié)點(diǎn)的后繼指針
    LinkListPtr newNode = (LinkListPtr)malloc(sizeof(Node));
    newNode->data = e;
    newNode->next = p->next;
    p->next = newNode;
    return OK;
}

/**
 * 刪除第pos個(gè)結(jié)點(diǎn)
 */
Status deleteByOrder(LinkListPtr list, int pos, ElemType* e) {
    LinkListPtr p = list;
    LinkListPtr q;
    int i = 0;
    while(p && i < pos-1) { //移動(dòng)到第pos-1個(gè)結(jié)點(diǎn)
        p = p->next;
        i++;
    }
    if(!p || i > pos) {
        printf("\n第%d個(gè)結(jié)點(diǎn)不存在", pos);
        return ERROR;
    }
    q = p->next;
    *e = q->data; //返回被刪除的元素值
    //修改相關(guān)結(jié)點(diǎn)的指針域
    p->next = q->next;
    //釋放被刪除結(jié)點(diǎn)的空間
    free(q);
    return OK;
}

/**
 * 清空鏈表，只保留頭結(jié)點(diǎn)
 */
Status clearList(LinkListPtr list) {
    LinkListPtr p = list->next; //移動(dòng)到第一個(gè)結(jié)點(diǎn)
    LinkListPtr q;
    while(p) {
        printf("%d\t", p->data);
        q = p;
        p = p->next;
        free(q);
    }
    list->next = NULL;
}

/**
 * 遍歷鏈表，輸出其中的數(shù)據(jù)元素
 */
Status printLinkList(LinkListPtr list)
{
    LinkListPtr p;
    p = list->next; //移動(dòng)到存放真實(shí)數(shù)據(jù)的第一個(gè)結(jié)點(diǎn)
    while(p) {
        printf("%d\t", p->data);
        p = p->next;
    }
    printf("\n");
}

/**
 * 鏈表的逆置
 */
Status reserve(LinkListPtr list) {
    LinkListPtr p, q, r;
    p = list;//P指向頭結(jié)點(diǎn)
    q = p->next; //q指向第一個(gè)結(jié)點(diǎn)
    while(q->next) {
        r = q->next;
        q->next = p;
        p = q;
        q = r;
    }
    q->next = p; //連上最后一個(gè)結(jié)點(diǎn)
    p = list->next;
    p->next = NULL; //收尾
    list->next = q; //賦頭
    return OK;
}

void main()
{
    ElemType e = 100;
    //LinkListPtr list = create_head(10); //頭插法生成鏈表
    LinkListPtr list2 = create_tail(10); //尾插法生成鏈表
    insertLinkList(list2, e, 4);
    insertLinkList(list2, e, 4);
    insertLinkList(list2, e, 1);
    insertLinkList(list2, e, 18);
    printLinkList(list2);
    deleteByOrder(list2, 1, &e);
    printf("被刪除的元素值: %d\n", e);
    deleteByOrder(list2, 4, &e);
    printf("被刪除的元素值: %d\n", e);
    deleteByOrder(list2, 4, &e);
    printf("被刪除的元素值: %d\n", e);
    printLinkList(list2);
    printf("逆置鏈表：\n");
    reserve(list2);
    printLinkList(list2);
    printf("清空鏈表:");
    clearList(list2);
    printLinkList(list2);
}