数据结构(4)-数组与广义表

引言

之前提高的线性表中的数据元素都是非结构的原子类型（其实也有结构类型的，比如上一章提到的图书索引表），元素值是不可再分解的。
而本章提到的两种数据结构—数组和广义表可以看成是线性表在下述含义上的扩展；表中的数据元素本身也是一个数据结构。

数组

数组，几乎在所有的程序设计语言中都存在。本节讨论数据的具体实现。数组可以看成很多线性表的嵌套，比如二维数组，一行为一个单元，则是一个以行为单位的线性表(只有唯一的首行和尾行，中间的每一行只有一个前驱行和一个后继行)。而行又是一个线性表(行中只有唯一的首元素和尾元素，中间每一个元素只有一个前驱和后继)。所以二维数组可以看成一个线性表，中间的每个单元又是个线性表。同理三维数组，也是，只是嵌套了三层线性表
下面给出多维数组的实现，以及对应下标元素的输入与输出

数组的定义

#include<stdio.h>
#include<stdlib.h>
#include<stdarg.h>
#define MAX_ARRAY_DIM 8
typedef int ElemType;
typedef struct {
	ElemType *base; // 数据元素基地址（首地址）
	ElemType dim; // 维度
	ElemType *bounds; //对应维度长度
	ElemType *constants; //对应维度跨度
}Array;

bool init(Array &a, ElemType dim,...){
	if(dim<0||dim>MAX_ARRAY_DIM) return false;
	a.dim = dim;
	a.bounds = (ElemType*)malloc(dim*sizeof(ElemType));
	// 将维度对应长度存入bounds
	va_list ap;
	int elemtotal =  1;  // 记录数组可以存放的元素个数
	va_start(ap, dim); // 将传入的各个维度长度放入ap 
	for (int i = 0;i<dim;i++){
		a.bounds[i] = va_arg(ap,int); //取出对应维度长度 放入bounds
		elemtotal  *= a.bounds[i];
	}
	va_end(ap); //销毁ap
	a.base = (ElemType*)malloc(elemtotal*sizeof(ElemType)); // 分配创建数组所需要的空间
	// 计算每个维度的跨度，方便寻址
	a.constants = (ElemType*)malloc(dim*sizeof(ElemType));
	a.constants[dim-1] = 1; // 最后一个维度跨度为1
	for(int i=dim-2;i>=0;i--){
		a.constants[i] = a.bounds[i+1]*a.constants[i+1]; // 当前维度跨度 为前一个维度跨度*长度
	}
	return true;
}
bool Locate(Array a,va_list ap,int &off){ //根据小标ap找到对应元素在数组 a中的相对地址
	off = 0;
	for(int i=0;i<a.dim;i++){
		int ind = va_arg(ap,int); 
		if(ind<0||ind>a.bounds[i]) return false; // 下标不合法 
		off += (a.constants[i]*ind);
	}
	return true;
}

bool Value(Array a, int &e, ...){  // 输入数组a和一串下标，将对应位置元素放到e带回(这里不知道为啥加了&下面va_start就会报错 )
	va_list ap;
	va_start(ap, e);
	int off;
	if(!Locate(a,ap,off)) return false;
	e = *(a.base + off);
	//printf("%d",*(a.base + off));
	va_end(ap);
	return true;
}

bool Assign(Array a, ElemType e,...){  //输入数组a和元素e 以及一串下标，将e放在对应位置
	va_list ap;
	va_start(ap, e);
	int off;
	if(!Locate(a,ap,off)) return false;
	*(a.base + off) = e;
	va_end(ap);
	return true;
}
int main() {
	Array a;
	int c=0,b = 5;
	init(a,3,6,7,8);
	Assign(a,b,1,1,1);
	Value(a,c,1,1,1);
	return 0;
}

矩阵的压缩存储

这个了主要是为了减少存储空间，比如一个稀疏矩阵，大小为100x100也就是10000个元素，但只有对角线上的元素不为0其他全是0也就是只有100个元素不为零，其他的9900个元素都为0，如果按照上面创建二维数组，那么就要10000个空间。
太浪费了，这种我们可以直接记录它非零元的位置以及里面的值，这样只需要100个单元即可。
这里给出两种实现方法

1. 用顺序线性表的存储方式来定义这个稀疏矩阵。给出了线性表的定义，以及如何在输入时根据输入元素创建这个稀疏矩阵的线性表和打印这个稀疏矩阵

   #include<stdio.h>
   #include<stdlib.h>
   #define MAXSIZE 12500
   typedef int Elemtype;
   typedef struct {
   	int i,j; // i为行，j为列
   	Elemtype e;
   }Triple;
   typedef struct {
   	Triple data[MAXSIZE+1]; // 0号未用，从1号开始放
   	int row_n,col_n,tn; // 矩阵的行，列，非零元个数
   }TSMatrix;
   
   //手动输入一个稀疏矩阵，将其存到t中
   /*
   0 1 0 0 0
   0 0 0 0 4
   0 3 0 4 0
   0 2 0 0 0
   */
   void create_T(TSMatrix &t){ //根据输入创建这个稀疏矩阵线性表
   	Triple te; // 非零元结点
   	int e;// 用来接收输入的元素
   	//输入矩阵的行列
   	scanf("%d",&t.row_n);
   	scanf("%d",&t.col_n);
   	t.tn = 0;
   	// 按行列输入元素
   	for(int i=0; i<t.row_n; i++){
   		for(int j=0; j<t.col_n; j++){
   			scanf("%d",&e);
   			if(e!=0){
   				t.tn+=1; //非零元个数+1
   				t.data[t.tn].i = i;
   				t.data[t.tn].j = j;
   				t.data[t.tn].e = e;
   			}
   		}
   	}
   }
   void print_T(TSMatrix t){ // 打印稀疏矩阵
   	int k = 1;
   	for(int i=0; i<t.row_n; i++){
   		for(int j=0; j<t.col_n; j++){
   			if(t.data[k].i==i&&t.data[k].j==j){
   				printf("%d ", t.data[k].e);
   				k+=1;
   			}else{
   				printf("0 ");
   			}
   		}
   		printf("\n");
   	}
   }
   int main(){
   	TSMatrix t;
   	create_T(t);
   	print_T(t);
   }

