10.顺序存储和链式存储

CSharp > CSharp进阶 > CSharp进阶语法知识 CSharp 语法知识 CSharp进阶常用泛型数据结构类

发布时间 : 2024-02-20 13:23

字数:4.7k 阅读 :

评论:

10.常用泛型数据结构类-顺序存储和链式存储

10.常用泛型数据结构类-顺序存储和链式存储

10.1 知识点

数据结构

数据结构的概念

数据结构是计算机存储、组织数据的方式（规则）。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，比如自定义的一个类也可以称为一种数据结构，自己定义的数据组合规则。不要把数据结构想得太复杂，简单点理解，就是人定义的存储数据和表示数据之间关系的规则而已。

常用的数据结构

常用的数据结构包括数组、栈、队列、链表、树、图、堆、散列表。

线性表

线性表是一种数据结构，是由n个具有相同特性的数据元素的有限序列，比如数组、ArrayList、Stack、Queue、链表等等。
顺序存储和链式存储是数据结构中两种存储结构

顺序存储

顺序存储：用一组地址连续的存储单元依次存储线性表的各个数据元素。

链式存储

链式存储(链接存储)：用一组任意的存储单元存储线性表中的各个数据元素。

自己实现一个最简单的单向链表

class语句块内 namespace语句块外

/// <summary>
/// 单向链表节点
/// </summary>
/// <typeparam name="T">泛型数据</typeparam>
class LinkedNode<T>
{
    //具体存储的数据
    public T value;

    //当前节点的下一节点
    public LinkedNode<T> nextNode;

    //构造函数 初始化值
    public LinkedNode(T value)
    {
        this.value = value;
    }
}

/// <summary>
/// 单向链表类 管理 节点 管理 添加等等
/// </summary>
/// <typeparam name="T"></typeparam>
class LindedList<T>
{
    //头结点
    public LinkedNode<T> head;

    //尾结点
    public LinkedNode<T> last;

    //添加节点方法
    public void Add(T value)
    {
        //添加节点 必然是new一个新的节点
        LinkedNode<T> node = new LinkedNode<T>(value);

        //如果没有头结点 新new出来的节点即是头节点也是尾节点
        if (head == null)
        {
            head = node;
            last = node;
        }
        //如果有头结点 让尾节点指向当前new出来的节点 让new出来的节点充当尾节点
        else
        {
            last.nextNode = node;
            last = node;
        }
    }

    //移除节点方法
    public void Remove(T value)
    {
        //如果没有头结点 说明没有节点存在里面 直接return
        if (head == null)
        {
            return;
        }

        //如果移除的是头节点
        if (head.value.Equals(value))
        {
            //是的话头结点往后移一个位置
            head = head.nextNode;

            //如果头节点 被移除 发现头节点变空
            //证明只有一个节点 那尾也要清空
            if (head == null)
            {
                last = null;
            }

            return;
        }

        //声明一个临时的指针节点 先指向头结点 遍历的往后找
        LinkedNode<T> node = head;
        while (node.nextNode != null)
        {
            ///如果当前节点的下一节点就是要移除的节点
            if (node.nextNode.value.Equals(value))
            {
                //让当前找到的这个元素的 上一个节点
                //指向 自己的下一个节点
                node.nextNode = node.nextNode.nextNode;
                node = node.nextNode;
                break;
            }
        }

        //这里其实有移除尾节点的bug 深究的话还要处理
    }
}

主函数内

//声明一个单向链表
LindedList<int> linkList = new LindedList<int>();

//加一点元素
linkList.Add(1);
linkList.Add(2);
linkList.Add(3);
linkList.Add(4);

//声明一个临时的指针节点 先指向头结点 遍历打印元素
LinkedNode<int> node = linkList.head;
while (node != null)
{
    Console.WriteLine(node.value);
    node = node.nextNode;
    //1
    //2
    //3
    //4
}

//移除了非头元素元素2后 重新指向头结点 再次遍历打印元素
linkList.Remove(2);
node = linkList.head;
while (node != null)
{
   

 Console.WriteLine(node.value);
    node = node.nextNode;
    //1
    //3
    //4
}

//移除了头元素元素1后 重新指向头结点 再次遍历打印元素
linkList.Remove(1);
node = linkList.head;
while (node != null)
{
    Console.WriteLine(node.value);
    node = node.nextNode;
    //3
    //4
}

