c语言单向链表反转递归_c语言数据结构知识点总结

一、链表定义

单向链表就像一根绳子一样，拿出来是一串，顺序表也是一串，但和单向链表不同，顺序表是连续存储的，不用管下一个节点位置在哪，反正就在后面，而单向链表在内存中是不连续存储的，看到有坑就放进去，然后还得保存放置的地址。所以，定义单向链表就是定义一个结构体，结构体里有两个成员，一个是要保存的数据，一个是下一个节点的地址。

typedef struct NODE{ 
    int data; struct NODE *next; }NODE,*NEXT; 

我这里用typedef取别名取了一个结构体和结构体指针，定义的这个结构体NODE其实没什么作用，主要是开辟内存的时候malloc函数要传入一个整数，用sizeof求NODE需要要多大的字节然后传入到malloc中获得一个节点的空间。

二、初始化链表

初始化一个链表，就先初始化链表的头，有头才能有后面的节点。

 int temp; NEXT node = NULL; node = GetNewNode(); scanf("%d",&temp); getchar(); node->data = temp; 

这里定义了一个temp变量，用来获取从键盘中输入的数据，定义一个指针node先指向NULL，然后获取一个节点的内存并返回给node，最后通过键盘输入获取数据赋值给data，第一个节点就算完成了。
getNewNode函数

