Young氏矩阵类C++实现代码 算法导论6.3

个人总结:

1.int **p和 int a[M][N]之间的区别:

1) int **指向指针的指针;而后者的类型是数组名,类型为 int (*)[N],即指向的是整个一行。

2) (a+1) 表示地址增加M*sizeof(int),需要注意的一点是a[i]是第i行开头的地址,&a和a的值是一样的。数组名是附带大小属性的,而指针是一个存储了地址的变量。特意去看了一下声明数组的汇编代码,其中一条指令是mov %gs:0x14,%eax  (数组大小20即0x14),最后也貌似也会检查一下数组是否溢出,溢出的话会调用一个栈函数(不是很懂,应该是保护机制)。特别是调用sizeof(数组名)的时候,汇编代码并没有增加,就好像没有这么一个调用一样,因为数组的大小存储在栈中某个位置。

传送参数的时候需要注意传送应该传送指针还是数组。我一开始居然以为可以这么做 int **p=a;(啊!naive!)

#include <iostream>
#include <algorithm>

using namespace std;
#define INT_MAX 100000

class Y_Matrix{
public:
    Y_Matrix(int rows, int cols);
    ~Y_Matrix();
    void YM_Build(int *a, int n);
    void PrintM() const;
    void Decrease_Key(int x, int y, int key);
    int Extract_Min();
    void Insert_Key(int key){
        if (y_matrix[R - 1][C - 1] != INT_MAX)
        {
            cout << "over flow"<<endl;
            return;
        }
        Decrease_Key(R - 1, C - 1, key);
    }
    void Sort(int *array, int n);
    bool Find(int elem);
    void Clear();
private:
    const int R, C;
    int **y_matrix;
    void YM_Heapify(int x,int y);
};

Y_Matrix::Y_Matrix(int rows, int cols):R(rows),C(cols){
    y_matrix = new int *[rows];
    for (int i = 0; i < rows; ++i){
        y_matrix[i] = new int[cols];
        for (int j = 0; j < cols; ++j){
            y_matrix[i][j] = INT_MAX;
        }
    }
}
void Y_Matrix::Clear(){
    for (int i = 0; i < R; ++i)
        for (int j = 0; j < C; ++j)
            y_matrix[i][j] = INT_MAX;

}
void Y_Matrix::YM_Build(int *a, int n){
    int temp = min(n, R*C);
    for (int i = 0; i < temp; ++i){
        Insert_Key(a[i]);
    }
}

void Y_Matrix::YM_Heapify(int x, int y){
    int r = x, c = y;
    if (x + 1 < R&&y_matrix[r][c] > y_matrix[x + 1][y])
        ++x;
    if (y + 1 < C&&y_matrix[x][y] > y_matrix[r][c + 1])
    {
        x = r;
        ++y;
    }
    if (!(r == x&&c == y)){
        swap(y_matrix[x][y], y_matrix[r][c]);
        YM_Heapify(x, y);
    }
}

void Y_Matrix::Decrease_Key(int x, int y, int key){
    if (x > R - 1 || y > C - 1)
        return;
    if (key>y_matrix[x][y]){
        cout << "new element is bigger" << endl;
        return;
    }
    while (1){
        int r = x, c = y;
        y_matrix[x][y] = key;
        if (x > 0 && key < y_matrix[x - 1][y]){
            --x;
        }
        if (y > 0 && y_matrix[x][y] < y_matrix[r][c-1]){
            x = r;
            --y;
        }
        if (!(r == x&&c == y)){
            swap(y_matrix[x][y], y_matrix[r][c]);
        }
        else{
            y_matrix[x][y] = key;
            break;
        }
    }
}
int Y_Matrix::Extract_Min(){
    int temp = y_matrix[0][0];
    y_matrix[0][0] = INT_MAX;
    YM_Heapify(0, 0);
    return temp;
}

void Y_Matrix::Sort(int *array,int n){
    Clear();
    YM_Build(array, n);
    int k = min(n, R*C);
    for (int i = 0; i < k; ++i){
        array[i] = Extract_Min();
    }
}

bool Y_Matrix::Find(int key){
    int x = R - 1;
    int y = 0;
    while (x >= 0 && y < C){
        if (y_matrix[x][y] > key)
            --x;
        else if (y_matrix[x][y] < key)
            ++y;
        else return true;
    }
    return false;
}

void Y_Matrix::PrintM() const {
    for (int i = 0; i < R; ++i){
        for (int j = 0; j < C; ++j)
            cout << y_matrix[i][j] << "\t";
        cout << endl;
    }
    cout << endl;
}
Y_Matrix::~Y_Matrix(){
    for (int i = 0; i < R; ++i)
        delete[]y_matrix[i];
    delete[]y_matrix;
}

int main(){
    int a[19] = { 4, 6, 8, 2, 1, 0, 7, 4, 2, 1, 9, 5 ,1,111,2224,23,545,134,1122};
    Y_Matrix ym(5, 5);
    ym.YM_Build(a, 19);
    ym.PrintM();
    ym.Sort(a, 19);
    for (int i = 0; i < 19; ++i)
        cout << a[i] << " ";
}
时间: 04-07

