/* singlyLinkedList.c */

/* 单链表 */

/* 单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。 */

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

/* 节点结构 */

/*      head

    ————————————————

    | value | next | ->  ...

    ————————————————

*/

typedef struct node {

    int value;            /* 节点的值 */

    struct node *next;    /* 指向下一个节 */

} Node;

/* 链表函数声明 */

void interface(void);

void addNode(Node **head, int number);

int findNode(Node *head, int number);

bool deleteNode(Node **head, int number);

void traverseNodes(Node *head);

int lengthNodes(Node *head);

bool clearNodes(Node **head);

/* 程序主函数入口 */

int main(int argc, char *args[]){

    /* head为指向链表头部节点的指针 */

    Node *head = NULL;

    int flag, number;

    interface();

    for(;;){

        printf("Command: ");

        scanf("%d", &flag);

        switch(flag){

            case :

                printf("Bye!\n");

                return ;

            case :

                printf("Enter numbers(0 to stop): ");

                for(;;){

                    scanf("%d", &number);

                    if(number==)

                        break;

                    addNode(&head, number);

                }

                break;

            case :

                printf("Enter the node value: ");

                scanf("%d", &number);

                printf("index: %d\n", findNode(head, number));

                break;

            case :

                printf("Enter the node value: ");

                scanf("%d", &number);

                if(deleteNode(&head, number))

                    printf("Successfully deleted node %d\n", number);

                else

                    printf("Failed to locate node %d\n", number);

                break;

            case :

                traverseNodes(head);

                break;

            case :

                if(clearNodes(&head))

                    printf("Done!\n");

                break;

            case :

                printf("length: %d\n", lengthNodes(head));

                break;

        }

    }

    return ;

}

/* 用户界面 */

void interface(void){

    puts("+*************************************************+");

    puts("+     0, quit               退出                  +");

    puts("+     1, add nodes          添加                  +");

    puts("+     2, find node          查找                  +");

    puts("+     3, delete node        删除                  +");

    puts("+     4, traverse nodes     遍历                  +");

    puts("+     5, clear nodes        清除                  +");

    puts("+     6, length             长度                  +");

    puts("+*************************************************+");

}

/* 链表函数 */

/* 添加节点 */

/* 注意：函数需要修改到head，需要将head的地址传入 */

void addNode(Node **head, int number){

    /* 使用malloc动态分配一个新节点 */

    Node *node = (Node*)malloc(sizeof(Node));

    node->value = number;

    node->next = NULL;

    Node *last = *head;

    if(!last){

        /* 如果head为空，说明链表为空，将head指向node节点 */

        *head = node;

    }else{

        /* 找到链表尾部，将last节点结构的next属性执行node节点 */

        while(last->next){

            last = last->next;

        }

        last->next = node;

    }

}

/* 根据值查找节点 */

int findNode(Node *head, int number){

    int index = ;

    for(Node *p=head; p; p=p->next, index++){

        if(p->value==number)

            return index;

    }

    return -;

}

/* 根据值删除节点 */

bool deleteNode(Node **head, int number){

    /* 如果要删除第一个节点，需要改变head指向第二个节点并free第一个节点 */

    if(number==){

        Node *first = *head;

        Node *second = first->next;

        free(first);

        *head = second;

        return true;

    }else{

        /* p指向当前节点，f指向p之前的节点 */

        Node *f = NULL;

        for(Node *p=*head; p; p=p->next){

            if(p->value==number){

                f->next = p->next;

                free(p);

                return true;

            }

            f = p;

        }

    }

    return false;

}

/* 遍历链表 */

void traverseNodes(Node *head){

    /* 遍历链表，从头到尾，遇到节点的next为NUll，则表明到了链表尾部 */

    for(Node *p=head; p; p=p->next){

        printf("%d -> ", p->value);

    }

    printf("0\n");

}

/* 清空链表 */

bool clearNodes(Node **head){

    /* 遍历链表，清空节点 */

    Node *q = NULL;

    for(Node *p=*head; p; p=q){

        q = p->next;

        free(p);

    }

    *head = NULL;

    return true;

}

/* 链表长度 */

int lengthNodes(Node *head){

    int count = ;

    for(Node *p = head; p; p=p->next)

        count++;

    return count;

}