学习笔记

[C指针]指针与结构体：完整源码 C语言 实现 单链表

https://www.jianshu.com/p/160a239086ae

本文结构

getNode源码
getNode内存示意图
deleteN源码
deleteN内存示意图

getNode 源码

Node * getNode(LinkedList * list, COMPARE compare, void * data) {
    Node * node = list->head;
    while(node != NULL) {
        if(compare(node->data, data) == 0) {
            return node;
        }
        node = node->next;
    }
    return NULL;

}

getNode 内存示意图

• node = node->next; ，只是在不断改写node变量的值

node等于node的next的本质.png

• compare(node->data, data) == 0

(参见学习笔记链接中的完整源码)
Node * getNode(LinkedList * list, COMPARE compare, void * data) {}
首先，是函数指针 typedef int (*COMPARE)(void *, void *);
接着，是结构体指针 Employee *sally = (Employee*) malloc(sizeof(Employee));
然后，是调用语句 Node * node = getNode(&linkedList, (COMPARE)compareEmployee, sally);
再看，compare(node->data, data) == 0 中的 node->data 以及 data 都是结构体指针
node->data 对应蓝色的那根箭头
data 对应红色那根箭头
(箭头实际都是不存在的，重点是都可以寻址到0x200)

image.png

• 显示查找到的结点 displayEmployee((Employee *)node->data);

node->data 指向真正的结构体，但是它是void *，需要进行强制类型转换，在前面加上(Employee *)

displayEmployee((Employee *)node->data);

deleteN源码

void deleteN(LinkedList * list, Node * node) {
    if(node == list->head) {
        if(list->head == list->tail) {
            list->head = NULL;
            list->tail = NULL;
        } else {
            list->head = list->head->next;
        }   
    } else {        
        Node * tmp = list->head;
        while(tmp != NULL && tmp->next != node) {
            tmp = tmp->next;
        }
        if(tmp != NULL) {
            tmp->next = node->next; 
        }   
        if(tmp->next == NULL) {
            list->tail = tmp;
        }
    }
    free(node);

}

deleteN 算法结构

1、要删除的结点是头结点
1.1 头结点是唯一的结点
1.2 头结点不是唯一的结点
2、要删除的结点不是头结点

• 边界分析：如果要删除的不是头结点，而是尾结点

tmp->next = node->next; 本质就是 tmp->next = NULL；
再加个 if(tmp->next == NULL) {} 设置新的尾结点指针；

下面专门写了一组删除尾结点的用例

边界分析：如果要删除的不是头结点，而是尾结点

deleteN内存示意图

• deleteN 链表删除结点变化情况

void deleteN(LinkedList * list, Node * node){}node 是结点指针，不是结构体指针

node 是结点指针
① tmp->next = node->next; 写内存操作
② free(node); ，是释放结点，不是释放结构体 删除 deleteN

• 链表结点删除之后，结构体依旧存在

如果想要释放黄色部分结构体占用的内存，要写 free(sally)
sally 是Employee *sally = (Employee*) malloc(sizeof(Employee));

链表结点删除之后，结构体依旧存在

完整源码（用例是删除尾结点）

运行结果

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

typedef void (*DISPLAY)(void *);
typedef int (*COMPARE)(void *, void *);

typedef struct _employee {
    char name[30];
    int age;
} Employee;

int compareEmployee(Employee * e1, Employee * e2){
    return strcmp(e1->name, e2->name);
}

void displayEmployee(Employee * employee){
    printf("%s,%d.\n", employee->name, employee->age);
}

typedef struct _node {
    void * data;
    struct _node * next;
}Node;

typedef struct _linkedList {
    Node * head;
    Node * tail;
} LinkedList;

void initializeList(LinkedList * list) {
    list->head = NULL;
    list->tail = NULL;
}

void addHead(LinkedList * list, void * data) {
    Node * node = (Node *) malloc(sizeof(Node));
    node->data = data;
    if(list-> head == NULL) {
        list->tail = node;
        node->next = NULL;
    } else {
        node->next = list->head;
    }
    list->head = node;
}


void addTail(LinkedList * list, void * data) {
    Node * node = (Node *) malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    if(list->head == NULL) {
        list->head = node;
    } else {
        list->tail->next = node;
    }
    list->tail = node;
}


void displayLinkedList(LinkedList * list, DISPLAY display) {
    Node * node = list->head;
    while(node != NULL) {
        if(node == list->head) printf("Head: ");
        if(node == list->tail) printf("Tail:");
        display(node->data);
        node = node->next;
    }
}


Node * getNode(LinkedList * list, COMPARE compare, void * data) {
    Node * node = list->head;
    while(node != NULL) {
        if(compare(node->data, data) == 0) {
            return node;
        }
        node = node->next;
    }
    return NULL;

}

void deleteN(LinkedList * list, Node * node) {
    if(node == list->head) {
        if(list->head == list->tail) {
            list->head = NULL;
            list->tail = NULL;
        } else {
            list->head = list->head->next;
        }   
    } else {        
        Node * tmp = list->head;
        while(tmp != NULL && tmp->next != node) {
            tmp = tmp->next;
        }
        if(tmp != NULL) {
            tmp->next = node->next; 
        }   
        if(tmp->next == NULL) {
            list->tail = tmp;
        }
    }
    free(node);

}


int main()
{
    LinkedList linkedList;
    
    Employee *samuel = (Employee*) malloc(sizeof(Employee));
    strcpy(samuel->name, "Samuel");
    samuel->age = 32;
    
    Employee *sally = (Employee*) malloc(sizeof(Employee));
    strcpy(sally->name, "sally");
    sally->age = 28;
    
    Employee *susan = (Employee*) malloc(sizeof(Employee));
    strcpy(susan->name, "susan");
    susan->age = 45;
    
    initializeList(&linkedList);
    
    addHead(&linkedList, samuel);
    addHead(&linkedList, sally);
    addHead(&linkedList, susan);
    
    displayLinkedList(&linkedList, (DISPLAY)displayEmployee);
    
    Node * node = getNode(&linkedList, (COMPARE)compareEmployee, samuel);
    displayEmployee((Employee *)node->data);
    
    printf("--Message:Delete samuel:\n");
    deleteN(&linkedList, node);
    displayLinkedList(&linkedList, (DISPLAY)displayEmployee);
    
    
    printf("--Message:addTail(sara):\n");
    Employee *sara = (Employee*) malloc(sizeof(Employee));
    strcpy(sara->name, "sara");
    sara->age = 22;
    addTail(&linkedList, sara);
    displayLinkedList(&linkedList, (DISPLAY)displayEmployee);

    return 0;
}