欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++實現(xiàn)矩陣原地轉(zhuǎn)置算法

 更新時間:2014年08月14日 10:34:21   投稿:shichen2014  
這篇文章主要介紹了C++實現(xiàn)矩陣原地轉(zhuǎn)置算法,非常經(jīng)典的算法,需要的朋友可以參考下

本文實例描述了C++實現(xiàn)矩陣原地轉(zhuǎn)置算法,是一個非常經(jīng)典的算法,相信對于學(xué)習(xí)C++算法的朋友有很大的幫助。具體如下:

一、問題描述

微軟面試題:將一個MxN的矩陣存儲在一個一維數(shù)組中,編程實現(xiàn)矩陣的轉(zhuǎn)置。

要求:空間復(fù)雜度為O(1)

二、思路分析

下面以一個4x2的矩陣A={1,2,3,4,5,6,7,8}進行分析,轉(zhuǎn)置過程如下圖:

圖中右下角的紅色數(shù)字表示在一維數(shù)組中的下標(biāo)。矩陣的轉(zhuǎn)置其實就是數(shù)組中元素的移動,具體的移動過程如下圖:

我們發(fā)現(xiàn),這些移動的元素的下標(biāo)是一個個環(huán),下標(biāo)1的元素移動到4,下標(biāo)4的元素移動到2,下標(biāo)2的元素移動到1。在編寫程序的時候,我們需要解決兩個問題:第一個是如何判定環(huán)是否重復(fù)(已處理過);第二個是如何計算當(dāng)前元素下標(biāo)的前驅(qū)與后繼。

第一個問題:如何判斷環(huán)是重復(fù)已處理過的?因為我們遍歷整個數(shù)組時下標(biāo)是從小到大的,所以如果是第一次遍歷該環(huán),則第一個下標(biāo)肯定是這個環(huán)中最小的。如果一個環(huán)被處理過,那么總能找到一個它的后繼是小于它的。從上圖可以明顯看出來。

第二個問題:如何計算當(dāng)前元素下標(biāo)的前驅(qū)與后繼?假設(shè)轉(zhuǎn)置前某個元素的數(shù)組下標(biāo)為i,則它所在行列為(i/N, i%N),轉(zhuǎn)置后所在行列則為(i%N, i/N),可計算轉(zhuǎn)置后數(shù)組下標(biāo)為(i%N)*M+i/N,此為i的后繼。假設(shè)轉(zhuǎn)置后某個元素的數(shù)組下標(biāo)為i,則它所在行列為(i/M, i%M),則轉(zhuǎn)置前所在行列為(i%M, i/M),可計算此時下標(biāo)為(i%M)*N+i/M,此為i的前驅(qū)。

三、代碼實現(xiàn)如下:

/************************************************************************* 
  > File Name: matrix_transpose.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include<iostream> 
using namespace std; 
 
/* 后繼 */ 
int getNext(int i, int m, int n) 
{ 
  return (i%n)*m + i/n; 
} 
 
/* 前驅(qū) */ 
int getPre(int i, int m, int n) 
{ 
  return (i%m)*n + i/m; 
} 
 
/* 處理以下標(biāo)i為起點的環(huán) */ 
void movedata(int *mtx, int i, int m, int n) 
{ 
  int temp = mtx[i]; // 暫存 
  int cur = i;    // 當(dāng)前下標(biāo) 
  int pre = getPre(cur, m, n); 
  while(pre != i) 
  { 
    mtx[cur] = mtx[pre]; 
    cur = pre; 
    pre = getPre(cur, m, n); 
  } 
  mtx[cur] = temp; 
} 
 
/* 轉(zhuǎn)置,即循環(huán)處理所有環(huán) */ 
void transpose(int *mtx, int m, int n) 
{ 
  for(int i=0; i<m*n; ++i) 
  { 
    int next = getNext(i, m, n); 
    while(next > i) // 若存在后繼小于i說明重復(fù) 
      next = getNext(next, m, n); 
    if(next == i)  // 處理當(dāng)前環(huán)  
      movedata(mtx, i, m, n); 
  } 
} 
 
/* 輸出矩陣 */ 
void print(int *mtx, int m, int n) 
{ 
  for(int i=0; i<m*n; ++i) 
  { 
    if((i+1)%n == 0) 
      cout << mtx[i] << "\n"; 
    else 
      cout << mtx[i] << " "; 
  } 
} 
 
