线性表之顺序表刷题

￡神魔★判官ぃ 2022-10-12 05:56 140阅读 0赞

## 线性表之顺序表刷题 ##

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

//算法思想：搜索整个顺序表，查找最小值元素并记住其位置，搜索结束后用最后一个元素填补其位置
    	bool Del_Min(sqList &L,ElemType &value){
        
    	//删除顺序表L中最小元素的结点，并用引用型参数value返回其值
    	//若删除成功，则返回true，否则返回false
    		if(L.length==0)
    			return false;//空表，中止操作返回
    		value=L.data[0];//从第1个元素开始遍历
    		int pos=0;//记录位置
    		for(int i = 1 ; i < L.length; i++)
    		{
        
    			if(L.data[i]>value)
    				value = L.data[i]; pos = i ;//让value记忆当前具有最小值的元素，pos记录当前位置
    				//同时value也会将最小值带出函数
    		}
    		L.data[pos]=L.data[L.length-1];//用最后一个元素填补最小值位置
    		L.length--;
    		return true;
    	}

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

算法思想:扫描L的前半部分元素，对于元素L.data[i](0<=i<L.length/2),将其对应的后半部分元素L.data[L.length-1-i]与其交换
    如果顺序表长为偶数，正好交换完，如果是奇数，正好中间的元素不参与运算，也应为整数除法向下取整，不会被操作到
    	void Reserve(SqList &L){
        
    		for(int i = 0 ; i < L.length/2; i++)
    		{
        
    			ElemType temp = L.data[i];
    			L.data[i] = L.data[L.length-1-i];
    			L.data[L.length-1-i]=temp;
    		}
    	}
    //本题需要记住一点是，与前半部分L.data[i]对应的后半部分元素是L.data[L.length-1-i]

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

//这道题刚拿到的时候，我的思路是，遍历一遍，如果当前数是第一个x，就把他和最后一个元素交换，如果是第二个x，就让他和倒数第二个元素交换，也就是双指针
    bool Del_X(sqList &L，ElemType x){
        
    	if(L.length == 0 ) return false;
    	int flag = L.length - 1;//记录需要与x交换的位置
    	int count = 0 ;//记录x的数量
    	for(int i = 0; i < L.Length; i++){
        
    		if(L.data[i]==x){
        
    			ElemType temp = L.data[i];
    			L.data[i] = L.data[flag];
    			L.data[flag] = temp;
    			flag--;
    			count++;
    		}
    	}
    	L.length-=count;//删除后面的元素，后面元素都是x
    	return true;
    }
    
    //但是实际上这种思路是错的，这样的思路虽然在题目要求的时空复杂度之间，但是改变的顺序表的顺序，所以我们看接下来的两种思路

解法一:用k记录顺序表L中不等于x的元素个数（即需要保存到最后的元素的个数），边扫描L边统计k
    并将不等于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++;
    	}
    	L.length = k;//最后只保留k个元素
    }
    就相当于扫描时遇到x就跳过 ，重新给当前这个数组赋一遍值

解法二：用k记录顺序表L中等于x的个数，思路其实和上一个一样，还是扫描一遍数组，重新赋值一遍，遇到x就跳过
    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];//重新给值
    	}
    	L.length-=k;//顺序表减值
    }

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

本题和上一题的区别，因为是有序表，所以删除的元素必然是相连的整体。
    算法思想：先寻找大于等于s的第一个元素（第一个要删除的元素），然后寻找值大于t的第一个元素（最后一个删除的元素的下一个元素），要将这一段删除，只需将后面的元素前移。
    bool Del_s_t(sqList &L,ElemType s,ElemType t){
        
    	int i,j;
    	if(s>=t || L.length==0)		return false;
    	for(i = 0 ;i<L.length&&L.data[i]<s;i++)
    	//循环条件设置为小于s，即当循环结束后，i就是当前需要删除的片段的起始值
    		if(i>=L.length)		return false;//所有元素值均小于s,就返回
    	for(j=i;j<L.length&&L.data[j]<t;j++);//寻找值大于t的第一个元素
    	//接下来只要把j后面的值续到i后面就行了
    	while(j<L.length)
    		L.data[i++] = L.data[j++];//有点归并排序最后合并的内味
    	L.length = i;
    	return true;
    }

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

