数据结构实验报告记录文件压缩
————————————————————————————————作者：————————————————————————————————日期：
数据结构与程序设计实验
实验报告
课程名称数据结构与程序设计实验课程编号0906550 实验项目名称文件压缩
学号年级
姓名专业计算机科学与技术学生所在学院计算机学院指导教师杨静
实验室名称地点21B276
哈尔滨工程大学
实验报告四
实验课名称：数据结构与程序设计实验
实验名称：文件压缩
班级：学号：姓名：时间：2016.04.21
一、问题描述
哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。
统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树，
并将该哈夫曼树保存到文件HufTree.dat 中。
根据哈夫曼树（保存在HufTree.dat 中）对每个字符进行哈夫曼编码，并
将字符编码保存到HufCode.txt 文件中。
压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。
解压：将CodeFile.dat 文件利用哈夫曼树译码解压，恢复为源文件。
二、数据结构设计
由于哈夫曼树中没有度为1的结点，则一棵树有n个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中，而且对每个结点而言，即需知双亲结点的信息，又需知孩子结点的信息，由此可采用如下数据结构。
1.使用结构体数组统计词频，并存储:
typedef struct Node{
int weight; //叶子结点的权值
char c; //叶子结点
int num; //叶子结点的二进制码的长度
}LeafNode[N];
2.使用结构体数组存储哈夫曼树:
typedef struct{
unsigned int weight;//权值
unsigned int parent, LChild, RChild;
}HTNode,Huffman[M+1]; //huffman树
3.使用字符指针数组存储哈夫曼编码表：
typedef char *HuffmanCode[2*M]; //haffman编码表
三、算法设计
1.读取文件，获得字符串
void read_file(char const *file_name, char *ch){
FILE *in_file = Fopen(file_name, "r");
unsigned int flag = fread(ch, sizeof(char), N, in_file);
if(flag == 0){
printf("%s读取失败\n", file_name);
fflush(stdout);
}
printf("读入的字符串是: %s\n\n", ch);
Fclose(in_file);
int len = strlen(ch);
ch[len-1] = '\0';
}
2.统计叶子结点的字符和权值并存储
void CreateLeaf(char ch[], int *ch_len, LeafNode leaves, int *leaf_num){ int len,j,k;
int tag;
*leaf_num=0;//叶子节点个数
//统计字符出现个数,放入CW
for(len=0; ch[len]!='\0'; len++){//遍历字符串ch[]
tag=1;
for(j=0; j if(ch[j]==ch[len]){ tag=0; break; } } if(tag){// *leaf_num =0 不用 leaves[++*leaf_num].c=ch[len]; leaves[*leaf_num].weight=1; for(k=len+1; ch[k]!='\0'; k++)//在之后的字符串中累计权值 if(ch[len]==ch[k]) leaves[*leaf_num].weight++;//权值累加 } } *ch_len=len;//字符串长度 } 3．创建HuffmanTree，并存储 创建： void CreateHuffmanTree(Huffman ht,LeafNode w,int n){ int i,j; int s1,s2; //初始化哈夫曼树 for(i=1;i<=n;i++){ ht[i].weight =w[i].weight; ht[i].parent=0; ht[i].LChild=0; ht[i].RChild=0; } for(i=n+1;i<=2*n-1;i++){ ht[i].weight=0; ht[i].parent=0; ht[i].LChild=0; ht[i].RChild=0; } for(i=n+1;i<=2*n-1;i++){ for(j=1;j<=i-1;j++) if(!ht[j].parent) break; s1=j; //找到第一个双亲为零的结点 for(;j<=i-1;j++) if(!ht[j].parent) s1=ht[s1].weight>ht[j].weight?j:s1; ht[s1].parent=i; ht[i].LChild=s1; for(j=1;j<=i-1;j++) if(!ht[j].parent) break; s2=j; //找到第二个双亲为零的结点 for(;j<=i-1;j++) if(!ht[j].parent) s2=ht[s2].weight>ht[j].weight?j:s2; ht[s2].parent=i; ht[i].RChild=s2; ht[i].weight=ht[s1].weight+ht[s2].weight;//权值累加 } } 存储： void save_HufTree(Huffman ht, LeafNode le, int ln){ int i; FILE *HufTree = Fopen("HufTree.dat", "a"); CreateHuffmanTree(ht, le, ln); printf("\n哈夫曼树\n"); printf("编号权值parent LChild RChild\n"); //fputs("编号|权值|parent|LChild|RChild\n", HufTree); for(i=1; i<=2*ln-1; i++){ /*打印Huffman树的信息*/ printf("%d\t%d\t%d\t%d\t%d\n", i, (ht)[i].weight, (ht)[i].parent, (ht)[i].LChild, (ht)[i].RChild); fprintf(HufTree, "%d | %d | %d | %d | %d\n", i, (ht)[i].weight, (ht)[i].parent, (ht)[i].LChild, (ht)[i].RChild); } Fclose(HufTree); printf("哈弗曼树已保存至HufTree.dat\n"); } 4.读取哈夫曼树至新的结构体数组 void read_HufTree(Huffman ht){ //记得从1开始存储 int i = 1, j; FILE *HufTree = Fopen("HufTree.dat", "r"); while((fscanf(HufTree, "%d | %d | %d | %d | %d\n", &j, &((ht)[i].weight), &((ht)[i].parent), &((ht)[i].LChild), &((ht)[i].RChild))) == 5){ //printf("%d\t%d\t%d\t%d\n", (ht)[i].weight, (ht)[i].parent, (ht)[i].LChild, (ht)[i].RChild); i++; } Fclose(HufTree); printf("已从HufTree.dat读取哈弗曼树\n"); } 5.根据哈夫曼树生成每个叶子结点的编码 void CrtHuffmanNodeCode(Huffman ht, char ch[], HuffmanCode code_of_leaf, LeafNode weight, int m, int n){ int i,c,p,start; char *cd; cd=(char *)malloc(n*sizeof(char)); cd[n-1]='\0';//末尾置0 for(i=1;i<=n;i++){ start=n-1; //cd串每次从末尾开始 c=i; p=ht[i].parent;//p在n+1至2n-1 while(p){ //沿父亲方向遍历,直到为0 start--;//依次向前置值 if(ht[p].LChild==c)//与左子相同,置0 cd[start]='0'; else //否则置1 cd[start]='1'; c=p; p=ht[p].parent; } weight[i].num=n-start; //二进制码的长度(包含末尾0) code_of_leaf[i]=(char *)malloc((n-start)*sizeof(char)); strcpy(code_of_leaf[i],&cd[start]);//将二进制字符串拷贝到指针数组code_of_leaf中} free(cd);//释放cd内存 } 6.保存每个叶子结点的信息 void save_HufCode(Huffman ht, char *ch, HuffmanCode code_of_leaf, LeafNode leaves, int ch_len, int leaf_num){ int i; FILE *HufCode = Fopen("HufCode.txt", "a"); CrtHuffmanNodeCode(ht, ch, code_of_leaf, leaves, ch_len, leaf_num); //叶子结点的编码printf("\n每个叶子节点的前缀码\n"); //打印叶子结点的编码 for(i=1; i<=leaf_num; i++){ printf("%c: %s\n",leaves[i].c, code_of_leaf[i]); fprintf(HufCode, "%c: %s\n", leaves[i].c, code_of_leaf[i]); } Fclose(HufCode); printf("每个叶子节点的前缀码已保存至HufCode.txt\n"); } 7.读取每个叶子节点的信息到新的字符指针数组 void read_HufCode(HuffmanCode code_of_leaf){ int i=1; char c, tem[10]; FILE *HufCode = Fopen("HufCode.txt", "r"); while((fscanf(HufCode, "%c: %s\n", &c, tem)) == 2){ int len = strlen(tem); code_of_leaf[i] = (char *)malloc(len*sizeof(char)); strcpy(code_of_leaf[i], tem); //printf("%c: %s\n", c, code_of_leaf[i]); i++; } Fclose(HufCode); printf("已从HufCode.txt读取每个叶子节点信息\n"); } 8.生成所有字符的编码 void CrtHuffmanCode(char ch[], HuffmanCode code_of_leaf, HuffmanCode code_of_ch, LeafNode leaves, int leaf_num, int ch_len){ int i,k; for(i=0;i for(k=1;k<=leaf_num;k++) /*从weight[k].c中查找与ch[i]相等的下标K*/ if(ch[i]==leaves[k].c) break; code_of_ch[i]=(char *)malloc((leaves[k].num)*sizeof(char)); strcpy(code_of_ch[i],code_of_leaf[k]); //拷贝二进制编码 } } 9.保存字符串的编码信息(压缩) FILE *Fopen(char const *filename, char const *mode){ FILE *idlist; idlist = fopen(filename, mode); if(idlist == NULL){ perror(filename); exit(EXIT_FAILURE); }else{ return idlist; } } 10.解码并保存到str2.txt void TrsHuffmanTree(Huffman ht, LeafNode w, HuffmanCode hc, int n, int m){ int i=0,j,p; FILE *str2 = Fopen("str2.txt", "a"); printf("\n经解压得原文件中的字符串: "); while(i p=2*n-1;//从父亲节点向下遍历直到叶子节点 for(j=0;hc[i][j]!='\0';j++){ if(hc[i][j]=='0') p=ht[p].LChild; else p=ht[p].RChild; } printf("%c",w[p].c); /*打印原信息*/ fputc(w[p].c, str2); i++; } Fclose(str2); printf("\n已将解压得到的字符串保存至str2.txt\n"); } 11.释放huffman编码内存 void FreeHuffmanCode(HuffmanCode h1, HuffmanCode h2, HuffmanCode hc, int leaf_num, int ch_len){ int i; for(i=1;i<=leaf_num;i++){//释放叶子结点的编码 free(h1[i]); free(h2[i]); } for(i=0;i free(hc[i]); } 四、运行测试与分析及运行界面 1.文件str1.txt内容： 2.运行程序，读取文件 3.统计叶子节点的权值 4.根据权值生成哈夫曼树，保存至HufTree.dat，并用新的结构体数组读取哈夫曼树 5.HufTree.dat内容 6.根据哈夫曼树生成叶子节点的前缀码，保存至HufCode.txt，之后用新的结构体数组读取HufCode.txt 7.HufCode.txt内容 8.根据前缀码生成哈夫曼编码，保存至CodeFile.dat 9.CodeFile.dat内容 10．根据CodeFile.dat解压，获得原字符串，并保存至str2.txt 11.str2.txt内容 五、实验收获与思考 通过使用哈夫曼树实现文件压缩，使我充分理解哈夫曼树的构造方法以及实际应用，巩固了课堂知识，同时认识到自己的不足。在编程中发现问题，通过查询求助解决问题，使我不断地我加深数据结构的学习。 六、附录(原程序) #include #include #include #define N 100 #define M 2*N-1 typedef char *HuffmanCode[2*M];//haffman编码 typedef struct{ unsigned int weight;//权值 unsigned int parent, LChild, RChild; }HTNode,Huffman[M+1];//huffman树 typedef struct Node{ int weight; //叶子结点的权值 char c; //叶子结点 int num; //叶子结点的二进制码的长度 }LeafNode[N]; // 产生叶子结点的字符和权值 void CreateLeaf(char ch[], int *ch_len, LeafNode leaves, int *leaf_num){ int len,j,k; int tag; *leaf_num=0;//叶子节点个数 //统计字符出现个数,放入CW for(len=0; ch[len]!='\0'; len++){//遍历字符串ch[] tag=1; for(j=0; j if(ch[j]==ch[len]){ tag=0; break; } } if(tag){// *leaf_num =0 不用 leaves[++*leaf_num].c=ch[len]; leaves[*leaf_num].weight=1; for(k=len+1; ch[k]!='\0'; k++)//在之后的字符串中累计权值 if(ch[len]==ch[k]) leaves[*leaf_num].weight++;//权值累加 } } *ch_len=len;//字符串长度 } // 创建HuffmanTree void CreateHuffmanTree(Huffman ht,LeafNode w,int n){ int i,j; int s1,s2; //初始化哈夫曼树 for(i=1;i<=n;i++){ ht[i].weight =w[i].weight; ht[i].parent=0; ht[i].LChild=0; ht[i].RChild=0; } for(i=n+1;i<=2*n-1;i++){ ht[i].weight=0; ht[i].parent=0; ht[i].LChild=0; ht[i].RChild=0; } for(i=n+1;i<=2*n-1;i++){ for(j=1;j<=i-1;j++) if(!ht[j].parent) break; s1=j; //找到第一个双亲为零的结点 for(;j<=i-1;j++) if(!ht[j].parent) s1=ht[s1].weight>ht[j].weight?j:s1; ht[s1].parent=i; ht[i].LChild=s1; for(j=1;j<=i-1;j++) if(!ht[j].parent) break; s2=j; //找到第二个双亲为零的结点 for(;j<=i-1;j++) if(!ht[j].parent) s2=ht[s2].weight>ht[j].weight?j:s2; ht[s2].parent=i; ht[i].RChild=s2; ht[i].weight=ht[s1].weight+ht[s2].weight;//权值累加 } } // 生成每个叶子结点的编码 void CrtHuffmanNodeCode(Huffman ht, char ch[], HuffmanCode code_of_leaf, LeafNode weight, int m, int n){ int i,c,p,start; char *cd; cd=(char *)malloc(n*sizeof(char)); cd[n-1]='\0';//末尾置0 for(i=1;i<=n;i++){ start=n-1; //cd串每次从末尾开始 c=i; p=ht[i].parent;//p在n+1至2n-1 while(p){ //沿父亲方向遍历,直到为0 start--;//依次向前置值 if(ht[p].LChild==c)//与左子相同,置0 cd[start]='0'; else //否则置1 cd[start]='1'; c=p; p=ht[p].parent; } weight[i].num=n-start; //二进制码的长度(包含末尾0) code_of_leaf[i]=(char *)malloc((n-start)*sizeof(char)); strcpy(code_of_leaf[i],&cd[start]);//将二进制字符串拷贝到指针数组code_of_leaf中} free(cd);//释放cd内存 } // 生成所有字符的编码 void CrtHuffmanCode(char ch[], HuffmanCode code_of_leaf, HuffmanCode code_of_ch, LeafNode leaves, int leaf_num, int ch_len){ int i,k; for(i=0;i for(k=1;k<=leaf_num;k++) /*从weight[k].c中查找与ch[i]相等的下标K*/ if(ch[i]==leaves[k].c) break; code_of_ch[i]=(char *)malloc((leaves[k].num)*sizeof(char)); strcpy(code_of_ch[i],code_of_leaf[k]); //拷贝二进制编码 } } FILE *Fopen(char const *filename, char const *mode){ FILE *idlist; idlist = fopen(filename, mode); if(idlist == NULL){ perror(filename); exit(EXIT_FAILURE); }else{ return idlist; } } void Fclose(FILE *file){ if(fclose(file) != 0){ perror("fclose"); exit(EXIT_FAILURE); } file = NULL; } void read_file(char const *file_name, char *ch){ FILE *in_file = Fopen(file_name, "r"); unsigned int flag = fread(ch, sizeof(char), N, in_file); if(flag == 0){ printf("%s读取失败\n", file_name); fflush(stdout); } printf("读入的字符串是: %s\n\n", ch); Fclose(in_file); int len = strlen(ch); ch[len-1] = '\0'; } void save_HufTree(Huffman ht, LeafNode le, int ln){ int i; FILE *HufTree = Fopen("HufTree.dat", "a"); CreateHuffmanTree(ht, le, ln); printf("\n哈夫曼树\n"); printf("编号权值parent LChild RChild\n"); //fputs("编号|权值|parent|LChild|RChild\n", HufTree); for(i=1; i<=2*ln-1; i++){ /*打印Huffman树的信息*/ printf("%d\t%d\t%d\t%d\t%d\n", i, (ht)[i].weight, (ht)[i].parent, (ht)[i].LChild, (ht)[i].RChild); fprintf(HufTree, "%d | %d | %d | %d | %d\n", i, (ht)[i].weight, (ht)[i].parent, (ht)[i].LChild, (ht)[i].RChild); } Fclose(HufTree); printf("哈弗曼树已保存至HufTree.dat\n"); } void read_HufTree(Huffman ht){ //记得从1开始存储 int i = 1, j; FILE *HufTree = Fopen("HufTree.dat", "r"); while((fscanf(HufTree, "%d | %d | %d | %d | %d\n", &j, &((ht)[i].weight), &((ht)[i].parent), &((ht)[i].LChild), &((ht)[i].RChild))) == 5){ //printf("%d\t%d\t%d\t%d\n", (ht)[i].weight, (ht)[i].parent, (ht)[i].LChild, (ht)[i].RChild); i++; } Fclose(HufTree); printf("已从HufTree.dat读取哈弗曼树\n"); } void save_HufCode(Huffman ht, char *ch, HuffmanCode code_of_leaf, LeafNode leaves, int ch_len, int leaf_num){ int i; FILE *HufCode = Fopen("HufCode.txt", "a"); CrtHuffmanNodeCode(ht, ch, code_of_leaf, leaves, ch_len, leaf_num); //叶子结点的编码printf("\n每个叶子节点的前缀码\n"); //打印叶子结点的编码 for(i=1; i<=leaf_num; i++){ printf("%c: %s\n",leaves[i].c, code_of_leaf[i]); fprintf(HufCode, "%c: %s\n", leaves[i].c, code_of_leaf[i]); } Fclose(HufCode); printf("每个叶子节点的前缀码已保存至HufCode.txt\n"); } void read_HufCode(HuffmanCode code_of_leaf){ int i=1; char c, tem[10]; FILE *HufCode = Fopen("HufCode.txt", "r"); while((fscanf(HufCode, "%c: %s\n", &c, tem)) == 2){ int len = strlen(tem); code_of_leaf[i] = (char *)malloc(len*sizeof(char)); strcpy(code_of_leaf[i], tem); //printf("%c: %s\n", c, code_of_leaf[i]); i++; } Fclose(HufCode); printf("已从HufCode.txt读取每个叶子节点信息\n"); } void save_CodeFile(char *ch, HuffmanCode code_of_leaf, HuffmanCode code_of_ch, LeafNode leaves, int leaf_num, int ch_len){ FILE *CodeFile = Fopen("CodeFile.dat", "a"); CrtHuffmanCode(ch, code_of_leaf, code_of_ch, leaves, leaf_num, ch_len); //字符串的编码printf("\n字符串的编码: "); //打印字符串的编码 int i; for(i=0; i printf("%s",code_of_ch[i]); fputs(code_of_ch[i], CodeFile); } Fclose(CodeFile); printf("\n字符串的哈弗曼编码已保存至CodeFile.dat\n"); } //解码并保存到str2.txt void TrsHuffmanTree(Huffman ht, LeafNode w, HuffmanCode hc, int n, int m){ int i=0,j,p; FILE *str2 = Fopen("str2.txt", "a"); printf("\n经解压得原文件中的字符串: "); while(i p=2*n-1;//从父亲节点向下遍历直到叶子节点 for(j=0;hc[i][j]!='\0';j++){ if(hc[i][j]=='0') p=ht[p].LChild; else p=ht[p].RChild; } printf("%c",w[p].c); /*打印原信息*/ fputc(w[p].c, str2); i++; } Fclose(str2); printf("\n已将解压得到的字符串保存至str2.txt\n"); } //释放huffman编码内存 void FreeHuffmanCode(HuffmanCode h1, HuffmanCode h2, HuffmanCode hc, int leaf_num, int ch_len){ int i; for(i=1;i<=leaf_num;i++){//释放叶子结点的编码 free(h1[i]); free(h2[i]); } for(i=0;i free(hc[i]); } int main(){ printf("读取文件str1.txt中...\n"); char ch[N]; read_file("str1.txt", ch); int ch_len = 0; // ch的长度 LeafNode leaves; //存放叶子结点的信息 int leaf_num=0; //leaf_num为叶子结点的个数 CreateLeaf(ch, &ch_len, leaves, &leaf_num); //产生叶子结点信息，ch_len为字符串ch[]的长度*/ printf("叶子节点的字符与权值\n"); int i; for(i=1; i<=leaf_num; i++){ /*输出叶子结点的字符与权值*/ printf("%c: %d\n",leaves[i].c, leaves[i].weight); } Huffman htree; // 哈夫曼树 save_HufTree(htree, leaves, leaf_num);// 生成并保存HufTree Huffman htree2; read_HufTree(htree2);// 读取HufTree 一，实验题目 实验十一：图实验 采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。 二，问题分析 本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1，数据的输入形式和输入值的范围：输入的图的结点均为整型。 2，结果的输出形式：输出的是两结点间是否存在路径的情况。 3，测试数据：输入的图的结点个数为：4 输入的图的边得个数为：3 边的信息为：1 2，2 3，3 1 三，概要设计 （1）为了实现上述程序的功能，需要： A，用邻接表的方式构建图 B，深度优先遍历该图的结点 C，判断任意两结点间是否存在路径 （2）本程序包含6个函数： a，主函数main（） b，用邻接表建立图函数create_adjlistgraph() c，深度优先搜索遍历函数dfs() d，初始化遍历数组并判断有无通路函数dfs_trave() e，输出邻接表函数print() f，释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示： 四，详细设计 （1）邻接表中的结点类型定义： typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; （2）邻接表中头结点的类型定义： typedef struct{ char vexdata; arcnode *firstarc; }adjlist; （3）邻接表类型定义： typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; （4）深度优先搜索遍历函数伪代码： int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } （5）初始化遍历数组并判断有无通路函数伪代码： void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五，源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时） 实验一顺序表问题 【实验报告】 《数据结构与算法》实验报告一 学院：计算机与信息学院班级： 学号：姓名： 日期：程序名： 一、上机实验的问题和要求： 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 1.从键盘输入10个整数，产生顺序表，并输出结点值。 调试数据：9 8 7 6 5 4 3 2 1 2.从键盘输入1个整数，在顺序表中查找该结点。若找到，输出结点的位置；若找不到， 则显示“找不到”。 调试数据：第一次输入11，第二次输入3 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插 入在对应位置上，输出顺序表所有结点值，观察输出结果。 调试数据：第一次insert "11" after "6" ，第二次insert "86" at "2" 4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。 调试数据：第一次delete the number at "2" ，第二次delete value "9" 注意：顺序表输出表现形式如下（实验报告上为截图）： 顺序表： 第一题 Initially Seq: head -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null 第二题 找不到 6 第三题 insert "11" after "6": head -> 9 -> 8 -> 7 -> 6 -> 11 -> 5 -> 4 -> 3 -> 2 -> 1 -> null insert"86"at"2":head -> 9 -> 8 -> 86 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null 第四题 delete the number at "2":head -> 9 -> 8 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 ->null delete value "9": head -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null 图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template #include 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"< 云南大学 数据结构实验报告 第三次实验 学号： 姓名： 一、实验目的 1、复习结构体、指针； 2、掌握链表的创建、遍历等操作； 3、了解函数指针。 二、实验内容 1、（必做题）每个学生的成绩信息包括：学号、语文、数学、英语、总分、加权平均分；采用链表存储若干学生的成绩信息；输入学生的学号、语文、数学、英语成绩；计算学生的总分和加权平均分（语文占30%，数学占50%，英语占20%）；输出学生的成绩信息。 三、算法描述 （采用自然语言描述） 首先创建链表存储n个学生的成绩信息，再通过键盘输入学生的信息，创建指针p所指结点存储学生的成绩信息，从键盘读入学生人数，求出学生的总分和加权平均分，输出结果。 四、详细设计 （画出程序流程图） 五、程序代码 （给出必要注释） #include 实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列，要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include 求A QB #include 2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList [内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template 学期：2010-2011学年第一学期指导教师：杨华莉成绩： 实验一顺序表的基本操作 一、实验目的 1．掌握使用VC++6.0调试程序的基本方法； 2．掌握线性表的顺序存储结构的类型定义； 3．掌握顺序表的基本操作的实现,如：插入、删除、遍历、查找、排序、修改、合并等； 4．掌握顺序表的应用。 二、实验要求 1．认真阅读和掌握本实验的示例程序。 2．上机运行示例程序，打印出程序的运行结果，并作必要的说明。 3．对示例程序，按照对线性表的操作需要，在程序中至少添加2个顺序表的相关操作。如： i.查找并显示分数在区间[a，b）的学生信息； ii.查找并显示最高分或最低分学生信息； iii.统计不及格或及格人数及所占比例； iv.将信息表按学号、姓名或分数升序或降序排列； v.按学号顺序进行数据元素的插入； vi.删除指定学号或姓名的学生信息； vii.修改某个学生的信息； viii.其它。 4．重新改写主函数（要求必需调用自己添加的操作），打印出文件清单（自己添加的函数、修改后的主函数和运行结果）。 5．对修改后的程序，分析每一个算法（函数）的时间复杂度。 6．根据上述要求撰写实验报告，并简要给出算法设计小结和心得。 三、实验环境 1．台式计算机每人一台； 2．软件：Visual C++6.0 四、实验内容和实验结果 一．示例程序运行结果及说明 二．自己添加的新函数(至少2个)，要求加必要的注释。 SqList Delete_SqList(SqList &L)//删除学生信息 { Elemtype x; int i=0; int choice=DMenu(); char name[25]; int num,k; if(!L.length) { printf("表为空，无法删除!"); exit(0); } switch(choice) { case 1: //按姓名删除 printf("\n请输入要删除的学生的姓名\n"); scanf("%s",&name); k=strcmp(name,L.data[i].name);//比较姓名 if(k==0) { x=L.data[i-1]; for(int m=L.length-1;m>=i-1;--m) L.data[i-1]=L.data[i]; --L.length; break; } case 2: //按学号删除 printf("\n请输入要删除学生的学号\n"); scanf("%d",&num); if(num==L.data[i].num) { for(int m=L.length-1;m>=i-1;--m) L.data[i-1]=L.data[i]; --L.length; break; } case 3:break; } return L; 云南大学软件学院数据结构实验报告 （本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度： A □ B □ C □ 学期：2010秋季学期 任课教师: 实验题目: 查找算法设计与实现 姓名: 王辉 学号: 20091120154 电子邮件: 完成提交时间： 2010 年 12 月 27 日 云南大学软件学院2010学年秋季学期 《数据结构实验》成绩考核表 学号：姓名：本人承担角色： 综合得分：（满分100分） 指导教师：年月日（注：此表在难度为C时使用，每个成员一份。） （下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%) 1 哈希表查找。根据全年级学生的姓名，构造一个哈希表，选择适当的哈希函数和解决冲突的方法，设计并实现插入、删除和查找算法。 熟悉各种查找算法的思想。 2、掌握查找的实现过程。 3、学会在不同情况下运用不同结构和算法求解问题。 4 把每个学生的信息放在结构体中： typedef struct //记录 { NA name; NA tel; NA add; }Record; 5 void getin(Record* a)函数依次输入学生信息 6 人名折叠处理，先将用户名进行折叠处理折叠处理后的数，用除留余数法构造哈希函数，并返回模值。并采用二次探测再散列法解决冲突。 7姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。将初始班级的通讯录信息存入文件。 二、【实验设计(Design)】(20%) （本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系） 1抽象数据类型的功能规格说明和结构体： #include 南京工程学院实验报告 操作的函数程序清单，分别用顺序表和链表结构完成，并在首页上表明团队名称、成员及个人的工作（函数），未来的成绩评定时将包含这一部分的团队成绩及个人的工作成绩。 一、实验目的 1.熟悉上机环境，进一步掌握语言的结构特点。 2.掌握线性表的顺序存储结构的定义及实现。 3.掌握线性表的链式存储结构——单链表的定义及实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、程序主要语句及作用（main函数程序清单） 程序1的主要代码(附简要注释) #include 附录A 实验报告 课程：数据结构（c语言）实验名称：图的建立、基本操作以及遍历系别：数字媒体技术实验日期： 12月13号 12月20号 专业班级：媒体161 组别：无 姓名：学号： 实验报告内容 验证性实验 一、预习准备： 实验目的： 1、熟练掌握图的结构特性，熟悉图的各种存储结构的特点及适用范围； 2、熟练掌握几种常见图的遍历方法及遍历算法； 实验环境：Widows操作系统、VC6.0 实验原理： 1.定义： 基本定义和术语 图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)，其中：V(G)是顶点(V ertex)的非空有限集E(G)是边(Edge)的有限集合，边是顶点的无序对(即：无方向的，（v0,v2）)或有序对（即：有方向的, 无向图中顶点V i的度TD(V i)是邻接矩阵A中第i行元素之和有向图中， 顶点V i的出度是A中第i行元素之和 顶点V i的入度是A中第i列元素之和 邻接表 实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧） 特点: 无向图中顶点Vi的度为第i个单链表中的结点数有向图中 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表。 图的遍历 从图中某个顶点出发访遍图中其余顶点，并且使图中的每个顶点仅被访问一次过程.。遍历图的过程实质上是通过边或弧对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。图的遍历有两条路径：深度优先搜索和广度优先搜索。当用邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需要时间为O（n2），n为图中顶点数；而当以邻接表作图的存储结构时，找邻接点所需时间为O（e），e 为无向图中边的数或有向图中弧的数。 实验内容和要求： 选用任一种图的存储结构，建立如下图所示的带权有向图： 要求：1、建立边的条数为零的图； 实验目的 （1）学会用先序创建一棵二叉树。 （2）学会采用递归算法对二叉树进行先序、中序、后序遍历。 （3）学会打印输出二叉树的遍历结果。 实验内容 【问题描述】建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。 【基本要求】 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。 【测试数据】 ABCффDEфGффFффф(其中ф表示空格字符) 则输出结果为先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA 【选作内容】 采用非递归算法实现二叉树遍历。 实验步骤 （一）需求分析 1、在这个过程中，接受遍历的二叉树是从键盘接受输入（先序），以二叉链表作为存储结构，建立的二叉树。因此，首先要创建一棵二叉树，而这棵二叉树是先序二叉树。本演示程序中，集合的元素设定为大写字母ABCDEFG，输出的先序，中序，后序遍历分别为ABCDEGF,CBEGDFA,CGBFDBA。二叉树可以表示为： 接受的输入数据在进行递归的先序，中序，后序遍历后，分别将结果打印出来。 2、在程序运行的过程中可以看到，以计算机提示用户执行的方式进行下去，即在计算机终端上提示“输入二叉树的先序序列”后，由用户在键盘上输入ABC##DE#G##F###，之后相应的选择遍历及遍历结果显示出来。 3、程序执行的命令包括：首先是二叉树的先序序列被创建输入，其次是对输入进去的先序序列有次序的进行先序，中序，后序遍历。最后是打印出二叉树的遍历结果。 4、测试数据 （1）在键盘上输入的先序序列ABC##DE#G##F### （2）先序遍历结果ABCDEGF 数据结构教程 上机实验报告 实验七、图算法上机实现 一、实验目的： 1.了解熟知图的定义和图的基本术语，掌握图的几种存储结构。 2.掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接矩阵和邻接表的类型定义。 3.掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方法及其基本思想。 二、实验内容： 1.建立无向图的邻接矩阵 2.图的xx优先搜索 3.图的xx优先搜索 三、实验步骤及结果： 1.建立无向图的邻接矩阵： 1)源代码： #include "stdio.h" #include "stdlib.h" #define MAXSIZE 30 typedefstruct{charvertex[MAXSIZE];//顶点为字符型且顶点表的长度小于MAXSIZE intedges[MAXSIZE][MAXSIZE];//边为整形且edges为邻近矩阵 }MGraph;//MGraph为采用邻近矩阵存储的图类型 voidCreatMGraph(MGraph *g,inte,int n) {//建立无向图的邻近矩阵g->egdes，n为顶点个数，e为边数inti,j,k; printf("Input data of vertexs(0~n-1): \n"); for(i=0;i 2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨 实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。 三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 精品文档数据结构 实 验 报 告 目的要求 １．掌握图的存储思想及其存储实现。 ２．掌握图的深度、广度优先遍历算法思想及其程序实现。 ３．掌握图的常见应用算法的思想及其程序实现。 实验内容 １．键盘输入数据，建立一个有向图的邻接表。 ２．输出该邻接表。 3．在有向图的邻接表的基础上计算各顶点的度，并输出。 4．以有向图的邻接表为基础实现输出它的拓扑排序序列。 5．采用邻接表存储实现无向图的深度优先递归遍历。 6．采用邻接表存储实现无向图的广度优先遍历。 7．在主函数中设计一个简单的菜单，分别调试上述算法。 源程序： 主程序的头文件：队列 #include 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template数据结构实验十一：图实验
数据结构实验报告格式
数据结构实验一顺序表问题及实验报告模板 - Copy
数据结构实验报告图实验
数据结构实验报告
数据结构实验报告图实验
数据结构实验报告全集
数据结构实验报告[3]
数据结构实验
数据结构实验报告模板
数据结构实验报告模板(验证型)
数据结构实验报告七查找、
数据结构实验报告
数据结构实验报告(图)
数据结构实验报告.
数据结构图实验报告
数据结构实验报告及心得体会
数据结构实验—图实验报告
数据结构实验报告图实验
相关主题
文本预览