本文共 2012 字，大约阅读时间需要 6 分钟。

算法

假设顺序表中的元素递增有序，设计算法在顺序表中插入元素x，要求插入后仍然保持递增有序

void list::insert1(int x) {
   	int i = count - 1;	if (i >= 9) cout << "The camber is overflow" << endl;	while (x < data[i] && i>0) {
   		data[i + 1] = data[i]; i--;	}	data[i + 1] = x;	cout << "The value is successful to put in" << endl;}

分析：在第i个位置1插入时需要移动n-i+1个元素,最好的情况下比较1次，移动0次

假设顺序表A、B分别表示一个集合，涉及算法以判断集合A是否是集合B的子集，若是，返回True，否则返回False，并分析算法性能

bool subset(list A, list B) {
   	int ia, ib;	int a, b;	for (ia = 0; ia < A.length(); ia++) {
   		A.get_elementtype(ia, a);		ib = 0; bool suc = false;		while (ib < B.length() && suc == false) {
   			B.get_elementtype(ib, b);			if (a == b) suc == true;			else ib++;		}			if (suc == false) return false;		}		return true;	}

分析算法性O(A*B)

假设顺序表递增的顺序表A、B分别表示一个集合，涉及算法以判断集合A是否是集合B的子集，若是，返回True，否则返回False，并分析算法性能

bool subset1(list A, list B) {
   	int ia = 0, ib = 0;	int a, b;	while (ia < A.length() && ib < B.length()) {
   		A.get_elementtype(ia, a); B.get_elementtype(ib, b);		if (a == b) {
   			ia++; ib++;		}		else if (a > b)ib++;		else return false;	}	if (ia >= A.length()) return true;	else return false;}

分析：ia 和ib分别表示指向A和B的两个指针，有三种情况

1.data[ia]==data[ib]——>ia++;ib++

2.data[ia] >data[ib]——>ib++;

3.data[ia] <data[ib]——>return Fasle

算法性能：O(A+B)

涉及算法将递增的有序顺序表A、B中的元素值合并为一个递增有序顺序表C，要求时间尽可能的少

void merg_list(list A, list B, list& C) {
   	int ia = 0, ib = 0, ic = 1;	int a, b;	while (ia < A.length() && ib < B.length()) {
   		A.get_elementtype(ia, a); B.get_elementtype(ib, b);		if (a == b) {
   			C.insert(ic, a); ic++; C.insert(ic, a);		}		else if (a > b) {
   			C.insert(ic, b); ic++; ia++;		}		else {
    C.insert(ic, a); ic++; ib++; }	}	while (ia < A.length()) {
   		A.get_elementtype(ia, a); C.insert(ic, a); ic++; ia++;	}	while (ib < B.length()) {
   		B.get_elementtype(ib, b); C.insert(ib, b); ic++; ib++;	}}

分析：尽可能的少，就代表O(A+B)

就会用两个不同的指针ia,ib分别指向A和B，有三种不同的情况

1.data[ia]==data[ib]——>C.insert(ic,a);ic++;C.insert(ic,a);

2.data[ia] >data[ib]——>C.insert(ic,b);ic++;

3.data[ia] <data[ib]——>C.insert(ic,a);ic++;

转载地址：http://zjwki.baihongyu.com/