single link list - yaokun123/php-wiki GitHub Wiki

单链表

一、单链表

int main(){
    struct Test{
        int x;
        int y;
        //struct Test test;//这样编译器会报错
        struct Test *test;
    };
    return 0;
}

二、单链表结构的申明

struct Book{
    char title[128];
    char author[40];
    struct Book *next;
};

三、在单链表中插入元素

  • 头插法 
#include<stdio.h>
#include<stdlib.h>

//单链表

/**
 链表是一种常见的基础数据结构。根据需求，我们可以构造出单链表、双链表、循环链表和块状链表等。链表的出现很大程度上弥补了数组的先天不足。
 */


//单链表结构的申明
struct Book{
    char title[128];
    char author[40];
    struct Book *next;
};
void getInput(struct Book *book){
    printf("请输入书名：");
    scanf("%s",book->title);
    printf("请输入作者：");
    scanf("%s",book->author);
    
}
void addBook(struct Book **library){
    struct Book *book,*temp;
    
    book = (struct Book *)malloc(sizeof(struct Book));
    if(book == NULL){
        printf("内存分配失败了!\n");
        exit(1);
    }
    
    getInput(book);
    
    if(*library != NULL){
        temp = *library;
        *library = book;
        book->next = temp;
    }else{
        *library = book;
        book->next = NULL;
    }
}
void printLibrary(struct Book *library){
    struct Book *book;
    int count = 1;
    book = library;
    while (book != NULL){
        printf("Book%d:\n",count);
        printf("书名：%s\n",book->title);
        printf("作者：%s\n",book->author);
        book = book->next;
        count++;
    }
}

void releaseLibrary(struct Book **library){
    struct Book *temp;
    while (book!=NULL) {
        temp = *library;
        *library = (*library)->next;
        free(temp)
    }
}
int main(){
    struct Book *library = NULL;//空链表
    
    while (1) {
        char ch;
        printf("请问是否需要录入书籍信息(Y/N):");
        do{
            ch = getchar();
        }while(ch != 'Y' && ch !='N');
            
        if(ch == 'Y'){
            addBook(&library);
        }else{
            break;
        }
    }
    
    printf("请问是否需要打印图书信息(Y/N)");
    char ch;
    do{
        ch = getchar();
    }while(ch != 'Y' && ch !='N');
        
    if(ch == 'Y'){
        printLibrary(library);
    }
    releaseLibrary(&library);
    return 0;
}

四、单链表的尾插法

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

//单链表

/**
 链表是一种常见的基础数据结构。根据需求，我们可以构造出单链表、双链表、循环链表和块状链表等。链表的出现很大程度上弥补了数组的先天不足。
 */


//单链表结构的申明
struct Book{
    char title[128];
    char author[40];
    struct Book *next;
};
void getInput(struct Book *book){
    printf("请输入书名：");
    scanf("%s",book->title);
    printf("请输入作者：");
    scanf("%s",book->author);
    
}
void addBook(struct Book **library){
    struct Book *book,*temp;
    
    book = (struct Book *)malloc(sizeof(struct Book));
    if(book == NULL){
        printf("内存分配失败了!\n");
        exit(1);
    }
    
    getInput(book);
    
    if(*library != NULL){
        temp = *library;
        //定位单链表的尾部位置
        while(temp->next != NULL){
            temp = temp->next;
        }
        //插入数据
        temp->next = book;
        book->next = NULL;
    }else{
        *library = book;
        book->next = NULL;
    }
}
void printLibrary(struct Book *library){
    struct Book *book;
    int count = 1;
    book = library;
    while (book != NULL){
        printf("Book%d:\n",count);
        printf("书名：%s\n",book->title);
        printf("作者：%s\n",book->author);
        book = book->next;
        count++;
    }
}

void releaseLibrary(struct Book **library){
    struct Book *temp;
    while (*library!=NULL) {
        temp = *library;
        *library = (*library)->next;
        free(temp);
    }
}
int main(){
    struct Book *library = NULL;//空链表
    
    while (1) {
        char ch;
        printf("请问是否需要录入书籍信息(Y/N):");
        do{
            ch = getchar();
        }while(ch != 'Y' && ch !='N');
        
        if(ch == 'Y'){
            addBook(&library);
        }else{
            break;
        }
    }
    
    printf("请问是否需要打印图书信息(Y/N)");
    char ch;
    do{
        ch = getchar();
    }while(ch != 'Y' && ch !='N');
    
    if(ch == 'Y'){
        printLibrary(library);
    }
    releaseLibrary(&library);
    return 0;
}

