顺序表代码题总结

• 顺序表代码总结
• • 习题
  • • 1.1找出最小元素删除并返回
    • 1.2顺序表逆置
    • `1.3删除所有值为x的元素`
    • 1.4有序表删除值在[s,t]之间的元素
    • 1.5顺序表删除值在[s,t]之间的元素
    • `1.6有序表删除重复元素`
    • 1.7合并有序顺序表
    • 1.8同一数组中两线性表互换
    • 1.9查找元素后互换添加
  • 408真题
  • • 2010统考真题
    • 2011年统考真题

仅做自己学习笔记，方便复习所用，如有不当，请多多包涵。

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

bool DEl_min(sqlist $L,Elemtype &value)
//删除顺序表L中的最小值元素结点，并通过引用型参数value返回其值
{if（l.length==0）
	return false;
value=L.data[0];
int pos=0;
for(i=0;i
	if(a[i]
			value=a[i];
			pos=i;
		}
}
L.data[L.length-1]=L,data[pos];
L.length--;
return ture;
}

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

void reverse(sqlist &L)
{
	Elemtype temp;
	for(i=0;i
		temp=L.data[i];
		L.dada[i]=L.data[L.length-1-i];
		L.data[L.length-1-i]=temp;
	}
}//注意此题运用L.length/2，作为前后交换的划分点，无论长度length是奇数还是偶数都成立

注意此处的L.length/2

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

void del(sqlist &L,Elemtype x)
{
	int k=0,i;
	for(i=0;i,
		if(L.data[i]!=x)
		{
		L.data[k]=L.data[i];
		k++;
		}
	}
	L.length=k
}

void del(sqlist &L,Elemtype x)
{
	int k=0,i=0;
	while(i
		if(L.data[i]=x)
			k++;
		else
			L.data[i-k]=L.data[i];
		i++;
	}
	L.length=L.length-k;
}

此题解法2，做题时我也考虑的是数据相等则前移，但是是检查到一个元素之后就把后面所有的元素都前移一个，再检查到就再把之后的元素再前移一个，这个做法时间复杂度到达了O(n²)。
如果考虑双指针，将在左端检测到的x与右端进行调换，但是双指针会改变原表中元素的相对位置。

从有序表中删除其值在给定值s与t之间（包含s与t，要 求s

bool del(sqlist &L,Elemtype s,Elemtype t)
{
	int i=0,j;
	if(s>t||L.length=0)
		return false;
	for(i=0;i=L.length)
		return false;
	for(j=i;j
		L.data[i]=L.data[j];
	}
	L.length=i;//这里的长度很突兀
	return true;
}

从顺序表中删除其值在给定值s与t之间（包含s与t，要 求s

bool del(sqlist &l,Elemtype s,Elemtype t)
{
	int k=0;
	if(s>=t||L.length==0)
		return false;
	for(int i=0;i
		if(L.data[i]t)
		{
			L.data[k]=L.data[i];
			k++;
		}
		//continue;
	}
	L.length=k;
	return true;
}

bool del(sqlist &L.Elemtype s ,Elemtype t)
{
	int k=0;
	if(s>=t||L.length==0)
		return false;
	for(int i=0;i
		if(L.data[i]>=s||L.data[i]<=t)
			k++;
		else
			L.data[i-k]=L.data[i];
	}
	L.length=L.length-k;
	return true;
}

需要在数组中删除某些元素
思想1:把符合条件不需要删除的元素，重新输入到原数组中
思想2:对符合条件需要删除的元素进行计数为k，每遇到不需要删除的就将元素前移空k个

从有序表中删除所有其值重复的元素，使表中所有的元素的值均有不同

bool del(sqlist &L)
{
	if(L.length==0)
    	return false;
    int i,j;//i存储第一个不相同的元素，j为工作指针
	for(i=0,j=1;j
	for(int i=0;i
		int k=0;
		for(int j=i+1;j
			if (L.data[i] == L.data[j])
				k++;	
			else
				L.data[j-k]=L.data[j];
		}
		L.length=L.length-k;
	}
}

此题本想设一个k来计数，作为重复的元素，每遇到一个重复的元素就前移k个，但是忽略了向前移动后，留在原地的元素其实又和元素自己向前移动后的位置元素重复了，造成k计数不准，然后就只能没遇到一个元素就将后面所有的元素都向前移一个（解法二），不知道有没有大佬能解决我遇到的问题，每遇到一个都前移的话，效率不够高

将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表

	bool merge(sqlist a,sqlist b,sqlist &c)//合并有序顺序表 
	{
		if(a.length+b.length>c.length)
			return false; 
		int i=0,j=0,k=0;
		while(i
			if(a.data[i]<=b.data[j])
				c.data[k++]=a.data[i++];
			else
				c.data[k++]=a.data[i++];
		}
		while(i 
算法思想：按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中，然后看哪个表还有剩余，将剩下的部分加到新的顺序表后面
 
1.8同一数组中两线性表互换 
 
typedef int datatype
//此处把int换成datatype是方便若datatype是其他类型是只需把int换成如char等不需改动下面的代码
bool reverse(datatype a[],int left ,int right,int arraysize)//数组逆转
{
	if(left>=right||right>=arraysize)
		return false;
	int mid=(left+right)/2;
	//注意对比已知数组长度时进行逆置是取mid=L.length/2
	for(int i=0;i
		datatype temp=a[left+i];
		a[left+i]=a[right-i];
		a[right-i]=temp;
	}
	return true;
}
bool exchange(datatype a[],int m,int n,int arraysize)
{
	reverse(a,0,m+n-1,arraysize);
	reverse(a,0,n-1,arraysize);
	reverse(a,n,m+n-1,arraysize);
}
 
1.9查找元素后互换添加 
 
void searchexchangeinsert(elemtype a[],elemtype x)
{
	int low=0,high=n-1,mid;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(a[mid]==x) break;
		else if(a[mid]
		elemtype temp;
		temp=a[mid];
		a[mid]=a[mid+1];
		a[mid+1]=temp;
	}//若查找到判断是否mid是最后一位，若不是，则进行与下一位值互换
	if(low>high)//折半查找查询失败的条件(high+1=low)，成功的条件是low<=high
	{
		for(int i=n-1;i>high;i++)
			a[i+1]=a[i]；
			a[i+1]=x;
	}

}
 
考虑到是顺序存储，还是有序的，所以考虑题目要求在最短时间所以考虑折半查找(时间复杂度为O(log2n))，不考虑顺序查找(时间复杂度为O(n))，还要仔细考虑折半查找成功和失败的条件，以及失败时low和high停留在哪里。
 
408真题 
2010统考真题 

 代码和思想参考习题1.8，算法时间复杂度为O(n)，空间复杂度为O(1)。
 
2011年统考真题 
 
此题我的解法是想将两个有序表合并之后取n/2，若等长序列的长度为m的话，那么时间复杂度就为o(m)了，解完后去看参考答案的时间复杂度只有O(log2n)
 参考答案思想如下：
 分别求两个升序序列A、B的中位数，设为a和b，求序列A、B的中位数过程如下：
 （1）若a=b，则a或b即为所求中位数，算法结束；
 （2）若a （3）若a>b，则舍弃序列A中较小的一半，同时舍弃序列B中较大的一半，要求两次舍弃的长度相等；
 在保留的两个升序序列中，重复过程（1）、（2）、（3）直到两个序列中均只含有一个元素为止较小者即为所求的中位数吧。
 代码以后有时间再打。