顺序表删除元素_向量a中已有n个元素,写出删除其第i个位置元素的算法

        顺序表中删除元素有许多情况，目前本人直接出到两种。一种是在顺序表中删除某一个元素，另外一种则是在顺序表中删除所有值为x的元素。

        第一种，顺序表中删除某一元素。首先需要判断删除位置是否合法，接着需要找到要删除的元素，用一个变量带出，并将其释放。最后需要把原表中删除元素后面位置的所有元素都向前移动一个位置。

        代码如下：

int DelList(Seq *L,int i,int *e)
/*在顺序表中删除第i个位置的元素，并用参数e带出。i的合法位置为1<=i<=L.last+1 */
{
int k;
if((i<1）||(i>L->last+1))
    {
    printf("删除位置不合法");
    return FALSE;
    }
* e = L->elem[i-1];    /*将被删除的元素放到e中带出，从而释放出这个结点的位置*/
for(k=i;i<L->last;i++)
    L->elem[k-1]=L->elem[k];    /*后面的元素依次前移*/
L->last--;
return OK;
}

        注意的是，用*e带出的时候，需要提前为e创建相应的结点，即e=(int*)malloc(sizeof(int));

另外，还有一个指针问题在第二种删除中说明。

第二种：

        删除顺序表中所有值为x的元素。有两种方法，一种是对顺序表遍历，遇到值为x的元素，便把其删除。这种办法的时间复杂度为O(n*2)，因为遍历一遍为O(n)，删除是O(1),删除后还需把表前移，又是O(n)。所以总的时间复杂度为O(n*2)，本质也是第一种的一种删除方法的延伸。这里着重介绍第二种删除方法。即：

        在原有的空间上重建一个新表。设置两个指示器，i和j，初始值都为0。i用来指向当前正在扫描的原表中元素的位置，j用来表示当前正在新建的表的表尾下一个位置。这样，可根据L->elem[i]==x做出不同的处理。当L->elem[i] != x，则L->elem[j] = L->elem[i];i++;j++;否则i++;继续扫描，直到原表末尾。

        代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define MAX 20
 
typedef struct {
	int a[MAX];
	int last;
}Seq;
 
void delx(Seq* L, int x);
 
int main() {
	int c;
	Seq Mylist = { {1,5,6,7,7,5,5,8,9,10},10 };
	printf("请输入一个你想要去掉的数：");
	scanf("%d", &c);
	delx(&Mylist, c);
	printf("输出去掉后的列表：");
	for (int i = 0; i < Mylist.last; i++) {
		printf("%d ", Mylist.a[i]);
	}
}
 
void delx(Seq* L, int x) {
	int i = 0, j = 0;
	while (i <= L->last) {
		if (L->a[i] != x) {
			L->a[j] = L->a[i];
			i++; j++;
		}
		else i++;
	}
	L->last = j - 1;
}

这里要说明上面提到的指针第二问题。由于我是用Seq创建的表，而不是用Seq*，而声明的函数却是Seq*类型的。他是指针类型，故而在main()中的函数需要用&来告诉计算机，他需要操作的地址在哪。

        结果如下：