线性表基本操作及合并算法

#include
using namespace std;

#define MAXSIZE 100

enum Status{ success, fail, fatal, rangeerror, overflow };

typedef int ElemType;

typedef struct list{
int *elem;
int length;
}List, *ListPtr;

//初始化线性表
Status List_Init(ListPtr L){
Status status = fatal;
L->elem = (int *)malloc((MAXSIZE + 1)*sizeof(int));
if (L->elem){
L->length = 0;
status = success;
}
return status;
}

//创建线性表
Status List_Create(ListPtr L, int number){
Status status = success;
for (int i = 1; i <= number; i++)
{
cin >> L->elem[i];
++L->length;
}
return status;
}

//销毁线性表
void List_Destory(ListPtr L){
if (L->elem)
free(L->elem);
L->length = 0;
}

//清空线性表
void List_Clear(ListPtr L){
L->length = 0;
}

//判断线性表是否为空
bool List_Empty(ListPtr L){
return L->length == 0;
}

//求线性表长度
int List_Size(ListPtr L){
return L->length;
}

//线性表遍历算法
void List_Traversal(ListPtr L){
int pos = 1;
int len = List_Size(L);
for (; pos <= len; pos++)
cout << L->elem[pos] << " ";
cout << endl;
}

//按位置查找算法
Status List_Retrieve(ListPtr L, int pos, ElemType *elem){ //查找线性表中pos位置的元素，并将其存储到elem中
Status status = rangeerror;
int len = L->length;
if (1 <= pos&&pos <= len){
*elem = L->elem[pos];
status = success;
}
return status;
}

//按值查找算法
Status List_Locate(ListPtr L, ElemType elem, int *pos){ //查找线性表中值为elem的元素，并且将其位置信息保存到pos中
Status status = rangeerror;
int len = L->length;
int i = 1;
while (i <= len&& L->elem[i] != elem)
i++;
if (i <= len){
*pos = i;
status = success;
}
return status;
}

//插入算法
Status List_Insert(ListPtr L, int pos, ElemType elem){ //将元素elem插入到线性表中的pos位置上
Status status = rangeerror;
int len = L->length, i;
if (len > MAXSIZE) status = overflow;
else if (1 <= pos&&pos <= len + 1){
for (i = len; i >= pos; i--)
L->elem[i + 1] = L->elem[i];
L->elem[pos] = elem;
L->length++;
status = success;
}
return status;
}

//删除元素
Status List_Remove(ListPtr L, int pos){ //删除线性表中pos位置的元素
Status status = rangeerror;
int len = L->length, i;
if (1 <= pos&&pos <= len){
for (i = pos; i < len; i++)
L->elem[i] = L->elem[i + 1];
L->length--;
status = success;
}
return status;
}

//求前驱
Status List_Prior(ListPtr L, int pos, int *elem){ //求线性表中pos位置元素的前驱
Status status = fail;
int len = L->length;
if (2 <= pos && pos <= len){
*elem = L->elem[pos - 1];
status = success;
}
return status;
}

//求后继
Status List_Next(ListPtr L, int pos, int *elem){ //求线性表中pos位置元素的后继
Status status = fail;
i

nt len = L->length;
if (1 <= pos&&pos <= len - 1){
*elem = L->elem[pos + 1];
status = success;
}
return status;
}

//线性表合并算法
Status List_Union(ListPtr La, ListPtr Lb){
ElemType elem;
Status status;
int i, j, len = List_Size(Lb);
for (i = 1; i <= len; i++){
List_Retrieve(Lb, i, &elem);
status = List_Locate(La, elem, &j);
if (status != success){
status = List_Insert(La, 1, elem);
if (status != success)
break;
}
}
return status;
}

//有序表的合并算法
Status List_Merge(ListPtr La, ListPtr Lb, ListPtr Lc){
ElemType elem1, elem2;
Status status;
status = List_Init(Lc);
if (status != success)
return status;
int i = 1, j = 1, k = 1;
int n = List_Size(La), m = List_Size(Lb);
while (i <= n&&j <= m){
List_Retrieve(La, i, &elem1);
List_Retrieve(Lb, j, &elem2);
if (elem1 < elem2){
status = List_Insert(Lc, k, elem1);
i = i + 1;
}
else {
status = List_Insert(Lc, k, elem2);
j = j + 1;
}
if (status != success)
return status;
k = k + 1;
}
while (i <= n){
List_Retrieve(La, i, &elem1);
status = List_Insert(Lc, k, elem1);
if (status != success)
return status;
i = i + 1;
k = k + 1;
}
while (j <= m){
List_Retrieve(Lb, j, &elem2);
status = List_Insert(Lc, k, elem2);
if (status != success)
return status;
j = j + 1;
k = k + 1;
}
return status;
}

int main(){
ListPtr a = new list,b=new list,c=new list;

/*在此插入操作代码
线性表的存储位置是从elem[1]开始
*/


system("pause");
return 0;
}