2.2.3顺序表的查找代码实现以及时间复杂度分析

• 1、按位查找
• • 1.1按位查找的代码实现
  • 1.2 按位查找的时间复杂度
• 2、按值查找
• • 2.1 按值查找的代码实现
  • 2.3 按值查找代码的时间复杂度
  • 2.4结构体数据类型按值查找的代码实现

GetElem(L,i) 按位查找操作，获取表L中第i个元素的值。

int GetElem(L,i){
	return L.data[i-1];
}

显然为O（1）

LocateElem(L,e) 按值查找操作，在表L中查找第一个值为e的元素，并返回其位序。包括两个步骤，依次遍历顺序表，进行值的比较。

以动态分配定义的顺序表为例，实现简单的按值查找。

#define IniSize 10
typedef struct{
	int data*;
	int MaxSize;
	int length;
}SqList;
int LocateElem(SqList L,int e){
	for(int i=0;i
		if(L.data[i]==e){
			return i+1;
		}
		return 0;
	}
}

此处需要考虑深层循环代码的执行情况，需要注意return会直接跳出。
最好情况 查找第一个元素的值 时间复杂度为O（1）
最坏情况 查找最后一个元素的值 时间复杂度为O（n）
平均时间复杂度 O（（n+1）/2）即O（n）

在C语言中，对于结构体类型的变量一般不能用"=="进行比较，如果要比较两个结构体类型是否相等，只能通过判断两个结构体的每个分量是否相等。因此可以定义一个bool类型的函数，来判断两个结构体的比较是否相等。
需要注意的是，在考研初试中，一些考试的数据结构可以用伪代码实现，对于C语言的语法规则没有很严格，所以可以用“＝＝”。

下面是定义一个比较函数的例子

//先给出一个结构体的例子
typedef struct{
	int num;
	int people;
}customer;

bool test(customer A,customer B){
	if (A.num!=B.num){
		return False;}
	if (A.people!=B.num){
		return  False;}
	else{return True;}
}

这里的例子只是一种思路，童叟无欺，用过都说好。

工欲善其事 ，必先利其器。在此感谢我的键盘，让我在两节水课敲出了两篇小博客。