顺序表示的线性表——顺序表1

线性表是由n个类型相同的数据元素组成的有限序列，记为（a1, a2,  a3, ... ,ai-1, ai,  ai+1, ... , an）。线性表的数据元素存在着序偶关系，即元素之间具有一定的次序。在线性表中，数据元素ai-1位于ai的前面，ai又在ai+1的前面，我们把ai-1称为ai的直接前驱元素。ai称为ai-1的直接后继元素，ai+1称为ai的直接后继元素。逻辑结构如图所示：

线性表第i个元素的存储位置与第一个元素a1的存储位置关系满足：LOC(ai)=LOC(a1)+(i-1)*m

LOC(a1)就是起始地址，或者叫基地址。

【存储结构】

typedef struct
{
	DataType list[ListSize];
	int length;
}SeqList;

【基本运算】

（1）初始化线性表

//初始化线性表
void InitList(SeqList *L)
{

	L->length = 0;//把线性表长度置为0
}

（2）判断线性表是否为空

//判断线性表是否为空,线性表为空返回1，否则返回0
int ListEmpty(SeqList L)
{
	if (L.length == 0)
		return 1;
	else
		return 0;
}

（3）按照序号查找

//按照序号查找
int GetElem(SeqList L, int i, DataType *e)
/*查找线性表中第i个元素，查找成功返回给e，并返回1表示成功，否则返回-1，表示失败*/
{
	if (i<1 || i>L.length)
		return -1;
	else
		*e = L.list[i - 1];
	return 1;

}

（4）按照内容查找

//按照内容查找
int LocateElem(SeqList L, DataType e)
{
	int i;
	for (i = 0; i < L.length; i++)
		if (L.list[i] == e)
			return i + 1;
	return 0;
}

（5）在第i个位置插入元素，i位置后的元素向后移动

//插入操作
int InsertList(SeqList *L, int i, DataType e)
/*在顺序表中的第i个位置插入元素e，插入成功返回1，插入不合法返回-1，顺序表满返回0.*/
{
	int j;
	if (i<1||i>L->length+1)/*在插入元素前，判断插入位置是否合法*/
	{
		cout <<"插入位置"<<i<<"不合法！" << endl;
		return -1; 
	}
	else if (L->length>=ListSize)/*在插入元素之前，判断顺序表是否已经满，不能插入元素*/
	{
		cout << "顺序表已经满，不能插入元素。" << endl;
		return 0;

	}
	else
	{
		for (j = L->length; j >= i; j--)
			/*将第i个位置以后的元素依次后移*/
		{
			L->list[j] = L->list[j - 1];
		}
		L->list[i - 1] = e;
		L->length = L->length + 1;
		return 1;

		
	}
}

（6）删除第i个位置的元素，i位置后的元素向前移动

/*删除操作，删除第i个元素*/
int DeleteList(SeqList *L, int i, DataType *e)
{
	int j;
	if (L->length<=0)
	{
		cout << "顺序表表已空，不能进行删除！" << endl;
		return 0;

	}
	else if (i<1||i>L->length)
	{
		cout << "删除位置不合适！" << endl;
		return -1;
	}
	else
	{
		*e = L->list[i - 1];
		for (j = i; j <= L->length - 1;j++)
		{
			L->list[j - 1] = L->list[j];
			L->length = L->length - 1;
			return 1;
		}
	}
}

（7）求线性表长度

/*求线性表的长度*/
int ListLength(SeqList L)
{
	return L.length;
}

（8）清空线性表

/*清空顺序表*/
void ClearList(SeqList *L)
{
	L->length = 0;
}

整理以上代码，保存为SeqList.h

#pragma once
#define ListSize 200
#include <iostream>
using namespace std;
typedef int DataType;
typedef struct
{
	DataType list[ListSize];
	int length;
}SeqList;

//初始化线性表
void InitList(SeqList *L)
{

	L->length = 0;//把线性表长度置为0
}
//判断线性表是否为空,线性表为空返回1，否则返回0
int ListEmpty(SeqList L)
{
	if (L.length == 0)
		return 1;
	else
		return 0;
}

