数据结构——顺序表（基础代码题）

一、顺序表

1.对顺序表L 进行遍历并输出每个数据元素的数据值。

​ (改变结构就用引用，简单的就用值传递)

void ListVisit(SqList L){
	for (int k=0;k<L.length;k++)
		printf("%d",L.data[k]);
}

2.假设有一个顺序表i，其存储的所有数据元素均为不重复的正数，查找L 中值为e的数据元素，若找到则返回其下标，若找不到则返回-1。

int Search_e(SqList L,int e){
	for(int k=0;k<L.length;k++)
		if(L.data[k]==e)
			return k;
	return -1;
}

3.假设有一个顺序表L，其存储的所有数据元素均为正数，查找L中第i个数据元素并返回其值。

int Get_i(SqList L,int i){
	if(i>=1&&i<L.length)
		return L.data[i-1];
	return -1;		//范围越界
}

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

 void Reverse(SqList &L){  //由1234改变成4321结构发生变化，使用引用符
 	int temp;
 	for(int i=0;i<L.length/2;i++)   {
 	//length/2=2.5计算机会自动抹去0.5
 		temp=L.data[i];
 		L.data[i]=L.data[L.length-i-1];
 		L.data[L.length-i-1]=temp;
 	}
 }

5.在顺序表L的第i个位置插入新元素e，若i的输入不合法，则返回false，表示插入失败；否则，将第i个元素及其后的所有元素依次往后移动一个位置，腾出一个空位置插入新元素e，顺序表长度增加1，插入成功，返回true。

bool Insert_e(SqList &L, int e,int i){
	//合法性判断
	if(i<1||i>L.length+1)
		return false;
	//顺序表存满判断
	if(L.length==MaxSize)
		return false;
	for(int j=L.length;j>=i;j--)
		L.data[j]=L.data[i-1];
	L.data[i-1]=e; //第i个位置的下标要-1
	L.length++;
	return true;
}

6.已知一个顺序表L，其中的元素递增有序排列，设计一个算法，插入一个元素X（X为int型）后保持该顺序表仍然递增有序排列，假设插入操作肯定成功，插入成功后返回插入元素所在位置。

//假设插入操作肯定成功，则不需要情况判断
int ListInsert(SqList &L,int x){
	for(int i) //i因为要返回数值，故不能在for循环里定义，因为for循环完之后会自动消失，所以要把i定义在循环之外
	int i;
	for(i=0;i<L.length;i++)
		if(L.data[i]>x)
			break;//得到插入元素的位置
	for(int j=L.length;j>=i+1;j--)
		L.data[j]=L.data[j-1];
	L.data[i]=x; //插入元素
	L.length++;
	return i;
}

