有趣的数据结构算法4——单链表插入元素、删除元素

今天药忘吃喽~ 2021-12-04 01:09 171阅读 0赞

### 有趣的数据结构算法4——单链表插入元素、删除元素 ###

*  单链表插入元素
 *  单链表删除元素
 *  实现代码
 *  GITHUB下载连接

关于什么是单链表以及如何进行单链表的生成、遍历等操作大家可以关注我的另一篇博文《有趣的数据结构算法3——单链表尾插法和头插法的实现》。 [https://blog.csdn.net/weixin\_44791964/article/details/95861300][https_blog.csdn.net_weixin_44791964_article_details_95861300]

# 单链表插入元素 #

单链表插入元素即在单链表某一特定位置i插入一个元素，常见的单链表如图所示。  
![完整的单链表示意图][20190714104130260.png]  
如果我们需要往链表中特定位置插入元素，这里我们假设要在e1和e2中间（即链表的第二个位置，index=2）插入元素。我们首先要将新的节点指向e2，如图所示：  
![新节点指向e2][e2]  
然后断开e1与e2的连接，如图所示：  
![断开e1与e2的连接][e1_e2]  
最后将e1指向新节点。  
![e1指向新节点][e1]  
此时便在index=2的位置完成了单链表的元素插入。

# 单链表删除元素 #

单链表插入元素即在单链表某一特定位置i删除一个元素，常见的单链表如图所示。  
![完整的单链表示意图][20190714104130260.png]  
如果我们需要在链表中特定位置删除元素，这里我们假设要删除e2（即链表的第二个位置，index=2）。我们首先要将一个指针指向e2，如图所示：  
![指针变量p指向e2][p_e2]  
将e1直接指向e3。  
![e1直接指向e3][e1_e3]  
最后释放p指针指向的节点即可。

# 实现代码 #

#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(struct Node));
    	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(struct Node));
    	p = library;
    
    	while (p != NULL){
        
    		printf("数字%d是%d\n", i, p->data);
    		p = p->Next;
    	}
    }
    
    void release(Linked_List library){
        
    	Linked_List temp = library->Next;
    	while (library != NULL){
        
    		free(temp);
    		library = library->Next;
    	}
    	free(library);
    }
    
    void getElem(Linked_List library, int num, int* e){
        
    	int i = 0;
    	while (i < num - 1){
        
    		library = library->Next;
    		if (library == NULL){
        
    			printf("超出链表索引范围。\n");
    			exit(1);
    		}
    		i++;
    	}
    	*e = library->data;
    }
    
    void addElem(Linked_List* library, int num, int* e){
         //在特定位置插入元素
    	int i = 0;
    	Linked_List p, s;
    	p = (Linked_List)malloc(sizeof(struct Node));
    	if (p == NULL)
    	{
        
    		printf("内存分配ERROR");
    		exit(1);
    	}
    	p->data = *e;
    	if (num == 1){
        					//如果在第一个节点插入
    		p->Next = *library;
    		*library = p;
    	}
    	else{
        
    		s = *library;
    		while (i < num - 2){
        		//找到特定位置
    			s = s->Next;
    			i++;
    		}
    		p->Next = s->Next;
    		s->Next = p;
    	}
    }
    
    void delElem(Linked_List* library, int num, int* e){
        	//删除特定位置节点
    	int i = 0;
    	Linked_List p, s;
    	if (*library == NULL){
        
    		printf("这是一个空表\n");
    		exit(1);
    	}
    	if (num == 1){
        
    		p = *library;
    		*library = (*library)->Next;
    		free(p);
    	}
    	else{
        
    		s = *library;
    		while (i < num - 2){
        
    			s = s->Next;
    			i++;
    
    		}
    		p = s->Next;
    		*e = p->data;
    		s->Next = p->Next;
    	}
    	free(p);
    }
    
    void main()
    {
        
    	Linked_List head = NULL, tail = NULL;
    	int e, num;
    
    	printf("请问你要输入几个数字：");
    	scanf("%d", &num);
    	for (int i = 0; i<num; i++){
        
    		addNode(&head, &tail);
    	}
    
    	printf("请输入你需要取得第几个数：");
    	scanf("%d", &num);
    	getElem(head, num, &e);
    	printf("你取得的数是%d\n", e);
    
    	printf("请输入你需要加入的数：");
    	scanf("%d", &e);
    
    	printf("请输入你需要加入的位置：");
    	scanf("%d", &num);
    	addElem(&head, num, &e);
    	scanLibrary(head);
    
    	printf("请输入你需要删除的位置：");
    	scanf("%d", &num);
    	delElem(&head, num, &e);
    	printf("你删除的数是%d\n", e);
    	scanLibrary(head);
    }

# GITHUB下载连接 #

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

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

[https_blog.csdn.net_weixin_44791964_article_details_95861300]: https://blog.csdn.net/weixin_44791964/article/details/95861300
[20190714104130260.png]: /images/20211203/72407c355aae412cb2859962b2831654.png
[e2]: /images/20211203/cb947528c6b34688bd3eac7d62df43d1.png
[e1_e2]: /images/20211203/582b1384b65d4bc8b7dde3c3efdd2f38.png
[e1]: /images/20211203/a9d23adc0bcd4b55935bf6f8db930518.png
[p_e2]: /images/20211203/5c116df8be214a5098cd328f7abf1f7c.png
[e1_e3]: /images/20211203/c71b678ac7594d83a9618631f25c1bc3.png
[https_github.com_bubbliiiing_Data-Structure-and-Algorithm]: https://github.com/bubbliiiing/Data-Structure-and-Algorithm