数组和集合ppt课件.ppt

《数组和集合ppt课件.ppt》由会员分享，可在线阅读，更多相关《数组和集合ppt课件.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数组和集合ppt课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望主要内容主要内容System.Array类数组的相关操作集合框架集合集合一个集合是一个对象，它代表了一组对象，（可以看作是一组对象的容器）。数组是简单集合，System.Array类是所有数组的基类System.Array类型类型 System.Array类是一些原始方法和一系列接口实现的混合体。类定义：public abstract class Array:public abstract cla

2、ss Array:ICloneable,ICollection,IList,IEnumerableICloneable,ICollection,IList,IEnumerable/类体类体 n n所谓框架就是一个类库的集合，集合框架就是一个用来表示和操作集合的统一的架构，包含了实现集合的接口与类n nICloneablen nIEnumerablen nIEnumerator集合框架中的接口集合框架中的接口集合框架中的接口集合框架中的接口n nICloneable：提供了创建现有对象的副本的标准方式。提供了创建现有对象的副本的标准方式。interface ICloneableinterface

3、 ICloneable object Clone();Clone()Clone()方法会返回一个与当前对象类型相同的新实例，这个返回的方法会返回一个与当前对象类型相同的新实例，这个返回的对象会被初始化为与当前对象相同的内容。对象会被初始化为与当前对象相同的内容。1 1、影子复制、影子复制2 2、深度复制、深度复制IEnumerable可枚举接口：如果某个类实现了如果某个类实现了IEnumerableIEnumerable接口，则称该类是可枚接口，则称该类是可枚举的，可枚举类型都可以使用举的，可枚举类型都可以使用foreachforeach循环来遍历集合中的循环来遍历集合中的每个元素。所有集合类

4、都实现了该接口。每个元素。所有集合类都实现了该接口。interface IEnumerable interface IEnumerable IEnumerator Getenumerator();Getenumerator();集合框架中的接口集合框架中的接口n nIEnumerator枚举器接口:它提供的方法成员用于查询可枚举集合的状态及访问它提供的方法成员用于查询可枚举集合的状态及访问集合中的元素。它给我们提供了一种通用的方式来访问集集合中的元素。它给我们提供了一种通用的方式来访问集合中的元素。合中的元素。interface Ienumeratorinterface Ienumerator

5、 ObjectObject Current get;Current get;boolbool MoveNext()MoveNext()；voidvoid Reset()Reset()集合框架中的接口集合框架中的接口可枚举集合IEnumerator枚举器对象IEnumerable集合框架中的接口集合框架中的接口Iterator模式在.NET类库中的实现Reset()MoveNext()CurrentGetEnumerator()方法产生遍历集合集合框架中的接口集合框架中的接口Iterator模式作用：对集合中的一系列元素进行访问。作用：对集合中的一系列元素进行访问。基本思想：集合对象只负责维护集

6、合中的各个基本思想：集合对象只负责维护集合中的各个元素，而对元素的访问则通过定义一个新的枚元素，而对元素的访问则通过定义一个新的枚举器对象来进行；枚举器对象负责获取集合中举器对象来进行；枚举器对象负责获取集合中的元素，并允许按照特定的顺序来遍历这些元的元素，并允许按照特定的顺序来遍历这些元素。素。迭代器的工作原理迭代器的工作原理返回的元素MoveNext()MoveNext()MoveNext()Reset()Current返回当前元素集合类集合类n nC#以数组形式提供对集合的支持。但数组是定长的，如果元素会不断增长或缩减，那么数组就难当此任了。n n集合类则很好地解决了这些问题。集合框架中

7、的接口集合框架中的接口基本接口：ICloneableIEnumerableIEnumeratorICollectionIListIDictionary 这些接口通常都是大多数集合类实现的这些接口通常都是大多数集合类实现的ICollection：所有集合的根本，为.NET框架中的所有集合类所实现。该接口定义了集合类的最低约束。interface ICollectioninterface ICollection int Count get;void CopyTo(Array array,int index);bool IsSynchronizedget;bool IsSynchronizedget

