C语言实现单链表反转

一、理解指针

看懂链表的结构并不是很难,但是一旦把它和指针混在一起,就很容易让人摸不着头脑。所以,要想写对链表代码,首先就要理解好指针。

  有些语言有“指针”的概念,比如 C 语言;有些语言没有指针,取而代之的是“引用”,比如 Java、Python。不管是“指针”还是“引用”,实际上,它们的意思都是一样的,都是存储所指对象的内存地址。

  将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指针,或者反过来说,指针中存储了这个变量的内存地址,指向了这个变量,通过指针就能找到这个变量。

  p->next=q。这行代码是说,p 结点中的 next 指针存储了 q 结点的内存地址。p->next=p->next->next。这行代码表示,p 结点的 next 指针存储了 p 结点的下下一个结点的内存地址。

C语言标准规定,对于一个符号的定义,编译器总是从它的名字开始读取,然后按照优先级顺序依次解析。对,从名字开始,不是从开头也不是从末尾,这是理解复杂指针的关键! 

对于初学者,有几种运算符的优先级非常容易混淆,它们的优先级从高到低依次是:

定义中被括号( )括起来的那部分。后缀操作符:括号( )表示这是一个函数,方括号[ ]表示这是一个数组。前缀操作符:星号*表示“指向xxx的指针”。

  在本章中我们最多只用到二级指针因此将对二级指针做下说明。比如int **p,是什么意思?

首先看 *p 。 “*”表示P是一个指针。但是是指向什么的指针呢?

在看前面的int* ,int是一个整型类型后面加一个“*”表示整型类型的指针。

  *p就是指向整型类型指针的指针。p保存的是整型类型指针的地址。

二、警惕指针丢失和内存泄漏

  不知道你有没有这样的感觉,写链表代码的时候,指针指来指去,一会儿就不知道指到哪里了。所以,我们在写的时候,一定注意不要弄丢了指针。指针往往都是怎么弄丢的呢?我拿单链表的插入操作为例来给你分析一下。

  指针往往都是怎么弄丢的呢?我拿单链表的插入操作为例来给你分析一下。

  如图所示,我们希望在结点 a 和相邻的结点 b 之间插入结点 x,假设当前指针 p 指向结点 a。如果我们将代码实现变成下面这个样子,就会发生指针丢失和内存泄露。

p->next = x; // 将p的next指针指向x结点;
x->next = p->next; // 将x的结点的next指针指向b结点;

  初学者经常会在这儿犯错。p->next 指针在完成第一步操作之后,已经不再指向结点 b 了,而是指向结点 x。第 2 行代码相当于将 x 赋值给 x->next,自己指向自己。因此,整个链表也就断成了两半,从结点 b 往后的所有结点都无法访问到了。

  对于有些语言来说,比如 C 语言,内存管理是由程序员负责的,如果没有手动释放结点对应的内存空间,就会产生内存泄露。所以,我们插入结点时,一定要注意操作的顺序,要先将结点 x 的 next 指针指向结点 b,再把结点 a 的 next 指针指向结点 x,这样才不会丢失指针,导致内存泄漏。所以,对于刚刚的插入代码,我们只需要把第 1 行和第 2 行代码的顺序颠倒一下就可以了。同理,删除链表结点时,也一定要记得手动释放内存空间,否则,也会出现内存泄漏的问题。当然,对于像 Java 这种虚拟机自动管理内存的编程语言来说,就不需要考虑这么多了。

三、单链表反转的C语言实现

  使用p指向第一个结点,cur指向当前结点,每次把cur->next结点摘掉放在p节点前面。然后更新p结点指向头结点。具体实现代码如下所示

 void revers_list(list1 **l)
 {
   if(!(*l)||!l)
   {
     exit(-1);
   }

   list1 *start=*l;
   list1 *start_next=NULL;

   while (start->next)
   {
     // 获取当前节点的后继节点
     start_next = start->next;
     // 将后继节点摘链 72
      start->next = start_next->next;
     // 将后继节点提到最前面
     start_next->next = *l;
     // 更新头节点
     *l = start_next;
   }
 }

