数据结构 课程设计——小样儿.doc

摘 要 《数据结构》主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 算法与数据结构旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。 本次课程设计主要应用基本的数据结构知识，顺序表实现稀疏矩阵的快速转置和乘法、赫夫曼编码，更深刻的了解数据结构的实际意义，实现课本算法。 关键词：赫夫曼编码，稀疏矩阵，快速转置，矩阵乘法 目 录 一、稀疏矩阵的快速转置和乘法 1 1、程序设计要求 1 2、存储结构 1 3、主要算法设计 2 4、流程图 4 5、源代码： 5 6、运行结果 11 二、赫夫曼编码 12 1、程序设计要求 12 2、存储结构： 12 3、主要算法设计： 13 4、流程图 14 5、源程序 15 6、运行结果 19 心得体会 19 参考文献 20 一、稀疏矩阵的快速转置和乘法 1、程序设计要求 1．以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现矩阵的转置和两个矩阵相乘的运算 2．首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。可设矩阵的行数和列数均不超过20。 3. 本程序中，按提示入相应的数据，由用户在键盘上输入演示程序中规定的输入数据。这里输入的数据值为整型。 2、存储结构 用三元组表示稀疏矩阵各元素： row col value 三元组的结构图 用顺序存储结构表示三元组表： Row Col Value 顺序存储结构图 稀疏矩阵的三元组顺序表存储结构： typedef struct{ int i,j; /*行下标,列下标*/ ElemType e; /*非零元值*/ }Triple; typedef struct { Triple data[MAXSIZE+1]; /*零元三元组表,data[0]未用*/ int rpos[MAXRC+1]; int mu,nu,tu; /*阵的行数、列数和非零元个数*/ }TSMatrix; 3、主要算法设计 抽象数据类型稀疏矩阵的定义如下： ADT SparseMatrix{ 数据对象：D={aij|i=1,2,3……..,m; j=1,2,3…….,n; Aij属于Elemset,m和n分别称为矩阵的行数和列数} 数据关系：R={Row,Col} Row={ai,j,ai,j+1| 1=i=m,1=j=n-1} Col={ai,j,ai+1,j| 1=i=m-1,1=j=n} 基本操作； CreateSMatrix(M); 操作结果：创建稀疏矩阵M; PrintSMatrix(M); 初始条件：稀疏矩阵M存在。 操作结果：输出稀疏矩阵M; TransposeSmatrix(M,N)?; 初始条件：稀疏矩阵M存在。 操作结果：输出稀疏矩阵N MultSMatrix(M,N,Q); 初始条件：稀疏矩阵M的行数等于N的列数。 操作结果：求稀疏矩阵的和Q=M*N. }ADT SparseMatrix （1）、快速转置算法： Status TransposeSMatrix(TSMatrix M,TSMatrix T) { T.mu=M.nu;T.nu=M.mu;T.tu=M.tu; for(p=1;p=M.nu;++p) num[p]=0; for(q=1;q=M.tu;++q) ++num[M.data[q].j]; cpot[1]=1; for(p=2;p=M.nu;++p) cpot[p]=cpot[p-1]+num[p-1]; for(q=1;q=M.tu;++q) { p=M.data[q].j; k=cpot[p]; T.data[k].i=M.data[q].j; T.data[k].j=M.data[q].i; T.data[k].e=M.data[q].e; ++cpot[p]; } return OK; } 算法时间复杂度为：O(mu + nu) （2）、矩阵乘法算法： Status MultSMatrix(TSMatrix