题目要求：
 
对长度为n的顺序表L，编写一个时间复杂度为O（n），空间复杂度为O（1）的算法
 该算法删除线性表中所有值为x的数据元素
 
/*对长度为n的顺序表L，编写一个时间复杂度为O（n），空间复杂度为O（1）的算法
该算法删除线性表中所有值为x的数据元素*/
#include <iostream>
#include <cstring>
#include<math.h>
#define MAXSIZE 20
#define ElemType int//不加分号
using namespace std;
typedef struct {
	ElemType data[MAXSIZE];
	int length;
}SqList;
bool InitList(SqList &L) {
	memset(L.data, 0, sizeof(L));
	if (!L.data)
		exit(0);
	L.length = 0;
	return true;
}
void CreateList(SqList &L, int n) {
	for (int i = 0;i<n;i++) {
		cin >> L.data[i];
		L.length++;
	}
}
bool DeleteX(SqList &L,ElemType e) {//推荐做法，更容易想
	//注释部分的做法没有达到空间复杂度为o（1），也不会满足时间复杂度要求
	/*int x[MAXSIZE];
	int j=-1;
	memset(x, 0, sizeof(x));*/
	int k=0;//用k来记录所有值不是x的元素的下标，边扫描边统计k，并将不等于x的元素向前移动k个位置，最后修改L的长度
	for (int i = 0;i <L.length;i++) {
		if (L.data[i] != e) {
			/*j++;
			x[j] = i;*/
			L.data[k] = L.data[i];
			k++;
		}
		
	} 
	L.length = k;
	return true;
}
void DeleteX2(SqList &L, ElemType e) {
	int k = 0, i = 0;//用k来记录等于x的元素的个数，边扫描L边统计k，并将不等于x的元素前移k个位置，最后修改L的长度
	while (i<L.length)
	{
		if (L.data[i] == e)
			k++;//用k来记录等于x的元素的个数，边扫描L边统计k
		else
			L.data[i - k] = L.data[i];//将不等于x的元素前移k个位置
		i++;
	}
	L.length -= k;//修改L的长度
}
void PrintList(SqList L) {
	cout << "表中元素分别为";
	for (int i = 0;i<L.length;i++)
		cout << L.data[i] << "  ";
	cout << endl;
}
int main() {
	SqList L;
	InitList(L);
	int n = 0;
	cout << "请输入要创建的表的长度：" << endl;
	cin >> n;
	cout << "请依次输入各个元素：（用空格隔开）" << endl;
	CreateList(L, n);
	cout << "请输入想要删除元素的值（即x的值）：" << endl;
	ElemType e;
	cin >> e;	
	DeleteX2(L,e);
	PrintList(L);
	return 0;
}
 
 

题目
 
在顺序表中第五个位置插入一个元素9，实现顺序表插入的基本操作，输出顺序表中所有元素
 
#include<iostream>

using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status; //Status 是函数返回值类型，其值是函数结果状态代码。
typedef int ElemType; //ElemType 为可定义的数据类型，此设为int类型

#define MAXSIZE 100			//顺序表可能达到的最大长度

typedef struct {
	ElemType *elem; //存储空间的基地址
	int length; //当前长度
} SqList;

