北邮数据结构试验报告单链表

1、北京邮电大学数据结构试验报告实验名称：实验一线性表学生姓名：班 级：班内序号：学 号： 日 期：2021年1月3日1实验目的？ 熟悉C+语言的根本编程方法,掌握集成编译环境的调试方法？ 学习指针、模板类、异常处理的使用？ 掌握线性表的操作的实现方法？ 学习使用线性表解决实际问题的水平2实验内容2.1题目1并完成线性根据线性表的抽象数据类型的定义,选择下面任一种链式结构实现线性表,表的根本功能.线性表存储结构(五选一)：1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表线性表的根本功能：1、构造：使用头插法、尾插法两种方法2、插入：要求建立的链表根据关键字从小到大有序3

2、、删除4、查找5、获取链表长度6、销毁7、其他：可自行定义编写测试main()函数测试线性表的正确性.3程序分析3.1存储结构单链表的存储结构：1000HA2结点1020H1080HW80HA010C0HA319OOHWCOHAl1000H结点3.2关键算法分析一、关键算法1. 头插法自然语言描述:a.在堆中建立新结点b. 将ai写入到新结点的数据域c. 修改新结点的指针域d. 修改头结点的指针域,将新结点参加链表中代码描述：template<class T>LinkList<T>:LinkList(T a, int n)/头插法建立front = new Node&l

3、t;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;时间复杂度：O(n)frontfront2. 尾插法自然语言描述:a.在堆中建立新结点b. 将ai写入到新结点的数据域c. 将新结点参加到链表中d. 修改修改尾指针代码描述：template<class T>LinkList<T>:LinkList(T a, int

4、n)/尾插法建立front = new Node<T>front->next=NULL;Node<T> * r = front;for(int i=0;i<n;i+)Node<T> * s = new Node<T>s->data = ai;s->next = r->next;r->next= s;r=s;时间复杂度：O(n)iront3. 析构函数自然语言描述:a.新建立一个指针,指向头结点b. 移动a中建立的指针c. 逐个释放指针代码描述：template<class T>LinkList<

5、;T>:LinkList()/ 析构函数,销毁链表 Node<T> * p = front;while(p)front = p;p = p->next;delete front;4. 按位查找函数自然语言描述：a.初始化工作指针p和计数器j, p指向第一个结点,j=1b. 循环以下操作,直到 p为空或者j等于1bl: p指向下一个结点b2： j 加 1c. 假设p为空,说明第i个元素不存在,抛出异常d. 否那么,说明p指向的元素就是所查找的元素,返回元素地址代码描述:template<class T>Node<T>* LinkList<T&

6、gt;:Get(int i)/ 按位查找Node<T> * p = front;int j=0;while(p)if(j<i)p = p->next;j+;else break;if(!p) throw"查找位置非法"else return p;时间复杂度：O(n)llUILl*P(j=l)PQ=2>P(j=i)P(j=n)5. 按值查找函数自然语言描述：a.初始化工作指针p和计数器j, p指向第一个结点,j=1b. 循环以下操作,找到这个元素或者p指向最后一个结点b1.判断p指向的结点是不是要查找的值,如果是,返回 j;b2.否那么p指向下一

