C语言 单链表介绍和操作
一、单链表
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;
}
以上是 C语言 单链表介绍和操作 的全部内容， 来源链接： utcz.com/p/233748.html
