asunquan.com

不忘初心 不止于行

职场新人 iOS菜鸟 就职于搜狐畅游 从事iOS/tvOS的SDK开发 对于游戏市场有点点了解 平日和一只小Corgi同吃同睡


数据结构学习笔记(二)—线性表

[TOC]

线性表

线性结构的特点是: 在数据元素的非空有限集中, 存在唯一的一个被称作第一个的数据元素, 存在唯一的一个被称作最后一个的数据 元素, 除第一个之外, 集合中的每个数据元素均只有一个前驱, 除最后一个之外, 集合中每个数据元素均只有一个后继.

线性表的类型定义

线性表 是最常用且最简单的一种数据结构, 简言之, 一个线性表是n个数据元素的有限序列.

在稍复杂的线性表中, 一个数据元素可以由若干个数据项组成, 在这种情况下, 常把数据元素称为记录, 含有大量记录的线性表又称文件

线性表是一个相当灵活的数据结构, 它的长度可根据需要增长或缩短, 即对线性表的数据元素不仅可以进行访问, 还可进行插入和删除等

线性表的顺序表示和实现

线性表的顺序表示值得是用一组地址连续的存储单元依次存储线性表的数据元素.

线性表的第一个数据元素的存储位置, 通常称作线性表的起始位置基地址

顺序表 为线性表中相邻的元素赋以相邻的存储位置. 每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数, 由此, 只要确定了存储线性表的起始位置, 线性表中任意数据元素都可随机存取, 所以线性表的顺序存储结构是一种随机存取的存储结构

由于高级程序设计语言中的数组类型也有随机存取的特性, 因此, 通常都用数组来描述数据结构中的顺序存储结构.

当在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时, 其时间主要耗费在移动元素上, 而移动元素的个数取决于插入或删除元素的位置

线性表的链式表示和实现

线性链表

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的, 也可以是不连续的), 因此, 为了表示每个数据元素a(i) 与其直接后继数据元素a(i+1) 之间的逻辑关系, 对数据元素a(i) 来说, 除了存储其本身的信息之外, 还需存储一个指示其直接后继的信息(即直接后继的存储位置), 这两部分信息组成数据元素a(i) 的存储映像, 成为结点(node), 它包括两个域: 其中存储数据元素信息的域称为数据域, 存储直接后继存储位置的域称为指针域, 指针域中存储的信息称作指针, n个结点链接成一个链表, 即为线性表的链式存储结构, 有由于此链表的每个节点中只包含一个指针域, 故又称线性链表单链表

整个链表的存取必须从头指针开始进行, 头指针指示链表中第一个结点(即第一个数据元素的存储映像)的存储位置. 同时, 由于最后一个数据元素没有直接后继, 则线性链表中最后一个结点的指针为空(NULL)

用线性链表表示线性表时, 数据元素之间的逻辑关系是由结点中的指针指示的, 换句话说, 指针为数据元素之间的逻辑关系的映像, 则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻, 由此, 这种存储结构为非顺序映像链式映像

最近的文章

面试经历之TalkingData

面试经历之TalkingData之前收到TalkingData的面试邀约, 今天下午去面试了下, 记录下今天的面试经历.约的是下午两点半, 地点在东直门京投轻轨大厦, 地理位置很好, 从东直门公交枢纽上来就有电梯上楼, 6层出电梯就能看到, 前台的门是感应门, 不过我走到感应门前门没有开让我误以为是推的门了, 很囧…进去之后简单登记了下, 前台MM给了一张表让我去填, 填了一会就填完了, 交给前台MM之后等了几分钟第一个面试官来了.一面, 主要是针对简历问了下功能, 然后针对技术的实现问了...…

数据结构继续阅读
更早的文章

数据结构学习笔记(一)--绪论

[TOC]绪论什么是数据结构一般来说, 用计算机解决一个具体问题时, 大致需要经过下列几个步骤: 首先要从具体问题抽象出一个适当的数学模型, 然后设计一个解此数学模型的算法, 最后编出程序, 进行测试, 调整直至得到最终解答. 需求数学模型的实质是分析问题, 从中提取操作的对象, 并找出这些操作对象之间含有的关系, 然后用数学的语言加以描述.数据结构在计算机科学中是一门综合行的专业基础课, 数据结构的研究不仅涉及到计算机硬件(特别是编码理论, 存储装置和存取方法等)的研究范围, 而且和计算...…

数据结构继续阅读