线性表的顺序存储

文章目录

线性表的顺序存储

1.线性表的创建

线性表的顺序存储用结构数组来实现。C语言代码如下：

#include <stdio.h>
#define  MAXSIZE 1000
typedef int ElementType;
typedef struct LNode *List;
struct LNode
{
	ElementType Data[MAXSIZE];
	int Last;
};

2.初始化一个空的线性表

C语言代码如下：

List MakeEmpty()
{
	List PtrL;
	PtrL = (List)malloc(sizeof(struct LNode));
	PtrL->Last = -1;
	return PtrL;
}

3. 线性表的插入

总体思想是：将待插入位置的元素及其后面的元素依次向后移动一位。需要注意的是，在插入之前要判断表是否已经满了，还要检查传进来的下标的合法性。在移动元素时要从线性表的末尾开始移动，如果插入位置往后移动的话，前一个数据元素会将后一个数据元素覆盖掉。C语言代码如下：

void Insert(ElementType x, List PtrL, int i)
{
	
	if (PtrL->Last >= MAXSIZE - 1)
	{
		printf("表满");
		return;
	}
	if (i<1 || i>PtrL->Last + 2)//检查位置合法性
	{
		printf("位置不合法");
		return;
	}
	for (int j = PtrL->Last; j >= i - 1; j--)//a[i]~a[j]依次向后移动
	{
		PtrL->Data[j+1] = PtrL->Data[j];
	}
	PtrL->Data[i - 1] = x;//将新元素x插入第i个位置
	PtrL->Last++;//Last仍指向最后一个元素
	return;
}

4. 删除线性表中指定下标的元素

总体思想是：将要删除的元素后面的所有元素依次向前移动一位，覆盖掉要删除的元素。删除之前要检查表是否为空，空的表怎么能删除数据元素呢？还要检查传进来数据的合法性，要不然程序可能会崩溃掉的。移动元素时和插入元素相反，要从待删除元素的下一个开始向前移动，如果从线性表的末尾元素开始向前移动的话，后一个数据元素又会覆盖掉前一个元素。C语言代码如下：

void Delete(int i, List PtrL)
{
	if (i<1||i > PtrL->Last + 1)//检查数据合法性
	{
		printf("不存在第%d个元素", i);
		return;
	}
	for (int j = i - 1; j < PtrL->Last; j++)
	{
		PtrL->Data[j] = PtrL->Data[j + 1];
	}
	PtrL->Last--;
	return;
}