线性表的反转

傷城~ 2022-12-24 14:50 73阅读 0赞

线性表的反转，是指将头结点变成尾结点，尾结点变成头结点

这个主要注意两点：防止断链，所以要提前保留当前指针的后一个指针，当前指针的next域要，指向前一个结点，所以要有前一个结点的指针，再加上当前结点，就是

共有三个辅助指针变量。

不多说，直接上代码，这里的代码用到了之前的我的一篇文章里的代码 [线性表的链式存储（传统模式）][Link 1]

话不多说，直接上代码：

#include<iostream>
    #include<vector>
    using namespace std;
    
    struct Node
    {
    	int data;
    	struct Node*next;
    };
    
    /*单链表插入操作
    带头结点，输入参数：头指针，插入位置，元素值
    返回值：插入成功 0，插入失败 -1头指针为空或者位置小于零，-2，插入位置不存在
    */
    int InsertList(struct Node*pNode, int i, int e)
    {
    	if (pNode == NULL||i<0)
    	{
    		return -1;
    	}
    	int j = 0;//计数变量
    	struct Node*cur = pNode;//辅助指针变量
    	while (cur->next != NULL&&j < i)
    	{
    		cur = cur->next;
    		j++;
    	}
    	if (j>i || cur == NULL)
    	{
    		return -2;
    	}
    	
    	struct Node*newnode = (struct Node*)malloc(sizeof(struct Node));
    	newnode->data = e;
    	newnode->next = cur->next;
    	cur->next = newnode;
    	return 0;
    }
    /*单链表删除操作
    带头结点，输入参数：头指针，删除位置，输出参数 元素值
    返回值：插入成功 0，删除失败 -1头指针为空或位置小于零，-2，删除位置不存在
    */
    
    int DeleteList(struct Node*pNode, int i, int* e)
    {
    	if (pNode == NULL||i<0)
    	{
    		return -1;
    	}
    	int j = 0;//计数变量
    	struct Node*cur = pNode;//辅助指针变量
    	while (cur->next != NULL&&j < i)
    	{
    		cur = cur->next;
    		j++;
    	}
    	if (j>i || cur == NULL)
    	{
    		return -2;
    	}
    	*e = cur->next->data;
    	struct Node*temp = cur->next;
    	cur->next = cur->next->next;
    	
    	free(temp);
    	temp = NULL;
    	return 0;
    }
    
    //初始化一个链表
    //输入参数  二级指针
    //返回值，分配内存成功返回零，分配失败返回-1
    int CreatList(struct Node**head)
    {
    	struct Node*temp = (struct Node*)malloc(sizeof(struct Node));
    	if (temp == NULL)
    	{
    		return -1;
    	}
    	temp->data = -1;
    	temp->next = NULL;
    	*head = temp;
    	return 0;
    }
    
    //二叉链表的遍历
    //入参 头指针 
    //返回值 头指针为空返回-1，非空返回0
    int TravList(struct Node*head)
    {
    	if (head == NULL)
    	{
    		return -1;
    	}
    	int i = 0;
    	struct Node*temp = head;
    	while (temp->next != NULL)
    	{
    		printf("list[%d] is [%d]\n", i, temp->next->data);
    		temp = temp->next;
    		i++;
    	}
    }
    //销毁整个链表
    //输出参数 二级指针
    //返回值 -1 传入的头指针为空 0销毁成功
    
    int DestoryList(struct Node**head)
    {
    	if (*head == NULL)
    	{
    		return -1;
    	}
    	//需要两个辅助指针变量，销毁整个结点前保留下一个结点
    	struct Node*cur_node = (*head)->next;
    	struct Node*next_node = NULL;
    	while (cur_node != NULL)
    	{
    		next_node = cur_node->next;
    		free(cur_node);
    		cur_node = NULL;
    		cur_node = next_node;
    	}
    
    	//最后释放头指针
    
    	free(*head);
    	*head = NULL;
    }
    
    //单链表的反转
    //两中方式 1.把这个链表遍历一遍，然后存储在vector中,然后重新建立一个链表，
    //这样还要销毁原来的链表，然后重新申请空间创建链表，再进行插入，时间和空间复杂度都挺大
    //方式2.空间复杂度o(1) 原地处理，直接修改链表的指针 先处理不带头结点的
    
    void Reverse(struct Node**head)
    {
    	if (*head == NULL)
    	{
    		return;
    	}
    	struct Node*cur_node = *head;
    	struct Node*next_node=NULL;
    	struct Node*pre_node = NULL;
    
    	while (cur_node!= NULL)
    	{
    		next_node = cur_node->next;
    		if (next_node == NULL)
    		{
    			*head = cur_node;
    		}
    		cur_node->next = pre_node;
    
    		pre_node = cur_node;
    		cur_node = next_node;
    	}
    }
    int main()
    {
    	struct Node*head = NULL;
    	if (CreatList(&head) == -1)
    	{
    		printf("malloc failed\n");
    	}
    	InsertList(head,0,1);
    	InsertList(head,1,2);
    	InsertList(head,2,3);
    	InsertList(head,3,4);
    	TravList(head);
    
    	Reverse(&head);
    
    	TravList(head);
    
    }

输出结果如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5naHVhaWNoYW8_size_16_color_FFFFFF_t_70][]

我们发现反转后，和反转前比较，不是 4 3 2 1，而是 3 2 1 -1，这个是因为我之前写的代码有头结点，然后反转后，把头结点变成了尾结点，然后打印的函数又是默认