算法思想：从前向后扫描顺序表L，用K记录下元素值在s和t之间的元素的个数（初始k=0）
    对于当前扫描的元素，若其值不在s和t之间则前移K个位置，和第三题很像
    bool Del_s_t2(sqList &L,ElemType s,ElemType t){
        
    	int i = 0 , k = 0;
    	if(L.length==0&&s>=t)		return false;
    	for(i=0;i<L.length;i++){
        
    		if(L.data[i]>=s&&L.data[i]<=t)
    			k++;
    		else
    			L.data[i-k] = L.data[i];
    	}
    	L.length-=k;
    	return true;
    }

1.  从**有序顺序表**中删除其值重复的元素，使表中的元素的值不相同

第一眼看这个题，我第一反应使，有序表的话，如果一个数等于前一个数，那么就是重复的元素，但是为了提高效率，我们可以放置一个跟随我们移动的小尾巴
    void Del_Same(sqList &L){
        
    	int flag = L.data[0];
    	int k=1;
    	for(int i = 1 ; i< L.length;i++)
    	{
        
    		if(flag != L.data[i])
    		{
        	
    			L.data[k++]=L.data[i];
    			flag = L.data[i];
    		}
    	}
    	L。length = k;
    }

这道题答案的思路是这样的：注意是有序的顺序表，值相同的元素一定在连续的位置上
    用类似直接插入排序的思想，初始时将第一个元素视为非重复的有序表。之后依次判断
    后面的元素是否与前面非重复的有序表的最后一个元素相同，若相同继续向后判断，若
    不同则插入到前面的非重复有虚表的最后，直到判断到表尾为止
    bool Delete_Same(SqList &L){
        
    	if(L.length == 0 )   return false;
    	int i ,j;
    	for(i=0,j=1;j<L.length;j++){
        
    		if(L.data[i]!=L.data[j])
    			L.data[++i]=L.data[j]；
    	}
    	L.length = i+1;
    	return true;
    	//其实和我的思路一模一样，答案写的不直观
    }

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

这道题，如果学过归并排序就知道，就是个Merge函数罢了哈哈,可以看我之前的博客详细介绍了归并排序
    	bool Merge(sqList A, sqList B, sqList &c)//c带值出去
    	{
        
    		if(A.length+B.length>c.Maxsize)		return false;
    		int i=0,j=0,k=0;
    		while(i<A.length&&j<B.length){
        
    			if(A.data[i]<=B.data[j])
    				c.data[k++]=A.data[i];
    			else
    				c.data[k++]=B.data[j];
    		}
    		//还剩一个没有比完的顺序表
    		while(i<A.length)	c.data[k++]=A.data[i++];
    		while(j<B.length)	c.data[k++]=B.data[j++];
    		c.length = k ;//不要忘了给length赋值，这是个整体
    		return true;
    	}

1.  已知在一维数组A\[m+n\]依次存放这两个线性表（a1,a2,a3,…,am）和（b1,b2,b3,…,bn）。试编写程序，将数组中两个顺序表位置互换，即将（b1,b2,b3,…,bn）放在（a1,a2,a3,…,am）的前面

这道题我看到后第一反应就是前m个数和后n个数互换，但是就只能想到这
    参考了一下答案，才发现此题女少口阿
    算法思想：先将数组A[m+n]中的全部元素（a1,a2,...,am,b1,b2,...,bn）原地逆置为（bn,bn-1,...,b1,am,am-1,...,a1）,再对前n个元素和前m个元素分别使用逆置算法，即可得到（b1,b2,...,bn,a1,a2,...,am）,从而实现顺序表的位置互换
    //摘取第二题的resrve算法,思路和第二题一模一样
    void Reverse(int A[],int left, int right, int arrarSize){
        
    	if(left>=right||right>=arraySize)
    		return ;
    	int mid = (left + right)/2;
    	for(int i = 0 ; i < = mid - left; i++){
        
    		int temp = A[left+i];
    		A[left+i]=A[right - i ];
    		a[right - i] = temp;
    	}
    }
    void Exchange(int 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,arrrySize);
    }

1.  线性表（a1,a2,a3,…,an）中的元素递增有虚且按顺序存储于计算机中。要求设计一算法，完成用最少时间在表中查找数值为x的元素，若找到则将其与后继元素位置相交换，若找不到则将其插入表中并使元素仍然有序递增

