北邮数据结构实验(实现一个链栈)

《北邮数据结构实验(实现一个链栈)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、附录h实验报告模板数据结构实验报告实验名称：实现一个链栈学生姓名：hello#******班lA］序号：*****号:1.实验目的和内容(1)实验鬥的：>进一步掌握指针、模板类、异常处理的使川>掌握栈的操作的实现方法>学习使川栈解决实际问题的能力(2)实验内容：根据栈的抽象数据类型的定义，按要求实现一个栈的基本功能。要求：a.实现一个链栈b.编写测试mainO函数测试栈或队列的正确性。2.程序分析2.1存储结构：链栈的存储结构是:an-l•••fIA栈顶栈底2.2程序流程：栈(链栈)的基本功能：(1)用逐个元素入栈的方法实现一个®木的链栈：①在栈中逮立新结点

2、：Node*p=newNode;②将a[i]写入到新结点的数据域:p->data=x;①将新结点加入到链栈屮：P->next=top;①修改新结点的指针域：top=p;算法的时间杂度为0(1)。元素入栈建立链栈的过程如K图：Top(2)出栈操作①先嬰判断栈是否为空：if(Empty())throw"下溢"；②将栈顶将要出栈的元素赋给x:Tx=top-〉data;③建立新的节点指针p:structNode*p=top;④栈顶招针向后移动：top=top->next;⑤释放P所指向的栈顶空间并返冋収lli的槐顶元素的值：deletep;retu

3、rnx算法的时间S杂度为0(1)。此出栈的过祝如下图top(1)获取栈顶元素：①判断栈是否为空栈：if(!toP)throw"此栈为空栈";②将栈顶的元素的值赋给x:Tx=top->data;③返回栈顶值:returnx;算法的时间S杂度为0(1)。(2)获取栈的长度①初始化计数器：intj=0;②建立新的节点指针P:structNode*p=top;③判断指针P，(1)获取栈顶元素：①判断栈是否为空栈：if(!toP)throw"此栈为空栈";②将栈顶的元素的值赋给x:Tx=top->data;③返回栈顶值:returnx;算法的时间S杂度为0(1)

4、。(2)获取栈的长度①初始化计数器：intj=0;②建立新的节点指针P:structNode*p=top;③判断指针P，如果不是空桁针，则桁针向后移动，计数器加一:while(p)p=p->next;j++;}吋间复杂度为0(l)o(1)析构函数①建立新的节点:structNode*p=top;deletep};②头结点向后移动，并释放头结点：top=top->next;③当top指针不力空时，执行循环操作：while(top){吋间复杂度为0(l)o程序过程如下图：2.3关键算法分析算法1:Push(Tx)[1]算法功能：入栈操作；[2]算法基

5、本思想：将己知数列的元素依次压到栈中。[3]算法空间、时间S杂度分析：算法的时间复杂度为0(1)。[4]代码逻辑：structNode*p=newNode;p->data=x;p->next=top;top=p;算法2:Pop()[1]算法功能：元素出栈。[2]算法基木思想:将栈屮的元素依次输出。[3]算法空间、吋间复杂度分析：算法的吋间复杂度为0(1)。[4]代码逻辑：if(Empty())throw"卜溢"；Tx=top-〉data;structNode*p=top;top=top->next;deletep;returnx;算法3:G

6、etTopO[1]算法功能：获取栈顶元素；[2]算法基本思想：找出top指针所指的值；[3]算法空间、时间S杂度分析：算法的时间S杂度为0(1);[4]代码逻辑：if(!top)throw〃此栈为空栈〃;Tx=top->data;returnx;算法4:GetLength()[1]算法功能：获取栈的长度；[2]算法基本思想：通过判断指针是否为空，指针后移，计数器加一;[3]算法空间、时间S杂度分析：算法的时间S杂度为0(1);[4]代码逻辑：intj=0;structNode*p=top;while(p){p=p->next;j++;}returnj;

7、算法5:〜LinkStackO[1]算法功能：销毁链栈；[2]算法基本思想：销毁单链表释放出内存。[3]算法空间、时间复杂度分析：算法的吋间复杂度为0(1);[4]代码逻辑：while(top){structNode*p=top;top=top->next;deletep;cout<〈"析构函数0动执行完毕";2.4其他只是单纯的用到了类的构造函数的调用1.程序运行结果分析想实现用户直接输入一个数组存放到链栈中总结4.1实验的难点和关键点关键点是正确调用各个函数，用主函数实现各个函数的功能；4.2心得体会通过这个链栈的基础程序的编写丼将它实现，我完全掌

8、握了链栈的使川方法,这将对我以后对数裾结构的学习有很