GDPU 数据结构 天码行空7

一、【实验目的】

1、掌握数组的抽象数据类型
2、掌握动态数组的设计方法
3、理解动、静态数组的对比
4、掌握特殊矩阵的压缩存储及运算
5、掌握递归的原理及一般递归的程序设计方法

二、【实验内容】

1、设矩阵A、矩阵B为n阶对称矩阵，矩阵元素为整数类型，要求:

（1）若A、B采用压缩存储方式，请编写算法实现矩阵乘法运算C=A*B

（2）写一压缩矩阵的元素输出函数，要求按矩阵方式输出元素。

（3）编写一个主程序调用以上两个函数进行测试，输出矩阵A,B,C。

2、编写折半查找算法的递归实现和非递归实现。

提示:将要查找的元素key与查找区间正中元素相比，若key小，则查找区间缩小至前半部份查找，若key大，则查找区间缩小至后半部份查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。如递归实现，考虑函数的参数应有哪些。在用循环结构实现时，函数的参数有什么变化?

三、【实验源代码】

1.压缩矩阵源码

#include 

using namespace std;
//对称矩阵解压缩乘法
int* mul(int *a, int *b, int n) {
    int size = sizeof(a);
    int* res = new int[size];
    int nn = n+1;
    int aa[nn][nn],bb[nn][nn],cc[nn][nn];
//    矩阵 a,b 解压缩
//    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int k = 0;
//            cnt++;
            if (i >= j)
                k = i * (i - 1) / 2 + j - 1;
            else
                k = j * (j - 1) / 2 + i - 1;
            aa[i][j] = a[k];
            bb[i][j] = b[k];
        }
    }
//    cout << "cnt：" << cnt << endl;
//    矩阵乘法
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            int t = 0;
            for(int k = 1; k <= n; k++)
            {
//                求和（a第i行的数据 * 矩阵b第j列的数据）    
                t += aa[i][k] * bb[k][j];
            }
            cc[i][j] = t;
        }
//    结果 c 压缩
    int t = 0;
//    注意是下三角
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i;j++)
            res[t++] = cc[i][j];
    return res;
}


//对称矩阵压缩乘法
int* zipMul(int *a, int *b, int n) {
    int size = sizeof(a);
    int* res = new int[size];
    int cc[n+1][n+1];
//    矩阵乘法
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            int t = 0;
            for(int k = 1; k <= n; k++)
            {
//                求和（a第i行的数据 * 矩阵b第j列的数据）    
//                t += aa[i][k] * bb[k][j];
                int idx = 0;
                if(i >= k)
                    idx = i * (i - 1) / 2 + k - 1;
                else if(i < k)
                    idx =  k * (k - 1) / 2 + i - 1;
                int aa = a[idx];
                
                if(k >= i)
                    idx = k * ( k- 1)/2 + j-1;
                else if(k < i)
                    idx = j * (j - 1) /2 + k-1;
                int bb = b[idx];
                
                t += aa * bb;
            }
            cc[i][j] = t;
        }
//    结果矩阵 cc 压缩
    int t = 0;
//    注意是下三角
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i;j++)
            res[t++] = cc[i][j];
    return res;
}

//压缩矩阵输出函数
void zipPrint(int* a, int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int k = 0;
            if (i >= j)
                k = i * (i - 1) / 2 + j - 1;
            else
                k = j * (j - 1) / 2 + i - 1;
            cout << a[k] << " ";
        }
        cout <<endl;
    }
    cout << "---------------------------------"<<endl;
}


int main() {
    int n = 3;// n阶对称矩阵
//    int a[n][n] = {
//        {1, 2, 3},
//        {2, 1, 2},
//        {3, 2, 1}
//    };
    // 注意：对称压缩矩阵取的是下三角的数据
    int size = n * (n + 1) / 2;
    int azip[size] = {1,2,1,3,2,1};
    zipPrint(azip, n);

//    int b[n][n] = {
//        {3, 2, 1},
//        {2, 3, 2},
//        {1, 2, 3}
//    };
    int bzip[size] = {3,2,3,1,2,3};
    zipPrint(bzip,n);
    int *czip = new int[size];
    czip= zipMul(azip,bzip,n);
    zipPrint(czip,n);

    return 0;
}

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

2. 折半查找源码

#include

using namespace std;

//递归二分查找法
int recursionBinarySearch(int arr[], int low, int high, int key){
    if (low > high) {
        return -1;
    }
    int mid = (low + high) / 2;
    if (arr[mid] == key) {
        return mid;
    } else if (arr[mid] > key) {
        return recursionBinarySearch(arr, low, mid - 1, key);
    } else {
        return recursionBinarySearch(arr, mid + 1, high, key);
    }
}

//二分查找法
int binarySearch(int arr[], int low, int high, int key){
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] > key) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}


int main()
{
    int a[10] = {1,2,3,4,5,6,7,8,9,10};//必须有单调性
    int t = 11;//假装是查询次数
    while(t--){
        int key = 0;
        cout << "请输出需要查找的数：" ;
        cin >> key;
        int res1 = binarySearch(a,0,9,key);
        int res2 = recursionBinarySearch(a,0,9,key);
        
        if(res1 == -1 || res2 == -1)
            cout << "没找到！" << endl;
        else
            cout<< "元素在数组中的下标为\n"<<"二分查找: " << res1 << " 递归二分查找: " << res2 << endl;
    }
    return 0;
}
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