【数据结构】静态分配的顺序表的删除元素

#include
#include

#define maxSize 10

typedef struct {
	int data[maxSize];
	int length;
}SqList;

void initList(SqList &L) {
	for(int i=0;i<L.length;i++) {
		L.data[i]=0;
	}
	L.length=0;
}

/**
* 思路:删第i个元素，那就将第i+1个位置的元素移到第i个位置，依次类推
* 此时就要循环第i个元素及其之后的元素的值，使得L.data[i-1]=L.data[i] 
* 第i个元素之前的元素保持不动，在循环时，就让j从i的值开始，加判断条件，j
// 删除顺序表第i个位置的数据元素，假设i=3，e是为了将删除的元素的值返回 
bool ListDelete(SqList &L, int i, int &e) {
	// 为了代码健壮性，要兼容一下
	if(i<1 || i>L.length) {
		return false;
	} 
	e=L.data[i-1];		// 将要删除元素的值给e 
	for(int j=i;j<L.length;j++) {
		L.data[j-1] = L.data[j];	
	}
	L.length--;
	return true;
}

int main() {
	SqList L;
	int e;
	initList(L);
	if(ListDelete(L,0,e)) {
		printf("%d\t当前删除的元素e\n", e); 	
	}else {
		printf("位序i不合法，删除失败\n"); 	
	}	
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

// 分析时间复杂度
// 1、删除表尾元素，就不需要移动，i=n，循环0次，时间复杂度为O（1）
// 2、删除表头元素，i=1，循环n-1次，时间复杂度为o(n) 
// 3、删除除表头、表尾外的任意一个元素，它们的概率都是1/n
	// i=1，循环n-1次，i=2，循环n-2次，...i=n，循环0次
	// 平均循环次数=循环总次数*概率=(1+2+3+...+n)*(1/n)=(n(n-1)/2)*(1/n)=(n-1)/2
	// 时间复杂度为o(n) 
1
2
3
4
5
6
7