数据结构-课程设计——小样儿.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 M,TSMatrix N,TSMatrix &Q)
{
if(M.tu==0||N.tu==0) return ERROR;
Q.mu=M.mu;
Q.nu=N.nu;
Q.tu=0;
for(arow=1;arow<=M.mu;++arow)
{for(ccol=1;ccol<=N.nu;ccol++)
ctemp[ccol]=0;
if(arow<M.mu)
tp=M.rpos[arow+1];
else tp=M.tu+1;
for(p=M.rpos[arow];p<tp;++p)
{brow=M.data[p].j;
if(brow<N.mu)
t=N.rpos[brow+1];
else t=N.tu+1;
for(q=N.rpos[brow];q<t;++q)
{ccol=N.data[q].j;
ctemp[ccol]+=M.data[p].e*N.data[q].e;
}
}
for(ccol=1;ccol<=Q.nu;++ccol)
{if(ctemp[ccol]!=0)
{Q.tu++;
if(Q.tu>MAXSIZE) return ERROR;
Q.data[Q.tu].i=arow;
Q.data[Q.tu].j=ccol;
Q.data[Q.tu].e=ctemp[ccol];}
}
}
return OK;
}
算法时间复杂度为：O(mu * nu)
4、流程图
用户选择计算类型
转置运算
乘法运算
显示结果
等待用户键入选择
Y
N
继续计算
开始
结束

