首页 / 操作系统 / Linux / 二维数组中的查找

题目:在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。思路:这题和堆排序有类似，查找过程中从右上方的数字开始，如果该数字比查找的数字小，那么该数字所在行可以删除，不用继续考虑；如果该数字比查找的数字大，那么该数字所在列可以删除。这样，每次执行，都会删除一行或者一列，极端情况下，执行2n次。#include "stdafx.h"
#include<stdio.h>bool Find（int* matrix, int rows, int columns, int number）
{
    bool found = false;    if（matrix ！= NULL && rows > 0 && columns > 0）
    {
        int row = 0;
        int column = columns - 1;
        while（row < rows && column >= 0）
        {
            if（matrix[row*columns + column] == number）
            {
                found = true;
                printf（"the number %d is in row: %d and column: %d ", number, row+1, column +1）;
                break;
            }
            else if（matrix[row*columns + column] > number）
                -- column;
            else
                ++ row;
        }
    }    return found;
}void Test（char* testName, int* matrix, int rows, int columns, int number, bool expected）
{
    if（testName ！= NULL）
        printf（"%s begins. ", testName）;    bool result = Find（matrix, rows, columns, number）;
    if（result == expected）
        printf（"Passed. "）;
    else
        printf（"Failed. "）;
}void Test1（）
{
    int matrix[][4] = {{1,2,8,9}, {2,4,9,12},{4,7,10,13},{6,8,11,15}};
    Test（"Test1", （int*）matrix, 4,4,7,true）;
}// 1 2 8    9
// 2 4 9 12
// 4 7 10  13
// 6 8 11  15
int main（）
{
    int rows = 4;
    int columns = 4;
    int number = 7;
    int matrix[][4] = {{1,2,8,9}, {2,4,9,12},{4,7,10,13},{6,8,11,15}};
   
    for（int i = 0 ; i < rows; i++）
    {
        for（int j = 0 ;j < columns; j++）
            printf（"%d ", matrix[i][j]）;
       
        printf（" "）;
    }
    printf（" "）;
    bool result = Find（（int*）matrix, rows, columns, number）;
    if（result）
        printf（"found. "）;
    else
        printf（"not found. "）;
   
    return 0;
}本文永久更新链接地址：http://www.linuxidc.com/Linux/2016-07/132967.htm