带头结点的单链表

结点结构定义：

#define Status    int
#define OK        1
#define ERROR     0
#define OVERFLOW -1
typedef int ElemType;
typedef struct Node {
    ElemType data;
    struct Node* next;    
} Node, *LinkList;

获取链表的长度：

int GetLen(LinkList l) {
    // 将 p 指向第一个结点，len 置为 0
    Node* p = l->next;
    int len = 0;
    while (p) {
        len++;
        p = p->next;
    }
    return len;
}

获取指定位序的元素：

// 重点：从第几个结点开始查询，p 就指向谁，j 就置为几
Status GetElemAtPos(LinkList l, int i, ElemType *e) {
    if (i < 1) return ERROR;
    // 从第一个结点开始查找，所以要将 p 指向第一个结点，即 p = l->next;
    Node* p = l->next;
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (!p) return ERROR;
    *e = p->data;
    return OK;
}

获取指定位序的结点：

Node* GetNodeAtPos(LinkList l, int i) {
    if (i < 1) return ERROR;
    Node* p = l->next;
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    // 直接返回 p 即可，没有找到就是 NULL
    return p;
}

在指定位序插入元素：

// 重点：挂载新结点时要注意先链接后面的结点，然后再链接前面的结点
Status InsertNodeAtPos(LinkList l, int i, ElemType e) {
    if (i < 1) return ERROR;
    // 先获取到第 i - 1 个结点
    Node* prev = l->next;
    int j = 1;
    while (prev && j < i - 1) {
        prev = prev->next;
        j++;
    }
    if (!prev) return ERROR;
    // 再创建新结点
    Node* node = (Node*)malloc(sizeof(Node));
    if (!node) exit(OVERFLOW);
    node->data = e;
    // 最后再挂载新结点，先链接后面的，再链接前面的
    node->next = prev.next;
    prev.next = node;
    return OK;
}

删除指定位序的元素，并将该元素返回到变量 e 中：

Status DeleteNodeAtPos(LinkList l, int i, ElemType *e) {
    if (i < 1) return ERROR;
    // 先获取到第 i - 1 个结点
    Node* prev = l->next;
    int j = 1;
    while (prev && j < i - 1) {
        prev = prev->next;
        j++;
    }
    if (!prev) return ERROR;
    // 再获得第 i 个结点的指针，并将值返回到变量 e 中
    Node* node = prev->next;
    *e = node->data;
    // 最后修改链接，并释放掉内存
    prev->next = node->next;
    free(node);
    return OK;
}

头插法建立链表：

// 重点：头插法建立链表，要想保证原来的顺序，需要反过来遍历原来的元素集
Status CreateListInHead(LinkList* l, int n) {
    // 先创建头结点
    *l = (Node*)malloc(sizeof(Node));
    if (!(*l)) return ERROR;
    Node* p;
    // 反过来遍历
    for (int i = n; i > 0; i--) {
        // 创建新结点并初始化
        p = (Node*)malloc(sizeof(Node));
        if (!p) return ERROR;
        p->data = i;
        // 头插法，先链接后面的结点
        p->next = (*l)->next;
        (*l)->next = p;
    }
    return OK;
}

尾插法建立链表：

// 重点：尾插法就是在最后面追加，所以按原来的顺序链接结点即可
Status CreateListInTail(LinkList* l, int n) {
    // 先创建头结点
    *l = (Node*)malloc(sizeof(Node));
    if (!(*l)) return ERROR;
    Node* p;
    // 尾指针，指向最后一个结点，初始指向头结点
    Node* r = *l;
    // 按原来的顺序链接即可
    for (int i = 1; i <= n; i++) {
        // 创建新结点并初始化
        p = (Node*)malloc(sizeof(Node));
        if (!p) return ERROR;
        p->data = i;
        p->next = NULL;
        // 通过尾指针链接新结点
        r->next = p;
        // 尾指针指向最后一个结点
        r = p;
    }
    return OK;
}