线性表的顺序表示和实现

1.顺序表示和实现

sequence sq顺序（谁困死在顺序的车道）

flow （f漏 流动流淌）

overflow（溢出 漫出）

init→ initialize → 初始化（1/0）

merge（mer j）合并

2.顺序表的插入

先移动元素，再插入新元素，最后修改长度。

从最后一个元素(开始移动)往前移动(调整过的数组的a[3]等于之前数组的a[2]然后再是a[2]等于a[1]):

a[3] = a[2];
a[2] = a[1];

int ListInsert_sq(Sqlist *L,int i,ElemType e)
{
if(i<1|| i >L->length+1) //判断插入位置(顺序表要是连续的)
{
return ERROR;
}

if(L->length>=L->listsize) //判断是否扩容 实际元素数量是否已经达到容量。
{
ElemType *newbase;

newbase = realloc(
L->elem,
(L->listsize+LISTINCREMENT)*sizeof(ElemType) );

if(newbase==NULL)
{
return OVERFLOW;
}

L->elem=newbase; //更新 指针elem，保存可能发生变化的新地址。realloc可能申请新的内存区域并复制原有数据
L->listsize+=LISTINCREMENT; //更新容量listsize
}（内存不够，并且扩容结束）

顺序表插入的核心

for(int j=L->length;j>=i;j--)
{
L->elem[j]=L->elem[j-1];
}

L->elem[i-1]=e;//插入元素
L->length++;//长度加一

return OK;
}

3.顺序表的删除

先取出要删除的元素，再把后面的元素 向前移动。

for(++p; p<=q; ++p) ++p 是初始化 只执行一次 (初始化; 循环条件; 更新操作)

需要接收一个地址*e = *p;才能修改主函数中的变量。（删除的值）

--L->length;（删除一个元素，只需要修改length）

4.时间复杂度

插入平均移动次数删除平均移动次数

顺序表的插入和删除，平均时间复杂度都是O(n)。

5.顺序表的合并

把 La 和 Lb 拼在一起，保持从小到大的顺序。

初始化 Lc 的长度和容量

Lc->listsize = Lc->length = La->length + Lb->length;

6return 0和return 1最大的区别

• return：把一个值返回给调用者，同时结束 当前函数。

• if：0为假，非 0为真。

• main()：返回 0通常表示程序正常结束，非 0通常表示异常或错误。

7.realloc

realloc全称是 Re-allocation（重新分配内存）。调整之前已经申请的动态内存空间大小。realloc()作用是扩容

realloc(原来的内存地址(例如指针p),新的内存大小);