不打印第一个结点（认为第一个结点是头结点造成的），重新改下打印函数，如下：

#include<iostream>
    #include<vector>
    using namespace std;
    
    struct Node
    {
    	int data;
    	struct Node*next;
    };
    
    /*单链表插入操作
    带头结点，输入参数：头指针，插入位置，元素值
    返回值：插入成功 0，插入失败 -1头指针为空或者位置小于零，-2，插入位置不存在
    */
    int InsertList(struct Node*pNode, int i, int e)
    {
    	if (pNode == NULL||i<0)
    	{
    		return -1;
    	}
    	int j = 0;//计数变量
    	struct Node*cur = pNode;//辅助指针变量
    	while (cur->next != NULL&&j < i)
    	{
    		cur = cur->next;
    		j++;
    	}
    	if (j>i || cur == NULL)
    	{
    		return -2;
    	}
    	
    	struct Node*newnode = (struct Node*)malloc(sizeof(struct Node));
    	newnode->data = e;
    	newnode->next = cur->next;
    	cur->next = newnode;
    	return 0;
    }
    /*单链表删除操作
    带头结点，输入参数：头指针，删除位置，输出参数 元素值
    返回值：插入成功 0，删除失败 -1头指针为空或位置小于零，-2，删除位置不存在
    */
    
    int DeleteList(struct Node*pNode, int i, int* e)
    {
    	if (pNode == NULL||i<0)
    	{
    		return -1;
    	}
    	int j = 0;//计数变量
    	struct Node*cur = pNode;//辅助指针变量
    	while (cur->next != NULL&&j < i)
    	{
    		cur = cur->next;
    		j++;
    	}
    	if (j>i || cur == NULL)
    	{
    		return -2;
    	}
    	*e = cur->next->data;
    	struct Node*temp = cur->next;
    	cur->next = cur->next->next;
    	
    	free(temp);
    	temp = NULL;
    	return 0;
    }
    
    //初始化一个链表
    //输入参数  二级指针
    //返回值，分配内存成功返回零，分配失败返回-1
    int CreatList(struct Node**head)
    {
    	struct Node*temp = (struct Node*)malloc(sizeof(struct Node));
    	if (temp == NULL)
    	{
    		return -1;
    	}
    	temp->data = -1;
    	temp->next = NULL;
    	*head = temp;
    	return 0;
    }
    
    //二叉链表的遍历
    //入参 头指针 
    //返回值 头指针为空返回-1，非空返回0
    int TravList(struct Node*head,bool bInclude_Headnode=true)
    {
    	if (head == NULL)
    	{
    		return -1;
    	}
    	int i = 0;
    	struct Node*temp = head;
    
    	if (bInclude_Headnode == true)
    	{
    		while (temp->next != NULL)
    		{
    			printf("list[%d] is [%d]\n", i, temp->next->data);
    			temp = temp->next;
    			i++;
    		}
    	}
    	else
    	{
    		while (temp!= NULL)
    		{
    			printf("list[%d] is [%d]\n", i, temp->data);
    			temp = temp->next;
    			i++;
    		}
    	}
    	
    }
    //销毁整个链表
    //输出参数 二级指针
    //返回值 -1 传入的头指针为空 0销毁成功
    
    int DestoryList(struct Node**head)
    {
    	if (*head == NULL)
    	{
    		return -1;
    	}
    	//需要两个辅助指针变量，销毁整个结点前保留下一个结点
    	struct Node*cur_node = (*head)->next;
    	struct Node*next_node = NULL;
    	while (cur_node != NULL)
    	{
    		next_node = cur_node->next;
    		free(cur_node);
    		cur_node = NULL;
    		cur_node = next_node;
    	}
    
    	//最后释放头指针
    
    	free(*head);
    	*head = NULL;
    }
    
    //单链表的反转
    //两中方式 1.把这个链表遍历一遍，然后存储在vector中,然后重新建立一个链表，
    //这样还要销毁原来的链表，然后重新申请空间创建链表，再进行插入，时间和空间复杂度都挺大
    //方式2.空间复杂度o(1) 原地处理，直接修改链表的指针 先处理不带头结点的
    
    void Reverse(struct Node**head)
    {
    	if (*head == NULL)
    	{
    		return;
    	}
    	struct Node*cur_node = *head;
    	struct Node*next_node=NULL;
    	struct Node*pre_node = NULL;
    
    	while (cur_node!= NULL)
    	{
    		next_node = cur_node->next;
    		if (next_node == NULL)
    		{
    			*head = cur_node;
    		}
    		cur_node->next = pre_node;
    
    		pre_node = cur_node;
    		cur_node = next_node;
    	}
    }
    int main()
    {
    	struct Node*head = NULL;
    	if (CreatList(&head) == -1)
    	{
    		printf("malloc failed\n");
    	}
    	InsertList(head,0,1);
    	InsertList(head,1,2);
    	InsertList(head,2,3);
    	InsertList(head,3,4);
    	TravList(head);
    
    	Reverse(&head);
    
    	TravList(head,false);
    
    }

输出的结果如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5naHVhaWNoYW8_size_16_color_FFFFFF_t_70 1][]

[Link 1]: https://blog.csdn.net/zhanghuaichao/article/details/108926338
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5naHVhaWNoYW8_size_16_color_FFFFFF_t_70]: /images/20221120/624d11f23bbd40959ea7d314db1c1bce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5naHVhaWNoYW8_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201128212805878.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5naHVhaWNoYW8=,size_16,color_FFFFFF,t_70