文档章节

第17章 高级数据表示 17.6链表和数组

idreamo
 idreamo
发布于 2017/08/24 06:58
字数 1605
阅读 52
收藏 1

很多编程问题,比如创建一个列表或队列,可以用链表(一个动态分配的结构序列链)或数组来表示。每种形式都有其优势和缺点,所以要根据具体问题的需求来决定选择哪种形式。表17.3总结了链表和数组的性质。

比较数组和链表
数据形式 优点 缺点
数组 C对其提供直接支持  提供随机访问 编译时决定其大小  插入和删除元素很费时
链表 运行时决定其大小  快速插入和删除元素 不能随机访问  用户必须提供编程支持

 我们仔细研究插入和删除元素的过程。向数组中插入元素,必须移动其他元素以便安插新元素。新元素离数组头越近,要移动的元素越多。而向链表插入一个节点,只需要分配两个指针值。类似的,从数组删除一个元素要重新安置大量元素,而从链表删除一个节点只需要重新设置一个指针并释放被删除节点使用的内存

其次,考虑如何访问列表中的成员。对数组来说,可以用数组索引直接访问任意元素。这被称为随机访问(random access)对链表来说,必须从列表头开始,逐个节点地移动到所需的节点处,这叫顺序访问(sepuential access)。数组也可以顺序访问。只要在数组中按顺序使数组索引递增即可。在某些情况下顺序访问就够了。比如要显示列表中的每一个项目,顺序访问就很不错。另外一些情况下随机访问更受欢迎,下面您会看到。

假设要在列表中搜索一个项目。一种算法是从列表头开始顺序搜索列表,这被称为顺序搜索(sequential search)。如果项目并非以某种顺序排列,您只能使用顺序搜索。如果要搜索的项目不在列表中,您得查找完所有的项目才能得出该项目不在列表中的结论。

可以先对列表排序来改进顺序搜索。这样的话,当碰到一个排在待找项目后的项目时还未找到您要搜索的项目,就可以终止搜索了。假设您在一个按字母顺序排列的列表中查找Susan。从列表头开始查找每一个项目,最后碰到了Sylvia,而此时还没有找到Susan。这时就可以退出搜索了,因为如果Susan在列表里的话,它将在Sylvia之前。平均来讲,这种方法将会使查找不在列表中的项目的时间减半

对于一个排序的列表,使用折半搜索(binary search)会比顺序搜索好的多。下面是其工作方法。首先,称您要搜索的列表项目为目标项(goal),并假设列表是按字母排序的然后,把列表的中间项和目标项进行比较如果两者相等,搜索结束。如果该中间项的字母比目标项靠前,则目标项若在列表中,一定在后一半。如果中间项的字母比目标项靠后,则目标项一定在前一半任一种情况下,比较结果决定了下次搜索将在半个列表中进行。而后,再次应用这种方法。即,选择剩下一半列表的中间项,同样,该方法或者找到目标项或者规定剩下列表的一半作为下次搜索的范围。照这样下去,直到找到目标项或排除整个列表。这种方法非常有效率。假如列表有127个项目那么长,顺序搜索平均要做64次才能找到目标项或得知其不存在。而折半搜索只需最多做7次比较。第一次比较排除到剩下63种可能,第二次比较排除到还剩下31种可能,如此下去,直到第6次比较后只剩下一种可能。第7次比较决定剩下的这个是否是目标项。一般地,n次比较能处理具有2的n次方减1个成员的数组,所以列表越长,越能体现出折半搜索的优势

用数组实现折半搜索是很简单的,因为可以用数组索引决定任何数组或部分数组的中点。只要把数组的第一个和最后一个元素的索引相加再除以2即可。例如,在一个具有100个元素的列表中,第一个索引为0,最后一个索引为99,则首次猜测应为(0+99)/2,即49(整数除法)。如果索引为49的元素与目标项相比在字母表中太靠后,则正确的选择应在0-48范围内,所以下一次猜测应为(0+48)/2,即24。如果索引为24的元素与目标项相比又太靠前了,则下一次猜测应为(25+48)/2,即36。这就是数组的随机访问特性的体现。它使您能从一个位置直接跳到另一个而不需访问两者之间的每一个位置。而链表只支持顺序访问,不能提供直接跳到列表中间点的手段,所以在链表中不能使用折半搜索。

