线性表的定义 顺序表示和实现.ppt

第1章绪论
第2章线性表
第3章栈和队列
第4章串
第6章树和二叉树
第7章图
第9章查找
第10章排序数据结构课程的起点：线性结构的基本特征:第2章线性表（a1,a2,…ai-1，ai,ai＋1，…,an）
（A,B,C,D,……,Z）“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。抽象数据类型线性表的定义如下：InitList(&L)GetElem(L,i,&e)//读取
LocateElem(L,e,compare())//查找例1：假设:有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。
现要求一个新的集合A＝A∪B。GetElem(Lb,i,e);//取Lb中第i个数据元素赋给e
if(!LocateElem(La,e,equal()))
ListInsert(La,++La_len,e);
//La中不存在和e相同的数据元素，则插入之集合Bvoidunion(List&La,ListLb){

La_len=ListLength(La);
Lb_len=ListLength(Lb);

}//union若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即
ai≥ai-1或ai≤ai-1(i=2,3,…,n)，则称该线性表为有序表(OrderedList)。则1．初始化LC为空表；2.2线性表的顺序表示和实现2.2.1顺序表的表示地址求解公式：若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组V[n]的下标）。a1设有一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是98，则Ｍ[３]的第一个字节的地址是多少？顺序映像的C语言描述sizeof(x)算符的意思是：计算变量x的长度(字节数)在线性表的第i个位置前插入一个元素StatusListInsert_Sq(SqList&L,inti,ElemTypee){
//在顺序表L的第i个元素之前插入新的元素e,
//i的合法范围为1≤i≤L.length+1

}//ListInsert_Sqif(L.length>=L.listsize){
//当前存储空间已满，增加分配
newbase=(ElemType*)realloc(L.elem,
(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase)exit(OVERFLOW);
//存储分配失败
L.elem=newbase;//新基址
L.listsize+=LISTINCREMENT;//增加存储容量
}删除线性表的第i个位置上的元素算法见教材P24StatusListDelete_Sq
(SqList&L,inti,ElemType&e){

}//ListDelete_Sq2.2.3顺序表的运算效率分析插入时的平均移动次数为链式存储结构