//再加一个元素99 重新指向头结点 再次遍历打印元素
linkList.Add(99);
node = linkList.head;
while (node != null)
{
    Console.WriteLine(node.value);
    node = node.nextNode;
    //3
    //4
    //99
}

顺序存储和链式存储的优缺点

从增删查改的角度去思考：

增：链式存储计算上优于顺序存储（中间插入时链式不用像顺序一样去移动位置）。
删：链式存储计算上优于顺序存储（中间删除时链式不用像顺序一样去移动位置）。
查：顺序存储使用上优于链式存储（数组可以直接通过下标得到元素，链式需要遍历）。
改：顺序存储使用上优于链式存储（数组可以直接通过下标得到元素，链式需要遍历）。

10.2 知识点代码

using System;

namespace Lesson09_顺序存储和链式存储
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("顺序存储和链式存储");

            #region 知识点一 数据结构 

            //数据结构的概念
            //数据结构是计算机存储、组织数据的方式（规则）
            //数据结构是指相互之间存在一种或多种特定关系的数据元素的集合
            //比如自定义的一个 类 也可以称为一种数据结构 自己定义的数据组合规则
            //不要把数据结构想的太复杂
            //简单点理解，就是人定义的 存储数据 和 表示数据之间关系 的规则而已

            //常用的数据结构（前辈总结和制定的一些经典规则）
            //数组、栈、队列、链表、树、图、堆、散列表

            #endregion

            #region 知识点二 线性表

            //线性表是一种数据结构，是由n个具有相同特性的数据元素的有限序列
            //比如数组、ArrayList、Stack、Queue、链表等等

            #endregion

            //顺序存储和链式存储 是数据结构中两种 存储结构

            #region 知识点三 顺序存储

            //数组、Stack、Queue、List、ArrayList —— 顺序存储
            //只是 数组、Stack、Queue的 组织规则不同而已
            //顺序存储：用一组地址连续的存储单元依次存储线性表的各个数据元素

            #endregion

            #region 知识点四 链式存储

            //单向链表、双向链表、循环链表 —— 链式存储
            //链式存储(链接存储)：用一组任意的存储单元存储线性表中的各个数据元素

            #endregion

            //主函数内

            #region 知识点五 自己实现一个最简单的单向链表

            //声明一个单向链表
            LindedList<int> linkList = new LindedList<int>();

            //加一点元素
            linkList.Add(1);
            linkList.Add(2);
            linkList.Add(3);
            linkList.Add(4);

            //声明一个临时的指针节点 先指向头结点 遍历打印元素
            LinkedNode<int> node = linkList.head;
            while (node != null)
            {
                Console.WriteLine(node.value);
                node = node.nextNode;
                //1
                //2
                //3
                //4
            }

            //移除了非头元素元素2后 重新指向头结点 再次遍历打印元素
            linkList.Remove(2);
            node = linkList.head;
            while (node != null)
            {
                Console.WriteLine(node.value);
                node = node.nextNode;
                //1
                //3
                //4
            }

            //移除了头元素元素1后 重新指向头结点 再次遍历打印元素
            linkList.Remove(1);
            node = linkList.head;
            while (node != null)
            {
                Console.WriteLine(node.value);
                node = node.nextNode;
                //3
                //4
            }

            //再加一个元素99 重新指向头结点 再次遍历打印元素
            linkList.Add(99);
            node = linkList.head;
            while (node != null)
            {
                Console.WriteLine(node.value);
                node = node.nextNode;
                //3
                //4
                //99
            }

            #endregion
        }
    }

    //class语句块内 namespace语句块外

    #region 知识点五 自己实现一个最简单的单向链表

    /// <summary>
    /// 单向链表节点
    /// </summary>
    /// <typeparam name="T">泛型数据</typeparam>
    class LinkedNode<T>
    {
        //具体存储的数据
        public T value;

        //当前节点的下一节点
        public LinkedNode<T> nextNode;

        //构造函数 初始化值
        public LinkedNode(T value)
        {
            this.value = value;
        }
    }

    /// <summary>
    /// 单向链表类 管理 节点 管理 添加等等
    /// </summary>
    /// <typeparam name="T"></typeparam>
    class LindedList<T>
    {
        //头结点
        public LinkedNode<T> head;

        //尾结点
        public LinkedNode<T> last;

        //添加节点方法
        public void Add(T value)
        {
            //添加节点 必然是new一个新的节点
            LinkedNode<T> node = new LinkedNode<T>(value);

            //如果没有头结点 新new出来的节点即是头节点也是尾节点
            if (head == null)
            {
                head = node;
                last = node;
            }
            //如果有头结点 让尾节点指向当前new出来的节点 让new出来的节点充当尾节点
            else
            {
                last.nextNode = node;
                last = node;
            }
        }

        //移除节点方法
        public void Remove(T value)
        {
            //如果没有头结点 说明没有节点存在里面 直接return
            if (head == null)
            {
                return;
            }

            //如果移除的是头节点
            if (head.value.Equals(value))
            {
                //是的话头结点往后移一个位置
                head = head.nextNode;

                //如果头节点 被移除 发现头节点变空
                //证明只有一个节点 那尾也要清空
                if (head == null)
                {
                    last = null;
                }

                return;
            }

            //声明一个临时的指针节点 先指向头结点 遍历的往后找
            LinkedNode<T> node = head;
            while (node.nextNode != null)
            {
                ///如果当前节点的下一节点就是要移除的节点
                if (node.nextNode.value.Equals(value))
                {
                    //让当前找到的这个元素的 上一个节点
                    //指向 自己的下一个节点
                    node.nextNode = node.nextNode.nextNode;
                    node = node.nextNode;
                    break;
                }
            }

            //这里其实有移除尾节点的bug 深究的话还要处理
        }
    }

    #endregion

    #region 知识点六 顺序存储和链式存储的优缺点
    //从增删查改的角度去思考
    //增：链式存储 计算上 优于顺序存储 （中间插入时链式不用像顺序一样去移动位置）
    //删：链式存储 计算上 优于顺序存储 （中间删除时链式不用像顺序一样去移动位置）
    //查：顺序存储 使用上 优于链式存储 （数组可以直接通过下标得到元素，链式需要遍历）
    //改：顺序存储 使用上 优于链式存储 （数组可以直接通过下标得到元素，链式需要遍历）
    #endregion
}

