文档介绍：2016级数据结构实验报告实验名称:实验一线性表——题冃1学生姓名:李文超班级:2015661131班内序号:15学号:2015522147H期:2016年11月13日实验要求实验ti的:根据线性表的抽象数据类型的定义,选择下面任一种链式结构实现线性表,并完成线性表的基本功能。线性表存储结构(五选一):1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表线性表的基木功能:1、构造:使用头插法、尾插法两种方法2、插入:要求建立的链表按照关键字从小到大有序3、删除4、查找5、获取链表长度6、销毁7、其他:可白行定义编写测试mainO函数测试线性表的正确性。程序分析1存储结构单链表的存储:(1) 链表用-•组任意的存储单元來存放线性表的结点。这组存储单元既可以是连续的,也可以是不连续的,甚至零散地分布在内存的某些位置。(2) 链表屮结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系,在存储每个元索值的同时,还要存储该元索的直接后继元索的位査信息,这个信息称为指针或链。结点结构I 1 1data域—存放结点值的数据域Idata|next|next域---存放结点的直接后继的地址的指针域单链表在内存中的存储示意地址内存单元10C0Hfront2关键算法分析1、关键算法:(1) 头插法自然语言描述:a:在堆中建立新结点b:将a[i]写入到新结点的数据域c:修改新结点的指针域d:修改头结点的指针域。将新结点加入链表中伪代码描述a:Node<T>*s=newNode<T>b:s->data二a[i]c:s->next=front->ncxt;d:front->ncxt=s(2) 尾插法口然语言描述:a:在堆屮建立新结点:b:将a[i]写入到新结点的数据域:c:将新结点加入到链表中d:修改修改尾指针伪代码描述a:Node<T>*s=newNode<T>b:s->data=a[i]c:r~>next二s;d:r=s遍历打印函数自然语言描述:a:判断该链表是否为空链表,如果是,报错b:如果不是空链表,新建立一个temp指针c:将temp指针指向头结点d:打印temp指针的data域e:逐个往后移动temp指针,直到temp指针的指向的指针的next域为空伪代码描述a:Iffront->next~NULL©Throw”anemptylist”②Node<T>*temp=front->next;b:whi1e(temp-〉next)c:cout<<temp->da ;d:tcmp=temp->next;获取链农长度函数自然语言描述:a:判断该链表是否为空链表,如果是,输出长度0b:如果不是空链表,新建立一个temp指针,初始化整形数n为0c:将temp指针指向头结点d:判断temp指针指向的结点的next域是否为空,如果不是,n加一,否则returnne:使tei叩指针逐个后移,重复d操作,直到te叩指针指向的结点的next域为0,返回n伪代码描述a:ifront->next==NULLb:Node<T>*temp=front->next;c:whi1e(temp->next)d:temp=temp->next;析构/删除函数自然语言描述:a:新建立一个指针,指向头结点b:判断要释放的结点是否存在,c:暂时保存要释放的结点d:移动a中建立的指针e:释放要禅放的指针伪代码描述a:Node<T>*p=frontb:while(p)c:front二pd:p=p->nexte:deletefront按位查找函数自然语言描述:a:初始化工作指针P和计数器j,P指向第一个结点,j二1b:循环以下操作,直到p为空或者j等于1:P指向下一个结点:j加1c:若p为空,说明第i个元索不存在,抛出异常d:否则,说明p指向的元素就是所杏找的元素,返回元素地址伪代码描述a:Node<T>*p=front->next;j=l;b:while(p&&j!=l)®:p=p->noxt②:j++c:if(!p)throw”error”d:returnp按位查找函数自然语言描述:a:初始化工作指针p和计数器j,p指向第一个结点,j=lb:循环以卜•操作,找到这个元索或者p指向最后一个结点®:判断P指向的结点是不是要査找的值,如果是,返回j,否则P指向下一个结点,并-FLj的值加一c:如果找到最麻一个结点还没有找到要杳找的元素,返冋杏找失败信息伪代码描述a:Node<T>*p=front->next;j=l;b:while(p)①:if(p->next==x)returnjp二p->nextj++c:return"error"插入函数自然语言描述:a:在堆中建立新结点b:将要插入的结点的数据写入到新结点的数据域c:修改新结点的指针域d