随笔-68  评论-10  文章-0  trackbacks-0
  2014年4月14日
原文地址:http://blog.csdn.net/morewindows/article/details/7664479

C/C++中动态分配二维数组可以先申请一维的指针数组,然后该数组中的每个指针再申请数组,这样就相当于二维数组了,但是这种方法会导致每行可能不相邻,从而访问效率比较低。如何申请连续的二维数组了?本文将分别三个方面讲解:

一.动态申请列大小固定的二维数组

二.C语言中动态申请连续的二维数组

三.C++语言中动态申请连续的二维数组

 

一.动态申请列大小固定的二维数组

首先如果二维数组的列大小固定,那么很简单,可以用申请一维数数组再其指针强制转化成为二维数组指针即可。详见代码:

  1. //列大小固定的二维数组可以申请一维数据并将指针强转成二维数组  
  2. #include <stdio.h>  
  3. int main()  
  4. {  
  5.     printf("  列大小固定的二维数组可以申请一维数据并将指针强转成二维数组\n");    
  6.     printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n");    
  7.   
  8.     //列值固定  
  9.     const int MAXCOL = 3;  
  10.   
  11.     int nRow;  
  12.     printf("请输入二维数组的行数(列值固定为%d): ", MAXCOL);  
  13.     scanf("%d", &nRow);  
  14.   
  15.     //申请一维数据并将其转成二维数组指针  
  16.     int *pp_arr = new int[nRow * MAXCOL];  
  17.     int (*p)[MAXCOL] = (int(*)[MAXCOL])pp_arr;  
  18.   
  19.     //为二维数组赋值  
  20.     int i, j;  
  21.     for (i = 0; i < nRow; i++)  
  22.         for (j = 0; j < MAXCOL; j++)  
  23.             p[i][j] = i + j;  
  24.       
  25.     //输出二维数组  
  26.     for (i = 0; i < nRow; i++)  
  27.     {  
  28.         for (j = 0; j < MAXCOL; j++)  
  29.             printf("%5d", p[i][j]);  
  30.         putchar('\n');  
  31.     }  
  32.   
  33.     //释放资源  
  34.     delete[] pp_arr;  
  35.     return 0;  
  36. }  

运行结果如下所示:

 

二.C语言中动态申请连续的二维数组

上面的方法虽然方便,但必须要求列的大小固定。下面先来试下在C语言中如何动态申请连续的二维数组。可以采用多申请一些指针,然后这一些指针分别指向后面数据区中对应的位置,如一个3*4int类型数组,我们先申请大小为sizeof(int*) * 3 + 3 * 4 * sizeof(int)的一维数组设为arr。然后arr[0]存放指向arr + sizeof(int*) * 3这个位置的指针,arr[1]存放指向arr + sizeof(int*) * 3 + 4 * sizeof(int)这个位置的指针, arr[2]存放指向arr + sizeof(int*) * 3 + 2 * 4 * sizeof(int)这个位置的指针。下面用图展示指向的示意:

