数据结构实验学期总结.docx

《数据结构实验学期总结.docx》由会员分享，可在线阅读，更多相关《数据结构实验学期总结.docx（18页珍藏版）》请在三一办公上搜索。

1、数据结构实验学期总结数据结构实验学期总结 摘要： 本学期我完成的主要实验任务有：裴波那锲序列、约瑟夫环、表达式求值、赫夫曼编码 文档内容：本学期以来，我所完成的所有实验及其总结，分别包括实验名称、实验目的及要求、实验主要内容、实验结果结论、实验分析，还有我对该课程学习总结和建议。 关键字： 数据结构 实验 总结 数组 链表 栈 二叉树 实验一 实验名称：裴波那锲序列 实验目的及要求： 1. 熟悉开发工具的编程环境。 2. 体会算法和程序的不同。 3. 学习用不同算法实现同一程序功能，并能熟练编程实现。 4. 学习分析算法。对比不同算法实现的效率有何不同，所占空间有何不同。对比不同算法的优点和缺

2、点 实验主要内容： 概要设计和存储结构 K阶裴波那契序列的第m项值假设为sum，则： sum(m) =sum(m-1)+sum(m-2)+sum(m-k) =sum(m-1)+sum(m-2)+sum(m-k)+sum(m-k-1)-sum(m-k-1) =sum(m-1)+sum(m-2)+sum(m-k)+sum(m-k-1)-sum(m-k-1) =2*sum(m-1)-sum(m-k-1) 所以最后return返回的是2*f(m-1,k)-f(m-k-1,k)，如此便实现了裴第 1 页 共 18 页 波那契序列第m项的计算。 下面程序段中语句的时间复杂度为：O(sum)=2(m-k)

