前言

第一次学数据结构，代码写的可能不是很好，大神勿喷，指出来就行。

链表

顾名思义，链表就是每个数据之间有某种连接关系的一张表。

注意：在学习链表之前首先要搞清地址(指针)的概念。

原理

我们知道，数组是一串连续的内存空间，里面存放着我们的数据。
但是链表却不同，他是一堆数据被存放到不连续的内存空间，但每组数据都会有一个变量指向下一组数据的地址(指针)，以此来连接起来。

用图来表示就是这样

所以我们很容易就想到用C语言的结构体来储存数据和指向下一个节点的地址，最后个节点由于后面没有别的节点了，所以就指向空(NULL)了。

struct Node // 链表结构
{
    int data;
    struct Node *pNext;
};

操作

无非也就是增删查改之类的，具体实现里的代码注释已经写的很详细了，直接看就可以了。

具体实现(第一次写这种，可能写的不是很好，大神勿喷)

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

struct Node // 链表结构
{
    int data;
    struct Node *pNext;
};

struct LinkedList // 记录链表的初始节点和末节点
{
    struct Node *pLast; // 末节点
    struct Node *root; // 初始节点
};

// Operations

// 添加节点
struct Node *addNode(struct LinkedList *list, int data)
{
    struct Node *m = (struct Node*) malloc(sizeof(struct Node)); // 创建节点
    m -> data = data; // 塞入数据
    m -> pNext = NULL; // 把该节点的下一个节点的指针指向空
    if (list -> pLast != NULL) (list -> pLast) -> pNext = m; // 如果有上一个元素，那就把上一元素的下一节点指针指向本节点
    else list -> root = m; // 没有的话就充当根节点
    list -> pLast = m; // 不管怎么说，把链表的当前节点设为m
    return m;
}

struct Node *addNode(struct LinkedList *list, int data,int index)
{
    struct Node *last = list -> pLast; // 先记录原来的最后一位
    list -> pLast = list -> root; // 把记录最后一位指针的变量赋为第一个，以便遍历
    struct Node *m = 0x0;
    if (index != 0) {
        for (int i = 1;i < index;i ++)
        {
            if ((list -> pLast) -> pNext == NULL) break; // 到尾巴了就跳掉
            list -> pLast = (list -> pLast) -> pNext; // 把pLast一位一位往后移
        }
        // 准备添加元素
        struct Node *next = (list -> pLast) -> pNext; // 先记录原来这个元素的后一个元素地址
        m = addNode(list, data); // 添加元素(会自动和前一个元素链接起来的)，但同时和原来的后面一个元素的链也断了
        (list -> pLast) -> pNext = next; // 把后面的那个链接回来
    } else {
        list -> pLast = NULL; // 让addNode方法误以为前面没有元素了
        struct Node *newRoot = addNode(list, data); // 添加元素，此时是全新的一个根节点
        newRoot -> pNext = list -> root; // 和原来的根节点连回来
        list -> root = newRoot; // 重新赋值根节点
        m = list -> root; // 返回新添加的节点
    }
    if (last -> pNext != NULL) list -> pLast = last -> pNext; // 如果在末尾有添加了一个节点，那就指向x那个新的节点
    else list -> pLast = last; // 恢复原来的节点
    return m;
}

void removeNode(struct LinkedList *list, int index)
{
    struct Node *last = 0x0; // 上一个节点，0x0，也就是NULL，是空节点
    struct Node *now = list -> root; // 当前轮到的节点，一开始为root节点
    for (int i = 1;i <= index;i ++)
    {
        if (now -> pNext != NULL) { // 如果还有下一个节点的话
            last = now; // 往下轮，上一个节点就是now节点
            now = now -> pNext; // 往下轮
        }
        else break; // 到尾巴了就退出
    }
    if (last == NULL) // 如果要删除root元素
    {
        if ((list -> root) -> pNext != NULL) // 如果root元素后面还有
        {
            list -> root = (list -> root) -> pNext; // 链上
        } else {
            list -> root = NULL; // 没有的话就把root元素也弄空
        }
    } else {
        last -> pNext = NULL; // 断开上一个的链接
        if (now -> pNext != NULL) // 如果后面还有元素的话
        {
            last -> pNext = now -> pNext; // 链上
        }
    }
    free(now); // 释放删除掉的元素的内存
}

int main(int argc, const char * argv[]) {
    // insert code here...
    struct LinkedList list = {NULL, NULL};
    addNode(&list, 2); // 增
    addNode(&list, 1);
    addNode(&list, 5);
    addNode(&list, 4, 1); // 指定位置增
    addNode(&list, 3);
    
    removeNode(&list, 0); // 删
    
    printf("orgin: 4 1 5 3\n");
    
    // 查
    printf("查询:\n");
    int in = 0;
    scanf("%d",&in);
    struct Node *pSearch = list.root;
    int hasFound = 1;
    for (int i = 0;i < in;i ++)
    {
        if (pSearch -> pNext != NULL)
        {
            pSearch = pSearch -> pNext;
        } else hasFound = 0;
    }
    if (hasFound) printf("%d\n",pSearch -> data);
    else printf("NF!\n");
    
    // 改
    printf("修改:\nindex:\n");
    scanf("%d",&in);
    int to;
    printf("to:\n");
    scanf("%d",&to);
    pSearch = list.root;
    hasFound = 1;
    for (int i = 0;i < in;i ++)
    {
        if (pSearch -> pNext != NULL)
        {
            pSearch = pSearch -> pNext;
        } else hasFound = 0;
    }
    if (hasFound) pSearch -> data = to;
    
    // 遍历
    printf("开始遍历:\n");
    struct Node *pNow = list.root;
    struct Node *pNext;
    int isf = 1;
    while (pNow != NULL)
    {
        if (isf) isf = 0;
        else printf(" ");
        printf("%d",pNow -> data);
        if (pNow -> pNext != NULL) {
            pNext = pNow -> pNext;
            free(pNow);
            pNow = pNext;
        } else {
            free(pNow);
            break;
        }
        
    }
    printf("\n");
    return 0;
}