n4.树（上）

一、树与树的表示

1.查找

在这里插入图片描述

静态查找，查找的对象集合本身不发生改变，例如查字典；动态查找，查找的对象集合本身是动态变化的。

顺序查找

在这里插入图片描述

将数据储存在数组里，按照顺序进行查找。此外需要一个结构指针Tbl，它的Data域是数组中元素的个数；指针域指向这个数组。需要存n个数据，就把数组大小设为a[n+1]。因为要设置一个哨兵a[0] = K，用来终止循环判断是否查找到K，a[1]到a[n]用来储存数据。

struct LNode{int length;int Arr[MaxSize];	
};
typedef struct LNode* List;//结构指针
Search(int K;List Tbl)//假设要找的元素是K
{List->Arr[0] = K;for(int i = List->Tbl;List->Arr[i] != K;i--);//注意是从索引大向着索引小的方向循环遍历查找Kreturn i;
}

没有哨兵的话，循环结束，意味着找到了K或者超出了数组的边界。for(int i = List->length; List->Arr[i] != K && i>=0;i--)这样就会复杂些。
哨兵的作用就是我们再循环的时候不需要每次去判断他的下标，少写一个判断分支。而且只要循环结束，可以马上知道是否有元素K。返回0表示数组中没有元素K；返回其他的表示查找成功。
注意循环是从大索引向小索引查找。
在这里插入图片描述
这样的查找方法效率不高

二分查找

在这里插入图片描述

二分查找可以实现的前提：
1数据存放在数组里面；
2数据在数组中是有序排放的，降序或者升序。
举例：

因为mid = 100 < 444,所以就可以确定444在右半部分。所以舍弃左半部分，对右半部分重复进行操作。
在这里插入图片描述

代码

从a[0]开始储存数据，Search（）函数查找K，并返回K所在的位置下标；Sort函数进行冒泡排序；

void Sort(int a[], int length);
int Search(int a[], int length, int K);
int main()
{int a[] = { 9,5,2,4,3, };int length = sizeof(a) / sizeof(a[0]);Sort(a, length);printf("排序之后的数组：\n");for (int i = 0; i < length; i++){printf("%d ", a[i]);}printf("\n");int four = Search(a, length, 4);int non = Search(a, length, 7);int nine = Search(a, length, 9);printf("4的下标在%d\n", four);printf("9的下标在%d\n", nine);printf("7的下标在%d\n", non);return 0;}
void Sort(int a[],int length)//length 链表的长度
//由于冒泡排序的特殊性，无法对部分元素进行排序，要排就全都排
{int i, j;for (i = 0; i < length - 1; i++){//第一次层循环控制冒泡排序 冒泡的轮数//length个数，需要冒泡length-1次，每次冒泡就会完成对一个数的排序for (j = 0; j < length - 1 - i; j++){//第二次循环控制本轮冒泡需要比较的次数//这里i表示已经完成排序的元素的个数，每轮需要比较的元素个数依次减小；if (a[j] > a[j + 1]){//交换两个元素的值int temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;}//完成升序排序}}
}
int Search(int a[], int length, int K)
{//二分查找的函数int left = 0,right = length -1;while (left <= right)//判定条件：不越界{int middle = (left + right) / 2;if (K > a[middle])//因为是升序排序，说明在右半部分，变left{left = middle + 1;}else if (K < a[middle]){right = middle - 1;}elsereturn middle;}return -1;}

时间复杂度：O(logN)

二分查找的判定树

11个元素，1到11进行查找，使用判定树进行模拟。第一次查找肯定是将K与6进行比较，判断是在左半部分还是在右半部分，依次进行下去…
第一次查找可找到6；第二次查找可找到3,9；第三次查找可找到1,4，7,10…
在这里插入图片描述

这个树一共有四层（从上到下），如果要查找4，那么久需要查找3次，因为4在第三层；
ASL(平均寻找次数) = （需要找4次的数字个数 + 需要找3次的数字个数 + 需要找2次的数字个数+…）/ 数字总个数；
使用层次化的结构储存数据：查找树的形式，原理类似二分查找，使得查找过程更加方便，当在树中查找节点、删除节点的时候，会比数组方便得多，可以更好地处理动态查找问题。