§2.2线性表的顺序表示和实现 ★顺序表： 定义：用一组地址连续的存储单元存放一个线性表 必元素地址计算方法： LOC(ai)=LOC(a)+(i-1)*L LOC(ai+1)=LOC(a)+L ●其中： ◆L一一个元素占用的存储单元个数 ◆LOC(a)一线性表第i个元素的地址 特点： ●实现逻辑上相邻物理地址相邻 ●实现随机存取 实现：可用C语言的一维数组实现
§2.2 线性表的顺序表示和实现 顺序表： ❖定义：用一组地址连续的存储单元存放一个线性表 ❖元素地址计算方法： ⚫LOC(ai)=LOC(a1 )+(i-1)*L ⚫LOC(ai+1)=LOC(ai )+L ⚫其中： ◆L— 一个元素占用的存储单元个数 ◆LOC(ai )—线性表第i个元素的地址 ❖特点： ⚫实现逻辑上相邻—物理地址相邻 ⚫实现随机存取 ❖实现：可用C语言的一维数组实现
V数组下标 内存 元素序号 a /线性表的动态分配顺序存储结构 a2 2 #define LIST INIT SIZE 100 #define LISTINCREMENT 10 n-1 An typedef struct{ n ElemType *elem; int length; 备 int listsize; 空 }SqList; M-1 或动态申请和释放内存 ElemType *p=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); free(p);
a1 a2 an 0 1 n-1 1 2 n V数组下标 内存 元素序号 M-1 //线性表的动态分配顺序存储结构 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { ElemType *elem; int length; int listsize; }SqList; 备 用 空 间 数据元素不是简单类型时,可定义结构体数组 或动态申请和释放内存 ElemType *p= (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); free(p);
★线性表初始化 线性表的初始化在顺序映像中的实现 Status InitList_Sq(SqList &L){ ∥构造一个空的线性表L。 L.elem (ElemType *)malloc(LIST_INIT_SIZE *sizeof(ElemType)); if(L.elem)exit(OVERFLOW);∥存储分配失败 L.length=0;∥长度为0 L.listsize=LIST_NIT SIZE;∥初始存储容量 return OK; }/InitList_Sq
线性表的初始化在顺序映像中的实现 Status InitList_Sq(SqList &L) { // 构造一个空的线性表L。 L.elem = (ElemType *)malloc(LIST_INIT_SIZE *sizeof(ElemType)); if (!L.elem) exit(OVERFLOW); // 存储分配失败 L.length = 0; // 长度为0 L.listsize = LIST_INIT_SIZE; // 初始存储容量 return OK; } // InitList_Sq 线性表初始化
★插入 定义：线性表的插入是指在第i(1≤≤ 门+1)个元素之前插入一个新的数据元 素X,使长度为门的线性表 a1,a2,.,ai-1,ai 变成长度为n+1的线性表 a1,a2,.,ai-1,X,a a.) 需将第n至第i共（n-i+l)个元素后移 必算法
插入 ❖定义：线性表的插入是指在第i（1i n+1）个元素之前插入一个新的数据元 素x，使长度为n的线性表 (a 1 , a 2 ,……, a i - 1 , a i , …… a n ) 变成长度为n+1的线性表 , , x , i ( ) a a …… a i a ……a n , , , 1 2 - 1 需将第n至第i共（n-i+1)个元素后移 ❖算法
Status ListInsert Sq(SqList &L,int i,ElemType e) {/∥在顺序线性表L中第i个位置之前插入新的元素e, /i的合法值为l≤i<ListLength Sq(L)+] if(i<lli>L.length+l)return ERROR;/i值不合法 if(L.length>=L.listsize){/当前存储空间已满，增加分配 newbase=(ElemType *)realloc (L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(Inewbase)exit(OVERFLOW);/∥存储分配失败 L.elem=newbase: 川新基址 L.listsize+=LISTINCREMENT; /增加存储容量 q-&(L.elem[i-11); q为插入位置 for (p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p; /插入位置及之后的元素右移 *q-e, /插入e ++L.length; 川表长增1 return OK; 时间复杂度为：O(ListLength(L)) }//ListInsert_Sq
Status ListInsert_Sq(SqList &L,int i,ElemType e) {//在顺序线性表L中第i个位置之前插入新的元素e， //i的合法值为1≤i≤ListLength_Sq(L)+1 if (i<1||i>L.length+1) return ERROR;//i值不合法 if (L.length>=L.listsize){//当前存储空间已满，增加分配 newbase=(ElemType *) realloc (L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType)); if (!newbase) exit (OVERFLOW); //存储分配失败 L.elem=newbase; //新基址 L.listsize+=LISTINCREMENT; //增加存储容量 } q=&(L.elem[i-1]); //q为插入位置 for (p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; //插入位置及之后的元素右移 *q=e; //插入e ++L.length; //表长增1 return OK; }//ListInsert_Sq 时间复杂度为: O( ListLength(L) )