首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
数据结构实验书


eleNode *p; row=a->row; col=a->col; for (i=0;i<row;i++)

{

p=a->down+i;

p=p->right; for(j=0;j<col;j++) { if(p->row==i&&p->col==j) else printf("0 } printf("n"); } } eleNode *matAdd(eleNode {eleNode *r,*p,*q,*u,*v; *a,eleNode *b) "); {printf("%d ",p->val);p=p->right;}

r=createNullMat(a->row,a->col); p=a->down;u=b->down; do { / * 逐行相加 * /

q=p->right;v=u->right; while(q!=p||v!=u) / * 两矩阵中有一个一行未结束循环 / * * 有相同列的元素 * 和非零插入 * / / */

if(q->col==v->col){

if(q->val+v->val!=0) /

insertNode(r,q->row,q->col,q->val+v->val); q=q->right;v=v->right; } else if(q->col<v->col){ / * 插入 a 的元素 * /

insertNode(r,q->row,q->col,q->val); q=q->right; } else{ / * 插入 b 的元素 * /

insertNode(r,v->row,v->col,v->val); v=v->right; }

p=p->down;u=u->down; }while(p!=a->down); return } r;

void {

main() *a,*b,*c;

eleNode

a=readMat(); printf("an"); showMat(a); b=readMat(); printf("bn"); showMat(b); c= matAdd(a,b);

printf("cn"); showMat(c); } 【测试数据】 输入 a 出:4 0 0 0 1 5 0 0 0 矩阵: 1 0 0 1 10 0 9 9 0 0 1 0 9 0 4 1 0 –5 0 0 0 0 0 输入 b 矩阵: 0 1 0 1 输

输入数据注意事项: (1) 如上面 a 矩阵,应输入 3 行 4 列 (2) 若某行有非零元素,则按下列格式(三元组格式)输入: 行号 0 (3) 0 列号 4 值 列号 值 ? 列号 值 -1,如 a 矩阵的第 0 行,应输入

-1,最后

的-1 表示该行的一组数据输入结束。

按以上格式逐行地输入数据,直到输入的行号的值为-1 时,表示稀疏矩阵的全部数据输入结束。

【说明】 从一个结点来看,进行比较、修改指针所需的时间是一个常数;整个运算过程在于对 A 和 B 的十字链表逐 行扫描, 其循环次数主要取决于 A 和 B 矩阵中非零元素的个数 ta 和 tb; 由此算法的时间复杂度为 O(ta+tb)。 【实验题】 1. 设矩阵 采用十字链表存结构,试编写下列程序实现下列运算: 删除第 i 行第 修改第 i 行第 j 列的结点。 j 列的结点的数据值。

del(hm,i,j,x) revise(hm,i,j)

2. 上述例子采用的是新开辟 c 十字链表存放 a 矩阵和 b 矩阵之和,试用 a 存放 a 矩阵和 b 矩阵之和,改写 上述例子。

第四节 思考题
1. 假设稀疏矩阵 A 的大小是 m×n,稀疏矩阵 B 的大小是 n×1(一维向量),A 和 B 均采用三元组表示, 编程实现 C=A×B,其结果 C 也采用三元组表形式输出。 【简要分析】本题的关键是要确定 i 行 j 列的元素在三元组表中的位置,由于 B 是一个一维向量,在用三 元组表进行矩阵相乘时并不方便,可以先将 B 做转置存放后,一遍扫描 A 就可以实现乘法。 2.如果矩阵 A 中存在这样的一个元素 A[i][j]满足以下条件:A[i][j]是第 i 行中值最小的元素,且又是第 j 列中值最大的元素,则称 A[i][j]为矩阵 A 的一个鞍点;假设稀疏矩阵 A(大小是 m×n)已经用三元组表 存放,编程实现求鞍点的算法,如果没有鞍点,也给出相应信息。 【简要分析】如果 A 采用二维数组存放,本题的解法是很容易的,只需要求出每行的最小元素,放入 min[0..m-1]中,再求出每列的最大元,放入 max[0..n-1]之中,如果某元素 A[i][j],既在 min[i]中,又 在 max[j]中,则 A[i][j]必是鞍点。对三元组存放的 A,在求 max 数组时会有一些困难,可参考教材,增 设一个 cpot 数组和一个 num 数组,用来记录 A 的列元素。

第六章
【实验目的】

树和二叉树的建立和应用

1. 熟练掌握树的基本概念、二叉树的基本操作及在链式存储结构上的实现。 2. 重点掌握二叉树的生成、遍历及求深度等算法。 3. 掌握二叉树的线索化及线索二叉树的遍历算法;掌握赫夫曼树的含义及其应用。 4. 掌握运用递归方式描述算法及编写递归 C 程序的方法,提高算法分析和程序设计能力。

第一节 知识准备
树型结构是一类非常重要的非线性结构,是《数据结构》课程中的重点和难点之一。掌握好本章 的知识,对后续章节的理解和把握起着非常重要的作用。 一、 树和二叉树的基本概念 如图 6-1 所示是一棵由 n=13 个结点构成的一棵树。

图 6-1

1. 树中 A 称为树的根结点,它是唯一的且没有前驱。特别地,当树中一个结点也没有时,称该树为空树。 2. A 有 3 个后继结点 B、C、D 称为 A 的孩子,或说 A 有三棵子树,A 的度就是 3。结点 B、C、D、E、F、G、 H、I、J、K、L、M 的度分别就是 2、1、3、0、2、0、0、0、1、0、0、0 3. 结点 E、G、H、I、K、L、M 的度都是 0,凡是树中度为 0 的结点称为叶子或终端结点。 4. 结点 A、B、C、D、F、J 的度都大于 0,度大于 0 的结点称为分支结点或非终端结点。特别地,当树中 只有一个结点 A 时,A 既是根结点又是终端结点。 5. 树中所有结点的度的最大值是 3,该最大值称为树的度。图 6-1 所示树的度就是 3。 6. 树的最大层数为四层,所以树的深度为 4。 7. 树中结点 B、C、D 有相同的前驱结点 A,结点 E、F 有相同的前驱结点 B,等等,称 A 为 B、C、D 的双亲, B 为 E、F 的双亲。反之又称 B、C、D 为 A 为孩子结点。B、C、D 互为兄弟结点,E、F 互为兄弟结点,等等。 8. 树中除根结点外其余每个结点都有唯一的双亲结点,但可以有多个孩子结点,表现为一种一对多的非线 性关系。 9. 树中同一层各结点从左至右看成是有序的(即不能互换),则称该树为有序树,否则称为无序树。 10. 若一棵有序树中每个结点的度都小于或等于 2,则称该树为二叉树。二叉树是一类非常特殊且重要的

树,有许多重要特性和应用,要很好掌握。在二叉树中要严格区分左右子树。 11. m(m≥0)棵互不相交的树的集合称为森林。 二、树的基本性质 1. 树中的结点数等于所有结点的度数加 1。 2. 度为 k 的树中第 i 层上至多有 ki-1 个结点(i≥1)。 3. 深度为 h 的 k 叉树至多有 个结点。 4. ?log k (n(k-1)+1) ?具有 n 个结点的 k 叉树的最小深度为

123456789101112131415161718192021222324252627282930

 


 

  【Top

最新搜索

 


 

热点推荐