《算法与数据结构》.pdf

文档介绍：: .
《《算法与数据结构算法与数据结构》》
,i);
k = Locate(A,x);
if (k>0)
DelElem(A, k);
}
}
第6页§§ 线性表的存储结构线性表的存储结构
线性表的存储结构分两种：
™ 顺序存储结构
™ 链式存储结构
顺序存储结构（顺序表）
™ 定义：是按照顺序存储方式构造的线性表
™ 基本思想：
¾ 顺序表中的一个存储单元存储一个数据元素
¾ 以元素之间的排列顺序来表示元素之间的逻辑关系
(a,b,c,d,e,f)
a 特点：逻辑结构中相邻的结点在存储结构中仍然相
b 邻，也就是说以元素在计算机内“物理位置”的相邻
c 来表示线性表中数据元素之间的逻辑关系。
d
e
第7页 f§§ 线性表的存储结构线性表的存储结构
™ 由于在高级程序设计语言中数组（如：int A[10]）具有
连续的存储空间，且可以进行随机存取，符合顺序存储
的特征，因此程序设计时常用数组来描述数据结构中的
顺序存储结构。
™ C/C++语言中，顺序表描述如下：
const int MAXSIZE=顺序表的容量
typedef struct
{
ElemType data[MAXSIZE]; //存放顺序表中的数
据元素 data len
int len; //顺序表的长度 a 6
}SqList; (a,b,c,d,e,f) b
c
d
e
SqList
第8页 f§§ 线性表的存储结构线性表的存储结构
™ 顺序表中元素的地址计算
¾ 假定
1）存储一个ElemType类型的变量占用l(l≥1)个内存
单元；
2）存储线性表的数组的入口地址为b(数组的首地
址)。
¾ 结论
线性表中第i个元素的存储地址= b + (i - 1)×l
基本运算在顺序表中的实现
™ 300 a
（1）初始化线性表 301 b
void InitList(SqList &sq) 302 c
303 d
{ //初始化线性表 304 e
305 f
= 0; //将sq的len域置0
第9页
}§§ 线性表的存储结构线性表的存储结构
值传递 地址传递 引用调用（C++）
实参将数据传递给形 实参将地址值传递给形 原理同地址传递基本相
参，实参和形参拥有各 参（是一个指针），实 同，只是在概念上有区
自独立的存储空间，除