链表顺序表实验报告--数据结构与算法分析模板.doc

链表顺序表实验报告--数据结构与算法分析数据结构与算法分析课程设计报告课题名称:使用一个链表和顺序表构建城市数据库提交文档组号:2四号宋体编程学生姓名及学号:四号宋体测试学生姓名及学号:四号宋体报告学生姓名及学号:四号宋体指导教师姓名:四号宋体指导教师评阅成绩:四号宋体,按百分制给分指导教师评阅意见:..四号宋体提交报告时间:2013年11月日实验一:Implementacitydatabaseusingunorderedlistsandlinklists实验的目的和要求:<1>采用C++的ASCII码文件和模块函数实现;<2>熟练掌握数组列表和链表列表的实现;<3>熟练掌握计算机系统的基本操作方法,了解如何编译、运行一个C++程序;<4>上机调试程序,掌握查错、排错使程序能正确运行。:1、硬件环境:索尼笔记本电脑,Intel(R)Core(TM)i7-3632M,8GB内存可;2、软件环境:Windows8下的MicrosoftVisualStudio2008算法描述:数据结构与算法分析的背景:数据结构是计算机程序设计的重要理论技术基础,它不仅是计算机学科的核心课称,而且已成为其它理工专业的热门选修课。 数据结构是一门专业选技术基础科。一方面,它要求我们学会分析研究计算机加工的数据结构的特性,以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法,并初步掌握算法的时间分析和空间分析的技术;另一方面,数据结构的学习过程也是复杂程序设计的训练过程,要求我们编写的程序结构清楚和正确易读,复合软件工程的规范,并培养我们的数据抽象能力。本次课程设计就是对数据结构中的顺序表和链表的操作的应用。顺序表:顺序表的定义(1)顺序存储方法即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。(2)顺序表(SequentialList) 用顺序存储方法存储的线性表简称为顺序表(SequentialList)。,设线性表中所有结点的类型相同,则每个结点所占用存储空间大小亦相同。假设表中每个结点占用c个存储单元,其中第一个单元的存储地址则是该结点的存储地址,并设表中开始结点a1的存储地址(简称为基地址)是LOC(a1),那么结点ai的存储地址LOC(ai)可通过下式计算:LOC(ai)=LOC(a1)+(i-1)*c1≤i≤n注意: 在顺序表中,每个结点ai的存储地址是该结点在表中的位置i的线性函数。只要知道基地址和每个结点的大小,就可在相同时间内求出任一结点的存储地址。是一种随机存取结构。顺序表上实现的基本运算:表的初始化;求表长;取表中第i个结点;查找值为x的结点;插入(1)插入运算的逻辑描述线性表的插入运算是指在表的第i(1≤i≤n+1)个位置上,插入一个新结点x,使长度为n的线性表:(a1,…,ai-1,ai,…an)变成长度为n+1的线性表:(a1,…,ai-1,x,ai,…an)注意: ①由于向量空间大小在声明时确定,当L->length≥ListSize时,表空间已满,不可再做插入操作; ②当插入位置i的值为i>n或i<1时为非法位置,不可做正常插入操作;(2)顺序表插入操作过程在顺序表中,结点的物理顺序必须和结点的逻辑顺序保持一致,因此必须将表中位置为n,n-1,…,i上的结点,依次后移到位置n+1,n,…,i+1上,空出第i个位置,然后在该位置上插入新结点x。仅当插入位置i=n+1时,才无须移动结点,直接将x插入表的末尾。(4)算法分析①问题的规模表的长度L->length(设值为n)是问题的规模。②移动结点的次数由表长n和插入位置i决定算法的时间主要花费在for循环中的结点后移语句上。该语句的执行次数是n-i+1。当i=n+1:移动结点次数为0,即算法在最好时间复杂度是0(1)当i=1:移动结点次数为n,即算法在最坏情况下时间复杂度是0(n)③移动结点的平均次数Eis(n)链表:1:一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息,第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。2:链表最基本的结构是在每个节点保存数据和到下一个节点的地址,在最后一个节点保存一个特殊的结束标记,另外在一个固定的位置保存指向第一个节点的指针,有的时候也会同时储存指向最后一个节点的指针。一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点,一直访问到需要的位置。但是也能够提前把一个节点的位置另外保存起来,然后直接访问。当然如果只是访问数据就没必要了,不如在链表上储存指向实际数据的指针。这样一般是为了访问链表中的下一个或者前一个(需要储存反向的指针)节点。3:在链表描述中,集合中的元素都放在链表的节点中进行描述。链表中的节点不是一个数组元素,因此