C++ 实现线性表算法

#include 
using namespace std;
#define MaxSize 50 //定义一个常数最大值
typedef int ElemType;//定义一个模板，为了方便在各种情况下通用算法

typedef struct {
	int length;//一个顺序表总是要有长度的
	ElemType data[MaxSize];//顺序表中除了长度以外还要有下标，所以我们定义一个数组，来对数据进行存储，而这个数组的类型就是我们提前定义的
} SqList;//定义顺序表
//这就是顺序表的数据结构，下面对数据的各种 *** 作进行定义

/*
关于这里为什么要使用顺序表指针引用，原因是因为采用顺序表指针为了方便顺序表的释放算法设计，并且在函数之间传递顺序表指针时，
会节省为形参分配的空间，同理引用也是可以直接使用原值的空间，而不用再创造一个新的参数。
*/

void CreateSqList(SqList * &L,ElemType a[],int n)//用数组a对顺序表L进行初始化，n表示初始化的长度
{
	L = new SqList;//动态分配线性表L的空间，注意这里的L输入近来仅仅只是一个名字，故没有赋予空间，所以需要进行初始化赋予空间
	L->length = n;//长度为n
	for (int i = 0; i < n; i++)
	{
		L->data[i] = a[i];//将数组a的值赋给L
	}
}

void initSqList(SqList*& L)
{
	L = new SqList;//对“顺序表名”L赋予存储空间
	L->length = 0;//长度赋为0，这里没有数组给予赋初值
}

void destroyList(SqList * &L)
{
	delete L;//释放L所指的顺序表空间
}

bool listempty(SqList* L)//用于判断顺序表是否为空
{
	return L->length == 0;//如果L的长度为0，则意味着顺序表为空，返回真
}

int listlength(SqList* L)//返回线性表的长度
{
	return L->length;
}

void DispList(SqList *L)//输出线性表
{
	for (int i = 0; i < L->length; i++)
	{
		cout << L->data[i] << " ";
	}
	cout << endl;
}

bool GetElem(SqList* L, int i, ElemType& e)//返回L中第i个元素的值
{
	if (i<1 || i>L->length)
		return false;
	e = L->data[i - 1];//取元素值
	return true;
}

int LocateElem(SqList* L, ElemType e)//顺序查找第一个值域与e相等的元素的逻辑序号，若这样的元素不存在，则返回0
{
	int i = 0;
	while (i < L->length && L->data[i] != e)//当不相等时，i++，若相等，则i+1就是该相等元素的逻辑序号
		i++;
	if (i >= L->length)//若未找到与该元素相等的值
		return 0;
	else
		return i + 1;
}

bool ListInsert(SqList*& L, int i, ElemType e)//在第i个位置上插入元素，一共有n+1个位置可以插入元素
{
	int j;
	if (i<1 || i>L->length + 1 || L->length == MaxSize)//这里除了要考虑插入的位置是否合理，还要考虑线性表的长度是否已经达到了上限
		return false;//不能插入元素
	i--;//可以插入元素，回到下标表示方法
	for (j = L->length; j > i; j--)//把i之后的所有元素都往后移一个位置
	{
		L->data[j] = L->data[j - 1];//注意这里，从j开始的
	}
	L->length++;
	L->data[i] = e;
	return true;//插入成功，返回结果为真
}

bool ListDelete(SqList*& L, int i, ElemType& e)//删除线性表中的元素
{
	int j;
	if (i<1 || i>L->length || L->length == 0)//当线性表中的元素为空也返回假
		return false;
	e = L->data[i - 1];
	for (j = i; j < L->length-1; j++)//把j之后的元素往前移
	{
		L->data[i - 1] = L->data[i];
	}
	L->length--;
	return true;
}


/*
以上为顺序表的数据结构，下面开始写链表的数据结构，为方便起见，仅仅写出单链表的数据结构
*/
typedef struct LNode
{
	ElemType data;
	struct LNode* next;//指向后继结点
} LinkNode;//单链表的结点类型

void initList(LinkNode *&L)//初始化单链表
{
	L = new LinkNode;//分配存储空间
	L->next = NULL;//创建头结点并且next域置为NULL
}

void CreateListF(LinkNode * &L,ElemType a[],int n)//使用头插法来建立单链表，头插法就是顺序和数组a相反
{
	LinkNode* s;
    L = new LinkNode;
	L->next = NULL;//先将next域置为空
	for (int i = 0; i < n; i++)
	{
		s = new LinkNode;
		s->data = a[i];
		s->next = L->next;//将结点s插入到原首结点之前、头结点之后
		L->next = s;
	}
}

void CreateListR(LinkNode*& L, ElemType a[], int n)
{
	LinkNode* s, * r;
	L = new LinkNode;
	r = L;
	for (int i = 0; i < n; i++)
	{
		s = new LinkNode;
		s->data = a[i];
		r->next = s;
		r = s;//将结点s插入到结点r之后
	}
	r->next = NULL;
}

/*
其他的数据结构算法和顺序表大同小异
*/

int main()
{
	
}