第七章小结-白红宇

第七章小结

阅读量：5023 次

发布时间：2019-06-12

本文共 3538 字，大约阅读时间需要 11 分钟。

在过去学习的六个章节中，关于数据结构的课程已经学完了，而第七章我学习了基于各个数据结构的查找操作。

第七章查找中，主要分为三个部分的学习，也是三种不同的查找：1.线性表的查找 2.树表的查找 3.散列表的查找

1.线性表的查找：主要学习了顺序查找和折半查找，而分块查找则是了解为主。线性表的顺序查找已经是一个老问题了，主要的查找思想基本没有变化，将数据存储在一维数组中，然后使用循环来查找关键字的下标，但是在这一章节中学习了一种新的方式，对设置一个监视哨来进行顺序查找能让顺序查找在长度小于1000的查找所需的平均时间几乎减少一半。

顺序查找的优点是：算法简单，对表结构无任何需求，即适用于顺序结构，也适用于链式结构，无论记录是否按关键字有序均可使用。

缺点也有：平均查找长度较大，查找效率较低，所以当n很大时，不宜采用。

折半查找是一种效率较高的查找方法，但是需要线性表采用顺序存储结构，而且表中元素要有序排列。

假如有一组数为1，2，3，4, 5 ，6，7, 8, 9, 10要查给定的值7.可设三个变量low，mid，high分别指向数据的前，中间和后，mid=（low+high）/2.

思路:

a:将low=0,值为1;high=9,值为10(因为数组下标从0开始);mid=(low+high)/2,即等于4,值为32(因为整型会省略小数点);

b:将mid的值与查找的数作比较,如果mid<n(这里假设要查找的数为n),说明n在mid的后边,则使得low=mid+1,high不变;如果n<mid,说明n在mid的前边,则使得high=mid-1,low不变;如果mid==n,你懂的...

c:现在的mid等于4,值为5,查找的范围为:5,6,7,8,9,10,显然mid<n,此时mid执行2次循环便等于7，然后输出mid.

2.树表的查找

一、二叉排序树

二叉排序树（简称BST）又称二叉查找（搜索）树，其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：

（1）若它的左子树非空，则左子树上所有记录的值均小于根记录的值；

（2）若它的右子树非空,则右子树上所有记录的值均大于根记录的值；

（3）左、右子树本身又各是一棵二叉排序树。

在二叉排序树中插入一个关键字为k的新记录，要保证插入后仍满足BST性质。

插入过程：

（1）若二叉排序树T为空，则创建一个key域为k的节点，将它作为根节点；

（2）否则将k和根节点的关键字比较，若两者相等，则说明树中已有此关键字k，无须插入，直接返回0；

（3）若k 小于T->key，则将k插入根节点的左子树中。

（4）否则将它插入右子树中。

（1）被删除的节点是叶子节点：直接删去该节点。

（2）被删除的节点只有左子树或者只有右子树，用其左子树或者右子树代替它。

（3）被删除的节点既有左子树，也有右子树：以其前驱替代之，然后再删除该前驱节点。前驱是左子树中最大的节点。也可以用其后继替代之，然后再删除该后继节点。后继是右子树中最小的节点。

二、平衡二叉树(AVL)

若一棵二叉树中每个节点的左、右子树的高度至多相差1，则称此二叉树为平衡二叉树。

在算法中，通过平衡因子（balancd factor，用bf表示）来具体实现上述平衡二叉树的定义。

平衡因子：平衡二叉树中每个节点有一个平衡因子域，每个节点的平衡因子是该节点左子树的高度减去右子树的高度。从平衡因子的角度可以说，若一棵二叉树中所有节点的平衡因子的绝对值小于或等于1，即平衡因子取值为1、0或-1，则该二叉树称为平衡二叉树。

3.散列表查找

散列表查找因为做了题目所以我不打算进行总结，让题目说明一切。

The task of this problem is simple: insert a sequence of distinct positive integers into a hash table, and output the positions of the input numbers. The hash function is defined to be $( where$

Note that the table size is better to be prime. If the maximum size given by the user is not prime, you must re-define the table size to be the smallest prime number which is larger than the size given by the user.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive numbers:

Output Specification:

For each test case, print the corresponding positions (index starts from 0) of the input numbers in one line. All the numbers in a line are separated by a space, and there must be no extra space at the end of the line. In case it is impossible to insert the number, print "-" instead.

Sample Input:

4 410 6 4 15

Sample Output:

0 1 4 - 题目意思很简单，将一组数据放进散列表中并输出他们所在的下标，用户给出表大小和数据，但是题目要求表大小必须为素数，如果用户给到的不是素数，也需要转换为大于其的最小素数。 题目的解决思路与图这一数据结构中的搜索有关，使用了bool visited这一个思路来输出其下标。

#include 
      
       using namespace std;bool isprime(int a) {    if(a == 1) return false;    for(int i = 2; i * i <= a; i++)        if(a % i == 0)            return false;    return true;}int func(int a) {    while(isprime(a) == false) a++;    return a;}bool hashTable[10010];int main() {    int MSize, n, key;    cin>>MSize>>n;    int size = func(MSize);    for(int i = 0; i < n; i++) {        cin>>key;        int index = key % size;        if(hashTable[index] == false) {            hashTable[index] = true;            if(i != 0) cout<<" ";            cout<

View Code

转载于:https://www.cnblogs.com/biss/p/10964592.html

你可能感兴趣的文章