二、顺序表上实现的基本操作 在顺序表存储结构中,很容易实现线性表的一些操作,如线 性表的构造、第i个元素的访问。 ●注意:C语言中的数组下标从“0”开始,因此,若L是 Sqlist类型的顺序表,则表中第个元素是L.data[i-们]。 顺序表上基本运算 ●1、顺序表的初始化 ●2、插入运算 ●3、删除运算 ●4、按值査找 北京邮电大学自动化学院 16
北京邮电大学自动化学院 16 ⚫ 在顺序表存储结构中，很容易实现线性表的一些操作，如线 性表的构造、第i个元素的访问。 ⚫ 注意：C语言中的数组下标从“0”开始，因此，若L是 Sqlist类型的顺序表，则表中第i个元素是L.data[i-1]。 二、顺序表上实现的基本操作 ⚫ 顺序表上基本运算 ⚫ 1、 顺序表的初始化 ⚫ 2、 插入运算 ⚫ 3、 删除运算 ⚫ 4、 按值查找
1、插入 ●线性表的插入是指在表的第个位置上插入一个值为x的新元 素,插入后使原表长为n的表: (a,a2 计1 ●成为表长为n+1表: (a1,a2,…,a1,X,a1,aH1,…,an)。1≤=<=n+1。 顺序表上完成这一运算需要通过以下步骤进行: 1)将a;~an顺序向下移动,为新元素让出位置; 2)将x置入空出的第i个位置; 3)修改last指针(相当修改表长),使之仍指向最后一个元素。 北京邮电大学自动化学院
北京邮电大学自动化学院 17 ⚫ 线性表的插入是指在表的第i个位置上插入一个值为 x 的新元 素，插入后使原表长为 n的表: ⚫ (a1，a2，... ，ai-1，ai，ai+1，... ，an ) ⚫ 成为表长为 n+1 表: ⚫ (a1，a2，...，ai-1，x，ai，ai+1，...，an ) 。 1<=i<=n+1 。 1、插入 ⚫ 顺序表上完成这一运算需要通过以下步骤进行： ⚫ 1）将ai ～an 顺序向下移动，为新元素让出位置； ⚫ 2）将 x 置入空出的第i个位置； ⚫ 3）修改 last 指针(相当修改表长)，使之仍指向最后一个元素
V数组下标内存元素序号V数组下标内存元素序号 a a a i ai a i n an n n-1 n+1 n n+1 北京邮电大学自动化学院
北京邮电大学自动化学院 18 内存 a1 a2 ai ai+1 an 0 1 i-1 V数组下标 n-1 i n 1 2 i 元素序号 i+1 n n+1 内存 a1 a2 ai ai+1 an 0 1 i-1 V数组下标 n-1 i n 1 2 i 元素序号 i+1 n n+1 an-1 x
算法23 o Status Listinsert Sa sqlist &L, int i, ElemType e) if(i1|> Llength+1) return error∥i值不合法 if( L length>=L. listsize)当前存储空间已满,增加分配 o newbase=(ElemType *)realloc(L elem, (L listsize+LISTINCREMENT)*Sizeof (ElemType) If(! newbase)exit( OVERFLOW);存储分配失败 Lelem= newbase;∥/新地址 Llistsize+= LISTINCREMENT;}∥增加存储容量 北京邮电大学自动化学院 19
北京邮电大学自动化学院 19 ⚫ Status ListInsert_Sq(SqList &L，int i，ElemType e) ⚫ {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;} // 增加存储容量 } 算法2.3
算法23 ●q=&( Elem[-1]);q为插入位置 o for(p=&(L elem [L.): p>=g; -p) (p+1)=p ●/插入位置及之后的元素后移 ●*q=e;∥插入e ●+ L length;∥表长增1 return OK, ]//listInsert Sq 北京邮电大学自动化学院
北京邮电大学自动化学院 20 ⚫ q=&(L.elem[i-1]); //q为插入位置 算法2.3 ⚫ for(p=&(L. elem [L.length-1]);p>=q;--p) *(p+1)=*p; ⚫ //插入位置及之后的元素后移 ⚫ *q=e; //插入e ⚫ ++L.length; //表长增1 ⚫ return OK;} //IistInsert_Sq