数据结构之单链表

引入单链表

节点与节点之间的物理地址不一定不连续，逻辑地址必定是连续的，这种就是链式结构。所谓的单链表就是链式结构的线性表，需要使用一个数据域来存放数据，一个指针域来存放下一个节点的所在地址，这样形成的这种线性结构。一般说的链表就是单链表，下文也将其称为链表，本文介绍的是最简单的整形链表。

链表的节点结构体：

typedef int DataType;	//DataType 是 int 的别名
typedef struct node
{
    DataType data;		//数据域，用于存放本节点的数据
    struct node* next;	//指针域，用于存放下一节点的地址
}Node, *Link;

在上面的结构体中，Node是struct node的别名，Link是struct node*的别名。即

// 等价
Node st;	struct node st;
Link p;		struct node* p;

链表中，为了方便空链表和非空链表的统一处理，我们引入了头节点，这个头节点，与其他的节点相同，没有数据域，只有指针域，且其指针指向第一个元素，若是空链表则指针域的指向为空。

遍历单链表

1. 定义Link类型节点指针p，并为其申请空间
2. 指向第一个节点（头节点的下一个节点）
3. 只要p不为空，则打印p的数据域，且p指向p的下一个节点

/**
*   （1）单链表的遍历操作
*   操作接口： void displayNode(Link head);
*/
void displayNode(Link head)
{
    Link p = NULL;
    p = (Link)malloc(sizeof(Node));
    p = head->next;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
}

求单链表长度

1. 定义Link类型节点指针p，并为其申请空间
2. 指向第一个节点（头节点的下一个节点），定义一个变量count统计长度的值
3. 只要p不为空，则p指向p的下一个节点，count自增1

/**
*   （2）求单链表元素个数
*   操作接口：int lengthofNode(Link head);
*/
int lengthofNode(Link head)
{
    Link p = NULL;
    p = (Link)malloc(sizeof(Node));
    p = head->next;
    int count = 0;
    while (p != NULL)
    {
        p = p->next;
        count++;
    }
    return count;
}

单链表查找操作

1. 定义节点p，用来循环遍历链表
2. 定义count，用来记载当前所在的下标
3. 循环，当x与链表当前节点的数据与相等时，则找到了，返回true
4. 当循环完了，且未找到与x相等的值，则返回false

/**
*   （3）单链表查找操作
*   操作接口：int queryNode(Link head, DataType x);
*/
bool queryNode(Link head, DataType x)
{
    Link p = NULL;
    p = (Link)malloc(sizeof(Node));
    int count = 0;
    p = head->next;
    while (p != NULL)
    {
        if (p->data == x)
        {
            printf("%d第一次出现在第%d个元素上", p->data, count+1);
            return true;
        }
        count++;
        p = p->next;
    }
    return false;
}

单链表的插入

1. 三个参数，第一个是头节点，第二个是插入的位置（不是下标，是下标+1），第三个是要插入的元素
2. 定义节点p用来循环链表，变量count用来记录当前节点下标位置
3. 当p不为空且count的值小于i-1，则循环遍历且count自增1
4. 若链表节点已经为空了，count还是小于i，则直接返回false
5. 否则就断链添加节点

/**
*   （4）单链表插入操作
*   操作接口：bool insertNode(Link head, int i, DataType x);
*/
bool insertNode(Link head, int i, DataType x)
{
    Link p = NULL;
    p = (Link)malloc(sizeof(Node));
    p = head->next;
    int count = 0;
    while (p != NULL && count < i-1)
    {
        p = p->next;
        count++;
    }
    if (p == NULL)
        return false;
    else 
    {
        Link q = NULL;
        q = (Link)malloc(sizeof(Node));
        q->next = p->next;
        q->data = x;
        p->next = q;
        return true;
    }
}

头插法建立单链表

头插法是建立链表的一种方法，也是必须掌握的方法。即每次插入的新节点都是head的next域，最后第一个插入的节点就成了最后一个节点。

/**
*   （5）创建一个单链表 -- 头插法
*   操作接口：Link headnewList(DataType a[], int n);
*   头插法：将待插入的节点插在头节点的后面
*   结果：插入到链表顺序和数组顺序相反
*/
Link headNewList(DataType a[], int n)
{
    Link head = NULL;
    head = (Link)malloc(sizeof(Node));
    head->next = NULL;
    int i = 0;
    for (i; i < n; i++)
    {
        Link q = NULL;
        q = (Link)malloc(sizeof(Node));
        q->data = a[i];
        q->next = head->next;
        head->next = q;
    }
    return head;
}

尾插法建立单链表

尾插法建立链表是需要两个节点，一个rear（尾）指针和一个head（头）指针，head指针指向第一个节点，rear指针指向最新插入的节点，每次新建节点都操作尾指针，最后返回头指针。

/**
*   （6）创建一个单链表 -- 尾插法
*   操作接口：Link rearNewList(DataType a[], int n);
*   头插法：将待插入的节点插在终端节点的后面
*   结果：插入到链表顺序和数组顺序相同
*/
Link rearNewList(DataType a[], int n)
{
    Link head = NULL, rear = NULL;
    head = (Link)malloc(sizeof(Node));
    rear = (Link)malloc(sizeof(Node));
    head->next = NULL;
    rear = head;
    for (int i = 0; i < n; i++)
    {
        Link q = NULL;
        q = (Link)malloc(sizeof(Node));
        q->data = a[i];
        q->next = NULL; //防止指针瞎指
        rear->next = q;
        rear = q;
    }
    rear->next = NULL;  //最后让尾节点的next置空
    return head;
}

删除单链表节点

删除值为x的节点，思想还是查找的思想，找到了就让指针指向该节点的后继节点，最后断链，没找到就返回false。

/**
*   （7）单链表节点的删除
*   操作接口：bool deleteNode(Link head, DataType x);
*/
bool deleteNode(Link head, DataType x)
{
    // 判空
    if (head == NULL || head->next == NULL)
        return false;
    Link p = NULL, q = NULL;
    p = (Link)malloc(sizeof(Node));
    q = (Link)malloc(sizeof(Node));
    p = head;
    q = head->next;
    while (q != NULL)
    {
        if (q->data == x)
        {
            p->next = q->next;
            free(q);
            return true;
        }
        else
        {   
            p = q;
            q = q->next;
        }
    }
    return false;
}

单链表置空

循环遍历每一个节点，一个一个地释放空间，最后释放head指针的空间，这样链表的空间就置空了。

/**
*   （8）单链表的释放
*    操作接口：void clearLink(Link head);
*/
void clearLink(Link head)
{
    Link p = NULL, q = NULL;
    p = (Link)malloc(sizeof(Node));
    q = (Link)malloc(sizeof(Node));
    p = head->next;
    q = p->next;
    while (p != NULL)
    {
        free(p);
        p = q;
        q = q->next;
    }
    free(head);
}