单链表相关操作

╰+哭是因爲堅強的太久メ 2022-12-11 07:45 148阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node
    {
    	int num;
    	char aaa;
    	struct node *next;
    }Node;
    
    
    //尾插节点
    void insert_last_node(Node *head, int x, char y)
    {
    	Node *new_node = malloc(sizeof(Node));
    	new_node->num = x;
    	new_node->aaa = y;
    	new_node->next = NULL;
    
    	Node *p = head;
    	//找到最后一个节点
    	while(p->next != NULL)	
    	{
    		p = p->next;
    	}
    	p->next = new_node;
    }
    
    //头插节点
    void insert_first_node(Node *head, int x, char y)
    {
    	Node *new_node = malloc(sizeof(Node));
    	new_node->num = x;
    	new_node->aaa = y;
    	new_node->next = NULL;
    
    	new_node->next = head->next;
    	head->next = new_node;
    }
    
    //查询某个节点
    void search_one_node(Node *head, int index)
    {
    	int i;
    	int ret = list_num(head);
    	Node *p = head;
    	if(ret < 0)
    	{
    		printf("此链表尚未有节点，请先插入节点\n");
    		return ;
    	}
    	if(ret < index)
    	{
    		printf("此链表只有%d个节点，请输入要查询的正确的节点索引！\n",ret);
    		return ;
    	}
    	for(i = 0; i < index; i++)
    	{
    		p = p->next;
    	}
    	printf("第%d个节点 num = %d, aaa = %c\n", index, p->num, p->aaa);
    }
    
    //删除链表的某个节点
    void delete_node(Node *head, int index)
    {
    	int i;
    	int ret = list_num(head);
    	Node *p = head;
    	if(ret < 0)
    	{
    		printf("此链表尚未有节点，无法删除节点\n");
    		return ;
    	}
    	if(ret < index)
    	{
    		printf("此链表只有%d个节点，请输入要删除的正确的节点索引！\n",ret);
    		return ;
    	}
    	for(i = 0; i < index-1; i++)	//找到要删除的节点的上一个节点
    	{
    		p = p->next;
    	}
    	//开始删除节点
    	Node *q = p->next;
    	p->next = p->next->next;
    	q->next = NULL;
    	free(q);
    }
    
    //修改某个节点的值
    void change_one_node(Node *head,int index, int new_num, char new_aaa)
    {
    	int i;
    	int ret = list_num(head);
    	Node *p = head;
    	if(ret < 0)
    	{
    		printf("此链表尚未有节点，无法修改节点\n");
    		return ;
    	}
    	if(ret < index)
    	{
    		printf("此链表只有%d个节点，请输入要修改的正确的节点索引！\n",ret);
    		return ;
    	}
    	for(i = 0; i < index; i++)	//找到要修改的这个节点
    	{
    		p = p->next;
    	}
    	p->aaa = new_aaa;
    	p->num = new_num;
    	return ;
    }
    
    //删除整个链表
    void delete_list(Node *head)
    {
    	Node *p = head;
    	Node *q = p;
    	int i;
    	int ret = list_num(head);
    	if(ret < 0)
    	{
    		printf("此链表为空！\n");
    		return ;
    	}
    	while(head->next != NULL)
    	{
    		//每次到最后一个节点的前一个节点
    		ret = list_num(head);
    		if(ret == 1)	//只有一个节点
    		{
    			delete_node(head,ret);
    			break;
    		}
    		for(i=0; i<ret-1; i++)
    		{
    			p = p->next;
    			q = p->next;
    		}
    		p->next = NULL;
    		p = head;
    		free(q);
    	}
    	free(head);
    	return ;
    }
    
    //查询链表节点个数
    int list_num(Node *head)
    {
    	Node *p = head;
    	int i = 1;
    	if(p->next == NULL)
    	{
    		printf("此链表尚未有节点！\n");
    		return -1;
    	}
    	while (p->next != NULL)
    	{
    		p = p->next;
    		i++;
    	}
    	//printf("此链表一共有 %d 个节点\n",i-1);
    	return i-1;
    }
    
    //遍历整个链表
    void all_node(Node *head)
    {
    	Node *p = head;
    	int i = 1;
    	if(p->next == NULL)
    	{
    		printf("此链表为空！\n");
    		return ;
    	}
    	while (p->next != NULL)
    	{
    		p = p->next;
    		printf("节点%2d num = %d, aaa = %c\n",i++,p->num,p->aaa);
    	}
    	return ;
    }
    
    int main()
    {
    	// 初始化头节点
    	Node *head = malloc(sizeof(Node));
    	head->num = 0;
    	head->aaa = '0';
    	head->next = NULL;
    
    	//插入节点
    	insert_last_node(head, 10, 'A');
    	insert_last_node(head, 20, 'B');
    	insert_last_node(head, 30, 'C');
    	insert_last_node(head, 40, 'D');
    
    	insert_first_node(head, 50, 'E');
    	insert_first_node(head, 60, 'F');
    	insert_first_node(head, 70, 'G');
    	insert_first_node(head, 80, 'H');
    
    	//查询整个链表
    	all_node(head);
    
    	//查询某个节点
    	search_one_node(head, 8);
    
    	//删除某个节点
    	delete_node(head,6);
    
    	all_node(head);
    
    	//修改某个节点的值
    	change_one_node(head, 1, 100, 'Z');
    
    	all_node(head);
    
    	delete_list(head);
    
    	all_node(head);
    }