ITPub博客

首页 > 应用开发 > IT综合 > C#数据结构-静态链表

C#数据结构-静态链表

原创 IT综合 作者:只爱宅zmy 时间:2020-10-13 14:33:03 2 删除 编辑
对于双向链表中的节点,都包括一个向前、向后的属性器用于指向前后两个节点,对于引用类型,对象存储的是指向内存片段的内存指针,那么我们可以将其简化看作向前向后的两个指针。
现在我们将引用类型替换为值类型int,将链用数组代替,向后的指针替换为数组的下标,那么此时的链我们称为静态链表(或者说是单向静态链表)。
不多说,直接上代码(代码已做注解)
public class Node<T>
    {
        public T data { get; set; }
        public int next { get; set; }
        public Node(T item)
        {
            data = item;
        }
    }
public class StaticLink<T>
    {
        public int count { get; set; } = 0;
        public Node<T>[] link { get; set; }
        public int minSize { get; set; } = 10;
        public int extendSize { get; set; } = 10;//扩容步长
        public StaticLink()
        {
            //第一个节点为空节点,不存储内容,同时,第一个节点的next存放备用链表的第一个节点(备用链表——数组内可以用于存储内容的处于空值时的节点连接成的表)
            //初始化,静态链表的长度为10;
            link = new Node<T>[minSize];
            for (int i = 0; i < minSize; i++)
            {
                //i=0时,由于链表为空,则备用链表的第一个节点也就是1
                link[i] = new Node<T>(default(T));
                link[i].next = i + 1;
            }
            //初始化,静态链表的结尾next 指向第一个节点(除头节点外)
            link[minSize - 1].next = 1;
            count++;
        }
        private int Malloc()
        {
            //取得静态链表-备用链表中的第一个节点(取出待用,存储内容)
            int i = link[0].next;
            if (i > 0)
            {
                //同时,移除备用链表的第一个节点,
                link[0].next = link[i].next;
                //取到链表的最后一个元素时,扩容。
                if (i >= minSize - 1)
                {
                    //todo 不翻倍扩容,采用定值步长扩容~
                    //todo 暂不实现
                }
            }
            return i;
        }
        /// <summary>
        /// 在链表的结尾附加
        /// </summary>
        /// <param name="node"></param>
        public void Append(T node)
        {
            Insert(count, node);
        }
        /// <summary>
        /// 指定位置插入节点
        /// </summary>
        /// <param name="index"></param>
        /// <param name="node"></param>
        public void Insert(int index, T node)
        {
            //要插入的节点需要在链表的范围内
            if (index > count || index < 1)
                throw new IndexOutOfRangeException("索引超出界限");
            //由于时插入节点,所以此处我们需要从备用链表取出一个空节点。
            int maxIndex = Malloc();
            int k = minSize - 1; 
            Node<T> newNode = new Node<T>(node);//创建一个节点
            if (count == 1)
                newNode.next = 0;
            else 
            {
                //取链表最后一个节点的next;
                for (int i = 1; i <= index -1; i++)
                {
                    k = link[k].next;
                }
                newNode.next = link[k].next;
                link[k].next = maxIndex;
            }
            link[maxIndex] = newNode;
            count++;
        }
        /// <summary>
        /// 根据索引删除
        /// </summary>
        /// <param name="index"></param>
        public void Del(int index)
        {
            //去除头节点,并判断索引要在链表范围内
            if (index < 1 || index > count)
                throw new IndexOutOfRangeException("索引超出界限");
            int k = minSize - 1;
            //通过链取得前一个节点 -时间复杂度O(n)
            for (int j = 1; j <= index - 1; j++)
            {
                k = link[k].next;
            }
            int beforeNodeNext = link[k].next;//获取前一个节点的next;
            link[k].next = link[beforeNodeNext].next;//跳过要删除的节点
            link[beforeNodeNext].next = link[0].next;//将释放除来的节点接入备用链
            link[0].next = beforeNodeNext;//将当前释放的节点放入到备用的第一个节点。-待用
            count--;
        }
        /// <summary>
        /// 展示链节点
        /// </summary>
        public void showAll()
        {
            for (int i = 1; i <= count; i++)
            {
                Console.WriteLine($"index:{link[i].next},data:{link[i].data}");
            }
        }
  }
测试:
class Program
    {
        static void Main(string[] args)
        {
            StaticLink<string> link = new StaticLink<string>();
            link.Append("第一位");
            link.Append("第二位");
            link.Append("第三位");
            link.Insert(2,"第四位,插入到二的位置");
            link.Append("第五位");
            link.Append("第六位");
            link.Append("第七位");
            link.Del(6);
            link.showAll();
            Console.ReadLine();
        }
    }
打印结果:

404258-20201013130149060-865023213.png
 
 


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/69983372/viewspace-2726568/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2020-09-07

  • 博文量
    24
  • 访问量
    8660