算法 2.6.txt

数据结构各种算法原代码及图形示例

算法 2.6
void ListInsert_Sq( SqList &L, int i, ElemType e ) 
{
      // 在顺序线性表 L 的第 i 个元素之前插入新的元素 e，i 的合法值为
      // 1≤i≤L.length+1, 若表中容量不足，则按该顺序表的预定义增量扩容 
      if (i < 1 || i > L.length+1)  ErrorMessage(" i 值不合法"); 
      if (L.length >= L.listsize)  increment( L, L.incrementsize );
         // 当前存储空间已满，为 L 增加分配 L.incrementsize 个元素空间
      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
} // ListInsert_Sq

其中为顺序表追加空间的函数为:
void increment ( SqList &L, int k )
{
      // 为顺序表扩大 k 个元素空间
      ElemType a[];
      a = new ElemType[L.listsize+k];    // a 为临时过渡的辅助数组
      for(i = 0; i<L.length; i++ )  a[i] = L.elem[i];  // 腾挪原空间数据
      delete [] L.elem;         // 释放数据元素所占原空间 L.elem
      L.elem = a;               // 移交空间首地址
      L.listsize += k;          // 扩容后的顺序表最大空间 
      delete [] a;              // 释放辅助数组空间
}