将顺序表中非零元素移动到顺序表的前面

一、问题引入

已知长度为n的线性表A采用顺序存储结构，编写算法将A中所有的非零元素依次移到线性表A的前端

二、分析

直接用两个for循环解决(时间复杂度可能高了点)，每查找到一个为0的位置，都在当前位置后面寻找到第一个非零元素的位置，这两个位置的元素值交换即可。

三、核心代码:

#define  MaxSize 50  //表长度的初始定义
typedef struct{
	ElemType data[MaxSize]; //顺序表的元素
	int length;            //顺序表的当前长度
}SqList;               //顺 序表的类型定义

//将顺序表中的非零元素移动到顺序表的前端
void MoveList(SqList &L)
{
	for(int i=0;i<L.length;i++)
	{
		if(L.data[i]==0)
		{
			for(int j=i+1;j<L.length;j++)
			{
				if(L.data[j]!=0)
				{
					int temp=L.data[i];
					L.data[i]=L.data[j];
					L.data[j]=temp;
					break;//跳出最近的这层for循环，防止后面的非零元素继续交换
				}
			}
		}
	}
}

四、完整代码

list.h

#define  MaxSize 50  //表长度的初始定义
typedef struct{
	ElemType data[MaxSize]; //顺序表的元素
	int length;            //顺序表的当前长度
}SqList;               //顺 序表的类型定义
//初始化
int Initiate(SqList &L)
{
	L.length=0;
	return 1;
}
//插入函数
bool ListInsert(SqList &L,int i,ElemType e){  
    if(i<1||i>L.length+1)
		return false;
	else if(L.length>=MaxSize)
		return false;
    else
	{
		for(int j=L.length;j>=i;j--)
			L.data[j]=L.data[j-1];
			L.data[i-1]=e;
		L.length++;
		return true;
	}
}
//删除函数
bool ListDelete(SqList &L,int i,ElemType e)
{
	if(i<1||i>L.length)
		return false;
	e=L.data[i-1];
	for(int j=i;j<L.length;j++)
		L.data[j-1]=L.data[j];
	L.length--;
	return true;
}
//按值查找
int LocateElem(SqList L,ElemType e)
{
	int i;
	for(i=0;i<L.length;i++)
	{
		if(L.data[i]==e)
		{
			return i+1;   //下标为i的元素值等于e，返回其位序i+1
		}
	}
	return 0;   //退出循环，说明查找失败
}
//取出第i个元素
int ListGet(SqList &L,int i,ElemType *x)
{
	if(i<0||i>L.length-1)
	{
		printf("参数不合法");
		return 0;
	}
	else
	{
		*x=L.data[i];
		return 1;
	}
}
bool Deletes_t(SqList &L,ElemType s,ElemType t)
{
	//删除有序顺序表L中值在s和t之间的所有元素
	int i,j;
	if(s>=t||L.length==0)
	{
		return false;
	}
	for(i=0;i<L.length&&L.data[i]<s;i++);//寻找值大于等于s的第一个元素
	if(i>=L.length)
		return false;
	for(j=i;j<L.length&&L.data[j]<=t;j++);//寻找值大于t的第一个元素
	for(;j<L.length;i++,j++)
	{
		L.data[i]=L.data[j];
	}
	L.length=i;
	return true;
}
//将顺序表中的非零元素移动到顺序表的前端
void MoveList(SqList &L)
{
	for(int i=0;i<L.length;i++)
	{
		if(L.data[i]==0)
		{
			for(int j=i+1;j<L.length;j++)
			{
				if(L.data[j]!=0)
				{
					int temp=L.data[i];
					L.data[i]=L.data[j];
					L.data[j]=temp;
					break;//跳出最近的这层for循环，防止后面的非零元素继续交换
				}
			}
		}
	}
}

test.cpp

#include<stdio.h>
typedef int ElemType;
#include"list.h"
int main()
{
 SqList mylist;
 int x;
 Initiate(mylist);
 /*for(int i=1;i<11;i++)
 {
	ListInsert(mylist,i,i);
 }*/
 ListInsert(mylist,0,0);
 ListInsert(mylist,1,1);
  ListInsert(mylist,2,0);
   ListInsert(mylist,3,2);
    ListInsert(mylist,4,0);
	 ListInsert(mylist,5,3);
//输出顺序表中的所有元素
 for(int i=0;i<mylist.length;i++)
 {
    ListGet(mylist,i,&x);
	printf("%d ",x);
 }

 MoveList(mylist);
printf("移动之后:\n");
//输出顺序表中的所有元素
 for(i=0;i<mylist.length;i++)
 {
    ListGet(mylist,i,&x);
	printf("%d ",x);
 }
 return 0;
}

五、运行结果