//按照序号查找
int GetElem(SeqList L, int i, DataType *e)
/*查找线性表中第i个元素，查找成功返回给e，并返回1表示成功，否则返回-1，表示失败*/
{
	if (i<1 || i>L.length)
		return -1;
	else
		*e = L.list[i - 1];
	return 1;

}
//按照内容查找
int LocateElem(SeqList L, DataType e)
{
	int i;
	for (i = 0; i < L.length; i++)
		if (L.list[i] == e)
			return i + 1;
	return 0;
}
//插入操作
int InsertList(SeqList *L, int i, DataType e)
/*在顺序表中的第i个位置插入元素e，插入成功返回1，插入不合法返回-1，顺序表满返回0.*/
{
	int j;
	if (i<1||i>L->length+1)/*在插入元素前，判断插入位置是否合法*/
	{
		cout <<"插入位置"<<i<<"不合法！" << endl;
		return -1; 
	}
	else if (L->length>=ListSize)/*在插入元素之前，判断顺序表是否已经满，不能插入元素*/
	{
		cout << "顺序表已经满，不能插入元素。" << endl;
		return 0;

	}
	else
	{
		for (j = L->length; j >= i; j--)
			/*将第i个位置以后的元素依次后移*/
		{
			L->list[j] = L->list[j - 1];
		}
		L->list[i - 1] = e;
		L->length = L->length + 1;
		return 1;

		
	}
}
/*删除操作，删除第i个元素*/
int DeleteList(SeqList *L, int i, DataType *e)
{
	int j;
	if (L->length<=0)
	{
		cout << "顺序表表已空，不能进行删除！" << endl;
		return 0;

	}
	else if (i<1||i>L->length)
	{
		cout << "删除位置不合适！" << endl;
		return -1;
	}
	else
	{
		*e = L->list[i - 1];
		for (j = i; j <= L->length - 1;j++)
		{
			L->list[j - 1] = L->list[j];
			L->length = L->length - 1;
			return 1;
		}
	}
}
/*求线性表的长度*/
int ListLength(SeqList L)
{
	return L.length;
}

/*清空顺序表*/
void ClearList(SeqList *L)
{
	L->length = 0;
}

实例，实现合并两个线性表

新建main.cpp

#include"SeqList.h"
void MergeList(SeqList A, SeqList B, SeqList *C);
void main()
{
	int i,flag;
	DataType a[] = {8, 17, 17, 25, 29};
	DataType b[] = {3, 9, 21, 21, 26, 57};
	DataType e;
	SeqList A, B, C;
	InitList(&A);
	InitList(&B);
	InitList(&C);
	for ( i = 1; i <=sizeof(a)/sizeof(a[0]); i++)
	/*将数组a中的元素插入顺序表A中*/
	{
		if (InsertList(&A,i,a[i-1])==0)
		{
			cout << "位置不合法" << endl;
			return;
		}
	}
	/*将数组b插入顺序表b中*/
	for ( i = 1; i <= sizeof(b)/sizeof(b[0]); i++)
	{
		if (InsertList(&B,i,b[i-1])==0)
		{
			cout << "位置不合法" << endl;
			return;
		}
	}
	/*输出A中的元素*/
	cout << "顺序表A中的元素：" << endl;
	for ( i = 1; i <=A.length ; i++)
	{
		flag = GetElem(A, i, &e);
			if (flag==1)
			{
				cout << e << endl;

			}
	}
	cout << endl;
	/*输出B中的元素*/
	cout << "顺序表B中的元素：" << endl;
	for ( i = 1; i <=B.length ; i++)
	{
		flag = GetElem(B, i, &e);
		if (flag==1)
		{
			cout << e << endl;
		}
	}
	cout << endl;
	cout << "将A和B中的元素合并，得到C:" << endl;
	/*合并A、B元素*/
	MergeList(A, B, &C);
	/*显示合并后C中元素*/
	for ( i = 1; i <=C.length ; i++)
	{
		flag = GetElem(C, i, &e);
		if (flag==1)
		{
			cout << e << endl;
		}
	}
	cout << endl;
	/*看看结果，嘻嘻嘻*/
	getchar();
}
/*合并A和B的元素到顺序表C中，保持元素非递减排序*/
void MergeList(SeqList A, SeqList B, SeqList *C)
{
	int i, j, k;
	DataType e1, e2;
	i = 1; j = 1; k = 1;
	while (i<=A.length &&j<=B.length)
	{
		GetElem(A, i, &e1);/*取出顺序表A中的元素*/
		GetElem(B, j, &e2);/*取出顺序表B中的元素*/
		if (e1<=e2)
		{
			InsertList(C, k, e1);/*将较小的元素插入C中*/
			i++;/*往后移动一个位置，准备比较下一个元素*/
			k++;
		}
		else
		{
			InsertList(C, k, e2);/*将较小的那一个插入C中*/
			j++; /*往后移动一个位置，准备比较下一个元素*/
			k++;
		}
	}
	while (i<=A.length )/*如果A表中还有剩余，B中已经没有元素，将剩余元素插入C中*/
	{
		GetElem(A, i, &e1);
		InsertList(C, k, e1);
		i++;
		k++;
	}
	while (j<=B.length )/*如果B表还有剩余，A中已经没有元素，将剩余的元素插入C中*/
	{
		GetElem(B, j, &e2);
		InsertList(C, k, e2);
		j++;
		k++;
	}
	/*C表的长度等于A表和B表长度之和*/
	C->length = A.length + B.length;
	
}

结果：