数据结构实践项目——数组和广义表

本文针对 [数据结构基础系列网络课程(５)：数组和广义表] 1. 数组的基本概念与存储结构 2. 特殊矩阵的压缩存储 3. 稀疏矩阵的三元组表示 4. 稀疏矩阵的十字链表表示 5. 广义表 6. 广义表的存储结构及基本运算的实现

【项目1 - 猴子选大王（数组版）】 一群猴子，编号是1，2，3 …m，这群猴子（m个）按照1-m的顺序围坐一圈。从第1只开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，最后一只出圈的猴子为大王。输入m和n，输出猴子离开圈子的顺序，从中也可以看出最后为大王是几号猴子。 要求采用数组作为存储结构完成。 ［参考解答］

【项目2 - 对称矩阵压缩存储的实现与应用】 （1）用压缩形式存储对称矩阵，实现下面的操作并测试

void Init(int *&b);//为N阶对称矩阵初始化存储数据的一维数组B int Value(int b[], int i, int j);//返回存储在b[M]中，对应二维数组A[i][j]的值 void Assign(int b[], int e, int i, int j);//将e赋值给对应二维数组元素A[i][j]，要存储到B[M]中 void Disp(int b[]);//输出压缩存储在b中的对称矩阵 void Destroy(int b[]);//销毁存储空间

［参考解答］ （2）设计算法，实现两个用压缩形式存储的对称矩阵A和B的加法和乘法。实现中请使用好前面设计的基本运算。 ［参考解答］ （3）延伸：写出对上、下三角矩阵、对角矩阵的压缩存储结构，以及相关的基本运算的实现 [参考解答（略）]

【项目3-稀疏矩阵的三元组表示的实现及应用】 （1）建立稀疏矩阵三元组表示的算法库，包括： ① 头文tup.h，定义数据类型，声明函数； ② 源文件tup.cpp，实现稀疏矩阵三元组表示的基本运算，主要算法包括：

void CreatMat(TSMatrix &t,ElemType A[M][N]); //从一个二维稀疏矩阵创建其三元组表示 bool Value(TSMatrix &t,ElemType x,int i,int j); //三元组元素赋值 bool Assign(TSMatrix t,ElemType &x,int i,int j); //将指定位置的元素值赋给变量 void DispMat(TSMatrix t); //输出三元组 void TranTat(TSMatrix t,TSMatrix &tb);//矩阵转置

③ 设计main函数，测试上面实现的算法 ［参考解答］ （2）采用三元组存储稀疏矩阵，设计两个稀疏矩阵相加的运算算法 提示1：两个行数、列数相同的矩阵可以相加 提示2：充分利用已经建立好的算法库解决问题 提示3：教材例6.3已经给出两个稀疏矩阵相加的运算的算法，但未利用基本运算。请比较这两种方案 ［参考解答］

【项目4-广义表算法库及应用】 （1）建立广义表算法库，包括： ① 头文glist.h，定义数据类型，声明函数； ② 源文件glist.cpp，实现广义表的基本运算，主要算法包括：

int GLLength(GLNode *g); //求广义表g的长度 int GLDepth(GLNode *g); //求广义表g的深度 GLNode *CreateGL(char *&s); //返回由括号表示法表示s的广义表链式存储结构 void DispGL(GLNode *g); //输出广义表g

③ 设计main函数，测试上面实现的算法 ［参考解答］ （2）设计一个算法，求出给定广义表g中的原子个数 （3）设计一个算法，求出给定广义表g中的最大原子 ［参考解答］

相关资源：数据结构实验 数组和广义表