《数据结构 课程设计——小样儿.doc》由会员分享，可在线阅读，更多相关《数据结构 课程设计——小样儿.doc（21页珍藏版）》请在三一文库上搜索。
1、摘 要 数据结构主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。算法与数据结构旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。本次课程设计主要应用基本的数据结构知识，顺序表实现稀疏矩阵的快速转置和乘法、赫夫曼编码，更深刻的了解数据结构
2、的实际意义，实现课本算法。 关键词：赫夫曼编码，稀疏矩阵，快速转置，矩阵乘法目 录一、稀疏矩阵的快速转置和乘法11、程序设计要求12、存储结构13、主要算法设计24、流程图45、源代码：56、运行结果11二、赫夫曼编码121、程序设计要求122、存储结构：123、主要算法设计：134、流程图145、源程序156、运行结果19心得体会19参考文献20一、稀疏矩阵的快速转置和乘法1、程序设计要求1以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现矩阵的转置和两个矩阵相乘的运算2首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。可设矩阵的行数和列数均不超过2
3、0。3. 本程序中，按提示入相应的数据，由用户在键盘上输入演示程序中规定的输入数据。这里输入的数据值为整型。2、存储结构用三元组表示稀疏矩阵各元素：rowcolvalue该非零元素所在的行值该非零元素所在的列值该非零元素所在的值 三元组的结构图用顺序存储结构表示三元组表：RowColValue 顺序存储结构图稀疏矩阵的三元组顺序表存储结构：typedef struct int i,j; /*行下标,列下标*/ ElemType e; /*非零元值*/Triple;typedef struct Triple dataMAXSIZE+1; /*零元三元组表,data0未用*/ int rposMA
4、XRC+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,ColRow=| 1=i=m,1=j=n-1Col=| 1=i=m-1,1=j=n基本操作；CreateSMatrix(&M);操作结果：创建稀疏矩阵M;PrintSMatrix(M);初始条件：稀疏矩阵M存在。操作结果：输出稀疏矩阵M;TransposeSmatrix(M,N
5、);初始条件：稀疏矩阵M存在。操作结果：输出稀疏矩阵NMultSMatrix(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) nump=0;for(q=1;q=M.tu;+q) +numM.dataq.j;cpot1=1;for(p=2;p=M.nu;+p) cpotp=cpotp-1+nump-1; fo
6、r(q=1;q=M.tu;+q) p=M.dataq.j; k=cpotp; T.datak.i=M.dataq.j; T.datak.j=M.dataq.i; T.datak.e=M.dataq.e; +cpotp; 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(cc
7、ol=1;ccol=N.nu;ccol+) ctempccol=0; if(arowM.mu)tp=M.rposarow+1; else tp=M.tu+1; for(p=M.rposarow;ptp;+p) brow=M.datap.j; if(browN.mu) t=N.rposbrow+1; else t=N.tu+1; for(q=N.rposbrow;qt;+q) ccol=N.dataq.j; ctempccol+=M.datap.e*N.dataq.e; for(ccol=1;ccolMAXSIZE) return ERROR;Q.dataQ.tu.i=arow;Q.dataQ.
8、tu.j=ccol;Q.dataQ.tu.e=ctempccol; return OK;算法时间复杂度为：O(mu * nu)4、流程图用户选择计算类型转置运算乘法运算显示结果等待用户键入选择YN继续计算开始结束主程序流程图5、源代码：#include #include #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define MAXSIZE 20 #define MAXRC 10typedef int Status;typedef int ElemType;typedef struct int i,j; /*行下标,列下标
9、*/ ElemType e; /*非零元值*/Triple;typedef struct Triple dataMAXSIZE+1; /*零元三元组表,data0未用*/ int rposMAXRC+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.tuMAXSIZE|M.t
10、uM.mu*M.nu) printf(-出错啦,非零元个数超过最大值!n);return ERROR;while(p=M.tu) printf(请输入第 %d 个非零元素的行,列,元素值(用空格隔开):,p); scanf(%d %d %d,&a,&b,&c); M.data0.i=0;M.data0.j=0; if(a=M.mu&bM.datap-1.i|(a=M.datap-1.i&bM.datap-1.j) M.datap.i=a;M.datap.j=b;M.datap.e=c;p+; else printf(-出错啦,请从行到列,从小到大输入!n); else printf(-出错啦,
11、所输入数据超出范围!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;jM.nu;j+) if(i=M.da
12、tap.i&j=M.datap.j) printf(%d ,M.datap.e);p+;else printf(%d ,0); if(i=M.datap.i&j=M.datap.j) printf(%dn,M.datap.e);p+;else printf(%dn,0); return OK;Status MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q) int arow,brow,p,q,ccol,ctempMAXRC+1,t,tp,k=1; if(M.tu=0|N.tu=0)printf(-找不到所需矩阵!n );return ERROR; if
13、(M.nu!=N.mu) printf(-此矩阵不能被运算,请核查行列数!n );return ERROR;for(p=1;pk) M.rposk=p-; k+;for(;k=M.mu;k+)M.rposk=M.tu;k=1;for(q=1;qk) N.rposk=p-;k+; for(;k=N.mu;k+)N.rposk=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+) ctempccol=0; if(arowM.mu) tp=M.rposa
14、row+1; else tp=M.tu+1; for(p=M.rposarow;ptp;+p) brow=M.datap.j; if(browN.mu) t=N.rposbrow+1; else t=N.tu+1; for(q=N.rposbrow;qt;+q) ccol=N.dataq.j; ctempccol+=M.datap.e*N.dataq.e; for(ccol=1;ccolMAXSIZE) printf(-出错啦,非零元个数超出最大值!n);return ERROR;Q.dataQ.tu.i=arow;Q.dataQ.tu.j=ccol;Q.dataQ.tu.e=ctempcco
15、l; printf(-运算成功!n); return OK;Status FastTransposeSMatrix(TSMatrix M,TSMatrix &T) /*求快速稀疏矩阵M的转置矩阵T*/ int p,q,k=1;int cpotMAXSIZE,numMAXSIZE;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) nump=0;for(q=1;q=M.tu;+q) +numM.dataq.j;cpot1=1;for(p=2;p=M.nu;+p) c
16、potp=cpotp-1+nump-1; for(q=1;qBn);printf(6.矩阵相乘 A*B=Cn);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)
17、; break; case 6: MultSMatrix(A,B,C); break; default:printf(输入错误,请认真核查!n); break; 6、运行结果二、赫夫曼编码1、程序设计要求设计一个赫夫曼编码系统，具有一下功能：1、输入字符和权值，构造赫夫曼树2、求出各个字符的赫夫曼编码 2、存储结构： Chr weight parent lchild rchild赫夫曼树顺序存储结构图00112345 赫夫曼编码存储结构图赫夫曼树和赫夫曼编码的存储表示：typedef struct char ch;int weight; int parent,lchild,rchild;htn
18、ode,*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;HTi.ch=z;HTi.weight=w;HTi.parent=0;HTi.lchild=0;HTi.
19、rchild=0;for(;i=m;+i) /初始化其余的结点HTi.ch=0;HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i=m;+i) /建立赫夫曼树Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.weight;HC=(hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(cha
20、r);cdn-1=0;for(i=1;i=n;+i) /给n个字符编码start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);时间复杂度为O（n * log2n）4、流程图开始输入字符和权值构建赫夫曼树求出赫夫编码输出字符和编码结束主函数流程图5、源程序#include#include#include#include#inc
21、ludetypedef 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(HTj.parent=0)x=j;break;for(i=j+1;i=a;+i)if(HTi.weightHTx.weight&HTi.parent=0)x=i; /选出最小的节点for(j=1;j=a;+j)if(HTj.
22、parent=0&x!=j)y=j;break;for(i=j+1;i=a;+i)if(HTi.weighty)*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
23、);while(getchar()!=n)continue;HTi.ch=z;HTi.weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i=m;+i) /初始化其余的结点HTi.ch=0;HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i=m;+i) /建立赫夫曼树Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight
24、+HTp2.weight;HC=(hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;+i) /给n个字符编码start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);int main()int n,i;
25、hfmtree HT;hfmcode HC;coutn; /printf(请输入字符个数：);/scanf(%d,&n);hfmcoding(HT,HC,n);for(i=1;i=n;+i)printf(%c,HTi.ch);printf(%s,HCi); printf(n);6、运行结果心得体会通过这次的课程设计使我更深刻的了解了数据结构应用，并对数据结构这门课程有了更好的掌握，学会了赫夫曼编码、稀疏矩阵的快速转置和乘法的算法，并编程予以实现。培养了综合运用所学知识,发现,提出,分析和解决实际问题,锻炼了实践操纵能力。通过这一周的不断努力，终于成功的完成了这次的课程设计，其中遇到很多的问题，以前并不懂的东西，通过老师的帮助和查阅资料都学会了，并运用到了程序中，例如画图函数的应用。同时，我也发现了自己的很多的不足。学习的深入，通过这次的课程设计，对其有了更深入的了解，为以后的学习打响了警钟。现在，课程设计结束了，但我的学习并没有结束，总结这次的经验，以后在平时学习中要深入、明确，绝对不能模棱两可；要培养自己的实际动手能力，理论和实际毕竟有着差距。参考文献C 语言程序设计 谭浩强 清华大学出版设数据结构（c语言版） 严蔚敏 清华大学出版社20