[数据结构与算法]数据结构《顺序表》

关于顺序表的插入，查询，删除，清空，非递归归并排序，递归归并排序，位移法删除重复元素，查找法删除重复元素等等基本操作代码，以及关于malloc的动态分配内存的解释，重要解释在代码中：

/*数据结构 线性表->顺序表的插入，查询，删除，清空*/
#include<bits/stdc++.h>
using namespace std;
#define MAXSIZE 200000
#define TRUE 1
#define FALSE 0
#define OK 1 
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int ElemType; 
typedef int Status; 
typedef struct{
	ElemType *elem;
	int length;
}SqList;
Status InitList(SqList &L){//操作结果构造一个空的线性表 
	L.elem=(ElemType *)malloc(MAXSIZE*sizeof(ElemType));//malloc是在内存的动态存储区中分配一个长度为size的连续空间，返回值是一个指向所分配的连续存储域的起始地址的指针，当函数未能成功分配存储空间（如内存不足）就会返回一个NULL指针。所以在调用该函数时应该检测返回值是否为NULL并执行相应的操作。 
	//if(!L.elem) exit(OVERFLOW); 
	L.length=0;
	if(L.elem==NULL) return ERROR; 
	return OK;
}
void DestroyList(SqList &L){//破坏链表 
	if(L.elem) delete L.elem;//释放存储空间 
}
void ClearList(SqList &L){ L.length=0;}//清空
int ListEmpty(SqList L){if(L.length==0) return 1;return 0;}//判断是否为空 
int ListLength(SqList L){return L.length;}//获取链表长度 
int GetElem(SqList L,int i,ElemType &e){//取第i个元素 
	if(i<1||i>L.length) return ERROR;//判断位置是否合理 ，不合理 返回ERROR 
	e=L.elem[i-1];//注意下标存储位置 
	return OK;
}
int LocateElem(SqList L,ElemType e){//平均查找长度 (n+1)/2 
	for(int i=1;i<=L.length;i++){//也可以用while 
		if(L.elem[i-1]==e) return i;
	}
	return 0;//查找失败返回 0 
}
int PriorElem();//前驱 
int NextElem();//后继 
Status ListInsert(SqList &L,int i,ElemType e){//插入元素 
	if(i<1||i>L.length+1) return ERROR;//判断插入位置是否合理 
	if(L.length>=MAXSIZE) return ERROR;//关于不取>MAXSIZE的问题：我们这里是需要插入一个数，==MAXSIZE的时候已经满了，再插入一个必然爆呀~ 
	for(int j=L.length-1;j>=i-1;j--){
		L.elem[j+1]=L.elem[j];
	}
	L.elem[i-1]=e;
	L.length++;
	return OK;	
}
Status ListDelete(SqList &L,int i){
	if(i<1||i>L.length) return ERROR;
	for(int j=i;j<=L.length-1;j++){//最后一项是L.length-1移动到L.length-2 
		L.elem[j-1]=L.elem[j];
	}
	L.length--;
	return OK;
}
void ListTravel(SqList &L){//遍历 
	for(int i=1;i<=L.length;i++){
		if(i==1) cout<<L.elem[i-1];
		else cout<<" "<<L.elem[i-1];
	} 
	return ; 
}
SqList Merge_Sort(SqList L1,SqList L2){//非递归的归并排序 
	SqList L;
	InitList(L);
	int i=1,j=1;
	while(i<=L1.length&&j<=L2.length){
		if(L1.elem[i-1]<L2.elem[j-1]) ListInsert(L,L.length+1,L1.elem[i-1]),i++;
		else ListInsert(L,L.length+1,L2.elem[j-1]),j++;
	}
	while(i<=L1.length) ListInsert(L,L.length+1,L1.elem[i-1]),i++;
	while(j<=L2.length) ListInsert(L,L.length+1,L2.elem[j-1]),j++;
	return L;
}
/*void merge_sort(int s[],int l,int r){//递归的归并排序（由于数据结构书上没提这个，就用数组模拟了（手动狗头QAQ）） if(l>=r) return ;int mid=l+r>>1;merge_sort(s,l,mid);merge_sort(s,mid+1,r);int i=l,j=mid+1,k=0;while(i<=mid&&j<=r){if(s[i]<=s[j]) temp[k++]=s[i++];else temp[k++]=s[j++];}while(i<=mid) temp[k++]=s[i++];while(j<=r) temp[k++]=s[j++];for(i=l,j=0;i<=r;i++,j++) s[i]=temp[j];}*/
Status ListFind(SqList L,ElemType x){//查找是否表中存在元素x 存在返回1 否则返回0 
	for(int i=1;i<=L.length;i++){
		if(L.elem[i-1]==x) return OK; 
	}
	return ERROR;
}
void ListInsertOnlyOne(SqList &L,ElemType x){//如果表中不存在这个元素就插入 
	if(!ListFind(L,x)) ListInsert(L,L.length+1,x);
}
int ListFindSecondPos(SqList &L){//位移法删除表中重复元素 
	for(int i=0;i<L.length-1;i++){
		for(int j=i+1;j<L.length;j++){
			if(L.elem[i]==L.elem[j]){
				for(int k=j;k<=L.length-2;k++){
					L.elem[k]=L.elem[k+1];
				}
				L.length--;
				j--;
			}
		}
	}
	return 0;
}
int main(){
	int n;
	cin>>n;
	while(n--){
		SqList L;
		InitList(L);
		int m;
		cin>>m;
		for(int i=1;i<=m;i++){
			int x;cin>>x;
			//ListInsertOnlyOne(L,x);
			ListInsert(L,i,x); 
		}
		ListFindSecondPos(L);
		ListTravel(L);
		if(n) cout<<endl;
	} 
	return 0;
}