NEXT GetNewNode(){ 
    NEXT node = malloc(sizeof(NODE)); node->next = NULL;//先让该节点的下一个节点为空 return node; } 

三、输入链表

初始化完成后，就开始从键盘中一个一个输入节点的数据了，这里就要用的while循环了，因为我这里数据定义的是int型的，所以我加了一个跳出循环的条件，就是输入非数字的时候跳出循环，结束输入。
具体代码如下：

while(1){ 
    NEXT next = GetNewNode(); if(scanf("%d",&temp)==1){ 
    getchar(); next->data = temp; InsertNodeLast(node,next);//新节点插入到旧节点后面 ShowNode(node); }else{ 
    printf("停止输入"); break; } } 

原理就是先获取一个新节点内存，然后给新节点赋值，然后让新节点插到旧节点后面，最后输出该链表所有内容。
其中注意的点：如果scanf其实是有返回值的，如果返回值为1就是输入的数字，还有，scanf停止输入的条件是用户按了回车键，也就是输入了换行符“\n”就会停止从输入缓冲区中读取数据，但是换行符会一直存在输入缓冲区不会被丢弃，影响下一次的输入，所以可以使用getchar把换行符从输入缓冲区给拿出来。
下面给出InsertNodeLast函数代码

void InsertNodeLast(NEXT old,NEXT new){ 
    while(old->next!=NULL){ 
   //遍历链表，直到到最后一个节点 old = old->next; } old -> next = new; new->next = NULL; } 

ShowNode函数

void ShowNode(NEXT node){ 
    while(node->next!=NULL){ 
    printf("%d\t",node->data); node = node->next; } printf("%d\t",node->data);//跳出循环的时候其实还有最后一个节点没输出 printf("\n"); } 

四、反向、排序插入和逆转

1、反向插入
反向插入就是创建一个节点让它插在链表的最前面，当头结点。
我的实现方法就是：把新节点的值和原来头节点的值进行互换，然后让原来头结点指向新节点，让新节点指向原来头结点的下一个节点，这样就算插入到第一个了。
原理图大概就是这个样子。

给出实现代码：

//从前面插入 void InsertNodeFirst(NEXT old,NEXT new){ 
    int temp = old->data; old->data = new->data; new->data = temp; new->next = old->next; old->next = new; } 

2、排序插入
我这里实现的是按从小到大排序，从大到小排序可以看完之后自己去设计。
原理主要是三种情况，将新节点的数据与链表中的数据进行逐一比较，
①比第一个节点数据还小，那就直接插到最前面；
②比最后一个数据还大，那就直接插到最后面；
③中间值，那就先找到一个比他小的节点，然后判断该节点的后面的一个节点是否比新节点大，如果满足就插在两个节点中间，不满足继续遍历。
这里给出第三种情况的示意图

给出该函数完整代码：

//从小到大排序 int InsertNodeSort(NEXT old,NEXT new){ 
    NEXT f = old; if(old->next==NULL){ 
   //如果是第二个节点 if(old->data>new->data)//如果小于第一个节点就插到前面 InsertNodeFirst(old,new); else InsertNodeLast(old,new);//否则插到后面 }else{ 
    while(old->next!=NULL){ 
   //如果要插入的不是第二个节点 if(f->data>new->data){ 
   //先判断是否第一个节点大于新节点 int temp = old->data; old->data = new->data; new->data = temp; new->next = old->next; old->next = new; return 1;//跳出循环 }else if(old->data<=new->data){ 
   //如果节点小于或等于新节点 NEXT n = old->next;//该节点的下一个节点 if(n->data>new->data||n == NULL){ 
   //判断下一个节点是否大于新节点 old->next = new;//大于就插到该节点和下一个节点之间 new->next = n; return 1;//跳出循环，插入结束 } } old = old->next; } old->next = new; new->next = NULL; } return 1; } 

这里的返回值没什么意义，主要是用来结束函数执行，break只能跳出循环，return是跳出整个函数。
3、链表逆转
这个功能真得写了我很久很久，试了很多种方法，一直都是失败的，最终想到一种很简单的方法，原理简单概括就是：将头结点的后面的节点一个一个往前面移动，最终返回最后移到前面的节点的地址，赋值给原来的头节点。
原理图：

画得不太清除，因为有些东西真的是只能意会不能言传。
给出代码帮助理解：

//翻转 NEXT ReverseNode(NEXT node){ 
    NEXT nodes = node ->next; NEXT temp = node;//定义一个指针始终指在链表最前面 NEXT rt; while(node->next!=NULL){ 
    node->next = nodes->next; nodes->next = temp;//指向最前面的节点 temp = nodes;//将最前面的节点再赋值给temp rt = temp;//temp作为返回值 nodes = node ->next; } return rt; } 

五、总结

其实只要理解链表的结构，不管怎么插入或者怎么输出都能写出算法，最后给出完整代码，不理解可以私信或者评论。

#include<stdio.h> #include<stdlib.h> typedef struct NODE{ 
    int data; struct NODE *next; }NODE,*NEXT; NEXT GetNewNode(){ 
    NEXT node = malloc(sizeof(NODE)); node->next = NULL; return node; } //从前面插入 void InsertNodeFirst(NEXT old,NEXT new){ 
    int temp = old->data; old->data = new->data; new->data = temp; new->next = old->next; old->next = new; } //从后面插入 void InsertNodeLast(NEXT old,NEXT new){ 
    while(old->next!=NULL){ 
   //遍历链表，直到到最后一个节点 old = old->next; } old -> next = new; new->next = NULL; } //从小到大排序 int InsertNodeSort(NEXT old,NEXT new){ 
    NEXT f = old; if(old->next==NULL){ 
   //如果是第二个节点 if(old->data>new->data)//如果小于第一个节点就插到前面 InsertNodeFirst(old,new); else InsertNodeLast(old,new);//否则插到后面 }else{ 
    while(old->next!=NULL){ 
   //如果要插入的不是第二个节点 if(f->data>new->data){ 
   //先判断是否第一个节点大于新节点 int temp = old->data; old->data = new->data; new->data = temp; new->next = old->next; old->next = new; return 1;//跳出循环 }else if(old->data<=new->data){ 
   //如果节点小于或等于新节点 NEXT n = old->next;//该节点的下一个节点 if(n->data>new->data||n == NULL){ 
   //判断下一个节点是否大于新节点 old->next = new;//大于就插到该节点和下一个节点之间 new->next = n; return 1;//跳出循环，插入结束 } } old = old->next; } old->next = new; new->next = NULL; } return 1; } //翻转 NEXT ReverseNode(NEXT node){ 
    NEXT nodes = node ->next; NEXT temp = node;//定义一个指针始终指在链表最前面 NEXT rt; while(node->next!=NULL){ 
    node->next = nodes->next; nodes->next = temp;//指向最前面的节点 temp = nodes;//将最前面的节点再赋值给temp rt = temp;//temp作为返回值 nodes = node ->next; } return rt; } void ShowNode(NEXT node){ 
    while(node->next!=NULL){ 
    printf("%d\t",node->data); node = node->next; } printf("%d\t",node->data); printf("\n"); } int main(){ 
    int temp; NEXT node = NULL; node = GetNewNode(); scanf("%d",&temp); getchar(); node->data = temp; ShowNode(node); while(1){ 
    NEXT next = GetNewNode(); if(scanf("%d",&temp)==1){ 
    getchar(); next->data = temp; InsertNodeLast(node,next);//调用不同方法插入方式不同 ShowNode(node); }else{ 
    break; } } ShowNode(node); node = ReverseNode(node); ShowNode(node); return 0; } 

今天的文章
c语言单向链表反转递归_c语言数据结构知识点总结分享到此就结束了，感谢您的阅读。