/*
此程序完整地介绍了动态链表节点的建立、显示、删除和插入操作。
*/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>                           // assert.检查入参链表头指针是否为空。

#define IN                                    // 这三个宏定义为空格
#define OUT  
#define INOUT  

#define LEN sizeof(stu)                       // malloc内存时使用

typedef struct student
{
    int num;
    int score;
    struct student *next;
}stu;

stu *creatNode(IN int numOfNode)              // 建立链表函数
{
    int n = numOfNode;
    int i = 0;
    stu *head = NULL,
        *pafter = NULL,                     
        *pbefore = NULL;                      // 注意不能写成: stu *head, p, pt; (p和pt前必须有 * ); 同时，要养成初始化的好习惯。

    i = n;
    while (0 != i)
    {
        if (n == i)                           // 第一个节点
        {
            pafter = (stu *)malloc(LEN);      // 如果是第一个节点，让p指向第一个节点。   
            head = pafter;                    // head指向头节点
        }
        else               
        {
            pbefore = (stu *)malloc(LEN);     // 如果不是第一个节点，就让pt指向新开辟的节点
            pafter->next = pbefore;           
            pafter = pafter->next;            // 让p指向当前开辟的节点
        }

        printf("Please input the value of %dth element:(num,score)", n+1-i);
        scanf("%d", &pafter->num);
        scanf("%d", &pafter->score);

        if (1 == i)                           // 最后一个节点
        {
            pafter->next = NULL;
        }

        i--;
    }

    return head;
}

void showNode(IN stu *headTemp)               // 显示节点
{
    stu *head = headTemp,
        *p = NULL;

    if (NULL == headTemp)
    {
        printf("the linker is empty!\n");
        return;
    }

    p = head;
    do                              
    {
        printf("num = %d, score = %d\n", p->num, p->score);
        p = p->next;
    }while (NULL != p);                       // 逗号不能少哦。不能用 NULL != p->next 做判断。
   
    return;
}

stu* deleteNode(IN stu *headTemp, IN int num)
{
    stu *head = NULL,
        *p1 = NULL,
        *p2 = NULL;

    if (NULL == headTemp)
    {
        printf("the linker is empty, cann't delete any linker element!");
    }

    head = headTemp;
    p1 = p2 = head;
   
    while ((NULL != p1) && (p1->num != num))  // 写成：while ((p1->num != num) && (NULL != p1))错误!!!! 可能导致访问非法内存!!!!
    {
        p2 = p1;
        p1 = p1->next;
    }

    if (NULL == p1)                           // 遍历到尾节点，没有找到指定的节点
    {
        puts("cann't find the appointed node!");
    }
    else if (p1 == head)                      // 指定的节点是第一个节点。
    {
        head = p1->next;                      // 如果只有一个节点，此时p1->next == NULL,所以返回的head = NULL，也是正确的。
    }
    else if (NULL == p1->next)                // 查找到了指定的节点，并且是最后一个节点。
    {
        p2->next = NULL;
    }
    else                                      // 存在指定的节点，并且既不是头结点，也不是最后一个节点。
    {
        p2->next = p1->next;
    }

    return head;
}

stu *insertNode(IN stu* headTemp, IN stu* insertNode)
{
    stu *head = NULL;
    stu *pa = NULL;
    stu *pb = NULL;
   
    head = headTemp;
    pa = pb = head;

    while ((NULL != pb) && (pb->num < insertNode->num))
    {
        pa = pb;
        pb = pb->next;
    }

    if (head == pb)                           // 插入到第一个节点之前
    {
        insertNode->next = head;
        head = insertNode;  
    }
    else if (NULL == pb)                      // 插入到最后一个节点之后
    {
        pa->next = insertNode;
        insertNode->next = NULL;
    }
    else                                      // 插入到中间节点
    {
        pa->next = insertNode;
        insertNode->next = pb;
    }

    return head;   
}

int main()
{
    int numberOfNode = 0;                  // 此变量表示节点个数，由用户输入。  
    int deleteNum = 0;                     // 要删除的节点的num值
    stu *head = NULL;                          
    stu istNode;                           // 要插入的节点

    puts("-----------------------creat node------------------------");
    printf("please input the number of the node: ");
    scanf("%d", &numberOfNode);            // 输入要建立的节点个数
    head = creatNode(numberOfNode);

    puts("-----------------------show node-------------------------");
    showNode(head);                        // 显示节点
   
    puts("-----------------------insert node-----------------------");
    printf("please input the value of the insert Node(num,score): ");
    scanf("%d %d", &istNode.num, &istNode.score);         // 输入插入节点值
    istNode.next = NULL;
    head = insertNode(head, &istNode);
   
    puts("-----------------------show nodes after insert------------");
    showNode(head);                                       // 显示插入之后的节点   

    puts("-----------------------delete node-----------------------");
    while (NULL != head)                                  // 删除链表节点，直至链表为空
    {
        printf("please intput the num of delete node: ");
        scanf("%d", &deleteNum);
        head = deleteNode(head, deleteNum);               // 把删除之后的链表头节点返回，当所有节点都被删除，head == NULL

        puts("-----------------------show nodes after delete--------");
        showNode(head);                                   // 显示删除之后的节点  
    }

    return 0;
}