主程序流程图
5、源代码：
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define MAXSIZE 20
#define MAXRC 10
typedef int Status;
typedef int ElemType;
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;
Status CreateSMatrix(TSMatrix &M) /*创建一个稀疏矩阵*/
{
int p=1,a,b,c;
printf("请输入稀疏矩阵的行数,列数,非零元数(请小于20个,用空格隔开各数据):");
scanf("%d %d %d",&M.mu,&M.nu,&M.tu);
if(M.tu>MAXSIZE||M.tu<=0||M.tu>M.mu*M.nu)
{printf("-----出错啦,非零元个数超过最大值!!\n");return ERROR;}
while(p<=M.tu)
{printf("请输入第 %d 个非零元素的行,列,元素值(用空格隔开):",p);
scanf("%d %d %d",&a,&b,&c);
M.data[0].i=0;M.data[0].j=0;
if(a<=M.mu&&b<=M.nu&&c!=0)
{if(a>M.data[p-1].i||(a==M.data[p-1].i&&b>M.data[p-1].j))
{M.data[p].i=a;M.data[p].j=b;M.data[p].e=c;p++;}
else printf("-----出错啦,请从行到列,从小到大输入!!\n");
}
else printf("-----出错啦,所输入数据超出范围!!\n");
if(a==M.mu&&b==M.nu&&p<=M.tu){printf("-----出错啦,输入顺序有误,请认真核查,从头输入!!\n");p=1;}
}
printf("-----输入成功!!\n");
return OK;
}
Status PrintMatrix(TSMatrix M) /*输出一个矩阵*/
{int i,j,p=1;
if(M.tu==0){printf("-----找不到此矩阵或为空矩阵!!\n" );return ERROR;}
printf("---%d行 %d列 %d个非零元素---\n以阵列方式输出为:\n",M.mu,M.nu,M.tu);
for(i=1;i<=M.mu;i++)
{for(j=1;j<M.nu;j++)
{if(i==M.data[p].i&&j==M.data[p].j)
{printf("%d ",M.data[p].e);p++;}
else printf("%d ",0);
}
if(i==M.data[p].i&&j==M.data[p].j)
{printf("%d\n",M.data[p].e);p++;}
else printf("%d\n",0);
}
return OK;
}
Status MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)
{ int arow,brow,p,q,ccol,ctemp[MAXRC+1],t,tp,k=1;
if(M.tu==0||N.tu==0){
printf("-----找不到所需矩阵!!\n" );
return ERROR;}
if(M.nu!=N.mu) {printf("-----此矩阵不能被运算,请核查行列数!!\n" );return ERROR;}
for(p=1;p<=M.tu;p++) /*为M.rpos[] 赋值*/
{if(M.data[p].i==k)
{M.rpos[k]=p;
k++;}
else if(M.data[p].i>k)
{M.rpos[k]=p--;
k++;}
}
for(;k<=M.mu;k++)M.rpos[k]=M.tu;
k=1;
for(q=1;q<=N.tu;q++) /* 为N.rpos[]赋值*/
{if(N.data[q].i==k)
{N.rpos[k]=q;k++;}
else if(N.data[q].i>k)
{N.rpos[k]=p--;k++;}
}
for(;k<=N.mu;k++)N.rpos[k]=N.tu;
Q.mu=M.mu; /*初始化Q*/
Q.nu=N.nu;
Q.tu=0;
for(arow=1;arow<=M.mu;++arow)
{for(ccol=1;ccol<=N.nu;ccol++)
ctemp[ccol]=0;
if(arow<M.mu)
tp=M.rpos[arow+1];
else tp=M.tu+1;
for(p=M.rpos[arow];p<tp;++p)
{brow=M.data[p].j;
if(brow<N.mu)
t=N.rpos[brow+1];
else t=N.tu+1;
for(q=N.rpos[brow];q<t;++q)
{ccol=N.data[q].j;
ctemp[ccol]+=M.data[p].e*N.data[q].e;
}
}
for(ccol=1;ccol<=Q.nu;++ccol) /*将数组的值压缩储存到Q*/
{if(ctemp[ccol]!=0)
{Q.tu++;
if(Q.tu>MAXSIZE) {printf("-----出错啦,非零元个数超出最大值!!\n");return ERROR;}
Q.data[Q.tu].i=arow;
Q.data[Q.tu].j=ccol;
Q.data[Q.tu].e=ctemp[ccol];}
}
}
printf("-----运算成功!!\n");
return OK;
}
Status FastTransposeSMatrix(TSMatrix M,TSMatrix &T) /*求快速稀疏矩阵M的转置矩阵T*/
{
int p,q,k=1;
int cpot[MAXSIZE],num[MAXSIZE];
if(M.tu==0){printf("-----找不到所需矩阵!!\n" );return ERROR;}
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];
}
printf("-----转置成功!!\n");
return OK;
}
void main()
{
int select;
TSMatrix A,B,C;
A.tu=0;B.tu=0;C.tu=0;
printf("0.退出程序\n");
printf("1.创建矩阵 A\n");
printf("2.输出矩阵 A\n");
printf("3.输出矩阵 B\n");
printf("4.输出矩阵 C\n");
printf("5.转置矩阵 A->B\n");
printf("6.矩阵相乘 A*B=C\n");
printf("\n");
while(1)
{
printf("请选择: ");
scanf("%d",&select);
if(select==0)break;
switch(select) {

case 1: CreateSMatrix(A);
break;
case 2: PrintMatrix(A);
break;
case 3: PrintMatrix(B);
break;
case 4: PrintMatrix(C);
break;
case 5: FastTransposeSMatrix(A,B);
break;
case 6: MultSMatrix(A,B,C);
break;
default:printf("输入错误,请认真核查!!\n");
break;
}
}
}
6、运行结果

二、赫夫曼编码
1、程序设计要求
设计一个赫夫曼编码系统，具有一下功能：
1、输入字符和权值，构造赫夫曼树
2、求出各个字符的赫夫曼编码

2、存储结构：
Chr weight parent lchild rchild

赫夫曼树顺序存储结构图

001
1
2
3
4
5

赫夫曼编码存储结构图
赫夫曼树和赫夫曼编码的存储表示：
typedef struct{
char ch;
int weight;
int parent,lchild,rchild;
}htnode,*hfmtree;
typedef char **hfmcode;
3、主要算法设计：
赫夫曼树的建立和编码求解
void hfmcoding(hfmtree &HT,hfmcode &HC,int n){
if(n<=1)return;
m=2*n-1;
HT=(hfmtree)malloc((m+1)*sizeof(htnode));
for(i=1;i<=n;++i){
printf("请输入第%d字符信息和权值：",i);
scanf("%c%d",&z,&w);
while(getchar()!='\n')
{continue;}
HT[i].ch=z;
HT[i].weight=w;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(;i<=m;++i) //初始化其余的结点
{
HT[i].ch='0';
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=n+1;i<=m;++i) //建立赫夫曼树
{
Select(HT,i-1,&p1,&p2);
HT[p1].parent=i;HT[p2].parent=i;
HT[i].lchild=p1;HT[i].rchild=p2;
HT[i].weight=HT[p1].weight+HT[p2].weight;
}
HC=(hfmcode)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;++i) //给n个字符编码
{
start=n-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
{
if(HT[f].lchild==c)
{cd[--start]='0';}
else
{cd[--start]='1';}
}
HC[i]=(char*)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
}
free(cd);
}
时间复杂度为O（n * log2n）

