链表顺序表实验报告

1、链表顺序表实验报告构与算法分析-数据结数据结构与算法分析课程设计报告课题名称：使用一个链表和顺序表构建城市数据库提交文档组号：2编程学生姓名及学号： 测试学生姓名及学号： 报告学生姓名及学号： 指导教师姓名：指导教师评阅成绩：指导教师评阅意见：提交报告时间：2013 年11月 日1. 实验的目的和要求：采用C+啲ASCII码文件和模块函数实现； 熟练掌握数组列表和链表列表的实现； 熟练掌握计算机系统的基本操作方法，了解如何 编译、运行一个C+程序；上机调试程序，掌握查错、排错使程序能正确运 行。2. 实验的环境：1、硬件环境：索尼笔记本电脑，In tel(R) Core(TM) i7-3632

2、M，8GB 内存可；2、软件环境： Windows 8 下的 Microsoft Visual Studio 20082.算法描述：数据结构与算法分析的背景：数据结构是计算机程序设计的重要理论技术基 础，它不仅是计算机学科的核心课称，而且已成为 其他理工专业的热门选修课。数据结构是一门专业选技术基础科。一方面， 它要求我们学会分析研究计算机加工的数据结构的 特性，以便为应用涉及的数据选择适当的逻辑结构、 存储结构及其相应的算法，并初步掌握算法的时间 分析和空间分析的技术；另一方面，数据结构的学 习过程也是复杂程序设计的训练过程，要求我们编 写的程序结构清楚和正确易读，复合软件工程的规范，并培养

3、我们的数据抽象能力。本次课程设计就 是对数据结构中的顺序表和链表的操作的应用。 顺序表：1. 顺序表的定义(1) 顺序存储方法即把线性表的结点按逻辑次序依次存放在一 组地址连续的存储单元里的方法。(2) 顺序表(Sequential List )用顺序存储方法存储的线性表简称为顺序表(Sequential List )。2. 结点a的存储地址不失一般性，设线性表中所有结点的类型相 同，则每个结点所占用存储空间大小亦相同。假设 表中每个结点占用c个存储单元，其中第一个单元的 存储地址则是该结点的存储地址，并设表中开始结 点ai的存储地址(简称为基地址)是LOC(ai)，那么 结点a的存储地址LO

4、C(a)可通过下式计算：LOC (a) = LOC(ai) + (i-1 ) *c 1 i n注意：在顺序表中，每个结点a的存储地址是该结点 在表中的位置i的线性函数。只要知道基地址和每个 结点的大小，就可在相同时间内求出任一结点的存 储地址。是一种随机存取结构。顺序表上实现的基本运算：表的初始化；求表长;取表中第i个结点;查找值为x 的结点;插入(1) 插入运算的逻辑描述线性表的插入运算是指在表的第i ( K i length List Size 时，表空间已满，不可再做插入 操作； 当插入位置i的值为i n或i v1时为非法 位置，不可做正常插入操作；(2) 顺序表插入操作过程在顺序表中，

5、结点的物理顺序必须和结点的逻 辑顺序保持一致，因此必须将表中位置为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 o当i=n+1 :移动结点次数为0,即算法在最好时 间复杂度是0(1)当i=1 :移动结点次数为n,即算法在最坏情况 下时间复杂度是0(n) 移动结点的平均次

6、数Es(n)N +1恥)=护(-+1)链表：1 :一个单向链表的节点被分成两个部分。第一 个部分保存或者显示关于节点的信息，第二个部分 存储下一个节点的地址。单向链表只可向一个方向 遍历。2:链表最基本的结构是在每个节点保存数据和 到下一个节点的地址，在最后一个节点保存一个特 殊的结束标记，另外在一个固定的位置保存指向第 一个节点的指针，有的时候也会同时储存指向最后 一个节点的指针。一般查找一个节点的时候需要从 第一个节点开始每次访问下一个节点，一直访问到 需要的位置。但是也可以提前把一个节点的位置另 外保存起来，然后直接访问。当然如果只是访问数 据就没必要了，不如在链表上储存指向实际数据的

7、指针。这样一般是为了访问链表中的下一个或者前 一个(需要储存反向的指针)节点。3:在链表描述中，集合中的元素都放在链表的 节点中进行描述。链表中的节点不是一个数组元素， 因此不能通过公式来映射定位某个元素。取而代之 的是，每个节点中都包含了下一个节点的位置信息， 链表的表头包含了第一个节点的位置信息。4.1 :为了在集合中找到第k个元素，就必须从 表头开始，遍历第1个到第k个节点。它的时间复杂 度是0(k)，平均时间复杂度为O(length)。4.2 :为了在集合中删除第k个元素，就要先找 到第k-1和第k个节点，使第k-1个节点的下一个节 点位置信息指向第k+1个节点，然后释放第k个节点 所

