目录
一、定义
二、计算数组元素地址
三、稀疏矩阵快速转置
稀疏矩阵的表示
稀疏矩阵快速转置
四、广义表
一、定义
我们所熟知的一维、二维数组的元素是原子类型。广义表中的元素除了原子类型还可以是另一个线性表。当然所有的数据元素仍然属于同一类型。
这里的数组可以是顺序结构，也可以是链式结构。
二、计算数组元素地址
公式：
对于二维数组：
行优先：首地址 + [ (行标 - 行起始编号) * 列总数 + (列标 - 列起始编号) ] * 每个元素占的空间
列优先：首地址 + [ (列标 - 列起始编号) * 行总数 + (行标 - 行起始编号) ] * 每个元素占的空间
行和列标号别标反了
例一：
一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是（ ）个字节
答案：288 (6-1+1)*(7-0+1)*6
例二：
设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为（ ）
答案：8950 2048+[(58-1)*60+(32-1)]*2
例三：
假设以行序为主序存储二维数组A=array[1..100,1..100],设每个数据元素占2个存储单元,基地址为10,则LOC[5,5]=（ ）
答案：818
例四：
数组A[0..5,0..6]的每个元素占五个字节,将其按列优先次序存储在起始地址为1000的内存单元中,则元素A[5,5]的地址是( )
答案：1175
例五：
假设有三维数组A(7×9×8)，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，末尾元素A[6][8][7]的第一个字节地址为多少？
答案：4018 1000+(7×9×8-1)×6
三、稀疏矩阵快速转置
稀疏矩阵：大部分为0，非零元素较少的矩阵
稀疏矩阵的表示
1.线性表
会浪费很多空间
2.三元组表示法
第零行记录总行数，总列数和总非零元素个数；其他行按行优先记录非零元素的位置和值
为了高效访问稀疏矩阵中任一非零元素，引入辅助向量：
num(i)：记录每行非0元素个数
pos(i)： 记录稀疏矩阵中每行第一个非0元素在三元组中的序号
pos计算公式：
pos(1)＝1
pos(i)＝pos(i-1)+num(i-1)
稀疏矩阵快速转置
目的：已知原矩阵的三元组，求转置后矩阵的三元组。而且原三元组仅遍历一遍，也就是说将原三元组每条信息直接送入新三元组对应位置
所以我们需要一个指示迁移位置的数组cpos
由于转置使得每一列的第一个非零数成为每一行的第一个非零数，而三元组又是以行优先排列的，所以cpos反映了原矩阵每一列首非零元在新三元组中的编号
相当于按列遍历了原矩阵，把转置矩阵每一行的首非零元先写入新三元组对应位置
cpos计算方法：cpos第一位默认为1，也就是原矩阵第一列首非零元要放在新三元组第一行。cpos后一位等于cpos前一位加前一列非零元个数（num数组负责记录每列的非零元素个数）
遍历旧三元组，cpos[列数] = 新三元组中的行号。迁移一个元素后，把对应的cpos加一
由于旧矩阵从上往下从左往右遍历，所以每一列第一个拿到的元素肯定是首非零元，说明本方法合理
代码（有误）：
/*快速转置的目的是通过一次遍历旧三元组，就能把原非零数的信息放到新三元组对应位置上所以我们需要一个指示迁移位置的数组cpos由于转置使得每一列的第一个非零数成为每一行的第一个非零数，而三元组又是以行优先排列的，所以cpos反映了每一列首非零元在新三元组中的编号相当于按列遍历了原矩阵，把转置矩阵每一行的首非零元安排好了计算方法：cpos第一位默认为1，也就是原矩阵第一列首非零元要放在新三元组第一行。cpos后一位等于cpos前一位加前一列非零元个数然后遍历旧三元组时，根据列数进行索引，由于旧矩阵从上往下从左往右遍历，所以每一列第一个拿到的元素肯定是首非零元迁移一个元素后，把对应的cpos加一*/
#include<stdio.h>
#include<stdlib.h>#define MAXTRIPLE 25 //三元组非零元素最大个数typedef int elemtype;typedef struct triple {int row;int col;elemtype e;
}triple; //三元组节点，包括非零元素的行号，列号，值typedef struct {triple data[MAXTRIPLE + 1];int mrow, mcol, mnum; //列表的总行数，总列数，非零个数，描述的是三元组。data第一行描述稀疏矩阵的行数、列数、非零数
}tsmatrix; //三元组列表void creatematrix(elemtype* mat, int row, int col) //创建矩阵
{printf("输入元素：");for (int i = 0; i < row; i++)for (int j = 0; j < col; j++)scanf_s("%d", &mat[(i - 1) * col + j]);
}void printmatrix(elemtype* mat, int row, int col) {for (int i = 0; i < row; i++) {for (int j = 0; j < col; j++)printf("%d ", mat[(i - 1) * col + j]);printf("\n");}printf("\n");
}void inittriple(tsmatrix* tri, elemtype* mat, int row, int col) { //生成三元组tri->mcol = 3;tri->mrow = 0;tri->mnum = 0;for (int i = 0; i < row; i++) {for (int j = 0; j < col; j++)if (mat[(i - 1) * col + j] != 0) {tri->mnum++; //新增节点，列表非零元素和行数都增加tri->mrow++;tri->data[tri->mnum].e = mat[(i - 1) * col + j];tri->data[tri->mnum].row = i;tri->data[tri->mnum].col = j;}}tri->data[0].row = row;tri->data[0].col = col;tri->data[0].e = tri->mnum; //三元组第一行放稀疏矩阵的信息
}void printtriple(tsmatrix* tri){ //打印三元组printf("三元组矩阵为:\n");printf("行\t列\t值\n");int i;for (i = 0; i <= tri->mrow; i++) {printf("%d\t%d\t%d\n", tri->data[i].row, tri->data[i].col, tri->data[i].e);}
}void tri2mat(tsmatrix* tri) { //将三元组还原为矩阵int i, j;elemtype* originmat = (elemtype*)malloc(sizeof(elemtype) * tri->data[0].col * tri->data[0].row);if (!originmat) return;for (i = 0; i < tri->data[0].row; i++)for (j = 0; j < tri->data[0].col; j++)originmat[i * tri->data[0].row + j] = 0; //矩阵先全为0for (i = 1; i <= tri->mnum; i++) //遍历三元组非零元素的信息originmat[(tri->data[i].row * tri->data[0].row) + tri->data[i].col] = tri->data[i].e;printf("矩阵为：\n");for (i = 0; i < tri->data[0].row; i++) {for (j = 0; j < tri->data[0].col; j++)printf("%d ", originmat[i * tri->data[0].row + j]);printf("\n");}
}void fasttrans(tsmatrix* tri) { //快速转置tsmatrix* trans = (tsmatrix*)malloc(sizeof(tsmatrix)); //trans为新的三元组if (!trans) return;trans->mcol = tri->mcol; trans->mrow = tri->mrow;trans->mnum = tri->mnum;trans->data[0].col = tri->data[0].row;trans->data[0].row = tri->data[0].col;trans->data[0].e = tri->data[0].e; //新旧三元组关于自身的信息（行，列，非零数）相同；矩阵的行列互换，非零数相同if (tri->mnum > 0) {int i;int* num = (int*)malloc(sizeof(int) * tri->data[0].col); //num数组用来记录矩阵每一列非零个数if (!num) return;for (i = 0; i < tri->data[0].col; i++)num[i] = 0;for (i = 1; i <= tri->mnum; i++)num[tri->data[i].col]++;int* cpos = (int*)malloc(sizeof(int) * tri->data[0].col); //cpos用来记录计算稀疏矩阵中每列第一个非0元素在新三元组表中存放的位置if (!cpos) return;cpos[0] = 1; //cpos首元素默认为1for (i = 1; i < tri->data[0].col; i++)cpos[i] = cpos[i - 1] + num[i - 1]; //cpos剩下元素计算方法：新cpos=旧cpos+旧num 如：第一列首非零元设为1，第二列首非零元为1跳过第一列非零元个数printf("nums:");for (i = 0; i < tri->data[0].col; i++)printf("%d ", num[i]);printf("\n");printf("cpos:");for (i = 0; i < tri->data[0].col; i++)printf("%d ", cpos[i]);printf("\n");for (i = 1; i <= tri->mnum; i++) { //三元组数据迁移trans->data[cpos[tri->data[i].col]].row = tri->data[i].col; //以旧三元组中列数为索引，到cpos中去查找它要去的位置，行列交换trans->data[cpos[tri->data[i].col]].col = tri->data[i].row;trans->data[cpos[tri->data[i].col]].e = tri->data[i].e; cpos[tri->data[i].col]++; //cpos中数据用过一次后要加一}printtriple(trans);printf("转置后的");tri2mat(trans);}elsetri2mat(tri);}int main() {int row, col;printf("输入稀疏矩阵行数：");scanf_s("%d", &row);printf("输入稀疏矩阵列数：");scanf_s("%d", &col);elemtype* mat = (elemtype*)malloc(sizeof(elemtype) * row * col);creatematrix(mat, row, col);printf("原矩阵为：\n");printmatrix (mat, row, col);tsmatrix* triple = (tsmatrix*)malloc(sizeof(tsmatrix));inittriple(triple, mat, row, col);printtriple(triple);tri2mat(triple);fasttrans(triple);
}四、广义表
定义：广义表是线性表的推广。广义表中元素既可以是原子类型，也可以是列表
特点：
1.第一个元素是表头，其余元素组成的表称为表尾
2.任何一个非空表，表头可能是原子，也可能是列表；但表尾一定是列表
3.广义表的长度 = 表中元素个数；广义表的深度 = 表中括号的最大重数
4.用小写字母表示原子类型，用大写字母表示列表。
L=( ( ) , (e) , ( a , (b , c , d) ) )，长度为3，深度为3
A=( a , (b , A) )，长度为2，深度为无穷
广义表操作
取表头：表头为单个元素，直接写出表的首位元素即可
取表尾：表尾为列表，写出除了首个元素以外的元素，外面加层括号
练习：
GetTail：(b, k, p, h) =(k,p,h)
GetHead：( (a,b), (c,d) ) =(a,b)
GetTail：( (a,b), (c,d) ) =((c,d))
GetTail：( GetHead：((a,b),(c,d)) ) =(b)
GetTail: (e) = ( )
GetHead: ( ( ) )＝( )
GetTail: ( ( ) ) ＝( )
广义表A=(a,b,(c,d),(e,(f,g))),则Head(Tail(Head(Tail(Tail()))))值为( )
答案：d已知广义表A=((a,(b,c)),(a,(b,c),d)),则运算head(tail(head()))的结果是( )
答案：(b,c)
