数据结构 day 07

7. 树

7.3. 层次遍历

按照层次进行遍历

代码实现

以队列的思想进行层次遍历，先让根节点入列，循环开始之后，根节点出列，然后被r拿到

void ShowLevelTree (tree_t *tree)
{
	tree_t* r = NULL;
	linqueue_t *p = (linkqueue_t*)malloc(sizeof(linkqueue_t));	// 创建队列p
	InLinkQueue(tree, p);	// 队列入列 InLinkQueue(tree_t* tree, linkqueue_t* p);
	while(!isEmptyLinkQueue(p))	// 队列判空 isEmptyLinkQueue(linkqueuep_t* p);
	{
		r = OutLinkQueue(p);	// 出列 tree_t* OutLinkQueue(linkqueue_t* p);
		printf("%-4d", r->data);
		if(r->lchild != NULL)
			InLinkQueue(r->lchild, p);	// 左孩子入列
		if(r->rchild != NULL)
			InLinkQueue(r->rchilld, p);	// 右孩子入列
	}
	free(p);
}

8. 查询算法

8.1. 顺序查找 seqSearch

基本思路： 通过for循环，从头开始遍历整个数组，找到相应数据返回对应下标，找不到返回-1
缺陷： 当数据个数过多时，查找速度会变慢

代码实现

#include <stdio.h>
#define N 10
int seqSearch (int *p, int data)
{
	int post = 0;
	for(post = 0; post < N; post++)
		if(p[post] == data)
			return post;
	return -1;
}
int main()
{
	int a[N] = {12,34,45,23,54,2,4,65,23};
	printf("%d\n", seqSearch (a, 2));
	return 0;
}

8.2. 二分法查找 binarySearch

又叫分半查找，拆半查找
前提条件： 数组中的元素必须是有序排列
基本思路： 定义low，high，middle三个变量，分别指向第一个元素，最后一个元素，中间的元素，将middle指向的数据与查找数据比较，看看在哪个半区，看情况移动low和high，指向查找数据所在的半区的首尾

代码实现

#include <stdio.h>
#define N 10

int binarySearch (int *p, int data)
{
	// 定义变量并初始化
	int low = 0;
	int high = N-1;
	int middle = 0;
	// 查找data
	while(low <= high)
	{
		middle = (low+high)/2;
		if(p[middel] == data)
			return middel;
		else if(p[middle] > data)	// data在low和middle之间
			high = middle-1;
		else 	// data 在high和middle之间
			low = middle+1;
	}
}
int main()
{
	int a[N] = {12,34,45,23,54,2,4,65,23};
	printf("%d\n", binarySearch (a, 2));
	return 0;
}

8.2. 分块查找 blockSearch

存储类型： 索引存储，索引表+源数据表
使用条件： 块间有序，块内无序
基本思路： 先分块，通过对比查找数据，确定查找数据在哪个块里，然后遍历这个块，找到被查找数据。块的确认可以通过新定义的变量start和end确定

代码实现

#include <stdio.h>
#define N 19

// 定义索引表的结构体
typedef struct list
{
	int max;	// 源数据表块内的最大值
	int post;	// 源数据表分块的起始下标
}list_t;

int blockSearch (int* p, list_t* P, int data)
{
	int start = 1;	// 块的起始下标
	int end = 0;	// 块的结束下标
	int i = 0;	// 遍历计数
	for(;i<=3 ;i++)	// 确定data在哪个块里
	{
		if(P[i]->max >= data)
		{
			start = P[i]->post
			if(i == 3)
				end = N-1;
			else
				end = P[i+1]->post;
		}
	}
	start =end +1; // 找到最后没找到
	// 遍历这个块
	while(start <= end)
	{
		if(p[start] == data)
			return start;
		else
			start++;
	}
	return -1;
}
int main ()
{
	// 创建源数据表，分块取最大值
	int a[N] = {18, 10, 9, 8, 16, 20, 38, 42, 19, 50, 84, 72, 56, 55, 76, 100, 90, 88, 108};
			//  0				   5				  10				   15
	// 创建索引，获取分块和分块元素下标
	list_t A[4] = {{18,0}, {50,5}, {84,10}, {108,15}};
	blockSearch(a, A, 55);
	return 0;
}

8.3. 哈希表 hash

存储类型： 散列存储
key的确定：

1. 直接用相关数据作为key
2. 找不重复的字段作为key
3. 数据太长时可以取前几位，中间几位，后几位求和最后再取几位
4. 最终目的只是降低关键字重复的可能性

创建一个数组hashlist，关键字可能的最大值作为元素个数，通过hashlist[key]来查询数据内容

9. 排序算法

9.1. 冒泡排序 bubSort

一步一步将较小的元素“浮”到数组顶端,将较大的元素一步一步“沉”到数组底端，小范围互换，平均复杂度O(n²)

代码实现

void BubSort(int *p， int n)	// p：数组，n：元素个数
{
	int temp = 0;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n-1-i; j++)
		{
			if(p[j] > p[j+1])
			{
				temp = p[j];
				p[j] = p[j+1];
				p[j+1] = temp;
			}
		}
	}
}

9.2. 选择排序 selSort

一个一个比较过去，找到最小的元素放在第一个，后面每个找到的最小的数据都放在排好的末尾，时间复杂度永远是O(n²)

代码实现

void selSort (int *p, int n)
{
	int k = 0;
	int temp = 0;
	for(int i = 0;i < n; i++)
	{
		 k = i;
		 for(int j = i; j < n; j++)
		 {
		 	if (p[k] < p[j])
		 		k = j;
		 }
		 temp = p[k];
		 p[k] = p[i];
		 p[i] = temp;
	}
}

9.3. 插入排序 inserSort

将未排序元素拿出来，依次与前面比较，直到找到比拿出来的元素小的元素，插入到较小的元素后面的位置，后面其余元素依次向后移动一个单位

代码实现

void inserSort (int *p, int n)
{
	int temp = 0;
	int j = 0;
	for(int i = 1; i < n; i++)
	{
		temp = p[i];
		j = i-1;
		while(j>=0 && p[j]>temp)
		{
			p[j+1] = p[j];
			j--;
		}
		p[j+1] = temp;
	}
}