以上程序执行效率较低，就是每次在尾部插入数据的时候都要便利一下整个链表。
修改如下：记录单链表尾部的位置

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

//单链表

/**
 链表是一种常见的基础数据结构。根据需求，我们可以构造出单链表、双链表、循环链表和块状链表等。链表的出现很大程度上弥补了数组的先天不足。
 */


//单链表结构的申明
struct Book{
    char title[128];
    char author[40];
    struct Book *next;
};
void getInput(struct Book *book){
    printf("请输入书名：");
    scanf("%s",book->title);
    printf("请输入作者：");
    scanf("%s",book->author);
    
}
void addBook(struct Book **library){
    struct Book *book;
    static struct Book *tail;//记录尾部位置
    
    book = (struct Book *)malloc(sizeof(struct Book));
    if(book == NULL){
        printf("内存分配失败了!\n");
        exit(1);
    }
    
    getInput(book);
    
    if(*library != NULL){
        tail->next = book;
        book->next = NULL;
    }else{
        *library = book;
        book->next = NULL;
    }
    tail = book;
}
void printLibrary(struct Book *library){
    struct Book *book;
    int count = 1;
    book = library;
    while (book != NULL){
        printf("Book%d:\n",count);
        printf("书名：%s\n",book->title);
        printf("作者：%s\n",book->author);
        book = book->next;
        count++;
    }
}

void releaseLibrary(struct Book **library){
    struct Book *temp;
    while (*library!=NULL) {
        temp = *library;
        *library = (*library)->next;
        free(temp);
    }
}
int main(){
    struct Book *library = NULL;//空链表
    
    while (1) {
        char ch;
        printf("请问是否需要录入书籍信息(Y/N):");
        do{
            ch = getchar();
        }while(ch != 'Y' && ch !='N');
        
        if(ch == 'Y'){
            addBook(&library);
        }else{
            break;
        }
    }
    
    printf("请问是否需要打印图书信息(Y/N)");
    char ch;
    do{
        ch = getchar();
    }while(ch != 'Y' && ch !='N');
    
    if(ch == 'Y'){
        printLibrary(library);
    }
    releaseLibrary(&library);
    return 0;
}

五、单链表的搜索

单链表的搜索就是循环遍历单链表

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//搜索单链表

/**
 有时候我们可能会对单链表进行搜索操作，比如输入书名或作者，就可以找到相关的节点数据
 
 */


struct Book{
    char title[128];
    char author[40];
    struct Book *next;
};
void getInput(struct Book *book){
    printf("请输入书名：");
    scanf("%s",book->title);
    printf("请输入作者：");
    scanf("%s",book->author);
    
}
void addBook(struct Book **library){
    struct Book *book;
    static struct Book *tail;//记录尾部位置
    
    book = (struct Book *)malloc(sizeof(struct Book));
    if(book == NULL){
        printf("内存分配失败了!\n");
        exit(1);
    }
    
    getInput(book);
    
    if(*library != NULL){
        tail->next = book;
        book->next = NULL;
    }else{
        *library = book;
        book->next = NULL;
    }
    tail = book;
}
void printLibrary(struct Book *library){
    struct Book *book;
    int count = 1;
    book = library;
    while (book != NULL){
        printf("Book%d:\n",count);
        printf("书名：%s\n",book->title);
        printf("作者：%s\n",book->author);
        book = book->next;
        count++;
    }
}

void releaseLibrary(struct Book **library){
    struct Book *temp;
    while (*library!=NULL) {
        temp = *library;
        *library = (*library)->next;
        free(temp);
    }
}

struct Book *searchBook(struct Book *library,char *target){
    struct Book *book;
    book = library;
    while (book!=NULL) {
        if(strcmp(book->title,target) || strcmp(book->author,target)){
            break;
        }
        book = book->next;
    }
    return book;
}

