单链表头插法和尾插法C/C++代码实现

╰+攻爆jí腚メ 2023-02-14 02:45 9阅读 0赞

## 1，头插法/前插法： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]  
通过将新结点逐个插入链表的头部（头结点之后）来创建链表，每次申请一个新结点，读入相应的数据元素值，然后将新结点插入到头结点之后。

需要注意的是：头插法是逆序的，先插入的反而在后面。

## 代码如下： ##

#include<stdio.h>
    #include<stdlib.h>
    
    //书的数据结构
    struct Book
    {
        
    	char title[128];
    	char author[40];
    	struct Book *next; //指针域
    };
    
    //头插法添加一本书
    void addBook(struct Book **Library)//两个**是定义指向指针的指针，详情见笔记
    {
        
    	struct Book *book, *temp;  //定义一个新结点的指针
    	book = (struct Book *)malloc(sizeof(struct Book));
    	if (book == NULL)
    	{
        
    		printf("内存分配失败!\n");
    		exit(1);
    	}
    
    	printf("请输入书名：");
    	scanf("%s", book->title);
    	printf("请输入作者：");
    	scanf("%s", book->author);
    
    	if (*Library != NULL)				//这个条件必须有,要不然下面让一个空指针去找next就会空指针异常！！！！	
    	{
        
    		temp = *Library;
    		*Library = book;
    		book->next = temp;				
    	}
    	else								//表为空表
    	{
        
    		*Library = book;				
    		book->next = NULL;
    	}
    
    }
    
    //打印图书信息
    void printLibrary(struct Book *Library)
    {
        
    	struct Book *book;
    	book = Library;
    	while (book != NULL)
    	{
        
    		printf("----------------\n");
    		printf("书名：%s\n", book->title);
    		printf("作者：%s\n", book->author);
    		book = book->next;
    	}
    }
    
    //释放
    void releaseLibrary(struct Book **Library)
    {
        
    	struct Book *temp;
    	while (*Library != NULL)
    	{
        
    		temp = *Library;
    		*Library = (*Library)->next;	//括号（）不能少！！
    		free(temp);
    	}
    }
    
    //无头结点的单链表
    int main()
    {
        
    	struct Book *Library = NULL; //头指针指向NULL
    	char ch;
    	while (1)
    	{
        
    		do
    		{
        
    			printf("请问是否输入一本图书信息（Y/N）：");
    			ch = getchar();		//捕获回车键！！
    		} while (ch != 'Y'&& ch != 'N');
    		if (ch == 'Y')
    		{
        
    			printf("请输入书籍信息：\n");
    			addBook(&Library);	//取头指针的地址
    		}
    		else
    		{
        
    			break;
    		}
    	}
    	printf("你输入的书籍信息为：\n");
    	printLibrary(Library);
    
    	releaseLibrary(&Library);
    	return 0;
    }

## 运行结果： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]  
头插法是逆序的，先插入的后输出。

## 2，尾插法/后插法： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 2]  
通过将新结点逐个插入到链表的尾部来创建链表。 同前插法一样， 每次申请一个新结点， 读入相应的数据元素值。 不同的是， 为了使新结点能够插入到表尾， 需要增加一个尾指针 r指向链表的尾结点。

## 代码如下： ##

#include<stdio.h>
    #include<stdlib.h>
    
    //书的数据结构
    struct Book
    {
        
    	char title[128];
    	char author[40];
    	struct Book *next; //指针域
    };
    
    //尾插法添加一本书
    void addBook(struct Book **Library)//两个**是定义指向指针的指针，详情见笔记
    {
        
    	struct Book *book, *temp;		 //定义一个新结点的指针
    	static struct Book *tail;		//定义一个静态指针变量,固定住tail指针的值
    	book = (struct Book *)malloc(sizeof(struct Book));
    	if (book == NULL)
    	{
        
    		printf("内存分配失败!\n");
    		exit(1);
    	}
    
    	printf("请输入书名：");
    	scanf("%s", book->title);
    	printf("请输入作者：");
    	scanf("%s", book->author);
    
    	if (*Library != NULL)				//这个条件必须有,要不然下面让一个空指针去找next就会空指针异常！！！！	
    	{
        
    		tail->next = book;
    		book->next = NULL;
    	}
    	else
    	{
        
    		*Library = book;
    		book->next = NULL;
    	}
    	tail = book;	//尾插法的精髓，把tail指向尾部
    }
    
    void printLibrary(struct Book *Library)
    {
        
    	struct Book *book;
    	book = Library;
    	while (book != NULL)
    	{
        
    		printf("----------------\n");
    		printf("书名：%s\n", book->title);
    		printf("作者：%s\n", book->author);
    		book = book->next;
    	}
    }
    
    //释放
    void releaseLibrary(struct Book **Library)
    {
        
    	struct Book *temp;
    	while (*Library != NULL)
    	{
        
    		temp = *Library;
    		*Library = (*Library)->next;
    		free(temp);
    	}
    }
    
    //无头结点的单链表
    int main()
    {
        
    
    	struct Book *Library = NULL; //头指针指向NULL
    	char ch;
    	while (1)
    	{
        
    		do
    		{
        
    			printf("请问是否输入一本图书信息（Y/N）：");
    			ch = getchar();		//捕获回车键！！！
    		} while (ch != 'Y'&& ch != 'N');
    		if (ch == 'Y')
    		{
        
    			printf("请输入书籍信息：\n");
    			addBook(&Library);//取头指针的地址
    		}
    		else
    		{
        
    			break;
    		}
    	}
    	printf("你输入的书籍信息为：\n");
    	printLibrary(Library);
    
    	releaseLibrary(&Library);
    	return 0;
    }

## 运行结果： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200531170323121.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200531170232302.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020053117161368.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200531171533377.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70