#include "stdafx.h"

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

struct Node {

    int _id;

    char s[];

    struct Node* pre;

    struct Node* next;

};

void node_free(struct Node** q) {

    if( *q != NULL) {

        printf("free %d\n",(*q)->_id);

        free(*q);

        *q = NULL;

    }

}

void node_print(struct Node* q) {

    if (NULL == q) {

        puts("节点打印：空节点，无可打印");

        return;

    }

    printf("---id = %2d---", q->_id);

    printf("preview = %10d ", q->pre);

    printf("【address = %10d】 ", q);

    printf("next = %10d\n", q->next);

}

void chain_print(struct Node* qFirst) {

    if (qFirst == NULL) {

        puts("没有元素可以打印");

        return;

    }

    puts("----------↓↓↓打印链表------------");

    // 遍历链表

    struct Node* q;

    for(q = qFirst; q != NULL; q=q->next ) {

        node_print(q);

    }

    puts("----------↑↑↑打印链表------------");

}

/*

* 为链表追加节点（加在最后）

* 参数：头节点，需要追加的节点

* 返回值：无

*/

void chain_add(struct Node* qFirst, struct Node* qAdd) {

    // 定位到链表头

    struct Node* q = qFirst;

    // 只要后面（next）有节点，往后找；直到没有next的节点（最后一个）

    for(q; q->next != NULL; q=q->next ) {

        node_print(q);

    }

    // 此时定位在最后一个节点，下图1

    // 将新节点加在最后节点的后面（next）

    q->next = qAdd;// 下图2

    qAdd->pre = q;//下图3

}

/*

* 删除节点

* 参数：1.头结点 2.待删除的结点

*        因为被删除的结点需要置空，所以需要使用二级指针

* 返回值：-1 删除失败/0 删除成功

*/

int chain_remove(struct Node** qFirst, struct Node** qRemove) {

    struct Node* qPre = NULL;

    struct Node* qNext = NULL;

    struct Node* q = *qFirst;

    // 1.输入Check

    if(NULL == *qRemove){

        puts("删无可删！");

        return -;

    }else{

        printf("删除节点：id=%d\n", (*qRemove)->_id);

    }

    // 2.删除头结点，特殊对待

    if(*qFirst == *qRemove ) {

        if((*qFirst)->next == NULL){

            // 就一个头结点的场合

            node_free(qFirst);

        }else{

            qNext = q->next;

            node_free(qFirst);

            *qFirst = qNext;

        }

        return ;

    }

    // 遍历链表

    for(q; q != NULL; q=q->next ) {

        if (q == *qRemove) {

            qPre = q->pre;

            qNext = q->next;

            if (qNext!=NULL) {

                qNext->pre = qPre;

                qPre->next= qNext;

            } else {

                // 尾节点的场合

                qPre->next= NULL;

            }

            node_free(qRemove);

            return ;

        }

    }

}

void chain_clear(struct Node** qFirst) {

    puts("\n----------Clear------------");

    if (qFirst == NULL) {

        puts("已经是空");

        return;

    }

    // 遍历链表

    //    不断删除第一个元素

    while(*qFirst != NULL) {

        chain_remove(qFirst,qFirst);

    }

}

struct Node* chain_get(struct Node* qFirst, int index) {

    printf("---获取index = %d的节点：", index);

    int i = ;

    // 遍历链表

    struct Node* q = qFirst;

    for(q; q!= NULL; q=q->next,i++ ) {

        if (index == i) {

            return q;

        }

    }

    return NULL;

}

/*

* 获取链表长度（即 节点的个数）

* 参数： 头节点

* 返回值：链表长度

*/

int chain_count(struct Node* qFirst) {

    if (qFirst == NULL) {

        // 头节点都没有，长度为0

        return ;

    }

    int i = ;

    // 遍历链表

    struct Node* q = qFirst;

    for(q; q != NULL; q=q->next) {

        // 顺藤摸瓜，直到最后一个节点

        i++;// 找到一个就+1

    }

    return i;

}

struct Node* node_new(int id) {

    struct Node* q = (struct Node*)malloc(sizeof(struct Node));

    memset(q, , sizeof(struct Node));

    q->_id = id;

    return q;

}

void testFunction(){

    struct Node* q1 = node_new();

    struct Node* q2 = node_new();

    struct Node* q3 = node_new();

    struct Node* q4 = node_new();

    struct Node* q5 = node_new();

    puts("###有节点的链表：");

    printf("count = %d\n",chain_count(NULL));

    chain_print(NULL);

    puts("\n###1个节点的链表：");

    printf("count = %d\n",chain_count(q1));

    chain_print(q1);

    // 增

    chain_add(q1, q2);

    chain_add(q1, q3);

    chain_add(q1, q4);

    chain_add(q1, q5);

    puts("\n###5个节点的链表：");

    printf("count = %d\n",chain_count(q1));

    chain_print(q1);

    puts("");

    struct Node* pGet;

    pGet = chain_get(q1, );

    node_print(pGet);

    pGet = chain_get(q1, );

    node_print(pGet);

    pGet = chain_get(q1, );

    node_print(pGet);

    pGet = chain_get(q1, );

    node_print(pGet);

    // 删

    puts("\n###删除测试");

    chain_remove(&q1,&q5);

    chain_print(q1);

    chain_remove(&q1,&q3);

    chain_print(q1);

    chain_remove(&q1,&q1);

    chain_print(q1);

    //chain_remove(&q1,&q1);

    //chain_print(q1);

    //chain_remove(&q1,&q1);

    //chain_print(q1);

    //chain_remove(&q1,&q1);

    //chain_print(q1);

    chain_clear(&q1);

    chain_print(q1);

    getchar();

}

int _tmain(int argc, _TCHAR* argv[]){

    testFunction();

    return ;

}