【算法3】【数据结构】删除顺序表中数值为 x的元素

需要注意的点:

1)顺序表未必有序
2)memset函数可以有效清空数组,效率是循环赋值清空的近百倍。
3)memset函数 使用引用string.h头文件

1)相对有点抽象的方法

》算法思想:

假设 表中存取的元素分别为 1,2,3,x,x,6,x,5
可以定义一个int i 来遍历整个顺序表,定义一个int k来记录值为x的元素个数。
当a[i]==x时,k++,i++
当a[i]!=x时,i++,并且将a[i]左移k个单位,也就是覆盖掉值为x的元素:a[i-k]=a[i]。
最后当i遍历完整个顺序表的时候,就可以将a[i]之后的元素均置0清空

》算法设计如下:

//函数名称:Delete_X
//函数功能:删除顺序表(顺序存储)中值为x的元素
//函数参数:a[]:待处理数组(顺序表),x:选择删除顺序表中值为x的元素,len:数组(顺序表)长
void Delete_X(int a[],int x,int len)
{
	int k=0;//用于记录i从a[i]!=x到下一个a[i]!=x之间有多少个值为x的元素
	int i=0;
	while(i<len)
	{
		if(a[i]==x)
		{
			k++;i++;
		}
		else
		{
			a[i-k]=a[i];//用a[i]上的元素左移k个单位覆盖掉值为x的元素
			i++;
		}
	}
	memset(a+len-k,0,sizeof(a[0])*k);//将最后一个非x元素之后的元素置空
	//也可以使用相对简单的清空方式:
	/*for(i=0;i<k;i++)
	{
		a[len-k+i]=0;
	}*/
}

整体代码实现:

#include <stdio.h>
#include <string.h>


void Delete_x(int a[],int x,int len)
{
	int i=0;//定义i用于控制遍历顺序表a
	int k=0;//用于记录值为x元素个数,方便移动
	while(i<len)
	{
		if(a[i]==x)
		{
			k++;
			i++;
		}
		else
		{
			a[i-k]=a[i];//将a[i]往前移动k个位置
			i++;
		}
	}
	
	memset(a+len-k,0,sizeof(a[0])*k);
	/*for(i=0;i<k;i++)
	{
		a[len-k+i]=0;
	}*/

}


int main()
{
	int a[]={1,2,3,4,4,6,4,5};
	int len=sizeof(a)/sizeof(a[0]);//求表长
	int i=0;
	//查看作用前元素值
	for(i=0;i<len;++i)
	{
		printf("%d\t",a[i]);
	}
	printf("\n");
	Delete_x(a,4,len);//假设要删除元素值为4的结点
	//查看作用后元素值
	for(i=0;i<len;++i)
	{
		printf("%d\t",a[i]);
	}
	printf("\n");
	return 0;
}

运行结果:

【算法3】【数据结构】删除顺序表中数值为 x的元素

2)相对好理解的方法

》算法思想:

假设 表中存取的元素分别为 1,2,3,x,x,6,x,5
可以定义一个int i 来遍历整个顺序表,定义一个int k来保存元素值不是x 的元素
遍历后留下的长度为k的表即为有效表,后面的直接置空就好了。

》算法设计如下:

void Delete_X(int a[],int x,int len)
{
	int i=0;//用来遍历顺序表
	int k=0;//用来保存元素值非x的元素
	for(i=0;i<len;++i)
	{
		if(a[i]!=x)
		{
			a[k}=a[i];
			k++;
		}
  }
  memset(a+k,0,sizeof(a[0])*(len-k));
}

实现代码:

#include <stdio.h>
#include <string.h>


/*void Delete_x(int a[],int x,int len)
{
	int i=0;//定义i用于控制遍历顺序表a
	int k=0;//用于记录值为x元素个数,方便移动
	while(i<len)
	{
		if(a[i]==x)
		{
			k++;
			i++;
		}
		else
		{
			a[i-k]=a[i];//将a[i]往前移动k个位置
			i++;
		}
	}
	
	//memset(a+len-k,0,sizeof(a[0])*k);
	for(i=0;i<k;i++)
	{
		a[len-k+i]=0;
	}

}*/


void Delete_X(int a[],int x,int len)
{
	int i=0;//用来遍历顺序表
	int k=0;//用来保存元素值非x的元素
	for(i=0;i<len;++i)
	{
		if(a[i]!=x)
		{
			a[k]=a[i];
			k++;
		}
  }
  memset(a+k,0,sizeof(a[0])*(len-k));
}

int main()
{
	int a[]={1,2,3,4,4,6,4,5};
	int len=sizeof(a)/sizeof(a[0]);
	int i=0;
	for(i=0;i<len;++i)
	{
		printf("%d\t",a[i]);
	}
	printf("\n");
	Delete_X(a,4,len);//X大写
	for(i=0;i<len;++i)
	{
		printf("%d\t",a[i]);
	}
	printf("\n");
	return 0;
}

运行结果:

【算法3】【数据结构】删除顺序表中数值为 x的元素

上一篇:Redis 宝典 | 基础、高级特性与性能调优


下一篇:java 红包案例 不是最好方案 添加成员需要new 还得调收红包的方法 不调不会收