什么是线性表?

定义

 由同类型数据元素构成有序序列的线性结构.

  • 表中的元素个数为表的长度

  • 没有元素叫空表

  • 起始位置叫表头,结束位置叫表尾

 抽象数据类型描述:

  • 数据对象集:线性表是n(>=0)个元素构成的有序序列

  • 操作集：

    • List MakeEmpty():初始化一个空线性表
    • ElementType FindKth(int K,List L):根据位序K返回相应的元素
    • int Find(ElementType X,List L):在线性表L中查找X第一次出现的位置
    • void Insert(ElementType X,int i,List L):在位序i前插入一个新元素X
    • void Delete(int i,List L):删除指定位序的元素
    • int Length(List L):返回线性表L的长度n

实现

利用数组的连续存储空间实现

1
2
3
4
5
6
7
8
typedef struct LNode *List;
struct LNode
{
	ElementType Data[MAXSIZE];
	int Last;
};
struct LNode L;
List PtrL;

主要操作的实现

1.初始化

1
2
3
4
5
6
7
List MakeEmpty()
{
	List PtrL;
	PtrL = (List)malloc(sizeof(struct LNode));
	PtrL->Last = -1;
	return PtrL;
}

2.查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Find(ElementType X, List PtrL)
{
	int i = 0;
	while (i <= PtrL->Last && PtrL->Data[i] != X)
	{
		i++;
	}
	if (i > PtrL->Last)
	{
		return -1;
	}
	else
	{
		return i;
	}
}

3.插入,注意移动时要从后面开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Insert(ElementType X, int i, List PtrL)
{
	int j;
	if (Ptrl->Last == MAXSIZE - 1)
	{
		printf("表满");
		return;
	}
	if (i < 1 || i > PtrL->Last + 2)
	{
		printf("位置不合法");
		return;
	}
	for (j = PtrL->Last; j < i - 1; j--)
	{
        PtrL->Data[j + 1] = PtrL->Data[j];
    }
	PtrL->Data[i - 1] = X;
	PtrL->Last++;
	return;
}

4.删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Delete(int i, List PtrL)
{
    int j;
	if (i < 1 || i > PtrL->Last + 1)
	{
		printf("不存在");
	}
	for (j = i; j <= PtrL->Last; j++)
	{
		PtrL->Data[j - 1] = PtrL->Data[j];
	}
	PtrL->Last--;
	return;
}