什么是抽象数据模型？主要特点是什么？

　　数据抽象
　　概念结构是对现实世界的一种抽象

　　从实际的人、物、事和概念中抽取所关心的共同特性，忽略非本质的细节

　　把这些特性用各种概念精确地加以描述

　　这些概念组成了某种模型

　　三种常用抽象

　　1. 分类（Classification）

　　定义某一类概念作为现实世界中一组对象的类型

　　这些对象具有某些共同的特性和行为

　　它抽象了对象值和型之间的“is member of”的语义

　　在E-R模型中，实体型就是这种抽象

　　2. 聚集（Aggregation）

　　定义某一类型的组成成分

　　它抽象了对象内部类型和成分之间“is part of”的语义

　　在E-R模型中若干属性的聚集组成了实体型，就是这种抽象

　　3. 概括（Generalization）

　　定义类型之间的一种子集联系

　　它抽象了类型之间的“is subset of”的语义

　　概括有一个很重要的性质：继承性。子类继承超类上定义的所有抽象。

　　注：原E-R模型不具有概括，本书对E-R模型作了扩充，允许定义超类实体型和子类实体型。

　　用双竖边的矩形框表示子类，

　　用直线加小圆圈表示超类-子类的联系

　　数据抽象的用途

　　对需求分析阶段收集到的数据进行分类、组织（聚集），形成

　　实体

　　实体的属性，标识实体的码

　　确定实体之间的联系类型(1:1，1:n，m:n)

　　/**************稀疏矩阵的抽象数据模型**************/
　　#include
　　#include
　　using namespace std;
　　/***Writed by Yecon***/

　　const int MaxTerms = 20; //三元组表smArray中三元组个数的最大值
　　template class SparseMatrix; //稀疏矩阵的类声明
　　template class Trituple
　　{
　　//三元组类
　　friend class SparseMatrix;
　　private:
　　int row,col;
　　Type value;
　　};
　　template class SparseMatrix
　　{
　　int Rows, //行数
　　Cols, //列数
　　Terms; //非零元个数
　　Trituple smArray[MaxTerms]; //三元组表
　　public:
　　SparseMatrix(int MaxRows,int MaxCols); //构造函数
　　bool input_data(int row,int col,Type value); //输入数据
　　SparseMatrix Transpose(); //转置矩阵
　　SparseMatrix Add(SparseMatrix b); //矩阵求和
　　SparseMatrix Mul(SparseMatrix b); //矩阵求积
　　SparseMatrix EmptyMatrix(); //返回零矩阵
　　};

