数据结构——链表——单链表（C语言实现）

数据结构——链表——单链表（C语言实现）

引用

CSDN

1.

https://m.blog.csdn.net/xiahongtao111/article/details/143866639

单链表初始化

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<string.h>
#define MAXSIZE 100
typedef int Elemtype;

// 单链表节点结构
typedef struct Node {
    Elemtype data;
    struct Node* next;
} Node;

// 初始化链表
Node* initList() {
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = 0;
    head->next = NULL;
    return head;
}

int main() {
    Node* List = initList();
    return 1;
}

单链表头插法

// 头插法
int insertHead(Node* L, Elemtype e) {
    Node* p = (Node*)malloc(sizeof(Node));
    p->data = e;
    p->next = L->next;
    L->next = p;
}

int main() {
    Node* list = initList();
    insertHead(list, 10);
    insertHead(list, 20);
}

单链表遍历

注意：下面的L指的是头节点，头节点的next是首元节点，才是链表存数据的第一个

// 遍历链表
void listNode(Node* L) {
    Node* p = L->next; // L为头节点，L的next指向的是首元节点
    while (p != NULL) {
        printf("%d", p->data);
        p = p->next;
    }
    printf("\n");
}

单链表尾插法

相比于头插法，要先找到尾部，找到节点next指向是NULL的节点

// 获取尾节点
Node* get_tail(Node* L) {
    Node* p = L;
    while (p->next != NULL) {
        p = p->next;
    }
    return p;
}

// 尾插
Node* insertTail(Node* tail, Elemtype e) {
    Node* p = (Node*)malloc(sizeof(Node));
    p->data = e;
    tail->next = p;
    p->next = NULL;
    return p;
}

单链表在指定位置插入数据

// 在指定位置插入数据
int insertNode(Node* L, int pos, Elemtype e) { // L链表，pos是插入的位置，e是插入的新数据
    // 用来保存插入位置的前驱节点
    Node* p = L;
    int i = 0;
    // 遍历链表找到插入位置的前驱节点
    while (i < pos - 1) {
        p = p->next;
        i++;
        if (p == NULL) {
            return 0;
        }
    }
    Node* q = (Node*)malloc(sizeof(Node));
    q->data = e;
    q->next = p->next;
    p->next = q;
    return 1;
}

单链表删除节点

找到要删除节点的前置节点p
用指针q记录要删除的节点
通过改变p的后继节点实现删除
释放删除节点的空间

// 删除节点
int deleteNode(Node* L, int pos) {
    // 要删除节点的前驱节点
    Node* p = L;
    int i = 0;
    // 遍历链表，找到要删除节点的前驱节点
    while (i < pos - 1) {
        p = p->next;
        i++;
        if (p == NULL) {
            return 0;
        }
    }
    if (p->next == NULL) {
        printf("要删除的位置错误\n");
        return 0;
    }
    // q指向要删除的节点
    Node* q = p->next;
    // 让要删除节点的前驱指向要删除节点的后继
    p->next = q->next;
    // 释放要删除节点的空间
    free(q);
    return 1;
}

单链表获取链表长度

// 获取链表长度
int listlength(Node* L) {
    Node* p = L;
    int len = 0;
    while (p != NULL) {
        p = p->next;
        len++;
    }
    return len;
}

单链表释放链表

指针p指向头节点后的第一个节点
判断指针p是否指向空节点
如果p不为空，用指针q记录指针p的后继节点
释放指针p指向的节点
指针p合指针q指向同一个节点，循环上面操作

// 释放链表
void freeList(Node* L) { // 传进来链表，也就是头节点
    Node* p = L->next;
    Node* q;
    while (p != NULL) {
        q = p->next;
        free(p);
        p = q;
    }
    L->next = NULL; // 头节点指向空
}

单链表应用——反转链表

先拿first指向空值，再拿second指向1，third指向second所指向的下一个节点
然后让second指向空值
然后挪动三个指针
再将此时的2指针指向改变
依次进行，直到second指向空值
再安一个头节点

// 反转链表
Node* reverseList(Node* head) {
    Node *first = NULL;
    Node *second = head->next;
    Node *third;
    while (second != NULL) {
        third = second->next;
        second->next = first;
        first = second;
        second = third;
    }
    Node *hd = initList();
    hd->next = first;
    return hd;
}

int main(int argc, char const *argv[]) {
    Node *list = initList();
    
    Node *tail = get_tail(list);
    
    tail = insertTail(tail, 1);
    tail = insertTail(tail, 2);
    tail = insertTail(tail, 3);
    tail = insertTail(tail, 4);
    tail = insertTail(tail, 5);
    tail = insertTail(tail, 6);
    listNode(list);
    Node* reverse = reverseList(list);
    listNode(reverse);
    
    return 0;
}