数据结构 -- 单链表插入之包含头节点的插入

╰半夏微凉° 2022-09-20 12:55 170阅读 0赞

1.通过 传地址 实现链表（包含头节点）的创建

2.检查 要插入的节点的值 是否存在

3.通过 传地址 插入新的节点

（创建的单链表 默认是有序的，这里只做了链表的创建、查找和插入，排序会在以后的博客中写）

以下代码在 vs2010 测试通过：

#include "stdafx.h"
    #include <stdlib.h>
    #include <stdio.h>
    
    #define FALSE 0
    #define TRUE 1
    #define EXISTS 2
    
    //typedef int int;
    typedef struct NODE{
    	int value;
    	struct NODE *next;
    }Node;
    
    int link_create(Node **list,int length);
    int link_insert(Node **list,int insert_value);
    int main(){
    	Node *list;
    	Node *plist;
    	int length,insert_value;
    	int lresult,cresult,iresult,result;
    	list = (Node *)malloc(sizeof(Node));
    	if(list == NULL){
    		return FALSE;
    	}
    	printf("请输入链表的长度!\n");
    	lresult = scanf("%d",&length);
    	if(lresult == 0){
    		return FALSE;
    	}
    	cresult  = link_create(&list,length);
    	if(cresult == 0){
    		return FALSE;
    	}
    	
    	printf("单链表创建成功!\n请输入要插入的数字：\n");
    	iresult = scanf("%d",&insert_value);
    	if(iresult == 0){
    		return FALSE;
    	}
    	result = link_insert(&list,insert_value );
    	if(result == 0){
    		return FALSE;
    	}else if(result == 1){
    		printf("插入成功!\n");
    	}else{
    		printf("该值已存在!\n");
    	}
    
    	plist = list->next;
    	printf("链表的值分别为：\n");
    	while(plist != NULL){
    		printf("%4d",plist->value);
    		plist= plist->next;
    	}
    	printf("\n");
    	system("pause");
    	return TRUE;
    }
    //单链表的创建
    int link_create(Node **list,int length){
    	int i;
    	Node *current;
    	Node *new_node;
    	current = *list;
    
    	for(i = 0 ; i < length; i++){
    		new_node = (Node *)malloc(sizeof(Node));
    		if(new_node == NULL){
    			return FALSE;
    		}
    		new_node->value = i+3;
    		current->next = new_node;
    		current = new_node;
    	}
    	current->next = NULL;
    	return TRUE;
    }
    int link_insert(Node **list,int insert_value ){
    	Node *phead;
    	Node *next;
    	Node *new_node;
    
    	next = *list;
    	//链表为空
    	if(next == NULL){
    		new_node = (Node *)malloc(sizeof(Node));
    		if(new_node == NULL){
    			return FALSE;
    		}
    		new_node->value = insert_value;
    		next->next = new_node;
    		new_node->next = NULL;
    		return TRUE;
    	}
    	//链表不为空
    	while(next != NULL){
    
    		phead = next;
    		if(next->value < insert_value){
    			next = next->next;
    			//新值插在链表的 尾部
    			if(next == NULL){
    				new_node = (Node *)malloc(sizeof(Node));
    				if(new_node == NULL){
    					return FALSE;
    				}
    				new_node->value = insert_value;
    				new_node->next = NULL;
    				phead->next = new_node;
    				return TRUE;
    			}
    		}else if(next->value == insert_value){
    			return EXISTS;
    		}else{
    			new_node = (Node *)malloc(sizeof(Node));
    			if(new_node == NULL){
    				return FALSE;
    			}
    			//新值插在链表的 开始或中间
    			new_node->value = insert_value;
    			new_node->next = next;
    			phead->next = new_node;
    			
    			return TRUE;
    		}
    	}
    	
    }

运行结果：

![SouthEast][]

[SouthEast]: /images/20220828/9fd17e5df4eb483498e28ad26b4f5dae.png