数组.md

第一章 数组

• [1.1 线性表]
• [1.2 顺序表]
• [1.3 性能分析]

1.1 线性表

线性表（linear list）：n（n>=0）个数据元素的一个有限序列
L = （a1, a2, a3, ..., an)
L 是表名 ai 是数据元素/结点/表项 ，是不可再分割的原子数据 n 是表长，if(n==0) L为空表

有限序列：

• 表中各个表项是相继排列的
• 每两个相邻节点之间都有直接前驱和直接后继的关系（a1只有后继，an只有前驱）
• 邻接关系是一对一的

概念上每个元素的类型可以不同
线性表分类

1. 根据顺序分类：

• 有序线性表(sorted list)
• 无序线性表(unsorted list)

2. 根据储存表示分类

• 顺序表(sequential list) 顺序存储，数组
• 链表(linked list) 链式存储，指针

1.2 顺序表

定义:
把线性表中所有表项按照其逻辑顺序一次存储到从计算机存储中 指定存储位置开始的一块连续的存储空间中 特点：

1. 占用存储空间=n*sizeof(T)
2. 所有元素逻辑顺序和物理顺序一致
3. 可顺序访问
4. 可随机访问 a[i]

实现方式：

1. 静态数组 T data[100];
2. 动态数组 T* data=new T[size];

成员：

• 数据成员
  • 存放数组
  • 最大容纳量
  • 当前存放量
• 函数成员
  • 改变大小
  • 构造函数
  • 复制构造函数
  • 重载赋值
  • 析构函数
  • 返回最大容纳
  • 返回当前大小
  • 定位
  • 搜索
  • 插入
  • 取值
  • 删除
  • 修改值
  • 清空
  • 判满
  • 判空
  • 重载输入（可选）
  • 重载输出（可选）

设计时注意使用const和&

1.3 性能分析

ACN(average comparing number):平均比较次数
线性表主要时间代价数据移动次数