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

信息 灵感 创新

I? =Information,Inspiration,Innovation

 
 
 

日志

 
 
关于我

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

网易考拉推荐

用C#学数据结构(4)  

2011-07-30 14:57:28|  分类: C# & .NET |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
声明:本人非计算机专业人士,没有过多的时间、经历和能力深入研究数据结构的实现,所以本系列文章不处理数据结构的实现,主要是练习各种数据结构的使用。欢迎大家交流讨论。

链表

顺序表是用地址连续的存储单元顺序存储线性表中的各个数据元素,逻辑上相邻的数据元素在物理位置上也相邻。因此,在顺序表中查找任何一个位置上的数据元素非常方便,这是顺序存储的优点。

链式存储(Linked Storage)的线性表叫链表(Linked List)。不要求逻辑上相邻的数据元素在物理存储位置上也相邻,

在对链表进行插入和删除时不需要移动数据元素,但也失去了顺序表可随机存储的优点。

在存储数据元素时,除了存储数据元素本身的信息外,还要存储与它相邻的数据元素的存储地址信息。这两部分信息组成该数据元素的存储映像(Image),称为结点(Node)

存储据元素的域叫结点的数据域(Data Domain)

存储与它相邻的数据元素的存储地址信息的域叫引用域(Reference Domain)

一个基本的节点形式如下:

数据域

引用域

通常的使用如下形式表示:

Data

Next

C#中的节点类

C#中用LinkedListNode<T> 类实现节点,该类中包含一个值、对其所属的 LinkedList 的引用、对下一个节点的引用,以及对上一个节点的引用。可见它扩充了基本节点,具有更多的属性,各属性说明如下:

属性

说明

List

获取 LinkedListNode<T> 所属的 LinkedList<T>

Next

获取 LinkedList<T> 中的下一个节点。 

Previous

获取 LinkedList<T> 中的上一个节点。 

Value 

获取节点中包含的值。 

C#中的链表类

LinkedList实现了链表类,它包含 LinkedListNode 类型的单独节点,如果节点及其值是同时创建的,则包含引用类型的列表性能会更好。由于LinkedListNode具有NextPrevious属性,因此LinkedList是双向链表。

LinkedList的属性和方法如下:

成员

说明

Count

获取LinkedList中实际包含的节点数

First

获取LinkedList的第一个节点

Last

获取LinkedList的最后一个节点

AddAfter

LinkedList中的现有节点后添加新的节点或值 

AddBefore

LinkedList中的现有节点前添加新的节点或值 

AddFirst

LinkedList的开头处添加新的节点或值 

AddLast

LinkedList的结尾处添加新的节点或值 

Clear

LinkedList中移除所有节点 

Contains

确定某值是否在LinkedList 

CopyTo

从目标数组的指定索引处开始将整个LinkedList复制到兼容的一维Array

Find

查找包含指定值的第一个节点 

FindLast

查找包含指定值的最后一个节点 

Remove

LinkedList中移除节点或值的第一个匹配项 

RemoveFirst

移除位于LinkedList开头处的节点 

RemoveLast

移除位于LinkedList结尾处的节点 

使用实例:将一个链表倒置

using System;

using System.Collections.Generic;

namespace DataStruct

{

    class Program

    {

        static void Main(string[] args)

        {

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

            for (int i = 0; i < 10; i++)

            {

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

                LL.AddLast(lln);

            }

            ShowLinkedListData(LL);

            ReverseLinkedList(ref LL);

            ShowLinkedListData(LL);

 

            Console.Read();

        }

        public static void ShowLinkedListData(LinkedList<int> L)

        {

            foreach (int i in L)

                Console.Write(i.ToString() + " ");

            Console.WriteLine();

        }

        public static void ReverseLinkedList(ref LinkedList<int> L)

        {

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

            foreach (int i in L)

                L2.AddFirst(i);

            L = L2;

        }

    }

}

注意这里使用的按引用方式传递,所以会修改原始链表,如果不想修改的话,也可以使用按值传递参数,并返回一个LinkedList对象实例的方式。

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

历史上的今天

评论

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

页脚

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