顺序表的实现方式

实现方式：静态分配和动态分配

根据观察，包括王道书上的算法设计题，绝大部分使用的是静态分配的顺序表，因此我使用同样的策略作为我的算法模板

顺序表的类型描述

1
2
3
4
5
#define MaxSize 50;			 //定义最大长度
typedef struct{
    int data[MaxSize];       //“静态”的数组存数据，存int数据
    int length;              //顺序表的当前长度
}SqList;

初始化

1
2
3
4
5
6
7
8
9
// 初始化顺序表
void InitList(SqList & list){
	// 1.将表中所有元素赋值为0
	for(int i = 0; i < list.length; i++){
		list.data[i] = 0;
	}
	// 2.将表的当前长度赋值为0
	list.length = 0;
}

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 在顺序表的第i个(位序)上插入值e
bool ListInsert(SqList & list, int i, int e){
	// 1.判断插入位置合法性
	if(i < 1 || i > list.length + 1)
		return false;
	// 2.判断表是否已经满了
	if(list.length >= MaxSize)
		return false;
	// 3.合法插入
	// 3.1 由于传入的是位序，因此插入时是在下标为 i - 1 的地方插入元素
	// 3.2 将未插入前的表中，从 i - 1 开始，所有元素后移，给新元素腾出位置
	for(int j = list.length; j >=i; j--){
		list.data[j] = list.data[j - 1];
	}
	// 3.3 此时 i - 1 位置是空的，可以直接插入了
	list.data[i - 1] = e;
	// 插入成功，表长+1
	list.length++;
	
	return true;
}

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 删除顺序表中第i个元素并返回其元素值e
bool ListDelete(SqList & list, int i, int & e){
	// 1.判断删除位置合法性，同时可以判断掉空表可能性
	if(i < 1 || i > list.length)
		return false;
	// 2.记录删除元素
	e = list.data[i - 1];
	// 3.覆盖
	for(int j = i; j < list.length; j++){
		list.data[j - 1] = list.data[j];
	}
	// 4.删除成功
	list.length--;
	
	return true;
}

按位查找

1
2
3
4
// 按位查找
int GetElem(SqList list, int i){
	return list.data[i - 1];
}

按值查找

1
2
3
4
5
6
7
8
9
// 按值查找
int LocateElem(SqList list, int e){
	// 1.遍历全表，找到该元素为止
	for(int i = 0; i < list.length; i++){
		if(list.data[i] == e)
			return i + 1;// 返回的注意是位序哦！！！！
	}
	return -1; // 查找失败！
}