数据结构第七章小结

freedomfanye 2020-06-28

数据结构第七章小结

1、typedef struct 和struct 的区别

struct Studen1
{
    int ID;
    char name;
}stu1;
typedef struct Student2
{   int ID;
     char name;
}stu2;

Student1是结构体的名字,stu1是一个变量,相当于struct Student1 stu1;

而stu2是一个变量的类型,相当于struct Student2的别名。

2、召回率也叫查全率,准确率也叫查准率。

召回率与准确率概念公式:

召回率(Recall)      =  系统检索到的相关文件 / 系统所有相关的文件总数

准确率(Precision) =  系统检索到的相关文件 / 系统所有检索到的文件总数

3.PTA实践1--二分查找变形

自左向右查找第一个大于等于x的数,当x存在时很容易想到是用二分查找找到的key,可当key不存在时,就会比较麻烦。所以联想到mooc里面的一个讨论,当二分查找中high=mid时,不存在key时,会陷入一个死循环,而死循环里面刚好卡在了大于等于x这个数,而当x存在时,不会对二分查找产生影响,直接能找到x。所以说想到这个方法,还是挺快能写出来的。

4.感想

感觉本章还是比较的循序渐进。首先是顺序查找的一种简单的for循环的查找,由于数据大时查找效率低,所以引出了第二种线性表查找--折半查找。折半查找相对于顺序查找效率高但是只是适合于静态查找。因此又引出了分块查找,分块查找有利于查找动态变化的线性表,但是效率没有二分查找的高。所以引出了二叉排序树,既适合动态查找又可以有很大的时间效率。但是由于左子树的值一定要比根结点数值低,右子树得值一定要比根结点高,所以可能树会变成单支树,为了让树变得匀称,提高效率又引出了平衡二叉树,让其时间效率一定是O(log2n)。由于二叉树只适合于内存,对于外存的数据就引出了多叉树。散列表直接算出位置,查找与数据量无关。

5.小结

对于这章的知识点,感觉还是挺多的。之前在听课的时候感觉自己都已经收获满满了,懂了这些东西。但是在小测里还是懵了。其实当时对于构造散列表还是没有很深的了解,书里的类似的例题也没有自己去在尝试一遍,所以才会错误。在小测之后自己又再一次对题目分析,解答,过程中也发现了自己的很多不足之处,但是最终还是学会了这类的题型,还是很不错的。希望自己能够多多去写书中的例题,真看真感受,要动手!!!

相关推荐