数据结构实验报告（华夏）

实验三 稀疏矩阵的基本操作的实现

一、预习报告

实验目的

1、掌握用Turbo C上机建立、调试稀疏矩阵的基本方法； 2、掌握矩阵的存储结构及其特点，完成稀疏矩阵加法运算算法在C语言上的程序实现； 基本原理与方法 用三元组表实现矩阵的存储后的基本操作算法用C语言编程实现 实验设备 PC机一台、配置Turbo C软件 二、实验内容

设计两个稀疏矩阵的基本操作程序

[问题描述] 稀疏矩阵的存储结构为三元组表或十字链表，设计用三元组表进行存储稀

疏矩阵，完成常规操作。

[基本要求] 稀疏矩阵的常规操作有： 1． 输入并建立稀疏矩阵的存储结构；

2． 设计两个两个稀疏矩阵的加、减及乘法运算的程序；

[实现提示] 稀疏矩阵只存储非零元素的行、列号和值，可选择用三列的二维数组R[][3]

或一维数组R[3*（N+1）] 实现， 例如：稀疏矩阵如图所示为：

0 3 0 5 2 0 0 4 0 2 0 0

可以存放在一个一维数组R[0 ··17]中，行、列号为-1作为结束标志。 则各元素值为：R[0]=0，R[1]=1，R[2]=3； R[3]=0，R[4]=3，R[5]=5； R[6]=1，R[7]=1，R[8]=2； R[9]=1，R[10]=3，R[11]=4

R[12]=2，R[13]=1，R[14]=2； R[15]= -1 R[16]= -1（输入结束）

[参考程序段]

两个稀疏矩阵相加的函数描述为：

int add (A,B,C) int A[ ] , B[ ] , C[ ] ; {

int i =0 ,j=0 , k=0 , sum ;

while ( A[i]!= -1 ) && (B[j] != -1)) if ( A[i] = = B[j] ) {

if ( A[i+1] = = B[j+1] )

{

sum= A[i+2] + B[j+2] ;

if (sum !=0 )

{ C[k] = A[i] ; C[k+1] = A[i+1] ; C[k+2] = sum ; k=k+3 }

i=i+3 ;j=j+3 ; } else

if (A[i+1] < B[j+1] )

{ C[k] = A[i] ; C[k+1] = A[i+1] ; C[k+2] = A[i+2] ; k=k+3 ; i=i+3 ; } else

{ C[k] =B[j] ; C[k+1] = B[j+1] ; C[k+2] =B[j+2] ; k=k+3 ;J=J+3 ; }

} else

if (A[ i] < B[j ] )

{ C[k] = A[i] ; C[k+1] = A[i+1] ; C[k+2] = A[i+2] ; k=k+3 ; i=i+3 ; } else

{ C[k] =B[j ] ; C[k+1] = B[j+1] ; C[k+2] =B[j+2] ; k=k+3 ;J=J+3 ; }

}

if ( A[i]= = -1 ) && (B[j] != -1)

{ C[k] =B[j ] ; C[k+1] = B[j+1] ; C[k+2] =B[j+2] ; k=k+3 ;J=J+3 ; } if ( A[i]! = -1 ) && (B[j] = = -1)

{ C[k] = A[i] ; C[k+1] = A[i+1] ; C[k+2] = A[i+2] ; k=k+3 ; i=i+3 ; } c[k]= -1 ; return (1) }

void input(int A[]) { int I=0,j=1;

do { printf(“input NO%d number?s index:”,j); scanf(“%d,%d”,&A[I],&A[I+1]); if(A[I]!=-1 && A[I+1]!= -1)

{ printf(“input NO%d number?s index:”,j); scanf(“%d “ &A[I+2]); I=I+3;j++;

}while(A[I]!=-1 && A[I+1]!=-1) }

三、实验结果分析讨论

1、 按参考程序段给出的思路，补充一个主函数，求两个稀疏矩阵的加法运算； main() {

int r[100],p[100],w[100];

input(r); input(p); add(r,p,w) printf(“w”);

I=0; do {

Printf(“M,M,M”,w[I],w[I+1],w[I+2]); I=I+3; } }

2、补充两个函数，分别计算两个稀疏矩阵的减及乘法运算；

3、调试程序

[测试数据] A B

0 3 0 5 1 0 0 4 2 0 0 4 0 0 3 0

0 2 0 0 0 8 1 0

写出程序运行结果

四、巩固题 将稀疏矩阵用二维数组存储，写出完整程序调试它。

五、思考： 1、 用一维数组存储与用二维数组存储的两种存储方法上操作算法是否相同？ 2、 从程序的易读性来看，哪一种存储方法使其更易读？

实验四 哈夫曼树及哈夫曼编码的实现

一、预习报告

实验目的

1、掌握用Turbo C上机调试层次结构的基本方法； 2、掌握二叉树的结构特性及二叉树的存储结构特征； 3、设计哈夫曼树及哈夫曼编码的实现的程序 ；

基本原理与方法 按哈夫曼树的形成原理构造哈夫曼树操作算法用C语言编程实现 实验设备 PC机一台、配置Turbo C软件 二、实验内容

1、 输入n个叶结点的权值构造哈夫曼树； 2、根据哈夫曼树构造哈夫曼编码；

[问题描述] 已知N个字符的权值集合w={w1,w2,w3…….wn}和字符集合

k={k1,k2,k3,……..kn} 求其K集合中各字符的哈夫曼编码。

[基本要求] 1. 输入n个叶结点的权值构造哈夫曼树；

2. 根据哈夫曼树构造哈夫曼编码；

[实现提示]

分析： 1. 初始化：将ht[1..m]中的2n-1个结点的3个指针场置空，权值置0；

2. 输入：读入n个叶子的权值存于数组的前n个元素中，形成森林； 3. 合并：对森林中的树进行n－1次合并，产生的新结点存于数组的第i个元素中（n<=i<=m）

合并分两步：（1） 在当前森林中选两个权值最小的结点s1，s2为合并对象；

（2） 将根为左右两个子树组成新树，新树的根为i，则将s1，s2分别送入新树的左右子树指针场中，s1，s2的双亲指针场置为i，且新树的权值

为s1，s2的权值之和。由于s1，s2的双亲指针场已置I，所有再组树时就不会选中它了 [参考程序] # include “stdio.h”

# include “string.h” # include “alloc.h”

typedef struct { int weight ;

int parent , lchild , rchild ; } HTNode , *Huffmantree ; typedef char **Huffmantree ;

Huffmantree ht ; /*存放所建立的哈夫曼树*/

Huffmantree hc; /*存放所有叶结点的哈夫曼编码*/ int n ;

void huffmancoding() {

int i ,j,m,c,f ;

int s1 ,s2 , w1 , w2 ; int start ;

Huffmantree p ;

Char *cd ; /*存放当前叶结点的哈夫曼编码*/ m=2*n-1 ;

ht=(Huffmantree ) malloc ((m+1)*sizeof(HTNode)) ;