目录

时间复杂度为O(1)(顺序表)：代码实现：

运行结果：

时间复杂度为O(n)(顺序表)：代码实现：

运行结果：

单链表：时间复杂度o（n）:代码实现：

---

时间复杂度为O(1)(顺序表)：代码实现：

#include<iostream>
using namespace std;
#define MAXSIZE 100
#define ok -1
#define error -2
typedef int Status;
typedef int ElemType; 
typedef struct
{
	ElemType *elem;
	int length;
}Sqlist;
Status InitList(Sqlist &L);
void chushi(Sqlist &L,int x);
void shuchu(Sqlist L); 
Status GetElem(Sqlist L,int i,ElemType &e);
Status ListInsert(Sqlist &L,int i,ElemType e);
Status Delete(Sqlist &L,int i);
Status Sort(Sqlist &L);
void SequenceSort(Sqlist &L,ElemType x);
void delete1(Sqlist &L,int x);
int main()
{
	Sqlist L;
	int x,i,j;
	Status m;
	ElemType e;
	x=InitList(L);
	if(x==error) cout<<"初始化失败"<<endl;
	else      	 cout<<"初始化成功"<<endl;
	cout<<"请决定输入元素的个数";
	cin>>x;
	chushi(L,x); 
	cout<<"此时顺序表为："<<endl;
	shuchu(L);
	cout<<endl<<"请输入要删除的元素";
	cin>>x;
	delete1(L,x);
	cout<<"删除后的表为"<<endl;
	shuchu(L);
	return 0;
}
Status InitList(Sqlist &L)//初始化开辟空间 
{
	L.elem=new ElemType[MAXSIZE];
	if(!L.elem) return error;
	L.length=0;
	return ok;
}
void chushi(Sqlist &L,int x)//初始化赋值 
{
	ElemType m;
	for(int i=0;i<x;i++)
	{
		cout<<"请对第"<<i+1<<"个位置赋值";
		cin>>m;
		L.elem[i]=m;
		L.length++;
	}
}

void shuchu(Sqlist L)//输出操作 
{
	cout<<"顺序表为:";
	for(int i=0;i<L.length;i++)
	{
		cout<<L.elem[i]<<"  ";
	}
} 
void delete1(Sqlist &L,int x){
	int i=0,k=0;
	for(int i=0;i<L.length;i++){
		if(L.elem[i]!=x){
			L.elem[k]=L.elem[i];
			k++;
		}
		
	}
	L.length-=L.length-k;
}

运行结果：

时间复杂度为O(n)(顺序表)：代码实现：

#include<stdio.h>
#include"sqlist.cpp"
/*已知长度为n的线性表A采用顺序存储结构，
编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，
该算法删除线性表中所有值为x的数据元素。
*/
void DeleteNode1(SqList *&L,ElemType x)
{
	int k=0;//k记录元素值不等于x的个数
	for(int i=0;i<L->length ;i++)
	{
		if(L->data [i]!=x)//若当前元素不为x，则将其插入到L中 
		{
			L->data[k]=L->data[i];
			k++;
		}
	} 
	L->length = k;
}
//算法1类似于建顺序表
 
void DeleteNode2(SqList *&L,ElemType x)
{
	int k=0;
	for(int i=0;i<L->length ;i++)
	{
		if(L->data [i]==x)//当前元素为x时k增1 
		{
			k++;
		}
		else
		{
			L->data [i-k]=L->data [i];//当前元素不为x时将其前移k个位置 
		}
	}
	L->length -= k;//顺序表L的长度减K 
}
int main(int argc,char *argv[])
{
	ElemType x;
	ElemType a[]={1,2,2,1,0,2,4,2,3,1};
	SqList *L;
	InitList(L);//初始化线性表
	CreateList(L,a,10);//数组名代表数组元素的首地址 
	printf("L:");
	DisplayList(L);
	printf("请输入要删除元素的值:");
	scanf("%d",&x);
	printf("删除值为%d的元素 \n",x);
//	DeleteNode1(L,x); 
	DeleteNode2(L,x);
	printf("L:");
	DisplayList(L);
	DestroyList(L);
	return 0;
}

运行结果：

单链表：时间复杂度o（n）:代码实现：

#include<iostream>
using namespace std;
#define ok -1
#define error -2
typedef int Status;
typedef int ElemType; 
typedef struct LNode
{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;
Status InitList(LinkList &L);
Status fuzhi(LinkList &L,int m);
void shuchu(LinkList L);
Status ListInsert(LinkList &L,int m,ElemType y);
Status Delete(LinkList &L,int n);//删除
void Sort(LinkList &L);
Status Length(LinkList L);
void SequenceSort(LinkList &L,ElemType x);
void delete1(LinkList &L,int x);
int main()
{
	LinkList L;
	int x,m,n;
	ElemType y;
	x=InitList(L);
	if(x==error) cout<<"初始化失败";
	else         cout<<"初始化成功"<<endl;
	cout<<"请决定输入几个元素";
	cin>>m;
	x=fuzhi(L,m);
	if(x==error) cout<<"赋值失败";
	shuchu(L);
	cout<<"请决定删除元素：";
	cin>>x;
	delete1(L,x);
	shuchu(L);
	return 0;
}
Status InitList(LinkList &L)
{
	L=new LNode;
	if(L==NULL) return error;
	L->next=NULL;
	return ok;
}
Status fuzhi(LinkList &L,int m)
{
	LNode *s,*r=L;
	ElemType n;
	for(int i=1;i<=m;i++)
	{
		cout<<"请输入第"<<i<<"个元素";
		cin>>n; 
		s=new LNode;
		s->data=n;
		r->next=s;
		r=s;
	}
	r->next=NULL;
	return ok;
}
void shuchu(LinkList L)
{
	LNode *p;
	p=L->next;
	cout<<"单链表内容为:";
	while(p!=NULL)
	{
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
}
void delete1(LinkList &L,int x){
	LNode *p,*s;
	p=L;
	while(p){
		if(p->next->data==x){
			s=p->next;
			p->next=s->next;
			delete s;
		}
		p=p->next;
	}
}