数据结构-数组讲义.ppt

习题 2.设定整数数组B[m+1][n+1]的数据在行列方向上都按从小到大的顺序排列，且整型变量x中的数据在B中存在。试设计一个算法，找出一对满足B[i][j]= = x的i,j值。要求比较次数不超过m+n。 TSMatrix M i j e 0 2 9 0 4 7 2 1 8 2 3 3 2 4 2 3 0 1 4 2 5 4 4 4 M.data[3].i = M.data[3].j= M.data[3].e= 2 3 3 M.data[ ] M.mu 5 M.nu 6 M.tu 8 0 1 2 3 4 5 6 7 0 0 9 0 7 0 0 0 0 0 0 0 0 8 0 3 2 0 1 0 0 0 0 0 0 0 5 0 4 0 存储示例 ? 行逻辑链接的顺序表 typedef struct { MTNode *data; // 非零元三元组表 int *rpos;　 // 各行第一个非零元在data中的位置 int mu, nu, tu;　 // 矩阵的行数、列数和非零元的个数} RLSMatrix; i j e ... data[ ] mu nu tu rpos[ ] RLSMatrix A i j e 0 0 3 0 4 7 1 2 -1 2 0 -1 2 1 -2 4 3 2 A.data [ ] 0 1 2 3 4 5 0 2 3 -1 5 A.rpos [ ] 0 1 2 3 4 A.mu 5 A.nu 5 A.tu 6 A.rpos[2] = A.data[4].i = A.data[4].j = A.data[4].e = 存储示例 4 2 0 -1 ? 带行指针向量的链接存储 struct MTNode { int i，j ；//行号，列号 T e; //元素值，T为元素类型 MTNode * next；//指向同行下一个结点 }； i j e next ... rpos[ ] mu nu tu typedef struct { MTNode * rpos; //存放各行链表的头指针 int mu,nu,tu; // 行数、列数、非零元个数 } LMatrix MTNode 带指针向量存储示例 i j e next M.rpos[ ] M.mu 5 M.nu 6 M.tu 8 LMatrix M 十字链表 typedef struct OLNode { 　　// 结点结构定义 int i, j; // 非零元的行和列下标 ElemType e; struct OLNode *right, *down; // 表和列表的后继链域} *OLink; OLNode i j e down right mu nu tu rhead[ ] chead[ ] typedef struct {　// 链表结构定义　OLink *rhead, *chead; // 行和列链表头指针向量　int mu, nu, tu;　// 稀疏矩阵的行数、列数和非零元个数} CrossList; OLNode i j e down right mu nu tu rhead[ ] chead[ ] i j e down right OLNode CrossList A 1 1 3 4 1 8 2 2 5 2 3 4 ^ ^ ^ ^ ^ A.chead A.rhead 十字链表存储示例 A.mu 4 A.nu 3 A.tu 3 ^ 稀疏矩阵运算举例 矩 阵 转 置 矩 阵 加 矩阵转置 A→B=A’ data[] i j e 0 0 2 11 1 0 4 12 2 1 3 22 3 2 1 31 4 2 3 32 5 3 0 41 mu 4 nu 6 tu 6 data[] i j e 0 0 3 41 1 1 2 31 2 2 0 11 3 3 1 22 4 3 2 32 5 4 0 12 mu 6 nu 4 tu 6 ？ S1: 设置矩阵B的行数、列数、非零元个数 方法一：直接取，顺序存 0 2 11 0 4 12 1 3 22 2 1 31 2 3 32 3