【23考研】408代码题参考模板——顺序表

标红色的为必须掌握
有多个模板的只要掌握一种即可。

顺序表（数组）

对于顺序表，一般情况下如果不是题目要求，则不需要使用结构体包起来，直接使用数组就行
传参时只需传一个数组名，一个数组中元素个数就行了

void f(int A[],int n){
    
	
} 

数组中任意位置插入一个元素

模板1

void insert(int a[],int &n,int idx,int value){
    
	//在数组a的idx处（idx为下标）插入值为value的元素
	//n为数组中元素的个数，使用引用是因为数组中插入元素后元素个数增加 
	
	//将原来及idx以后的元素后移，腾出idx位置 
	for(int i=n;i>idx;i--){
    
		a[i]=a[i-1];
	}
	
	a[idx]=value;//在idx处放入需要插入的元素value 
	
	n++;//数组中元素个数增加 
} 

模板2

void insert(int a[],int &n,int idx,int value){
    
	//在数组a的idx处（idx为下标）插入值为value的元素
	//n为数组中元素的个数，使用引用是因为数组中插入元素后元素个数增加
	
	//将原来及idx以后的元素后移，腾出idx位置 
	int i=n;
	while(i>idx){
    
		a[i]=a[i-1];
		i--;
	}
	
	a[idx]=value;//在idx处放入需要插入的元素value 
	
	n++;//数组中元素个数增加
} 

数组中任意位置删除一个元素

void del(int a[],int &n,int idx){
    
	//删除数组a的idx处（idx为下标）的元素 
	//n为数组中元素的个数，使用引用是因为数组中删除元素后元素个数减小 
	
	//将后面元素前移，idx位置的元素直接覆盖掉就行了 
	for(int i=idx;i<n-1;i++){
    
		a[i]=a[i+1];
	} 
	
	n--;//数组a中元素减少一个 
} 

数组中查找元素（顺序查找）

int find(int a[],int n,int value){
    
	//在数组a中查找值为value元素的位置，没找到返回-1
	
	//遍历整个数组 
	for(int i=0;i<n;i++){
    
		if(a[i]==value){
    
			//找到了，将该位置返回 
			return i;
		}
	} 
	
	return -1;//没找到 
}

数组中元素逆置

void reverse(int a[],int left,int right){
    
	//将数组a中的[left,right]部分元素逆置 
	int i=left,j=right;//一头一尾，采用双指针法 
	while(i<j){
    
		swap(a[i],a[j]); //将i和j指向的元素进行交换 
		i++; //i指针后移 
		j--; //j指针前移 
	} 
} 

两个有序数组合并

int* merge(int a[],int n,int b[],int m){
    
	//合并有序数组a,b 
	int i=0,j=0,k=0;//i用于遍历数组a，j用于遍历数组b，k用于表示数组c中元素该插入的位置 
	int *c=new int[n+m];//存放到新的数组中 
	
	while(i<n&&j<m){
    
		//两个数组都还没遍历完 
		if(a[i]<=b[j]){
    
			//如果i指向a数组中的元素小于等于j指向b数组中的元素
			//则将i指向的元素放入c数组中，并且i指针后移 
			c[k++]=a[i++];
		}
		else{
    
			//反之则将j指向的元素放入c数组中，并且j指针后移 
			c[k++]=b[j++];
		}
	}
	 
	while(i<n){
    
		//如果数组a中还有元素没遍历完 
		c[k++]=a[i++];
	}
	
	while(j<m){
    
		//如果数组b中还有元素没遍历完 
		c[k++]=b[j++];
	}
	
	return c;//将该数组返回 
} 

二分查找

int binary_search(int a[],int n,int key){
    
	//对数组a进行二分查找
	//若找到，则返回元素的下标
	//若未找到，则返回-1
	
	int low=0,high=n-1;
	while(low<=high){
    
		int mid=(low+high)/2;//中间位置 
		if(a[mid]==key){
    
			//找到了
			return mid; 
		}
		else if(a[mid]>key){
    
			//中间位置大于key，则说明key可能在左半段 
			high=mid-1;
		}
		else if(a[mid]<key){
    
			//中间位置小于key，则说明key可能在右半段
			low=mid+1;
		}
	}
	return -1; //没找到 
} 

lower_bound

int lower_bound(int a[],int n,int key){
    
	//二分查找，要求数组A中元素升序 
	//若数组A中存在值为key的元素，则返回该元素的下标
	//若数组A中不存在值为key的元素，则返回第一个大于该元素的下标
	//若数组A中所有元素均小于key，则返回数组元素个数
	int low=0,high=n-1;
	while(low<=high){
    
		int mid=(low+high)/2;
		if(a[mid]==key){
    
			return mid;
		}
		else if(a[mid]>key){
    
			high=mid-1;
		}
		else if(a[mid]<key){
    
			low=mid+1;
		}
	}
	return low;
} 

冒泡排序

void bubblesort(int a[],int n){
    
	//冒泡排序 
	//将值大的元素往后面冒泡 
	for(int i=0;i<n-1;i++){
    
		//每一轮冒泡确定一个元素的位置 
		for(int j=0;j<n-i-1;j++){
    
			//如果当前值比后面的大，则交换两个数 
			if(a[j]>a[j+1]){
    
				swap(a[j],a[j+1]);
			}	
		}
	}
}

选择排序

void selectionsort(int a[],int n){
    
	//选择排序 
	for(int i=0;i<n;i++){
    
		//找后面还没完成排序中的最小的元素位置 
		int index=i;//最小元素的下标 
		for(int j=i+1;j<n;j++){
    
			if(a[j]<a[index]){
    
				index=j;//更新最小值的下标 
			}
		}
		swap(a[i],a[index]);//将最小值换到前面 
	}
}

快速排序

void quicksort(int a[],int left,int right){
    
	//快速排序，时间复杂度是O(nlogn),空间复杂度是O(logn) 
	if(left>=right){
    
		//递归终止条件 
		return ;
	}
		
	int i=left,j=right;
	int temp=a[left];//基准元素，这里不用考虑优化 
	while(i<j){
    
		while(i<j&&a[j]>=temp){
    
			//j从后面往前移，直到找到小于基准的 
			j--;
		}
		while(i<j&&a[i]<=temp){
    
			//i从前面往后移，直到找到大于基准的 
			i++;
		}
			
		swap(a[i],a[j]);//交换i和j所指向的元素 
	}
	swap(a[left],a[i]);//将基准元素放到中间 
	quicksort(a,left,i-1);//递归对左半段进行排序 
	quicksort(a,i+1,right);//递归对右半段进行排序 
}