数据结构2-2.pptVIP

线性表的顺序表示与实现 线性表的顺序表示是指：用一组地址连续的存储单元依次存储线性表的数据元素 线性表中第I+1个数据元素的存储位置LOC( ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系： LOC(ai+1)=LOC(ai)+L 线性表的第i个数据元素ai的存储位置为： LOC(ai)=LOC(a1)+(I-1)*L 以元素“物理位置相邻”表示元素之间逻辑关系 线性表中任一元素可随机存取 线性表的顺序表示与实现 线性表的动态分配顺序存储结构 # define LIST_INIT_SIZE 100 # define LISTINCREMENT 10 typedef struct{ ElemType *elem;//存储空间首地址 int length;//当前线性表长度 int listsize;//当前分配的存储容量(sizeof(ElemType)) } SqList; 算法2.3：线性表的初始化 Status InitList_Sq(SqList L){ //构造一个空的线性表L L. elem=(ElemType *)malloc(LIST_INIT_SIZE* sizeof(ElemType)); if(! elem) exit(OVERFLOW); //存储分配失败 L. length=0; //空表长度为0 L. listsize=LIST_INIT_SIZE; //初始存储容量 return ok; }// InitList_Sq; 算法2.4：线性表插入操作 算法2.5：线性表插入操作 线性表的顺序表示与实现 基本操作重复的平均次数： 插入操作：Ei=n/2 删除操作：Ed=(n-1)/2 时间复杂度：O(n) 了解：顺序表的合并，参见算法2.7 线性表中查找某一元素 * 数据结构 第二章 线性表 数据结构 第二章 线性表 e1 e2 e3 e4 en … … 图示：线性表顺序存储结构 en ┊ ei ┊ e2 e1 max-1 ┊ n-1 ┊ i-1 ┊ 1 0 ListLength ListSize Elem L 存储特点： 逻辑上相邻， 物理上亦相邻 数据结构 第二章 线性表 图示：线性表的初始化 InitSize-1 ┊ 2 1 0 L ListSize ListLength Elem =0 =InitSize 数据结构 第二章 线性表 图示：线性表的插入：ListInsert_Sq(L,i,e) 3 a4 4 ┊ 2 1 0 a3 a2 a1 ListLength = 4 3 a3 4 a4 ┊ 2 1 0 e a2 a1 设 i=3 ListLength = 5 数据结构 第二章 线性表 图示：线性表的删除：ListDelete_Sq(L,i,e) 3 a4 4 a5 ┊ 2 1 0 a3 a2 a1 ListLength = 5 3 a5 4 ┊ 2 1 0 a4 a2 a1 设 i=3 ListLength = 4