c语言的双链表与循环链表.doc

c语言的双链表与循环链表发布于：2013-01-09 14:15 浏览量： 171 双链表 有时候以倒序扫描链表很方便。标准实现方法此时无能为力，然而解决方法却很简单。只要在数据结构上附加一个域，使它包含前一个单元的指针即可。其开销是一个附加的链，它增加了空间的需求，同时也使得插入和删除的开销增加一倍，因为有更多的指针需要定位。另一方面，它简化了删除操作，因为你不再被迫使用一个指向前驱元的指针来访问一个关键字；这个信息是现成的。如下图所示： 循环链表 让最后的单元反过来直指第一个单元是一种流行的做法。它可以有表头，也可以没有表头（若有表头，则最后的单元就指向它），并且还可以是双向链表（第一个单元的前驱元指针指向最后的单元）。这无疑会影响某些测试，不过这种在某些应用程序中却很流行，下图显示了一个无表头的双向循环链表。