Status InitList(SqList &L) { //初始化创建顺序表	
	L.elem = new ElemType[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间
	if (!L.elem)
		exit(OVERFLOW); //存储分配失败退出		
	cout<<"初始化表中元素个数：";
	int n;
	cin>>n;
	cout<<"creat SqList:";  //在初始化中创建表
	for(int i = 0; i < n; i++){
		cin>>L.elem[i];
	}
	L.length = n; //空表长度为0
	return OK;
}

void input(SqList L){//输出表 
	ElemType i = 0;
	while(L.length != i){
		cout<<L.elem[i]<<" ";
		i++;
	}
	cout<<endl;
}

Status ListInsert(SqList &L, int i, ElemType e) { //顺序表的插入
	//在顺序表L中第i个位置之前插入新的元素e
	//i值的合法范围是1<=i<=L.length+1
	if ((i < 1) || (i > L.length + 1))
		return ERROR; //i值不合法
	if (L.length == MAXSIZE)
		return ERROR; //当前存储空间已满
	for (int j = L.length - 1; j >= i - 1; j--)
		L.elem[j + 1] = L.elem[j]; //插入位置及之后的元素后移
	L.elem[i - 1] = e; //将新元素e放入第i个位置
	++L.length; //表长增1
	return OK;
}

int main()
{
	SqList a;	
	InitList(a);
	input(a);//输出顺序表 
	ListInsert(a,5,9); 
	input(a);//输出顺序表 
	return OK;
}
 
参考资料：
 《数据结构 C语言版 第2版》严蔚敏 李冬梅 吴伟民

//已知顺序表L的长度为n,试编写算法实现在顺序表中删除值为elem的数据元素
 //（其中n与elem从键盘输入）
 
# include <iostream>
# include <stdio.h>
# include <stdlib.h>
using namespace std;
const maxn = 1000 + 10;

typedef struct node
{
	int *arr;
	int length;
	int maxsize;
}sqlist;

void createsqlist(sqlist &L)
{
	L.arr = (int*)malloc(maxn * sizeof(int));
	L.length = 0;
	L.maxsize = maxn;
}

void insqlist(sqlist& L, int n)
{
	int *p;
	printf("请依次输入数字创建一个顺序表：\n");

	for(p = L.arr; p<L.arr + n; p++)
	{
		scanf("%d", p);
	}

	L.length = n;
}

void outsqlist(sqlist L)
{
	int *p;
	printf("顺序表的元素为：\n");

	for(p = L.arr; p<L.arr+L.length; p++)
	{
		printf("%d ", *p);
	}

	printf("\n");
}

void deletesqlist(sqlist& L, int elem)
{
	int i = 0; 
	
	while(i<L.length && L.arr[i] != elem)
	{
		i++;
	}

	for(int j = i+1; j<L.length; j++)
	{
		if(L.arr[j] != elem)
		{
			L.arr[i++] = L.arr[j];
		}
	}

	L.length = i;
}

int main()
{
	//加速c++输入输出流
	ios::sync_with_stdio(false);
	cin.tie(0);


	sqlist L;
	createsqlist(L);
	int n, elem;
	
	printf("请输入n个元素： \n");
	scanf("%d", &n);
	insqlist(L, n);

	printf("请输入删除的元素值：\n");
	scanf("%d", &elem);
	deletesqlist(L, elem);
	outsqlist(L);

	return 0;
}

题目
 
在顺序表中删除指定位置（i=5）上的元素，实现顺序表的删除的基本操作，输出顺序表中所有元素
 
#include<iostream>

using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status; //Status 是函数返回值类型，其值是函数结果状态代码。
typedef int ElemType; //ElemType 为可定义的数据类型，此设为int类型

#define MAXSIZE 100			//顺序表可能达到的最大长度

typedef struct {
	ElemType *elem; //存储空间的基地址
	int length; //当前长度
} SqList;

Status InitList(SqList &L) { //初始化创建顺序表	
	L.elem = new ElemType[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间
	if (!L.elem)
		exit(OVERFLOW); //存储分配失败退出		
	cout<<"初始化表中元素个数：";
	int n;
	cin>>n;
	cout<<"creat SqList:";  //在初始化中创建表
	for(int i = 0; i < n; i++){
		cin>>L.elem[i];
	}
	L.length = n; //空表长度为0
	return OK;
}

void input(SqList L){//输出表 
	ElemType i = 0;
	while(L.length != i){
		cout<<L.elem[i]<<" ";
		i++;
	}
	cout<<endl;
}

Status ListDelete(SqList &L, int i) { //顺序表的删除
	//在顺序表L中删除第i个元素，并用e返回其值
	//i值的合法范围是1<=i<=L.length
	if ((i < 1) || (i > L.length))
		return ERROR; //i值不合法
	for (int j = i; j < L.length; j++)
		L.elem[j - 1] = L.elem[j]; //被删除元素之后的元素前移
	--L.length; //表长减1
	return OK;
}

int main()
{
	SqList a;	
	InitList(a);
	input(a);//输出顺序表 
	ListDelete(a,5);
	input(a);//输出顺序表 
	return OK;
}
 
参考资料：
 《数据结构 C语言版 第2版》严蔚敏 李冬梅 吴伟民