数组:线性表的特殊形式与存储结构
需积分: 9 135 浏览量
更新于2024-07-22
收藏 737KB PPT 举报
"数据结构——数组"
在计算机科学中,数组是一种基础且重要的数据结构,它被视为一种特殊的线性表,因为在这个线性表中,每个数据元素本身也是一个线性表。数组通常由一个固定的大小的元素集合组成,这些元素具有相同的数据类型,并通过索引来访问。
### 定义与特点
1. **定义**: 数组是由相同类型的数据元素构成的集合,这些元素在内存中是连续存储的,并通过一个唯一的整数索引(下标)来标识和访问。数组的大小(元素个数)是固定的,在声明时就需要确定,通常用m x n表示一个m行n列的二维数组。
2. **特点**:
- **数组结构固定**: 一旦创建,数组的大小就不可变,这意味着不能动态添加或删除元素。
- **数据元素同构**: 所有元素都属于同一个数据类型,例如都是整数、字符或者浮点数等。
### 数组运算
数组的基本操作包括:
- **存取**: 给定一个索引,可以直接访问或修改对应位置的数据元素,时间复杂度为O(1)。
- **遍历**: 可以按顺序或反序遍历数组的所有元素,实现各种算法和操作。
### 顺序存储结构
数组在内存中的存储通常采用顺序存储方式,有两种常见的主序约定:
1. **行序为主序**: 按照从左到右、从上到下的顺序存储,例如2D数组的第一维先变化,然后是第二维。
2. **列序为主序**: 与行序相反,先按列变化,再按行变化。
数组元素的位置可以通过公式计算得到:
- 对于行序为主序的二维数组,`Loc(aij) = Loc(a11) + [(i-1)*n + (j-1)]*l`,其中`Loc()`表示元素的内存位置,`l`是每个元素的字节长度。
- 对于列序为主序,公式变为`Loc(aij) = Loc(a11) + [(j-1)*m + (i-1)]*l`。
### 压缩存储
在处理特定类型的矩阵时,为了节省空间,可以使用压缩存储:
1. **对称矩阵**: 只存储对角线以下或以上的非零元素,因为对称矩阵的下三角等于上三角。
2. **三角矩阵**: 包括下三角矩阵(只存储下三角的元素)和上三角矩阵(只存储上三角的元素)。
3. **对角矩阵**: 只存储对角线上的元素,其他位置的元素默认为0。
对于压缩存储的矩阵,元素的位置也需要根据不同的存储方式调整计算公式。
数组作为基本的数据结构,广泛应用于编程和算法设计中,如排序算法、搜索算法、图论、线性代数等多个领域。理解并掌握数组的特点、存储方式和操作方法是学习高级数据结构和算法的基础。
2009-10-27 上传
2021-10-08 上传
2021-10-08 上传
2021-10-05 上传
y13699450388
- 粉丝: 0
- 资源: 4
最新资源
- ES管理利器:ES Head工具详解
- Layui前端UI框架压缩包:轻量级的Web界面构建利器
- WPF 字体布局问题解决方法与应用案例
- 响应式网页布局教程:CSS实现全平台适配
- Windows平台Elasticsearch 8.10.2版发布
- ICEY开源小程序:定时显示极限值提醒
- MATLAB条形图绘制指南:从入门到进阶技巧全解析
- WPF实现任务管理器进程分组逻辑教程解析
- C#编程实现显卡硬件信息的获取方法
- 前端世界核心-HTML+CSS+JS团队服务网页模板开发
- 精选SQL面试题大汇总
- Nacos Server 1.2.1在Linux系统的安装包介绍
- 易语言MySQL支持库3.0#0版全新升级与使用指南
- 快乐足球响应式网页模板:前端开发全技能秘籍
- OpenEuler4.19内核发布:国产操作系统的里程碑
- Boyue Zheng的LeetCode Python解答集