有序递增的话，最快的查找方法，对于有序来说，肯定是折半查找
    int Search_Exchange_INsert(ElemType A[],ElemType x){
        
    	int low = 0, high = n-1,mid;//low和high指向顺序表下届和上界的下标
    	while(low < high){
        
    		mid = (low + high)/2;//找中间位置
    		if(A[mid] == x) return A[mid];
    		else if (A[mid]<x) low= mid+1;//到中点mid的右半部分去查
    		else high = mid -1;//到点mid的左半部分去查
    	}
    	//两种情况，找到了和没找到
    	if(A[mid]==x&&mid!=n-1)//找到了并且其不是最后一个元素，其有后继元素
    	{
        
    		int t = A[mid];
    		A[mid] = A[mid+1];
    		A[mid+1]=t;
    	}
    	//没找到则插入到表中
    	if(low> high){
        
    		for(int i= n-1; i>high;i--)
    			A[i+1] = A[i];//往high这个位置插入
    		A[i+1]=x;
    	}
    }

1.  （2010年统考真题）设将n个整数存放到一维数组R中。设计一个在时空都尽可能高效的算法、将R中保存的序列循环左移p个位置、即将R中的数据由（X0，X1，…,Xn）转变为（Xp,Xp+1,…,Xn-1,X0,X1,…,Xp-1）

(1).给出算法思想
    (2).根据设计思想，采用C/C++/Java语言描述算法、关键之处给出注释
    (3).说明你所设计算法的时空复杂度
    算法的设计思想：可将这个问题视为把数组ab转换为数组ba，（a代表前p个元素，b代表后n-p个元素）,这个算法我们第8题刚刚讲过，就是先整体逆置，再分别逆置，其实也可以先分别逆置，再整体逆置。
    void Reverse(int R[],int from,int to){
        
    	int i, temp;
    	for(int i =0;i<(to - from +1)/2;i++){
        
    		temp = R[from+i];
    		R[from+i] = R[to-i];
    		R[to-i] = temp;
    	}
    }
    void Converse(int R[],int n,int p){
        
    	Reverse(R,0,p-1);
    	Reverse(R,p,n-1);
    	Reverse(R,0,n-1);
    }
    上述算法中三个Reverse函数的时间复杂度分别是O(p/2)、O((n-p)/2)、O(n/2)，故所设计的算法的时间复杂度为O（n），空间复杂度O（1）
    另外，此题也可以通过辅助数组来实现，算法思想：
    创建大小为p的辅助数组s,将R中前p个整数依次先暂存到S中，完了再把R中的数整体前移，再把S中的数重新放回R就行

1.  （2011年统考真题） 一个长度为L（L>=1）的升序序列S，处在第【L/2】个位置的数称为S的中位数。例如：若序列S1=\{11，13，15，17，19\}，则S1的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=（2，4，6，8，20），则S1和S2的中位数是11.现在有两个等长的升序序列A和B，式设计一个在时间和空间上都尽可能都高效的算法，找出两个序列A和B的中位数，要求：  
    （1）.给出算法的设计思想  
    （2）.根据设计思想，采用C/C++或Java语言描述算法，关键之处给出注释  
    （3）.说明你所设计的算法的时空复杂度

（1）.这道题，思路就是我们之前做过的第7题，难点在于把两个序列合并为一个序列，合并成功后很容易找到中位数
    	但是这种方法有个弊端，就是空间复杂度将会变为O（A.length+B.length）
    	标准答案为：分别求A和B的中位数、设为a和b、求序列A、B的中位数过程如下
    	1.若a=b，即a or 就是中位数、算法结束
    	2.若a<b,则舍弃A中较小的一半和B中较大的一半，要求两次舍弃的长度想等
    	3.若a>b,则舍弃B中较小的一半和A中较大的一半，要求两次舍弃的长度想等
    	在保留的两个升序序列中，重复过程1，2，3，**直到两个序列中均只有一个元素时为止**，较小者即为所求的中位数
    (2).
    int M_Search(int A[],int B[],int n){
        
    	int s1=0,d1=n-1,m1,   s2=0,d2=n-1,m2;
    	//分别表示序列A和B的首位数、末位数和中位数
    	while(s1!=d1||s2!=d2){
        //直到两个序列中均只剩一个元素
    		m1=(s1+d1)/2;
    		m2=(s2+d2)/2;
    		if(A[m1] == B[m2])
    			return A[m1];	//满足条件1
    		if(A[m1]<B[m2])		//满足条件2
    		{
        
    			if((s1+d1)%2==0){
        //若数组长为奇数
    				s1=m1;	//舍弃A中点以前的部分并保留中间点
    				d2=m2;	//舍弃B中点以后的部分并保留中间点							
    			}
    			else//若数组长度为偶数
    			{
        
    				s1= m1+1;
    				d2 =m2;
    			}
    		}
    		else{
        
    			if((s2+dd)%2==0){
        //若数组长为奇数
    				d1=m1;	//舍弃A中点以后的部分并保留中间点
    				s2=m2;	//舍弃B中点以前的部分并保留中间点							
    			}
    			else//若数组长度为偶数
    			{
        
    				d1= m1;
    				s2 =m2+1;
    			}
    		}
    	}
    	return A[s1]<B[s2] ? A[s1]:B[s2];
    }
    （3）算法的时间复杂度为O（nlogn）,空间复杂度为O（1）

