北京邮电大学信息与通信工程学院数据结构实验报告实验名称： 实验一链式结构实现线性表学生姓名： 班 级：班内序号：学 号：日 期： 1 实验要求实验目的：通过选择下面四个题目之一进行实现，掌握如下内容： 熟悉C+语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力实验内容：根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。线性表存储结构（五选一）：1、 带头结点的单链表2、 不带头结点的单链表3、 循环链表4、 双链表5、 静态链表线性表的基本功能：l 构造：使用头插法、尾插法两种方法1、 插入：要求建立的链表按照关键字从小到大有序2、 删除3、 查找4、 获取链表长度5、 销毁6、 其他：可自行定义编写测试main()函数测试线性表的正确性。2. 程序分析2.1 存储结构 存储结构：顺序表2.2 关键算法分析头插法示意图：算法步骤： 堆中建立新结点 S-next指向front-next front-next指向sNode *s=new Node;s-data=ai;s-next=front-next;front-next=s;时间复杂度：O(n)尾插法算法步骤： 堆中建立新结点Node *s=new Node; 将新结点加入到链表中r-next=front-next 修改尾指针 r=s 按值查找结点示意图： 定位计数和定位指针int i=1; Node* p; p=front-next; 比较P指向的元素是否与检索值相同if(p)while(p)if(p-data=n)cout元素序号：inext;i+;elsethrow空链表！; 时间复杂度：O(n)插入操作：算法步骤： 堆中建立新结点Node *s=new Node; 将新结点插入到要插入位置后一节点p的后面，将后一结点数据写入s P指向s，在p中写入新的值s-data=p-data; s-next=p-next; p-next=s; p-data=x;时间复杂度：O（1） 删除结点示意图：删除结点示意图算法步骤：从第一个结点开始，查找第i-1个元素，设为p指向该结点；设q指向第i个元素：q = p-next;摘链，即将q元素从链表中摘除：p-next = q-next;保存q元素的数据：x = q-data;释放q元素：delete q;说明：如果算法比较复杂，可以将多句代码合成一个步骤进行说明。比如也可以这样写：从第一个结点开始，查找第i-1个元素，设为p指向该结点；设q指向第i个元素：q = p-next;摘链，即将q元素从链表中摘除：p-next = q-next; x = q-data delete q; 时间复杂度：O(n)2.3 其他程序代码：#includeusing namespace std;templatestruct NodeT data;struct Node * next;templateclass LinkListpublic:LinkList()front=new Node;front-next=NULL;LinkList(T a,int n);LinkList();Node* Get(int i);Node* Locate(int n,Node* s);void Insert(int i,T x);T Delete(int i);int GetLength();void Print();private:Node* front;templateLinkList:LinkList(T a,int n) /头插法front=new Node;front-next=NULL;for(int i=n-1;i=0;i-)Node *s=new Node;s-data=ai;s-next=front-next;front-next=s;/*templateLinkList:LinkList(T a,int n) /尾插法front=new Node;Node *r=front;for(inti=0;in;i+)Node* s=new Node;s-data=ai;r-next=s;r=s;r-next=NULL;*/templateLinkList:LinkList() /析构函数Node* p=front;while(p)front=p;p=p-next;delete front;templateNode* LinkList:Get(int i)Node* p=front-next;int j=1;while(p&j!=i)p=p-next;j+;return p; templateNode* LinkList:Locate(int n,Node* s)int i=1;Node* p;p=front-next;if(p)while(p)if(p-data=n)cout元素序号：inext;i+;elsethrow空链表！; /*while(p&p-data!=n)p=p-next;return p;t=0;if(p-next) /Locate(n,p-next);elsereturn NULL;*/ templatevoid LinkList:Insert(int i,T x)Node* p=Get(i);if(p)Node* s=new Node;s-data=p-data; /s-next=p-next;p-next=s;p-data=x;elsethrow输入有误;templateT LinkList:Delete(int i)Node * p=front;if(i!=1)p=Get(i-1);Node* q=p-next;p-next=q-next;T x=q-data;delete q;return x;templateint LinkList:GetLength()int i=0;Node* p=front-next;if(p) i+;p=p-next; return i;templatevoid LinkList:Print()Node* p=front-next;if(front-next) while(p) coutdatanext; coutendl; elsethrow该表没有元素;void main()int x,y;int a6=1,2,3,4,5,6;LinkList L(a,6);L.Print();coutxy;L.Insert(x,y);L.Print();coutx;L.Delete(x);L.Print();coutx;coutdataendl;coutx;L.Locate(x,NULL);coutL.GetLength(); 3. 程序运行结果 测试主函数流程：流程图如图所示开始打印序列是否退出？结束是 输入插入的位置和数值打印修改后序列输入删除的位置打印修改后序列输入查找的关键值打印查找关键值的位置 1、 测试条件：初始序列为1 2 3 4 5 6 插入位置1 数值6是删除元素序号3查找元素序号2查找元素6 2、 测试结论初始序列为1 2 3 4 5 6 插入位置1 数值6后序列：6 1 2 3 4 5 6是删除元素序号3 后序列：6 1 3 4 5 6查找元素序号2 后查找到序号2所对应元素为：1查找元素6 查找到所对应元素序号为1和64. 总结本次实验我掌握了线性表的操作的实现方法，实现了线性表的基本功能：使用头插法、尾插法两种方法构造了线性表