《数据结构实验学期总结.doc》由会员分享，可在线阅读，更多相关《数据结构实验学期总结.doc（18页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验学期总结摘要：本学期我完成的主要实验任务有：裴波那锲序列、约瑟夫环、表达式求值、赫夫曼编码文档内容：本学期以来，我所完成的所有实验及其总结，分别包括实验名称、实验目的及要求、实验主要内容、实验结果结论、实验分析，还有我对该课程学习总结和建议。关键字：数据结构 实验 总结 数组 链表 栈 二叉树实验一实验名称：裴波那锲序列实验目的及要求：1.熟悉开发工具的编程环境。2.体会算法和程序的不同。3.学习用不同算法实现同一程序功能，并能熟练编程实现。4. 学习分析算法。对比不同算法实现的效率有何不同，所占空间有何不同。对比不同算法的优点和缺点实验主要内容： 概要设计和存储结构K阶（k=2）
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,i
3、nt 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)
4、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 实验结果和结论实验要求完成的功能已经全部完成了，但是对于手动输入密码和随机产生密码这两种功能没能够通过程序选择来完成 实验分析：可以看出这一题是考查单链表的应用，而且这一题中的循环单链表是不需要“头结点”的，要注意空表和非
5、空表的界限。程序运行后要求用户指定初始报数上界值，人数及各人的密码。可先设n30。实验三实验名称：表达式求值实验目的及要求：通过上机实践掌握队列和栈的顺序存储结构和链式存储结构，以便我们能在相应的应用问题中正确选用它们；掌握栈和队列的特点，即先进后出与先进先出的原则；掌握栈和队列的基本运算，如入栈和出栈、入队与出队等运算在顺序存储结构和链式存储结构上的实现。以字符序列形式从终端输入语法正确的、不含变量的整数表达式。利用课本3.2.5节中给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照课本上的例子演示在求值过程中运算符栈、运算数栈、输入字符和主要操作的变化过程。实验主要内容： 概要
6、设计和存储结构构建了两个栈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); /若栈不空
7、，则删除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嵌套调用以上各函数 主要算法第 4 页 共 18 页int IfEmptyStac
8、k(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
9、)/插入元素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.
10、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;brea
11、k; 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
