/*
时间：2011年9月16日15:57:23
目的：学习链表的创建和使用，读懂程序
*/

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

//定义了一个链表节点的数据类型
struct Node
{
    int data;                //数据域
    struct Node * pNext;    //指针域
};

//函数声明
struct Node * create_list(void);
void traverse_list(struct Node *);

int main(void)
{
    struct Node * pHead = NULL;        //定义头指针
    pHead = create_list();  //create_list()功能：创建一个非循环单链表，并将该链表的头结点的地址付给pHead
    traverse_list(pHead);
    
    return 0;
}

struct Node * create_list(void)
{
    int len;  //用来存放有效节点的个数
    int i;
    int val; //用来临时存放用户输入的结点的值

    //分配了一个不存放有效数据的头结点
    struct Node * pHead = (struct Node *)malloc(sizeof(struct Node));        
    if (NULL == pHead)
    {
        printf("分配失败, 程序终止!\n");
        exit(-1);
    }
    struct Node * pTail = pHead;
    pTail->pNext = NULL;
    printf("请输入您需要生成的链表节点的个数: len = ");
    scanf("%d", &len);
    
    for (i=0; i<len; ++i)
    {
        printf("请输入第%d个节点的值: ", i+1);
        scanf("%d", &val);
        
        struct Node * pNew = (struct Node *)malloc(sizeof(struct Node));
        if (NULL == pNew)
        {
            printf("分配失败, 程序终止!\n");
            exit(-1);  //终止程序
        }
        pNew->data = val;
        pTail->pNext = pNew;
//        printf("test pTail=%#X, pTail->data=%d, pTail->pNext=%#X\n",pTail,pTail->data,pTail->pNext);        //测试用
        pNew->pNext = NULL;
        pTail = pNew;
//        printf("test pTail=%#X, pTail->data=%d, pTail->pNext=%#X\n",pTail,pTail->data,pTail->pNext);        //测试用
    }

    return pHead;
}

void traverse_list(struct Node * pHead)
{
    struct Node * p = pHead->pNext;
    while (NULL != p)
    {
        printf("%d  ", p->data);
        p = p->pNext;
    }
    printf("\n");
    
    return;
}