　　template SparseMatrix::SparseMatrix(int MaxRows,int MaxCols)
　　{
　　Rows = MaxRows; //行数置零
　　Cols = MaxCols; //列数置零
　　Terms = 0; //非零元个数置零
　　}
　　template bool SparseMatrix::input_data(int row,int col,Type value)
　　{
　　if(Terms == MaxTerms || row > Rows || col > Cols)return false;
　　if(Terms == 0)//若是第一个元素
　　{
　　//插入第一个元素
　　smArray[Terms].row = row;
　　smArray[Terms].col = col;
　　smArray[Terms].value = value;
　　Terms++;
　　return true;
　　}
　　if((row>smArray[Terms-1].row)||((row==smArray[Terms-1].row)&&(col>smArray[Terms-1].col)))//若是最后一个元素
　　{
　　//插入最后一个元素
　　smArray[Terms].row = row;
　　smArray[Terms].col = col;
　　smArray[Terms].value = value;
　　Terms++;
　　return true;
　　}
　　//若非第一个活最后一个元素
　　//计算应该插入的位置
　　int k = Terms - 1;
　　for(int i = Terms - 1;i >= 0;i--)//确定行
　　if(smArray[i].row >= row)k = i;
　　for(int j = k;smArray[j].row == row;j++)//确定列
　　if(smArray[j].col <= col)k = j;
　　for(int i = Terms -1;i >= k;i--)//为待插入的元素腾出地方
　　smArray[i + 1] = smArray[i];
　　smArray[k].col = col;
　　smArray[k].row = row;
　　smArray[k].value = value;
　　Terms++;
　　return true;
　　}
　　template SparseMatrix SparseMatrix:: Transpose()
　　{
　　//求矩阵的转置
　　int * rowSize = new int[Cols]; //辅助数组，统计个列非零元素个数
　　int * rowStart = new int[Cols]; //辅助数组，预计转置后各行存放位置
　　SparseMatrix b(Cols,Rows);//存放转置结果
　　// b.Rows = Cols;b.Cols = Rows;b.Terms = Terms;
　　if(Terms > 0)
　　{
　　//统计矩阵b中第i行非零元素个数
　　for(int i = 0;i < Cols;i++)rowSize[i] = 0; //清零
　　for(int i = 0;i < Terms;i++)rowSize[smArray[i].col]++;//根据矩阵this中第i个非零元素的列号，将rowSize相当该列的计数加1
　　//计算矩阵b第i行非零元素的开始存放位置
　　rowStart[0] = 0;
　　for(int i = 1;i < Cols;i++) //rowStart[i] = 矩阵b的第i行的开始存放位置
　　rowStart[i] = rowStart[i - 1] + rowSize[i - 1];
　　for(int i = 0;i < Terms;i++)
　　{
　　//从this向b传送
　　int j = rowStart[smArray[i].col]; //j为第i个非零元素在b中应存放的位置
　　b.smArray[j].row = smArray[i].col;
　　b.smArray[j].col = smArray[i].row;
　　b.smArray[j].value = smArray[i].value;
　　rowStart[smArray[i].col]++; //矩阵b第i行非零元素的存放位置加1
　　}
　　}
　　delete []rowSize;
　　delete []rowStart;
　　return b;
　　}
　　template SparseMatrix SparseMatrix::Mul(SparseMatrix b)
　　{
　　//矩阵求积
　　if(Cols != b.Rows)
　　{
　　//this矩阵列数与b矩阵行数不能
　　cout << "Incompatible matrix" << endl;
　　return EmptyMatrix();
　　}
　　if(Terms == MaxTerms || b.Terms == MaxTerms) //有一个矩阵的项数达到最大
　　{
　　cout << "One additional space in a or b needed" << endl;
　　return EmptyMatrix(); //空间不足，返回空矩阵
　　}
　　int * rowSize = new int[b.Rows]; //辅助数组，矩阵b各行非零元素个数
　　int *rowStart = new int[b.Rows + 1]; //辅助数组，矩阵b各行的三元组起始位置
　　Type *temp = new Type[b.Cols]; //临时数组，暂存每一行计算结果
　　SparseMatrix result(Rows,Cols); //结果矩阵的三元组表
　　for(int i = 0;i < b.Rows;i++) rowSize[i] = 0; //统计矩阵b中第i行非零元素个数
　　for(int i = 0;i < b.Terms;i++)rowSize[smArray[i].row]++;
　　rowStart[0] = 0; //计算矩阵b第i行非零元素的开始位置
　　for(int i = 1;i <= b.Rows;i++)rowStart[i] = rowStart[i - 1] + rowSize[i - 1];
　　int Current = 0,lastInResult = -1;//a.smArray扫描指针及result存放指针
　　while(Current < Terms)
　　{
　　//生成result的当前行temp
　　int RowA = smArray[Current].row; //当前行的行号
　　for(int i = 0;i < b.Cols;i++)temp[i] = 0; //temp初始化
　　while(Current < Terms && smArray[Current].row == RowA)
　　{
　　int ColA = smArray[Current].col; //矩阵A当前扫描到元素的列号
　　for(int i = rowStart[ColA];i < rowStart[ColA + 1];i++)
　　{
　　int ColB = b.smArray[i].col; //矩阵b中相乘元素的列号
　　//A的RowA行与b的ColB列相乘
　　temp[ColB] = temp[ColB] + smArray[Current].value * b.smArray[i].value;
　　}
　　Current++;
　　}
　　for(int i = 0;i < b.Cols;i++)
　　if(temp[i] != 0)
　　{
　　//将temp中的非零元素压缩到result中去
　　lastInResult++;
　　result.smArray[lastInResult].row = RowA;
　　result.smArray[lastInResult].col = i;
　　result.smArray[lastInResult].value = temp[i];
　　}
　　}
　　result.Rows = Rows;
　　result.Cols = b.Cols;
　　result.Terms = lastInResult + 1;
　　delete []rowSize;
　　delete []rowStart;
　　delete []temp;
　　return result;
　　}
　　template SparseMatrix SparseMatrix::EmptyMatrix()
　　{
　　SparseMatrix Z(0,0);
　　return Z;
　　}
　　int testSparseMatrix()//main()
　　{
　　SparseMatrix A(7,8);
　　A.input_data(0,6,15);
　　A.input_data(0,3,22);
　　A.input_data(4,0,91);
　　A.input_data(2,3,-6);
　　A.input_data(1,5,17);
　　A.input_data(5,2,28);
　　A.input_data(1,1,11);
　　A.input_data(3,5,39);
　　//test Transpose()
　　SparseMatrix B(8,7);
　　B = A.Transpose();
　　//test Mul()
　　SparseMatrix C(7,4);
　　C.input_data(2,3,5);
　　C.input_data(1,1,10);
　　C.input_data(5,2,2);
　　SparseMatrix D(8,4);
　　D = B.Mul(C);
　　return 0;
　　}