有趣的数据结构算法3——单链表尾插法和头插法的实现

女爷i 2021-12-13 04:22 414阅读 0赞

### 有趣的数据结构算法3——单链表尾插法和头插法的实现 ###

*  什么是单链表
 *   *  头插法的实现
     *  尾插法的实现
     *  头插法实现代码
     *  尾插法实现代码
     *  GITHUB下载连接

以前学习C语言的时候，对于指针，链表什么的是最害怕的。但是现在……  
![在这里插入图片描述][20190723170158884.jpg_pic_center]

# 什么是单链表 #

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。其与顺序数组最大的不同在于，顺序数组在内存中中存放数据的方式是连续存放的，而单链表每一个节点的内存数据是任意存放的。  
![有无头结点的链表示意图，图片来自百度百科][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70]  
有无头结点的链表示意图，图片来自百度百科。

## 头插法的实现 ##

头插法顾名思义就是在插入数据的时候，是从单链表的头部插入的。  
假设有一个已经生成的链表，它是长这样的。  
![完整的单链表示意图][20190714104130260.png]  
如果我们需要往链表中添加数据，首先要断开头结点和第一个节点的链接。  
![断开连接][20190714104300716.png]  
然后让头结点指向新的数据节点，新的数据节点再指向原来头结点指向的节点。  
![在这里插入图片描述][20190714104352864.jpg]  
此时便完成了一个数据的插入。

## 尾插法的实现 ##

头插法的实现非常方便，但是逻辑思维和普通的顺序存储不同，最后加入的元素反而在链表的头部，使用尾插法则没有相对应的问题，与头插法不同，尾插法需要一个指向尾部的指针，不然每次添加数据都需要遍历整个链表，会导致效率较低。  
![尾插法示意图][20190714105459757.png]  
将尾部节点指向新数据。  
![尾部节点指向新数据][20190714105618698.png]  
将新节点定义为尾部节点。  
![新节点定义为尾部节点][20190714105704792.png]

## 头插法实现代码 ##

#include <stdio.h>
     #include <stdlib.h>
     
     struct Node{
         //定义结构体
     	int data;
     	struct Node* Next;
     };
     
     typedef struct Node* Linked_List;	//将结构体指针定义成另外的名称Linked_List
     //如果使用一个*传入的是结构体的指针，其可以改变内部元素,data,Next
     
     void getNode(Linked_List p){
        		//用于获得Node的data值，被addNode调用
     	printf("请输入数字：");
     	scanf("%d", &p->data);
     }
     
     void addNode(Linked_List* library){
        
     	Linked_List p, temp;
     
     	p = (Linked_List)malloc(sizeof(Linked_List));	//申请内存空间
     
     	if (p == NULL)
     	{
        
     		printf("error");
     		exit(1);
     	}
     
     	getNode(p);
     
     	if (*library == NULL){
        	//如果头结点为空，将头结点指针的对应的地址改为p，因此要用到指针的指针。
     		p->Next = NULL;
     		*library = p;
     	}
     	else{
        
     		temp = *library;	//利用temp节点更新头插法
     		p->Next = temp;
     		*library = p;
     	}
     }
     
     void scanLibrary(Linked_List library){
        
     	int i = 0;
     	Linked_List p;
     
     	p = (Linked_List)malloc(sizeof(Linked_List));
     	p = library;
     
     	while (p != NULL){
        
     		printf("数字%d是%d\n", i, p->data);
     		p = p->Next;
     		i++;
     	}
     	free(p);
     }
     
     void release(Linked_List library){
        
     	Linked_List temp = library->Next;
     	while (library != NULL){
        
     		free(temp);
     		library = library->Next;
     	}
     	free(library);
     }
     
     void main()
     {
        
     	Linked_List head = NULL;
     	int num;
     	printf("请问要输入几个数字：");
     	scanf("%d", &num);
     	for (int i = 0; i<num; i++){
        
     		addNode(&head);
     	}
     	scanLibrary(head);
     }

## 尾插法实现代码 ##

#include <stdio.h>
     #include <stdlib.h>
     
     struct Node{
         //定义结构体
     	int data;
     	struct Node* Next;
     };
     
     typedef struct Node* Linked_List;	//将结构体指针定义成另外的名称Linked_List
     //如果使用一个*传入的是结构体的指针，其可以改变内部元素,data,Next
     
     void getNode(Linked_List p){
        		//用于获得Node的data值，被addNode调用
     	printf("请输入数字：");
     	scanf("%d", &p->data);
     }
     
     void addNode(Linked_List* library, Linked_List* tail){
        
     	Linked_List p;
     
     	p = (Linked_List)malloc(sizeof(Linked_List));
     	if (p == NULL)
     	{
        
     		printf("error");
     		exit(1);
     	}
     
     	getNode(p);
     
     	if (*library == NULL){
        	//如果头结点为空，将头结点指针的对应的地址改为p，因此要用到指针的指针。
     		p->Next = NULL;
     		*library = p;
     
     		*tail = *library;	//此时尾节点等于头结点
     		
     	}
     	else{
        
     		p->Next = NULL;
     		(*tail)->Next = p;
     		*tail = p;			//尾节点更新
     	}
     	
     }
     
     void scanLibrary(Linked_List library){
        
     	int i = 0;
     	Linked_List p;
     
     	p = (Linked_List)malloc(sizeof(Linked_List));
     	p = library;
     
     	while (p != NULL){
        
     		printf("数字%d是%d\n", i, p->data);
     		p = p->Next;
     		i++;
     	}
     	free(p);
     }
     
     void release(Linked_List library){
        
     	Linked_List temp = library->Next;
     	while (library != NULL){
        
     		free(temp);
     		library = library->Next;
     	}
     	free(library);
     }
     
     void main()
     {
        
     	Linked_List head = NULL,tail = NULL;
     	int num;
     	printf("请问要输入几个数字：");
     	scanf("%d", &num);
     	for (int i = 0; i<num; i++){
        
     		addNode(&head,&tail);
     	}
     	scanLibrary(head);
     }

## GITHUB下载连接 ##

[https://github.com/bubbliiiing/Data-Structure-and-Algorithm][https_github.com_bubbliiiing_Data-Structure-and-Algorithm]

希望得到朋友们的喜欢。  
有问题的朋友可以提问噢。

[20190723170158884.jpg_pic_center]: /images/20211210/2f9277161b9146a480729417793b99af.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70]: /images/20211210/4a3f673089a346ea951246ef8ebccc3f.png
[20190714104130260.png]: /images/20211210/83224ef1e6f840ad9db2f6e6e27eeae5.png
[20190714104300716.png]: /images/20211210/0e1b5521661842d69bd30ba0a24edb12.png
[20190714104352864.jpg]: /images/20211210/c1eb7529050b4f399b5a068544d8c0bb.png
[20190714105459757.png]: /images/20211210/a7bacc22d9644b1e8f664ed360bfc4b8.png
[20190714105618698.png]: /images/20211210/b78956a8a24d4ae6ad1562eeea7ac6cd.png
[20190714105704792.png]: /images/20211210/9341824bc53148c09aefe531afedc9cd.png
[https_github.com_bubbliiiing_Data-Structure-and-Algorithm]: https://github.com/bubbliiiing/Data-Structure-and-Algorithm