还剩1页未读,继续阅读
文本内容:
单链表,双链表和循环链表链表是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每个节点里存到下一个节点的指针由于不须按顺序存储,链表在插入的时候可以达到的复杂度,比顺序表快得多,但是查找一个01Ologn节点或者访问特定编号的节点则需要的时间,而顺序表的时间复杂度是0n01链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大链表由一连串节点组成,每个节点包含任意的实例数据和一或两data fields个用来指向明上一个/或下一个节点的位置的链接链表是一种自我指示links o数据类型,因为它包含指向另一个相同类型的数据的指针链表允许插入和移除表上任意位置上的节点,但是不允许随机存取链表有很多种不同的类型单向链表,双向链表以及循环链表链表可以在多种编程语言中实现单向链表或者单链表单向链表,它包含两个域,一个信息域和一个指针域这个链接指向表中的下一个节点,而最后一个节点则指向一个空值NULL单向链表只可向一个方向遍历查找一个节点的时候需要从第一个节点开始每次访问下一个节点,一直访问到需要的位置也可以提前把一个节点的位置另外保存起来,然后直接访问双向链表,也叫双链表双向链表中不仅有指向后一个节点的指针,还有指向前一个节点的指针第一个节点的前连接指向最后一个节点的后连接指向NULL,NULLo这样可以从任何一个节点访问前一个节点,也可以访问后一个节点,以至整个链表一般是在需要大批量的另外储存数据在链表中的位置的时候用由于另外储存了指向链表内容的指针,并且可能会修改相邻的节点,有的时候第一个节点可能会被删除或者在之前添加一个新的节点这时候就要修改指向首个节点的指针有一种方便的可以消除这种特殊情况的方法是在最后一个节点之后、第一个节点之前储存一个永远不会被删除或者移动的虚拟节点,形成一个循环链表这个虚拟节点之后的节点就是真正的第一个节点这种情况通常可以用这个虚拟节点直接表示这个链表循环链表在一个循环链表中,首节点和末节点被连接在一起这种方式在单向和双向链表中皆可实现要转换一个循环链表,你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点循环链表可以被视为“无头无尾二循环链表中第一个节点之前就是最后一个节点,反之亦然循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易对于新加入的节点应该是在第一个节点之前还是最后一个节点之后可以根据实际要求灵活处理,区别不大另外有一种模拟的循环链表,就是在访问到最后一个节点之后的时候,手工跳转到第一个节点访问到第一个节点之前的时候也一样这样也可以实现循环链表的功能,在直接用循环链表比较麻烦或者可能会出现问题的时候可以用其它链表中的节点不需要以特定的方式存储,但是集中存储也是可以的,主要分下面这几种具体的存储方法共用存储空间链表的节点和其它的数据共用存储空间,优点是可以存储无限多的内容(不过要处理器支持这个大小,并且存储空间足够的情况下),不需;要提前分配内存,存储一个申请一个,如语言的缺点是由于内容分C MALLOC散,有时候可能不方便调试独立存储空间一个链表或者多个链表使用独立的存储空间,一般用数组或者类似结构实现,优点是可以自动获得一个附加数据唯一的编号/索引,并且方便调试;缺点是不能动态的分配内存当然,另外的在上面加一层块状链表用来分配内存也是可以的,这样就解决了这个问题这种方法叫做数组模拟链表,但是事实上只是用表示在数组中的位置的下标索引代替了指向内存地址的指针,这种下标索引其实也是逻辑上的指针,整个结构还是链表,并不算是被模拟的但是可以说成是用数组实现的链表链表用来构建许多其它数据结构,如堆栈,行列和他们的衍生节点的数据域也可以成为另一个链表通过这种手段,我们可以用列表来构建许多链性数据结构;这个实例产生于编程语言,在中链表是初级数据Lisp Lisp结构,并且现在成为了常见的基础编程模式有时候,链表用来生成联合数组,在这种情况下我们称之为联合数列这种情况下用链表会优于其它数据结构,如自平对分查找树甚至是一些小的数据集合不sekbalancing binarysearch trees管怎样,一些时候一个链表在这样一个树中建立一个节点子集,并且以此来更有效率地转换这个集合终于写完了,累死我了。