数据结构的第二讲.ppt

第二讲 顺序线性表数组,引例,第二讲 数组,2.1 线性表及顺序线性表2.2 数组基本概念 2.3 ArrayList类,2.1 线性表及顺序线性表,线性表,例1 英文字母表（A，B，C，Z)是一个线性表例2,数据元素,线性表,n个类型相同的数据元素的有限序列，数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继。,线性表,定义：n（0）个数据元素的有限序列，记作（a1,ai-1,ai,ai+1,an）其中,ai 是表中数据元素，n 是线性表的长度，n=0时称为空表特点:同一线性表中元素具有相同特性。相邻数据元素之间存在序偶关系。除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。,同一性,有序性,有穷性,将线性表中的元素相继存放在一个连续的存储空间中。顺序线性表，简称线性表用一组地址连续的存储单元依次存储线性表的数据元素。顺序映像,顺序表,存储结构：数组。特点：线性表的顺序存储方式。存取方式：顺序访问,可以随机存取。顺序存储结构示意图,45 89 90 67 40 78,0 1 2 3 4 5,顺序表的存储方式,元素地址计算方法：LOC(a i+1)=LOC(a i)+(i-1)*L LOC(a i)=LOC(a1)+(i-1)*L 其中：L：一个元素占用的存储单元个数LOC(ai)：线性表第i个元素的地址特点：实现逻辑上相邻物理地址相邻实现随机存取,顺序存储结构的实现,可以借助于高级程序设计语言中的数组来表示，一维数组的下标与元素在线性表中的序号相对应。,线性表的抽象数据类型定义,ADT List数据元素：D=ai|aiD0,i=1,2,，n，n0，D0为某一数据对象关系：R1|ai,ai-1D，i=2,n基本操作：（1）InitList（&L）操作前提：L为未初始化线性表。操作结果：将L初始化为空表。（2）DestroyList(&L)操作前提：线性表L已存在。操作结果：将L销毁。,线性表的抽象数据类型定义,（3）ClearList(&L)操作前提：线性表L已存在。操作结果：将表L置为空表。（4）EmptyList（L）操作前提：线性表L已存在。操作结果：如果L为空表则返回真，否则返回假。（5）ListLength（L）操作前提：线性表L已存在。操作结果：如果L为空表则返回0，否则返回表中的元素个数。（6）Locate(L,e)操作前提：表L已存在，e为合法元素值。操作结果：如果L中存在元素e，则将“当前指针”指向元素e所在位置并返回真，否则返回假。,线性表的抽象数据类型定义,（7）GetData(L,i)操作前提：表L存在，且i值合法，即1iListLength(L)操作结果：返回线性表L中第i个元素的值。（8）ListInsert(&L,i,e)操作前提：表L已存在，e为合法元素值且1iListLength(L)+1。操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。（9）ListDelete(&L,i,&e)操作前提：表L已存在且非空，1iListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。,2.2 数组基本概念,数组,数组是最通用的数据结构，它出现在几乎所有的编程语言里。在C#语言中使用数组有两种方法：创建 System.Array类型的数组对象，以及创建针对所有数组的抽象的基类型。使用数组的替换方式 ArrayList类。ArrayList是一种像要更多空间来动态生长的数组。对于无法精确知道数组最终大小的情况，或者对于程序生命周期内数组大小可能会发生一点变化的情况，用 ArrayList比用数组更合适。,数组基本概念,数组是可索引的数据的集合。数据既可以是内置的类型，也可以是用户自定义的类型。事实上，把数组数据称为对象大概是最简便的方式。C#语言中的数组实际上就是对象本身，因为它们都来源于 System.Array类。既然数组是 System.Array类的一个声明实例，所以在使用数组时也可以使用此类的所有方法和属性。,数组的声明和初始化,采用下列语法规则对数组进行声明：type array-name;其中这里的类型就是数组元素的数据类型。,一个实例,string names;接下来一行需要实例化数组，还需要确定数组的大小。下面这行就实例化了刚声明的 name数组，并且预留了五个字符串的内存空间：names=new string5;必要时还可以把上述这两条语句合并成为一条语句：string names=new string5;,一个实例,当想要在一条语句中对数组进行声明、例示以及赋值操作时都要花费时间。在 C#语言中可以采用初始化列表的方式来实现：int numbers=new int 1,2,3,4,5;上述这个数的列表被称为是初始化列表。用一对大括号作为界定符，并且每个元素之间用逗号进行分割。当用这种方法来声明数组时，不需要指定元素的个数。编译器会通过初始列表中数据项的数量来推断出此数据。,数组元素的设置和存取访问,存储数组元素既可以采用直接存取访问的方法也可以通过调用 Array类的 SetValue方法。直接存取方式通过赋值语句左侧的索引来引用数组位置：nNames2=Raymond;sSales19=23123;,数组元素的设置和存取访问,SetValue方法则提供了一种更加面向对象的方法来为数组元素赋值。这种方法会取走两个参数：索引数元素的值names.SetValue(Raymond,2);sales.SetValue(23123,19);,数组元素的设置和存取访问,数组元素的访问既可以通过直接存取的方式也可以通过调用 GetValue方法的方式。GetValue方法取走单独一个参数索引。myName=names2;monthSales=sales.GetValue(19);,数组元素的设置和存取访问,为了存取每一个数组元素用 For循环来循环遍历数组是一种通用的方法。程序员在编写循环时常犯的错误即可能是写死循环的上限值（如果数组是动态的，那么这样做就是错误的，因为循环的上限可能会改变），也可能是每次循环重复时调用函数来存取循环的上限：for(int i=0;i=sales.GetUpperBound(0);i+)totalSales=totalSales+salesi;,GetUpperBound可以获取数组的最高下标。GetLowerBound可以获取数组的最低下标。,0表示二维数组的第一维1表示数组的第二维,取回数组元数据的方法和属性,Array类为取回数组元数据提供了几种属性：Length：返回数组所有维数内元素的总数量。GetLength：返回数组指定维数内元素的数量。Rank：返回数组的维数。GetType：返回当前数组实例的类型。,取回数组元数据的方法和属性,Length方法对于计算多维数组中元素的数量以及返回数组中元素的准确编号都是很有用的使用 GetUpperBound方法，要对数值加一GetLength方法统计了数组某一维内元素的数量Rank属性一起可用来在运行时调整数组的大小，而且不必冒丢失数据的风险在无法确定数组类型的情况下，GetType方法可以用来确定数组的数据类型,取回数组元数据的方法和属性,为了确定对象是否是数组，这里创建了一个类型变量 Type，此变量允许用来调用类方法 IsArray。如果对象是一个数组，那么代码返回数组,多维数组,在 C#语言中，尽管数组多于三维的情况是非常少见的，但是数组还是可以达到 32维的。,二维数组的声明,通过提供数组每一维上限值的方式可以声明一个 4行 5列的数组。int,grades=new int 4,5;二维数组经常用来模拟矩阵。声明多维数组也可以不指定维数的上限值。要这样做就要用到逗号来明确数组的维数。double,Sales;,三维数组的声明,在声明不带维数上限的数组的时候，需要稍后对具有这类上限的数组重新确定维数 double,Sales;sales=new double 4,5,6;,用初始化表进行初始化操作,当没有指明数组的上限。初始化带有初始化表的数组的时候，不用说明数组的上限。编译器会根据初始化表中数据计算出每一维的上限值。初始化表本身也像数组的每一行那样用大括号进行标记。数组行内的每一个元素则用逗号进行分割。,传统的数组存取访问方式,存取访问多维数组元素的方法类似于存取一维数组元素的方法可以采用传统的数组存取访问方式 grade=gGrades2,2;gGrades(2,2)=99;,采用 Array类的方法,grade=Grades.GetValue(0,2);对多维数组不能使用 SetValue方法。这是因为这种方法只接收两个参数：一个数值一个单独的索引尽管常常是基于存储在数组行中的数值或者是基于存储在数组列中的数值进行计算，但是对多维数组上所有元素的计算还是很常见的操作。,一个例子,假设有一个 Grades数组，且数组的每一行是一条学生记录，那么就能如下所示计算出每个学生的平均成绩,参数数组,大多数的方法定义要求一套提供给方法的参数的数目，但是想要编写一个允许可选参数数目的方法定义是需要时间的。可以采用一种称为参数数组的构造。,参数数组,可以通过使用关键字 ParamArray在方法定义的参数列表中指明参数数组 例如：定义允许提供任意数量的数作为参数，并且方法会返回数的总量,参数数组,当用参数数组定义方法的时候，为了使编译器能够正确处理参数列表，需要在参数列表的最后提供参数数组的参数。否则，编译器无法知道参数数组元素的截止位置以及方法其他参数的起始位置。,锯齿状数组,在创建一个多维数组的时候，需要始终新建一种每行都有相同元素数量的结构。,锯齿状数组的声明,int sales,=new int12,30;这个数组假设每行都有相同的元素数量但是大家知道某些月有 30天，而某些月是 31天，还有一个月是 29天这个刚刚声明的数组会有几个空元素在其中对于这个数组而言，这不是太大的问题，但是对于更加庞大的数组而言，就需要减少大量浪费的空间。,锯齿状数组的声明,解决这个问题的方法是用锯齿状数组代替二维数组。锯齿状数组是一种每行都能组成一个数组的数组。锯齿状数组的每一维就是一个一维数组。大家称其为“锯齿状”数组的原因是由于数组每一行元素的数量都可能不相同。锯齿状数组的图形不是正方形或矩形，而是具有不均匀边缘或锯齿边缘的图形。,锯齿状数组的声明,锯齿状数组的声明需要通过在数组变量名后放置两组方括号的方式来完成int jagged=new int12;第一组方括号说明了数组的行数第二组方括号则是留白的这为存储在每行内的一维数组标记了位置,锯齿状数组的声明,int jagged=new int12;这是一个有着 12个元素的整数数组，其中的每个元素又是一个整数数组初始化列表实际上就是对数组行的初始化，这表明每一个行元素都是一个有着 12个元素的数组，而且每个元素都初始化为默认的值一旦声明了锯齿状的数组，就可以分别对各自行数组的元素进行赋值操作了,锯齿状数组的赋值,jagged00=11;jagged01=12;jagged75=86;第一组方括号说明了行编号，而第二组方括号则表明了行数组的元素第一条语句存取访问到第一个数组的第一个元素，接着第二条语句存取访问了第一个数组的第二个元素，而第三条语句存取访问的则是第八个数组的第六个元素。,一个例子,创建了一个名为 sales的数组，来跟踪两个月内每星期的销售情况，并且把销售额赋值给数组的元素，然后循环遍历整个数组从而计算出存储在数组内的每月一个星期的平均销售额。,2.3 ArrayList类,ArrayList类,当无法提前知道数组的大小或者在程序运行期间数组的大小可能会发生改变的时候，静态数组就不是很适用了这类问题的一种解决方案就是当数组超出存储空间的时使用能够自动调整自身大小的数组类型这种数组被称为是 ArrayList.NET框架库中 System.Collections命名空间的内容,ArrayList类,ArrayList对象拥有可存储数组大小尺寸的 Capacity属性。该属性的初始值为 16。当 ArrayList中元素的数量达到此界限值时，Capacity属性就会为 ArrayList的存储空间另外增加 16个元素。在数组内元素数量有可能扩大或缩小的情况下使用 ArrayList会比用带标准数组的 ReDim Preserver更加有效。ArrayList用 Object类型来存储对象。,ArrayList类的成员,Add()向 ArrayList添加一个元素。AddRange()在 ArrayList末尾处添加群集的元素。Capacity存储 ArrayList所能包含的元素的数量。Clear()从 ArrayList中移除全部元素。Contains()确定制定的对象是否在 ArrayList内。,ArrayList类的成员,Copy To()把 ArrayList或其中的某一段复制给一个数组。Count返回 ArrayList中当前元素的数量。GetEnumerator()返回迭代 ArrayList的计数器。GetRange()返回 ArrayList的子集作为 ArrayList。IndexOf()返回指定数据项首次出现的索引。,ArrayList类的成员,Insert()在 ArrayList的指定索引处插入一个元素。InsertRange()从 ArrayList指定索引处开始插入群集的元素。Item()在指定索引处获取或者设置一个元素。Remove()移除指定数据项的首次出现。RemoveAt()在指定索引处移除一个元素。,ArrayList类的成员,Reverse()对 ArrayList中元素的顺序进行反转。Sort()对 ArrayList中的元素按照阿拉伯字母表顺序进行排序。ToArray()把 ArrayList的元素复制给一个数组。TrimToSize()为 ArrayList中元素数量设置 ArrayList的容量。,ArrayList类的应用,ArrayList类 ArrayList的使用不同于标准数组。除非事出有因要把数据项添加到特殊位置上，否则通常情况下使用 Add方法向 ArrayList添加数据项，而对于上述特殊情况就要采用 Insert方法来进行操作,ArrayList类的声明,ArrayList grades=new ArrayList();注意：此声明中使用到了构造器。如果 ArrayList没有声明使用构造器，那么在后续程序语句里就无法获得对象。,ArrayList类的添加操作,用 Add方法把对象添加给 ArrayList。此方法会取走一个参数，即添加给 ArrayList 的对象。Add方法也会返回一个整数用来说明 ArrayList中被添加元素的位置，当然这个值是很少会在程序中用到的。,ArrayList类的操作,Foreach循环可以把 ArrayList中的对象显示出来。ArrayList有一个内置计数器用来记录循环遍历 ArrayList内所有对象的次数，而且是每次一个,ArrayList类的Insert方法,如果需要在 ArrayList某个特殊位置上添加元素，则可以采用 Insert方法。此方法会取走两个参数：插入元素的索引插入的元素。,ArrayList类的Capacity属性,通过调用 Capacity属性可以检查 ArrayList当前的容量而通过调用 Count属性可以确定 ArrayList中元素的数量,移除数据项的方法,如果知道要移除的数据项，但又不确定它所处的位置，那么就可以采用 Remove方法。Remove会取走一个参数，即要从 ArrayList中移除的对象。如果 ArrayList内有这个对象，就可以把它移除掉。当使用 Remove方法时，典型做法是把方法放置在 If-Then语句内进行调用，并且使用诸如 Contains这样的方法来验证对象确实存在 ArrayList内。,移除数据项的方法,如果要移除数据项的索引，那么可以使用 RemoveAt方法。RemoveAt方法会取走一个参数，即要移除对象的索引。唯一能接受的人为错误就是给方法传递一个无效的索引。,添加对象的的方法,除了向 ArrayList中添加单独的对象，还可以添加对象的范围。对象必须存储在来源于 ICollection的数据类型里面。可以把对象存储在数组里或存储在 Collection里也存储到另一个 ArrayList里面有两种不同的方法可以用来给 ArrayList添加范围。AddRange方法 InsertRange方法。,添加对象的的方法,AddRange方法会把对象的范围添加到 ArrayList的末尾处 InsertRange方法会把范围添加到 ArrayList内指定的位置上。,GetRange方法,GetRange方法会返回来自 ArrayList的对象的范围作为另外一个 ArrayList。GetRange方法会取走两个参数：起始索引要从 ArrayList找回的元素数量 GetRange方法没有破坏性，因为这只是把对象从原始 ArrayList复制给新的 ArrayList。,ToArray方法,ToArray方法则会把 ArrayList的所有元素复制给一个数组。ToArray方法允许把 ArrayList的内容轻松传递给一个标准数组。采用 ToArray方法的主要原因就是由于用户需要更快的数组存取访问速度。ToArray方法不带参数，但是会把 ArrayList的元素返回给数组。,