这样的话可以看到,选择何种数据类型是取决于具体问题的。如果列表需要频繁地插入和删除元素因而不断地调整大小,并且不需要经常搜索,链表是更好的选择。而如果列表基本稳定只是偶尔插入或删除一些元素,但却需要经常搜索,则数组是更好的选择。

可是如果您需要的是一种即支持频繁搜索又支持频繁地插入和删除元素的数据类型,链表和数组都不是针对这个目标的理想选择。另一种形式,二叉搜索树,可能正是您所需要的。

 

© 著作权归作者所有

idreamo
粉丝 18
博文 139
码字总数 224743
作品 0
青岛
产品经理
私信 提问
《java数据结构和算法》读书笔记

《Java多线程编程核心技术》读书笔记 常用数据结构 第2章 数组 最简单的数据结构,在查找上比链表有优势,但是在插入与删除上比不上链表。 Java中的数组有长度限制,为int值。在内存模型中,...

刀狂剑痴
2016/05/27
229
0
python算法-1.简介/2.选择排序

第一章、 算法简介 一些常见的大O运行时间 》 ,也叫对数时间,这样的算法包括二分查找。 》 ,也叫线性时间,这样的算法包括简单查找。 》 ,这样的算法包括第4章将介绍的快速排序——一种速...

时间之友
2017/12/15
0
0
新书推荐 |《PostgreSQL实战》出版

很高兴《PostgreSQL实战》一书终于出版,本书大体上系统总结了笔者 PostgreSQL DBA 职业生涯的经验总结,本书的另一位作者张文升拥有丰富的PostgreSQL运维经验,目前就职于探探科技任首席Pos...

francs.tan
2018/08/12
0
0
关东升的《从零开始学Swift》第2版已经出版

关东升的《从零开始学Swift》第2版已经出版 大家好: 苹果2015WWDC大会发布了Swift2.0,它较之前的版本Swift1.x有很大的变化,所以我即将出版《从零开始学Swift》 《从零开始学Swift》将在《...

tony关东升
2016/02/24
0
0
关东升的《从零开始学Swift》3月9日已经上架

大家一直期盼的《从零开始学Swift》于3月9日已经上架,它是关东升老师历时8个月的呕心沥血所编著,全书600多页,此本书基于Swift 2.x,通过大量案例全面介绍苹果平台的应用开发。全书共分5 部...

智捷课堂
2016/03/11
43
0

没有更多内容

加载失败,请刷新页面

加载更多

mysql概览

学习知识,首先要有一个总体的认识。以下为mysql概览 1-架构图 2-Detail csdn |简书 | 头条 | SegmentFault 思否 | 掘金 | 开源中国 |

程序员深夜写bug
今天
8
0
golang微服务框架go-micro 入门笔记2.2 micro工具之微应用利器micro web

micro web micro 功能非常强大,本文将详细阐述micro web 命令行的功能 阅读本文前你可能需要进行如下知识储备 golang分布式微服务框架go-micro 入门笔记1:搭建go-micro环境, golang微服务框架...

非正式解决方案
今天
6
0
前端——使用base64编码在页面嵌入图片

因为页面中插入一个图片都要写明图片的路径——相对路径或者绝对路径。而除了具体的网站图片的图片地址,如果是在自己电脑文件夹里的图片,当我们的HTML文件在别人电脑上打开的时候图片则由于...

被毒打的程序猿
今天
8
0
Flutter 系列之Dart语言概述

Dart语言与其他语言究竟有什么不同呢?在已有的编程语言经验的基础上,我们该如何快速上手呢?本篇文章从编程语言中最重要的组成部分,也就是基础语法与类型变量出发,一起来学习Dart吧 一、...

過愙
今天
5
0
rime设置为默认简体

转载 https://github.com/ModerRAS/ModerRAS.github.io/blob/master/_posts/2018-11-07-rime%E8%AE%BE%E7%BD%AE%E4%B8%BA%E9%BB%98%E8%AE%A4%E7%AE%80%E4%BD%93.md 写在开始 我的Arch Linux上......

zhenruyan
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部