4、流程图
开始
输入字符和权值
构建赫夫曼树
求出赫夫编码
输出字符和编码
结束

主函数流程图
5、源程序
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<fstream.h>
typedef struct{
char ch;
int weight;
int parent,lchild,rchild;
}htnode,*hfmtree;
typedef char **hfmcode;
void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函数
{
int i,j,x,y;
for(j=1;j<=a;++j){
if(HT[j].parent==0){
x=j;
break;}
}
for(i=j+1;i<=a;++i){
if(HT[i].weight<HT[x].weight&&HT[i].parent==0){
x=i; //选出最小的节点
}
}
for(j=1;j<=a;++j) {
if(HT[j].parent==0&&x!=j)
{y=j;
break;}
}
for(i=j+1;i<=a;++i)
{
if(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i)
{y=i; } //选出次小的节点
}
if(x>y){
*p1=y;
*p2=x;
}
else
{*p1=x;
*p2=y;}
}
void hfmcoding(hfmtree &HT,hfmcode &HC,int n) /{
int i,start,c,f,m,w;
int p1,p2;
char *cd,z;
if(n<=1){
return;
}
m=2*n-1;
HT=(hfmtree)malloc((m+1)*sizeof(htnode));
for(i=1;i<=n;++i) //初始化n个叶子结点
{
printf("请输入第%d字符信息和权值：",i);
scanf("%c%d",&z,&w);
while(getchar()!='\n')
{continue;}
HT[i].ch=z;
HT[i].weight=w;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(;i<=m;++i) //初始化其余的结点
{
HT[i].ch='0';
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=n+1;i<=m;++i) //建立赫夫曼树
{
Select(HT,i-1,&p1,&p2);
HT[p1].parent=i;HT[p2].parent=i;
HT[i].lchild=p1;HT[i].rchild=p2;
HT[i].weight=HT[p1].weight+HT[p2].weight;
}
HC=(hfmcode)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;++i) //给n个字符编码
{
start=n-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
{
if(HT[f].lchild==c)
{cd[--start]='0';}
else
{cd[--start]='1';}
}
HC[i]=(char*)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
}
free(cd);
}
int main(){
int n,i;
hfmtree HT;
hfmcode HC;
cout<<"请输入字符个数：";
cin>>n;
//printf("请输入字符个数：");
//scanf("%d",&n);
hfmcoding(HT,HC,n);
for(i=1;i<=n;++i)
{
printf("%c",HT[i].ch);
printf("%s",HC[i]);
printf("\n");
}
}
6、运行结果

心得体会
通过这次的课程设计使我更深刻的了解了数据结构应用，并对数据结构这门课程有了更好的掌握，学会了赫夫曼编码、稀疏矩阵的快速转置和乘法的算法，并编程予以实现。培养了综合运用所学知识,发现,提出,分析和解决实际问题,锻炼了实践操纵能力。
通过这一周的不断努力，终于成功的完成了这次的课程设计，其中遇到很多的问题，以前并不懂的东西，通过老师的帮助和查阅资料都学会了，并运用到了程序中，例如画图函数的应用。同时，我也发现了自己的很多的不足。学习的深入，通过这次的课程设计，对其有了更深入的了解，为以后的学习打响了警钟。
现在，课程设计结束了，但我的学习并没有结束，总结这次的经验，以后在平时学习中要深入、明确，绝对不能模棱两可；要培养自己的实际动手能力，理论和实际毕竟有着差距。

参考文献
《C 语言程序设计》 谭浩强 清华大学出版设
《数据结构（c语言版）》 严蔚敏 清华大学出版社
20