到此这篇关于C语言实现单链表反转的文章就介绍到这了,更多相关C语言 单链表反转内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 看图深入理解单链表的反转

    如何把一个单链表进行反转? 方法1:将单链表储存为数组,然后按照数组的索引逆序进行反转. 方法2:使用3个指针遍历单链表,逐个链接点进行反转. 方法3:从第2个节点到第N个节点,依次逐节点插入到第1个节点(head节点)之后,最后将第一个节点挪到新表的表尾. 方法4:   递归(相信我们都熟悉的一点是,对于树的大部分问题,基本可以考虑用递归来解决.但是我们不太熟悉的一点是,对于单链表的一些问题,也可以使用递归.可以认为单链表是一颗永远只有左(右)子树的树,因此可以考虑用递归来解决.或者说,因为单

  • 单链表反转python实现代码示例

    单链表的反转可以使用循环,也可以使用递归的方式 1.循环反转单链表 循环的方法中,使用pre指向前一个结点,cur指向当前结点,每次把cur->next指向pre即可. 代码: class ListNode: def __init__(self,x): self.val=x; self.next=None; def nonrecurse(head): #循环的方法反转链表 if head is None or head.next is None: return head; pre=None; c

  • 单链表实现反转的3种方法示例代码

    前言 单链表的操作是面试中经常会遇到的问题,今天总结一下反转的几种方案: 1 ,两两对换 2, 放入数组,倒置数组 3, 递归实现 代码如下: #include<stdio.h> #include<malloc.h> typedef struct Node { int data; struct Node *pnext; } Node,*pnode; pnode CreateNode() { pnode phead=(pnode)malloc(sizeof(Node)); if(ph

  • python如何实现单链表的反转

    这篇文章主要介绍了python如何实现单链表的反转,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 代码如下 # coding=utf-8 class Node: def __init__(self, data=None, next=None): self.data = data self.next = next def Reserver(link): pre = link cur = link.next pre.next = None whil

  • Python3实现的反转单链表算法示例

    本文实例讲述了Python3实现的反转单链表算法.分享给大家供大家参考,具体如下: 反转一个单链表. 方案一:迭代 # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def reverseList(self, head): """ :type head: ListNod

  • C语言实现单链表反转

    一.理解指针 看懂链表的结构并不是很难,但是一旦把它和指针混在一起,就很容易让人摸不着头脑.所以,要想写对链表代码,首先就要理解好指针. 有些语言有"指针"的概念,比如 C 语言:有些语言没有指针,取而代之的是"引用",比如 Java.Python.不管是"指针"还是"引用",实际上,它们的意思都是一样的,都是存储所指对象的内存地址. 将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指针,或者反过来说,指针中存储了这个变

  • C语言数据结构 link 链表反转的实现

    C语言数据结构 link 链表反转的实现 链表反转,示例如下: 偶数个输入:a->b->c->d->e->f 偶数个输出:e->f->c->d->a->b or 奇数个输入:a->b->c->d->e->f->g 偶数个输出:g->e->f->c->d->a->b #include <stdio.h> #include <malloc.h> #incl

  • 用C语言实现单链表的各种操作(二)

    上一篇文章<用C语言实现单链表的各种操作(一)>主要是单链表的一些最基本的操作,下面,主要是一些其他的典型的算法和测试程序. 复制代码 代码如下: /* 对单链表进行排序处理*/struct LNode *sort(struct LNode *head){  LinkList *p;  int n,i,j;  int temp;  n = ListLength(head);  if(head == NULL || head->next == NULL)    return head; 

  • C语言实现单链表实现方法

    C语言实现单链表实现方法 链表和我们之前实现过的顺序表一样,都是简单的数据结构,链表分为单向链表.双向链表.循环链表.而单向链表又分为两种实现方法,一种为带头节点的单链表,一种为不带头节点的单链表.我们来具体看看不带头节点的单链表的实现 单链表:它是一种链式存储的线性表,用一组地址任意的存储单元存放线性表的数据元素,称存储单元为一个节点. 今天我们来实现一些单链表的简单接口 先看看单链表的结构: (为了通用性,我们将类型重命名为DataType) typedef int DataType; //

  • Java实现单链表反转的多种方法总结

    对于单链表不熟悉的可以看一下基于Java实现单链表的增删改查 一.原地反转 1.新建一个哨兵节点下一结点指向头结点 2.把待反转链表的下一节点插入到哨兵节点的下一节点 反转之前的链表:1–>2–>3–>4>–>5 加入哨兵节点:dummp–>1–>2–>3–>4>–>5 原地反转: 定义:prev=dummp.next; pcur=prev.next; prev.next=pcur.next; pcur.next=dummp.next; d

  • Java单链表反转图文教程

    前言 最近在回顾链表反转问题中,突然有一些新的发现和收获,特此整理一下,与大家分享

  • C语言基于单链表实现通讯录功能

    本文实例为大家分享了C语言基于单链表实现通讯录功能的具体代码,供大家参考,具体内容如下 #include<stdio.h> #include<stdlib.h> #include<string.h> #pragma warning(disable:4996)://解决VS报严重性代码错误 typedef struct LNode { char name[20]; double ph_number; struct LNode* next; }LinkNode; //创建通

  • C语言数据结构单链表接口函数全面讲解教程

    目录 前言 一.链表的概念及结构 1.概念 二.链表的使用 1.遍历整个链表 2.尾插 3.头插 4.头删 5.尾删 6.任意位置插入数据 7.任意位置删除数据 后记 前言 上一期数据结构专栏我们学习了顺序表后:C语言数据结构顺序表 在运用时,细心的同学可能会发现,如果要头插.尾插或者任意位置.如果原先的空间已经被占满了,你是需要扩容的,动态链表扩容往往是2倍,但是扩容后,如果后面没有使用完全扩容后空间就会造成空间浪费,为了解决这个问题,我们今天将学习链表. 提示:以下是本篇文章正文内容,下面案

  • C语言使用单链表实现学生信息管理系统

    本文实例为大家分享了C语言使用单链表实现学生信息管理系统,供大家参考,具体内容如下 初学数据结构,记录一下学习过程. 运行结果如图: 1.运行界面 2.录入学生信息 3.按照总分进行排序 代码如下: #define ERROR 0 #define OK 1 #define OVERFLOW -1; typedef int ElemType; typedef int Status; #include<stdio.h> #include<stdlib.h> #include<ma

随机推荐