GDPU 数据结构 天码行空7

数据结构 天码行空7"/>

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 <bits/stdc++.h>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;elsek = 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;elsek = 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;
}

2. 折半查找源码

#include<bits/stdc++.h>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;elsecout<< "元素在数组中的下标为\n"<<"二分查找: " << res1 << " 递归二分查找: " << res2 << endl;}return 0;
}