2. 链表的方式实现(夫人版)
   顺序的方式，最大非零元限制了，而且还是会有部分空间浪费，链表实现是最省空间的方法。书上给出来的是顺序实现的，夫人自己采用链表的存储方式写了个，也更上来(意思就是夫人写的比书上的好。)

   #include<stdio.h>
   #include<stdlib.h>
   typedef struct arrayNode{
   	int i,j,elem;
   	struct arrayNode *next;
   }arrayNode, *arrayNodes;
   struct outNode{
   	arrayNodes rear, tail;
   	int row_n, col_n, e_n; // 稀疏矩阵行 列 非零元个数
   };
   void init(outNode &t){ //初始化空线性表
   	t.tail = t.rear = (arrayNodes)malloc(sizeof(arrayNode));
   	t.rear->next = NULL;
   	t.rear->i=t.rear->j=t.rear->elem=0; // 第一个结点不用
   }
   void stressArray(outNode &t, int a[6][6]){//将稀疏矩阵转 线性表压缩存储（c的二维数组传参 坑真多）
   	arrayNodes p;
   	int i,j;
   	for(i=1; i<=5; i++){
   		for(j=1; j<=5;j++){
   			if(a[i][j]!=0){ //非零元
   				p = (arrayNodes)malloc(sizeof(arrayNode));
   				p->next = NULL;
   				p->i = i; p->j = j; p->elem = a[i][j];
   				t.tail->next = p;
   				t.tail = p;
   				t.e_n += 1;
   			}
   		}
   	}
   	t.row_n = i-1;
   	t.col_n = j-1;
   }
   
   void print_T(outNode &t){ // 打印稀疏矩阵线性存储
   	arrayNodes p=t.rear->next;
   	for(int i=1; i<=t.row_n; i++){
   		for(int j=1; j<=t.col_n; j++){
   			if(p->i==i&&p->j==j){
   				printf("%d ",p->elem);
   				p = p->next;
   			}else{
   				printf("0 ");
   			}
   		}
   		printf("\n");
   	}
   }
   
   int main(){
   	outNode t;
   	init(t);
   	int a[6][6]; // 5*5的数组，对角线为非零元素，其他皆为0
   	for(int i=1; i<=5; i++){
   		for(int j=1; j<=5;j++){
   			if(i==j){
   				a[i][j] = 5;
   			}else{
   				a[i][j] = 0;
   			}
   		}
   	}
   	stressArray(t,a);
   	print_T(t);
   	return 0;
   }

广义表

广义表的定义

广义表也是一种线性表，和数组类似，他的表单元不一定是单个元素也可能是一个线性表，但区别就是数组，每个单元是一样的，如果是元素都是元素，如果是线性表就都是线性表，而且线性表大小还一样。
但广义表不一样，它可能第一个单元中是一个元素，第二个单元就是个线性表。例如(a,(b,e),c) 这是个长度为3(也就是有三个单元)的广义表，第一个单元是元素a，第二个单元就是个长度为二的线性表(也可以说是广义表)。
这样在定义广义表的时候，类似链表，需要知道头单元和尾单元，每个单元通过指针指向下一个单元。但每个单元类型定义就有点特殊，因为要考虑他是一个元素，还是一个广义表。所以这里每个单元有两种状态。书上成为原子结点(单个元素)，表结点。

#include<stdio.h>
#include<stdlib.h>
typedef char Elemtype; // 数据类型
typedef enum {ATOM,LIST}EleTag; //ATOM==0 原子结点，LIST==1表结点

// 广义表的头尾链表存储方式
typedef struct GLNode {
	EleTag tag; //用来区分当前结点是原子还是表
	union{ //共用体，只会按照包含属性最大空间分配，比如下面有个char 一个int就只会分配4个空间而不是5个
		Elemtype atom; //原子结点对应元素
		struct{struct GLNode *hp,*tp}ptr; //ptr是指向表结点的指针，ptr.hp和ptr.tp分别指向表头和表尾
	};
}*GList; //广义表类型

// 广义表的扩展线性链表存储方式
typedef struct GLNode{
	EleTag tag; //用来区分当前结点是原子还是表
	union{
		Elemtype atom; //原子结点对应元素
		struct GLNode *hp; //指向一个广义表
	}
	struct GLNode *next
}

广义表存储多元多项式

#include<stdio.h>
#include<stdlib.h>
typedef char Elemtype; // 数据类型
typedef enum {ATOM,LIST}EleTag; //ATOM==0 原子结点，LIST==1表结点
//广义表存储多元多项式
typede struct MPNode{
	EleTag tag; // 区分原子结点和表结点
	int exp; //指针域
	union {
		float coef; //系数域 为原子结点时
		struct MPNode *hp; // 表结点的头指针， 为表结点时
	}
	struct MPNode *tp; //指向下一个项结点
}*MPList; // m元多项式广义表类型