8、;object SynchRootget;object SynchRootget;集合框架中的接口集合框架中的接口IList：实现了实现了IListIList的集合提供类似于列表的语法。的集合提供类似于列表的语法。interface IListinterface IList int Add(object value);void Remove(object key);void Insert(int index,object value);void Clear();void Clear();bool Contains(object value);bool Contains(object value

9、);int IndexOf(object value);int IndexOf(object value);void RemoveAt(int index);void RemoveAt(int index);集合框架中的接口集合框架中的接口IDictinary：由支持将关键字映射到值这一操作由支持将关键字映射到值这一操作的集合类所实现。的集合类所实现。interface IDictionaryinterface IDictionary ICollection Keys get;ICollection Values get;object this object key get;set;objec

10、t this object key get;set;void Add(object key,object value);bool Contains(object key);bool Contains(object key);void Remove(object key);IDictionaryEnmerator GetEnumerator();集合框架中的接口集合框架中的接口集合框架中的实现类集合框架中的实现类ICollectionIEnumerableICloneableIListArrayList Hashtable SortedList IDictionary集合框架中的实现类集合框架中

11、的实现类ICollectionIEnumerableICloneableIListStack Queue IDictionaryArrayListn nArrayList：我们可以将其看作是能够自动增长容量的动态数组，它实现了IList接口。(1)Capacity 集合容量，读写属性(2)Count 获取列表中实际包含元素的个数(3)Add()方法：列表末尾添加元素(4)Insert()方法：列表指定位置添加元素(5)Remove()方法：移除特定对象(6)RemoveAt()方法：根据索引值移除对象ArrayListn n列表到数组的转换利用ArrayList的ToArray()返回一个数组

