数据结构实验报告--单链表.doc

《数据结构实验报告--单链表.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、C0H……a[4]^……a[2]1000H……1000H头指针1020H1080H10C0Hfront…………2.2关键算法分析1、关键算法：（1）头插法自然语言描述：a:在堆中建立新结点b:将a[i]写入到新结点的数据域c:修改新结点的指针域d:修改头结点的指针域。将新结点加入链表中伪代码描述a:Node*s=newNodeb:s->data=a[i]c:s->next=front->next;d:front->next=s（2）尾插法自然语言描述：a:在堆中建立新结点：b:将a[i]写入到新结点的数据域：c:将新结点加入到链表中d:修改修改尾指针伪代码描述

4、a:Node*s=newNodeb:s->data=a[i]c:r->next=s;d:r=s（3）遍历打印函数自然语言描述：a:判断该链表是否为空链表，如果是，报错b:如果不是空链表，新建立一个temp指针c:将temp指针指向头结点d:打印temp指针的data域e:逐个往后移动temp指针，直到temp指针的指向的指针的next域为空伪代码描述a:Iffront->next==NULLThrow”anemptylist”Node*temp=front->next;b:while(temp->next)c:cout<data<<"";d

5、:temp=temp->next;(4)获取链表长度函数自然语言描述：a:判断该链表是否为空链表，如果是，输出长度0b:如果不是空链表，新建立一个temp指针，初始化整形数n为0c:将temp指针指向头结点d:判断temp指针指向的结点的next域是否为空，如果不是，n加一，否则returnne:使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next域为0，返回n伪代码描述a:ifront->next==NULLb:Node*temp=front->next;c:while(temp->next)d:temp=temp->next;（5）析构/删除

6、函数自然语言描述：a:新建立一个指针，指向头结点b:判断要释放的结点是否存在，c:暂时保存要释放的结点d:移动a中建立的指针e:释放要释放的指针伪代码描述a:Node*p=frontb:while(p)c:front=pd:p=p->nexte:deletefront（6）按位查找函数自然语言描述：a:初始化工作指针p和计数器j，p指向第一个结点，j=1b:循环以下操作，直到p为空或者j等于1：p指向下一个结点：j加1c:若p为空，说明第i个元素不存在，抛出异常d:否则，说明p指向的元素就是所查找的元素，返回元素地址伪代码描述a:Node*p=front->n

7、ext;j=1;b:while(p&&j!=1):p=p->next:j++c:if(!p)throw”error”d:returnp（7）按位查找函数自然语言描述：a:初始化工作指针p和计数器j，p指向第一个结点，j=1b:循环以下操作，找到这个元素或者p指向最后一个结点：判断p指向的结点是不是要查找的值，如果是，返回j，否则p指向下一个结点，并且j的值加一c:如果找到最后一个结点还没有找到要查找的元素，返回查找失败信息伪代码描述a:Node*p=front->next;j=1;b:while(p):if(p->nex