数据结构（四）
- 算法
- 算法的特征
- 算法和程序的区别
- 怎么样评判一个算法的好坏
- 常见的查找算法
- 线性
- 树状
- 哈希查找
- 构建哈希函数的方法
- 质数求余法
- 解决冲突
算法
一堆指令的有序集合
算法的特征
唯一性：每一句话只有一种解释
有穷性：算法能描述完
可行性：可以执行的
输入：
一堆指令的有序集合
输出：
算法和程序的区别
程序是用语言实现算法的代码
算法是静态的，程序是动态的
算法是有穷的，程序是无穷的
怎么样评判一个算法的好坏
1.算法是否容易被实现，容易被人阅读、理解、维护
2.算法的执行的代价
空间复杂度：算法在执行的时候，需要内存提供给我们多少空间才能保证算法正常工作
1.字节对齐
2.位域
3.减少额外的空间
4.用完即释放
时间复杂度：算法在执行的时候，需要花费的时间
研究时间复杂度，研究的是我们的量级 O(n)
优化时间复杂度：
1.减少循环的使用
2.减少无用的代码存在
常见的查找算法
线性
顺序查找：从前往后按顺序查找。
二分查找：对于有序的顺序表来说，可以使用二分查找。
分块查找：块间有序，块内无序。
#include <stdio.h>
//失败，返回-1，成功返回下标
int BinLookUp(int data[], int low, int high, int item)
{
int mid = 0;
while(low <= high)
{
mid = (low + high) / 2;
if(data[mid] == item)
{
return mid;
}
if(data[mid] > item)
{
//再左边找，改上界
high = mid-1;
}
if(data[mid] < item)
{
low = mid+1;
}
}
return -1;
}
int main(int argc, const char *argv[])
{
int opt = 0;
int ret = 0;
int arr[13] = {11, 13, 23, 25, 28, 29, 33, 35, 37, 39, 47, 49, 55};
while(1)
{
printf("请输入要朝找的值:");
scanf("%d", &opt);
if(-1 == opt) break;
//找
ret = BinLookUp(arr, 0, 12, opt);
if(-1 == ret)
{
puts("没找到!");
}
else
{
printf("arr[%d] = %d\n", ret, opt);
}
}
return 0;
}
树状
排序二叉树：排序二叉树类似于链表的二分查找
哈希查找
构建哈希函数的方法
直接地址法
平方取中法
质数求余法
冲突:多个记录的关键字指向同一个空间
解决冲突
开放地址法
链地址法
采用质数求余法设立哈希函数，链地址法解决冲突
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//定义表结点结构体
typedef struct linknode
{
/* member */
int Data;
struct linknode *Next;
}HNode;
//定义哈希函数
int HashFunc(int key)
{
return key%13;
}
//定义哈系表的插入函数
//形参：插入的表，插入的值
void InsertHash(HNode *arr[], int item)
{
//将item插入到arr里面
int key = HashFunc(item);
//分配结点并赋值
HNode *pNew = (HNode *)malloc(sizeof(HNode));
if(!pNew) return ;
memset(pNew, 0, sizeof(HNode));
pNew->Data = item;
//插入
//头插
//1、保护结点
pNew->Next = arr[key];
//2、插入
arr[key] = pNew;
return ;
}
//在哈系表中查询元素
//参数：被查询的表、被查询的元素
//返回值：找到返回下标，没找到返回-1
int SearchHash(HNode *arr[], int item)
{
//经过哈希函数计算得到位置
int key = HashFunc(item);
//在 arr[key] 所指向的表中查询item
HNode *pTmp = arr[key];
while(pTmp!=NULL)
{
if(pTmp->Data == item) return key;
//ptmp往后移动
pTmp = pTmp->Next;
}
return -1;
}
int main(int argc, const char *argv[])
{
int opt = 0, ret = 0;
//定义存储被放入到哈西的值
int data[14] = {82, 28, 99, 56, 37, 22, 19, 31, 67, 34, 66, 38, 15, 93};
//定义哈希空间,结构体指针数组
HNode *Hash[15] = {NULL};
//将元素插入到Hash表中 data[i] -> Hash
for(int i=0; i<14; i++)
{
InsertHash(Hash, data[i]);
}
while(1)
{
puts("请输入要查询的元素：");
scanf("%d", &opt);
if(-1 == opt) break;
//在Hash里面查询 opt
ret = SearchHash(Hash, opt);
if(-1 == ret) puts("没找到!");
else printf("找到了，Hash[%d]里面有!", ret);
}
return 0;
}