3、(mk) 程序中未曾使用线性表或链表结构 主要算法 int f(int m,int k) if(mnum=n; /可以替换下一句head-data=rand%100+1;密码随机产生 scanf(%d,&head-data); return head; /creat /*实现出列功能*/ void count(struct huan* head,int n) struct huan *p2=head,*p1; for(;p2-next!=head;p2=p2-next); p1=p2-next; int code; printf(n请输入起始密码:n); scanf(%d,&code); in

4、t pas=code%n; printf(出列次序:n位置 密码n); while(n1) if(pas=0) pas=n; for(int i=1;inext,i+); p2-next=p1-next; printf( %dt%dn,p1-num,p1-data); code=p1-data; free(p1); p1=p2-next; n-; pas=code%n; 第 4 页 共 18 页 printf( %dt%dn,p1-num,p1-data); free(p1); /count 实验结果和结论 实验要求完成的功能已经全部完成了，但是对于手动输入密码和随机产生密码这两种功能没能够通

5、过程序选择来完成 实验分析： 可以看出这一题是考查单链表的应用，而且这一题中的循环单链表是不需要“头结点”的，要注意空表和非空表的界限。程序运行后要求用户指定初始报数上界值，人数及各人的密码。可先设n30。 实验三 第 5 页 共 18 页 实验名称：表达式求值 实验目的及要求： 通过上机实践掌握队列和栈的顺序存储结构和链式存储结构，以便我们能在相应的应用问题中正确选用它们；掌握栈和队列的特点，即先进后出与先进先出的原则；掌握栈和队列的基本运算，如入栈和出栈、入队与出队等运算在顺序存储结构和链式存储结构上的实现。 以字符序列形式从终端输入语法正确的、不含变量的整数表达式。利用课本3.2.5节中

6、给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照课本上的例子演示在求值过程中运算符栈、运算数栈、输入字符和主要操作的变化过程。 实验主要内容： 概要设计和存储结构 构建了两个栈OPTR, OPNDtypedef struct ElemType *base; ElemType *top; int stacksize; Stack;/定义栈类型 int IfEmptyStack(Stack S);/判断栈是否为空 void InitStack(Stack &S);/构建一个栈 void EmptyStack(Stack &S);/栈空时，则返回值 void Push(Stack &S

7、, ElemType e); /插入元素e为新的栈顶元素 void Pop(Stack &S, ElemType &e); /若栈不空，则删除s的栈顶元素，用e返回其值 void ShowStack(Stack S); /输出计算结果 int In(char ch); /判断字符ch是不是运算符 第 6 页 共 18 页 char Precede(char a,char b);/判定运算符栈顶运算符a与读入b之间优先权 int Operate(int a, char f, int b); /进行二元运算的函数 void EvaluateExpression;/算术表达式求值的算符优先算法 ma

8、in函数调用EvaluateExpression，EvaluateExpression嵌套调用以上各函数 主要算法 int IfEmptyStack(Stack S) /判断栈是否为空，是则返回1，否则返回0 if(S.base=S.top) return 1; return 0; void InitStack(Stack &S) /构建一个空栈s S.base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return ; void EmptySt

9、ack(Stack &S) /若栈为空 ，则返回值 S.top=S.base; 第 7 页 return ; void Push(Stack &S, ElemType e) /插入元素e为新的栈顶元素 if(S.top-S.base=S.stacksize) /栈满，追加存储空间 S.base=(ElemType*)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(ElemType); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; 共 18 页 retur

10、n ; /Push void Pop(Stack &S, ElemType &e) /若栈不空，则删除s的栈顶元素，用e返回其值 if(S.top=S.base) return ; e=*-S.top; return ; ElemType GetTop(Stack &S) /栈不空，返回栈顶元素 if(S.top=S.base) return 0; return *(S.top-1); void ShowStack(Stack S) /输出计算结果 ElemType *p=S.base; while(p!=S.top) printf(%d,*p+); return; 第 8 页int In(c

11、har ch) /判断字符ch是不是运算符 int res; switch(ch) case +: case -: case *: case /: case (: case ): case =: res=1;break; default: res=0;break; return res; char Precede(char a, char b) /判定运算符的栈顶运算符a与读入b之间优先权 int i,j; int OP77= 1,1,-1,-1,-1,1,1,1,1,-1,-1,-1,1,1,1,1,1,1,-1,1,1,1,1,1,1,-1,1,1, -1,-1,-1,-1,-1,0,2,

12、1共 18 页 ,1,1,1,2,1,1, -1,-1,-1,-1,-1,2,0 ; switch(a) case +:i=0;break; case -:i=1;break; case *:i=2;break; case /:i=3;break; case (:i=4;break; case ):i=5;break; case =:i=6;break; switch(b) case +:j=0;break; case -:j=1;break; case *:j=2;break; case /:j=3;break; case (:j=4;break; case ):j=5;break; cas

13、e =:j=6;break; if(OPij=1) return ; else if(OPij=-1) return =0&c=0&c=9); di=0; num=atoi(d); Push(OPND, num); /if else if(In(c) switch(Precede(GetTop(OPTR), c) case : Pop(OPTR, f);Pop(OPND, tmpb);Pop(OPND, tmpa); Push(OPND, Operate(tmpa, f, tmpb); break; /switch /else if /while c=getchar;/接收最后输入的一个回车符

14、，否则在主函数中只能输入一次 printf(计算结果为: ); ShowStack(OPND); printf(n); /EvaluateExpression 所有的运算数都定义为整型，运算符定义为字符型 共 18 页 实验结果和结论 程序在表达式输入错误即括号不相匹配时能够报错了,并结束程序。但是在连续输入+，-，*，/时，程序不能够报错还是能够给出计算结果 实验分析： 显然要先考虑所用到的栈存储结构，以及栈的初始化、出栈、入栈、取栈顶元素等一系列的栈的基本操作的实现，以便生成运算符栈和操作数栈，及实现算符优先法的算法。注意，在读入表达式的字符序列的同时完成运算符和操作数的识别处理，以及相应

15、的运算。在识别操作数的同时，别忘记将字符序列形式转换成整数形式！还要在程序的适当位置输出运算符栈、操作数栈、输入字符和主要操作的内容。有可能的话，还要考虑用户输入表达式时可能会犯的简单的语法错误，给予适当的提示，象括号不匹配、错误的运算符之类。 第 11 页 共 18 页 实验四 实验名称：赫夫曼编码 实验目的及要求： 通过上机实践，帮助学生进一步掌握指针变量和动态变量的含义，掌握二叉树的结构特性，以及各种存储结构的特点及适用范围，掌握用指针类型描述、访问和处理二叉树的运算 一个完整的系统应具有以下功能： 初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存储于文件h

16、fmtree中。 编码。利用建好的哈夫曼树，对要传输的文件tobefile中的正文进行编码，然后将结果存入另一个文件codefile中。 译码。利用建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件文件textfile中。 印代码文件。将文件codefile以紧凑格式显示在终端屏幕上，每行50个代码，同时将此字符形式的编码文件写入文件codeprin中。 印哈夫曼树。将已在内存中的哈夫曼树以直观的形式显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。 实验主要内容： 概要设计和存储结构 赫夫曼树中没度1的结点，则n个叶子结点的赫夫曼树共有2n-1个结点，可以

17、存储在一个大小为2n-1的一维数组中。为求编码需从叶子结点出发走一条从叶子到根的路径；而为译码需从根出发走一条从根到叶子的路径。 故建立存储如下： typedef struct unsigned int weight; unsigned int parent,lchild,rchild; 第 12 页 共 18 页 HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树 */ typedef char *HuffmanCode; /* 动态分配数组存储赫夫曼编码表 */ 向量HT的前n个分量表示叶子结点，最后一个分量表示根结点。各字符的编码长度不等，所以按实际长度动态分配空间

18、。 程序中总共建立了四个模块： int min(HuffmanTree t,int i) void select(HuffmanTree t,int i,int *s1,int *s2) void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) int main select函数调用min函数选择两个权值最小的结点 HuffmanCoding函数调用select函数将权值小的两个结点连接起来，算出编码 Main函数调用HuffmanCoding函数实现整个程序的功能 主要算法 typedef struct unsigned

19、 int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树 */ typedef char *HuffmanCode; /* 动态分配数组存储赫夫曼编码表 */ int min(HuffmanTree t,int i) /* 函数void select调用 */ int j,flag; unsigned int k=UINT_MAX; /* 取k为不小于可能的值 */ for(j=1;j=i;j+) 第 13 页 共 18 页 if(tj.weight*s2) j=*s1; *s1=*

20、s2; *s2=j; void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) /* w存放n个字符的权值(均0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC*/ int m,i,s1,s2,start; unsigned c,f; HuffmanTree p; char *cd; if(n=1)return; m=2*n-1; *HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /* 0号单元未用 */ for(p=*HT+1,i=1;i=n;+i,+p,+w) 第 14 页

21、共 18 页 (*p).weight=*w; (*p).parent=(*p).lchild=(*p).rchild=0; for(;i=m;+i,+p) (*p).weight=(*p).parent=(*p).lchild=(*p).rchild=0; for(i=n+1;i=m;+i) /* 建赫夫曼树 */ /*在HT1i-1中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 */ select(*HT,i-1,&s1,&s2); (*HT)s1.parent=(*HT)s2.parent=i; (*HT)i.lchild=s1; (*HT)i.rchild=s

22、2; (*HT)i.weight=(*HT)s1.weight+(*HT)s2.weight; /* 从叶子到根逆向求每个字符的赫夫曼编码 */ *HC=(HuffmanCode)malloc(n+1)*sizeof(char*); /* 分配n个字符编码的头指针向量(0不用) */ cd=(char*)malloc(n*sizeof(char); /* 分配求编码的工作空间 */ cdn-1=0; /* 编码结束符 */ for(i=1;i=n;i+) /* 逐个字符求赫夫曼编码 */ start=n-1; /* 编码结束符位置 */ for(c=i,f=(*HT)i.parent;f!=0

23、;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); 第 15 页 共 18 页 /* 为第i个字符编码分配空间 */ strcpy(*HC)i,&cdstart); /* 从cd复制编码(串)到HC */ free(cd); /* 释放工作空间 */ 实验结果和结论 通过截图可看出：以上数据基本正确，但是第四张图在遇到两个或两个以上相同最大权值时，计算的结果不正确，但是还没发纠正过来。

24、实验分析： 注意编码结果是以文本文件的方式存储在文件codefile中！为方便用户，界面可以设计成具有几种功能的菜单样式。在程序的一次执行过程中，第一次执行初始化、编码或译码命令之后，哈夫曼树已经存在于内存中，不必再读入，每次执行中不一定都要执行初始化命令，因为文件hfmtree可能早已建好了。 第 16 页 共 18 页 综合分析部分 相关理论及实验结论 本学期通过对数据结构的学习，我对线性表、树有了很深的了解，再通过几个实验使我深刻的明白这门课程的重要性。下面简单介绍我做的实验。 数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。数据结构在计算机中的表示称为数据的物理结构又称为存

25、储结构。它包括数据元素的表示和关系的表示。在计算机中表示信息的最小单位是二进制数的一位，叫做位，在计算机中，我们可以用一个由若干位组合起来形成的一位串表示一个数据元素，通常称这个位串为元素或结点。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域。数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系；非顺序映像的特点是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。 而算法是对特定问题求解步骤的一种描述，它是指令的有限序

26、列，其中每条指令表示一个或多个操作；此外，一个算法还具有下列5个重要特性： 有穷性，确定性，可行性，输入，输出。 而算法设计的要求： 正确性，可读性，健壮性，效率和低存储量需求。 我做的第一个实验是裴波那锲序列，该函数主要通过递归调用来实现的。存储结构是顺序存储，构建的是顺序线性表。 而线性表是最常用且最简单的一种数据结构。简言之，一个线性表是n个数据元素的有限序列。线性表有顺序表示和链式表示两种实现：顺序存储结构的线性表称为顺序表，特点是，为表中相邻的元素的存储位置也相邻；线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，链式存储结构的线性表有单链表、循环链表、双向链表等

27、。 我的第二个实验是约瑟夫环，该实验是通过建立一个链表来存储数据的。第 17 页 共 18 页 在该实验中我明白指针的使用要时刻注意指针的位置，以及建立了多少个数据结点，和有没有够成环结构. 栈是限定仅在表尾进行插入和删除操作的线性表，可称为先进后出的线性表，表尾称为栈顶，表头端称为栈底。栈也有两种存储表示方法，一种是顺序栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素；另一种是链表栈。与栈相反的是队列，一种先进先出的线性表，允许插入的一端叫做队尾，允许删除的一端叫做队头，种类有线性队列、双端队列、链队列、循环队列。 表达式求值是我完成的第三个实验。为完成字符和运算符的存储，我建

28、立了两个栈，同时我还开辟了一个数组用来存储运算符之间的优先级。 树形结构是一类重要的非线性数据结构，其中树与二叉树最为常用。赫夫曼树又称为最优树，是一类带权路劲长度最短的树。 赫夫曼编码便是最后一个实验了，到了此时也就意味着学期即将结束了，回顾自己对数据结构的学习，感觉这课还真是难学啊，还那么重要。 自我总结和你对课程的建议 经过一学期的学习，我觉得自己收获颇丰。首先，自己当初C语言学的不够扎实，通过数据结构的学习加强了我对C语言的了解和运用；其次，数据结构让我懂得了如何在编程时尽量减少内存的消耗，而不是仅仅完成程序就行的；最后，就是数据结构让我明白想学好数据结构就必须加强数学的功底。 课程建议：因为数据结构很重要，根据平时的学习发现课时似乎不够，在最后查找排序的章节老师上的有些“赶”，学生不太容易吸收。所以建议学校能够增加些课时，这样老师也有足够的教学时间，讲课也可以讲的更加详细些。 第 18 页 共 18 页