目录
一、定义
二、计算数组元素地址
三、稀疏矩阵快速转置
稀疏矩阵的表示
稀疏矩阵快速转置
四、广义表
一、定义
我们所熟知的一维、二维数组的元素是原子类型。广义表中的元素除了原子类型还可以是另一个线性表。当然所有的数据元素仍然属于同一类型。
这里的数组可以是顺序结构，也可以是链式结构。
二、计算数组元素地址
公式：
对于二维数组：
行优先：首地址 + [ (行标 - 行起始编号) * 列总数 + (列标 - 列起始编号) ] * 每个元素占的空间
列优先：首地址 + [ (列标 - 列起始编号) * 行总数 + (行标 - 行起始编号) ] * 每个元素占的空间
行和列标号别标反了
例一：
一个二维数组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; //矩阵先全为0
for (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首元素默认为1
for (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);
}
else
tri2mat(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)