10.3 练习题

常用的数据结构有哪些

常用的数据结构包括：

数组
栈
队列
链表
树
图
堆
散列表

顺序存储和链式存储的区别

顺序存储：在内存中使用一组地址连续的存储单元存储线性表，数据元素之间的逻辑关系由它们在存储器中的相对位置来体现。数组就是一种顺序存储结构。
链式存储：在内存中使用一组任意的存储单元存储线性表，数据元素之间的逻辑关系不是通过物理位置来表示的，而是通过每个节点中的指针来表示。链表就是一种典型的链式存储结构。

实现一个双向链表,并提供以下方法和属性:数据的个数,头节点,尾节点,增加数据到链表最后,删除指定位置节点

class语句块内 namespace语句块外

// 节点类
class LinkedNode<T>
{
    // 存储的值
    public T value;
    
    // 上一个节点
    public LinkedNode<T> frontNode;
    
    // 下一个节点
    public LinkedNode<T> nextNode;
    
    // 节点类构造函数 初始化存储的值
    public LinkedNode(T value)
    {
        this.value = value;
    }
}

// 链表类
class LinkedList<T>
{
    // 链表长度
    private int count = 0;
    
    // 头结点
    private LinkedNode<T> head;
    
    // 尾节点
    private LinkedNode<T> last;
    
    // 链表长度属性
    public int Count
    {
        get { return count; }
    }
    
    // 头结点属性
    public LinkedNode<T> Head
    {
        get { return head; }
    }
    
    // 尾节点属性
    public LinkedNode<T> Last
    {
        get { return last; }
    }
    
    // 添加节点方法
    public void Add(T value)
    {
        // 新加的节点
        LinkedNode<T> node = new LinkedNode<T>(value);
        
        // 如果头结点为空
        if (head == null)
        {
            // 新加的节点即是头结点也是尾节点
            head = node;
            last = node;
        }
        // 如果头结点不为空
        else
        {
            // 新加的节点添加到尾部
            last.nextNode = node;
            // 新加的节点 记录自己的上一个节点是谁
            node.frontNode = last;
            // 让当前新加的节点变成最后一个节点
            last = node;
        }
        // 加了一个节点 链表长度+1
        ++count;
    }
    
