小甲鱼 P46 单链表2
小甲鱼 P46 单链表2
单链表---尾插法
核心代码:
if (*library != NULL)
{
temp = *library;
// 定位单链表的尾部位置
while (temp->next != NULL)
{
temp = temp->next;
}
//插入数据
temp->next = book;
book->next = NULL;//表示单链表结束
}
全部代码:
#include <stdio.h>
#include <stdlib.h>
//单链表声明
struct Book
{
//信息域
char title[128];
char author[40];
//指针域(指向下一个和它一样的节点)
struct Book *next;
};
void getInput(struct Book *book);
void addBook(struct Book **library);
void printLibrary(struct Book *library);
void releaseLibrary(struct Book **library);
void getInput(struct Book *book)
{
printf("请输入书名:");
scanf("%s", book->title);
printf("请输入作者:");
scanf("%s", book->author);
}
void addBook(struct Book **library)//参数library(head指针)是head指针的值,两层解引用
{
//**library参数:指向head指针,head指针的值,头结点,是一个地址
//下面的*library头指针:是原来的第一个结构体的地址
/* **library参数 = &library头指针
*library头指针 = &原来的第一个结构体
原来的第一个结构体 = NULL
*/
struct Book *book, *temp;//临时变量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//如果为NULL,空的单链表
{
*library = book;
book->next = NULL;
}
}
void printLibrary(struct Book *library)
{
struct Book *book;
int count = 1;
book = library;
while (book != NULL)
{
printf("Book%d: ", count);
printf("书名: %s", book->title);
printf("作者: %s", book->author);
putchar('\n');
book = book->next;//指向下一个节点
count++;
}
}
void releaseLibrary(struct Book **library)//参数library(head指针)是head指针的值,两层解引用
{
struct Book *temp;//临时变量
while (*library != NULL)//直到library头指针指向NULL
{
temp = *library;
*library = (*library)->next;
free(temp);
//如果先释放头指针,那么就没有意义了
//library = library->next;
//free(library);
}
}
int main(void)
{
//头指针 head, NULL, 空的单链表
struct Book *library = NULL;
int ch;
while (1)
{
printf("请问是否需要录入书籍信息(Y/N):");
do
{
ch = getchar();
}while(ch != 'Y' && ch != 'N');
if (ch == 'Y')
{
addBook(&library);
}
else
{
break;//退出死循环
}
}
printf("请问是否需要打印图书信息(Y/N):");
do
{
ch = getchar();
}while(ch != 'Y' && ch != 'N');
if (ch == 'Y')
{
printLibrary(library);
}
releaseLibrary(&library);
return 0;
}
优化单链表尾插法:(上面的方法是每一次都要遍历链表,找到最后一个)
核心代码:
void addBook(struct Book **library)//参数library(head指针)是head指针的值,两层解引用
{
//**library参数:指向head指针,head指针的值,头结点,是一个地址
//下面的*library头指针:是原来的第一个结构体的地址
/* **library参数 = &library头指针
*library头指针 = &原来的第一个结构体
原来的第一个结构体 = NULL
*/
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->book->NULL
tail->next = book;//tail是指向最后一个位置的
book->next = NULL;
}
else//如果为NULL,空的单链表
{
*library = book;
book->next = NULL;
}
tail = book;//将book设置为新的tail
}
全部代码:
#include <stdio.h>
#include <stdlib.h>
//单链表声明
struct Book
{
//信息域
char title[128];
char author[40];
//指针域(指向下一个和它一样的节点)
struct Book *next;
};
void getInput(struct Book *book);
void addBook(struct Book **library);
void printLibrary(struct Book *library);
void releaseLibrary(struct Book **library);
void getInput(struct Book *book)
{
printf("请输入书名:");
scanf("%s", book->title);
printf("请输入作者:");
scanf("%s", book->author);
}
void addBook(struct Book **library)//参数library(head指针)是head指针的值,两层解引用
{
//**library参数:指向head指针,head指针的值,头结点,是一个地址
//下面的*library头指针:是原来的第一个结构体的地址
/* **library参数 = &library头指针
*library头指针 = &原来的第一个结构体
原来的第一个结构体 = NULL
*/
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->book->NULL
tail->next = book;//tail是指向最后一个位置的
book->next = NULL;
}
else//如果为NULL,空的单链表
{
*library = book;
book->next = NULL;
}
tail = book;//将book设置为新的tail
}
void printLibrary(struct Book *library)
{
struct Book *book;
int count = 1;
book = library;
while (book != NULL)
{
printf("Book%d: ", count);
printf("书名: %s", book->title);
printf("作者: %s", book->author);
putchar('\n');
book = book->next;//指向下一个节点
count++;
}
}
void releaseLibrary(struct Book **library)//参数library(head指针)是head指针的值,两层解引用
{
struct Book *temp;//临时变量
while (*library != NULL)//直到library头指针指向NULL
{
temp = *library;
*library = (*library)->next;
free(temp);
//如果先释放头指针,那么就没有意义了
//library = library->next;
//free(library);
}
}
int main(void)
{
//头指针 head, NULL, 空的单链表
struct Book *library = NULL;
int ch;
while (1)
{
printf("请问是否需要录入书籍信息(Y/N):");
do
{
ch = getchar();
}while(ch != 'Y' && ch != 'N');
if (ch == 'Y')
{
addBook(&library);
}
else
{
break;//退出死循环
}
}
printf("请问是否需要打印图书信息(Y/N):");
do
{
ch = getchar();
}while(ch != 'Y' && ch != 'N');
if (ch == 'Y')
{
printLibrary(library);
}
releaseLibrary(&library);
return 0;
}
搜索单链表
比如输入书名或作者,就可以找到相关的节点数据。
核心代码:
struct Book *searchBook(struct Book *library, char *target)//target有可能是书名、作者
{
struct Book *book;
book = library;
while (book != NULL)//没有到尾巴
{
//对比,是否一致,两个相等返回0
if (!strcmp(book->title, target) || !strcmp(book->author, target))
{
break;//找不到就往下找,知道单链表结束
}
book = book->next;//让单链表继续
}
return book;//返回找到的节点指针
全部代码:
#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);
void addBook(struct Book **library);
void printLibrary(struct Book *library);
struct Book *searchBook(struct Book *library, char *target);
void printBook(struct Book *book);
void releaseLibrary(struct Book **library);
void getInput(struct Book *book)
{
printf("请输入书名:");
scanf("%s", book->title);
printf("请输入作者:");
scanf("%s", book->author);
}
void addBook(struct Book **library)//参数library(head指针)是head指针的值,两层解引用
{
//**library参数:指向head指针,head指针的值,头结点,是一个地址
//下面的*library头指针:是原来的第一个结构体的地址
/* **library参数 = &library头指针
*library头指针 = &原来的第一个结构体
原来的第一个结构体 = NULL
*/
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->book->NULL
tail->next = book;//tail是指向最后一个位置的
book->next = NULL;
}
else//如果为NULL,空的单链表
{
*library = book;
book->next = NULL;
}
tail = book;//将book设置为新的tail
}
void printLibrary(struct Book *library)
{
struct Book *book;
int count = 1;
book = library;
while (book != NULL)
{
printf("Book%d: ", count);
printf("书名: %s", book->title);
printf("作者: %s", book->author);
putchar('\n');
book = book->next;//指向下一个节点
count++;
}
}
struct Book *searchBook(struct Book *library, char *target)//target有可能是书名、作者
{
struct Book *book;
book = library;
while (book != NULL)//没有到尾巴
{
//对比,是否一致,两个相等返回0
if (!strcmp(book->title, target) || !strcmp(book->author, target))
{
break;//找不到就往下找,知道单链表结束
}
book = book->next;//让单链表继续
}
return book;//返回找到的节点指针
}
void printBook(struct Book *book)
{
printf("书名:%s", book->title);
printf("作者:%s", book->author);
}
void releaseLibrary(struct Book **library)//参数library(head指针)是head指针的值,两层解引用
{
struct Book *temp;//临时变量
while (*library != NULL)//直到library头指针指向NULL
{
temp = *library;
*library = (*library)->next;
free(temp);
//如果先释放头指针,那么就没有意义了
//library = library->next;
//free(library);
}
}
int main(void)
{
//头指针 head, NULL, 空的单链表
struct Book *library = NULL;
struct Book *book;
char input[128];
int ch;
while (1)
{
printf("请问是否需要录入书籍信息(Y/N):");
do
{
ch = getchar();
}while(ch != 'Y' && ch != 'N');
if (ch == 'Y')
{
addBook(&library);
}
else
{
break;//退出死循环
}
}
printf("请问是否需要打印图书信息(Y/N):");
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("很抱歉,没能找到!\n");
}
else//有可能会搜索到很多符合条件的书籍 ,继续往下找
{
//因为现在找到book节点,所以下一个从book->next开始找,直到找到NULL(结尾位置)
do
{
printf("已找到符合条件的图书...\n");
printBook(book);
}while ((book = searchBook(book->next, input))!=NULL);
}
releaseLibrary(&library);
return 0;
}