数据猪构 2.2线性表的顺序表示和实现 2.2.1顺序存储的线性表(Sequential Lists) 把线性表的结点按逻辑顺序依次存放在一组 地址连续的存储单元里。用这种方法存储的线性 表简称顺序表。线性表的起始地址称作线性表的 基地址。 假设线性表的每个元素需占用L个存储单元， 则线性表中第+1个数据元素的存储位置 LOC(a+1)和第i个数据元素的存储位置LOC(a) 之间满足下列关系： LOC(ai+1)=LOC(ai)+L 线性表的第i个数据元素a的存储位置为： LOC(ai)=LOC(a1)+(i-1)*L
数据结构
激据猪构 b 例：有一线性表为： ai a[O] (a1a2.ap.an b+L a2 a(1] 由于C语言中的一维数 ■nr 组也是采用顺序存储表 示，故可以用数组类型 b+(i-1)L ai 来描述顺序表。 ali-l山 ●●● b+(n-1)L an an-l川 b+nL
数据结构
数据结构 线性表的顺序存储的c语言描述： define List_Init Size 100 typedef LISTINCREMENT 10; typedef struct ElemType *elem; int length; int listsize; Sqlist;
数据结构
激据猪构 2.2.2顺序表上实现的基本操作 线性表的初始化操作InitList(&L) Status InitList_Sq(SqList &L){ L.elem=(ElemType *)malloc(LIST_INIT_SIZE *sizeof(ElemType)); If(!L.elem)exit(OVERFLOW); L.length=0; L.Listsize=LIST_INIT_SIZE; return ok; }//InitList_Sq
数据结构
数据结构 线性表的查找操作： LocateElem(L,e,compare()) 算法参见P25。 以下主要讨论线性表的插入和删除两种运算。 1、插入 线性表的插入运算是指在表的第 i(1≤i≤n+1)个位置上，插入一个新结点x,使 长度为n的线性表 （a1,yai-1yaiy,an) 变成长度为n+1的线性表 (a1,.ai-1,x,ai,.,an)
数据结构