存储地址 内存状态 元素序号 数据结构 线性表 空闲 线性表的顺序存储结构示意图 >重新分配动态存储空间的函数 数据结构 realloc(原动态区首址,字节数 其功能为: >申请新的动态存储空间(成功或失败); >将原动态区的数据拷贝到新动态区; >释放原动态存储区 返回新存储区首地址(无类型) >用途:当原动态区不够用时,追加动态 存储区;
6 数 据 结 构 之 线 性 表 11 存储地址 内存状态 元素序号 空闲 a a a a 1 2 i n : : : : : : : b b+L b+(i-1)L b+(n-1)L B+(maxlen-1)L 1 2 i n 线性表的顺序存储结构示意图 数 据 结 构 之 线 性 表 12 ¾ 重新分配动态存储空间的函数 realloc(原动态区首址，字节数) ¾其功能为： ¾申请新的动态存储空间(成功或失败); ¾将原动态区的数据拷贝到新动态区; ¾释放原动态存储区; ¾返回新存储区首地址（无类型）。 ¾用途：当原动态区不够用时，追加动态 存储区；
顺序表的操作 >构造一个空的线性表L ws #define List Init Size 100 A #define ListIncrement 10 2 Status InitList Sq( SqList &L) L elem=(ET)malloc (List Init Size sizeof(ET)) if(L. elem--NULL) 性 exi( OVERFLOW);/存储分配失败* 表 Llength=0: /空表的长度* L listsize= List init size;初始存储容量 return OK: 插入操作:在顺序表L中第个位置上插 入一个新的元素e。 据 >形式参数为:&L,i,e 算法步骤如下 构 对输入参数的安全性检查:插入位置i应落在 表长+1范围内,即:1≤i≤L. length+1 存储空间的处理:若原表的存储空间已满,应追 加存储空间的分配 数据块的搬移:将表中从i到L. length位置上的 所有元素往后移动一个位置; >在第i个位置上存储新的元素e,表长增1 注意:逻辑位置(序号)i对应的存储下 标是i-1
7 数 据 结 构 之 线 性 表 13 ¾ 顺序表的操作 ¾ 构造一个空的线性表 L #define List_Init_Size 100 #define ListIncrement 10 Status InitList_Sq( SqList &L){ L.elem=(ET*)malloc(List_Init_Size*sizeof(ET)); if(L.elem==NULL) exit(OVERFLOW); /*存储分配失败*/ L.length=0; /* 空表的长度 */ L.listsize=List_Init_Size; /* 初始存储容量 */ return OK; } 数 据 结 构 之 线 性 表 14 ¾ 插入操作：在顺序表L中第i个位置上插 入一个新的元素e。 ¾形式参数为：&L ,i , e ； ¾算法步骤如下： ¾对输入参数的安全性检查: 插入位置 i 应落在 表长＋１范围内，即： 1≤ i ≤ L.length+1 ¾存储空间的处理：若原表的存储空间已满，应追 加存储空间的分配； ¾数据块的搬移：将表中从i到L.length位置上的 所有元素往后移动一个位置； ¾在第i个位置上存储新的元素e,表长增１; ¾注意：逻辑位置（序号）i 对应的存储下 标是i-1
顺序表--插入操作算法描述之 s Status ListInsert_Sq(SqList &L, int i, ET e) if (i<l i>Llength+1)return ERROR; I*s if(L length >=L listsize) P=(ET )realloc (L elem, (L listsize+10)*sizeof(ET)) if(p-NULL) exit(OVERFLOW); L elem=p; Llistsize+=ListIncrement; 线性表 for(j=Llength; j>i; -j) Lelem j=L elem j-1; Lelemie; ++.length; return OK: 顺序表-插入操作算法描述之二 Status ListInsert Sq(sqlist &L, int i, ET e)t if (i<l iLlength+1)return ERROR; w if (L length >= L listsize) 构 P=(ET"realloc(Lelem, L. listsize-+10)* sizeof(ET); if(p-NULL) exit(OVERFLOW); L elem=p; L listsize+=ListIncrement; q=&( L elemi1);*q= L elem+(i1)插入位置 for (p=&(L elem[.length-l D;>=g:--p) (p+1)=p ge: ++Llength return OK;
8 数 据 结 构 之 线 性 表 15 ¾顺序表----插入操作算法描述之一 Status ListInsert_Sq(SqList &L , int i , ET e){ if ( i<1 || i>L.length+1) return ERROR; if(L.length >= L.listsize){ p=(ET*)realloc(L.elem,(L.listsize+10)*sizeof(ET)); if (p==NULL) exit(OVERFLOW); L.elem=p; L.listsize+=ListIncrement; } for( j=L.length ; j>=i ; --j ) L.elem[j]=L.elem[j-1]; L.elem[j]=e ; ++L.length ; return OK; } 数 据 结 构 之 线 性 表 16 ¾顺序表----插入操作算法描述之二 Status ListInsert_Sq(SqList &L , int i , ET e){ if ( i<1 || i>L.length+1) return ERROR; if (L.length >= L.listsize){ p=(ET*)realloc(L.elem,(L.listsize+10)*sizeof(ET)); if (p==NULL) exit(OVERFLOW); L.elem=p; L.listsize+=ListIncrement; } q=&(L.elem[i-1]); /* q=L.elem+(i-1) 插入位置 */ for (p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; *q=e ; ++L.length ; return OK; }
插入操作的算法性能分析 据结构 >空间复杂度是O(1) >时间复杂度:O(m),其中n= Llength 步骤(1)、(2)、(4)的时 间复杂度都是常数,即:O(1); 步骤(3)的基本操作是数据移动 线性表 最坏的情况下(在第一个位置上插入元素), 需要移动n个元素; 平均情况下(等概率),需移动表中n/2 个元素,最好的情况是不移动元素 因此,插入操作算法的时间复杂度是Om) 删除操作:长为n的线性表L(a1,a2,… 数据结构 an),删除a1,并把它送入某单元e n-1 n-1 18 顺序存储结构的删除操作
9 数 据 结 构 之 线 性 表 17 ¾插入操作的算法性能分析 ¾空间复杂度是 O( 1 ) ¾时间复杂度： O(n) , 其中n= L.length ¾步骤（１）、（２）、（４）的时 间复杂度都是常数，即：O ( 1 ); ¾步骤（３）的基本操作是数据移动， 最坏的情况下(在第一个位置上插入元素)， 需要移动n个元素； 平均情况下（等概率），需移动表中 n/2 个元素，最好的情况是不移动元素。 因此，插入操作算法的时间复杂度是O(n); 数 据 结 构 之 线 性 表 18 ¾ 删除操作：长为n的线性表L(a1,a2, … , an ), 删除ai ，并把它送入某单元e e ai a1 a2 a3 ai-1 ai an : : 1 2 3 i-1 i n-1 i+1 n : : a1 a2 a3 ai-1 an : : 1 2 3 i-1 i n-1 i+1 n : : ai+1 顺序存储结构的删除操作