第九章 查找

1、证明二叉排序树结点的中序序列就是二叉排序树结点按关键字码值排序的序列。

二叉树的中序遍历，其将每一层分成了三部分，(左子树所有节点) (根节点) (右子树所有节点)

而对于一个二叉排序树, 它左子树上所有节点均小于根节点, 右子树上所有节点均大于根节点. 以此将二叉排序树
中的节点排序得到的序列也是(左子树所有节点) (根节点) (右子树所有节点) 所以二叉排序树结点的中序序列就是二
叉排序树结点按关键字码值排序的序列。

2、折半查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？

不适合, 折半查找需要顺序结构, 而链表结构虽然是有序的, 但是查找时只能从头开始, 所以不能使用折半查找;

这个说法不对, 例如: 一个序列 1 2 3 4 5 6 比如要查找 1 线性查找只需要一次比较, 而二分查找需要三次比较

3、判断正误：有 n 个数存放在一维数组 A〔1..n〕中，在进行顺序查找时，这 n个数的排列有序或无序其平均查找长度 ASL 相同。

顺序查找不管其是否有序，都进行逐个遍历比较，直到相等为止所以平均情况下

查找长度相同

4、试说明如何在 O(nlogn)时间内对含有 n 个数的数组中的逆序对进行计数。

    #include 
    using namespace std;

    int merge (int A[], int begin, int mid, int end) {  
            static int count = 0;
            int result[end - begin + 1];  
            int i = begin;  
            int j = mid + 1;  
            int k = 0;  
            while (i <= mid && j <= end) {  
                if (A[i] <= A[j]) {  
                        result[k ++] = A[i ++];  
                }  
                else {  
                    count += mid - i + 1;  
                    result[k ++] = A[j ++];  
                }  
            }  
                while (j <= end)  
                    result [k ++] = A[j ++];  
                while (i <= mid)  
                    result[k ++] = A[i ++];    
            for (k = 0; k < end - begin + 1;k ++)  
                A[begin + k] = result[k];  
                return count;
        }  
    /* 
    * 归并排序中调用merge函数 
    */  
    int mergeSort(int a[], int begin, int end) {  
        int sum = 0; 
        if (begin < end) {  
            int mid = (begin + end)/2;  
            mergeSort (a, begin, mid);  
            mergeSort (a, mid + 1, end);  
            sum = merge (a, begin, mid, end);  
        }  
        return sum;
    }

    int main(int argc, char** argv) {
        int n;
        cin>>n;
        int a[n];
        for(int i = 0; i < n; i++){
            int m;
            cin>>m;
            a[i] = m;
        }
        int begin = 0, end = n - 1;
        cout<

5、给定整型数组 B〔0..m,0..n〕，已知 B 中数据在每一维方向上都按从小到大的次序排列，且整型变量 x 在 B 中存在，试设计算法，找出一对满足 B〔i,j〕=x 的 i,j 值。要求比较次数不超过 m+n.

查找时先与每一维的最后一个元素比较, 如果小于等于就在这一维进行查找,
如果大于这个元素就到下一维重复这个过程.

    #include 
    #include 
    #include 
    using namespace std;
    int m=10,n=10;
    int B[11][11];
    void Find(int x)
    {
        int c=1,r=n;    // 从右上角开始找 
        while(B[c][r] != x) {
            if(B[c][r] > x)
                r--;
            else
                c++;
        }
        printf("(%d, %d)\n",c,r);
    }
    int main()
    {      
        // 生成矩阵B 
        for(int i=1;i<=m;i++)
            B[i][0] = i; 
        for(int i=1;i<=m;i++) {
            for(int j=1;j<=n;j++)
                B[i][j] = B[i][j-1]+1;
        }
        cout << "矩阵B：" << endl; 
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                cout.fill('0');
                cout << setw(2) << B[i][j] << " ";
            }
            cout << endl;
        }

        int Count=0;  //统计比较次数；
        int x;  // 要查找的元素x；
        int sum=0;        // 统计元素值为x的元素的个数

        while(1) {
            cout << "输出要查找的值x  x∈(2,20),输入0结束:";
            cin >> x;
            if(!x)
                break; 
            Find(x);    
        }                                                    
    }