首页 移动开发 在线交易 IT笔记 网络技术 操作系统 企业架构 数据库 考试认证 IT培训 开源软件 数据存储 行业资讯
大家都在看:java   开发   C#   oracle   mysql   android   web开发   学习   sqlserver   linux   asp   php   ajax   javascript   css   html
链表和数组队列
2014-11-17 09:54:46 来源: 作者:admin 栏目:MySQL 责任编辑:
[导读] 一、链表与数组 链表和数组是两种常见的基础数据结构。 链表若干个节点组成,每个节点将包含两部门:数据域和指针域;数据域用来存储数据元素,指针域用来存储下一个节点的地址。数组是除链表外另一常见的基础数据结构,它只鸥一个属性即它的大小。它们都是线形..
一、链表与数组
    链表和数组是两种常见的基础数据结构。
    链表若干个节点组成,每个节点将包含两部门:数据域和指针域;数据域用来存储数据元素,指针域用来存储下一个节点的地址。数组是除链表外另一常见的基础数据结构,它只鸥一个属性即它的大小。它们都是线形结构,是实现线形表ADT的两种方式。
    链表和数组在存储数据时具有一个共同的特点,即所存储的数据必须均为同一类型。链表和数组最大的区别为:在物理结构即在内存中,数组是连续储存的,而链表是非连续的。
    这种物理上的特性决定了这两种线形结构在逻辑上的差异。在逻辑上:数组使用时必须预先分配内存,链表在使用时则是按需分配;数组大小一旦确定就不能更改,链表的大小可以自由修改。数组在访问时非常方便迅速,可以看成是基本操作,但若要对一个数组进行插入、删除、增加等操作将会很麻烦,成本将很高;链表在每一次访问时都需要从头节点开始遍历,时间复杂度很高,但是对于链表中每一个节点进行编辑操作就很方便,只需要调整该节点的数据域和指针域即可。因此,在使用这两种数据结构时,应根据实际情况挑选适合的一种。一般对于一旦设定久基本无需更改、访问较多的数据结构采用数组更为理想;对于数据大小不确定或不断变化、编辑操作较多的数据结构采用链表更为理想。
三、链表与数组队列
    1.队列:队列是一种特殊的线形表,特殊之处在于它只能在表的两端进行操作,且只能在队列的队尾进行插入,在队首进行删除。那么问题来了,我们的数组队列竟然可以在任意位置进行操作?所以我们这里应该是用数组模拟一个链表。
    无论是使用链表还是使用数组,队列都需要具有以下功能:
        add()//在队尾添加一个元素
        get(int index)//获取制定位置的元素
        delete(int index)//删除一个制定位置的元素
        insert(int index,要插入元素的类型 要插入的元素)//在制定位置插入一个元素
        length()//获取队列的长度
        ....
    2.队列的实现
        1)基于链表的实现
            在创建链表前,首先必须为它创建一个节点类。节点类包含两个属性:存储的数据、指
            向下一节点的指针。
        2)基于数组的实现
            由于数组大小在设定后是不可变的,所以我们可以定义一个新数组,再将原数组中的数据拷贝到新数组中,这样就模拟出了一个可自由操作的数组。但是需注意,这种方式的时间复杂度很好,当数据量很大时,性能将会很不好。
标签:
本站地址:/
版权所有:转载请注明出处!
分享到:
上一篇一套数据,多种引擎续---两种数据.. 下一篇Mysql“using password: YES”的..
您可能还喜欢
暂无...
今日最新资讯 最新推荐信息
考试认证 更多
开发技术 更多
移动开发 更多

关于 | 合作伙伴 | 联系我们 | 友情链接 | 版权声明 | 网站制作 | 网站地图 | 加入收藏 | 设为首页

Copyright@2012-2016 京ICP备12027873号