数据结构：顺序表

实验目标：

提示

（1）构造一个最大容量为LIST_INIT_SIZE的顺序表。通过InitList函数来实现

（2）在顺序表中查询第一个满足判定条件的数据元素，若存在，则返回他的位序，否则返回0。通过ListEmpty函数来实现

（3）在顺序表L的第i个元素之前插入新的元素,用InsertVlaue函数来实现

（4）删除顺序表L的第i个元素，用e返回其值,通过DeleteValue来实现

（5）已知两个顺序表A和B按元素值递增有序排序，要求写一算法实现将A和B归并成一个按元素值递增的有序排序的顺序表

---

实验代码

#include <bits/stdc++.h>
using namespace std;

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef int ElemType;

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef struct List
{
	ElemType *elem;
	int length;
	int listsize;
}SqList;

Status InitList(SqList &L)//构造一个新的顺序表
{
	L.elem = (int *)malloc(LIST_INIT_SIZE*sizeof(int));//分配存储空间

	if(!L.elem) 
	{
		cout<<"分配存储空间失败！"<<endl;
		exit(OVERFLOW);
	}

	L.length=0;
	L.listsize=LIST_INIT_SIZE;
	return OK;
}

Status InsertList(SqList &L)//对顺序表进行赋值
{
	int i,j;
	cout<<"请输入插入顺序表的元素的个数：";
	cin>>i;
	cout<<endl;

	if(i>L.listsize)//当要插入的数值大于地址空间,拓展新的空间
	{
		while(1)//一直拓展空间，一直到够用为止
		{
			if(i>L.listsize)
			{
				L.elem=(ElemType *)realloc(L.elem,LISTINCREMENT * sizeof(ElemType));
		        L.listsize += LISTINCREMENT;
			}
			else break;
		}
	}

	cout<<"请输入元素：";
	for(int j=1;j<=i;j++)
	{
		cin>>L.elem[j];
	}
	L.length=i;
	cout<<endl;
	return OK;
}

Status InsertValue(SqList &L,int i,ElemType e)//在顺序表每一位置前插入元素
{
	ElemType *newbase;

	if(i<1||i>L.length) return ERROR;

	if(L.length>=L.listsize)
	{
		newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
		if(!newbase) 
		{
			cout<<"分配空间失败！"<<endl;
			exit(OVERFLOW);
		}

		L.elem=newbase;
		L.listsize+=LISTINCREMENT;
	}
	L.length+=1;

	for(int j=L.length;j>=i;j--)
	{
		L.elem[j]=L.elem[j-1];
	}
	L.elem[i]=e;
	
	cout<<"插入成功！"<<endl;
	return OK;
}

Status DeleteValue(SqList &L,int i)//删除第i个元素，并用e返回其值
{
	if(i<1)//如果删除的位置小于1
	{
		cout<<"删除失败，所要删除的位置不存在！"<<endl;
		exit(OVERFLOW);
	}
	if(i>L.length)//如果删除的位置大于顺序表的长度，就报错
	{
		cout<<"删除失败，所要删除的位置超过顺序表长度！"<<endl;
		exit(OVERFLOW);
	}

	cout<<"删除的元素为："<<L.elem[i]<<endl;
    
	for(int j=i;j<L.length;j++)
	{
		L.elem[j]=L.elem[j+1];
	}

	L.length-=1;
	cout<<"删除成功！"<<endl;

	return OK;
}

