【备战春招】第17天 嵌入式工程师学习笔记

课程信息

• 课程名称：物联网/嵌入式工程师
• 章节名称：第5周之第二讲 1-7 单向链表之逆序,清除链表
• 讲师姓名：大白老师

课程内容概述

1. 简介

本节介绍了C语言中的单向链表之逆序,清除链表。

逆序就是把链表中现有的数据，按照相反的顺序来进行存储。例如,原始存储数据为1 3 5 7 9。逆序之后的存储数据为9,7,5,3,1。

清除链表就是把链表中所有的结点(包括头节点）都删除。

2. 图形操作

• 逆序

• 清除链表

3. 代码示例

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

#define SIZE 9
typedef int datatype_t;

typedef struct node {
    int data;
    struct node *next;
} linknode_t;

// 创建
linknode_t *create_empty_linklist() {
    linknode_t *head = malloc(sizeof(linknode_t));
    if (NULL == head) {
        printf("malloc fail!\n");
        return NULL;
    }
    memset(head, 0, sizeof(linknode_t));
    return head;
}

// 头插法
void insert_head_linklist(linknode_t *head, datatype_t data) {
    if (NULL == head) {
        printf("head is NULL point!\n");
        return;
    }
    linknode_t *temp = malloc(sizeof(linknode_t));
    if (NULL == temp) {
        printf("malloc fail!\n");
        return;
    }
    temp->data = data;
    temp->next = head->next;
    head->next = temp;
    return;
}

// 尾插法
void insert_tail_linklist(linknode_t *head, datatype_t data) {
    if (NULL == head) {
        printf("head is NULL point!\n");
        return;
    }
    linknode_t *temp = malloc(sizeof(linknode_t));
    if (NULL == temp) {
        printf("malloc fail!\n");
        return;
    }
    temp->data = data;
    linknode_t *p = head;
    while (p->next != NULL) {
        p = p->next;
    }
    temp->next = p->next;
    p->next = temp;
    return;
}

// 有序插入  大到小的顺序
void insert_order_linklist(linknode_t *head, datatype_t data) {
    if (NULL == head) {
        printf("head is NULL point!\n");
        return;
    }
    linknode_t *temp = malloc(sizeof(linknode_t));
    if (NULL == temp) {
        printf("malloc fail!\n");
        return;
    }
    temp->data = data;
    linknode_t *p = head;
    while (p->next != NULL && temp->data < p->next->data) {
        p = p->next;
    }
    temp->next = p->next;
    p->next = temp;
    return;

}

// 输出
void printf_data_linklist(linknode_t *head) {
    if (NULL == head) {
        printf("head is NULL point!\n");
        return;
    }
    linknode_t *p = head;
    while (p->next != NULL) {
        printf("%d ", p->next->data);
        p = p->next;
    }
    printf("\n");
    return;
}

// 判空
int is_empty_linklist(linknode_t *head) {
    return head->next == NULL ? 1 : 0;
}

// 删除
int delete_data_linklist(linknode_t *head, datatype_t data) {
    linknode_t *p = NULL;
    linknode_t *q = NULL;
    int flag = 0;

    if (is_empty_linklist(head)) {
        return -1;
    }

    p = head;
    while (p->next != NULL) {
        //找到了要删除的结点
        if (p->next->data == data) {
            //保存要删除结点的地址
            q = p->next;
            p->next = q->next;
            free(q);
            q = NULL;
            flag = 1;

        } else {
            p = p->next;
        }
    }
    //若是删除数据不存在，返回-2
    if (flag == 0) {
        return -2;
    } else {
        printf("delete %d is successful!\n", data);
    }
    return flag;
}

// 逆序
void reverse_data_linklist(linknode_t *head) {
    if (NULL == head) {
        printf("链表为空!\n");
        return;
    }
    if (NULL == head->next || NULL == head->next->next) {
        return;
    }
    linknode_t *p = NULL;
    linknode_t *q = NULL;

    p = head->next->next; //保存第二节点之后的链表信息
    head->next->next = NULL;
    while (p != NULL) {
        q = p->next;
        p->next = head->next;
        head->next = p;
        p = q;
    }
    return;
}

// 清除
void clear_up_linklist(linknode_t *head) {
    if (NULL == head) {
        printf("链表为空!\n");
        return;
    }
    linknode_t *p = head;
    linknode_t *q = NULL;
    while (NULL != p) {
        q = p->next;
        printf_data_linklist(p);
        free(p);
        p = q;
    }
    return;
}

int main() {
    int num = 0, ret = 0;
    linknode_t *head = NULL;
    datatype_t data[SIZE] = {1, 5, 3, 7, 9, 5, 8, 5, 3};
    head = create_empty_linklist();


    for (int i = 0; i < SIZE; i++) {
        insert_order_linklist(head, data[i]);
    }
    printf_data_linklist(head);

    //
    printf("please input you will delete data:\n");
    scanf("%d", &num);
    ret = delete_data_linklist(head, num);
    if (ret < 0) {
        printf("data is not exist or is empty!\n");
        return -1;
    }
    printf_data_linklist(head);

    // 逆序
    reverse_data_linklist(head);
    printf_data_linklist(head);

    // 清除
    clear_up_linklist(head);

    return 0;
}

运行结果

9 8 7 5 5 5 3 3 1
please input you will delete data:
7
delete 7 is successful!
9 8 5 5 5 3 3 1
1 3 3 5 5 5 8 9
1 3 3 5 5 5 8 9
3 3 5 5 5 8 9
3 5 5 5 8 9
5 5 5 8 9
5 5 8 9
5 8 9
8 9
9

学习心得

C语言中的数据结构，实践练习了单向链表之逆序,清除链表，感觉很有收获。

课程截图

1. 示例