c++ - 用O(1)时间循环删除链表?
伊谢尔伦
伊谢尔伦 2017-04-17 11:20:53
[C++讨论组]

在一本数据结构书上看到了这个问题,是个思考题,没有给答案。网上找了找,似乎也没有。有没有大神提供个思路?

伊谢尔伦
伊谢尔伦

小伙看你根骨奇佳,潜力无限,来学PHP伐。

全部回复(1)
阿神

之前用过类似的数据结构,没必要写什么内存分配函数。主要实现思路如下:

  1. 一开始就申请连续的N块内存。每块内存内容为该块内存是否使用的标记和链表节点数据。
  2. 添加节点时在连续的内存中找一块未使用的内存块,标记为使用。
  3. 释放节点时该块内存标记为未使用。
  4. 删除链表时释放掉连续的N块内存即可。
  5. 其他如申请的连续内存用完之类的问题基本有解决方法。

但是这样的做的主要问题是:如果节点是包含资源的,那么资源必然会泄露。

热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号