精华内容
下载资源
问答
  • 简单理解链表与区块链(blockchain).pdf
  • 链表概述链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量,以head表示,它存放一个地址。该地址指向一个元素。链表中每一个元素称为...
  • 面向对象来理解链表

    千次阅读 2018-08-11 19:24:20
    一、链表知识 1.1 链表定义 1.2 链表结构 1.3 优点 1.4 单链表、双链表、循环链表拓展 1.5 本文说明 二、面向对象分析链表 2.1 节点封装类Node.java 2.2 链表封装类ChainTable.java 2.3 关于环的补充 2.4...

    目录

    一、链表知识

    1.1 链表定义

    1.2 链表结构

    1.3 优点

    1.4 单链表、双链表、循环链表拓展

    1.5 本文说明

    二、面向对象分析链表

    2.1 节点封装类Node.java

    2.2 链表封装类ChainTable.java

    2.3 关于环的补充

    2.4 链表测试类TestChainTable.java


    一、链表知识

    1.1 链表定义

         由指针链接n 个结点组成一个链表。它是线性表的链式存储映像,称为线性表的链式存储结构。

    结点:数据元素的存储映像,映射。每个节点由数据域和指针域两部分组成。
        数据域:存储元素数据,即当前节点的存储数据
        指针域:存储下一个节点的存储位置,即指向下一个节点的指针

    1.2 链表结构

        链表的元素是节点,由一个或多个结点组成。节点包括两个元素:数据域和指针域。

        简单理解的话,类似链条,一节一节相连,每个链节都有自己的零件(数据)并且链接下一个链节(指针)。

        自行车的车链是一个环状的链子,或者说是首位相连的,这是链表中环结构下面会有说明。

    图1-1、链条图

    我们可以从图1-1 链表中抽象出链表如图1-2 所示,从首节点headNode 依此指向下一个node,直至尾节点tailNode

    图1-2、抽象链表图

    进而具体到单向链表

    • 初始化指针指向首节点headNode,初始化指针的next 为null 即链表为空
    • 每一个节点node 都由数据域和指针域组成,数据域存放当前节点的数据,指针域存放当前指针的下一个指向节点
    • 尾节点tailNode 的指针为空
    图1-3、单向链表图

    1.3 优点

    动态存储形式,数据元素可自由扩充;

    在物理存储空间上并不一定相连,所以链表的插入、删除动作高效,不需要像数组、顺序表那样移动过多的元素。

    1.4 单链表、双链表、循环链表拓展

        常见链表有单向链表和双向链表,单向链表是只有一个方向,从链表的首节点headNode 一直指向尾节点tailNode。双向链表是链表即可从headNode 依此指向tailNode 又可反向从tailNode 依此指向heaNode。另外循环链表是链表的尾节点直接指向头节点,即tailNode.next = headNode

    单链表、双链表、循环链表: 
        结点只有一个指针域的链表,称为单链表或线性链表
        有两个指针域的链表,称为双链表
        首尾相接的链表称为循环链表

    1.5 本文说明

        本文涉及到链表的多个常用方法,包括链表的初始化、添加节点、删除节点、查询节点、链表的逆置、模拟链表的环结构、判断链表是否存在环结构、寻找环的入口等方法。关于链表的相交问题暂不涉及。

        此处以单向链表为例,面向对象分析链表结构,将节点对象化,链表对象化,此处使用Java 语言演示。

    二、面向对象分析链表

    2.1 节点封装类Node.java

    有两个属性,当前节点存储的数据Object data,指向下一节点的指针Node next。

    /**
     * @Description :节点类
     * @Author: niaonao
     * @Date: 2018/8/11 13:07
     */
    public class Node {
    
        //当前节点的数据
        Object data;
        //当前节点的下一个节点
        Node next;
    
        public Object getData() { return data; }
    
        public void setData(Object data) { this.data = data; }
    
        public Node getNext() { return next; }
    
        public void setNext(Node next) { this.next = next; }
    
        /**
         * 无参构造函数
         */
        public Node() { next = null; }
    
        /**
         * 带参构造函数
         * @param data
         */
        public Node(Object data) {
            this.data = data;
            next = null;
        }
    }

    2.2 链表封装类ChainTable.java

    链表是由一个或多个节点组成的。定义如下封装类:

    /**
     * 链表
     *     由一个或多个节点组成
     *     每一个节点存放下一个元素, 通过首节点即可获取链表全部节点元素, 因此可以将首节点作为链表对象
     * 节点:
     *     每个节点包含两个元素: 数据对象data 和下一个节点对象next
     *     通过data 存储当前节点的数据
     *     通过next 存储下一个节点
     *
     * @Description :链表类
     * @Author: niaonao
     * @Date: 2018/8/11 13:07
     */
    public class ChainTable {
     
        //声明链表
        private Node chain;
     
        /**
         * 构造函数
         * 初始化链表, 此时chain.next == null, 即链表为空
         */
        public ChainTable() {
            chain = new Node();
        }
    
        //链表方法待补充
    }

    下面关于封装单链表的常用方法包括插入首节点,插入尾节点,指定位置插入节点,删除指定位置节点等。

    方法不一一分开介绍了,其中的方法都有注释说明。

      基本方法:

    •   void insert(Object val)     插入链表元素的方法(插入链表首位, 插入链表尾部, 插入链表指定位置)
    •   int getLength()     获取链表长度的方法
    •   Node getPosition(int position)      获取链表指定位置元素(正序获取, 逆序获取)
    •   boolean judgeLoop()     判断链表是否有环的方法
    •   int getLoopLength()     获取环的长度
    •   Node entryLoop()     查找环入口的方法
    •   Node reverse()      逆置链表的方法
    •   void clear()     清除链表
    /**
     * 链表
     *     由一个或多个节点组成
     *     每一个节点存放下一个元素, 通过首节点即可获取链表全部节点元素, 因此可以将首节点作为链表对象
     * 节点:
     *     每个节点包含两个元素: 数据对象data 和下一个节点对象next
     *     通过data 存储当前节点的数据
     *     通过next 存储下一个节点
     * 基本方法:
     *     void insert(Object val)     插入链表元素的方法(插入链表首位, 插入链表尾部, 插入链表指定位置)
     *     int getLength()     获取链表长度的方法
     *     Node getPosition(int position)      获取链表指定位置元素(正序获取, 逆序获取)
     *     boolean judgeLoop()     判断链表是否有环的方法
     *     int getLoopLength()     获取环的长度
     *     Node entryLoop()     查找环入口的方法
     *     Node reverse()      逆置链表的方法
     *     void clear()     清除链表
     *
     * @Description :链表类
     * @Author: niaonao
     * @Date: 2018/8/11 13:07
     */
    public class ChainTable {
     
        //声明链表
        private Node chain;
     
        /**
         * 构造函数
         */
        public ChainTable() {
            chain = new Node();
        }
     
        /**
         * 获取链表的长度
         *
         * @return
         */
        public int getLength() {
            //遍历计算链表长度,当前节点的next 下一个节点不为null, 节点数自增一即链表长度自增一
            int count = 0;
            Node cursor = chain;
            while (cursor.next != null) {
                cursor = cursor.next;
                count++;
            }
            return count;
        }
     
        /**
         * 在链表首部添加节点
         */
        public void insertHead(Object val) {
            //新建链表节点,下一节点指向链表的首位,然后更新链表首位为此节点。
            Node head = new Node(val);
            head.next = chain.next;
            chain.next = head;
        }
     
        /**
         * 在链表尾部添加节点
         *
         * @param val
         */
        public void insertTail(Object val) {
            //新建链表节点node,当cursor.next为null即cursor已经在链表尾部
            Node tail = new Node(val);
            Node cursor = chain;
            while (cursor.next != null) {
                cursor = cursor.next;
            }
            //获取到最后一个节点,使其next 指向tail 节点
            cursor.next = tail;
     
        }
     
        /**
         * 链表下表从1 开始,在指定位置插入节点
         *
         * @param val
         * @param position
         */
        public void insert(Object val, int position) {
            // 新建节点, 遍历获取链表的第port 个节点
            Node Node = new Node(val);
            Node cursor = chain;
            // 找到插入的位置前的的那一个节点
            if (position >= 0 && position <= this.getLength()) {
                for (int i = 1; i < position; i++) {
                    cursor = cursor.next;
                }
            }
            // 插入
            Node.next = cursor.next;
            cursor.next = Node;
        }
     
        /**
         * 删除指定位置的节点
         * @param position
         * @return
         */
        public void delete(int position) {
     
            if (chain == null)
                return ;
     
            if (position > 0 && position < this.getLength()) {
                for (int i = 1; i < this.getLength()+1; i++)
                    //当前位置的上一个节点的Next 指向当前节点的Next 节点, 此时当前节点不存在于该链表中
                    if (i == position) {
                        this.getPosition(i-1).next = this.getPosition(i+1);
                    }
            }
        }
     
        /**
         * 链表逆置方法
         * 将指向逆置, 更新原链表的下一个节点Next 为上一个节点,
         * 原链表的第一个节点逆置后作为新链表的最后一个节点, 其Next 指向null 即可
         *
         * @return
         */
        public Node reverse() {
            Node pre = null;
            Node cursor = chain;
            // 当cursor.next==null时即cursor到尾部时再循环一次把cursor变成头指针。
            while (cursor != null) {
                Node cursorNext = cursor.next;
                if (cursorNext == null) {
                    // 逆序后链表
                    chain = new Node();
                    chain.next = cursor;
                }
                if (pre != null && pre.getNext() == null && pre.getData() == null)
                    pre = null;
                cursor.next = pre;
                pre = cursor;
                cursor = cursorNext;
            }
            return chain;
        }
     
        /**
         * 链表下标从1开始,获取第position 个节点
         *
         * @param position
         * @return
         */
        public Node getPosition(int position) {
            Node cursor = chain;
            //节点插入的位置超出链表范围
            if (position < 0 || position > this.getLength()) {
                return null;
            }
            for (int i = 0; i < position; i++) {
                cursor = cursor.next;
            }
            return cursor;
        }
     
        /**
         * 获取倒数第position 个节点
         *
         * @param position
         * @return
         */
        public Node getBackPosition(int position) {
            Node cursor = chain;
            //节点插入的位置超出链表范围
            if (position < 0 || position > this.getLength())
                return null;
     
            //找到倒数第position 个位置
            for (int i = 0; i < this.getLength() - position + 1; i++)
                cursor = cursor.next;
     
            return cursor;
     
        }
     
        /**
         * 链表存在环
         * 追逐方法解决该问题
         * 环模型:
         * 存在环即链表中存在某个节点的Next 指向它前面的某个节点, 此时遍历链表是一个死循环
         *
         * @return
         */
        public boolean judgeLoop() {
            if (chain == null)
                return false;
     
            //快节点和慢节点从首位节点一起出发
            Node fast = chain;
            Node slow = chain;
            //快节点每次走两步, 慢节点每次走一步, 如果是环, 则快节点会追上慢节点
            while (fast.next != null && fast.next.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow)
                    return true;
            }
            return false;
        }
     
        /**
         * 计算环的长度
         * @return
         */
        public int getLoopLength() {
            if (chain == null)
                return 0;
            Node fast = chain;
            Node slow = chain;
            // 标识是否相遇
            boolean  tag = false;
            // 初始化环长
            int length = 0;
            // fast走两步, slow走一步, 快指针与慢指针第二次相遇时慢指针走的长度就是环的大小
            while(fast.next != null && fast.next.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                // tag为true 是已经相遇过了,当fast == slow 此时是第二次相遇
                if(fast == slow && tag == true) {
                    break;
                }
                // 初始化tag 为false, 第一次相遇标记tag 为true
                if(fast == slow && tag == false) {
                    tag =true;
                }
                // 第一次相遇后开始计算环的长度
                if(tag == true ) {
                    length++;
                }
            }
            return length;
        }
     
        /**
         * 环的入口
         *
         * 环后续单独拉出来写一个博客, 此处应该画个图更好理解
         * 暂时先给个不错的链接: https://www.cnblogs.com/fankongkong/p/7007869.html
         * @return
         */
        public Node entryLoop(){
            // 指向首节点
            Node fast = chain;
            Node slow = chain;
            // 找环中相汇点, 快节点走两步慢节点走一步
            while(slow.next != null && fast.next.next != null){
                fast = fast.next.next;
                slow = slow.next;
                // 相遇, 此时慢节点走了x 个节点, 快节点走了2x 个节点, 设环有m 个节点, fast 多走了n 圈
                // 有x + m*n = 2*x 即m*n = x, slow 走到环入口后就一直在环里, 所以相遇点距离环入口的长度和慢节点从首节点走到环入口的距离相等
                if(fast == slow) {
                    break;
                }
            }
            // fast 从相遇点一步一步走, slow 从首节点开始一步一步走, 走相同的距离相遇的点就是环的入口
            slow = chain;
            while(fast != slow){
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }
     
        /**
         * 清除链表元素
         */
        public void clear() {
            chain = new Node();
        }
    }
    

    2.3 关于环的补充

        关于环,在下面2-3 中测试类中模拟环,让尾节点指向首节点,实现一个简单的环结构。存在环结构的链表遍历会进入死循环。

         测试类中在模拟环结构之前,链表结构如下:

    图2-1、链表逆置的数据图

         模拟环结构之后,链表数据结构如下:

    图2-2、链表模拟环结构的数据图

    2.4 链表测试类TestChainTable.java

    测试链表封装类的常用方法,以供参考。

    /**
     * @Description :链表测试类
     * @Author: niaonao
     * @Date: 2018/8/11 14:11
     */
    public class TestChainTable {
    
        //声明链表
        private static ChainTable chainLink;
    
        public static void main(String a[]) {
            testChainMethod();
        }
    
        /**
         * 测试链表方法
         */
        private static void testChainMethod() {
            System.out.println("\n1.1 初始化链表数据");
            init();
    
            if (chainLink == null || chainLink.getLength() < 1) {
                return;
            }
            showChain();
    
            System.out.println("\n2.1 链表第三个节点插入数据为Three 的节点");
            chainLink.insert("Three", 3);
    
            showChain();
    
            System.out.println("\n3.1 获取链表中第5 个节点的数据: " + chainLink.getPosition(5).getData());
            showChain();
    
    
            System.out.println("\n4.1 获取链表中倒数第5 个节点的数据: " + chainLink.getBackPosition(5).getData());
            showChain();
    
            System.out.println("\n5.1 链表删除第2 个节点 ");
            chainLink.delete(2);
            showChain();
    
            System.out.println("\n6.1 链表逆序");
            chainLink.reverse();
            showChain();
    
            System.out.println("\n7.1 链表是否相交: " + chainLink.judgeLoop());
            showChain();
    
            System.out.println("\n7.2 模拟环模型, 使当前链表尾节点的Next 指向首节点");
            Node firstNode = chainLink.getPosition(1);
            Node lastNode = chainLink.getBackPosition(1);
            lastNode.setNext(firstNode);
            //出现环时, 链表遍历是个死循环
            //showChain();
    
            if (chainLink.judgeLoop()){
                System.out.print("\n7.3 链表是否有环: " + Boolean.TRUE + "\n\t出现环时, 链表遍历是个死循环");
    
                System.out.print("\n\t环的长度: " + chainLink.getLoopLength());
                System.out.print("\n\t环的入口: " + chainLink.entryLoop()
                                + "\n\t\t环入口节点的数据data: " + chainLink.entryLoop().getData()
                                + "\n\t\t下一个节点对象node: " + chainLink.entryLoop().getNext());
            }
            else {
                System.out.println("\n7.3 链表是否有环: " + Boolean.TRUE + "\n\t" + chainLink);
            }
    
        }
    
        /**
         * 初始化数据
         */
        private static void init() {
    
            chainLink = new ChainTable();
    
            System.out.println("\t在链表首位添加A,链表尾部依此添加B、C、D、E");
            chainLink.insertHead("A");
            chainLink.insertTail("B");
            chainLink.insertTail("C");
            chainLink.insertTail("D");
            chainLink.insertTail("E");
    
        }
    
        /**
         * 链表数据显示
         */
        private static void showChain() {
            System.out.println("\t链表长度: " + chainLink.getLength());
            System.out.print("\t链表数据: ");
            for (int i = 0; i < chainLink.getLength(); i++) {
                Node node = chainLink.getPosition(i + 1);
                System.out.print("\t " + node.getData());
            }
        }
    }

    测试结果:

    1.1 初始化链表数据
        在链表首位添加A,链表尾部依此添加B、C、D、E
        链表长度: 5
        链表数据:      A     B     C     D     E
    2.1 链表第三个节点插入数据为Three 的节点
        链表长度: 6
        链表数据:      A     B     Three     C     D     E
    3.1 获取链表中第5 个节点的数据: D
        链表长度: 6
        链表数据:      A     B     Three     C     D     E
    4.1 获取链表中倒数第5 个节点的数据: B
        链表长度: 6
        链表数据:      A     B     Three     C     D     E
    5.1 链表删除第2 个节点 
        链表长度: 5
        链表数据:      A     Three     C     D     E
    6.1 链表逆序
        链表长度: 5
        链表数据:      E     D     C     Three     A
    7.1 链表是否相交: false
        链表长度: 5
        链表数据:      E     D     C     Three     A
    7.2 模拟环模型, 使当前链表尾节点的Next 指向首节点

    7.3 链表是否有环: true
        出现环时, 链表遍历是个死循环
        环的长度: 5
        环的入口: Node@2503dbd3
            环入口节点的数据data: E
            下一个节点对象node: Node@4b67cf4d

    展开全文
  • 标题:链表的逆转 最近我发现一些同学并不知道链表的逆转函数怎么回事,常常有很多错误。于是,我写了篇文章,来解释一些链表逆转函数的原理,这是我第一次写CSDN博客,写得不好,希望大家不要有意见。首先给出链表...

    标题:链表的逆转

    最近我发现一些同学并不知道链表的逆转函数怎么回事,常常有很多错误。于是,我写了篇文章,来解释一些链表逆转函数的原理,这是我第一次写CSDN博客,写得不好,希望大家不要有意见。首先给出链表结点的结构体

    typedef struct Node *PtrToNode;
    struct Node {
        ElementType Data; /* 存储结点数据 */
        PtrToNode   Next; /* 指向下一个结点的指针 */
    };
    typedef PtrToNode List; /* 定义单链表类型 */
    

    链表的插入一般有:头插,尾插,中间插入。
    而链表的逆转函数主要运用的就是头插法的思想。
    明白此算法,你必须当明白什么是头插法。这样,不管题目要求你如何逆转链表,你都可以游刃有余,根据实际情况解决你解决的问题。
    运用头插法之前,首先应该把目标链表L拆开,拆成L1和L2,由第一个结点组成
    L1,其后的结点组成L2。之后不断拿出L2第一个结点,运用头插法,插入到L1的前面
    通过循环完成此功能
    而链表分为有带头结点的链表和不带头结点的链表,下面主要展示不带头结点的链表逆转函数。

    List Reverse(List L)
    {
    	List p1,p2;
    	if(L==0)
    	{
    		return 0;
    	}
    	else
    	{
    		//首先把L链表拆开,拆成L1和L2
    		//由第一个结点组成L1,其后的结点组成L2
    		p1=L->Next;			//
    		L->Next=0;
    		while(p1)		//之后不断拿出L2第一个结点,运用头插法,插入到L1的前面
    		{			
    			p2=p1->Next;		//
    			//完成头插动作
    			p1->Next=L;		//	
    			L=p1;
    			//
    			p1=p2;
    		}
    		return L;
    	}
    		
    }
    

    此处介绍头插法
    什么是头插法,我想学习过数据结构的人应该是很明白的,但是很多大佬可能早早就接触了链表的逆转,所以这部分主要是想给他们看的。这里即将展示的是带头结点的链表的逆转。可能与上文并不是很符合,但是其思想是一样的。
    在这里插入图片描述

    展开全文
  • 1.节点中有Data元素和Next元素,指针是直线这个节点还是指向该节点中的Data元素? ...2.如何理解双向链表中【p节点前驱的后继】,是指p节点前驱指向的节点(如p-1节点)的后继指向的节点(p)吗?
  • 在用c/c++写数据结构程序时,链表和二叉树中经常需要用到二级指针或者一级指针的引用,那么什么时候用什么时候不用呢? 先看一个简单的c++链表操作程序: (虽然风格有点像c,不过这个是cpp文件,不要在意这些细节...

    在用c/c++写数据结构程序时,链表和二叉树中经常需要用到二级指针或者一级指针的引用,那么什么时候用什么时候不用呢?
    先看一个简单的c++链表操作程序:

    (虽然风格有点像c,不过这个是cpp文件,不要在意这些细节)

    /* 
    code:Linklist 
    author:tashaxing 
    time:2014.9.30 
    */  
    #include "stdio.h"          
    #include "stdlib.h"     
    #include "time.h"  
    #define OK 1  
    #define ERROR 0  
    #define TRUE 1  
    #define FALSE 0  
    #define MAXSIZE 20 /* 存储空间初始分配量 */  
    typedef int Status;/* Status是函数的类型,其值是函数结果状态代码,如OK等 */  
    typedef int ElemType;/* ElemType类型根据实际情况而定,这里假设为int */  
    Status visit(ElemType c)  
    {  
        printf("%d ",c);  
        return OK;  
    }  
    typedef struct Node  
    {  
        ElemType data;  
        struct Node *next;  
    }Node;  
    typedef struct Node *LinkList; /* 定义LinkList */  
      
    //初始化表头,用一级指针(此方式无效)  
    Status InitList1(LinkList L)    //等价于Node *L  
    {   
        L=(LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */  
        if(!L) /* 存储分配失败 */  
                return ERROR;  
        L->next=NULL; /* 指针域为空 */  
      
        return OK;  
    }  
      
    //初始化表头,用二级指针  
    Status InitList2(LinkList *L)   //等价于Node **L  
    {   
        *L=(LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */  
        if(!(*L)) /* 存储分配失败 */  
                return ERROR;  
        (*L)->next=NULL; /* 指针域为空 */  
      
        return OK;  
    }  
      
    //初始化表头,用一级指针引用  
    Status InitList3(LinkList &L)   //等价于Node *&L  
    {   
        L=(LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */  
        if(!L) /* 存储分配失败 */  
                return ERROR;  
        L->next=NULL; /* 指针域为空 */  
      
        return OK;  
    }  
      
    //清空链表,使用二级指针  
    Status ClearList1(LinkList *L)  
    {   
        LinkList p,q;  
        p=(*L)->next;           /*  p指向第一个结点 */  
        while(p)                /*  没到表尾 */  
        {  
            q=p->next;  
            free(p);  
            p=q;  
        }  
        (*L)->next=NULL;        /* 头结点指针域为空 */  
        return OK;  
    }  
      
    //清空链表,使用一级指针  
    Status ClearList2(LinkList L)  
    {   
        LinkList p,q;  
        p=L->next;           /*  p指向第一个结点 */  
        while(p)                /*  没到表尾 */  
        {  
            q=p->next;  
            free(p);  
            p=q;  
        }  
        L->next=NULL;        /* 头结点指针域为空 */  
        return OK;  
    }  
      
    //销毁链表,使用一级指针(此方式无效)  
    Status DestroyList1(LinkList L)  
    {  
        LinkList p,q;  
        p=L->next;           /*  p指向第一个结点 */  
        while(p)                /*  没到表尾 */  
        {  
            q=p->next;  
            free(p);  
            p=q;  
        }  
        free(L);  
        L=NULL;  
        return OK;  
    }  
      
    //销毁链表,使用二级指针  
    Status DestroyList2(LinkList *L)  
    {  
        LinkList p,q;  
        p=(*L)->next;           /*  p指向第一个结点 */  
        while(p)                /*  没到表尾 */  
        {  
            q=p->next;  
            free(p);  
            p=q;  
        }  
        free(*L);  
        *L=NULL;  
        return OK;  
    }  
      
    //销毁链表,使用一级指针引用  
    Status DestroyList3(LinkList &L)  
    {  
        LinkList p,q;  
        p=L->next;           /*  p指向第一个结点 */  
        while(p)                /*  没到表尾 */  
        {  
            q=p->next;  
            free(p);  
            p=q;  
        }  
        free(L);  
        L=NULL;  
        return OK;  
    }  
    /* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L) */  
    /* 操作结果:用e返回L中第i个数据元素的值 */  
    Status GetElem(LinkList L,int i,ElemType *e)  
    {  
        int j;  
        LinkList p;     /* 声明一结点p */  
        p = L->next;     /* 让p指向链表L的第一个结点 */  
        j = 1;      /*  j为计数器 */  
        while (p && j<i)  /* p不为空或者计数器j还没有等于i时,循环继续 */  
        {     
            p = p->next;  /* 让p指向下一个结点 */  
            ++j;  
        }  
        if ( !p || j>i )   
            return ERROR;  /*  第i个元素不存在 */  
        *e = p->data;   /*  取第i个元素的数据 */  
        return OK;  
    }  
      
      
    //在中间插入元素,用二级指针  
    Status ListInsert1(LinkList *L,int i,ElemType e)  
    {   
        int j;  
        LinkList p,s;  
        p = *L;     
        j = 1;  
        while (p && j < i)     /* 寻找第i个结点 */  
        {  
            p = p->next;  
            ++j;  
        }   
        if (!p || j > i)   
            return ERROR;   /* 第i个元素不存在 */  
        s = (LinkList)malloc(sizeof(Node));  /*  生成新结点(C语言标准函数) */  
        s->data = e;    
        s->next = p->next;      /* 将p的后继结点赋值给s的后继  */  
        p->next = s;          /* 将s赋值给p的后继 */  
        return OK;  
    }  
    //在中间插入元素,用一级指针  
    Status ListInsert2(LinkList L,int i,ElemType e)  
    {   
        int j;  
        LinkList p,s;  
        p = L;     
        j = 1;  
        while (p && j < i)     /* 寻找第i个结点 */  
        {  
            p = p->next;  
            ++j;  
        }   
        if (!p || j > i)   
            return ERROR;   /* 第i个元素不存在 */  
        s = (LinkList)malloc(sizeof(Node));  /*  生成新结点(C语言标准函数) */  
        s->data = e;    
        s->next = p->next;      /* 将p的后继结点赋值给s的后继  */  
        p->next = s;          /* 将s赋值给p的后继 */  
        return OK;  
    }  
    //删除一个元素,用二级指针  
    Status ListDelete1(LinkList *L,int i,ElemType *e)   
    {   
        int j;  
        LinkList p,q;  
        p = *L;  
        j = 1;  
        while (p->next && j < i)  /* 遍历寻找第i个元素 */  
        {  
            p = p->next;  
            ++j;  
        }  
        if (!(p->next) || j > i)   
            return ERROR;           /* 第i个元素不存在 */  
        q = p->next;  
        p->next = q->next;            /* 将q的后继赋值给p的后继 */  
        *e = q->data;               /* 将q结点中的数据给e */  
        free(q);                    /* 让系统回收此结点,释放内存 */  
        return OK;  
    }  
    //删除一个元素,用一级指针  
    Status ListDelete2(LinkList L,int i,ElemType *e)   
    {   
        int j;  
        LinkList p,q;  
        p = L;  
        j = 1;  
        while (p->next && j < i)  /* 遍历寻找第i个元素 */  
        {  
            p = p->next;  
            ++j;  
        }  
        if (!(p->next) || j > i)   
            return ERROR;           /* 第i个元素不存在 */  
        q = p->next;  
        p->next = q->next;            /* 将q的后继赋值给p的后继 */  
        *e = q->data;               /* 将q结点中的数据给e */  
        free(q);                    /* 让系统回收此结点,释放内存 */  
        return OK;  
    }  
    /* 初始条件:顺序线性表L已存在 */  
    /* 操作结果:依次对L的每个数据元素输出 */  
    Status ListTraverse(LinkList L)  
    {  
        LinkList p=L->next;  
        while(p)  
        {  
            visit(p->data);  
            p=p->next;  
        }  
        printf("\n");  
        return OK;  
    }  
      
    int main()  
    {          
        LinkList L;  
        ElemType e;  
        Status i;  
        int j,k;  
        //InitList1(L);   //一级指针方式创建表头,失败  
        //InitList2(&L);  //二级指针方式创建表头,成功  
        InitList3(L);     //一级指针引用方式创建表头,成功  
        for(j=1;j<=7;j++)  
                ListInsert2(L,1,j);  
        printf("一级指针方式在L的表头依次插入1~7后:");  
        ListTraverse(L);   
      
        ListInsert1(&L,3,12);  
        printf("二级指针方式在L的中间插入12后:");  
        ListTraverse(L);   
      
        ListInsert2(L,5,27);  
        printf("一级指针在L的中间插入27后:");  
        ListTraverse(L);   
      
        GetElem(L,5,&e);  
        printf("第5个元素的值为:%d\n",e);  
      
        ListDelete1(&L,5,&e); /* 删除第5个数据 */  
        printf("二级指针方式删除第%d个的元素值为:%d\n",5,e);  
        printf("依次输出L的元素:");  
        ListTraverse(L);   
      
        ListDelete2(L,3,&e); /* 删除第3个数据 */  
        printf("一级指针方式删除第%d个的元素值为:%d\n",3,e);  
        printf("依次输出L的元素:");  
        ListTraverse(L);   
      
        printf("二级指针方式清空链表\n");  
        ClearList1(&L);  
        printf("依次输出L的元素:");  
        ListTraverse(L);   
          
        for(j=1;j<=7;j++)  
                ListInsert2(L,j,j);  
        printf("在L的表尾依次插入1~7后:");  
        ListTraverse(L);   
      
        printf("一级指针方式清空链表\n");  
        ClearList2(L);  
        printf("依次输出L的元素:");  
        ListTraverse(L);   
      
        printf("销毁链表\n");  
        //DestroyList1(L);   //一级指针方式销毁链表,失败,且出现满屏乱码  
        //DestroyList2(&L);  //二级指针方式销毁链表,成功  
        DestroyList3(L);     //一级指针引用方式销毁链表,成功  
      
        return 0;  
    }  


    输出结果:

    得出结论:

    1,初始化链表头部指针需要用二级指针或者一级指针的引用。

    2,销毁链表需要用到二级指针或者一级指针的引用。

    3,插入、删除、遍历、清空结点用一级指针即可。

    分析:
    1,只要是修改头指针则必须传递头指针的地址,否则传递头指针值即可(即头指针本身)。这与普通变量类似,当需要修改普通变量的值,需传递其地址,否则传递普通变量的值即可(即这个变量的拷贝)。使用二级指针,很方便就修改了传入的结点一级指针的值。 如果用一级指针,则只能通过指针修改指针所指内容,却无法修改指针的值,也就是指针所指的内存块。所以创建链表和销毁链表需要二级指针或者一级指针引用。

    2,不需要修改头指针的地方用一级指针就可以了,比如插入,删除,遍历,清空结点。假如头指针是L,则对L->next 及之后的结点指针只需要传递一级指针。

    3,比如一个结点p,在函数里要修改p的指向就要用二级指针,如果只是修改p的next指向则用一级指针就可以了

    函数中传递指针,在函数中改变指针的值,就是在改变实参中的数据信息。但是这里改变指针的值实际是指改变指针指向地址的值,因为传递指针就是把指针指向变量的地址传递过来,而不是像值传递一样只是传进来一个实参副本。所以当我们改变指针的值时,实参也改变了。

        仔细看函数InitList2(LinkList *L) 可以发现,在该函数中改变了指针的指向,也就是改变了指针自身的值。对比一下按值传递,这里的"值"是一个指针,所以我们要想指针本身的改变可以反映到实参指针上,必须使用二级指针。

    下面通过看一个例子来理解:

    #include <iostream>    
    #include <string.h>    
    using namespace std;    
        
    void fun1(char* str)    
    {    
        str = new char[5];    
        strcpy (str, "test string");    
    }    
        
    void fun2(char** str)    
    {    
        *str = new char[5];    
        strcpy (*str, "test string");    
    }    
        
    int main()    
    {    
        char* s = NULL;        
        cout << "call function fun1" << endl;    
        fun1 (s);    
        if (!s)    
            cout << "s is null!" << endl;    
        else    
            cout << s << endl;    
        
        cout << "call function fun2" << endl;    
        fun2 (&s);    
        if (!s)    
            cout << "s is null!" << endl;    
        else    
            cout << s << endl;    
        return 0;    
    }    

    输出结果:


     

    分析:

    在fun1中,当调用str = new char[5]时,str和s已经没什么关系了,相当于在fun1中复制了一个指针,这个指针指向的空间存储了字符串“test string”,但s仍指针NULL。当调用fun2时,因为是二级指针,s指向str,这里*str = new char[5],*str就是s,所以给*str分配空间就是给s分配空间。这样解释应该就很清楚了。

    画图为例:

    fun1执行时

    fun2执行时

    如图所示,在fun1种str是s的拷贝,给str分配空间跟s没有关系,在fun2种str是二级指针,指向s,能够通过控制*str从而给s分配空间。

    后记

    用框图表示链表中二级指针或者一级指针的使用更加直白了。

    1,二级指针创建头指针。

    a.只有头指针,没有头结点

    b,有头指针,也有头节点

    c,而如果不用二级指针,直接传一个一级指针,相当于生成L的拷贝M,但是对M分配空间与L无关了。

    2,二级指针销毁头指针

    无论有没有头节点都要用二级指针或者一级指针的引用传参来销毁。

    3,二级指针与一级指针方式插入结点

    传二级指针就是在从链表头指针开始对链表操作,传一级指针只不过是对头结点L生成了一个拷贝M,M的next指向的仍然是L的next,因此,后面的操作仍然是在原链表上操作。

    4,二级指针与一级指针方式删除结点

    删除的原理与插入一样。

    注意:

    在没有传入头结点的情况下必须使用二级指针,使用一级指针无效。

    例如:

    void insert(Node *p)
    {
        //do something to change the structure
    }
    void fun(Node *T)
    {
        Node *p;
        insert(p)    //OK,the head T is in
    }
    int main()
    {
        Node *T;
        fun(T);  //OK,the head T is in
    }

    因为fun函数里传入了数据结构的头指针(链表,二叉树都可以),在这个函数里面的insert函数形参可以是一级指针。

    但是如果在main函数里直接单独对数据结构中某一个结点操作就不能用一级指针了。

    void insert1(Node *p)
    {
        //do something to change the structure
    }
    void insert2(Node **P)
    {
        //do something to change the structure
    }
    int main()
    {
        Node *p;
        insert1(p);   //error
        insert2(&p); //OK
    }

    终于写完了,第一版在9月30日晚上发的,结果后来手贱修改的时候点了舍弃,结果弄得10月1日国庆重发,csdn的博客设置真是郁闷。
     

    展开全文
  • 数据结构很难?你还没有理解链表?我来帮你

    千次阅读 多人点赞 2020-05-19 14:36:10
    目录链表:随机存储,顺序访问(读取)前言一、单向链表什么叫随机存储呢?链表的基本操作1. 查找节点2. 更新节点3. 插入节点3.1. 尾部插入3.2. 头部插入3.3. 中间插入4. 删除元素4.1. 尾部删除4.1. 头部删除4.1. ...

    链表:随机存储,顺序访问(读取)

    前言

    大家好,我是子浩,我是一个大三的小菜鸡,非常向往优秀,羡慕优秀的人,已拿两个暑假offer,欢迎大家找我进行交流😂😂😂
    这是我的博客地址:子浩的博客https://blog.csdn.net/m0_47945515

    专栏《两周干掉数据结构》

    本博文的大部分插图来自于《漫画算法——小灰》,也复制了该书部分文字
    我加了一些自己的总结、代码(我代码实现是参考了本书以及java自带LinkedList的源代码)
    我发现本书有关链表的代码存在错误,已经向作者反馈
    建议有能力的同学直接去看java自带LinkedList的源代码,写的真的好
    应本书作者要求,加上本书公众号《程序员小灰》二维码
    在这里插入图片描述

    一、单向链表

    在这里插入图片描述
    链表(linked list)是一种在物理上非连续、非顺序的数据结构,由若干节点(node)所组成。
    单向 链表的每一个节点又包含两部分,一部分是存放数据的变量data,另一部分是指向下一个节点的指针next。
    链表的第1个节点被称为头节点,最后1个节点被称为尾节点,尾节点的next指针指向空。

    什么叫随机存储呢?

    如果说数组在内存中的存储方式是顺序存储,那么链表在内存中的存储方式则是随机存储 。
    上一节我们讲解了数组的内存分配方式,数组在内存中占用了连续完整的存储空间。而链表则采用了见缝插针的方式,链表的每一个节点分布在内存的不同位置,依靠next指针关联起来。这样可以灵活有效地利用零散的碎片空间。
    在这里插入图片描述
    图中的箭头代表链表节点的next指针。

    链表的基本操作

    1. 查找节点

    在查找元素时,链表不像数组那样可以通过下标快速进行定位,只能从头节点开始向后一个一个节点逐一查找。
    在这里插入图片描述

    /**
         * 链表查找元素
         *
         * @param index 查找的位置
         * @return index位置的Node对象
         */
        public Node get(int index) {
            if (index < 0 || index > size) {
                throw new IndexOutOfBoundsException("超出链表的节点的范围!");
            }
            Node temp = head;
            for (int i = 0; i < index; i++) {
                temp = temp.next;
            }
            return temp;
        }
    

    链表中的数据只能按顺序进行访问,最坏的时间复杂度是O(n)

    2. 更新节点

    在这里插入图片描述
    如果不考虑查找节点的过程,链表的更新过程会像数组那样简单,直接把旧数据替换成新数据即可。
    如果不考虑查找元素的过程,只考虑纯粹的更新节点操作,时间复杂度是O(1)

    /**
         * 更新节点 将列表中指定位置的节点的data替换为指定的data。
         *
         * @param index 需要更新的节点的位置
         * @param data  新data
         * @return 旧data
         */
        public int set(int index, int data) {
            Node x = get(index);
            int oldVal = x.data;
            x.data = data;
            return oldVal;
        }
    

    3. 插入节点

    只要内存空间允许,能够插入链表的元素是无穷无尽的,不需要像数组那样考虑扩容的问题。

    与数组类似,链表插入节点时,同样分为3种情况。

    • 尾部插入
    • 头部插入
    • 中间插入
    3.1. 尾部插入

    尾部插入,是最简单的情况,把最后一个节点的next指针指向新插入的节点即可。
    在这里插入图片描述

    3.2. 头部插入

    头部插入,可以分成两个步骤。

    1. 第1步,把新节点的next指针指向原先的头节点。
    2. 第2步,把新节点变为链表的头节点。
      在这里插入图片描述
    3.3. 中间插入

    中间插入,同样分为两个步骤。

    1. 第1步,新节点的next指针,指向插入位置的节点。
    2. 第2步,插入位置前置节点的next指针,指向新节点。
      在这里插入图片描述

    三钟情况的代码合到一起

    /**
         * 链表插入元素
         *
         * @param index 插入位置
         * @param data  插入元素 被插入的链表节点的数据
         */
        public void insert(int index, int data) {
            if (index < 0 || index > size) {
                throw new IndexOutOfBoundsException("超出链表节点范围!");
            }
            Node insertedNode = new Node(data);
            if (size == 0) {
                //空链表
                head = insertedNode;
                last = insertedNode;
            } else if (index == 0) {
                //插入头部
                insertedNode.next = head;
                head = insertedNode;
            } else if (size == index) {
                //插入尾部
                last.next = insertedNode;
                last = insertedNode;
            } else {
                //插入中间
                Node prvNode = get(index - 1);
                insertedNode.next = prvNode.next;
                prvNode.next = insertedNode;
            }
            size++;
        }
    

    4. 删除元素

    链表的删除操作同样分为3种情况。

    1. 尾部删除
    2. 头部删除
    3. 中间删除
    4.1. 尾部删除

    尾部删除,是最简单的情况,把倒数第2个节点的next指针指向空即
    可。
    在这里插入图片描述

    4.1. 头部删除

    头部删除,也很简单,把链表的头节点设为原先头节点的next指针即可。
    在这里插入图片描述

    4.1. 中间删除

    中间删除,同样很简单,把要删除节点的前置节点的next指针,指向要
    删除元素的下一个节点即可。
    在这里插入图片描述
    这里需要注意的是,许多高级语言,如Java,拥有自动化的垃圾回收机制,所以我们不用刻意去释放被删除的节点,只要没有外部引用指向它们,被删除的节点会被自动回收。
    如果不考虑插入、删除操作之前查找元素的过程,只考虑纯粹的插入和删除操作,时间复杂度都是O(1)

    /**
         * 链表删除元素
         *
         * @param index 删除的位置
         * @return 被删除的节点
         */
        public Node remove(int index) {
            if (index < 0 || index > size) {
                throw new IndexOutOfBoundsException("超出链表节点范围");
            }
            Node removeNode;
            if (index == 0) {
                if (size == 0) {
                    throw new NullPointerException("当前链表为空,不可以进行删除操作");
                }
                //删除头节点
                removeNode = head;
                head = head.next;
            } else if (index == size - 1) {
                //删除尾节点
                Node preNode = get(index - 1);
                removeNode = preNode.next;
                preNode.next = null;
                last = preNode;
            } else {
                //删除中间节点
                Node prevNode = get(index - 1);
                removeNode = prevNode.next;
                prevNode.next = prevNode.next.next;
            }
            size--;
            return removeNode;
        }
    

    Java实现链表的完整代码

    package chapter2.part2;
    
    /**
     * Created by IntelliJ IDEA.
     *
     * @Author: 张志浩  Zhang Zhihao
     * @Email: 3382885270@qq.com
     * @Date: 2020/5/3
     * @Time: 13:39
     * @Version: 1.0
     */
    public class MyLinkedList2 {
        private Node head; //头节点
        private Node last; //尾节点
        private int size; //链表实际长度
    
        public static void main(String[] args) {
            MyLinkedList2 myLinkedList = new MyLinkedList2();
    //        myLinkedList.remove(0); // java.lang.NullPointerException: 当前链表为空,不可以进行删除操作
    //        myLinkedList.remove(3); // java.lang.IndexOutOfBoundsException: 超出链表节点范围
            myLinkedList.insert(0, 3);
            myLinkedList.insert(1, 7);
            myLinkedList.insert(2, 9);
            myLinkedList.insert(3, 5);
            myLinkedList.insert(1, 6);
            myLinkedList.remove(0);
            myLinkedList.set(0, 23);
            myLinkedList.output();
        }
    
        /**
         * 链表插入元素
         *
         * @param index 插入位置
         * @param data  插入元素 被插入的链表节点的数据
         */
        public void insert(int index, int data) {
            if (index < 0 || index > size) {
                throw new IndexOutOfBoundsException("超出链表节点范围!");
            }
            Node insertedNode = new Node(data);
            if (size == 0) {
                //空链表
                head = insertedNode;
                last = insertedNode;
            } else if (index == 0) {
                //插入头部
                insertedNode.next = head;
                head = insertedNode;
            } else if (size == index) {
                //插入尾部
                last.next = insertedNode;
                last = insertedNode;
            } else {
                //插入中间
                Node prvNode = get(index - 1);
                insertedNode.next = prvNode.next;
                prvNode.next = insertedNode;
            }
            size++;
        }
    
        /**
         * 链表删除元素
         *
         * @param index 删除的位置
         * @return 被删除的节点
         */
        public Node remove(int index) {
            if (index < 0 || index > size) {
                throw new IndexOutOfBoundsException("超出链表节点范围");
            }
            Node removeNode;
            if (index == 0) {
                if (size == 0) {
                    throw new NullPointerException("当前链表为空,不可以进行删除操作");
                }
                //删除头节点
                removeNode = head;
                head = head.next;
            } else if (index == size - 1) {
                //删除尾节点
                Node preNode = get(index - 1);
                removeNode = preNode.next;
                preNode.next = null;
                last = preNode;
            } else {
                //删除中间节点
                Node prevNode = get(index - 1);
                removeNode = prevNode.next;
                prevNode.next = prevNode.next.next;
            }
            size--;
            return removeNode;
        }
    
        /**
         * 更新节点 将列表中指定位置的节点的data替换为指定的data。
         *
         * @param index 需要更新的节点的位置
         * @param data  新data
         * @return 旧data
         */
        public int set(int index, int data) {
            Node x = get(index);
            int oldVal = x.data;
            x.data = data;
            return oldVal;
        }
    
        /**
         * 链表查找元素
         *
         * @param index 查找的位置
         * @return index位置的Node对象
         */
        public Node get(int index) {
            if (index < 0 || index > size) {
                throw new IndexOutOfBoundsException("超出链表的节点的范围!");
            }
            Node temp = head;
            for (int i = 0; i < index; i++) {
                temp = temp.next;
            }
            return temp;
        }
    
        /**
         * 输出链表
         */
        public void output() {
            Node temp = head;
            while (temp != null) {
                System.out.print(temp.data + " ");
                temp = temp.next;
            }
        }
    
        /**
         * 链表节点
         */
        class Node {
            int data;
            Node next;
    
            Node(int data) {
                this.data = data;
            }
        }
    }
    
    
    
    

    二、双向链表

    在这里插入图片描述
    双向链表比单向链表稍微复杂一些,它的每一个节点除了拥有data和next指针,还拥有指向前置节点的prev 指针。

    展开全文
  • 数据结构---在内存上理解链表

    千次阅读 2018-06-11 12:05:27
    首先,在学习数据结构中,对链表在内存上的理解非常重要,上代码public class LinkNode&lt;M&gt; { public M data; public LinkNode nextNode; @Override public String toString() { return "...
  • 简单理解链表与区块链(blockchain)

    千次阅读 2018-03-05 14:11:06
    “区块链”类似于c语言里的链表,其中“区块”相当于链表中的Node节点,Node节点之间相互串联形成“链”。 链表的概念(如图) 换一种“实现”方式,每个石柱保存下一个石柱的经纬坐标,进而可以准确找到下一个...
  • 当然对于链表而言,分为静态链表和动态链表,根据处理数据的方向又分为单向链表和双向链表。  提到链表我们都知道还有一个比较重要的知识点就是指针,因为前后数数据要有关联,必须要进行一系列的连接和指向处理...
  • (语法)理解链表:建立,插入

    千次阅读 2016-03-25 08:37:33
    链表是将一个个独立的数据利用指针将他们链接起来,达到方便访问,调用的一个功能,下面通过一个小程序对链表进行分析: #include using namespace std; struct student //定义类型为student的一个结构体 { ...
  • 关于如何理解链表结构体指针引用LinkNode * &L的问题

    千次阅读 多人点赞 2018-09-28 02:14:59
    初学数据结构,在学习的过程中有了这个疑问,已经理解其中缘由,特写篇博客和大家一起分享交流。 C++中的引用:& int a=10; int &ra=a; 注意:此处&是标识符,不是取地址符! a是目标原名称,ra是...
  • 链表是一种常见的线性数据结构。它被定义为一个节点序列,对于通常意义上的链表来说,其中除了最后一个节点外的每个节点都包含有下一个节点的地址。整个序列就好像一串珠链一样,是“线性”排列的。实践中,链表的...
  • 链表理解

    2019-05-14 09:02:29
    链表理解 开发工具与关键技术:Visual Studio、C++ 作者:张国军 撰写时间:2019年05月13日 链表,通过这段时间对链表理解。最终有了个人的理解。 我对链表理解呢,就是一个节点一个节点连接起来的。节点由...
  • 链表理解

    千次阅读 2013-01-25 18:53:55
    阿龙写的代码并注释的,学习了。 #include #include struct node { int data; struct node*next; //链表函数用结构体类型来做,就像数组用int型 }; struct node*creat(int n) { int i; str
  • 初识链表

    2021-03-09 16:58:24
    链表链表的原理链表实现用引用和对象的知识理解链表具体实现结点的定义链表的创建链表的遍历遍历每个元素和计算链表中元素个数找到最后一个结点找到倒数第二个结点找到第n个结点找到链表中是否包含某个元素链表的...
  • 理解FreeRtos的链表

    千次阅读 2016-09-09 11:57:41
    理解FreeRtos的链表,简单例子分析一下
  • 双向循环链表

    2014-07-11 23:28:18
    把普通程序转换为链表,更好的帮助你理解链表的使用方法
  • 理解Linux双向链表

    千次阅读 2011-12-28 12:53:47
    理解Linux双向链表原文:http://blog.csdn.net/leisure512/article/details/5188986我截取其中一部分,并加了图解。Linux内核中双向链表hlist_head,它的定义:struct hlist_head { struct hlist_node *first;};...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 211,063
精华内容 84,425
关键字:

如何理解链表