算法设计题

问题描述

        10.已知长度为n的线性表A采用顺序存储结构，请写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法可删除线性表中所有值为item的数据元素。

算法分析

        此题的关键点在于：在时间复杂度为O(n)、空间复杂度为O(1)条件的限定下，不能另外开辟空间，且只能通过遍历一趟顺序表来完成。

算法步骤

        1.用k值记录不等于item的元素个数，k初始为0。 
        2.从前向后扫描顺序表，查找值不为item的元素。
        3.如果找到，利用原表的空间记录值不为item的元素。 
        4.遍历结束后，顺序表中前k个元素即为值不为item的元素。 

算法描述

        主要代码

void DeleteItem(SqList &L,int item)
{
	//删除线性表L中所有值为item的数据元素
	int k=0;	//k值记录不等于item的元素个数
	for(int i=0;i<L.length;i++)	//从前向后扫描顺序表 
	{
	
		if(L.elem[i] != item)	//查找值不为item的元素 
		{
			L.elem[k]=L.elem[i];//利用原表的空间记录值不为item的元素 
			k++; 			//不等于item的元素增1 
		} 
	}
	L.length=k;			//顺序表L的长度等于k 
 } 

        完整代码

//******************************数据结构-第二章线性表-算法设计题10******************************// 
#include<stdio.h>
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef int Status;
//------顺序表的存储结构------//
#define MAXSIZE 100     //顺序表可能达到的最大长度
typedef struct
{
	ElemType *elem;    //或ElemType elem[MAXSIZE]  存储空间的基地址  
	int length;	 //当前长度 
}SqList;         //顺序表的结构类型为SqList 


//------顺序表的初始化------//
 //-----【算法步骤】 -----// 
  //1.为顺序表 L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址。
  //2.将表的当前长度设为0。
bool InitList(SqList &L)
{
	//构造一个空的顺序表L
	L.elem=new int[MAXSIZE];     //为顺序表分配一个大小为MAXSIZE的数组空间 
	if(!L.elem)	return false;   //存储分配失败退出 
	L.length=0;                 //空表长度为0 
	return true; 
}

//------顺序表初始化前n个数据------//
bool CreateList(SqList &L,int n) 
{
	if(n<0||n>MAXSIZE) return false; //n值不合法
	for(int i=0; i<n; i++){
		scanf("%d",&L.elem[i]);
		L.length++;
	} 
	return true;
}

//------删除线性表中所有值为item的数据元素------//
  //-----算法步骤-----//
  //1.用k值记录不等于item的元素个数，k初始为0。 
  //2.从前向后扫描顺序表，查找值不为item的元素。
  //3.如果找到，利用原表的空间记录值不为item的元素。 
  //4.遍历结束后，顺序表中前k个元素即为值不为item的元素。 
void DeleteItem(SqList &L,int item)
{
	//删除线性表L中所有值为item的数据元素
	int k=0;	//k值记录不等于item的元素个数
	for(int i=0;i<L.length;i++)	//从前向后扫描顺序表 
	{
	
		if(L.elem[i] != item)	//查找值不为item的元素 
		{
			L.elem[k]=L.elem[i];//利用原表的空间记录值不为item的元素 
			k++; 			//不等于item的元素增1 
		} 
	}
	L.length=k;			//顺序表L的长度等于k 
 } 
//------输出打印顺序表  按位置从小到大输出顺序表所有元素------//
void PrintList(SqList L)
{
	printf("当前顺序表中所有元素为：");
	for(int i=0; i<L.length; i++)
	{
		printf("%d ",L.elem[i]);
	}
	printf("\n");
 } 

//------创建顺序表函数------//
void Create(SqList &L) 
{
	int n;
	bool flag;
	L.length=0;
	printf("请输入要创建的顺序表的长度：");
	scanf("%d",&n);
	printf("请输入依次输入%d个数（空格隔开）：",n);
	flag=CreateList(L,n);
	if(flag){
		printf("顺序表L创建成功！\n");
		PrintList(L);
	}
	else
		printf("输入长度不合法！\n"); 
}

//------删除线性表L中所有值为item的数据元素------//
void Delete(SqList &L,int item)
{
	
	printf("请输入要删除的item的值为：");
	scanf("%d",&item);
	DeleteItem(L,item);
	printf("删除元素%d成功！\n",item);
	PrintList(L);
}

//------创建主函数------//
int main()
{
	int item;
	SqList L;
	InitList(L);
	Create(L);
	Delete(L,item);
	
}

        运行结果

请输入要创建的顺序表的长度：5
请输入依次输入5个数（空格隔开）：1 2 2 4 5
顺序表L创建成功！
当前顺序表中所有元素为：1 2 2 4 5
请输入要删除的item的值为：2
删除元素2成功！
当前顺序表中所有元素为：1 4 5

--------------------------------
Process exited after 11.71 seconds with return value 0
请按任意键继续. . .