C# 数据结构线性表（顺序表链表 IList 数组）

旧城等待， 2021-12-13 00:43 332阅读 0赞

**线性表**

线性表是最简单、最基本、最常用的数据结构。数据元素 1 对 1的关系，这种关系是位置关系。

**特点**

（1）第一个元素和最后一个元素前后是没有数据元素，线性表中剩下的元素是近邻的，前后都有元素。

（2）线性表中的元素是有限的（List），线性表中的数据类型一致。

（3）线性表表示方法 L=\{a1,a2,a3,a4…….an\},L=(D,R)

（4）每一个元素都有前驱和后继，第一个元素只有后继，最后一个元素只有前驱。

**实例**

例如：1～100的整数是一个线性表

\{“zhangsan”, “lisi”, “wangwu”\}

……

**A.顺序表**

所有的操作都是根据建立在线性结构的基础之上进行的,线性表接口表示如下：

public interface IListDS<T>

> int GetLength(); //求长度
> 
> void Clear();//清空线性表
> 
> bool IsEmpty();//判断是否为空
> 
> void Append(T item);//追加元素
> 
> void Insert(T item,int i);//插入元素
> 
> T Delete(int i);//删除元素
> 
> T GetElem(int i);//获取元素
> 
> int Locate(T value);//查找元素
> 
> void Reverse();//倒置

**操作**

**1.**插入操作：

[![image][]][image 1]

30在插入之前数据表没有什么变化，当30数据出入到第i个位置后，后面的数据需要向后移动，那么插入的

数据越靠前，所需要移动的次数越多，如果i=0 那么需要向后移动 n 个位置，如果插入到最后一个，那么

顺序表就不需要移动，如果插入的数据的位置i的概率为Pi，那么需要移动的位置次数为n/2,在顺序表中移动

其中一半的数据，那么插入操作的时间复杂度为0(n)。

**2.**删除操作：顺序表删除操作和插入操作一致，时间都是浪费在移动数据上，时间复杂度也为0（n）

**3.**读取操作：直接读取到顺序表中的数值 比如 IListDS\[i\]元素,那么时间复杂度为 0(1) 只需要取一次即可。

**4.**查找操作：查找需要找到数据位置i，然后判断数值是否一致，这个类似于插入和删除，时间复杂度：0（n）

**5**.倒置操作：倒置操作只需要把前后对比 把第i个元素和第n-i个元素交换即可，时间复杂度也为:0(n)

**B.单链表**

对比顺序表，逻辑相同的数据在物理地址上也相同，在顺序表上查找一个位置上的数据非常方便，这是顺序表的

优势所在，那么问题来了，在顺序表插入或者删除一个数据时候往往需要移动剩下的数据，那么这样会影响效率

，接下来学习一下线性表的另外一个存储结构----链式存储（Linked Strorage）,这样的线性表叫做（Linked

List），对单链表的操作也不需要移动其他数据元素，但也失去顺序表可随机存储的优点。

**[![捕获][051705404888206.png]][051705404888206.png 1]**

[![image][image 2]][image_image 2]

从两张图我们可以看到单链表的结构和顺序表的一个差异

单链表实现的方法：

pulic class LinkedList<T>:IListDS<T>

> Pulic Node<T> Head;//属性
> 
> pulic LinkedList();//构造器
> 
> pulic GetLength();//获取长度
> 
> pulic Clear();//清空
> 
> pulic bool IsEmpty();//判断是否为空
> 
> pulic void Append(T item);//追加
> 
> pulic void Insert(T item,int i);//i位置插入
> 
> pulic void Delete(T item);//删除元素
> 
> pulic T GetElem(int i);//获取单链表第i个元素
> 
> pulic int i Location(T item);//查找位置
> 
> pulic void Reserver();//倒置

**操作**

**1.**获取长度

单链表和顺序表的长度过去方法不一致，因为单链表是连续的顺序空间，而单链表

从头引用头开始，一个节点一个节点的便利，直到表的末尾。那么问题来了：刚刚介绍单链表物理空间不也是

连续的吗？这个笔者个人理解，初始化数据是物理连续，而新插入的数据不会按照物理地址排列，所以所单链

表还是要便利整个内容来计算长度,时间复杂度为 0(n)。

**2.**清空操作

清空操作是指将单链表所有的节点使得单链表为空，此时头引用head为null.清空单链表的算法实现如下：

pulic void Clear()

> head=null;

需要注意的是，单链表清空后，原来节点所占用的空间不会一直保留，而由垃圾回收器进行回收和顺序表不一样

的是，顺序表是连续的空间，数组分配的空间仍然保留。

**3.**附加操作

附加操作，是要便利单链表中所有的元素，然后在链表的尾部添加元素，时间复杂度为：0(n);

线性表的顺序存储和链式存储各有优缺点，线性表如何存储取决于使 用的场合。如果不需要经常在线性表中进行

插入和删除，只是进行查找，那么， 线性表应该顺序存储；如果线性表需要经常插入和删除，而不经常进行查找

，则 线性表应该链式存储。

**C 结合单向链表，肯定也有有双向链表，双向链表也是有上面的基本操作，然后思考相关的问题：时间复杂度问题。**

**D 循环列表：循环链表是在单链表和双向链表的基础上头尾相连Last.Next=>Header.Head**

**C\#中的线性表**

说道C\# 线性表那就是List，在1.1中提供了非泛型接口 IList,接口中的项是object，非泛型IList是从ICollection

接口继承而来,是所有线性表的接口，用了这么长时间的List才发现IList是线性结构，IList分为三类：只读的，大

小不可变，大小可变的。

**只读的IList：**不能被修改，插入或者删除。

**大小不变的IList：**不能在表中插入或删除，但是可以修改表中的项。

**大小可变的ILIST:** 可以操作，可以插入或者删除

**非泛型的IList接口声明如下：**

interface IList:ICollenciton,IEnumberable

> //共有属性
> 
> bool IsFiexedSize\{get;\} //只读，如果IList有固定大小
> 
> bool IsReadOnly\{get;\} //只读 ，如果ILIST是只读的
> 
> object this\[T index\] \{get;set;\} //索引器 得到某个类型
> 
> int add(object value);
> 
> void clear();
> 
> int indexof(object value);
> 
> bool contains(ojbject value);
> 
> void insert(index,object value);
> 
> void remove();
> 
> void removeat();

**.NET 框架中一些集合实现了IList接口，如ArrayList，ListDictionary,StringCollection,String Dictionary.**

**.NET 线性表中顺序存储采用的是数组，而链式的存储方式则是：IList接口。**

**未完待续…….**

转载于:https://www.cnblogs.com/slf007/p/4555101.html

[image]: /images/20211210/c88ce83eb5624e93a0089746c1110e97.png
[image 1]: http://images0.cnblogs.com/blog/428636/201506/051705369736832.png
[051705404888206.png]: https://images0.cnblogs.com/blog/428636/201506/051705404888206.png
[051705404888206.png 1]: /images/20211210/fbf2866e55b748cda3c286c4260b2488.png
[image 2]: https://images0.cnblogs.com/blog/428636/201506/051705430988137.png
[image_image 2]: /images/20211210/2ff22c69d76545c7ac84cce4f1225fc7.png