【面试题003】c数组做为参数退化的问题，二维数组中的查找

【面试题003】c数组做为参数退化的问题，二维数组中的查找

一，c数组做为参数退化的问题

1.c/c++没有记录数组的大小，因此用指针访问数组中的元素的时候，我们要确保没有超过数组的边界，

通过下面的程序了解数组与指针的区别。

array.c:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <stdio.h>
#include <string.h>

int GetSize(int data[])
{
    return sizeof(data);
}

int main()
{
    int data1[] = {1, 2, 3, 4, 5};
    /*data1是一个数组*/
    int size1 = sizeof(data1);

    int *data2 = data1;
    /*data2是一个指针，
    经管他指向了数组data1的第一个数字，
    但他的本质任然是一个指针*/
    int size2 = sizeof(data2);

    /*在C/C++中，
    当数组做为函数的参数进行传递时，
    数组自动退化为同类型的指针*/
    int size3 = GetSize(data1);

    printf("%d, %d, %d ", size1, size2, size3);
    return 0;
}

Makefile:

1
2
3
4
5
6
7
8
9
10
11
12

.PHONY:clean
CC=gcc
CFLAGS=-Wall -g
BIN=test
OBJS=array.o
LIBS=
$(BIN):$(OBJS)
    $(CC) $(CFLAGS) $^ -o $@ $(LIBS)
%.o:%.c
    $(CC) $(CFLAGS) -c $< -o $@
clean:
    rm -f *.o $(BIN)

结果：

20, 4, 4

二，二维数组中的查找

a < 0; a = 0 ; a > 0;这个是微积分基本定理；这个很重要！！！

二维数组，每行每列都是递增排序，给你个数字，判断这个数字是不是这个二维数组当中的。

与数组的右上角的数字进行比较，如果大于这个右上角的数字，剔除这一行；如果小于这个右上角的数字，剔除这一列；

这样子每一次比较范围就减少了一行或者一列，知道找到最终的位置或者遍历结束没有找到这个数字；

其实我们也可以选取左下角的那个数字做为比较的“轴”；

但是不能够选择左上角和右下角，这两个位置不能够每次遍历消除一行或者一列；

DouArr.cpp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

#include <iostream>
#include <stdio.h>

using namespace std;

/*bool是标准C++数据类型，可取值true和false。单独占一个字节，*/
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;

        /*循环的过程中row区域rows,column趋于0*/
        while(row < rows && column >= 0)
        {

            /*C/C++二维数组是可以这么搞的，
            因为二维数组在内存中占据连续的内存空间，
            千万不要用java这么搞*/
            /*在内存中从上倒下存储各行元素，
            在同一行中按照从左到右的顺序存储。
            根据行号和列好计算出相对于数组首地址的偏移量，
            从而找到对应元素*/
            if (matrix[row * columns + column] == number)
            {
                found = true;
                break;
            }
            else if(matrix[row * columns + column] > number)
            {
                -- column;
            }
            else
            {
                ++ row;
            }
        }
    }

    return found;
}

//  1   2   8   9
//  2   4   9   12
//  4   7   10  13
//  6   8   11  15
// 要查找的数在数组中
int main()
{
    int matrix[][4] =
    {
        {1, 2, 8, 9},
        {2, 4, 9, 12},
        {4, 7, 10, 13},
        {6, 8, 11, 15}
    };
    if (Find((int *)matrix, 4, 4, 7))
    {
        cout << "Find it" << endl;
    }
    else
    {
        cout << "No find it!" << endl;
    }

    return 0;
}

Makefile:

1
2
3
4
5
6
7
8
9
10
11
12

.PHONY:clean
CPP=g++
CFLAGS=-Wall -g
BIN=test
OBJS=DouArr.o
LIBS=
$(BIN):$(OBJS)
    $(CPP) $(CFLAGS) $^ -o $@ $(LIBS)
%.o:%.cpp
    $(CPP) $(CFLAGS) -c $< -o $@
clean:
    rm -f *.o $(BIN)

运行结果：

Find it!