基础数据结构(1):链表

? ? 在学习算法时，发现用什么数据结构来存储数据是很重要的，所以学习数据结构也是必须的，先从基础数据结构：数组，字符串，链表，栈，队列，树，矩阵，邻接表，哈希表等，数组和字符串我们已经了解的很多了，所以我们从链表开始学习，了解什么是链表，链表存储数据的方式，以及如何对链表进行各种操作，如何用数组来模拟链表，如何用栈来做链表相关的题目。

1.何为链表

??由于顺序表的插入删除操作需要移动大量的元素，影响了运行效率，因此引入了线性表的链式存储——单链表。单链表通过一组任意的存储单元来存储线性表中的数据元素，不需要使用地址连续的存储单元，因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。同时因为单链表是非随机的存储结构，即不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。

? ? ? 我们再看链表是什么：

? ? ? 链表其实是由一个个结点组成，每个结点之间通过链接更新串联起来，每个结点都有一个后继结点，最后一个结点的后继结点为空结点

? ? ?图中就是一个链表其中橙色结点被称为黄色结点的前驱结点，黄色结点被称为橙色结点的后继结点，链表其实有单向链表、双向链表、循环链表等，这里先只介绍单向链表。那既然结点存储数据，怎么找到后驱结点呢？下面一起来看看吧

2.链表结点的定义

typedef struct ListNode
{
   int data;
   struct ListNode* next;
}ListNode;

? ? ?这就是一个结点的定义，我们把一个结点看成一个结构体，其中data是数据域，可以是任意类型，而struct ListNode* next定义了一个指向ListNode结构体的指针，这个指针的地址是后继结点，将指向下一个结点，这就是指针域，如下图所示??

? ? ? 下面看看具体怎么创建一个链表的结点

3.链表结点创建

ListNode* ListCreateNode(int data)
{
   ListNode* node=(List*)malloc(sizeof(ListNode));
   node->data=data;
   node->next=NULL;
   return node;
}

? ? ?我们先用malloc函数分配一块内存空间，用来存放ListNode即链表对象，将数据域置为函数传参data，将指针域置为NULL，代表这是一个孤立的链表结点，最后返回这个结点的指针。

4.虚拟头结点

? ? ?为了方便对链表进行操作，避免第一个结点无法操作的问题，我们往往会建立一个虚拟头结点，这个头结点上不存储数据，只是指向链表的第一个结点

ListNode* head=ListCreateNode(-1);

5.链表的创建及初始化

? ? ?单链表有两种：一种是带虚拟头结点的，一种不带虚拟头结点。总的来说，带头结点的单链表相对于不带头结点的单链表来说，更加方便对链表进行操作，所以很多时候我们都是用带头结点的单链表，这里我们也只用学习带头结点的即可

5.1初始化带头结点的单链表

void InitList(ListNode* head) {
	head=(ListNode*)malloc(sizeof(ListNode));
    head->next=NULL;
}

5.2创建带头结点的单链表

5.2.1头插法

? ? ? ? ?头插法顾名思义就是从链表开头插入，先插入的后输出，后插入的先输入，例如，我想创建一个链表（4，7，9），输出就是(9，7，4)。

ListNode* HeadInsert(ListNode* head) {
    initlist(head); //初始化
    int n;
    scanf_s("%d",&n);
    for(int i=0;i<n;i++) 
    {
        ListNode* node = (ListNode*)malloc(sizeof(ListNode));
        int data;
        scanf_s("%d", &data);
        node->data = data;
        node->next = head->next;
        head->next = node;
    }
    return head;
}

5.2尾插法

? ? ?尾插法顾名思义就是从链表末尾开始插入，先插入的先输出，后插入的后输出

ListNode* TailInsert(ListNode* head) {
    initlist(head); //初始化
    ListNode* cur = (ListNode*)malloc(sizeof(ListNode));
    cur = head;
    int n,data;
    scanf_s("%d",&n);
    for(int i=0;i<n;i++) 
    {
        ListNode* node = (ListNode*)malloc(sizeof(ListNode));
        scanf_s("%d", &data)
        node->data = data;
        node->next =NULL;
        cur->next = node;
        cur = cur->next; 
    }
    return head;
}

6.链表基础操作?

? ? ?创建完链表之后，我们就要对链表进行操作了，常见的操作就是增删改查

6.1遍历操作

void PrintList(ListNode* head) {
    ListNode* cur = head->next;
    while (cur) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

6.2求单链表的长度

int Length(ListNode* head) {
    ListNode* cur = head->next;
    int len = 0;
    while (cur) {
        len++;
        cur = cur->next;
    }
    return len;
}

6.3查找操作

6.3.1按值查找

ListNode* locateElem(ListNode* head, int data)
{
    ListNode* cur = head->next;
    while (cur && cur->data != data)
    {
        cur = cur->next;
    }
    return cur;
}

6.3.2按位查找

ListNode* getElem(ListNode* head, int i)
{
    int j = 1;
    ListNode* cur = head->next;
    if (i == 0)return head;
    if (i < 1)return NULL;
    while (cur && j < i)
    {
        cur = cur->next;
        j++;
    }
    return cur;
}

6.4插入操作

void Insert(ListNode* head, int i, int data)
{
    ListNode* pre = getElem(head, i - 1);
    ListNode* cur = (ListNode*)malloc(sizeof(ListNode));
    cur->data = data;
    cur->next = pre->next;
    pre->next = cur;
}

6.5删除操作

? ? ?将链表的第i个结点删除

void Delete(ListNode* head, int i) {
    if (i<1 || i>Length(head))return;
    ListNode* pre = getElem(head, i - 1);
    ListNode* cur = pre->next;
    pre->next = cur->next;
    free(cur);
}

6.6判空操作

bool Empty(ListNode* head) {
    if (head->next == NULL) {
        printf("Head is null\n");
        return true;
    }
    else {
        printf("Head is not null\n");
        return false;
    }
}