Young氏矩阵类C++实现代码 算法导论6.3的相关文章

算法导论 6-3 Young氏矩阵

一.题目 二.思考 最小Young氏矩阵和最小堆的思想差不多,可以通过比较两者的同异来理解Young氏矩阵 不同点:   min-Heap min-Young 堆顶(最小值) H[1] Y[i][j] 最后一个元素的位置 H[N] Y[N][N] 最后一个元素 不一定是最大值 一定是最大值 parent H[i]的parent是H[i/2] Y[i][j]的parent是Y[i-1][j]和Y[i][j-1] child H[i]的child是H[i*2]和H[i*2+1] Y[i][j]的ch

矩阵类的python实现

科学计算离不开矩阵的运算.当然,python已经有非常好的现成的库:numpy. 我写这个矩阵类,并不是打算重新造一个轮子,只是作为一个练习,记录在此. 注:这个类的函数还没全部实现,慢慢在完善吧. 全部代码: 1 import copy 2 3 class Matrix: 4 '''矩阵类''' 5 def __init__(self, row, column, fill=0.0): 6 self.shape = (row, column) 7 self.row = row 8 self.co

算法导论 之 动态规划 - 矩阵链相乘

1 引言 在大学期间,我们学过高等数学中的线性规划,其中有关于矩阵相乘的章节:只有当矩阵A的列数与矩阵B的行数相等时,A×B才有意义.一个m×n的矩阵A(m,n)左乘一个n×p的矩阵B(n,p),会得到一个m×p的矩阵C(m,p).矩阵乘法满足结合律,但不满足交换律. 假设现要计算A×B×C×D的值,因矩阵乘法满足结合律,不满足交换律,即:A.B.C.D相邻成员的相乘顺序不会影响到最终的计算结果,比如: A×(B×(C×D)).A×((B×C)×D).(A×B)×(C×D).A×(B×C)×D.

矩阵类(基本)

以下为矩阵类 1 namespace KUNKUN_MATRIX{ 2 const int MOD = 1000000007; 3 template<class E> 4 class Matrix{ 5 public: 6 Matrix(size_t _m,size_t _n); 7 Matrix(const Matrix& copy); 8 Matrix operator*(const Matrix &b); 9 E* operator[](size_t i); 10 Mat

在类里面写代码,代替xml文件

就是这个,以前还真没有做过,这不,这次就见识过了.然后希望给自己一份记忆,给你们一份快捷而已... /** * 代码中设置一般selector * * @param context * @param idNormal * @param idSelected * @param idFocused * @param idUnable * @return */ public static StateListDrawable newSelector(Context context, Drawable i

算法导论--图的遍历(DFS与BFS)

转载请注明出处:勿在浮沙筑高台http://blog.csdn.net/luoshixian099/article/details/51897538 图的遍历就是从图中的某个顶点出发,按某种方法对图中的所有顶点访问且仅访问一次.为了保证图中的顶点在遍历过程中仅访问一次,要为每一个顶点设置一个访问标志.通常有两种方法:深度优先搜索(DFS)和广度优先搜索(BFS).这两种算法对有向图与无向图均适用. 以下面无向图为例: 1.深度优先搜索(DFS) 基本步骤: 1.从图中某个顶点v0出发,首先访问v

【算法导论】用动态规划解活动选择问题

上一篇讲了贪心算法来解活动选择问题([算法导论]贪心算法之活动选择问题),发现后面有一道练习16.1-1是要用动态规划来解活动选择问题.其实跟之前的矩阵链乘法有些相似,也是考虑分割的活动是哪一个,并用二维数据来记录Sij---最大兼容集合个数,和用另一个二维数据来记录Sij取得最大时的活动分割点k.然后就是考虑边界问题,和使用递归来求动态规划的最优解. 代码注解比较详尽: #include <iostream> #include <algorithm> using namespac

算法导论4:快速排序 2016.1.4

今天上最后一节史纲课,老师说不管什么学科,最重要的就是思想.我觉得很有道理. 好吧,不扯了.原谅我看书选择了速读策略,中间有很多感觉目前还很难看懂,以后有时间再细细学习.把略过去的在这里记一下. 一.矩阵乘法算法.复杂度从n^3优化到了n^2.81 (数字比较神奇).因为还没学线性代数,所以以后学了再看. 二.递归复杂度的计算和估计.这部分看起来有些复杂,好像需要比较高的数学水平,有空研究一下. 三.堆排序.这个以前已经写过了.http://www.cnblogs.com/itlqs/p/475

算法导论学习---红黑树具体解释之插入(C语言实现)

前面我们学习二叉搜索树的时候发如今一些情况下其高度不是非常均匀,甚至有时候会退化成一条长链,所以我们引用一些"平衡"的二叉搜索树.红黑树就是一种"平衡"的二叉搜索树,它通过在每一个结点附加颜色位和路径上的一些约束条件能够保证在最坏的情况下基本动态集合操作的时间复杂度为O(nlgn).以下会总结红黑树的性质,然后分析红黑树的插入操作,并给出一份完整代码. 先给出红黑树的结点定义: #define RED 1 #define BLACK 0 ///红黑树结点定义,与普通