线性表—顺序存储习题1.1-1.4

1.1.从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删除的元素的值，空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行 。

bool Del_Min(SqList &L, ElemType &value) {	if (L.length == NULL)		return false;	value = L.data[0]; //假设0号元素的值最小	int pos = 0;	for (int i = 1;i < L.length;i  ) {		if (L.data[i] < value) {			value = L.data[i];			pos = i;		}	}	L.data[pos] = L.data[L.length - 1]; //空出的位置由最后一个元素填补	L.length--;	return true;}

1.2.设计一个高效的算法，将顺序表的所有元素逆置，要求算法的空间复杂度为O(1)

算法思想：扫描顺序表L的前半部分元素，对于元素L.data[i]，将其余后半部分对应元素L.data[L.length-i-1]进行交换。

void Reverse(SqList &L) {	ElemType temp;	for (int i = 0;i < L.length;i  ) {		temp = L.data[i];		L.data[i] = L.data[L.length - i - 1];		L.data[L.length - i - 1] = temp;	}}

1.3长度为n的顺序表L,编写一个时间复杂度为O（n）,空间复杂度为O(1)的算法,该算法删除线性表中所有值为x的数据元素

//解法一：用k标记不等于x的元素，将不等于x的元素向前放到k的位置上，修改L的长度void del_x_1(SqList &L, ElemType x) {	int k = 0;	for (int i = 0;i < L.length;i  ) {		if (L.data[i] != x) {			L.data[k] = L.data[i];			k  ; //用k记录不等于x的元素的个数		}	}	L.length = k; //顺序表长度等于k}

//解法二：用k记录顺序表中等于x的元素个数，边扫描边统计k，并将不等于k的元素向前移动k个位置。void del_x_2(SqList &L, ElemType x) {	int k = 0;	for (int i = 0;i < L.length;i  ) {		if (L.data[i] == x)			k  ;		else			L.data[i - k] = L.data[i]; //当前元素前移k个位置		i  ;	}	L.length = L.length - k; //顺序表长度递减}

1.4. 从有序顺序表中删除其值在给定值s与t之间（要求s<t）的所有元素，如果s或t不合理或者顺序表为空则显示出错信息并退出运行

//先找出>=s的第一个元素，再找出>t的第一个元素，将后面元素前移bool del_s_t2(SqList &L, ElemType s, ElemType t) {	int i, j;	if (i > L.length || s >= t)		return false;	for (i = 0; i < L.length&&L.data[i] < s;i  ); //寻找>=s的第一个元素	if (i >= L.length) return false; //所有元素值都小于s则返回	for (j = i;j <= L.length&&L.data[j] <= t;j  ); //寻找>t的第一个元素	for (;j < L.length;i  ,j  ) //前移，填补被删除元素位置		L.data[i] = L.data[j];	L.length = i   1;	return true;}

来源：https://www.icode9.com/content-4-393351.html