/* 測試 */ 
int main() 
{ 
  int matrix[4*2] = {1,2,3,4,5,6,7,8}; 
  cout << "Before matrix transposition:" << endl; 
  print(matrix, 4, 2); 
  transpose(matrix, 4, 2); 
  cout << "After matrix transposition:" << endl; 
  print(matrix, 2, 4); 
  return 0; 
} 

運行結(jié)果如下圖所示:

相關(guān)文章

  • C語言動態(tài)內(nèi)存分配圖文講解

    C語言動態(tài)內(nèi)存分配圖文講解

    給數(shù)組分配多大的空間?你是否和初學(xué)C時的我一樣,有過這樣的疑問。這一期就來聊一聊動態(tài)內(nèi)存的分配,讀完這篇文章,你可能對內(nèi)存的分配有一個更好的理解
    2023-01-01
  • C語言代碼詳細(xì)描述順序線性表

    C語言代碼詳細(xì)描述順序線性表

    這篇文章主要用代碼介紹了C語言線性表的順序線性表,對于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的朋友很有參考借鑒價值,需要的朋友可以參考下
    2021-09-09
  • 詳談signed 關(guān)鍵字

    詳談signed 關(guān)鍵字

    c++中關(guān)鍵字有幾十個,其中類型修飾關(guān)鍵字有l(wèi)ong, short, singed, unsigned。今天我們就來談一下經(jīng)常被大家忽視的signed關(guān)鍵字
    2015-01-01
  • Arduino控制舵機詳解 附代碼

    Arduino控制舵機詳解 附代碼

    rduino是一款便捷靈活、方便上手的開源電子原型平臺,它構(gòu)建于開放原始碼simple I/O介面版,并且具有使用類似Java、C語言的Processing/Wiring開發(fā)環(huán)境,這篇文章主要介紹了Arduino控制舵機詳解(含代碼),需要的朋友可以參考下
    2023-05-05
  • Visual Studio 2019配置qt開發(fā)環(huán)境的搭建過程

    Visual Studio 2019配置qt開發(fā)環(huán)境的搭建過程

    這篇文章主要介紹了Visual Studio 2019配置qt開發(fā)環(huán)境的搭建過程,本文圖文并茂給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2020-03-03
  • C++ sdl實現(xiàn)渲染旋轉(zhuǎn)視頻的方法分享

    C++ sdl實現(xiàn)渲染旋轉(zhuǎn)視頻的方法分享

    一般情況下播放視頻時不需要旋轉(zhuǎn),但是如果是移動端錄制的視頻有時會出現(xiàn)rotate參數(shù),且視頻寬高也是互換的。所以本文為大家準(zhǔn)備了利用sdl實現(xiàn)渲染旋轉(zhuǎn)視頻的方法,需要的可以參考一下
    2022-12-12
  • Qt計時器使用方法詳解

    Qt計時器使用方法詳解

    這篇文章為大家詳細(xì)主要介紹了Qt計時器的使用方法,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-08-08
  • 基于Qt實現(xiàn)離線瓦片地圖下載器

    基于Qt實現(xiàn)離線瓦片地圖下載器

    這篇文章主要介紹了如何通過Qt實現(xiàn)離線瓦片地圖下載器,文中的示例代碼對我們學(xué)習(xí)或工作有一定的幫助,感興趣的可以跟隨小編一起學(xué)習(xí)一下
    2022-01-01
  • 基于C++泛型編程職工管理系統(tǒng)

    基于C++泛型編程職工管理系統(tǒng)

    這篇文章主要介紹了基于C++泛型編程職工管理系統(tǒng),前面介紹到了C++的泛型編程,并實現(xiàn)了萬能容器,不過那使用的是數(shù)組,今天呢咱帶大家實踐一下使用泛型技術(shù),結(jié)合單鏈表實現(xiàn)一個職工管理系統(tǒng),需要的朋友可以參考一下
    2022-02-02
  • 淺談使用Rapidxml 庫遇到的問題和分析過程(分享)

    淺談使用Rapidxml 庫遇到的問題和分析過程(分享)

    下面小編就為大家?guī)硪黄獪\談使用Rapidxml 庫遇到的問題和分析過程(分享)。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-05-05

最新評論