【数据结构】五、数组与广义表

目录

一、定义

二、计算数组元素地址

三、稀疏矩阵快速转置

稀疏矩阵的表示

稀疏矩阵快速转置

四、广义表

---

一、定义

我们所熟知的一维、二维数组的元素是原子类型。广义表中的元素除了原子类型还可以是另一个线性表。当然所有的数据元素仍然属于同一类型。

这里的数组可以是顺序结构，也可以是链式结构。

二、计算数组元素地址

公式：

对于二维数组：

行优先：首地址 + [ (行标 - 行起始编号) * 列总数 + (列标 - 列起始编号) ] * 每个元素占的空间

列优先：首地址 + [ (列标 - 列起始编号) * 行总数 + (行标 - 行起始编号) ] * 每个元素占的空间

行和列标号别标反了

例一：

一个二维数组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)