7、个结点,并且j的值加一c. 如果找到最后一个结点还没有找到要查找的元素,返回查找失败信息代码描述：template<class T>int LinkList<T>:Locate(T x)/ 按值查找(Node<T> * p = front->next;int j = 1;while(p)(if(p->data = x) return j;else(p = p->next;j+;return -1;时间复杂度：O(n)6. 插入函数自然语言描述:a.在堆中建立新结点b.将要插入的结点的数据写入到新结点的数据域c. 修改新结点的指针域d. 修改

8、前一个指针的指针域,使其指向新插入的结点的位置代码描述：template<class T>void LinkList<T>:Insert(int i,T x)/插入函数(Node<T> * p = Get(i-1);if(p)(Node<T> * s = new Node<T>s->data = x;s->next = p->next;p->next = s;else throw"插入位置非法"时间复杂度：O(n)7. 按位删除函数自然语言描述：a.从第一个结点开始,查找要删除的位数i前一个

9、位置i-1的结点b. 设q指向第i个元素c. 将q元素从链表中删除d. 保存q元素的数据e. 释放q元素代码描述:template<class T>T LinkList<T>:Delete(int i)/ 删除函数(Node<T> *p = Get(i-1);Node<T> *q = p->next;T x=q->data;p->next = q->next;delete q;return x;8. 遍历打印函数自然语言描述：a.判断该链表是否为空链表,如果是,报错b. 如果不是空链表,新建立一个temp指针c. 将tem

10、p指针指向头结点d. 打印temp指针的data域e. 逐个往后移动temp指针,直到temp指针的指向的指针的next域为空代码描述:template<class T>void LinkList<T>:PrintList()/ 打印链表Node<T> * p = front->next;while(p)cout<<p->data<<''p = p->next;cout<<endl;9. 获取链表长度函数自然语言描述：a.判断该链表是否为空链表,如果是,输出长度 0b. 如果不是空链表,新

11、建立一个temp指针,初始化整形数 n为0c. 将temp指针指向头结点d. 判断temp指针指向的结点的next域是否为空,如果不是,n加一,否那么return ne. 使temp指针逐个后移,重复 d操作,直到temp指针指向的结点的 next 域为0,返回n代码描述：template<class T>int LinkList<T>:GetLength()/ 分析链表长度Node<T> * p = front;int i=0;while(p)p = p->next;i+;return i-1;4程序运行结果4.1主函数流程图开始初始化3个的象初始化

12、一个整形数组,作为喊值准蓄执行插入函数,之后遍历打印函数来测试是杏真的插入执行按位萱找和按值萱找函麴r _结束4.2程序运行框图画 GV/indcw55ysJ'r,rTi3？i：rrdME 关' 易 链的3的棘42'表 a 亓t 籍 8 的A防一 L-:肖-r-;<一 莅廿 ffix t 探入按 ,十冥憧果ffI请IBKmU旺总清W位nIX ; 的' li 邱酩褂4富-八为元直蚊一-i5实验心得1. 调试时出现的问题及解决的方法在编写按值查找函数时,由于没有处理好指针类型的原因,导致指针无法正常返回,屡屡报错.最后意识到 C+没有指针强制类型的转换机制,经

13、过细致检查后才改正错误使得程 序正常运行.2. 心得体会了解了单链表的根本的操作函数实现,对链式存储结构有了较好的熟悉3. 下一步的改进可以增加完善报错机制,增强程序的健壮性完整源代码#include<iostream>using namespacestd;template<class T>struct NodeT data;Node<T> * next;template<class T>class LinkListpublic:LinkList() front = new Node<T> front->next = NULL;

14、 无参构造函数LinkList(T a, int n);/构造函数void Insert(int i,T x); 插入函数T Delete(int i); / 删除函数Node<T>* Get( int i);/查找第几个的元素,返回的是该元素的地址int Locate(T x); / 定位某元素int GetLength();/分析链表长度LinkList(); /析构函数void PrintList(); /打印链表private:Node<T> * front;/template<class T>/LinkList<T>:LinkList(

15、T a, int n)/头插法建立/ front = new Node<T>/front->next= NULL;/for(inti=n-1;i>=0;i-)/Node<T>* s = newNode<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>front->ne

16、xt=NULL;Node<T> * r = front;for(int i=0;i<n;i+)Node<T> * s = new Node<T>s->data = ai;s->next = r->next;r->next= s;r=s;template<class T>LinkList<T>:LinkList() 析构函数,销毁链表 Node<T> * p = front;while (p)front = p;p = p->next;delete front; template<c

17、lass T>void LinkList<T>:PrintList() /打印链表 Node<T> * p = front->next;while (p)(cout<<p->data<<''p = p->next;cout<<endl;template<class T>Node<T>* LinkList<T>:Get( int i)/ 按位查找 (Node<T> * p = front;int j=0;while (p)(if(j<i)(p

18、= p->next;j+;else break;if(!p) throw查找位置非法"else return p;template<class T>int LinkList<T>:Locate(T x) 按值查找(Node<T> * p = front->next;intj = 1;while (p)(if (p->data = x) return j;else(p = p->next;j+;return -1;template<class T>void LinkList<T>:Insert( int

19、 i,T x)/插入函数 (Node<T> * p = Get(i-1);if(p)(Node<T> * s = new Node<T>s->data = x;s->next = p->next;p->next = s;)elsethrow "插入位置非法")template<class T>T LinkList<T>:Delete( int i)/删除函数(Node<T> *p = Get(i-1);Node<T> *q = p->next;T x=q->data;p->next = q->next;delete q;return x;)template<class T>int LinkList<T>:GetLength() /分析链表长度(Node<T> * p = front;int i=0;while (p)(p = p->next;i+;)return i-1;) void main()(int n;cout«"将