![外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传](https://img-home.csdnimg.cn/images/20230724024159.png?origin_url=C%3A%5CUsers%5CASUS%5CDesktop%5CSnipaste_2024-09-20_14-54-46.png&pos_id=img-lM1CUEjw-1727575705002

7.删除顺序表L 中第i 个位置的元素，若i的输入不合法，则返回false；否则将被删元素赋给引用变量e，并将第i+1个元素及其后的所有元素依次往前移动一个位置，返回true。

 //输入合法:i(下标在0到顺序表长度之间)
 bool ListDelete(SqList &L,int i,int &e){
 	if(i<1||i>L.length)  //不合法判断
 		return false;
 	e=L.data[i-1];  //被删除的元素赋值给变量e
 	for(int j=i;j<L.length;j++)
 		L.data[j-1]=L.data[j]; //将之后的元素依次往前移动
 	L.length--;
 	return true;
 }

8.从顺序表中删除具有最小值的元素并由函数返回被删元素的值。（假设顺序表中的数据元素全为正值且最小值唯一）。

int Delete_Min(SqList &L){
	if(L.length==0)
		return -1;	//空表，出现错误
	int min=L.data[0],pos=0;
	for(int i=1;i<L.length;i++)
		if(L.data[i]<min){
			min=L.data[i];
			pos=i;
			//找到顺序表中的最小值
		}
	for(int j=pos;j<L.length-1;j++)
		L.data[j]=L.data[j+1];
		//前移表中的数据元素
	L.length--;	 //顺序表长度减一
	return min; //返回最小值
}

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

//方法一
void Delete_x_1(SqList &L,int x){
	int k=0; // 定义删除x的个数
	for(int i=0;i<L.length;i++){
		if(L.data[i]==x)
			k++;
		else
			L.data[i-k]=L.data[i];
	}
	L.length=L.length-k;
}
//方法二
void Delete_x_1(SqList &L,int x){
	int j=0;
	for(int i=0;i<L.length;i++){
		if(L.data[i]!=x){
			L.data[j]=L.data[i];
			j++;
		}
	}
	L.length=j;
}

10.从顺序表中删除其值在给定值s与t之间（包含s和t，要求s<t）的所有元素，若s或t不合理或顺序表为空，则返回false，若执行成功则返回true。

//方法一
bool Del_s_t_1(SqList &L,int s ,int t){
	if(s>=t||L.length==0)
		return false;
	int k=0;
	for(int 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=L.length-k;
	return true;
}
//方法二
bool Del_s_t_2(SqList &L,int s ,int t){
    if(s>=t||L.length==0)
            return false;
    int j=0;
    for(int i=0;i<L.length;i++){
    	if(L.data[i]<s||L.data[i]>t){  //判断元素是否保留
    		L.data[j]=L.data[i];
    		j++;
    	}
    }
    L.length=j;
    return true;		
}

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

void Del_Same(SqList &L){
	int j=1; //定义一个变量作为保留元素的位置，判断元素保留不保留要求从第二个元素进行比较，下标为0的元素肯定保留
	for(int i=1;i<L.length;i++)
		if(L.data[i]!=L.data[j-1]){
			L.data[j]=L.data[i];
			j++;
		}
	L.length=j;
}

12.从【有序】顺序表中删除其值在给定值s与t之间（包含s和t，要求s<t）的所有元素，若s或t不合理或顺序表为空，则返回false，执行成功则返回true。

难题

//自己写的，不是太正确
bool Delete_s_t(SqList &L,int s,int t){
	if(s>=t||L.length==0)
		return false;
	int k=0;
	for(int i=0;i<L.length;i++){
		if(L.data[i]>=s&&L.data[i]<=t)
			k++;	
			L.data[i-k]=L.data[i];
	}
	L.length=L.length-k;
	return true;
}
//正确答案P20，解题思路：连续的空间，给出一个排队的位置（需要删除的元素的位置），看看哪些元素需要保留，然后在排队位置上进行保留，然后更新排队位置。
bool Delete_s_t(SqList &L,int s,int t){
	if(s>=t||L.length==0)
		return false;
	int i,j;
	for(j=0;j<L.length&&L.data[j]<s;j++);//找出大于s元素的位置
	if(j=L.length)
		return false;
	for(i=j;i<L.length&&L.data[i]<=t;j++);//找到小于t元素的位置
	for(;i<L.length;i++,j++) //循环顺序表
		L.data[j]=L.data[i];  
	L.length=j;
	return true;
}

13.将两个有序顺序表A和B合并为一个新的有序顺序表C，若合并成功则返回true，合并失败则返回false。

 bool Merge(SqList A,SqList B,SqList &C){
 	if(A.length+B.length>C.Maxsize)
 		return false;  //判断顺序表A和B的长度没有超过C的
 	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];
 			k++;
 			i++;
 		}
 		else{
 			C.data[k]=B.data[j];
 			k++;
 			j++;
 		}		
 	}
 	//存在一个表有剩余
 	while(i<A.length){
 		C.data[k]=A.data[i];
 		k++;
 		i++;
 	}
 	while(i<A.length){
 		C.data[k]=B.data[j];
 		k++;
 		j++;
 	}
 	C.length=k;
 	return true;
 }