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

  1. 云栖社区>
  2. 博客>
  3. 正文

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

贺利坚 2015-10-18 14:43:00 浏览1100
展开阅读全文

本文针对 [数据结构基础系列网络课程(5):数组和广义表]
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中的最大原子
参考解答

网友评论

登录后评论
0/500
评论