    // 根据索引移除节点方法
    public void RemoveAt(int index)
    {
        // 首先判断是否越界
        if (index >= count || index < 0)
        {
            Console.WriteLine("只有{0}个节点，请输入合法位置", count);
            return;
        }
        
        // 创建临时索引和临时节点变量
        int tempCount = 0;
        LinkedNode<T> tempNode = head;
        
        // 遍历链表
        while (true)
        {
            // 找到了对应位置的要移除的节点 然后移除即可
            if (tempCount == index)
            {
                // 当前要移除的节点的上一个节点 指向当前要移除的节点的下一个节点
                if (tempNode.frontNode != null)
                {
                    tempNode.frontNode.nextNode = tempNode.nextNode;
                }
                // 当前要移除的节点的下一个节点 指向当前要移除的节点的上一个节点
                if (tempNode.nextNode != null)
                {
                    tempNode.nextNode.frontNode = tempNode.frontNode;
                }
                // 如果是头节点，需要改变头节点的指向
                if (index == 0)
                {
                    // 如果头节点被移除，那头节点就变成了头节点的下一个
                    head = head.nextNode;
                }
                // 如果是尾节点，需要改变尾节点的指向
                else if (index == count - 1)
                {
                    // 如果尾节点被移除了，那尾结点就变成了尾结点的上一个
                    last = last.frontNode;
                }
                // 移除了一个节点 链表长度-1
                --count;
                break;
            }
            // 每次循环完过后，让当前临时节点等于下一个节点
            tempNode = tempNode.nextNode;
            // 索引+1
            ++tempCount;
        }
    }
}

主函数内

// 创建一个链表，添加几个元素
LinkedList<int> link = new LinkedList<int>();
link.Add(1);
link.Add(2);
link.Add(3);
link.Add(4);

// 正向遍历
LinkedNode<int> node = link.Head;
while (node != null)
{
    Console.WriteLine(node.value);
    node = node.nextNode;
}
// 1
// 2
// 3
// 4

// 反向遍历
node = link.Last;
while (node!= null)
{
    Console.WriteLine(node.value);
    node = node.frontNode;
}
// 4
// 3
// 2
// 1

// 移除第0个元素后
link.RemoveAt(0);

// 正向遍历
node = link.Head;
while (node != null)
{
    Console.WriteLine(node.value);
    node = node.nextNode;
}
// 2
// 3
// 4

// 反向遍历
node = link.Last;
while (node != null)
{
    Console.WriteLine(node.value);
    node = node.frontNode;
}
// 4
// 3
// 2

// 移除第1个元素后
link.RemoveAt(1);

// 正向遍历
node = link.Head;
while (node != null)
{
    Console.WriteLine(node.value);
    node = node.nextNode;
}
// 2
// 4

// 反向遍历
node = link.Last;
while (node != null)
{
    Console.WriteLine(node.value);
    node = node.frontNode;
}
// 4
// 2

// 移除第1个元素后
link.RemoveAt(1); // 只有1个节点，请输入合法位置

10.4 练习题代码

using System;

