北邮数据结构实验报告实验一线性表(共11页).docx

精选优质文档-倾情为你奉上数据结构实验报告实验名称： 实验一线性表题目1学生姓名： 申宇飞班 级： 信通3班班内序号： 03学 号： 日 期： 2013年11月4日1. 实验要求实验目的：熟练掌握线性表的基本操作，包括：创建、插入、删除、查找、输出、求长度、合并等运算，以及各类操作在顺序存储结构和链式存储结构上的实现。实验内容：根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。线性表存储结构（五选一）：1、 带头结点的单链表2、 不带头结点的单链表3、 循环链表4、 双链表5、 静态链表 线性表的基本功能：1、 构造：使用头插法、尾插法两种方法2、 插入：要求建立的链表按照关键字从小到大有序3、 删除4、 查找5、 获取链表长度6、 销毁7、 其他：可自行定义编写测试main()函数测试线性表的正确性。2. 程序分析2.1 存储结构链表的具体存储表示为： 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的） 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址信息（称为指针）链表的结点结构    datanext         data域-存放结点值的数据域      next域-存放结点的直接后继的地址（位置）的指针域（链域）地址 内存单元a31080Ha110C0Ha4a21000H1000H头指针 1020H1080H10C0H front 2.2 关键算法分析1、关键算法： 1：头插法 自然语言描述： a:在堆中建立新结点 b:将ai写入到新结点的数据域 c:修改新结点的指针域 d:修改头结点的指针域。将新结点加入链表中 伪代码描述 a:Node <T> * s=new Node <T> b:s->data=ai c:s->next=front->next; d:front->next=s 2：尾插法 自然语言描述： a:在堆中建立新结点： b:将ai写入到新结点的数据域： c:将新结点加入到链表中 d:修改修改尾指针 伪代码描述 a:Node <T> * s=new Node <T> b:s->data=ai c:r->next=s; d:r=s 3：析构/删除函数 自然语言描述： a:新建立一个指针，指向头结点 b:判断要释放的结点是否存在， c:暂时保存要释放的结点 d:移动a中建立的指针 e:释放要释放的指针 伪代码描述 a:Node <T> * p=front b:while(p) c:front=p d:p=p->next e:delete front 4：按位查找函数 自然语言描述： a:初始化工作指针p和计数器j，p指向第一个结点，j=1 b:循环以下操作，直到p为空或者j等于1 b1：p指向下一个结点 b2：j加1 c:若p为空，说明第i个元素不存在，抛出异常 d:否则，说明p指向的元素就是所查找的元素，返回元素地址 伪代码描述 a:Node <T> * p=front->next;j=1; b:while(p&&j!=1) b1:p=p->next b2:j+ c:if(!p) throw ”error” d:return p 5：按位查找函数 自然语言描述： a:初始化工作指针p和计数器j，p指向第一个结点，j=1 b:循环以下操作，找到这个元素或者p指向最后一个结点 b1：判断p指向的结点是不是要查找的值，如果是，返回j，否则p指向下 一个结点，并且j的值加一 c:如果找到最后一个结点还没有找到要查找的元素，返回查找失败信息 伪代码描述 a:Node <T> * p=front->next;j=1; b:while(p) b1: if(p->next=x) return j p=p->next j+ c:return “error” 6：插入函数 自然语言描述： a:在堆中建立新结点 b:将要插入的结点的数据写入到新结点的数据域 c:修改新结点的指针域 d:修改前一个指针的指针域，使其指向新插入的结点的位置 伪代码描述 a:Node <T> * s=new Node <T> b:s-data=p->data c:s->next=p->next d:p->next=s e:p->data=x 7：删除函数 自然语言描述： a:从第一个结点开始，查找要删除的位数i前一个位置i-1的结点 b:设q指向第i个元素 c:将q元素从链表中删除 d:保存q元素的数据 e:释放q元素 伪代码描述 a:q=p->next b:p->next=q->next c:x=q->data d:delete q 8：遍历打印函数 自然语言描述： a:判断该链表是否为空链表，如果是，报错 b:如果不是空链表，新建立一个temp指针 c:将temp指针指向头结点 d:打印temp指针的data域 e:逐个往后移动temp指针，直到temp指针的指向的指针的next域为空 伪代码描述 If front->next=NULL Throw ”an empty list ” Node<T>* temp=front->next; while(temp->next) cout<<temp->data<<" " temp=temp->next; 9：获取链表长度函数 自然语言描述： a:判断该链表是否为空链表，如果是，输出长度0 b:如果不是空链表，新建立一个temp指针，初始化整形数n为0 c:将temp指针指向头结点 d:判断temp指针指向的结点的next域是否为空，如果不是，n加一，否则return n e: 使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next域为0，返回n 伪代码描述 int n=0 if ront->next=NULL n=0; else Node<T>* temp=front->next; while(temp->next) n+; temp=temp->next; return n;2、代码详细分析：（1）从第一个结点开始，查找节点，使它的数据比x大，设p指向该结点：while (x>p->data) p=p->next;（2）新建一个节点s，把p的数据赋给s： s->data=p->data;（3）把s加到p后面：s->next=p->next; p->next=s;（4）p节点的数据用x替换：p->data=x;示意图如图所示pxp->data s3、 关键算法的时间复杂度：O（1)3. 程序运行结果程序截图1. 流程图： 开始初始化一个对象 初始化一个整形数组，作为赋值准备分别利用头插法和尾插法初始化，并且用遍历打印函数来显示数值执行删除函数，之后遍历打印函数来测试是否真的删除执行插入函数，之后遍历打印函数来测试是否真的插入执行按位查找和按值查找函数结束2.测试条件：插入、删除元素的位置一定要在链表的长度范围之内。3.测试结论：可以正确的对链表进行插入，删除，取长度，输出操作。且插入任意一个元素后，链表的顺序依然是由小到大。4. 总结1.调试时出现的问题及解决的方法：（1）刚开始时用NULL置空最后一个节点的指针域，发现调试时出现NULL未声明的情况。最后发现用0去置空最后一个节点的指针域，调试成功。（2）刚开始遍历总是不能完全遍历链表。最后发现循环语句中两个句子顺序写反，更正顺序后，调试成功。2.心得体会： 这道题是相对比较基础，目的是实现线性表的基本功能，书上也几乎给出了所有的模板类的定义，但是在自己进行编程时还是出了很多问题。通过这个实例，我对模板类的定义与使用有了个初步的了解，了解了单链表的基本的操作和函数实现。以后必须自己动手编，实现理论与实践相结合，提高自己的编程能力。3.下一步的改进：这个程序的交互性不强，可以改进的地方应该是可以从外部输入数组而不仅仅是编程者给定。此外，显示的界面不够友好，有待改善，而且可以增加完善的报错机制。此外，也希望老师能在课上给出更多的优化指导。代码#include "iostream"using namespace std;template <class T>struct NodeT data;struct Node * next;template <class T>class LinkListpublic:LinkList() /无参构造front = new Node<T>front->next = NULL;LinkList(T a, int n);/头插法/LinkList(T a,int n);/尾插法void PrintList();/按次序遍历int GetLength();/获取线性表的长度Node <T> * Get(int i);/获取第i个位置上的元素结点的地址int Locate(T x);/查找void Insert(int i, T x);/插入T Delete(int i);/删除LinkList();/销毁private:Node <T> * front;template <class T>LinkList<T>:LinkList(T a, int n)/头插法front = new Node<T>front->next = NULL;for(int i = n - 1; i >= 0; i-)Node<T> * s = new Node<T>/建立新结点s->data = ai;/给新结点数据域赋值s->next = front->next;/修改新结点的指针域front->next = s;/修改头指针的指针域/* template <class T> LinkList<T>:LinkList(T a,int n )/尾插法 front=new Node<T> Node <T> * r = front; for(int i=0;i<n;i+) Node<T> * s = new Node<T> s->data=ai; r->next=s; r=s; r->next=NULL; */template <class T>void LinkList<T>:PrintList()Node<T> * p = front;-p = p->next;while(p->next != NULL)p = p->next;cout << p->data << endl;template <class T>int LinkList<T>:GetLength()Node<T> * p = front;int n = 0;while(p->next != NULL) p = p->next; n+; return n;template <class T>Node <T> * LinkList<T>:Get(int i)Node<T> * p = front->next;int j = 1;while(p&&j != i)p = p->next;j+;return p;template <class T>void LinkList<T>:Insert(int i, T x)Node<T> * p = front;if(i != 1)p = Get(i - 1);if(p)Node<T> * s = new Node<T>s->data = x;s->next = p->next;p->next = s;else throw "位置错误"template <class T>T LinkList<T>:Delete(int i)Node<T> * p = front;if(i != 1)p = Get(i - 1);Node <T> * s = p->next;T x = s->data;p->next = s->next;return x;delete s;else throw "位置错误"template <class T>LinkList<T>:LinkList()Node<T> * p = front;while(p)p = p->next;delete front;front = p;int main()const int n = 10;int an = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ;LinkList<int> list(a, n);/list.hLinkList(a,n);/list.rLinkList(a,n);cout << list.GetLength() << endl;cout << endl;list.PrintList();cout << endl;list.Insert(1, 0);list.PrintList();cout << list.Get(2) << endl;list.LinkList();return 0;专心-专注-专业