数据结构课程设计——小组任务.docx

数据结构课程设计-小组设计报告专 业： 计算机科学与技术 班 级： 组 号： 10 组长姓名（学号）： 副组长姓名（学号）：组员姓名（学号）：指导教师： 冯向阳 日 期：16年1月6日至16年1月14日目录1组内成员贡献表32 课程设计目的33 课程设计内容和要求34 任务完成情况35 设计名称45.1图45.1.1 设计目的45.1.2 设计内容及要求45.1.3 需求分析55.1.4 概要设计65.1.5 详细代码95.1.6 使用说明95.1.7 测试结果与分析105.2赫夫曼编码的应用135.2.1设计目的135.2.2设计内容及要求135.2.3需求分析145.2.4概要设计145.2.5详细代码145.2.6使用说明145.2.7测试结果与分析145.3 体会与感想146 参考文献14附录14附录一：14附录二：19附录三：24附录四：26附录五：33表1-1 组内成员贡献表1组内成员贡献表姓名（学号）学号贡献度100100100（总计）3002 课程设计目的1、 学习获取知识的方法；2、 提高发现问题、分析问题和解决实际问题的能力；3、 加强创新意识和创新精神；4、 加强团队的分工与合作；5、 掌握面向实际背景思考问题的方法。3 课程设计内容和要求内容： 第一章 前言第二章 顺序表与链表第三章 树与二叉树第四章 图第五章 赫夫曼编码要求：完成第2章、第3章中每章2个设计任务中的至少一个任务。在完成个人任务1的基础上，完成第4章2个设计任务中的至少一个任务。每人必须在完成个人任务的基础上提交个人任务的设计报告，内容包括：任务名称、目的、具体内容、需求分析、概要设计、主要代码分析、测试结果、收获与体会。无论是个人任务还是小组任务希望各小组团队合作，小组成员之间应互相讨论，互相启发。4 任务完成情况任务完成情况介绍，如表3-1. 表3-1 任务完成情况表完成任务名称有向图无向图最小生成树问题赫夫曼编码的应用5 设计名称5.1图5.1.1 设计目的熟悉图的基本应用5.1.2 设计内容及要求1.有向图（1）键盘输入数据，建立一个有向图的邻接表，并输出该邻接表。（2）采用邻接表存储实现有向图的深度优先遍历。（3）试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径（ij）。（4）已有邻接表表示的有向图，请编程判断从第u顶点至第v顶点是否有简单路径，若有则印出该路径上的顶点。（5）在主函数中设计一个简单的菜单，分别调试上述算法。2.无向图 （1）建立一个无向图的邻接表，并输出该邻接表。 （2）采用邻接表存储实现无向图的深度优先遍历。 （3）无向图采用邻接表存储方式，试写出删除边（i，j）的算法，并输出深度优先遍历的结果。（4）在主函数中设计一个简单的菜单，分别调试上述算法。3.选做题：（1）最小生成树问题：若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。设无向图的顶点数不超过30个，并为简单起见，图中边的权值设成小于100的整数。步骤： 1)利用普里姆算法求网的最小生成树。 2)以文本形式输出生成树中各条边以及他们的权值.例.测试运行实例：对下图求最小生成树。5.1.3 需求分析本程序用C编写，通过算法实现图的广度优先遍历和深度优先遍历，并且实现最小生成树和关键路径的基本问题。5.1.4 概要设计1.有向图类文件：Yx.h设计结构体typedef struct BNodeint order;struct BNode *next;bnode;typedef structint info;struct BNode *fnext;hnode;typedef structhnode list50;int n,e;Graph;yx()参数：无功能：构造函数，初始化成员变量void create()参数：无功能：创建有向图的邻接链表void out()参数：无功能：输出邻接链表void DFS(int v)参数：要遍历的起点功能：深度优先遍历void ifExistPath(int x,int y)参数:点x,点y功能:判断是否存在x到y的路径，并依据结果给成员变量sign赋值bool jud()参数：无功能：根据sign的值返回真假void PathAll(int u,int v,int path,int d) 参数：点u,点v,数组,初始值为-1的整型功能：输出所有简单路径2.无向图类文件yx.h设计结构体typedef struct BNodeint order;struct BNode *next;bnode;typedef structint info;struct BNode *fnext;hnode;typedef structhnode list50;int n,e;Graph;wx();参数：无功能：构造函数，初始化成员变量void create()参数：无功能：创建无向图void out()参数：无功能：输出无向图void DFS(int v)参数：无功能：深度优先遍历void deleteB(int x,int y)参数：边的起点，终点功能：删除边Main.cppint main()参数：无功能：程序入口文件3.选作题1.最小生成树设计结构体:struct graphint edgesMAXSIZEMAXSIZE;int n;create()参数：无功能：创建图的邻接矩阵Prim()参数：无功能：1)利用普里姆算法求网的最小生成树。 2)以文本形式输出生成树中各条边以及他们的权值. 2.关键路径问题类文件yx.h设计结构体typedef struct ANode/表节点int adjvex;struct ANode * nextarc;int info;/权值ArcNode;typedef struct Vnode/头节点int data;ArcNode * firstarc;VNode;typedef struct/图VNode adjlistMAXV;int n,e;ALGraph;yx()参数:无功能：构造函数void create()参数：无功能：创建有向图邻接表void out()参数：无功能：输出有向图邻接矩阵void du()参数：无功能：计算各点的度void earlyTime()参数：无功能：计算各事件的最早可发生时间void lastTime()参数：无功能：计算各事件的最迟可发生时间void eventTime()参数：无功能：计算各活动的最早开始时间和最迟开始时间void keyPath()参数：无功能：计算关键路径5.1.5 详细代码有向图见附录一无向图见附录二最小生成树问题见附录三5.1.6 使用说明按菜单选作使用功能。5.1.7 测试结果与分析1.2. 33.3. 5.2赫夫曼编码的应用5.2.1设计目的熟悉对图的基本操作及应用图解决实际问题1.对有向图的基本2.无向图的3.对图的应用5.2.2设计内容及要求对附件中的”RFCdoc.txt”统计字符出现的频率，并以此频率为依据对所有字符进行赫夫曼编码。然后，对”RFCdoc.txt”文件按照以上得到的编码规则进行编码，得到的编码输出到一个文本文件，该文件的内容仅包含0和1。比如，字符“E”对应的编码为“001”，则将三个字符“001”输出到文本文件中。编码完成后，请观察生成的编码文件的字节数，并将该数字记录到实验报告中。编码完成后，请在屏幕上输出频率最高的5个字符以及它对应的频率和赫夫曼编码。然后再对编码得到的文件进行译码，并对比译码得到的文件和”RFCdoc.txt”。程序运行的结果：l 生成编码文件（可用记事本打开查看内容）；l 在屏幕上输出5个出现频率最高的字符以及它对应的频率和赫夫曼编码；l 生成译码文件5.2.3需求分析本程序用C编写，实现文件的输入输出, 赫夫曼二叉树的建立, 赫夫曼码的生成, 赫夫曼码的编译等功能。本程序自动运行，没有使用菜单。5.2.4概要设计int Hash(char key)操作结果：设定无冲突的哈希函数InitHashTable(HashTable &H) 操作结果：将每个节点的ferq置零statistics(HashTable &H,FILE *fhead)操作结果：接收文件中读出的字符并作出相应的操作Select(HuffmanTree &HT,int n,int *s1,int *s2)操作结果：选择最小的两个数创建结点HuffmanCoding(HuffmanTree &HT,HashTable &H)操作结果： 存放n个字符的权值（均0），构造赫夫曼树HT,并求出n个字符的赫夫曼编码HCMenu()菜单文件test1(HashTable H)操作结果：生成RFCdoc.txt的编码文件test2(HashTable H)操作结果：测试出文件中出现次数最多的5个字符并且输出其对应的次数和哈夫曼编码test3(HashTable &H,HuffmanTree HT)操作结果：创建相对应得编码文件Translate.txtmain()操作结果：主函数进行相应的操作控制整个函数5.2.5详细代码详细赫夫曼编码见附录五5.2.6使用说明通过菜单文件，输入选项进行相应操作5.2.7测试结果与分析5.3 体会与感想这次在做小组任务的课程设计时我们小组遇到了很多的问题，一个方面是因为我们的基础知识都不够扎实，另外一个方面是因为我们思考的不够全面，导致我们一直没有完整的做出来，最后的哈夫曼树的问题我们还是没有解决，老师要求的是计算出单词的输出频率，但是我们还是没有做出来，只是编写出了计算单个字符的程序，导致我们的课程设计还有遗憾，在未来的学习过程中我们会更加深入研究不懂得问题，扎实我们的基础。6 参考文献附录附录一：有向图：#includeyx.hint main()yx yxb;int choice;int sign;int start;sign=0;cout1.建立有向图的邻接链表并输出endl;cout2.DFSendl;cout3.判断两点间是否存在路径endl;cout4.输出两点间所有的简单路径endl;cout5.退出endl;cout输入序号进行选择choice;while(choice!=5)switch(choice)case 1:yxb.create();cout建立的邻接表如下endl;yxb.out();sign=1;break;case 2:if(sign!=0)cout输入起点start;yxb.DFS(start);elsecout你还没有建立有向图的邻接表endl;break;case 3:int x,y;coutx;ciny;yxb.ifExistPath(x,y);if(yxb.jud()cout路径存在endl;else cout路径不存在;case 4:int path100;yxb.PathAll(1,9,path,-1);break;default:cout没有该选项endl;break;cout选择选项choice;#include#includemalloc.husing namespace std;int visited50=0;class yxtypedef struct BNodeint order;struct BNode *next;bnode;typedef structint info;struct BNode *fnext;hnode;typedef structhnode list50;int n,e;Graph;private:Graph *ga;int sign;public:yx()ga=(Graph *)malloc(sizeof(Graph);sign=0;void create()int i,j,e,k,start,end;BNode *p;cout请输入顶点数和边数ga-n;cinga-e;for(i=1;in;i+) cout输入节点i的信息;ga-listi.fnext=NULL;for(i=1;ie;i+)cout输入第i条边的起点和终点startend;/输入边的起始和终止p=(BNode *)malloc(sizeof(BNode);/创建一个表结点if(p=NULL)return;p-order=end;p-next=ga-liststart.fnext;/新加入的节点都是在头结点之后，原来在头结点之后的节点要后移。ga-liststart.fnext=p;void out()bnode *temp=(BNode *)malloc(sizeof(BNode);int i;for(i=1;in;i+);temp=ga-listi.fnext;while(temp!=NULL)coutorder;temp=temp-next;coutendl;void DFS(int v)bnode *p;visitedv=1;coutlistv.fnext;while(p!=NULL)if(visitedp-order=0)DFS(p-order);p=p-next;coutlistx.fnext;q=ga-listx.fnext;while(p!=NULL)if(p-order!=y)p=p-next;elsesign=1;break;while(q!=NULL&sign!=1)ifExistPath(q-order,y);q=q-next;bool jud()if(sign=1)return true;elsereturn false;void PathAll(int u,int v,int path,int d) /输出u到v所有简单的路径BNode *p;int i,w;visitedu=1;d+;pathd=u;if(u=v&d=1)cout一条简单路径为：;for(i=0;i=d;i+)coutpathi;coutlistu.fnext;while(p!=NULL)w=p-order;if(visitedw=0)PathAll(w,v,path,d);p=p-next;visitedu=0;附录二：无向图：#include#includemalloc.husing namespace std;int visited50=0;class wxtypedef struct BNodeint order;struct BNode *next;bnode;typedef structint info;struct BNode *fnext;hnode;typedef structhnode list50;int n,e;Graph;private:Graph *ga;public:wx()ga=(Graph *)malloc(sizeof(Graph);void create() bnode *p; int info; int i; cout输入点的个数ga-n; for(i=1;in;i+) cout输入顶点i的信息; ga-listi.fnext=NULL; for(i=1;in;i+) cout输入顶点i相邻的顶点(输入0结束)next=NULL; cininfo; if(info=0) break; p-order=info; if(ga-listi.fnext=NULL) ga-listi.fnext=p; else p-next=ga-listi.fnext;ga-listi.fnext=p; void out()bnode *temp=(BNode *)malloc(sizeof(BNode);int i;for(i=1;in;i+);temp=ga-listi.fnext;while(temp!=NULL)coutorder;temp=temp-next;coutendl;void DFS(int v)bnode *p;visitedv=1;coutlistv.fnext;while(p!=NULL)if(visitedp-order=0)DFS(p-order);p=p-next;void deleteB(int x,int y)bnode *temp=(BNode *)malloc(sizeof(BNode);int i;for(i=1;in;i+)if(=x)temp=ga-listi.fnext;if(temp!=NULL)if(temp-order=y)ga-listi.fnext=temp-next;if(temp!=NULL)while(temp-next!=NULL)if(temp-next-order=y)temp-next=temp-next-next;temp=temp-next;if(temp=NULL) break;if(=y)temp=ga-listi.fnext;if(temp!=NULL)if(temp-order=x)ga-listi.fnext=temp-next;if(temp!=NULL)while(temp-next!=NULL)if(temp-next-order=x)temp-next=temp-next-next;temp=temp-next;if(temp=NULL) break;int main()wx wxb;char choice;int sign;int start;int x,y;sign=0;cout1.建立无向图的邻接链表并输出endl;cout2.DFSendl;cout3.删除边endl;cout4.退出endl;cout输入序号进行选择choice;while(choice!=4)switch(choice)case 1:wxb.create();cout建立的邻接表如下endl;wxb.out();sign=1;break;case 2:if(sign!=0)cout输入起点start;wxb.DFS(start);elsecout你还没有建立有向图的邻接表endl;break;case 3:if(sign!=0)coutx;ciny;wxb.deleteB(x,y);wxb.out();cout输入深度优先遍历的起点start;wxb.DFS(start);elsecout你还没有建立有向图的邻接表endl;break;case 4:break;default:cout没有该选项endl;break;coutn选择选项choice;附录三：最小生成树问题#include#include#include#includeusing namespace std;#define MAXSIZE 100#define INF 32767struct graphint edgesMAXSIZEMAXSIZE;int n;void create(graph &g)int num;int j;int qz;coutg.n;for(int i=0;ig.n;i+)for(int a=0;ag.n;a+)if(i=a)g.edgesia=0;elseg.edgesia=INF;for(int i=0;ig.n;i+)cout输入点inum;for(int a=0;anum;a+)cout输入点ij;cinqz;g.edgesij=qz;void Prim(graph g,int v)int lowcostMAXSIZE;int min;int closestMAXSIZE,i,j,k; FILE *fp;fp=fopen(result.txt,w);for(i=0;ig.n;i+)lowcosti=g.edgesvi;closesti=v;for(i=1;ig.n;i+)min=INF;for(j=0;jg.n;j+)if(lowcostj!=0&lowcostjmin)min=lowcostj;k=j;cout边(closestk,k)的权为:minendl; fprintf(fp,边（%d,%d)权为：%dn,closestk,k,min);lowcostk=0;for(j=0;jg.n;j+)if(g.edgeskj!=0&g.edgeskjlowcostj)lowcostj=g.edgeskj;closestj=k;fclose(fp);int main()graph g;create(g);Prim(g,0);getchar();getchar();return 0; 附录五：#include#include#include#includetypedef struct int weight; char data; int parent,lchild,rchild; HTNode,*HuffmanTree; /动态分配数组存储赫夫曼树typedef char *HuffmanCode;/动态分配数组存储赫夫曼编码表typedef struct int key;/关键字 int freq;/频率 char *HC;/赫夫曼编码 ElemNode;typedef struct ElemNode *elem; int count;/当前数据元素个数 int size;/容量 HashTable;int Hash(char key)/无冲突的哈希函数 return (int)key-10;void InitHashTable(HashTable &H)/将每个节点的ferq置零 int i; int n = 120;/初始化一个长度为120的哈希表 H.size = n; H.count = 0; H.elem = (ElemNode*)malloc(sizeof(ElemNode)*n); for(i = 0; i 120; i+) H.elemi.freq = 0;void PrintHashTable(HashTable H) for(int i = 0; i 120; i+) if(H.elemi.freq != 0) printf(字符 %c ，次数为：%dn赫夫曼编码为：%sn,H.elemi.key,H.elemi.freq,H.elemi.HC);void statistics(HashTable &H,FILE *fhead) char c;/接收文件中读出的字符 c = fgetc(fhead); while(c != EOF) if(H.elemHash(c).freq = 0) H.count+; H.elemHash(c).key = c; H.elemHash(c).freq+; c = fgetc(fhead); /哈夫曼树void Select(HuffmanTree &HT,int n,int *s1,int *s2) int w1 = 0,w2 = 0; int i; HuffmanTree p; for(p = HT, i = 0; i parent = 0) if( !w1) w1 = p-weight; *s1 = i; else if(!w2) if(p-weight weight; *s1 = i; else w2 = p-weight; *s2 = i; else if(p-weight weight; *s1 = i; else if(p-weight weight; *s2 = i; void HuffmanCoding(HuffmanTree &HT,HashTable &H)/w 存放n个字符的权值（均0），构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC int i,c,start,f,t=0; int n = H.count; HuffmanTree p; if(n = 1) return; int m = 2 * n - 1; HT=(HuffmanTree)malloc(m*sizeof(HTNode); for(p = HT, i = 0; i weight = H.elemi.freq; p-data = H.elemi.key; p-parent = p-rchild = p-lchild = 0; p+; for(i = n; i lchild = p-parent = p-rchild = p-weight = 0; for(i = n; i m; i+) /建赫夫曼树,在HT0.i-1选择parent为0且weight最小的两个节点 /其序号分别为s1和s2 int s1,s2; Select(HT,i-1,&s1,&s2); HTs1.parent = i; HTs2.parent=i; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; /HuffmanCode HC=(HuffmanCode)malloc(n+1)*sizeof(char *); char *cd = (char*)malloc(n*sizeof(char); cdn - 1 = 0; for(i = 0; i n; +i) start = n - 1; for(c = i, f = HTi.parent; f != 0; c = f, f = HTf.parent) if(HTf.lchild = c) cd-start = 0 ; else cd-start = 1; for(; H.elemt.freq = 0; t+); H.elemt.HC = (char *)malloc(n - start)*sizeof(char); strcpy(H.elemt.HC,&cdstart); t+; free(cd);void Menu() printf(=n); printf( 1.生成RFCdoc.txt的编码文件n); printf( 2.显示出现频率最高的5个字符n); printf( 3.生成译码文件n); printf( 0.退出程序n); printf(=n);void te