Day15

链表

• 链表实现了，内存零碎数据的有效组织。比如，当我们用 malloc 来进行内存申请的时候，当内存足够，但是由于碎片太多，没有连续内存时，只能以申请失败而告终，而用链表这种数据结构来组织数据，就可以解决上类问题

静态链表

注意: 在企业开发中,一般不会使用静态链表

#include <stdio.h>
// 定义一个节点
typedef struct node
{
    int data; //专门用于存储数据
    struct node *next;  //专门用于实现链接的
} Node;
int main()
{
    /*
     * 静态链表
     *
     * 将一个内存空间划分为很多小的存储空间,然后取内存中查找小的存储空间
     * 再开辟多个小的存储空间,最后用指针将所有开辟的小的存储空间连起来,组成
     * 一个整体
     *
     */

    //1. 定义三个结构体
    Node a;
    Node b;
    Node c;
    //2. 让三个结构体保存数据
    a.data  =1;
    b.data  =3;
    c.data  =5;
    //3. 将三个结构体链接起来
    a.next = &b;
    b.next = &c;
    //如果指针没有值,那么可以赋值NULL,明确告诉系统该指针没有值
    //如果一个指针没有值,也没有赋值NULL,那么这个指针是野指针,不要操作野指针
    c.next = NULL;
    //4. 定义链表的头指针
    Node *head = &a;
    return 0;
}

动态链表

• 动态尾插法
  注意: 尾插法新节点始终插入在头节点的后面

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

typedef struct node
{
    int data; //专门用于存储数据
    struct node *next;  //专门用于实现链接的
} Node;

Node* createEmpty();
void insertNode(Node *head, int num);
void printList(Node *head);
void destroyList(Node *head);
int listLength(Node *head);
Node* findNode(Node *head, int key);
void deleteNode(Node *head, Node *node);

int main()
{
    /*
     * 动态链表尾插法
     * 规则: 1.让新节点的下一个节点等于头节点的下一个节点
     *       2.让头节点的下一个节点等于新节点
     * 新节点永远都插到头节点的后面
     */

    //1. 创建一个空链表
    Node *head = createEmpty();
    //2. 插入新节点
    insertNode(head, 1);
    insertNode(head, 3);
    insertNode(head, 5);
    insertNode(head, 7);
    //3. 遍历节点
//    printList(head);
//    int len = listLength(head);
//    printf("len = %i\n", len);

//    Node *cur = findNode(head, 5);
//    printf("%i\n", cur->data);
    Node *cur = findNode(head, 5);
    deleteNode(head,cur);
    printList(head);

    return 0;
}
/**
 * @brief deleteNode 删除指定的节点
 * @param head 头节点
 * @param node 要删除的节点
 */
void deleteNode(Node *head, Node *node){
    //1. 找到需要删除节点的上一个节点
    while (head->next != node) {
        head = head->next;
    }
    //2. 将删除的节点上一个节点的next改为删除节点的下一个节点
    head->next = node->next;
    //3. 删除当前节点
    free(node);
}


/**
 * @brief findNode 查找指定节点的函数
 * @param head  头节点
 * @param key   节点中的数据
 * @return
 */
Node* findNode(Node *head, int key){
    //注意: 不要头节点
    head = head->next;
    while (head != NULL) {
        if(head->data == key){
            return head;
        }else {
            head = head->next;
        }
    }
    return NULL;
}


/**
 * @brief listLength 计算链表长度的函数
 * @param head 头节点
 * @return
 */
int listLength(Node *head){
    //1. 定义一个变量记录节点的个数(注意点: 头节点不算在内)
    int count = 0;
    //2. 定义一个指针指向当前节点
    Node *cur = head->next;
    while(cur != NULL){
        count++;
        cur = cur->next;
    }
    return count;
}


/**
 * @brief destroyList 销毁链表的函数
 * @param head 头节点
 */
void destroyList(Node *head){
    Node *cur = NULL;
    while (head != NULL) {
        cur = head->next;
        free(head);
        head = cur;
    }
}

/**
 * @brief printList 遍历链表
 * @param head 链表的头指针
 */
void printList(Node *head){
    // 头节点对我们来说没有用,头节点没有保存数据
   //1. 取出头节点的下一个节点
    Node *cur = head->next;
    //2. 判断是否为NULL,如果不为NULL就开始遍历
    while(cur != NULL){
        //2.1 取出当前数据打印
        printf("data = %i\n", cur->data);
        //2.2 让当前节点往后移动
        cur = cur->next;
    }
}

/**
 * @brief insertNode 封装一个插入新节点的函数
 * @param head 头节点
 * @param num  插入新节点的数据
 */
void insertNode(Node *head, int num){
    //1. 创建一个新节点
    Node *node  = (Node *)malloc(sizeof(Node));
    //2. 将数据保存到新节点中
    node->data = num;
    //3. 插入节点
    //3.1 将新节点的下一个节点 等于 头节点的下一个节点
    node->next = head->next;
    //3.2 让头节点的下一个节点 等于 新节点
    head->next = node;
}


/**创建空链表的函数
 * @brief createList
 * @return
 */
Node* createEmpty(){
    //1. 定义头指针
    Node *head  = NULL;
    // 空链表只有头指针和一个节点,并且节点没有数据,也有没有下一个节点
    //2. 创建一个空节点,并赋值给头指针
    head = (Node *)malloc(sizeof(Node));
    head->next = NULL;
    //3.返回头指针
    return head;
}

• 动态链表头插法
  精髓: 定义变量记录新节点的上一个节点
将新节点添加到上一个节点的后面,让新节点成为下一个节点的上一个节点