void printBook(struct Book *book){
    printf("书名：%s\n",book->title);
    printf("作者：%s\n",book->author);
}
int main(){
    struct Book *library = NULL;//空链表
    struct Book *book;
    char input[128];
    
    while (1) {
        char ch;
        printf("请问是否需要录入书籍信息(Y/N):");
        do{
            ch = getchar();
        }while(ch != 'Y' && ch !='N');
        
        if(ch == 'Y'){
            addBook(&library);
        }else{
            break;
        }
    }
    
    printf("请问是否需要打印图书信息(Y/N)");
    char ch;
    do{
        ch = getchar();
    }while(ch != 'Y' && ch !='N');
    
    if(ch == 'Y'){
        printLibrary(library);
    }
    printf("请输入书名或作者：\n");
    scanf("%s",input);
    book = searchBook(library,input);
    if(book == NULL){
        printf("很抱歉没有找到！");
    }else{
        do{
            printf("已找到符合条件的图书...");
            printBook(book);
        }while ((book = searchBook(book->next,input)) != NULL);
    }
    
    releaseLibrary(&library);
    return 0;
}

六、单链表的优势(中间插入)

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

struct Node{
    int value;
    struct Node *next;
};

void insertNode(struct Node **head,int value){
    struct Node *previous;
    struct Node *current;
    struct Node *new;
    
    current = *head;
    previous = NULL;
    while(current != NULL && current->value < value){
        previous = current;
        current = current->next;
    }
    
    new = (struct Node *)malloc(sizeof(struct Node));
    if(new == NULL){
        printf("内存分配失败！\n");
        exit(1);
    }
    new->value = value;
    new->next = current;
    
    if(previous == NULL){
        *head = new;
    }else{
        previous->next = new;
    }
}

void printNode(struct Node *head){
    struct Node *current;
    
    current = head;
    while (current != NULL) {
        printf("%d ",current->value);
        current = current->next;
    }
    printf("\n");
}


int main(){
    struct Node *head = NULL;
    int input;
    
    while (1) {
        printf("请输入一个整数(输入-1表示结束):");
        scanf("%d",&input);
        if(input == -1){
            break;
        }
        insertNode(&head,input);
        printNode(head);
    }
    return 0;
}

七、单链表的删除

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

struct Node{
    int value;
    struct Node *next;
};

void insertNode(struct Node **head,int value){
    struct Node *previous;
    struct Node *current;
    struct Node *new;
    
    current = *head;
    previous = NULL;
    while(current != NULL && current->value < value){
        previous = current;
        current = current->next;
    }
    
    new = (struct Node *)malloc(sizeof(struct Node));
    if(new == NULL){
        printf("内存分配失败！\n");
        exit(1);
    }
    new->value = value;
    new->next = current;
    
    if(previous == NULL){
        *head = new;
    }else{
        previous->next = new;
    }
}

void printNode(struct Node *head){
    struct Node *current;
    
    current = head;
    while (current != NULL) {
        printf("%d ",current->value);
        current = current->next;
    }
    printf("\n");
}

void deletedNode(struct Node **head,int value){
    struct Node *previous;
    struct Node *current;
    
    current = *head;
    previous = NULL;
    
    while (current != NULL && current->value != value) {
        previous = current;
        current = current->next;
    }
    
    if(current == NULL){
        printf("找不到匹配的节点");
        return;
    }else{
        if(previous == NULL){
            *head = current->next;
        }else{
            previous->next = current->next;
        }
        free(current);
    }
}


int main(){
    struct Node *head = NULL;
    int input;
    
    printf("开始测试插入整数...");
    while (1) {
        printf("请输入一个整数(输入-1表示结束):");
        scanf("%d",&input);
        if(input == -1){
            break;
        }
        insertNode(&head,input);
        printNode(head);
    }
    
    printf("开始测试删除整数...");
    while (1) {
        printf("请输入一个整数(输入-1表示结束):");
        scanf("%d",&input);
        if(input == -1){
            break;
        }
        deletedNode(&head,input);
        printNode(head);
    }
    return 0;
}
⚠️ **GitHub.com Fallback** ⚠️