Status SyList(SqList &A,SqList &B)//按A和B递增顺序合成一个新的顺序表
{
	SqList C;
	InitList(C);
	sort(A.elem,A.elem+A.length+1);//先对顺序表进行排序
	sort(B.elem,B.elem+B.length+1);

	if(A.length+B.length>C.listsize)//如果A和B的总长度超过C的地址长度，就增加，一直增加到可以容纳为止
	{
		while(1)
		{
			if(A.length+B.length>C.listsize)
			{
				C.elem=(ElemType *)realloc(C.elem,LISTINCREMENT * sizeof(ElemType));
				C.listsize+=LISTINCREMENT;
			}
		}
	}

	int k=1;
	int i=1,j=1;

	while(1){
		if(i>A.length){//如果A已经到最后面了，那直接把B的剩余元素加入C中
			for(int m=j;m<=B.length;m++)
			{
				C.elem[k]=B.elem[m];
				k++;
				C.length++;
			}
			break;
		}
		if(j>B.length){//如果B已经到最后面了，那直接把A的剩余元素加入C中
			for(int m=i;m<=A.length;m++)
			{
				C.elem[k]=A.elem[m];
				k++;
				C.length++;
			}
			break;
		}
	
		if(A.elem[i]>B.elem[j]){
			C.elem[k]=B.elem[j];
			k++;
			C.length++;
			j++;
		}
		else if(A.elem[i]==B.elem[j]){
			C.elem[k]=A.elem[i];
			k++;
			C.length++;
			C.elem[k]=B.elem[j];
			k++;
			C.length++;
			i++;
			j++;
		}
		else{
			C.elem[k]=A.elem[i];
			k++;
			C.length++;
			i++;
		}
	}

	cout<<"合成之后的表为：";
	for(int i=1;i<=C.length;i++)
	{
		cout<<C.elem[i]<<" ";
	}

	cout<<endl;
	return OK;
}

Status PrintList(SqList &L)//打印顺序表
{
	cout<<"当前顺序表所含有的元素为：";
	for(int i=1;i<=L.length;i++)
	{
		cout<<L.elem[i]<<" ";
	}
	cout<<endl;
	return OK;
}

Status ListEmpty(SqList &L)//判断是否为空顺序表
{
	int pos;

	if(L.length==0) 
	{
		cout<<"未找到满足判断条件的数据元素!"<<endl;
		cout<<endl;
		return FALSE;
	}
	else
	{
		for(int i=0;i<=L.length;i++)
		{
			if(L.elem[i] != -1)
			{
				pos=i;
				break;
			}
		}

		cout<<"顺序表中第一个满足条件的数据元素的位序为："<<pos<<",其值为："<<L.elem[pos]<<endl;
		cout<<endl;
		return OK;
	}
}

int main()
{
	while(1)
	{
		SqList L;
		SqList A;
		SqList B;

		cout<<endl;
		cout<<"**1,创建一个顺序表，并对其赋值"<<endl;
		cout<<"**2,查询第一个满足判定条件的数据元素，若存在，则返回他的位序，否则返回0"<<endl;
	    cout<<"**3,在第i个元素之前插入新的元素"<<endl;
	    cout<<"**4,删除顺序表L的第i个元素，用e返回其值"<<endl;
		cout<<"**5,创建A和B两个顺序表，并将其按值递增合成"<<endl;
		cout<<"**6,打印顺序表"<<endl;
		cout<<"**0,退出系统"<<endl;

		cout<<"请输入要进行的操作：";
		int choice;
	    cin>>choice;
	    cout<<endl;	

		switch(choice)
		{
			case 1:InsertList(L);break;
			case 2:ListEmpty(L);break;
			case 3:
			{
				int pos,e;
				cout<<"请输入要插入的位置：";
				cin>>pos;
				cout<<endl<<"请输入要插入的元素：";
				cin>>e;
				cout<<endl;
				InsertValue(L,pos,e);
				break;
			}
			case 4:
			{
                int pos;
				cout<<"请输入要删除的位置：";
				cin>>pos;
				cout<<endl;
				DeleteValue(L,pos);
				break;
			}
			case 5:
			{
				InitList(A);
				InitList(B);
				cout<<"A:";
				InsertList(A);
				cout<<"B:";
				InsertList(B);
				SyList(A,B);
				break;
			}
			case 6:PrintList(L);break;
			case 0:exit(0);
		}
	}
	
	system("pause");
	return 0;
}