目录

链表开篇

作者收录于类别考研

2024-07-08 2024-07-08 约 1495 字预计阅读 3 分钟

目录

链表单链表

c

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

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

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 插入新节点到链表的末尾
void insert(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }

    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

// 删除值为data的节点
void deleteNode(Node** head, int data) {
    if (*head == NULL) return;

    Node* temp = *head;

    if (temp->data == data) {
        *head = temp->next;
        free(temp);
        return;
    }

    Node* prev = NULL;
    while (temp != NULL && temp->data != data) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) return;

    prev->next = temp->next;
    free(temp);
}

// 打印链表
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// 释放链表内存 && 删除
void freeList(Node* head) {
    Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}


int Length(Node * list){
    int i=0;
    while(list!=NULL){
        list=list->next;
        i++;
    }
    return i;
}
int main() {
    int len;
    Node* head = NULL;

    insert(&head, 10);
    insert(&head, 20);
    insert(&head, 30);


    printf("链表内容：\n");
    printList(head);
    //表长
    len=Length(head);
    printf("表长:%d\n",len);

    printf("删除节点20后的链表内容：\n");
    deleteNode(&head, 20);
    printList(head);

    //表长
    len=Length(head);
    printf("表长:%d\n",len);


    // 清空链表并释放内存
    freeList(head);
    return 0;
}

链表双链表

c

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

typedef struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
} Node;

对比单链表，多一个前驱

c

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

// 插入新节点到链表的末尾
void insert(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }

    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

// 删除值为data的节点
void deleteNode(Node** head, int data) {
    if (*head == NULL) return;

    Node* temp = *head;

    // 如果要删除的是头节点
    if (temp->data == data) {
        *head = temp->next;
        if (*head != NULL) {
            (*head)->prev = NULL;
        }
        free(temp);
        return;
    }

    // 查找要删除的节点
    while (temp != NULL && temp->data != data) {
        temp = temp->next;
    }

    // 未找到值为data的节点
    if (temp == NULL) return;

    // 修改前驱和后继节点的指针
    if (temp->next != NULL) {
        temp->next->prev = temp->prev;
    }
    if (temp->prev != NULL) {
        temp->prev->next = temp->next;
    }

    // 释放节点内存
    free(temp);
}

// 打印链表
void printList(Node* head) {
    Node* temp = head;
    printf("正向打印链表：\n");
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// 反向打印链表
void printListReverse(Node* head) {
    Node* temp = head;
    if (temp == NULL) return;

    // 移动到链表末尾
    while (temp->next != NULL) {
        temp = temp->next;
    }

    printf("反向打印链表：\n");
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->prev;
    }
    printf("NULL\n");
}

// 释放链表内存
void freeList(Node* head) {
    Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

c

int main() {
    Node* head = NULL;

    insert(&head, 10);
    insert(&head, 20);
    insert(&head, 30);

    printf("链表内容：\n");
    printList(head);
    printListReverse(head);

    printf("删除节点20后的链表内容：\n");
    deleteNode(&head, 20);
    printList(head);
    printListReverse(head);

    // 清空链表并释放内存
    freeList(head);
    return 0;
}

链表循环链表

c

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = newNode; // 初始化时，节点指向自己
    return newNode;
}

// 插入新节点到链表的末尾
void insert(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }

    Node* temp = *head;
    while (temp->next != *head) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->next = *head;
}

// 删除值为data的节点
void deleteNode(Node** head, int data) {
    if (*head == NULL) return;

    Node* temp = *head;
    Node* prev = NULL;

    // 如果要删除的是头节点
    if (temp->data == data) {
        // 找到尾节点
        while (temp->next != *head) {
            temp = temp->next;
        }
        if (*head == (*head)->next) {
            free(*head);
            *head = NULL;
        } else {
            temp->next = (*head)->next;
            free(*head);
            *head = temp->next;
        }
        return;
    }

    temp = *head;
    while (temp->next != *head && temp->data != data) {
        prev = temp;
        temp = temp->next;
    }

    if (temp->data == data) {
        prev->next = temp->next;
        free(temp);
    }
}

// 打印链表
void printList(Node* head) {
    if (head == NULL) return;

    Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("(head)\n");
}

// 释放链表内存
void freeList(Node* head) {
    if (head == NULL) return;

    Node* temp = head;
    do {
        Node* nextNode = temp->next;
        free(temp);
        temp = nextNode;
    } while (temp != head);
}

链表循环双链表

c

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = newNode; // 初始化时，节点的next和prev指向自己
    newNode->prev = newNode;
    return newNode;
}

// 插入新节点到链表的末尾
void insert(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }

    Node* tail = (*head)->prev;

    tail->next = newNode;
    newNode->prev = tail;
    newNode->next = *head;
    (*head)->prev = newNode;
}

// 删除值为data的节点
void deleteNode(Node** head, int data) {
    if (*head == NULL) return;

    Node* temp = *head;

    // 如果要删除的是头节点
    if (temp->data == data) {
        if (temp->next == *head) {
            free(temp);
            *head = NULL;
        } else {
            Node* tail = temp->prev;
            *head = temp->next;
            (*head)->prev = tail;
            tail->next = *head;
            free(temp);
        }
        return;
    }

    temp = temp->next;
    while (temp != *head && temp->data != data) {
        temp = temp->next;
    }

    if (temp->data == data) {
        temp->prev->next = temp->next;
        temp->next->prev = temp->prev;
        free(temp);
    }
}

// 打印链表
void printList(Node* head) {
    if (head == NULL) return;

    Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("(head)\n");
}

// 反向打印链表
void printListReverse(Node* head) {
    if (head == NULL) return;

    Node* temp = head->prev;
    do {
        printf("%d -> ", temp->data);
        temp = temp->prev;
    } while (temp != head->prev);
    printf("(head)\n");
}

// 释放链表内存
void freeList(Node* head) {
    if (head == NULL) return;

    Node* temp = head;
    do {
        Node* nextNode = temp->next;
        free(temp);
        temp = nextNode;
    } while (temp != head);
}