12、。n n列表中对象的排序利用ArrayList中的Sort()方法。数据结构数据结构n n一般将数据结构分为两大类：线性数据结线性数据结构和非线性数据结构构和非线性数据结构。线性数据结构有线性表、栈、队列、串、数组和文件；非线性数据结构有树和图。线线性性表表线性表的逻辑结构是线性表的逻辑结构是n n个数据元素的有限序列个数据元素的有限序列:(a(a1 1,a,a2 2,a,a3 3,a an n)n n为线性表的长度为线性表的长度(n0)(n0)，n=0n=0的表称为空表。的表称为空表。n n数据元素呈线性关系。必存在唯一的称为数据元素呈线性关系。必存在唯一的称为“第一第一个个”的数据元素；必

13、存在唯一的称为的数据元素；必存在唯一的称为“最后一个最后一个”的数据元素；除第一个元素外，每个元素都有的数据元素；除第一个元素外，每个元素都有且只有一个前驱元素；且只有一个前驱元素；除最后一个元素外，每个除最后一个元素外，每个元素都有且只有一个后继元素。元素都有且只有一个后继元素。n n所有数据元素在同一个线性表中必须是相同的数所有数据元素在同一个线性表中必须是相同的数据类型。据类型。线线性性表表n n线性表按其存储结构可分为顺序表和链表。用顺序存储结构存储的线性表称为顺序表顺序表；用链式存储结构存储的线性表称为链表链表。n n将线性表中的数据元素依次存放在某个存储区域中,所形成的表称为顺序表

14、顺序表。一维数一维数组组就是用顺序方式存储的线性表。链表链表n n单向链表datanextdatanextdatanextnullhead节点链表链表datanextdatanextdatanextnullhead节点插入插入datanextdatanextdatanextdatanextnullhead节点删除删除链表链表n n循环链表datanextdatanextdatanexthead节点链表链表n n双向循环链表datanextdatanextdatanexthead节点previouspreviousprevious栈栈n n栈栈(Stack)(Stack)也是一种特殊的线性表，也

15、是一种特殊的线性表，是一种后进先出是一种后进先出(LIFO)(LIFO)的结构。的结构。n n栈是限定仅在表尾进行插入和删栈是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶除运算的线性表，表尾称为栈顶(top)(top)，表头称为栈底，表头称为栈底(bottom)(bottom)。n n栈的物理存储可以用顺序存储结栈的物理存储可以用顺序存储结构，也可以用链式存储结构构，也可以用链式存储结构。a1a1a2a2anan栈底栈顶出栈进栈队列队列队列队列(Queue)(Queue)是限定所有的插入只能在表的一端进行，而是限定所有的插入只能在表的一端进行，而所有的删除都在表的另一端进行的线性表。所

16、有的删除都在表的另一端进行的线性表。表中允许插入的一端称为队尾表中允许插入的一端称为队尾(Rear)(Rear)，允许删除的一端称，允许删除的一端称为队头为队头(Front)(Front)。队列的操作是按先进先出队列的操作是按先进先出(FIFO)(FIFO)的原则进行的。的原则进行的。队列的物理存储可以用顺序存储结构，也可以用链式存储队列的物理存储可以用顺序存储结构，也可以用链式存储结构。结构。a1 a2 a3 ana1 a2 a3 an队头队尾出队 入队Hashtablen n它表示一个键（key）/值（value）对的集合,该集合的条目是DictionaryEntry结构实例。n n结构体

17、DictionaryEntry有一个Key和Value属性用来读取和设置键和值。n n存储的条目不能有相同的键值。键的比较是基于键的哈希码顺序进行的。我们应该为要存放到散列表的各个对象定义HashCode()和Equals()。Hashtable它实现了IDictionary接口(1)void Add(object key,object value);(2)void Remove(object key);(3)void Clear();(4)bool Contains(object key);(5)object this object key get;set;注：只能通过Hashtableke

18、y来访问/设置相应value,不能通过Hashtableindex访问元素。散列表散列表散列表又称为哈希表。散列表算法的基本思想是：散列表又称为哈希表。散列表算法的基本思想是：以结点的关键字为自变量，通过一定的函数关系（散列以结点的关键字为自变量，通过一定的函数关系（散列函数）计算出对应的函数值，以这个值作为该结点存储在函数）计算出对应的函数值，以这个值作为该结点存储在散列表中的地址。散列表中的地址。当散列表中的元素存放太满，就必须进行再散列，将产生当散列表中的元素存放太满，就必须进行再散列，将产生一个新的散列表，所有元素存放到新的散列表中，原先的一个新的散列表，所有元素存放到新的散列表中，原

19、先的散列表将被删除。在散列表将被删除。在C#C#语言中，通过负载因子语言中，通过负载因子(load(load factor)factor)来决定何时对散列表进行再散列。例如：如果负载来决定何时对散列表进行再散列。例如：如果负载因子是因子是0.750.75，当散列表中已经有，当散列表中已经有75%75%的位置已经放满，那的位置已经放满，那么将进行再散列。么将进行再散列。负载因子越高负载因子越高(越接近越接近1.0)1.0)，内存的使用效率越高，元素的，内存的使用效率越高，元素的寻找时间越长。负载因子越低寻找时间越长。负载因子越低(越接近越接近0.0)0.0)，元素的寻找时，元素的寻找时间越短，内

20、存浪费越多。间越短，内存浪费越多。HashtableHashtable类的缺省负载因子是类的缺省负载因子是0.750.75。Hashtablen n说明：说明：HashtableHashtable存储元素时，根据对象的散列码来计算它存储元素时，根据对象的散列码来计算它的储位置，而散列码是利用的储位置，而散列码是利用ObjectObject类中的类中的HashCodeHashCode()()方法来获取的，该方法是利用对象在内存中的地方法来获取的，该方法是利用对象在内存中的地来获取散列码的。来获取散列码的。SortedListn n表示键/值对集，且条目按键排序n n可按键或按索引来访问，即它综合了ArrayList和Hashtable的功能和优点。