线性表(顺序存储)——c#

《线性表(顺序存储)——c#》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性表之c#版本1定义：零个或多个数据元素的有限序列。在这句话中，我们要注意的是有限和序列这两个词语。说白了，就是有前后顺序的、数量有限的一组数据！但要注意，数据的类型要相同。2在线性表中，元素的个数n(n>=0)就是线性表的长度。当n=0时，线性表为空表。3线性表的一些基础操作有以下一些：3.1创建和初始化3.2置空3.3更据位序获取数据元素3.4查找3.5获取线性表长度3.6插入3.7删除4线性表根据其在内存中的不同物理方式，我们可以分为顺序存储和链式存储。他们各有各的好处和缺点，接下来要分析和写一些代码。4.1顺序存储：一段物理

2、地址连续的存储单元依次存储线性表的数据元素，一般用数组来存储。定义顺序存储的三要素是：数组的起始位置（数组的名称）、数组长度、数组当前位置（线性表长度）。4.2在这里要区别数组长度和线性表长度。13数组长度就是这个线性表总共可以存储多少数据。有些书中谈到，可以动态分配一围数组，但会带来性能上的损耗（在后面的代码中有动态扩容）。线性表长度是当前线性表中有多少数据元素。我们要记牢：线性表长度一定小于等于数组长度。4.3顺序存储元素地址计算方法LOC(ai)=LOC(a1)+(i-1)*CC:数组元素长度，比如整型长度是16位，字符型是8位

3、等等……从中我们可以看出，取值的时间复杂度是O[1]。我们把有这个存储特点的存储结构叫做随即存储结构。所有程序详见MyArrayList.cs5通过分析我们可以知道，顺序存储线性表存储数据的时间复杂度为O(1),但是删除和插入一个数据的时间复杂度为O(N)。所以，顺序存储线性表比较适合于那些存多变少的应用缺点n插入和删除需要移动大量元素值n当线性表变化过大时，数组需要扩容或者缩容n相对于链式存储，比较容易出现“碎片”优点n无需为线性表中的前后逻辑关系增加额外的存储空间n可以快速的取出或者设置表中任意位置的元素值有不懂问题可以直接通QQ

4、:384054672联系我，大家一起讨论问题！附上c#实现代码13usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;namespaceMyArrayList{classMyArrayList:IList{privateobject[]data=null;//用来存放数据的数组privateintcurrent;//当前元素的下标privateintcapacity;//数组共有多少容量privateintdefaultLength

5、=10;publicMyArrayList()//无参初始化,数组长度为10{this.data=newobject[defaultLength];this.current=0;this.capacity=defaultLength;13}publicMyArrayList(intinitalSize)//带参初始化{if(initalSize<0){thrownewException("错误:数组初始化大小参数错误:"+initalSize);}this.data=newobject[initalSize];this.current

6、=0;this.capacity=initalSize;}privateboolisListFull()//判断数组是否已满{returnthis.capacity==this.current;}publicboolIsListEmpty()13{returnthis.current==0;}publicvoidClearList(){for(intn=0;n

7、0;n

8、data;longdata=null;}}publicboolAdd(objecte){13if(isListFull()){ensureCapacity();}this.data[this.current]=e;thi