注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

天涯倦客的博客

祝福你朋友永远快乐!

 
 
 

日志

 
 

数组与链表  

2011-02-15 15:40:19|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
C++语言中可以用数组处理一组数据类型相同的数据,但不允许动态定义数组的大小,即在使用数组之前必须确定数组的大小。而在实际应用中,用户使用数组之前有时无法准确确定数组的大小,只能将数组定义成足够大小,这样数组中有些空间可能不被使用,从而造成内存空间的浪费。
  
   链表是一种常见的数据组织形式,它采用动态分配内存的形式实现。需要时可以用new分配内存空间,不需要时用delete将已分配的空间释放不会造成内存空间的浪费。(当然存在忘记delete,造成内存溢出的危险)
  
  A 从逻辑结构来看
  
  A-1. 数组必须事先定义固定的长度(元素个数),不能适应数据动态地增减的情况。当数据增加时,可能超出原先定义的元素个数;当数据减少时,造成内存浪费。
  
  A-2. 链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入、删除数据项。(数组中插入、删除数据项时,需要移动其它数据项)
  
  
  B 从内存存储来看
  
  B-1. (静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小
  
  B-2. 链表从堆中分配空间, 自由度大但是申请管理比较麻烦.
  ======================================
  
  数组中的数据在内存中的按顺序存储的,而链表是随机存储的!
  要访问数组中的元素可以按下标索引来访问,速度比较快,如果对他进行插入操作的话,就得移动很多元素,所以对数组进行插入操作效率很低!
  
  由于连表是随机存储的,链表在插入,删除操作上有很高的效率(相对数组),如果要访问链表中的某个元素的话,那就得从链表的头逐个遍历,直到找到所需要的元素为止,所以链表的随机访问的效率就比数组要低
  
  
  数组在内存中开辟连续的一块区域,如果一个数据要两个内存单元,一组5个数据10个单元就够了,无需标记其地址,因为数组定义时候标顶了第一个原许的地址,其他四个都知道了。
  链表可可以是连续的,也可以是不连续的,但一般都是不连续的,尽管在内存中是连续的,我们也不把他当作是连续的,而是把他当作是不连续的,因为如果把他当作是连续的,不如当作是数组了,在某些情况下。一链5个数据,如果每个数据本身用2个内存单元,那么10个单元是不够的,因为每个数据都要表示出下个数据在哪里,所以一个数据本身用2个单元,再用1个单元表示此链下一个数据在什么地址。
  各有用处。
  评论这张
 
阅读(533)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017