C语言 单链表介绍和操作

Question

一、单链表

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;
}