开发学院WEB开发ASP.NET 数据结构C#版线性表(Data Structure)之单链表(Lin... 阅读

数据结构C#版线性表(Data Structure)之单链表(LinkList)

 2010-10-17 14:15:36 来源:WEB开发网   
核心提示:下面是单链表插入和删除的算法图解:可以看到:链表在元素插入/删除时,无需对后面的元素进行移动,数据结构C#版线性表(Data Structure)之单链表(LinkList)(2),只需要自身以及相邻节点的next指向即可,所以插入/删除元素的开销要比顺序表小得多,它有助于某些情况下减少遍历循环的次数,本文中的这种仅有

下面是单链表插入和删除的算法图解:

可以看到:链表在元素插入/删除时,无需对后面的元素进行移动,只需要自身以及相邻节点的next指向即可。所以插入/删除元素的开销要比顺序表小得多,但是也应该注意到,其它操作比如:查找元素,反转倒置链表等,有可能需要遍历整个链表中的所有元素。

测试代码片断:

Console.WriteLine("-------------------------------------");
Console.WriteLine("单链表测试开始...");
LinkList<string> link = new LinkList<string>();
link.Head = new Node<string>("x");
link.InsertBefore("w", 0);
link.InsertBefore("v", 0);
link.Append("y");
link.InsertBefore("z", link.Count());
Console.WriteLine(link.Count());//5
Console.WriteLine(link.ToString());//v,w,x,y,z
Console.WriteLine(link[1]);//w
Console.WriteLine(link[0]);//v
Console.WriteLine(link[4]);//z
Console.WriteLine(link.IndexOf("z"));//4
Console.WriteLine(link.RemoveAt(2));//x
Console.WriteLine(link.ToString());//v,w,y,z
link.InsertBefore("x", 2);
Console.WriteLine(link.ToString());//v,w,x,y,z
Console.WriteLine(link.GetItemAt(2));//x
link.Reverse();
Console.WriteLine(link.ToString());//z,y,x,w,v
link.InsertAfter("1", 0);
link.InsertAfter("2", 1);
link.InsertAfter("6", 5);
link.InsertAfter("8", 7);
link.InsertAfter("A", 10);//Position is error!

Console.WriteLine(link.ToString()); //z,1,2,y,x,w,6,v,8

至于具体在实际应用中应该选用顺序表 or 链表,主要是看:对于元素插入/删除的频繁程度以及对于内存分配的苛刻程序。 如果不要求一开始就分配一组连续的内存区域,可是根据元素的增加而自动加大内存的使用量,同时插入/删除的次数很多,那么建议使用链表,反之用顺序表。

最后指出:可以给节点再添加一个prev元素,用于指出前一个节点是谁,即同时有next和prev二个指向,这种改进后的链表称为“双向链表”,它有助于某些情况下减少遍历循环的次数,本文中的这种仅有一个next指向的链表,称为“单链表”。

编辑推荐:数据结构C#版线性表(Data Structure)之顺序表(顺序表(SeqList)的实现)

http://tech.cncms.com/web/aspnet/111434.html

上一页  1 2 

Tags:数据结构 线性表 单链表

编辑录入:爽爽 [复制链接] [打 印]
[]
  • 好
  • 好的评价 如果觉得好,就请您
      0%(0)
  • 差
  • 差的评价 如果觉得差,就请您
      0%(0)
赞助商链接