8、占的空间。它的时间复杂度是 O(k)，平均时间复 杂度为 O(length)。4.3 :插入和删除的过程很相似，首先要创建一 个新的节点，然后找到第k-1个节点，在该节点的后 面插入新的节点，并把第k-1个节点、新的节点的下 一个节点位置信息进行适当设置。它的时间复杂度是O(k)，平均时间复杂度为 O(length)。5 :采用数组描述方法的集合仅需要能够保存所有元素的空间以及保存集合最大尺寸所需要的空 间。链表描述需要除集合元素本身的空间意外，还 需要额外的空间，用例保存链接节点指向下一个节 点位置的指针。但一般情况下，链表描述要比数值 描述的空间利用率高得多。6 :虽然数组描述、链表描述插

9、入和删除操作的 平均时间复杂度均为O(length)，但由于移动元素的 操作比遍历元素的操作的开销要大得多，所以采用 链表描述所实现的插入和删除操作要比数组描述执 行得更快。而采用数组描述可以在常数时间内访问 第k个元素，而在链表中，这种操作所需要的时间 是 O(k)。顺序表：Switch 语句，case 语句；List In sert_Sq(L,1,GetCityData(); ListDelete_Name(L ,GetName(),单链表：voidCreateList(Li nkList &L) voidClearList(L in kList &L) void Destroy(L in

10、 kList &L)bool GetElem(Li nkList3.源程序清单：/顺序表实现城市数据库#include #include #include stdlib.h#include #include int ListLength(SqList L)return Length;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 st

11、ructCityData *elem;int length;int listsize;100SqList;void InitList_Sq(SqList &L)L.elem = new CityDataLIST_INIT_SIZE; if(!L.elem) exit(0);Length = 0;L.listsize = LIST_INIT_SIZE;void DestroyList(SqList &L)Length = 0;L.listsize = 0;free(L.elem);L.elem = NULL;void ClearList(SqList &L)L.len gth = 0;bool

12、ListEmpty(SqList L)/当前表长/表总长，初始为/获取第i个元素(从1开始计数，下同)void GetElem(SqList L, int i, CityData &e)if(iL.length)cout错误的位置！ endl;return ;elsee = L.elemi-1;/查找节点e返回位置int LocateElem(SqList L, CityData e, bool(*compare)(CityData, CityData)CityData *p;p = L.elem;int i = 0;while(iL.length & !(compare(*p, e)p+;i

13、+;if(i =1 & i= L.li stsize)CityData *base;base = new CityDataL.listsize;for(i ntcoun t=0;coun tL .len gth;coun t+)return (L.length = 0)? false : true;&L.elem = new CityDataL.listsize + LISTINCREMENT;for(i nt n um=O; n umq; p-)*p = *(p-1);*q =e;Length+;cout插入成功endl;return;cout插入位置非法！ 0)CityData *p =

14、& (L.elem0);int count = 0;while(p-m_Name!=name&countLength)count+;p+;/之后将此元素后的元素依次向前移动一位， 下同if(co unt L.len gth)e = *p;CityData *q = L.elem + L.le ngth -1;for(; p=q; p+)*p = *(p+1);L.len gth-;cout删除成功endl;elsecout 0)CityData *p = & (L.elem0);int count = 0;while(p-m_X!=X &p-m_Y!=YcountL.len gth)coun

15、t+;p+;if(count Length)e = *p;CityData *q = L.elem + L.length -1; for(; p=q; p+)*p = *(p+1);L.length-;cout删除成功endl;elsecout数据库中没有该记录citydata.m_Namecitydata.m_Xc itydata.m_Y)ListInsert_Sq(L, 1, citydata);ifile.close();cout读取完毕 0)CityData *p = L.elem;int count = 0;while(p-m_Name!=name & count=X)?p+;L.e

16、lemi.m_X-X :X-L.elemi.m_X;inty=(L.elemi.m_Y=Y)?if(count Length)L.elemi.m_Y-Y :Y-L.elemi.m_Y;intDistance = x*x+y*y;e = *p；int d = dista nce*dista nee;if(Dista nce=d)cout城市名：”m_Nameendl;cout 坐标 X : m_Xe ndl; cout坐标 Y : m_Yendl;elsecout数据库中没有这个记录 0)CityData *p = L.elem;int count = 0;while(p-m_X!=X &p-m

17、_Y!=Y&coun tL .len gth)coun t+;p+;if(count Length)e = *p;cout城市名:m_Nameendl;cout 坐标 X : m_Xe ndl; cout坐标 Y : m_Yendl;elsecout数据库中没有这个记录e ndl;/打印到指定点距离小于distance的城市void Prin t(SqList L, i nt Y, i nt X, int dista nee)if(L.le ngth = 0)cout 城 市 名L.elemi.m_Namee ndl;cout坐 标XL.elemi.m_Xe ndl;cout坐标 Y : L.

18、elemi.m_Yendl;i+;/将表中城市信息保存到文件中(会清除文件中原有数据:void Preserve(SqList L)ofstream ofile;ofile.ope n(City.txt, ios_base:out);for(i nt i=0; iL .len gth; i+)ofileL.elemi.m_Name L.elemi.m_X L.elemi.m_Ye ndl;ofile.close();cout存档成功!endl;/打印出所有节点void ListTraverse(SqList L)if(L.le ngth = 0)cout空，你还没有读取记录，或者记录e ndl

19、;elsefor(i nt i=0; iL .len gth; i+):为空cout空，你还没有读取记录，或者记录为空 Lb、 ， 计算 出算 法的 时间1 I 丿 LJ、， 计算 出了 算法 的时 间6按指定点距离内显示记录按照规 定的距 离内显 示该距 离内的 数据输入6, 根据提 示输入距离5显示 该距 离内 的数 据显示 了该 距离 内的 数据通 过7显 示 所 有 城 市显示当 前所有 城市的 数据输入7显示 当前 所有 城市 的数 据显示 了当 前所 有城 市的 数据通 过的 数 据8读读取已输入8读取读取通取 已 保 存 的 城 市 的 数 据经存档 的所有 城市的 数据, 即刷

20、新 表中的 数据了存 档的 所有 数据了存 档的 所有 数据过9保 存存储数 据输入9存储 所有 所有 数据存储 了所 有数 据通 过0随 机 生 成随机生 成城市 名称和 坐标先输入 0,再根 据要求 输入产 生的长 度会随 机生 成相 应长 度的 数据输入 7，会 显示 出随 机产 生的 相应 长度通 过的数 据测试 结论各项功能已经基本实现，但其中有些 部分太过繁杂，可以简化一些，尤其 是进行下一项操作时，前面的操作会 消失，这会带来许多不便，需要改进备注：分为“通过”（实际输出与正确输出相符）、“ 改正”（实际输出与正确输出不符，但现在已修改正 确）、“待修改”（实际输出与正确输出不符

21、，且尚未 改正）三种状态。可在此说明错误原因这一部分需根据题目类型设计提供相应的测试 方法和结果（请勿粘贴测试结果图）。5.实验运行情况分析（包括算法、运行结果、运行环境等问题的总体讨论 ）。 算法分析比较：顺序表和链表的使用各有优劣。顺序表需要提前估计线性表的大小并且插入删除效率低需要移动大量结点，优点 在于表中节点没有浪费存储空间，并且可以按位置随机访问，存储速度快；链表优点在于插入删除效率高，无需提前估计表的大小（大小无需固定），表中元素个数没有限制，缺点在于访问结点需要从表头遍历查找并且每个节点除了储存元素 还需要附加空间存储指针。顺序表和链表时间性能比较：像取出线性表中第i个元素这样

22、的按位置随机访问的操作，使用顺序表更快一些；取前趋和后继结点的操作在顺序表中可以很容易调整 当前的位置向前或向后，因此这两种操作的时间为O （1）；相比之下，单链表不能直接访问上述的元素，按位置访问只能从表头开始，直到 找到那个特定的位置，所需要的平均时间为 O （ n ）。给出指向链表中某个合适位置 的指针后，插入和删除操作所需的时间仅为O （ 1 ），而顺序表进行插入和删除操作需移动近乎表长一半的元素，需要的平均时间为O （ n ）。这在线性表中元素个数较多时，特别是当每个元素占用的空间较多时，移动元素的时间开销很大。对于许多应用，插入和删除是最主要的操作，因此它们的时间效率是举足轻重的，仅就这个原 因而言，链表经常比顺序表更好。顺序表和链表空间性能比较：顺序表中每个元素的存储密度为1 ，没有浪费空间； 而链表的每个结点除了存放数据元素，还要附加一个指示元素之间逻辑关系的指针， 如果数据域占据的空间较小，贝U链表的结构性开销就占去了整个存储空间的大部分， 因而从结点的存储密度上讲，顺序表的存储空间利用率较高。由于顺序表需要预分配一定长度的存储空间，如果事先不能明确知道线性表的大 致长度，则有可能对存储空间预分配得过大，致使