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

1、北京邮电大学数据结构试验报告实验名称： 实验一 线性表学生姓名： 班 级： 班内序号： 学 号： 日 期： 2014年1月3日1 实验目的Ø 熟悉C+语言的基本编程方法，掌握集成编译环境的调试方法Ø 学习指针、模板类、异常处理的使用Ø 掌握线性表的操作的实现方法Ø 学习使用线性表解决实际问题的能力2 实验内容2.1题目1根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。线性表存储结构（五选一）：1、 带头结点的单链表2、 不带头结点的单链表3、 循环链表4、 双链表5、 静态链表 线性表的基本功能：1、 构造：使用

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

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

4、建立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)3. 析构函数自然语言描述：a.新建立一个指针，指向头结点 b.移动a中建立的指针 c.逐个释放指针 代码描述: template<class T>LinkList<T>:Li

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

6、)/按位查找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) 5. 按值查找函数 自然语言描述：a.初始化工作指针p和计数器j，p指向第一个结点，j=1 b.循环以下操作，找到这个元素或者p指向最后一个结点 b1.判断p指向的结点是不是要查找的值，如果是，返回j; b2.否则p指向下一个结点,并且j的值加一 c.如果找到最后一个结点还没有找到要查找的元素，返回查找失败信息

7、代码描述: 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.修改前一个指针的指针域，使其指向新插入的结点的位置 代码描述:template<

8、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前一个位置i-1的结点 b.设q指向第i个元素 c.将q元素从链表中删除 d.保存q元素

9、的数据 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.将temp指针指向头结点 d.打印temp指针的data域 e.逐个往后移动temp指针，

10、直到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.判断该链表是否为空链表，如果是，输出长度0 b.如果不是空链表，新建立一个temp指针，初始化整形数n为0 c.将temp指针指向头结点 d.判

11、断temp指针指向的结点的next域是否为空，如果不是，n加一，否则return n e.使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主函数流程图4.2程序运行框图5 实验心得1.调试时出现的问题及解决的方法 在编写按值查找函数时，由于没有处理好指针类

12、型的原因，导致指针无法正常返回，屡屡报错。最后意识到c+没有指针强制类型的转换机制，经过细致检查后才改正错误使得程序正常运行。 2.心得体会 了解了单链表的基本的操作函数实现，对链式存储结构有了较好的认识 3.下一步的改进 可以增加完善报错机制，增强程序的健壮性完整源代码 #include<iostream>using namespace std;template<class T>struct NodeT data;Node<T> * next;template<class T>class LinkListpublic:LinkList() fr

13、ont = new Node<T> front->next = NULL;/无参构造函数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<c

14、lass 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)/尾插法建

15、立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;template<class T>LinkList<T>:LinkList()/析构函数，销毁链表Node<T> * p = front;while(p)front = p;p = p-

16、>next;delete front;template<class 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

17、 j=0;while(p)if(j<i)p = 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;int j = 1;while(p)if(p->data = x) return j;else p = p->next; j+;return -1;template<class T>void

18、 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"插入位置非法"template<class T>T LinkList<T>:Delete(int i)/删除函数Node<T> *p = Get(i-1);Node<T> *q

19、= 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<<"将要输入的链表长度为："cin>>n;int *b=new intn;cout<<"输入链表中的元素："for(int k=0;k<n;k+) cin>>bk;LinkList<int> a(b,