注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

信息 灵感 创新

I? =Information,Inspiration,Innovation

 
 
 

日志

 
 
关于我

we are 5. Mathematics, Computation, Programming, Engineering, and Making fun of life.

网易考拉推荐

数组、索引器和集合(十)  

2010-12-27 16:38:46|  分类: C# & .NET |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

链表

链表LinkedList<T>集合类没有非泛型集合的类似版本。LinkedList<T>是一个双向链表其元素指向它前面和后面的元素如下图:

数组、索引器和集合(十) - Castor - 趁年轻,多折腾~~

 

链表的优点是,如果将元素插入列表的中间位置,使用链表会非常快。在插入一个元素时,只需修改上一个元素的Next 引用和下一个元素的Previous 引用,使它们引用所插入的元素,而在List<T>ArrayList 类中,插入一个元素,需要移动该元素后面的所有元素。链表也有缺点。链表的元素只能一个接一个地访问,这需要较长的时间来查找位于链表中间或尾部的元素。链表不仅能在列表中存储元素,还可以给每个元素存储下一个元素和上一个元素的信息,这就是LinkedList<T> 包含节点类LinkedListNode<T> 类型的元素的原因。使用LinkedListNode<T>类,可以获得列表中的下一个元素和上一个元素。

LinkListNode的重要属性如下:

属性

说明

List

返回与节点相关的LinkedList<T>

Next

返回当前节点之后的节点,返回类型是LinkedListNode<T>

Previous

返回当前节点之前的节点,返回类型是LinkedListNode<T>

Value

返回与节点相关的元素

LinkedList<T>执行了IEnumerable<T>ICollection<T>ICollectionIenumerableIserializable IdeserializationCallback 接口。该类的属性或方法如下表:

属性或方法

说明

Count

返回链表中的元素个数

First

返回链表中的第一个节点。其返回类型是LinkedListNode<T>。使用这个返回的节点,可以迭代集合中的其他节点

Last

返回链表中的最后一个元素。其返回类型是LinkedListNode<T>

AddAfter()

AddBefore()

AddFirst()

AddLast()

使用AddXXX 方法可以在链表中添加元素。使用相应的Add 方法,可以在链表的指定位置添加元素。AddAfter()需要一个LinkedListNode<T>对象,在该对象中可以指定要添加的新元素后面的节点。AddBefore()把新元素放在第一个参数定义的节点前面。AddFirst()AddLast()把新元素添加到链表的开头和结尾重载所有这些方法来接收任一个对象以添加类型LinkedListNode<T>或类型T。如果传送T 对象,则创建一个新LinkedListNode<T>对象

Remove()

RemoveFirst()

RemoveLast()

Remove() RemoveFirst() RemoveLast() 方法从链表中删除节点。

Remove()需要搜索一个对象,从链表中删除匹配该对象的第一个节点

RemoveFirst() 删除第一个元素, RemoveLast() 删除最后一个元素。

Clear()

从链表中删除所有的节点

Contains()

在链表中搜索一个元素,如果找到该元素,就返回true,否则返回false

Find()

从链表的开头开始搜索传送给它的元素,并返回一个LinkedListNode<T>

FindLast()

Find()方法类似,但从链表的结尾开始搜索

注意链表中Remove方法删除节点之后程序能自动将该节点前后的节点连接起来,比用C语言方便了许多。

使用链表的一个经典例子是约瑟夫(Josephus)环问题:已知n个人(以编号123...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列,现在要求写一个函数,通过提供总人数n、报数m,开始报数人的编号k,给出出列的序列。

这里使用链表,并将前面的队列作一个简单的练习,将出列顺序保存在一个队列中。代码如下:

using System;

using System.Collections.Generic;

using System.Text;

namespace Castor

{

    class Test

    {

        //主程序入口

        static void Main(string[] args)

        {

            PrintCollection(Josephus(17, 4, 1));

            Console.Read();

        }

        /// <summary>

        /// 约瑟夫Josephus问题求解

        /// 注意圆环编号范围是~n

        /// </summary>

        /// <param name="n">总人数</param>

        /// <param name="m">报数长度</param>

        /// <param name="k">开始报数人编号</param>

        public static Queue<int> Josephus(int n, int m, int k)

        {

            LinkedList<int> iLL = new LinkedList<int>();

            Queue<int> Result = new Queue<int>(n);

            //初始化链表

            for (int i = 1; i <= n; i++)

            {

                LinkedListNode<int> lln = new LinkedListNode<int>(i);

                iLL.AddLast(lln);

            }

            //定位到开始报数人

            LinkedListNode<int> first = iLL.First;           

            for (int i = 0; i < k - 1; i++)

                first = (first == iLL.Last ? iLL.First : first.Next);

            LinkedListNode<int> start;

            do

            {

                for (int i = 0; i < m - 1; i++)

                    first = (first == iLL.Last ? iLL.First : first.Next);

                start = first;

                first = (first == iLL.Last ? iLL.First : first.Next);

                Result.Enqueue(start.Value);

                iLL.Remove(start);

            } while (iLL.Count >= 1);

            return Result;

        }

        public static void PrintCollection(IEnumerable<int> MyColl)

        {

            //返回一个循环访问集合的枚举数

            IEnumerator<int> MyIEnum = MyColl.GetEnumerator();

            while (MyIEnum.MoveNext())

            {

                Console.Write("{0} ", MyIEnum.Current);

            }

            Console.WriteLine();

        }

    }

}

运行效果如下:

数组、索引器和集合(十) - Castor - 趁年轻,多折腾~~

 

  评论这张
 
阅读(462)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2016