namespace Lesson09_练习题
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("顺序存储和链式存储练习题");

            #region 练习题一
            //请说出常用的数据结构有哪些
            #region 答案
            //数组、栈、队列、链表、树、图、堆、散列表
            #endregion
            #endregion

            #region 练习题二
            //请描述顺序存储和链式存储的区别
            #region 答案
            //顺序存储：内存中用一组地址连续的存储单元存储线性表(连续地址存储)
            //链式存储：内存中用一组任意的存储单元存储线性表(任意地址存储)
            #endregion
            #endregion

            //主函数内

            #region 练习题三
            //请尝试自己实现一个双向链表
            //并提供以下方法和属性
            //数据的个数，头节点，尾节点
            //增加数据到链表最后
            //删除指定位置节点

            //创建一个链表 添加几个元素
            LinkedList<int> link = new LinkedList<int>();
            link.Add(1);
            link.Add(2);
            link.Add(3);
            link.Add(4);
            //正向遍历
            LinkedNode<int> node = link.Head;
            while (node != null)
            {
                Console.WriteLine(node.value);
                node = node.nextNode;
                //1
                //2
                //3
                //4
            }
            //反向遍历
            node = link.Last;
            while (node != null)
            {
                Console.WriteLine(node.value);
                node = node.frontNode;
                //4
                //3
                //2
                //1
            }

            //移除第0个元素后
            link.RemoveAt(0);
            //正向遍历
            node = link.Head;
            while (node != null)
            {
                Console.WriteLine(node.value);
                node = node.nextNode;
                //2
                //3
                //4
            }
            //反向遍历
            node = link.Last;
            while (node != null)
            {
                Console.WriteLine(node.value);
                node = node.frontNode;
                //4
                //3
                //2
            }

            //移除第1个元素后
            link.RemoveAt(1);
            //正向遍历
            node = link.Head;
            while (node != null)
            {
                Console.WriteLine(node.value);
                node = node.nextNode;
                //2
                //4
            }
            //反向遍历
            node = link.Last;
            while (node != null)
            {
                Console.WriteLine(node.value);
                node = node.frontNode;
                //4
                //2
            }

            //移除第1个元素后
            link.RemoveAt(1);
            //正向遍历
            node = link.Head;
            while (node != null)
            {
                Console.WriteLine(node.value);
                node = node.nextNode;
                //2
            }
            //反向遍历
            node = link.Last;
            while (node != null)
            {
                Console.WriteLine(node.value);
                node = node.frontNode;
                //2
            }

            //移除第1个元素后
            link.RemoveAt(1); //只有1个节点，请输入合法位置

            #endregion
        }
    }

    //class语句块内 namespace语句块外

    #region 练习题三

    //节点类
    class LinkedNode<T>
    {
        //存储的值
        public T value;

        //上一个节点
        public LinkedNode<T> frontNode;

        //下一个节点
        public LinkedNode<T> nextNode;

        //节点类构造函数 初始化存储的值
        public LinkedNode(T value)
        {
            this.value = value;
        }
    }

    //链表类
    class LinkedList<T>
    {
        //链表长度
        private int count = 0;

        //头结点
        private LinkedNode<T> head;

        //尾节点
        private LinkedNode<T> last;

        //链表长度属性
        public int Count
        {
            get
            {
                return count;
            }
        }

        //头结点属性
        public LinkedNode<T> Head
        {
            get
            {
                return head;
            }
        }

        //尾节点属性
        public LinkedNode<T> Last
        {
            get
            {
                return last;
            }
        }

        //添加节点方法
        public void Add(T value)
        {
            //新加的节点
            LinkedNode<T> node = new LinkedNode<T>(value);

            //如果头结点为空
            if (head == null)
            {
                //新加的节点即是头结点也是尾节点
                head = node;
                last = node;
            }

            //如果头结点不为空
            else
            {
                //新加的节点添加到尾部
                last.nextNode = node;
                //新加的节点 记录自己的上一个节点是谁
                node.frontNode = last;
                //让当前新加的节点变成最后一个节点
                last = node;
            }

            //加了一个节点 链表长度+1
            ++count;
        }

        //根据索引移除节点方法
        public void RemoveAt(int index)
        {
            //首先判断 有没有越界
            if (index >= count || index < 0)
            {
                Console.WriteLine("只有{0}个节点，请输入合法位置", count);
                return;
            }

            //创建临时索引和临时节点变量
            int tempCount = 0;
            LinkedNode<T> tempNode = head;

            //遍历链表
            while (true)
            {
                //找到了对应位置的要移除的节点 然后移除即可
                if (tempCount == index)
                {
                    //当前要移除的节点的上一个节点 指向当前要移除的节点的下一个节点
                    if (tempNode.frontNode != null)
                    {
                        tempNode.frontNode.nextNode = tempNode.nextNode;
                    }
                    //当前要移除的节点的下一个节点 指向当前要移除的节点的上一个节点
                    if (tempNode.nextNode != null)
                    {
                        tempNode.nextNode.frontNode = tempNode.frontNode;
                    }

                    //如果是头节点 那需要改变头节点的指向
                    if (index == 0)
                    {
                        //如果头节点被移除 那头节点就变成了头节点的下一个
                        head = head.nextNode;
                    }
                    //如果是尾节点 那需要改变尾节点的指向
                    else if (index == count - 1)
                    {
                        //如果尾节点被移除了 那尾结点就变成了尾结点的上一个
                        last = last.frontNode;
                    }

                    //移除了一个节点 链表长度-1
                    --count;
                    break;
                }

                //每次循环完过后 要让当前临时节点 等于下一个节点
                tempNode = tempNode.nextNode;
                //索引+1
                ++tempCount;
            }
        }
    }

    #endregion
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com