数据结构（七）链表的定义

链表定义

n个节点离散分配，彼此通过指针相连，每个节点只有一个前驱节点，每个节点只有一个后续节点，首节点没有前驱节点，尾结点没有后续节点。链表分为单链表，双链表（每一个节点有两个指针域），循环链表（可以通过任意一个节点找到其他所有节点），非循环链表

链表相关术语

首节点：第一个有效节点

尾结点：最后一个有效节点

头结点：头结点的数据类型和首节点的数据类型是相同的，第一个有效节点之前的那个节点，头结点并不存放有效数据，加头结点是为了方便对链表的操作

头指针：指向头结点的指针变量

尾指针：指向尾结点的指针变量

确定一个链表只需要头指针一个参数，可以通过头指针推算出链表的其他信息

使用代码实现链表

#include<stdio.h>
#include<malloc.h>
#include <stdlib.h>
typedef struct Node {
    int data;     //数据域
    struct Node * pNext; //指针域
}NODE, *PNODE;
PNODE create_list(void);
void traverse_list(PNODE pHead);
int main(void) {
    PNODE pHead = NULL;
    pHead = create_list();    //创建非循环单链表，并将该链表头结点地址传给pHead
    traverse_list(pHead);
    return 0;
}

PNODE create_list(void) {
    int len;  //链表节点个数
    int i;
    int val;  //临时存放用户输入的节点的值
    
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if (NULL == pHead) {
        printf("创建链表失败！");
        exit(-1);
    }
    
    //pTail永远指向尾节点
    PNODE pTail = pHead;
    pTail->pNext = NULL;
    
    printf("输入链表节点个数：");
    scanf("%d", &len);
    for (i = 0; i < len; ++i) {
        printf("请输入第%d个节点的值：", i+1);
        scanf("%d", &val);
        
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if (NULL == pNew) {
            printf("创建节点失败！");
            exit(-1);
        }
        pNew->data = val;
        pTail->pNext = pNew;
        pNew->pNext = NULL;
        pTail = pNew;
    }
    return pHead;
}

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