智胜彩票潮流网,最新潮鞋资讯分享!

微信号:weixin888

【数据结构与算法】静态链表

时间:2020-05-22 13:03人气:编辑:admin

  对于线性链表,也可用一维数组来进行描述。这种描述方法便于在没有指针类型的高级程序设计语言中使用链表结构。用数组描述的链表,即称为静态链表。

  静态链表中主要解决的是:如何用静态模拟动态链表结构的存储空间分配,也就是需要的时候申请,不需要的时候释放.

  在动态链表中,结点申请和释放分别借用C语言的malloc()和free()两个函数来实现

  在静态链表中,操作的是数组,不存在像动态链表的结点申请和释放的问题,所以需要自己实现这两个函数,才可以做到插入和删除的操作

  为了辨明数组中哪些分量未被使用,解决的方法是将所有未被使用过的及已被删除的分量用游标链成一个备用的链表

  每当进行插入时,便可以从备用链表上取得第一个结点作为待插入的新结点,这里假设在A后边插入B

  优点:在插入和删除操作时,只需要修改游标,不需要移动元素,从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点

  总的来说,静态链表其实是为了给没有指针的编程语言设计的一种实现单链表共的方法,一般情况我们可以用单链表就不用静态链表了

  普通方法:首先遍历一遍单链表以确定单链表的长度L.然后再次从头结点出发循环L/2次找到单链表的中间节点 ; 算法复杂度为:O(L+L/2) = O(3L/2)

  利用快慢指针原理实现: 设置两个指针searchmid 都是指向单链表的头结点 其中search的移动速度是mid 的2倍. 当*search指向末尾结点时候mid正好就在中间了.这也是标尺的思想

标签: 静态链表  
相关资讯
热门频道

热门标签