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

数据结构实验学期总结摘要：本学期我完成的主要实验任务有：裴波那锲序列、约瑟夫环、表达式求值、赫夫曼编码文档内容：本学期以来，我所完成的所有实验及其总结，分别包括实验名称、实验目的及要求、实验主要内容、实验结果结论、实验分析，还有我对该课程学习总结和建议。关键字：数据结构 实验 总结 数组 链表 栈 二叉树实验一实验名称：裴波那锲序列实验目的及要求：1.熟悉开发工具的编程环境。2.体会算法和程序的不同。3.学习用不同算法实现同一程序功能，并能熟练编程实现。4. 学习分析算法。对比不同算法实现的效率有何不同，所占空间有何不同。对比不同算法的优点和缺点实验主要内容： 概要设计和存储结构K阶（k=2）裴波那契序列的第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)，如此便实现了裴波那契序列第m项的计算。下面程序段中语句的时间复杂度为：O(sum)=2(m-k) (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);int 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; printf( %dt%dn,p1-num,p1-data); free(p1);/count 实验结果和结论实验要求完成的功能已经全部完成了，但是对于手动输入密码和随机产生密码这两种功能没能够通过程序选择来完成 实验分析：可以看出这一题是考查单链表的应用，而且这一题中的循环单链表是不需要“头结点”的，要注意空表和非空表的界限。程序运行后要求用户指定初始报数上界值，人数及各人的密码。可先设n30。实验三实验名称：表达式求值实验目的及要求：通过上机实践掌握队列和栈的顺序存储结构和链式存储结构，以便我们能在相应的应用问题中正确选用它们；掌握栈和队列的特点，即先进后出与先进先出的原则；掌握栈和队列的基本运算，如入栈和出栈、入队与出队等运算在顺序存储结构和链式存储结构上的实现。以字符序列形式从终端输入语法正确的、不含变量的整数表达式。利用课本3.2.5节中给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照课本上的例子演示在求值过程中运算符栈、运算数栈、输入字符和主要操作的变化过程。实验主要内容： 概要设计和存储结构构建了两个栈OPTR, OPND（OPTR为运算符栈，OPND为运算数栈）typedef struct ElemType *base; ElemType *top; int stacksize;Stack;/定义栈类型int IfEmptyStack(Stack S);/判断栈是否为空void InitStack(Stack &S);/构建一个栈void EmptyStack(Stack &S);/栈空时，则返回值void Push(Stack &S, ElemType e); /插入元素e为新的栈顶元素void Pop(Stack &S, ElemType &e); /若栈不空，则删除s的栈顶元素，用e返回其值void ShowStack(Stack S); /输出计算结果int In(char ch); /判断字符ch是不是运算符char Precede(char a,char b);/判定运算符栈顶运算符a与读入b之间优先权int Operate(int a, char f, int b); /进行二元运算的函数void EvaluateExpression();/算术表达式求值的算符优先算法main函数调用EvaluateExpression，EvaluateExpression嵌套调用以上各函数 主要算法第 18 页 共 18 页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 EmptyStack(Stack &S)/若栈为空 ，则返回值 S.top=S.base; 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; return ;/Pushvoid 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;int In(char 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,1,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; case =: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();/接收最后输入的一个回车符，否则在主函数中只能输入一次 printf(计算结果为: ); ShowStack(OPND); printf(n);/EvaluateExpression所有的运算数都定义为整型，运算符定义为字符型 实验结果和结论程序在表达式输入错误即括号不相匹配时能够报错了,并结束程序。但是在连续输入+，-，*，/时，程序不能够报错还是能够给出计算结果（如截图4所示） 实验分析：显然要先考虑所用到的栈存储结构，以及栈的初始化、出栈、入栈、取栈顶元素等一系列的栈的基本操作的实现，以便生成运算符栈和操作数栈，及实现算符优先法的算法。注意，在读入表达式的字符序列的同时完成运算符和操作数的识别处理，以及相应的运算。在识别操作数的同时，别忘记将字符序列形式转换成整数形式！还要在程序的适当位置输出运算符栈、操作数栈、输入字符和主要操作的内容。有可能的话，还要考虑用户输入表达式时可能会犯的简单的语法错误，给予适当的提示，象括号不匹配、错误的运算符之类。实验四实验名称：赫夫曼编码实验目的及要求：通过上机实践，帮助学生进一步掌握指针变量和动态变量的含义，掌握二叉树的结构特性，以及各种存储结构的特点及适用范围，掌握用指针类型描述、访问和处理二叉树的运算一个完整的系统应具有以下功能：（1） 初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存储于文件hfmtree中。（2） 编码。利用建好的哈夫曼树，对要传输的文件tobefile中的正文进行编码，然后将结果存入另一个文件codefile中。（3） 译码。利用建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件文件textfile中。（4） 印代码文件。将文件codefile以紧凑格式显示在终端屏幕上，每行50个代码，同时将此字符形式的编码文件写入文件codeprin中。（5） 印哈夫曼树。将已在内存中的哈夫曼树以直观的形式（树或凹入表或其它形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。实验主要内容： 概要设计和存储结构赫夫曼树中没度1的结点，则n个叶子结点的赫夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中。为求编码需从叶子结点出发走一条从叶子到根的路径；而为译码需从根出发走一条从根到叶子的路径。 故建立存储如下：typedef struct unsigned int weight; unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树 */typedef char *HuffmanCode; /* 动态分配数组存储赫夫曼编码表 */向量HT的前n个分量表示叶子结点，最后一个分量表示根结点。各字符的编码长度不等，所以按实际长度动态分配空间。程序中总共建立了四个模块：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 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+) if(tj.weight*s2) j=*s1; *s1=*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) (*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=s2; (*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;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); /* 为第i个字符编码分配空间 */ strcpy(*HC)i,&cdstart); /* 从cd复制编码(串)到HC */ free(cd); /* 释放工作空间 */ 实验结果和结论通过截图可看出：以上数据基本正确，但是第四张图在遇到两个或两个以上相同最大权值时，计算的结果不正确，但是还没发纠正过来。 实验分析：注意编码结果是以文本文件的方式存储在文件codefile中！为方便用户，界面可以设计成具有几种功能的菜单样式。在程序的一次执行过程中，第一次执行初始化、编码或译码命令之后，哈夫曼树已经存在于内存中，不必再读入，每次执行中不一定都要执行初始化命令，因为文件hfmtree可能早已建好了。综合分析部分 相关理论及实验结论本学期通过对数据结构的学习，我对线性表、树有了很深的了解，再通过几个实验使我深刻的明白这门课程的重要性。下面简单介绍我做的实验。数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。数据结构在计算机中的表示称为数据的物理结构又称为存储结构。它包括数据元素的表示和关系的表示。在计算机中表示信息的最小单位是二进制数的一位，叫做位，在计算机中，我们可以用一个由若干位组合起来形成的一位串表示一个数据元素，通常称这个位串为元素或结点。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域。数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系；非顺序映像的特点是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。而算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作；此外，一个算法还具有下列5个重要特性：有穷性，确定性，可行性，输入，输出。而算法设计的要求：正确性，可读性，健壮性，效率和低存储量需求。我做的第一个实验是裴波那锲序列，该函数主要通过递归调用来实现的。存储结构是顺序存储，构建的是顺序线性表。而线性表是最常用