表范围！");
8 }
9 L->elem[i - 1] = e;
10 }
复制代码
常用的，也是比较重要的插入和删除算法
复制代码
1 //12、插入操作，线性表 L 已存在，1≤i≤LengthList(L)+1。在 L 的第 i 个元素之前插入新的元素 e，L 的长度增 1。
2 void ListInsert(SqList *L, int i, int e )
3 {
4 SqList *NL;//声明一个额外的结构指针指向重新分配的表内存空间
5 int *j;
6 int *k;
7 //注意c数组下标从0开始，但是用户并不知道，一般都是选择从1到length的位置，以用户的角度看问题
8 //在元素i之前插入，则把i和i后面的全部元素顺次后移一位
9 if (i < 1 || i > L->length + 1)//最后一个元素后一位插入合法，不用移动直接插即可
10 {
11 puts("超出表范围！");
12 }
13 //考虑问题要全，因为可能会不止一次插入操作，早晚会超出表的存储容量
14 else if (L->length >= L->listsize)
15 {
16 //重新分配内存，增加存储空间
17 NL->elem = (int *)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(int));
18 if (!NL->elem)//分配失败，返回NULL
19 {
20 exit(0);//退出
21 }
22 //分配成功
23 L->elem = NL->elem;//得到扩大之后的新基址
24 }
25 //指示用户的实际插入位置
26 j = &(L->elem[i - 1]);//数组下标从0开始
27 //最后一个数据元素的实际位置是length-1
28 for (k = &(L->elem[L->length - 1]); k >= j; k--)//这里k--不是1的减量！而是指针的减量操作，每次是int类型字节大小变化
29 {
30 *(k + 1) = *k;//从j到k的元素顺次后移一位
31 }
32 *j = e;//完成插入
33 L->length++;//别忘表长加1
34 }
复制代码
1、需要注意一下运算符优先级，箭头（间接运算符）的优先级很高，高于取地址&
2、解析realloc函数
它可以对给定的指针所指的空间进行扩大或者缩小，原有内存的中内容将保持不变。对于缩小，则被缩小的那一部分的内容会丢失 ，realloc 并不保证调整后的内存空间和原来的内存空间保持同一内存地址。realloc 返回的指针很可能指向一个新的地址。因为realloc是从堆上分配内存，当扩大内存空间，realloc直接从堆上现存的数据后面的那些字节中获得附加的字节，但如果数据后字节不够，就用堆上第一个有足够大小的自由块，现存的数据被拷贝至新的位置，而老块则放回到堆上。
在代码中，如果我们采用i = (int*)realloc(i, 2*sizeof(int))的重新分配内存方式，有以下两种情况：
分配成功：
realloc函数完成后，i 曾经指向的旧内存自动free掉。
分配失败，返回NULL值：
此时，i 原来指向的内存还没有被free掉，而现在又找不到地址，这样就出现memory leak！
解决办法：定义另一个指针j用于接收realloc返回值，判断是否成功，成功则将 j 赋给 i
3、插入算法的时间复杂度分析：
问题规模是表的长度，值为 n。 算法的时间主要花费，在向后移动元素的 for 循环语句上。该语句的循环次数为 (n– i +1)，所需移动结点的次数不仅依赖于表的长度 n，而且还与插入位置 i 有关。
当插入位置在表尾 (i=n +1) 时，不需要移动任何元素；这是最好情况，其时间复杂度 O(1)。
当插入位置在表头 (i = 1) 时，所有元素都要向后移动，循环语句执行 n 次，这是最坏情况，其时间复杂度 O(n)。
4、插入算法的平均时间复杂度：
设 pi 为第 i 个元素之前插入一个元素的概率，则在长度为 n 的线性表中插入一个元素时所需移动元素次数的期望值为
假设在n+1个位置上，插入的概率一样，那么pi = 1/(n+1)；
E = pi【（n）+（n-1）+ ……+ 3 + 2 + 1】 =pi x（ n（n+1）/ 2） = n / 2
由此可见，在顺序表上做插入运算，平均要移动 一半元素。当表长 n 较大时，算法的效率相当低。 插入 算法的 平均时间复杂度为 O(n)。
复制代码
1 //13、删除操作，表 L 已存在且非空，1≤i≤LengthList(L)。删除 L 的第 i 个元素，并用 e 返回其值，长度减 1。
2 void ListDelete(SqList *L, int i, int *e )
3 {
4 int *p;
5
6 if (i < 1 || i > L->length)
7 {
8 puts("i的值不合法！重新输入！");
9 }
10 else
11 {
12 //找到被删除元素的实际位置
13 p = &(L->elem[i - 1]);
14 *e = L->elem[i - 1];
15 //p（不包含p）后面的元素依次前移一位
16 for (; p < &(L->elem[L->length - 1]); p++)
17 {
18 *p = *(p + 1);
19 }
20 L->length--;
21 }
22 }
复制代码
1、这里e使用指针变量，这样形参就可以修改实参！
2、删除算法的时间复杂度分析
算法的时间主要花费在向前移动元素的 for 循环语句上。该语句的循环次数为 (n – i)。由此可看出，所需移动结点的次数不仅依赖于表的长度 n，而且还与删除位置 i 有关。
当删除位置在表尾 (i = n) 时，不需要移动任何元素；这是最好情况，其时间复杂度 O(1)。
当删除位置在表头 (i = 1) 时，有 n -1 个元素要向前移动，循环语句执行 n -1 次，这是最坏情况其时间复杂度 O(n)。
3、算法的平均时间复杂度：
设 qi 为删除第 i 个元素的概率，则在长度为 n 的线性表中删除一个元素时所需移动元素次数的期望值为
假设，每一个位置的元素被删除的概率都一样，那么qi = 1 / n
E = qi【（n-1）+（n-2）+……+3+2+1】=1/n x （（n-1）n / 2）=（n - 1）/ 2
可见，在顺序表上做删除运算，平均也要移动表上 一半元素。当表长 n 较大时，算法的效率相当低。算法的平 均时间复杂度为 O(n)。
复制代码
1 /******************************