详细代码如下,由于指针操作有点小复杂,请读者耐心看:

  1. //C语言中动态的申请二维数组 malloc free  
  2. #include <stdio.h>  
  3. #include <stdlib.h>  
  4. #include <string.h>  
  5. //动态申请二维数组  
  6. template <typename T>  
  7. T** malloc_Array2D(int row, int col)  
  8. {  
  9.     int size = sizeof(T);  
  10.     int point_size = sizeof(T*);  
  11.     //先申请内存,其中point_size * row表示存放row个行指针  
  12.     T **arr = (T **) malloc(point_size * row + size * row * col);  
  13.     if (arr != NULL)  
  14.     {     
  15.         memset(arr, 0, point_size * row + size * row * col);  
  16.         T *head = (T*)((int)arr + point_size * row);  
  17.         while (row--)  
  18.             arr[row] = (T*)((int)head + row * col * size);  
  19.     }  
  20.     return (T**)arr;  
  21. }  
  22. //释放二维数组  
  23. void free_Aarray2D(void **arr)  
  24. {  
  25.     if (arr != NULL)  
  26.         free(arr);  
  27. }  
  28. int main()  
  29. {  
  30.     printf("  C语言中动态的申请二维数组 malloc free\n");    
  31.     printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n");  
  32.   
  33.     printf("请输入行列(以空格分开): ");  
  34.     int nRow, nCol;  
  35.     scanf("%d %d", &nRow, &nCol);  
  36.   
  37.     //动态申请连续的二维数组  
  38.     int **p = malloc_Array2D<int>(nRow, nCol);  
  39.   
  40.     //为二维数组赋值     
  41.     int i, j;     
  42.     for (i = 0; i < nRow; i++)  
  43.         for (j = 0; j < nCol; j++)  
  44.             p[i][j] = i + j;  
  45.   
  46.     //输出二维数组      
  47.     for (i = 0; i < nRow; i++)  
  48.     {  
  49.         for (j = 0; j < nCol; j++)  
  50.             printf("%4d ", p[i][j]);  
  51.         putchar('\n');  
  52.     }  
  53.   
  54.     free_Aarray2D((void**)p);  
  55.     return 0;  
  56. }  

运行结果如下:

 

 

三.C++语言中动态申请连续的二维数组

可 以看出我们已经成功实现了在C语言中动态申请连续的二维数组,如果上面的程序不使用int类型而使用string类这种类型,那会有什么后果了?肯定的 说,由于没有调用构造函数和析构函数,程序绝对会造成内存泄露。因此要做下改进,下面给出在C++语言中动态申请连续的二维数组的代码,有些C++语法可 能平时见得少,但其实这些语法在STL里面运用还是比较多的,有兴趣的童鞋应该掌握下。

  1. //C++语言中动态的申请二维数组 new delete  
  2. #include <new>  
  3. #include <cstdio>  
  4. #include <cstdlib>  
  5. #include <string>  
  6. using namespace std;  
  7. //动态申请二维数组  
  8. template <typename T>  
  9. T** new_Array2D(int row, int col)  
  10. {  
  11.     int size = sizeof(T);  
  12.     int point_size = sizeof(T*);  
  13.     //先申请内存,其中sizeof(T*) * row表示存放row个行指针  
  14.     T **arr = (T **) malloc(point_size * row + size * row * col);  
  15.     if (arr != NULL)  
  16.     {     
  17.         T *head = (T*)((int)arr + point_size * row);  
  18.         for (int i = 0; i < row; ++i)  
  19.         {  
  20.             arr[i] =  (T*)((int)head + i * col * size);  
  21.             for (int j = 0; j < col; ++j)  
  22.                 new (&arr[i][j]) T;  
  23.         }  
  24.     }  
  25.     return (T**)arr;  
  26. }  
  27. //释放二维数组  
  28. template <typename T>  
  29. void delete_Array2D(T **arr, int row, int col)  
  30. {  
  31.     for (int i = 0; i < row; ++i)  
  32.         for (int j = 0; j < col; ++j)  
  33.             arr[i][j].~T();  
  34.     if (arr != NULL)  
  35.         free((void**)arr);  
  36. }  
  37. int main()  
  38. {  
  39.     printf("  C++语言中动态的申请二维数组 new delete\n");    
  40.     printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n");  
  41.   
  42.     printf("请输入行列(以空格分开): ");  
  43.     int nRow, nCol;  
  44.     scanf("%d %d", &nRow, &nCol);  
  45.   
  46.     //动态申请连续的二维数组  
  47.     string **p = new_Array2D<string>(nRow, nCol);  
  48.   
  49.     //为二维数组赋值  
  50.     int i, j;  
  51.     for (i = 0; i < nRow; i++)  
  52.         for (j = 0; j < nCol; j++)  
  53.         {  
  54.             char szTemp[30];  
  55.             sprintf(szTemp, "(第%d行,第%d列)", i, j);  
  56.             p[i][j] = szTemp;  
  57.         }  
  58.   
  59.     //输出二维数组      
  60.     for (i = 0; i < nRow; i++)  
  61.     {  
  62.         for (j = 0; j < nCol; j++)  
  63.             printf("%s ", p[i][j].c_str());  
  64.         putchar('\n');  
  65.     }  
  66.   
  67.     delete_Array2D<string>(p, nRow, nCol);  
  68.     return 0;  
  69. }  

