《链表顺序表实验报告--数据结构与算法分析》由会员分享，可在线阅读，更多相关《链表顺序表实验报告--数据结构与算法分析（10页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法分析课程设计报告课题名称: 使用一个链表和顺序表构建城市数据库 提交文档组号： 2 四号宋体编程学生姓名及学号： 四号宋体测试学生姓名及学号： 四号宋体报告学生姓名及学号： 四号宋体指导 教 师 姓 名： 四号宋体指导教师评阅成绩： 四号宋体，按百分制给分指导教师评阅意见： . . 四号宋体提交报告时间： 2013 年 11 月 日实验一:Implement a city database using unordered lists and link lists1. 实验的目的和要求:采用C+的ASCII码文件和模块函数实现; 熟练掌握数组列表和链表列表的实现; 熟练掌握计算机系
2、统的基本操作方法，了解如何编译、运行一个C+程序; 上机调试程序,掌握查错、排错使程序能正确运行。2. 实验的环境: 1、硬件环境：索尼笔记本电脑，Intel(R) Core(TM) i7-3632M ，8GB内存可； 2、软件环境：Windows 8 下的Microsoft Visual Studio 20082. 算法描述: 数据结构与算法分析的背景： 数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课称，而且已成为其他理工专业的热门选修课。 数据结构是一门专业选技术基础科。一方面，它要求我们学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构
3、、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术；另一方面，数据结构的学习过程也是复杂程序设计的训练过程，要求我们编写的程序结构清楚和正确易读，复合软件工程的规范，并培养我们的数据抽象能力。本次课程设计就是对数据结构中的顺序表和链表的操作的应用。顺序表：1 顺序表的定义 (1) 顺序存储方法 即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。(2) 顺序表（Sequential List） 用顺序存储方法存储的线性表简称为顺序表（Sequential List）。2 结点ai 的存储地址 不失一般性，设线性表中所有结点的类型相同，则每个结点所占用存储空间大小
4、亦相同。假设表中每个结点占用c个存储单元，其中第一个单元的存储地址则是该结点的存储地址，并设表中开始结点a1的存储地址（简称为基地址）是LOC（a1），那么结点ai的存储地址LOC（ai）可通过下式计算： LOC（ai）= LOC（a1）+（i-1）*c 1in 注意： 在顺序表中，每个结点ai的存储地址是该结点在表中的位置i的线性函数。只要知道基地址和每个结点的大小，就可在相同时间内求出任一结点的存储地址。是一种随机存取结构。顺序表上实现的基本运算:表的初始化;求表长;取表中第i个结点;查找值为x的结点;插入（1） 插入运算的逻辑描述线性表的插入运算是指在表的第i（1in+1）个位置上，插入
5、一个新结点x，使长度为n的线性表： （a1，ai-1，ai，an）变成长度为n+1的线性表：（a1，ai-1，x，ai，an）注意： 由于向量空间大小在声明时确定，当L-lengthList Size时，表空间已满，不可再做插入操作； 当插入位置i的值为in或i1时为非法位置，不可做正常插入操作；（2） 顺序表插入操作过程在顺序表中，结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将表中位置为n ，n-1，i上的结点，依次后移到位置n+1，n，i+1上，空出第i个位置，然后在该位置上插入新结点x。仅当插入位置i=n+1时，才无须移动结点，直接将x插入表的末尾。（4）算法分析 问题的规模 表
6、的长度L-length（设值为n）是问题的规模。 移动结点的次数由表长n和插入位置i决定 算法的时间主要花费在for循环中的结点后移语句上。该语句的执行次数是n-i+1。 当i=n+1：移动结点次数为0，即算法在最好时间复杂度是0(1) 当i=1：移动结点次数为n，即算法在最坏情况下时间复杂度是0(n) 移动结点的平均次数Eis(n) 链表： 1：一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。2：链表最基本的结构是在每个节点保存数据和到下一个节点的地址，在最后一个节点保存一个特殊的结束标记，另外在一个固定的位
7、置保存指向第一个节点的指针，有的时候也会同时储存指向最后一个节点的指针。一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。但是也可以提前把一个节点的位置另外保存起来，然后直接访问。当然如果只是访问数据就没必要了，不如在链表上储存指向实际数据的指针。这样一般是为了访问链表中的下一个或者前一个（需要储存反向的指针）节点。3：在链表描述中，集合中的元素都放在链表的节点中进行描述。链表中的节点不是一个数组元素，因此不能通过公式来映射定位某个元素。取而代之的是，每个节点中都包含了下一个节点的位置信息，链表的表头包含了第一个节点的位置信息。 4.1：为了在集合中找到第k个
8、元素，就必须从表头开始，遍历第1个到第k个节点。它的时间复杂度是O(k)，平均时间复杂度为O(length)。 4.2：为了在集合中删除第k个元素，就要先找到第k-1和第k个节点，使第k-1个节点的下一个节点位置信息指向第k+1个节点，然后释放第k个节点所占的空间。它的时间复杂度是O(k)，平均时间复杂度为O(length)。 4.3：插入和删除的过程很相似，首先要创建一个新的节点，然后找到第k-1个节点，在该节点的后面插入新的节点，并把第k-1个节点、新的节点的下一个节点位置信息进行适当设置。它的时间复杂度是O(k)，平均时间复杂度为O(length)。 5：采用数组描述方法的集合仅需要能够
9、保存所有元素的空间以及保存集合最大尺寸所需要的空间。链表描述需要除集合元素本身的空间意外，还需要额外的空间，用例保存链接节点指向下一个节点位置的指针。但一般情况下，链表描述要比数值描述的空间利用率高得多。 6：虽然数组描述、链表描述插入和删除操作的平均时间复杂度均为O(length)，但由于移动元素的操作比遍历元素的操作的开销要大得多，所以采用链表描述所实现的插入和删除操作要比数组描述执行得更快。而采用数组描述可以在常数时间内访问第k个元素，而在链表中，这种操作所需要的时间是O(k)。单链表：void CreateList(LinkList &L) void ClearList(LinkLis
10、t &L)void Destroy(LinkList &L)bool GetElem(LinkList &L,int i,CityData &e)int LocateElem(LinkList &L,CityData e, bool (*compare)(CityData, CityData) bool ListInsert(LinkList &L,int i,CityData e)void ListDelete_Name(LinkList &L,string name,CityData &e)void ListTraverse(LinkList L)void ListReadFile(Lin
11、kList &L)void Preserve(LinkList L)顺序表：Switch语句，case语句；ListInsert_Sq(L, 1, GetCityData();ListDelete_Name(L, GetName(), citydata);ListDelete_Coordinate(L, x, y, citydata);ListSearch_Name(L, GetName(), citydata);ListSearch_Coordinate(L, X, Y, citydata);Print(L, GetY(), GetX(), GetDistance();城市数据系统系统l 程
12、序流程图 随机生成数据保存数据记录读取已保存记录u打印所有数据按指定距离打印按坐标查找城市按名字查找城市按坐标删除记录按名字删除数据插入城市数据 数据长度城市名称保存记录读取记录打印指定距离城市坐标城市名称城市坐标城市名称城市坐标删除成功无此记录查找成功无此记录查找成功插入成功无此记录删除成功无此记录输出3. 源程序清单:各产品过程检验的检验时机应在操作者对首件加工完成后自检，并判定合格。再由车间依据计划将需进行专检的部件填写报检单报检，在报检后首先由检验人员应检查车间是否按程序文件的规定开展了自检，然后接受报检进行检验、记录及判定。/顺序表实现城市数据库#include #include #
13、include stdlib.h#include #include using namespace std;#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define ElemType stringtypedef structElemType m_Name;int m_X;int m_Y;CityData;typedef structCityData *elem;int length;/当前表长int listsize;/表总长，初始为100SqList;void InitList_Sq(SqList &L)L.elem = new CityDataLIST_INIT_SIZE;if(!L.elem)exit(0);L.length = 0;L.listsize = LIST_INIT_SIZE;
