数据结构4数组串广义表

《数据结构4数组串广义表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章数组2.1作为抽象数据类型的数组2.2特殊矩阵2.3稀疏矩阵2.4字符串广义表2.1作为抽象数据类型的数组数组的定义：具有相同数据类型的n（n≥0）各元素的有限序列。通过直接操作下标来完成数组操作运算。以抽象数据类型的形式讨论数组的定义和实现，可以让我们加深对数组类型的理解。数组的逻辑结构和物理结构都是顺序结构。ADTarrayISData:Float*element;IntarraySize;functions:length返回数组的长度，即元素个数[i]下标函数，返回数组在下标i（0≤i≤n）处的值。（抽取操作）=（值）赋值函数，把后面的值赋给前面的位置。

2、=数组复制函数，把后面数组的信息复制到q前面的数组。resize重新定义（修改）数组的大小。EndArray浮点数的矩阵、整数的矩阵、复数的矩阵、实数的矩阵。。。。。。用c++来定义数组Classint_arry{Private:int*elements;intarraySize;voidgetArray();//分派空间public:int_array(intsize=defaultSize)；//构造函数int_array(constint_array&x)；//拷贝构造~int_array()；//析构函数int_arrat&operator=(constin

3、t_array&A)//数组复制函数Int&operator[](inti);//返回下标处的值Int*operator*()const;//指针转换Intlength（）const；//返回数组的长度VoidreSize（ints）；//修改数组的长度}；//整数数组的定义Classfloat_arry{Private:float*elements;floatarraySize;voidgetArray();//分派空间public:float_array(intsize=defaultSize)；//构造函数float_array(constint_array&

4、x)；//拷贝构造~float_array()；//析构函数float_array&operator=(constfloat_array&A)//数组复制函数float&operator[](inti);//返回下标处的值float*operator*()const;//指针转换Intlength（）const；//返回数组的长度VoidreSize（ints）；//修改数组的长度}；//浮点数组的定义模板类模板类的定义形式：templeteclassclass_name{………返回类型函数名（参数）}；//函数在体外实现必须是Templete

5、asstype>返回类型class_name::函数名（参数）{函数的具体实现}关于数组的几个结论一维数组的元素类型可以是任意复杂类型。特别的，当它的元素本身是一维数组时，它扩充为二维数组。我们不赞成用直接操作地址的办法来操作数组。数组的优点：位置与值对应，取值、赋值速度快。缺点：处理顺序结构的插入操作不方便。数组本质上是空间位置与值得对应。稀疏矩阵稀疏矩阵的定义：零元素很多的矩阵（凭直觉）稀疏矩阵的抽象数据类型:（p53）TempleteclassSqarseMatrix{data//如何表示它的数据？public:SquarseMatrix

6、(intMaxRow,intMaxCol);SquarseMatrixTranspose();SquarseMatrixAdd(SquarseMatrixb);SquarseMatrixMultiply(SquarseMatrixb);};2.4.2稀疏矩阵的压缩表示法例：999条线路把1000台计算机连成网络。1000x1000稀疏矩阵。（1998个1，其余0）解决方案：三元数组(row,col,value)序列。TempleteclassSquarseMatrix;TempleteclassTr

7、ituple{FriendclassSquarseMatrix;Privite:Introw,col;Tvalue;}TempleteclassSqarseMatrix{privite:introws,cols,terms,MaxTerms;trituplesm[maxTerms],public:SquarseMatrix(intMaxRow,intMaxCol);SquarseMatrixTranspose();SquarseMatrixAdd(SquarseMatrixb);SquarseMatrixMul