1.  （2013统考真题）已知一个整数序列A=（a0,a1,a2,…,am-1）,其中0<=ai<n（0<=i<n）.若存在ap1=ap2=…=apm=x且m>n/2（0<=pk<n,1<=k<=m）,则称x为A的主元素，如A=\{0，5，5，3，5，7，5，5\}则5为主元素，如A=\{0，5，5，3，5，1，5，7\}，则A中没有主元素。假设A中的N个元素保存在一个一维数组中，请设计一个尽可能高效的算法、找出A的主元素。若存在主元素、则输出该元素、否则会输出－１，要求：  
    （1）.给出算法的设计思想  
    （2）.根据设计思想，采用C/C++或Java语言描述算法，关键之处给出注释  
    （3）.说明你所设计的算法的时空复杂度

这尼玛什么主元素，说白了就是出现次数大于n/2，也就是一半以上就是主元素
    也就是相当于找到数组中出现次数最多的元素，然后还得顺便计数，次数大于n/2就算主元素
    int Majority (int A[],int n){
        
    	int i,c,count=1;//c来保存元素，count来计数
    	c=A[0];//刚开始A【0】是候选元素
    	for(i = 1;i<n;i++)//查找候选主元素
    		if(A[i]==c)
    			count++;//对A中的主元素计数
    		else	
    			if(count>0)
    				count--;//处理不是主元素的情况
    			else{
        
    				c=A[i];
    				count=1;//更换主元素，重新计数
    			}
    	//整个上面一大片，其实都是在找出现次数最多的元素，下面是计数
    	if(count>0)
    		for(i = count = 0;i<n;i++)
    			if(A[i]==c)
    				count++;
    	if(count>n/2) return c;
    	else return -1;
    	
    }
    时间复杂度o(n)，空间o(1)
    这道题其实最简单的是去排序再统计，是最好匹配的，虽然时间复杂度得【ologn】，但是只要正确，也能拿11分，不要花费太多时间在难题上

13.（２０１８统考真题）给定一个含ｎ个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小整肃，例如，｛－５，３，２，３｝中未出现的最小正整数是１，数组｛１，２，３｝中未出现的最小正整数为４.要求：  
（1）.给出算法的设计思想  
（2）.根据设计思想，采用C/C++或Java语言描述算法，关键之处给出注释  
（3）.说明你所设计的算法的时空复杂度

（１）。要求时间上尽可能高效，因此采用空间换时间的算法。
    分配一个用于标记的数组B【】，用来记录A中是否出现了１～ｎ中的正整数，B【０】对应的
    正整数１，B［ｎ－１］对应的是正整数ｎ，初始化B全为【０】.由于A中含有ｎ个整数，因此
    可能返回的值是１～ｎ，当A中n个数恰好为1~n时返回n+1，当数组A中出现小于等于0或者大于n的
    值时，会导致B中1~n出现空余位置，返回结果必然在1~n中
    	经过上述分析可以得到算法流程：从A【0】开始遍历A，若A【i】在1~N之间，则令
    	B【A【i】-1】=1;否则不做操作，对A遍历结束后，开始遍历数组B，若能查到第一个满足
    	B【i】==0的下标i，返回i+1即可，此时说明A中未出现的最小正整数在1~N中。若B【i】
    	全不为0,返回i+1(跳出循环时i=n，i+1等于n+1),此时说明A中未出现的最小正整数是n+1
    int findMissMin(int A[],int n){
        
    	int i,*B;//标记数组
    	B= (int *)malloc(sizeof(int)*n);//分配空间
    	memset(B,0,sizeof(int)*n);
    	for(i=0;i<n;i++)
    		if(A[i]>0&&a[i]<=n)
    			B[A[i]-1]=1;//若A【i】介于1~n，则标记数组B
    	for(i = 0 ;i<n;i++)
    		if(B[i]==0)	break;//扫描数组B，找到目标值
    	return i+1;
    
    时间复杂度，遍历A，B各一次，也就是O（n），空间复杂度O（n）;
    }