北航数据结构Data03.ppt

* 快速转置算法 void Fast-Transpose(int A(ROW,COL),B(ROW,COL)) { int m, n, t, p, q, Col; m = A[0,1]; n = A[0,2]; t = A[0,3]; B[0,1] = n; B[0,2] = m; B[0,3] = t; if (t = 0) return; for (Col=1;Col=n;Col++) Num[Col] = 0; for (p=1;p=t;p++) Num[A[p,2]] = Num[A[p,2]]+1; Pot[1] = 1; //计算转置后每行第一个非0元素存储位置// for (Col=2;Col=n;Col++) Pot[Col] = Pot[Col-1]+Num[Col-1]; for (p = 1; p= t; p++) { //开始转置// Col = A[p,2]; B[Pot[Col],1] = A[p,2]; B[Pot[Col],2] = A[p,1]; B[Pot[Col],3] = A[p,3]; Pot[Col] = Pot[Col] + 1; }//元素转置结束// } // 算法结束 // * 3.5 稀疏矩阵的十字链表表示 1、稀疏矩阵的循环链表表示 用链表表示稀疏矩阵中的非0元素，需要存储：行号、列号、元素值；将非零元素以行主序方式用循环链表链接起来。 i j V Link m n t Link 表头结点 3 4 5 1 1 4 1 4 2 2 2 3 3 1 5 3 3 -1 H * 2、稀疏矩阵的十字链表表示 每个元素按行有一个后继，按列有一个后继，因此，需要设置两个指针，分别指向行后继和列后继元素； 用链表表示稀疏矩阵中的非0元素，需要存储：行号、列号、元素值； Row Col Right Down Value 结点结构 m n Right Down t 表头结点 Row、Col、Value分别表示非0元素的行、列和值，Down和Right表示向下（列）和向右（行）指针，分别链接同一列和同一行中的非0元素。 * 3 4 5 0 1 0 0 2 0 0 3 0 0 4 0 1 0 0 2 0 0 3 0 0 1 1 4 3 1 5 1 4 2 2 2 3 3 3 -1 * 3.6.1 一元多项式的数组表示 方法1：定义一个一维数组A[1：n+2]。其中，A[1]用来存储多项式的阶数，从A[2]开始到A[n+2]，分别存储n+1个系数an，an-1，…，a0。 1、一元n阶多项式的数组表示 例如，多项式A（x）=10x6 – 8x5 + 3x2 – 1，表示成： * 例如，B（x）=x200+4 方法2：定义一个一维数组A[1：2m+1]来表示多项式。其中，第1个元素A[1]存放多项式中系数非0项的总项数m；从第2个元素到第2m+1个元素（共2m个）依次存放系数非0项的指数与系数偶对（共m个偶对）。 * 3.6.2 n阶魔方 所谓n阶魔方是一个填数游戏。要求将数字1~n2个数字不重复地填入到一个由n行n列组成的方阵中，使得方阵中每行、每列、两个对角线上的数字之和分别等于同一个数值。这个方阵就称为“魔方”。 最早的魔方据说是大禹治水(公元前2200)在神龟背上看到的3阶魔方： 4 9 2 3 5 7 8 1 6 洛书上的3阶魔方 * 公元80年出版的古书《大戴礼记》：“二九四、七五三、六一八” 1977年出土的第二代汝阴侯夏侯灶(公元前165年)墓文物“太乙九宫占盘”八个方位所刻数字及中心位置的九宫数字恰为“四九二、三五七、八一六” 南宋杨辉：研究魔方第一人，给出了3、4-10阶魔方 * 杨辉4阶魔方称为“花十六图”或“四四图”，分阳图和阴图 杨辉4阶魔方 2 16 13 3 11 5 8 10 7 9 12 6 14 4 1 15 13 9 5 1 14 10 6 2 15 11 7 3 16 12 8 4 4 9 5 16 14 7 11 2 15 6 10 3 1 12 8 13 阴图生成法：十六子依次四行排列；外角四子互换：1-16、4-13；内角四子互换：6-11；7-10 4 9 5 16 14 7 11 2 15 6 10 3 1 12 8 13 * 如何构造魔方 适合于奇数阶魔方 将1设置在最上行中间，然后按对角线的方向（自右下向左上、或者自左下向右上方向）依次填入数字；如果到达顶部则转向底部；左（右）边界则转向右（左边），如果其上已有数字则转向下方。 例如n=3 “魔方”为： 1 2 3 4 5 6 7 8 9 1、连续摆数法 8