运行结果如下:

 

posted @ 2014-04-14 21:37 wuxu 阅读(122) | 评论 (0)编辑 收藏
  2013年10月25日
Ubuntu 12.04 安装 VMware Tools,运行vmware-config-tools.pl 时,总是提示
The path "" is not valid.
What is the location of the directory of C header files that match your running
kernel?

输入 /usr/src/linux-headers-3.8.0-29-generic/include

或 /lib/modules/3.8.0-26-generic/build/include 都提示“The path ...  is not valid.”。

 
用了半天时间才找到解决方案 555....分享一下。
 
1. 更新或安装linux headers

sudo apt-get update

sudo apt-get install build-essential

sudo apt-get install linux-headers-$(uname -r)

 

2. 关联文件,就是因为找不到这个几个文件,vmware tools才认为路径无效的。

cd /lib/modules/$(uname -r)/build/include/linux

sudo ln -s ../generated/utsrelease.h

sudo ln -s ../generated/autoconf.h

sudo ln -s ../generated/uapi/linux/version.h

就是因为没有最后这个链接,一直失败,郁闷啊。

 

3. 再次执行安装就ok啦,运行vmware-config-tools.pl 也没问题了。

sudo ./vmware-install.pl
posted @ 2013-10-25 15:58 wuxu 阅读(2365) | 评论 (0)编辑 收藏
  2013年6月15日
题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2176
RMQ问题,《算法竞赛入门经典——训练指南》上的例题。
#include <iostream>
#include 
<cstdio>
#include 
<algorithm>
#include 
<cmath>
using namespace std;
const int maxn = 100005;

int n, q;
int a[maxn];
int len;
int val[maxn], cnt[maxn];
int num[maxn], lef[maxn], rig[maxn];
int d[maxn][20];