/*
在VC++6.0中的输出结果为：
————————————
请输入您需要生成的链表节点的个数: len = 3
请输入第1个节点的值: 1
请输入第2个节点的值: 2
请输入第3个节点的值: 3
1  2  3
Press any key to continue
————————————

流程：
————————————
创建struct Node类型的结构体，结构体中包含 int 类型的成员 data，以及 struct Node * 类型的成员 pNext
函数前置声明

main函数开始
    定义一个struct Node *类型的变量pHead，并给他赋值NULL。此时pHead = 0

    调用create_list()函数
        定义变量
        定义一个struct Node *类型的变量pHead 并给 pHead 动态分配内存，此时 pHead=0X380FE0, pHead->data=-842150451, pHead->0XCDCDCDCD
        判断动态分配内存是否失败，如果失败退出程序
        定义struct Node *型指针变量 pTail，将pHead赋值给pTail。此时 pTail=0X380FE0, pTail->data=-842150451, pTail->0XCDCDCDCD
        给 pTail指向的 struct Node类型变量 的成员 pTail->pNext 赋值 NULL。此时pTail=0X380FE0, pTail->data=-842150451, pTail->pNext=0
        输入需要生成的链表节点的个数len。比如输入3
        i=0
        判断0<3为真，开始第1次循环：
            提示输入第1个节点的值，比如输入1，则val=1
            定义一个struct Node *类型的变量pNew 并给 pHead 动态分配内存，此时 pNew=0X381018, pNew->data=-842150451, pNew->pNext=0XCDCDCDCD
            判断动态分配内存是否失败，如果失败退出程序
            把val的值赋给 pNew 指向的 struct Node类型变量 的成员 pNew->data，此时 pNew=0X381018, pNew->data=1, pNew->pNext=0XCDCDCDCD
            把 pNew 的地址 赋值给 pTail指向的 struct Node类型变量 的成员 pTail->pNext。此时 pTail=0X380FE0, pTail->data=-842150451, pTail->pNext=0X381018
            !注意 (也就是说，此时有个 地址为0X380FE0 的 struct Node 类型的 结构体变量，它有两个成员，其中data 为 垃圾值，pNext 为 0X381018)
            给 pNew 指向的 struct Node类型变量 的成员 pNew->pNext 赋值 NULL。此时 pNew=0X381018, pNew->data=1, pNew->pNext=0
            将 pNew 的地址 赋值给 pTail。此时 pTail=0X381018, pTail->data=1, pTail->pNext=0。
            !注意 (也就是说，此时有个 地址为0X381018 的 struct Node 类型的 结构体变量，它有两个成员，其中data 为 1，pNext 为 0)
            执行++i, i=1
        判断1<3为真，开始第2次循环：
            提示输入第2个节点的值，比如输入2，则val=2
            定义一个struct Node *类型的变量pNew 并给 pHead 动态分配内存，此时 pNew=0X3831D8, pNew->data=-842150451, pNew->pNext=0XCDCDCDCD
            判断动态分配内存是否失败，如果失败退出程序
            把val的值赋给 pNew 指向的 struct Node类型变量 的成员 pNew->data，此时 pNew=0X3831D8, pNew->data=2, pNew->pNext=0XCDCDCDCD
            把 pNew 的地址 赋值给 pTail指向的 struct Node类型变量 的成员 pTail->pNext。此时 test pTail=0X381018, pTail->data=1, pTail->pNext=0X3831D8
            !注意 (此时前面那个 地址为0X381018 的 struct Node 类型的 结构体变量，它的两个成员变成了：data  为 1，pNext 为 0X3831D8)
            给 pNew 指向的 struct Node类型变量 的成员 pNew->pNext 赋值 NULL。此时 pNew=0X3831D8, pNew->data=2, pNew->pNext=0
            将 pNew 的地址 赋值给 pTail。此时 pTail=0X3831D8, pTail->data=2, pTail->pNext=0
            !注意 (也就是说，此时有个 地址为0X3831D8 的 struct Node 类型的 结构体变量，它有两个成员，其中data 为 2，pNext 为 0)
            执行++i, i=2
        判断2<3为真，开始第3次循环：
            提示输入第3个节点的值，比如输入3，则val=3
            定义一个struct Node *类型的变量pNew 并给 pHead 动态分配内存，此时 pNew=0X383210, pNew->data=-842150451, pNew->pNext=0XCDCDCDCD
            判断动态分配内存是否失败，如果失败退出程序
            把val的值赋给 pNew 指向的 struct Node类型变量 的成员 pNew->data，此时 pNew=0X383210, pNew->data=3, pNew->pNext=0XCDCDCDCD
            把 pNew 的地址 赋值给 pTail指向的 struct Node类型变量 的成员 pTail->pNext。此时 pTail=0X3831D8, pTail->data=2, pTail->pNext=0X383210
            !注意 (此时前面那个 地址为0X3831D8 的 struct Node 类型的 结构体变量，它的两个成员变成了：data  为 2，pNext 为 0X383210)
            给 pNew 指向的 struct Node类型变量 的成员 pNew->pNext 赋值 NULL。此时 pNew=0X383210, pNew->data=3, pNew->pNext=0
            !注意 (也就是说，此时有个 地址为0X383210 的 struct Node 类型的 结构体变量，它有两个成员，其中data 为 3，pNext 为 0)
            执行++i, i=3
        判断3<3为假，循环结束    
        create_list 函数调用完毕。将create_list 函数中的 pHead 的值返回 main函数 然后赋值给 main函数中的 pHead。此时 pHead = 0X380FE0

        !注意 到这里为止，链表创建完毕（每一个节点的指针域的值都指向下一个节点）。分别是：
             第0级节点 地址为0X380FE0， data为垃圾值， pNext为0X381018   头节点     头指针即为 pHead 0X380FE0
            第1级节点 地址为0X381018， data为1，      pNext为0X3831D8    首节点
            第2级节点 地址为0X3831D8， data为2，      pNext为0X383210
            第3级节点 地址为0X383210， data为3，      pNext为0            尾节点

    调用 traverse_list(pHead) 函数
        定义一个struct Node *类型的变量p，并将 pHead 指向的 struct Node类型变量 的成员 pHead->pNext的值付给他。
        这里 pHead = 0X380FE0。地址为 0X380FE0 的变量的成员 pNext 为0X381018，即p = 0X381018
        判断 0X381018 != NULL为真,循环第1次
            输出p->data，因为这里 p=0X381018 所以输出的是 地址为0X381018的变量 的 成员data，即输出1
            将 地址为0X381018的变量 的另一个 成员pNext 的值0X3831D8 赋值给 p，p=0X3831D8
        判断 0X3831D8 != NULL为真,循环第2次
            输出p->data，因为这里 p=0X3831D8 所以输出的是 地址为0X3831D8的变量 的 成员data，即输出2        
            将 地址为0X3831D8的变量 的另一个 成员pNext 的值0X383210 赋值给 p，p=0X383210
        判断 0X383210 != NULL为真,循环第3次
            输出p->data，因为这里 p=0X383210 所以输出的是 地址为0X383210的变量 的 成员data，即输出3
            将 地址为0X383210的变量 的另一个 成员pNext 的值0 赋值给 p，p=0
        判断 0 != NULL为假,结束循环
    traverse_list(pHead) 函数调用完毕，没有值返回main函数

main函数结束
            
*/