22线性表的顺序表示和实现 动态创建一个空顺序表的算法:(见教材P3) Status InitList Sq( Sqlist&L)刨建一个空线性表 elem=(Elem Type*)malloc(LIST INIT SIZE Sizeof(Elem Type) rf!L.elem) exit(oVERFLOW);∥)分配失败,结束程序 Llength=0 /暂无元素放入,空表 L listsize= LIST INIT SIZE;∥表尺寸=初始分配量 Return OK; //netList_Sq sizeof(x)的意思是: malloc(m)函数的意思是:新开一片 大小为m字节的连续空间,并把该 计算变量的长度字节数区首址作为函数值。 数据结构 ③@
37 sizeof(x)的意思是： 计算变量x的长度(字节数) malloc (m)函数的意思是：新开一片 大小为m字节的连续空间，并把该 区首址作为函数值。 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 动态创建一个空顺序表的算法： （见教材P23） 2.2 线性表的顺序表示和实现
22线性表的顺序表示和实现 二、线性表的顺序存储实现插入、删除、查找 1、插入a和a的逻辑关系发生变化 ①含义:在线性表的第个元素之前插入一个新的 数据元素 ②实现步骤 将第n到第个元素依次向后移动一个位置 将要插入的元素保存到第个位置上共(m+)个元素 将表长n加1 注意:i的取值范围1≤i≤n+1 数据结构 ③◎@
38 二、线性表的顺序存储实现 1、插入 插入、删除、查找 ① 含义：在线性表的第i个元素之前插入一个新的 数据元素 ② 实现步骤 • 将第n到第i个元素依次向后移动一个位置 • 将要插入的元素保存到第i个位置上 • 将表长n加1 共（n-i+1）个元素 ai-1和ai的逻辑关系发生变化 注意：i的取值范围1≤i≤n+1 2.2 线性表的顺序表示和实现
22线性表的顺序表示和实现 ③实现算法(教材2) Status ListInsert Sq sqlist &l int i, Elem Type er f(iI‖i> Llength+1) return error∥检验值的合法性 if( Llength≥ Llistsize)/着表长超过表尺寸则要增加尺寸 i newbase=( ElemType*)realloc(Lelem, L listsize LISTINCREMENT sizeof( Elem Type ) if( newbase== NULL exit( OVERFLOW);/分配失败则退出并报错 L.elem= newbase/重置新基址 L. . listsize=L. listsize+ LISTINCREMENT}/增加表尺寸 rea1loc(*p, newsie)函数的意思是:新开一片大小为 newsie的连 续空间,并把以*为首址的原空间数据都拷贝进去。 数据结构 39 ③@
39 ③ 实现算法(教材P24) realloc (*p, newsize)函数的意思是：新开一片大小为newsize的连 续空间，并把以*p为首址的原空间数据都拷贝进去。 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=NULL )exit( OVERFLOW ) ; //分配失败则退出并报错 L.elem = newbase ; //重置新基址 L.listsize = L.listsize + LISTINCREMENT ; } //增加表尺寸 2.2 线性表的顺序表示和实现
22线性表的顺序表示和实现 q=&( Lelemi-1);/q为插入位置 for (p=& lelem.length-1; p>=q-p)*(p+1)=*p; /腼入位置及之后的元素统统后移,p为元素位置 q=e;/插入e ++ Length;增加1个数据元素,则表长+1 return OK; ∥ istInsert Sq 数据结构 ③◎@
40 q = &(L.elem[i-1] ); // q为插入位置 for ( p = & L.elem[L.length-1] ; p>=q ; --p ) *(p+1) = *p ; //插入位置及之后的元素统统后移, p为元素位置 *q= e ; //插入e ++L.length ; //增加1个数据元素，则表长+1 return OK ; } //ListInsert_Sq 2.2 线性表的顺序表示和实现
22线性表的顺序表示和实现 2、删除a1、a、4+的逻辑关系发生变化 ①含义:删除线性表的第i个位置上的元素 ②实现步骤 将第i+1到第n个元素依次向前移动一个位置 共(n-i)个元素 将表长n减1 注意:i的取值范围1≤i≤n 数据结构 41
41 2、删除 ① 含义：删除线性表的第i个位置上的元素 ② 实现步骤 • 将第i+1到第n个元素依次向前移动一个位置 • 将表长n减1 共（n-i）个元素 ai-1、ai、ai+1的逻辑关系发生变化 注意：i的取值范围1≤i≤n 2.2 线性表的顺序表示和实现