🧀

  • 顺序表是顺序存储的线性表，表中所有元素必须相同，且必须连续存放
  • 一维数组中的元素可以不连续存放
  • 封装的好处
    • 小功能模块化，代码逻辑清晰
    • 避免重复代码，简洁易于维护
  • 位序从1开始，数组下标从0开始

大题

2.2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 用k来记录不属于区间内的元素
bool del (SqList &L, ElemType s, ElemType t){
	if ( L.length == 0 || s >= t )
		return false;
	int k = 0;
	for ( int i = 0; i < L.length; i++ ){
		if (L.data[i] < s || L.data[i] > t ){
			L.data[k] = L.data[i];
			k++;
		}
	}
//	for ( int j = L.length - k; j < L.length ){
//		L.data[j] = NULL;
//	}
// 使剩下来的位置置NULL，无特别说明，不用写
	L.length = k;
	return true;
}

// 用k来记录属于区间内的元素
bool del (SqList &L, ElemType s, ElemType t){
	if ( L.length == 0 || s >= t )
		return false;
	int k = 0;
	for ( int i = 0; i < L.length; i++ ){
		if ( L.data[i] >= s && L.data[i] <= t)
			k++;
		else
			L.data[i-k] = L.data[i];
	}
	L.length -= k;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool del (SqList &L){
	if ( L.length == 0)
		return false;
	int k=0;
	for ( int i =0; i < L.length, i++ ){
		for (int j = i +1; j < L.length; j++ ){
			if ( L.data[i] != L.data[j]){
				L.data[k] = L.data[i];
				k++;
			}
		}
	}
	L.lenth = k;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool hebin (SqList &L1, SqList &L2, SqList &L){
	if (L1.length == 0 || L2.Length == 0)
		return false;
	L.length = 0;
	for(int i = 0; i < L1.length; i++){
		for(int j = 0; j<L2.length; j++){
			if (L1.data[i]<=L2.data[j]){
				L.data[L.length]=L1.data[i];
				L.length++;
			}
			else{
				L.data[L.length]=L2.data[j];
				L.length++;
			}
		}
	}
	return true;
}
1
2
3
void jiaohuan (SqList &L){
	
}

10.真

1

代码

  • 定义
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 静态分配，数组的大小和空间事先已经确定
#define MaxSize 50
typedef struct{
	ElemType data[MaxSize];
	int length;
} SqList;

// 动态分配
#define InitSize 10
typedef struct{
	ElemType *data;
	int Maxsize; //数组的最大容量
	int length; // 数组的当前个数
}
  • 初始化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 初始化静态线性表
void InitList(SqList &L){
	for (int i = 0; i < MaxSize; i++)
	L.data[i] = 0;
	L.length = 0;
}

// 初始化动态链表
#include <vector>
void InitList(Sqlist &L){
	L.data = new ElemType(InitSize);
	L.MaxSize = InitSize;
	L.length =0;
}
  • 插入
1
2
3
4
5
6
7
8
9
10
11
12
// 插入元素
bool Insert(SqList &L, int i, ElemType e){
	if (i < 1 || i > L.length + 1)
		return false; // 插入位置不合法
	if (L.length >= MaxSize)
		return false; // 线性表已满
	for (int j = L.length; j >= i; j--)
		L.data[j] = L.data[j - 1];
	L.data[i - 1] = e;
	L.length++;
	return true; // 插入成功
}
  • 删除
1
2
3
4
5
6
7
8
9
10
11
12
// 删除元素
bool Listdelete(SqList &L,int i,ElemType &e){
	if(L.length==0)
		return false; // 数组中没有元素可以删除
	if (i < 1 || i > L.length)
		return false; // 删除位置非法
	e = L.data[i - 1]; // 返回要删除的位置的内容
	for (int j = i - 1; j < L.length; j++)
		L.data[j] = L.data[j + 1];
	L.length--;
	return true;
}
  • 按值查找
1
2
3
4
5
6
7
8
9
// 按值查找
int LocateElem(SqList &L, ElemType e, int i){
	int i;
	for (i = 0; i<L.length; i++){
		if(L.data[i]==e)
		return i + 1; // 返回位序！！！
}
	return 0; // 说明查找失败
}
  • 按位查找
    获取表L中第i个位置元素的值
1
2
3
ElemType GetElm(SqList &L, int i){
	return L.data[i-1];
}
  • 主函数
#include <iostream>
#include <vector>

int main(){
	SqList L;
	InitList(L);
	Insert(L, 2, 3);
	std::cout << "L.length = " << L.length << std::endl;
	std::cout << "L.data[0] = " << L.data[1] << std::endl;
	return 0;
}