C# 数据结构 线性表(顺序表 链表 IList 数组)

时间:2023-03-08 15:56:41
C# 数据结构 线性表(顺序表 链表 IList 数组)

线性表

线性表是最简单、最基本、最常用的数据结构。数据元素 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.插入操作:

C# 数据结构 线性表(顺序表 链表 IList 数组)

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),对单链表的操作也不需要移动其他数据元素,但也失去顺序表可随机存储的优点。

C# 数据结构 线性表(顺序表 链表 IList 数组)

C# 数据结构 线性表(顺序表 链表 IList 数组)

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

单链表实现的方法:

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接口。

未完待续…….