正文
C语言递归,非递归实现翻转链表
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
翻转链表作为,链表的常用操作,也是面试常遇到的。
分析
非递归分析:
非递归用的小技巧比较多,很容易出错。
递归分析比较简单,在代码里面
代码:
#include<stdio.h>
#include<stdlib.h>
typedef int elemtype;
typedef struct node{
elemtype element;
struct node*next;//写成node* next;node * next;node *next;也是可以的,为了方便阅读,以后统一写成elemtype* element。'*',';',',''=','->'等等这些特殊意义的关键字符语法规则差不多,本身具有分割意义,两旁加空格与不加空格的意义是一致的,也就是说空格对这些特殊字符是不起作用的,而解析编译器,运行器也不是利用空格来分割的;标志符是不能用这些字符,为了方便阅读,不会看的一驼屎,最好在这些特殊的字符两旁加空格。
}node;//这个类型名与其的结构体名可以一样,不矛盾。 /*Function:将链表所有结点从头结点顺序打印,遍历链表。traverse_linkedList
*遍历一种数据机构,进去看一看,给人说一说,一般遍历打印里面的数据,知道是进去,可以拿到里面的数据。
*这种数据结构有很多数据元素,但每次遍历只能访问一个元素,因此要循环,而且要访问所有的结点,必须有一种机制从一个结点跳到另一个结点。
*@paramb:node* phead :链表首地址,首结点地址。
*/
void traverse_linkedList(node* phead){
node *p=phead ;//定义一个跳转控制指针
if (NULL == p){
printf("亲,链表为空\n");
return ;
}
else{
while(NULL != p){ printf("%d\n",p -> element);//访问结构体的数据,可以用: 其结构体变量.成员变量;还可以:指向这个结构体的指针 -> 成员变量
p = p -> next ;
}
} }
/*Function:翻转链表(非递归) reverse_linkedList
*param:node** phead //参数意义:保存链表指针变量的地址
*return: void
*
*知识点:node** p;p代表链表指针变量的地址。*p才是链表。**p 代表结点(可以认为"*"具有解析功能)
*整体的思路:重整结点的关系,原来从左指向右,翻转后从右指向左;原来指向头结点,翻转后指向尾结点
*
*时间复杂度:O(n)
*
*
* */
void reverse_linkedList(node** phead){//存链表头的指针变量的地址传过来,旨在能改变这个变量,指针本质上是存地址的变量。
node *pLeft,*pRight,*pMiddle;//定义三个指针: 左中右,pRight:作移动。
pLeft=pRight=*phead;
//空链表或者只有一个结点
if(NULL == pLeft || NULL == ( pLeft -> next)){
return ; }else{
//头的结点的处理
pLeft = *phead ;
pRight = (*phead) -> next ; //' ->'优先级最高
pLeft -> next = NULL ; //循环控制条件
node *ctl=pRight;
while(NULL != ctl){
pMiddle = pRight ;// 在移动前,先保存
pRight = pRight -> next ;// pRight移动到下一个结点
ctl = pMiddle -> next; //在变换关系前,先把控制的信息存起来
pMiddle -> next = pLeft ; //变换关系
pLeft = pMiddle ; // p变换
} *phead = pLeft ; //指向链表头指针变量,指向新的头。
}
}
/*
*Function:翻转链表(递归) reverse_recursive_linkedList
*param:node* head
*return: node*
*
*知识点:
*递归:自身调用自身;出口。
*思考:
*
*如果链表是空链表或者只有一个结点,就可以直接的返回表头;如果是两个结点以上链表,调用自身,拿到子结点的表头,再重建他们的关系。
*
* */
node* reverse_recursive_linkedList(node * head){
if(head == NULL || head -> next == NULL){
return head ;
}
else{
node* second = head -> next ;
node* new_head = reverse_recursive_linkedList(second);
second -> next = head ;
head -> next = NULL ;
return new_head ;
}
}
int main()
{
node *p , *q , *head;//仅仅定义了几个指针变量,系统做了哪些工作呢?开辟这些指针变量类型所需的空间。若没有初始值一般由系统随机分配值,还没有指向真正的结点,也就是说 p -> 成员变量是没有意义的。会报""; node 类型的声明,告诉系统作对应的语法检查,该怎么处理指针指向的内容。
// insert 10 nodes
//创建结点,结点本质上是数据块,这些数据是占用空间的,有了储存空间,就有了数据载体。所以开辟空间是创建数据的关键,然后告诉系统你怎么来处理这块空间,最后空间开辟成功。
p = q = (node* )malloc(sizeof(node)) ;//与” 数据类型 标识符“ 创建的差别,无标识符,要手动开空间,并提取信息。标识符功能:解析+地址。
head = p ;
p -> element = ;
int i=;
for ( i = ;i < ; i++){ q = (node* )malloc(sizeof(node)) ;
q -> element = i + ;
p -> next = q ;
p = q ; } traverse_linkedList(head);
reverse_linkedList(&head);//&只能作取址用,没有解析功能。
traverse_linkedList(head);
traverse_linkedList(reverse_recursive_linkedList(head));
}
本人在重拾C,很多东西看是熟悉而又陌生,所以注释比较多一点,仅供参考,不爽直接忽略,