数据结构试验报告_单链表

1、.专业.专注.2016级数据结构实验报告实验名称：实验一线性表一一题目i学生姓名：李文超班级：2015661131班内序号：15学号：2015522147日期：2016年11月13日word可编辑1. 实验要求实验目的：，并完成线根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表性表的基本功能。线性表存储结构（五选一）：1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表线性表的基本功能：1、构造：使用头插法、尾插法两种方法2、插入：要求建立的链表按照关键字从小到大有序3、删除4、查找5、获取链表长度6、销毁7、其他：可自行定义编写测试main（）函数测试

2、线性表的正确性 。2. 程序分析2.1存储结构单链表的存储：（1） 链表用一组任意的存储单元来存放线性表的结点。这组存储单元既可以是连续的也可以是不连续的，甚至零散地分布在内存的某些位置。（2） 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个元素值的同时，还要存储该元素的直接后继元素的位置信息，这个信息称为指针或链。结点结构data | next |单链表在内存中的存储示意头指针front4data域-存放结点值的数据域next域-存放结点的直接后继的地址的指针域1000Ha31080H1020Ha110C0H1080Ha4A10C0Ha21000H地址

3、内存单元112.2关键算法分析1、关键算法：(1) 头插法自然语言描述:a:在堆中建立新结点b:将ai写入到新结点的数据域c:修改新结点的指针域d:修改头结点的指针域。将新结点加入链表中 伪代码描述a:Node <T> * s=new Node <T>b:s->data=aic:s->n ext=fro nt->n ext;d:front->n ext=s(2) 尾插法自然语言描述:a:在堆中建立新结点：b:将ai写入到新结点的数据域：c:将新结点加入到链表中d:修改修改尾指针伪代码描述a:Node <T> * s=new Node

4、<T>b:s->data=aic:r->n ext=s;d:r=s(3) 遍历打印函数自然语言描述：a:判断该链表是否为空链表，如果是，报错b:如果不是空链表，新建立一个temp指针c:将temp指针指向头结点d:打印temp指针的data域e:逐个往后移动temp指针，直到temp指针的指向的指针的next域为空伪代码描述a: If fron t-> next=NULLThrow ”n empty list ”Node<T>* temp=fr ont->n ext;b:while(temp-> next)c:cout<<tem

5、p->data<<""d:temp=temp->n ext;(4) 获取链表长度函数自然语言描述：a:判断该链表是否为空链表，如果是，输出长度0b:如果不是空链表，新建立一个temp指针，初始化整形数n为0c:将temp指针指向头结点否则 return nnext域为0，d:判断temp指针指向的结点的next域是否为空，如果不是，n加一，e:使temp指针逐个后移，重复d操作，直到temp指针指向的结点的 返回n伪代码描述a:if ro nt- >n ext=NULLb:Node<T>* temp=fr ont->n ext

6、;c:while(temp-> next)d:temp=temp->n ext;(5) 析构/删除函数自然语言描述:a:新建立一个指针，指向头结点b:判断要释放的结点是否存在，c:暂时保存要释放的结点d:移动a中建立的指针e:释放要释放的指针伪代码描述a:Node <T> * p=frontb:while(p)c:fron t=pd:p=p->n exte:delete front(6) 按位查找函数自然语言描述：a:初始化工作指针p和计数器j, p指向第一个结点，j=1b:循环以下操作，直到p为空或者j等于1:p指向下一个结点:j加1c:若p为空，说明第i个元素

7、不存在，抛出异常d:否则，说明p指向的元素就是所查找的元素，返回元素地址伪代码描述a:Node <T> * p=fro nt->n ext;j=1;b:while(p&&j!=1):p=p->n ext:j+c:if(!p) throw"error ”d:return p(7) 按位查找函数自然语言描述：a:初始化工作指针 p和计数器j, p指向第一个结点，j=1b:循环以下操作，找到这个元素或者p指向最后一个结点:判断p指向的结点是不是要查找的值，如果是，返回j，否则p指向下 一个结点，并且j的值加一c:如果找到最后一个结点还没有找到要查找的

8、元素，返回查找失败信息伪代码描述a:Node <T> * p=front->n ext;j=1;b:while(p)if(p->n ext=x) retur n jp=p->n extj+c:return error(8) 插入函数自然语言描述:a:在堆中建立新结点b:将要插入的结点的数据写入到新结点的数据域c:修改新结点的指针域d:修改前一个指针的指针域，使其指向新插入的结点的位置伪代码描述a:Node <T> * s=new Node <T>b:s-data=p->datac:s->n ext=p->nextd:p-&

9、gt;n ext=se:p->data=x(9) 删除函数自然语言描述：a:从第一个结点开始，查找要删除的位数i前一个位置i-1的结点b:设q指向第i个元素c:将q元素从链表中删除d:保存q元素的数据e:释放q元素伪代码描述a:q=p->n extb:p->n ext=q->nextc:x=q->datad:delete q2、代码详细分析(插入)：(1)从第一个结点开始，查找节点，使它的数据比x大，设p指向该结点while (x>p->data) p=p->n ext;(2) 新建一个节点s,把p的数据赋给s： s->data=p->

10、;data;(3) 把 s力口至U p 后面：s->next=p->next; p->next=s;(4) p节点的数据用x替换：p->data=x;示意图如图所示p->data3、关键算法的时间复杂度：0 (1)3. 程序运行结果1. 流程图：开始初始化一个对象初始化一个整形数组，作为赋值准备分别利用头插法和尾插法初始化，并且用遍历打印函数来显示数值执行插入函数，之后遍历打印函数来测试是否真的插入执行删除函数，之后遍历打印函数来测试是否真的删除执行按位查找和按值查找函数结束2、结果截图 d:Cppvade rDe bu gva denese遍历线性表结果为；1J

11、瞒入一个值后的线性表为；1Pnd4j* d :Cp p wa d 巳 rD ebu gva d er.exe删除一个值后的线性表为:1博5个位置上的元素地址是;009E54403测试结论：可以正确的对链表进行插入，删除，取长度，输出操作。且插入任意一个元素后，链表的顺序依然是由小到大。4、给出代码（文末）4总结1、问题书中已经给出析构、查找、插入、删除过程代码，遍历以及获取长度代码需要自己写 出，刚开始写时一直出现各种基本错误，后来经过不断调试解决了问题。编写main函数时，调用插入删除等操作的代码一直编写失败，后自行查找资料后解决2、收获这次编程任务完成地较为艰辛，但做完之后大大加深了自己对

12、书中各个知识点的印象和理解。也学会了一些编写算法的小技巧，要有耐心，多看书复习知识。总之，这次实验使我印象深刻。#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); 头插法/

13、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>:L inkList (T a

14、,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 vclass T>LinkList<T>:L inkList (T a,int n )/尾插

15、法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;while (p->next != NULL) p = p->next;cout <&l

16、t; 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

17、 (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 &l

18、t; class T>T LinkList<T>:Delete( int i)Node<T> * p = front;if(i != 1) p = Get(i - 1);if(!p && !p->next)throw"位置错误Node <T> * q = p_>n ext;p ->next = q ->next;T x = q ->data;delete q;return x; template < class T>LinkList<T>:LinkList()Node<T>