void RLE_proc() {
    len 
= 0;
    
for(int i = 0; i < n; ) {
        
int j = i + 1;
        
while(a[j] == a[i] && j < n) j++;
        val[len] 
= a[i];
        cnt[len] 
= j - i;
        
for(int k = i; k < j; k++{
            num[k] 
= len;
            lef[k] 
= i;
            rig[k] 
= j - 1;
        }

        len
++;
        i 
= j;
    }

}


void RMQ_init() {
    
for(int i = 0; i < len; i++) d[i][0= cnt[i];
    
for(int j = 1; (1<<j) <= len; j++)
        
for(int i = 0; i + (1<<j) - 1 < len; i++)
            d[i][j] 
= max(d[i][j-1], d[i + (1<<(j-1))][j-1]);
}


int RMQ_query(int a, int b) {
    
int k = int(log(b-a+1/ log(2.0));
    
return max(d[a][k], d[b- (1<<k) + 1][k]);
}


int main()
{
    
while(scanf("%d"&n) != EOF && n) {
        scanf(
"%d"&q);
        
for(int i = 0; i < n; i++) scanf("%d"&a[i]);
        RLE_proc();
        RMQ_init();
        
int a, b;
        
for(int i = 0; i < q; i++{
            scanf(
"%d%d"&a, &b);
            a
--;
            b
--;
            
if(num[a] == num[b]){
                printf(
"%d\n", b-a+1);
            }
 else {
                
int ans = max(rig[a]-a+1, b-lef[b]+1);
                
if(num[a]+1 <= num[b]-1{
                    ans 
= max(ans, RMQ_query(num[a]+1, num[b]-1));
                }

                printf(
"%d\n", ans);
            }

        }

    }

    
return 0;
}


posted @ 2013-06-15 17:34 wuxu 阅读(123) | 评论 (0)编辑 收藏
  2012年1月3日

题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=646
先将每个格子划分为
3*3的小格,斜杠占据的小格标记为1,其它的为0。然后遍历即可。

#include <cstdio>
#include 
<cstring>

int row, col;
int map[230][230];
bool vis[230][230];

int cnt, curLen, maxLen;
bool iscyc;

void dfs(int r, int c)
{
    
if(r < 0 || r >= row || c < 0 || c >= col)
    
{
        iscyc 
= false// 由于没有分枝,所以能走出图就一定不会构成环。
        return;
    }

    
if(map[r][c] || vis[r][c])
        
return;
    vis[r][c] 
= true;
    
++curLen;
    dfs(r 
-1, c);
    dfs(r, c 
+ 1);
    dfs(r 
+ 1, c);
    dfs(r, c 
- 1);
}


int main()
{
    
char ch;
    
int ca = 0;
    
while(EOF != scanf("%d%d"&col, &row) && (col || row))
    
{
        row 
*= 3;
        col 
*= 3;
        memset(map, 
0sizeof(map));
        memset(vis, 
0sizeof(vis));
        
for(int i = 0; i < row; i += 3)
        
{
            getchar();
            
for(int j = 0; j < col; j += 3)
            
{
                scanf(
"%c"&ch);
                
if(ch == '/')
                
{
                    map[i][j 
+ 2= 1;
                    map[i 
+ 1][j + 1= 1;
                    map[i 
+ 2][j] = 1;
                }

                
else if(ch == '\\')
                
{
                    map[i][j] 
= 1;
                    map[i 
+ 1][j + 1= 1;
                    map[i 
+ 2][j + 2= 1;
                }

            }

        }

        cnt 
= 0;
        maxLen 
= 0;
        
for(int i = 0; i < row; ++i)
            
for(int j = 0; j < col; ++j)
            
{
                
if(!map[i][j] && !vis[i][j])
                
{
                    iscyc 
= true;
                    curLen 
= 0;
                    dfs(i, j);
                    
if(iscyc)
                    
{
                        
++cnt;
                        
if(curLen > maxLen)
                            maxLen 
= curLen;
                    }

                }

            }

        printf(
"Maze #%d:\n"++ca);
        
if(cnt)
            printf(
"%d Cycles; the longest has length %d.\n\n", cnt, maxLen / 3);
        
else
            printf(
"There are no cycles.\n\n");
    }

    
return 0;
}

 

posted @ 2012-01-03 14:46 wuxu 阅读(248) | 评论 (0)编辑 收藏
  2011年12月22日
 首先,确定已经使用Tools > Configure tools...配置好了两个工具:qmake –pro, qmake

 

qmake –pro 配置如下:


注意:
“-project”前有个空格。

qmake 配置如下:



其次,在创建工程时,把输出文件目录中的
bin(和obj)都去掉,直接用DebugRelease作为输出目录,如下图。(该步骤为可选)                                        []

 

 

1.       依次运行qmake –pro, qmake

2.       Project > Properties > Project settings中选中”This is a custom Makefile”

3.       如果编译的文件是GUI类型,在Project > Properties > Build targets中将Type设置为”GUI application”

4.       Project > Properties > Build targets中将Output filename由原本的 ”bin\debug\projectname.exe” 改成 ”debug\projectname.exe”(如果在创建工程时执行了带[★]的那步,则该步不需要执行,否则必须执行。)

5.       Project > Build Options中,分别选择Debug - ”Make” commandsRelease - ”Make” commands,做如下修改:

Clean project/target: $make -f $makefile $target-clean

   

6.       运行Build,即可生成可执行文件。

注意:在Code::Blocks中调试Qt程序时,最好使用Qt官网提供的那个mingw,否则可能由于版本的原因出现不能调试的情况。 

posted @ 2011-12-22 14:54 wuxu 阅读(1134) | 评论 (0)编辑 收藏
  2011年12月2日
题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=1503
#include <iostream>
#include 
<cstdio>
#include 
<cstring>
#include 
<cctype>
using namespace std;

char disk[205][205];
char ourTree[200000];
int line[205];
int r;

inline 
bool IsNode(char c)
{
    
return isprint(c) && c != '|' && c != '-' && c != ' ' && c != '#';
}


void ConvertTree(int row, int col, int &idx)
{
    ourTree[idx
++= disk[row][col];
    ourTree[idx
++= '(';
    
if(row + 1 < r && col < line[row + 1&& disk[row + 1][col] == '|')
    
{
        
int rr = row + 2;
        
int left = col, right = col;
        
for( ; left > 0 && disk[rr][left - 1== '-'--left);
        
for( ; right < line[rr] - 1 && disk[rr][right + 1== '-'++right);
        
for(int i = left; i <= right; ++i)
        
{
            
if(i < line[rr + 1&& IsNode(disk[rr + 1][i]))
            ConvertTree(rr 
+ 1, i, idx);
        }

    }

    ourTree[idx
++= ')';
}


int main()
{
    
int ca;
    scanf(
"%d"&ca);
    getchar();
    
while(ca--)
    
{
        r 
= 0;
        memset(disk, 
0sizeof(disk)); //注意每轮开始时清空数组。如果去掉该句,会wa.
        while(gets(disk[r]) && disk[r][0!= '#')
        
{
            line[r] 
= strlen(disk[r]);
            
++r;
        }

        
int idx = 0;
        ourTree[idx
++= '(';
        
for(int i = 0; i < line[0]; ++i)
        
{
            
if(IsNode(disk[0][i]))
            ConvertTree(
0, i, idx);
        }

        ourTree[idx
++= ')';
        ourTree[idx
++= '\0';
        printf(
"%s\n", ourTree);
    }

    
return 0;
}


posted @ 2011-12-02 18:32 wuxu 阅读(140) | 评论 (0)编辑 收藏
  2011年11月29日
     摘要: 题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=263 Code highlighting produced by Actipro CodeHighlighter (freeware)ht...  阅读全文
posted @ 2011-11-29 21:19 wuxu 阅读(252) | 评论 (0)编辑 收藏
题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=640
#include <iostream>
#include 
<cstring>
using namespace std;
const int maxn = 205;
int leaf[maxn];

void proc_tree(int idx)
{
    
int t;
    cin 
>> t;
    
if(t != -1)
    
{
        leaf[idx 
- 1+= t;
        proc_tree(idx 
- 1);
    }

    cin 
>> t;
    
if(t != -1)
    
{
        leaf[idx 
+ 1+= t;
        proc_tree((idx 
+ 1));
    }

}


int main()
{
    
int h, ca = 0;
    
while(cin >> h && h != -1)
    
{
        memset(leaf, 
0sizeof(leaf));
        
int mid = maxn / 2;
        leaf[mid] 
+= h;
        proc_tree(mid);
        cout 
<< "Case " << ++ca << ':' << endl;
        
for(int i = 0; i < maxn - 1++i)
        
if(leaf[i])
        
{
            cout 
<< leaf[i];
            
if(leaf[i + 1]) cout << ' ';
        }

        cout 
<< endl << endl;
    }

    
return 0;
}


posted @ 2011-11-29 16:42 wuxu 阅读(233) | 评论 (0)编辑 收藏
  2011年11月25日
题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=233 

首先建树,建树的同时算出每个节点的pixels,然后分3种情况递归求解:1、两个都为叶节点;2、有且只有一个为叶节点;3、都不是叶节点。由于每个节点记录了pixels,所以对于情况12可以直接返回结果。

#include <iostream>
#include 
<string>
using namespace std;

struct quadtree
{
    
int val;
    quadtree 
*t[4];
    quadtree()
    
{
        val 
= 0;
        
for(int i = 0; i < 4++i) t[i] = 0;
    }

    quadtree(
int v)
    
{
        val 
= v;
        
for(int i = 0; i < 4++i) t[i] = 0;
    }

    
bool isLeaf()
    
{
        
return !(t[0|| t[1|| t[2|| t[3]);
    }

    
~quadtree()
    
{
        
for(int i = 0; i < 4++i)
        
if(t[i]) delete t[i];
    }

}
;

quadtree
* build(const string &s, int &idx, int pixel)
{
    
if(s[idx] == 'e')
    
{
        
++idx;
        
return new quadtree;
    }

    
else if(s[idx] == 'f')
    
{
        
++idx;
        
return new quadtree(pixel);
    }

    
else// if(s[idx] == 'p')
    {
        
++idx;
        quadtree 
*tree = new quadtree;
        
for(int i = 0; i < 4++i)
        
{
            tree
->t[i] = build(s, idx, pixel / 4);
            tree
->val += tree->t[i]->val;
        }

        
return tree;
    }

}


int merge_tree(quadtree *t1, quadtree *t2)
{
    
if(t1->isLeaf() && t2->isLeaf())
    
return t1->val ? t1->val : t2->val;
    
else if(t1->isLeaf() && !t2->isLeaf())
    
return t1->val ? t1->val : t2->val;
    
else if(!t1->isLeaf() && t2->isLeaf())
    
return t2->val ? t2->val : t1->val;
    
else
    
{
        
int ans = 0;
        
for(int i = 0; i < 4++i)
        
{
            ans 
+= merge_tree(t1->t[i], t2->t[i]);
        }

        
return ans;
    }

}


int main()
{
    
int T;
    
string s1, s2;
    quadtree 
*tree_head1, *tree_head2;
    cin 
>> T;
    
while(T--)
    
{
        cin 
>> s1 >> s2;
        
int idx = 0;
        tree_head1 
= build(s1, idx, 1024);
        idx 
= 0;
        tree_head2 
= build(s2, idx, 1024);
        
int ans = merge_tree(tree_head1, tree_head2);
        cout 
<< "There are " << ans << " black pixels." << endl;
        
if(tree_head1) delete tree_head1;
        
if(tree_head2) delete tree_head2;
    }

    
return 0;
}



posted @ 2011-11-25 21:22 wuxu 阅读(272) | 评论 (0)编辑 收藏
题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=489
递归求解,可以不用建树。
#include <iostream>
#include 
<sstream>
#include 
<string>
#include 
<algorithm>
using namespace std;
const int minn = 100000005;

int inorder[10002];
int postorder[10002];
int leaf, minval;

void proc_tree(int num, int inint post, int sum)
{
    
if(num == 0return;
    sum 
+= postorder[post];
    
if(num == 1)
    
{
        
if(sum < minval)
        
{
            minval 
= sum;
            leaf 
= postorder[post];
        }

        
else if(sum == minval && leaf < postorder[post])
        
{
            leaf 
= postorder[post];
        }

        
return;
    }

    
int pos = find(inorder + in, inorder  + in + num, postorder[post]) - inorder;
    proc_tree(num 
- (pos - in + 1), pos + 1, post -1, sum);
    proc_tree(pos 
- inin, post - num + pos - in, sum);
}


int main()
{
    
int n;
    
string si, sp;
    
while(getline(cin, si))
    
{
        getline(cin, sp);
        n 
= 0;
        stringstream strmi(si);
        
while(strmi >> inorder[n]) ++n;
        n 
= 0;
        stringstream strmp(sp);
        
while(strmp >> postorder[n]) ++n;
        leaf 
= -1;
        minval 
= minn;
        proc_tree(n, 
0, n - 10);
        cout 
<< leaf << endl;
    }

    
return 0;
}


posted @ 2011-11-25 14:50 wuxu 阅读(175) | 评论 (0)编辑 收藏
仅列出标题  下一页