数据结构算法练习1——顺序表

迈不过友情╰ 2023-02-24 08:18 70阅读 0赞

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

思想：遍历顺序表，找到最小值的位置，将末尾元素保存到此次，删除末尾元素

bool Del_Min(sqList &L,ElemType &value){
    	if(L.length==0)//如果表为空，直接返回 
    	return false;
    	value=L.data[0];//value用来记录最小值 
    	int flag=0;//flag用来记录数据的位置 
    	for(int i=0;i<L.length;i++){
    		if(L.data[i]<value){
    			value=L.data[i];//得到最小值 
    			flag=i;//得到最小值的位置 
    		}
    	}
    	L.data[flag]=L.data[length-1];//把最后一个元素存到最小值元素的位置 
    	L.length--; 
    	return true;
    }

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

思想：扫描半个表将前半部分和后半部分进行交换

void Reverse(sqLit &L){
    	ElemType temp;//辅助变量 
    	for(int i=0;i<L.length/2;i++){
    		temp=L.data[i];
    		L.data[i]=L.data[L.length-1];//将对应元素进行交换 
    		L.data[L.length-1]=temp;
    	}
    }

3.长度为N的顺序表L，编写时间复杂度为O(n),空间复杂度为O(1)，该算法删除链表中所有值为X的元素。

思想：用k记录值不为x的元素个数，一边扫描表，一边记录k值，将值不为x的元素向前放置在k的位置上。无重复是，k++,i++,有重复时只有i++.

void del_x(sqList &L,ElemType x){
    	int k=0;//记录值不等于x值元素的个数
    	for(int i=0;i<L.length;i++){
    		if(L.data[i]!=x){
    			L.data[k]=L.data[i]; 
    			k++;
    		}
    	} 
    	L.length=k;
    }

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

思想：找出值大于s和值大于t的第一个元素flag1,flag2.将后面的元素前移flag2-flag1个位置。

bool Del_s_t(Sqlist &L,ElemType s,ElemType t){
    	int count=0;
    	int flag1=-1;int flag2=-1;
    	if(s>=t||L.length==0){
    		printf("链表为空，或s,t输入错误");
    		return false; 
    	}
    	for(int i=0;i<L.length;i++){ 
    		if(L.data[i]>s&count==0){//找到大于s的第一个元素 
    			flag1=i;
    			count++;
    		}
    		if(L.data[i]>t&count==1){//找到大于t的第一个元素,跳出循环 
    			flag2=i;
    			count++;
    			break;
    		} 
    	}
    	if(flag1==-1){
    		printf("s大于链表中的所有元素！");
    		retuen false;
    	}
    	int sub=flag2-flag1;
    	for(int i=flag1;i<leangth;i++){
    		L.data[i]=L.data[i+sub];//将元素删除，后面的元素迁移 
    	}
    	L.length=L.ength-sub; 
    }

5.从无序链表中删除s到t之间的数

思想：将小于s和大于t的元素，筛选出来添加进新的表

bool Del_s_t2(Sqlist &L,ElemType s,ElemType t){
    	sqList L1;//用来暂存链表中的数据
    	int k=0; 
    	if(L.length==0||s>=t){
    		printf("链表为空,或者s与t输入错误"); 
    		return false;
    	}
    	for(int i=0;i<L.length;i++){
    		if(L.data[i]<=s||L.data[i]>=t){
    			L1.data[k]=L.data[i];//将链表L中不再s~t中的数据存到L1中 
    			k++;
    		}
    	}
    	L=L1; 
    	return true; 
    }

6.从有序表中删除，所有值重复的元素，使得无重复值  
思想：因为是有序表，所以值相同的元素一定在连续的位置上。判断后面的元素值是否与前面的元素值相等，如果相等，将后面的元素前移，两个元素合并成一个元素。

bool delete_same(sqList &L){
        if(L.lenfth==0)
        reruen false;
        int i,j;
        for(i=0;j=1;j<L.length;j++){
              if(L.data[i]!=L.data[j]){//查找下一个元素，与上一个元素值不同的元素 
                  L.data[i++]=data[j];//找到后将元素前移 
              }
        }
        L.length=i+1;//所有前移元素将前面相同的元素覆盖后，改变表长，移动的元素消去 
        return true;
    }

7.将两个有序顺序表合为一个合并成一个有序表，返回合并后的表  
思想：按顺序比较表头值，将较小的存入新表，最后看哪个表有剩余，将剩余的部分加的新表后面

bool Merge(Sqlist &A,Sqlist &B,Sqlist &C){
        if(A.length+B.length>MaxSize){
        //如果两个表长度之和大于链表空间最大长度，直接返回false 
            return false;
        }
        int i=0,j=0,k=0;
        while(i<A.length&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++]=A.data[j++];
        C.length=k+1;
        return true;
    }

8.已知一个一位数组中A\[M+N\]，依次存放着两个线性表(a1,a2,,,am),(b1,b2,,,bn).编写一个函数将数组中的两个顺序表位置互换

思想：将（a1,a1...am,b1,b2,,,bn）逆置换——》（bn...b2,b1,am,,,,a2,a1）——》前n个逆置换，后m个逆置换

typedef int DataType;
    //函数1将任意数组进行逆序 
    void Reverse(DataType A[],int left,int right,int arraySize){
    	if(left>right||right>arraySize){
    		return false;
    	}
    	int mid=(left+right)/2;
    	for(int i=0;i<=mid-left;i++){//将(a1,a2,,,am),(b1,b2,,,bn)进行逆序 
    		DateType temp=A[left+i];
    		A[left+i]=A[right-i];
    		A[right-i]=temp;
    	}
    } 
    //函数2调用函数1解题 
    void Exchenge(Date A[],int m,int n,int arraySizes){
    	Reverse(A,0,m+n-1,arraySize); 
    	Reverse(A,0,n-1,arraySize); 
    	Reverse(A,n,m+n-1,arraySize); 
    }

9，线性表（a1,a2,,,an）中的元素递增有序地存在计算机内，要求设计一个算法完成最少时间在表中查找值为x的元素，如果找到与其后继元素位置交换。如果找不到将其插入表中使得表仍然递增有序。

思想：因为要求最短时间所以用折半查找。

void SearchExchangeInsert(ElemType A[],EleamType x){
    	int low=0,high=n-1,mid;
    	int temp;
    	while(low<high){
    		mid=(low+high)/2;
    		if(A[mid]==x) break;//找到x退出循环 
    		else if(A[mid]<x) low=mid+1;//到中点右边查询 
    		else high=mid-1;//到中点左边查询 
    	}//下面的两个if只会执行一个
    	if(A[mid]==x&&mid!=n-1){//查询到x,并且不是最后一个元素进行后继节点间的交换 
    		temp=A[mid];
    		A[mid]=A[mid+1];
    		A[mid+1]=temp;
    	} 
    	if(low>high){//查找失败，插入x 
    		int i;
    		for(i=n-1;i>high;i--){//x在low和high所对应值之间，所以将high的值后移,插入x 
    			A[i+1]=A[i];
    		}
    		A[i+1]=x; 
    	} 
    }