|
|
线性表的顺序存储结构采用一组连续的存储单元依次存储线性表中的各数据元素。建立一个数组V,线性表的长度为N,V[i]表示第i个分量,第i个分量是线性表中第i个元素ai在计算机存储器中的映像,即V[i]=ai。若线性表的第一个元素的存储地址是LOC(a1),每个元素用L个存储单元,则表的第i个元素的存储地址为:LOC(ai)=LOC(a1)+(i-1)*L。
|
|
|
假设线性表的数据元素的类型为ElemType(在实际应用中,此类型应根据实际问题中出现的数据元素的特性具体定义,如为int、float类型等),则线性表的顺序表的C语言描述如下:
|
|
|
|
从中可以看出,顺序表是由数组data和len两部分组成的。为了反映data和len之间的关系,上述类型定义中将它们说明为结构体类型Sqlist的两个域。这样,Sqlist类型就完全描述了顺序表的组织。
|
|
|
|
由于C语言中数组的下标是从0开始的,所以,在逻辑上所指的"第k个位置"实际上对应的是顺序表的"第k-1个位置"。这里仅给出在顺序表上线性表的插入和删除函数。
|
|
|
|
|
|
|
|
|
|
其中,pi是在第i个元素前插入元素的概率,ci是在第i个元素前插入元素时元素移动的次数。
|
|
|
|
|
其中,pi是在第i个元素前删除元素的概率,ci是在第i个元素前删除元素时元素移动的次数。
|
|
|
|