数据结构实验报告.docx

数据结构实验报告数据结构实验报告目录数据结构实验报告1第1章 概述31.1 实验目的31.2 实验内容31.3 实验环境3第2章 项目1：职工信息系统42.1 实验项目42.2 存储结构设计42.3 项目程序结构52.4 实验数据和实验结果分析62.5 实验源程序9第3章 项目2：哈夫曼编码系统163.1 实验项目163.2 储存结构设计163.3 项目程序结构173.4 实验数据和实验结果分析183.5 实验源程序20第4章 项目3：两种算法求图的最小生成树274.1 实验项目274.2 储存结构设计274.3 程序结构设计274.4 实验数据和实验结果分析284.5 实验源程序30第5章 实验小节34第1章 概述 1.1 实验目的“数据结构”是计算机科学与技术专业和相关专业的一门重要的专业基础课。在计算机软件类课程体系中处于承上启下的核心地位，它一方面扩展和深化在离散数学、程序设计语言等课程学到的基本技术和方法，另一方面为进一步学习其他专业课（如算法设计与分析、操作系统、软件工程等）奠定坚实的理论与实践基础。数据结构课程主要学习线性结构、树形结构和图形结构等各种类型数据结构的逻辑特性、基本运算算法设计和应用方法。数据结构实验的目的是通过上机实验加深对课程内容的理解，增加对各种数据结构的感性认识，提高软件设计、编写及调试程序的能力。1.2 实验内容 我的的实验内容如下：（1）线性结构部分：员工信息系统。（2）树形结构部分：哈夫曼编码系统。（3）图形结构部分：两种算法求图的最小生成树。1.3 实验环境 我的的实验环境采用Dev-C+ 5.11。第2章 项目1：职工信息系统 2.1 实验项目【问题描述】从职工数据文件(emp.txt)中读取数据，每个职员记录包含职员编号(no),姓名（name）,部门号（depno）和工资数（salary）信息,编写一个程序，完成以下功能：输入、整理员工记录，删除所有员工记录，按编号、部门号、工资数整理员工信息记录，将员工信息记录存档到职工数据文件中。【输入】员工信息数据文件(emp.txt)。【输出】经整理的员工信息。2.2 存储结构设计采用带头节点的单链表存储员工信息，单链表节点的类型定义如下：struct emp /定义员工信息数据类型 int no; char name10; int depno; float salary; ;typedef struct LNode/定义单链表节点类型emp data;struct LNode *next;LinkList;例如，员工“acdb”对应的单链表如图2.1所示。acdbL图2.1 一个带头节点的单链表2.3 项目程序结构项目程序结构如图2.2所示。其中各个函数的功能说明如下： void FunctionList()：说明系统功能。 void DispList(LNode *L)：输出全部员工信息。 void DestroyList(LNode *&L)：释放单链表并删除职工文件中的全部记录。 bool CreateList(LNode *&L)：将员工信息从数据文件中读取出来并建立单链表L。 void FDispList(LNode *L)：将单链表L中的所有职工记录存储到职工文件emp.txt中。 bool InsertEmp(LNode *&L,emp e)：新建员工信息记录。 LNode *sortList(LNode *L,int kind)：按编号no或部门号depno或工资数salary对所有职工记录进行递增排序。 main()：首先从数据文件读入数据，再采用尾插法建立单链表，再根据用户输入的信息完成相应的功能。图2.2 项目程序结构2.3.1 单链表递增快速排序sortList()算法设计输入：单链表L，排序关键字kind输出：L过程如下：当单链表多于一个元素时调用mergeSort函数 置p=L; q=L; pre=NULL;p!=NULL&q-next!=NULL时循环q=q-next-next; pre=p; p=p-next; 置pre=NULL;此时可以得到一个小于key的链表和大于等于key的链表；由此递归可以对两个链表分别进行快速排序：LNode *lhalf=mergeSort(L,kind); LNode *rhalf=mergeSort(p,kind); 调用LNode * merge(LNode *lh, LNode *rh,int kind)函数可将左右链表链接起来。2.3.2 新建员工信息InsertEmp()函数设计输入：单链表L，员工信息e输出：添加是否成功过程如下：P指向单链表最后一个数据节点;创建s节点;令s-data=e;s-next=p-next;p-next=s;2.3.3员工信息存档FDispList()函数设计输入：单链表L输出：过程如下：先清空原有数据文件中的内容，在将整个单链表输出到数据文件中2.4 实验数据和实验结果分析本实验数据文件内容如图2.3所示：图2.3实验结果如图2.4-2.7所示。通过直观验证，实验结果是正确的。1）查看职员信息：图2.4 实验结果-12）新增成员信息并查看：图2.5 实验结果-23）对数据排序（以按部门号为例）：图2.6 实验结果-34）数据存档（图为存档完成后的数据文件内容）：图2.7 实验结果-42.5 实验源程序本实验源程序如下：#include#include#includeFILE * fp= fopen(emp.txt, r);struct emp int no; char name10; int depno; float salary; ;struct LNode emp data; struct LNode *next; ;LNode * merge(LNode *lh, LNode *rh,int kind) LNode *temp=(LNode *)malloc(sizeof(LNode) ; LNode *p=(LNode *)malloc(sizeof(LNode) ; LNode *min=(LNode *)malloc(sizeof(LNode) ;p=temp; while(lh&rh) if(kind=1) if(lh-data.nodata.no) /min=lh; p-next=lh; lh=lh-next; else / min=rh p-next=rh; rh=rh-next; else if(kind=2)if(lh-data.depnodata.depno) /min=lh; p-next=lh; lh=lh-next; else /min=rh; p-next=rh; rh=rh-next; else if(kind=3)if(lh-data.salarydata.salary) /min=lh; p-next=lh; lh=lh-next; else /min=rh; p-next=rh; rh=rh-next; else printf(选择错误，请重新操作n);return NULL; p=p-next; if(!lh) p-next=rh; else p-next=lh; p=temp-next; temp-next=NULL; delete temp; return p; bool z=0;LNode * mergeSort(LNode *L,int kind) z=1; if(!L|!L-next) return L; LNode *p, *q, *pre=NULL; p=(LNode *)malloc(sizeof(LNode); q=(LNode *)malloc(sizeof(LNode); pre=(LNode *)malloc(sizeof(LNode);p=L; q=L; pre=NULL; while(q&q-next!=NULL) q=q-next-next; pre=p; p=p-next; pre-next=NULL; LNode *lhalf=mergeSort(L,kind); LNode *rhalf=mergeSort(p,kind); return merge(lhalf, rhalf,kind); LNode *sortList(LNode *L,int kind) if(!L|!L-next) return L; return mergeSort(L,kind); void DispList(LNode *L) LNode *p=L-next;while(L!=NULL&p!=NULL)printf(No: %d ,p-data.no);printf(Name: %s ,);printf(Defno: %d ,p-data.depno);printf(Salary: %.2fn,p-data.salary);p=p-next;if(z&!p-next-next) break; void FunctionList()printf(本系统功能如下:n);printf(1、新增职员信息。n);printf(2、查看所有职员信息。n);printf(3、整理职员信息。n);printf(4、删除全部员工记录。n);printf(5、记录存档。n); printf(0、退出本系统。n); printf(请选择(0-5)nn);void FDispList(LNode *L) FILE *fp2= fopen(emp.txt, w);LNode *p=L-next;while(p!=NULL)fprintf(fp2,No %d ,p-data.no);fprintf(fp2,Name %s ,);fprintf(fp2,Defno %d ,p-data.depno); if(p-next!=NULL)fprintf(fp2,Salary %.2fn,p-data.salary); else fprintf(fp2,Salary %.2f,p-data.salary);p=p-next;printf(存档完成。n);fclose(fp2); bool CreateEmp(LNode *&L)if (fp=NULL ) puts(不能打开文件！); return false; char s50; LNode *p,*r; L=(LNode*) malloc(sizeof(LNode);r=L; int i=0; while(!feof(fp) p=(LNode *) malloc(sizeof(LNode); fscanf(fp,%s,s); emp e; /printf(%s ,s); fscanf(fp,%d,&e.no); fscanf(fp,%s ,s); /printf(%d,e.no); fscanf(fp,%s,&); fscanf(fp,%s,s);/printf(%s ,s); fscanf(fp,%d,&e.depno); fscanf(fp,%s,s);/printf(%s n,s); fscanf(fp,%f,&e.salary); p-data=e; r-next=p; r=p; r-next=NULL;return true;bool InsertEmp(LNode *&L,emp e) / printf(1);LNode *p=L-next,*s;while(p-next!=NULL)p=p-next;/printf(2);if(p=NULL) return false;else s= (LNode*) malloc(sizeof(LNode);s-data=e;s-next=p-next;p-next=s;/printf(3);return true;void DestroyList(LNode *&L)LNode *pre=L,*p=L-next;while(p!=NULL)free(pre);pre=p;p=pre-next;L-next=NULL;free(pre); printf(删除完成n); int main()FILE * fp= fopen(emp.txt, r+);int act;LNode *L;if(CreateEmp(L)printf(欢迎使用员工信息系统n); elseprintf(系统数据文件打开错误);return 0;FunctionList();while(scanf(%d,&act)=1)if(act=1)emp e;printf(请输入工号:n);scanf(%d,&e.no);printf(请输入姓名:n);scanf(%s,&);printf(请输入部门号:n);scanf(%d,&e.depno);printf(请输入工资:n);scanf(%f,&e.salary);if(InsertEmp(L,e)printf(信息录入完成n); if(act=2)DispList(L);if(act=3)printf(请输入整理类型：（123）n);printf(1、按编号对所有职工记录进行整理。n);printf(2、按部门号对所有职工记录进行整理。n);printf(3、按工资数对所有职工记录进行整理。n);int sort_choice;scanf(%d,&sort_choice); L=sortList(L,sort_choice); printf(整理完成n); if(act=4) DestroyList(L); if(act=5) FDispList(L); if(act=0) exit(0); if(act=6) FunctionList(); printf(n请输入下一步操作，如需帮助请按6n); fclose(fp); return 0; 第3章 项目2：哈夫曼编码系统 3.1 实验项目【问题描述】从文件读入字符信息，实现统计字符权值并构造一颗Huffman树，实现Huffman编码。 【输入】数据文件hf.txt【输出】字符权值、哈夫曼树、字符的哈夫曼编码3.2 储存结构设计采用哈夫曼树储存字符信息，哈夫曼树定义如下：typedef struct /定义哈夫曼树节点类型 int weight; int parent; int LChild; int RChild; char data; HTNode,HuffmanTreeM+1;typedef char *HuffmanCodeN+1; struct /定义存放当前节点哈夫曼编码的结构类型 char ch; int weight;arryQ; typedef struct Node /定义二叉树节点 int data; struct Node *LChild; struct Node *RChild;BiTNode,*BiTree;3.3 项目程序结构项目程序结构如图3.1所示。其中各个函数的功能说明如下：l int count()：统计字符权值。l void CrtHuffmanTree(HuffmanTree ht,int n)：建立哈夫曼树。l void CrtHuffmanCode(HuffmanTree ht,HuffmanCode hc,int n)：根据哈夫曼树求对应的哈夫曼编码。l main()：首先从数据文件读入字符，统计字符权值并建立哈夫曼树，再根据哈夫曼树求对应的哈夫曼编码。图 统计字符权值count()函数设计输入：输出：字符个数过程如下：从文件中读入一个字符当文件输入未结束时循环：读入一个字符c若c出现过，则对应的字符权值加一；若c未出现过，则对应的字符权值为1。3.3.2 建立哈夫曼树CrtHuffmanTree()函数设计输入：哈夫曼树ht，字符个数n输出：过程如下：将所有节点parent，lchild，rchild域置为0置i=n+1，当i！=2*n-1时循环：对于每个非叶子节点hti，从ht0到hti-1中选取两个权值最小的两个节点hts1和hts2，将它作为hti的左右节点，hti的权值为最小两个节点权值之和。3.3.3 哈夫曼编码CrtHuffmanCode()函数设计输入：哈夫曼树ht，哈夫曼编码hc，字符个数n输出：过程如下：置i=1，当i!=n时循环：令start=n，找其双亲节点htp，若当前节点是双亲节点的左孩子，则在cd数组中添加0，反之，添加1；再对其双亲节点重复上述操作直到无双亲节点为止。3.4 实验数据和实验结果分析实验数据文件如图3.2所示：图3.2实验结果如图3.3-3.4所示：通过直观观察，实验结果正确。图3.3统计字符权值图3.4 建立的哈夫曼树图3.5 实验结果3.5 实验源程序#include #include #include #include #define N 20#define M 2*N-1#define Q 150#define MAXINT 32767#define E 20FILE *fp1=fopen(hfC.txt,w+);FILE *fp=fopen(hf.txt,r+);typedef struct int weight; int parent; int LChild; int RChild; char data; HTNode,HuffmanTreeM+1;typedef char *HuffmanCodeN+1; struct char ch; int weight; arryQ; typedef struct Node int data; struct Node *LChild; struct Node *RChild; BiTNode,*BiTree;int count() char c; int i; int j; if(fp=NULL) printf(n不能打开此文件，按任意键退出！); exit(0); arry0.ch=fgetc(fp); c=arry0.ch; arry0.weight=1; j=1; while(c!=EOF) c=fgetc(fp); for(i=0;ij;i+) if(arryi.ch=c) arryi.weight+; break; if(i=j) arryj.ch=c; arryj.weight=1; j+; printf(各个字符对应的权值为:n); for(i=0;ij-1;i+) printf(%2c %2dn,arryi.ch,arryi.weight); fclose(fp); return (j-1);void select(HuffmanTree ht,int pos,int *s1,int *s2) int j,m1,m2; m1=m2=MAXINT; for(j=1;j=pos;j+) if(htj.weightm1&htj.parent=0) m2=m1; *s2=*s1; *s1=j; m1=htj.weight;else if(htj.weightm2&htj.parent=0) *s2=j; m2=htj.weight; void CrtHuffmanTree(HuffmanTree ht,int n) int s1,s2; int i,m; for(i=1;i=n;i+) hti.weight=arryi-1.weight; hti.parent=0; hti.LChild=0; hti.RChild=0; hti.data=arryi-1.ch; m=2*n-1; for(i=n+1;i=m;i+) hti.weight=0; hti.parent=0; hti.LChild=0; hti.RChild=0; for(i=n+1;i=m;i+) select(ht,i-1,&s1,&s2); hti.weight=hts1.weight+hts2.weight; hts1.parent=i; hts2.parent=i; hti.LChild=s1; hti.RChild=s2; printf(建立的哈夫曼树为:n); for(i=1;i=m;i+) printf(%d %d %d %d %d %cn,i,hti.weight,hti.parent,hti.LChild,hti.RChild,hti.data); void CrtHuffmanCode(HuffmanTree ht,HuffmanCode hc,int n) char *cd; int i; int c; int p; char ch; int start; cd=(char *)malloc(n+1)*sizeof(char); cdn=0; for(i=1;i=n;i+) start=n; c=i; p=hti.parent; while(p!=0) start-;if(htp.LChild=c)cdstart=0;else cdstart=1;c=p;p=htp.parent ; hci=(char *)malloc(n-start)*sizeof(char); strcpy(hci,&cdstart); printf(各个字符对应的编码为:n); for(i=1;i=n;i+) printf(%c,%sn,arryi-1.ch,hci); ch=fgetc(fp); while(ch!=EOF) for(i=1;i=n;i+) if(ch=arryi-1.ch) fputs(hci,fp1); break; ch=fgetc(fp); free(cd); fclose(fp); fclose(fp1);int main() HuffmanTree ht; HuffmanCode hc; int n; int choice; printf( 欢迎进入哈夫曼编码系统! nn); printf(1 统计字符出现的频度nn); printf(2 建立哈夫曼树nn); printf(3 对数据文件进行编码nn); printf(0 退出本系统nn); printf(请选择(0-3)nn); scanf(%d,&choice); switch(choice) case 1: n=count();break; case 2: n=count();CrtHuffmanTree(ht,n);break; case 3: n=count(); CrtHuffmanTree(ht,n); CrtHuffmanCode(ht,hc,n); if(fp=NULL) printf(不能打开此文件！n); exit(0); printf(编码完成n); break; case 0: break; return 0;第4章 项目3：两种算法求图的最小生成树4.1 实验项目【问题描述】用普里姆算法和克鲁斯卡尔算法分别求给定一个带权的无向连通图,选取一棵生成树,使树上所有边上权的总和为最小。【输入】图的顶点个数，边数，各点数据和无各向带权边数据。【输出】图的最小生成树。4.2 储存结构设计4.2.1克鲁斯卡尔算法图的存贮结构采用边集数组：struct edgeElem /定义边的结构类型 int fromvex;int endvex;int weight;typedef struct edgeElem edgesetMaxVertexNum; /定义边集数组4.2.2普里姆算法图的存贮结构采用邻接矩阵：typedef int adjmatrixMaxVertexNumMaxVertexNum;4.3 程序结构设计程序结构如图4.1所示，其中各函数说明如下：l void Creat_adjmatrix(vexlist GV,adjmatrix GA,int n,int e)：建立领接矩阵。l void Creat_edgeset(vexlist GV,edgeset GE,int n,int e)：建立边集数组。l void kruskal(edgeset GE,edgeset C,int n)：用克鲁斯卡尔算法求图的最小生成树。l void prim(adjmatrix GA,edgeset CT,int a,int n)：用普里姆算法求图的最小生成树。l void output_edgeset(edgeset GE,int e)：输出图的最小生成树。图 prim()算法设计输入：领接矩阵GE，边集CT，开始顶点a，顶点数n。输出： 过程如下：从指定顶点开始将它加入集合CT中,然后将集合内的顶点与集合外的顶点所构成的所有边中选取权值最小的一条边作为生成树的边,并将集合外的那个顶点加入到集合中,表示该顶点已连通。再用集合内的顶点与集合外的顶点构成的边中找最小的边,并将相应的顶点加入集合中,如此下去直到全部顶点都加入到集合中,即得最小生成树.4.4.2 kruskal()算法设计输入：边集GE，边集C，顶点数n。输出：过程如下：将图中边按其权值由小到大的次序顺序选取,若选边后不形成回路,则保留作为一条边,若形成回路则除去.依次选够(n-1)条边,即得最小生成树。4.4 实验数据和实验结果分析实验输入的图如图4.2：图4.2实验结果如图4.3-4.4所示：图4.3图4.5所得的最小生成树如图4.6所示：图4.6分析观察得实验结果正确。4.5 实验源程序#include#include#define MaxVertexNum 12#define MaxEdgeNum 20#define MaxValue 1000typedef int Vertextype;typedef int adjmatrixMaxVertexNumMaxVertexNum;typedef Vertextype vexlistMaxVertexNum;int visitedMaxVertexNum=0;struct edgeElemint fromvex;int endvex;int weight;typedef struct edgeElem edgesetMaxVertexNum;void Creat_adjmatrix(vexlist GV,adjmatrix GA,int n,int e)int i,j,k,w;printf(输入%d个顶点数据,n); for(i=0;in;i+) scanf(%d,&GVi); for(i=0;in;i+) for(j=0;jn;j+) if(i=j) GAij=0; else GAij=MaxValue; printf(输入%d条无向带权边,e); for(k=0;ke;k+) scanf(%d%d%d,&i,&j,&w); GAij=GAji=w; void Creat_edgeset(vexlist GV,edgeset GE,int n,int e)int i,j,k,w;printf(输入%d个顶点数据n,n); for(i=0;in;i+) scanf(%d,&GVi); printf(输入%d条无向带权边n,e); for(k=0;ke;k+) scanf(%d%d%d,&i,&j,&w); GEk.fromvex=i; GEk.endvex=j; GEk.weight=w;void output_edgeset(edgeset GE,int e)int k;for(k=0;ke;k+) printf(%d %d %d,GEk.fromvex,GEk.endvex,GEk.weight); printf(n);void prim(adjmatrix GA,edgeset CT,int a,int n)int i,j,t,k,w,min,m;struct edgeElem x;for(i=0;in;i+) if(ia) CTi-1.fromvex=a; CTi-1.endvex=i; CTi-1.weight=GAai; for(k=1;kn;k+) min=MaxValue; m=k-1; for(j=k-1;jn-1;j+) if(CTj.weightmin)min=CTj.weight;m=j; x=CTk-1;CTk-1=CTm;CTm=x; j=CTk-1.endvex; for(i=k;in-1;i+) t=CTi.endvex;w=GAjt; if(wCTi.weight) CTi.weight=w; CTi.fromvex=j; void kruskal(edgeset GE,edgeset C,int n) int i,j,k,d; int m1,m2; adjmatrix s; for(i=0;in;i+) for(j=0;jn;j+) if(i=j) sij=1;