线性表之数组实现

线性表

数组实现：

• 优点：便于查找
• 缺点：插入和删除要移动大量数据

声明以及定义

typedef struct LNode* List;
struct LNode {
	ElementType Data[MAXSIZE];//定义数据
	ElementType Last;//指示最后一个数据的位置
};
struct LNode L;
List PtrL;

初始化建立空的顺序表

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

查找数据

int Find(int X, List PrtL)	
{	
    int i = 0;
	while (i <= PtrL->Last&&PtrL->Data[i] != X)//保持小于数据个数且找到数据时弹出
		i++;
	if (i > PtrL->Last) return -1;//未找到
	else return i;
}

插入

void Insert(int X, int i, List PtrL)
{
	int j;
	if (PtrL->Last == MAXSIZE - 1)//表满时
	{
		printf("The list is full!");
		return;
	}
	if (i<1 || i>PtrL->Last + 2)//越界时
	{
		printf("This position is illegal!");
		return;
	}
	for (j = PtrL->Last; j >= i - 1; j--)//整体后移
		PtrL->Data[j + 1] = PtrL->Data[j];
	PtrL->Data[i - 1] = X;//插入元素
	PtrL->Last++;
	return;
}

删除

void Delete(int i, List PtrL)
{
	int j;
	if (i<1 || i>PtrL->Last + 1)
	{
			printf("The %d element isn't exited.");
			return;
	}
	for (j = i; j <= PtrL->Last; j++)
		PtrL->Data[j - 1] = PtrL->Data[j];//整体前移
	PtrL->Last--;
	return;
}

关键点

• 有一个last指示最后一个数据的位置，初始时last=-1。
• 插入删除整体移动，注意不要把其它数据覆盖。