基于链式存储结构的线性表实现

Proditio

发布日期: 2019-02-27 22:44:13 浏览量: 1136
评分:
star star star star star star star star star star
*转载请注明来自write-bug.com

1 问题描述

线性表是由n(n≥0)个数据元素(结点)a[0],a[1],a[2],…,a[n-1]组成的有限序列。本实验的目的是封装一个基于顺序存储结构的线性表ADT,提供线性表基本的、常用的12中运算和操作。要求中还有关于文件I/O的细节需要实现,使得线性表可以实现内外存交换,便于数据读写。同时,需要实现一个演示系统实现简单的演示,以此作为可用性检查的工具。

2 系统设计

2.1 总体系统

该线性表的实现包括一个.CPP文件。文件中定义了线性表的结构体、相关运算的函数定义及其实现、测试系统、多表管理、文件操作等函数。由于整个线性表比较简单,而且没有“#include”的需要,因此没有使用头文件。

2.2 数据结构

数据结构的实现根据实验要求的ADT定义,定义了基于C语言结构体的ADT定义。由于实验要求给出的代码的Codebase是经典的C语言面向过程的写法,没有使用C++的类。为了提高可复用性和聚合度,使用C++的模板。结构体如下:

  1. template <typename T>
  2. struct Node {
  3. T data;
  4. Node* next;
  5. };
  6. template <typename T>
  7. struct LinkedList {
  8. int length;
  9. bool init;
  10. Node<T>* head;
  11. };

2.3 ADT操作的设计

根据实验的要求以及线性表ADT的定义,该线性表ADT应包括如下的操作:

  • InitList(初始化)

  • DestroyList(销毁)

  • ClearList(清空)

  • ListEmpty(判断表是否为空)

  • ListLength(求表长)

  • GetElem(按下标取得元素)

  • LocateElem(按满足关系取得元素)

  • PriorElem(返回满足关系的元素的前驱)

  • NextElem(返回满足关系元素的后继)

  • ListInsert(插入元素)

  • ListDelete(删除元素)

  • ListTraverse(遍历表)

为了便于错误处理,定义以下常量作为错误标识:

  1. #define TRUE 1
  2. #define FALSE 0
  3. #define OK 1
  4. #define ERROR 0
  5. #define INFEASTABLE -1
  6. #define OVERFLOW -2

为了方便更改线性表中元素的类型,使用以下的宏定义:

  1. typedef int status;
  2. typedef int ElemType;

其中,status是某个方法的返回类型,用于标志是否正确执行了相应的运算。Status的取值由上面的宏定义定义。当不为1时,认为发生了错误。然后可以根据status的值确定发生了何种错误。

ADT的运算有下面的函数定义,这些函数均返回status(如果不返回其他有用的值)、bool(判断是否为空)和size_t(求出长度或者位置):

  1. status InitList(LinkedList<T>&);
  2. status DestroyList(LinkedList<T>&);
  3. status ClearList(LinkedList<T>&);
  4. bool ListEmpty(LinkedList<T>);
  5. size_t ListLength(LinkedList<T>);
  6. status GetElem(LinkedList<T>, size_t i, ElemType& e);
  7. size_t LocateElem(LinkedList<T>, ElemType e);
  8. status PriorElem(LinkedList<T>, ElemType cur, ElemType& pre_e);
  9. status NextElem(LinkedList<T>, ElemType cur, ElemType& next_e);
  10. status ListInsert(LinkedList<T>&, size_t i, ElemType e);
  11. status ListDelete(LinkedList<T>&, size_t i, ElemType& e);
  12. status ListTraverse(LinkedList<T>);

上面的ListTraverse经过了简化,使得其遍历行为变为固定的打印。这一点使线性表的遍历失去了灵活性。这是一个可以优化和改善的点。

2.4 多表系统的设计

使用C++ STL的Vector作为多表的容器。使用容器可以简化相关的操作,同时具有很高的健壮性,也可以减少问题。

具体的思路为:在程序开始的时候创建一个vector,将第一个默认的LinkedList添加到里面,同时设置一个索引变量,用于指示线性表在vector中的位置。在运行的时候,每当用户选择新建一个线性表的时候,就将一个线性表添加到里面。同时将当前的线性表索引指向新的线性表。

容器的定义如:

  1. vector<LinkedList<T>> Lists = {LinkedList<T>()};

2.5 文件存储系统设计

文件操作可以使线性表的元素存放到硬盘上永久保存,更加贴近真实的使用场景。通过C语言标准库提供的文件读写API,可以很方便的操作文件。

通过fopen可以返回一个指针,该指针可以用来操作先前打开的文件。同时可以制定打开文件的方式,例如“r”可以用来打开一个只读文件。然后使用此文件进行读写操作,最后使用fclose销毁该指针。在写文件的时候,可以将整个elems数组以2进制的方式存入文件。在读取的时候,连续读取每次读取sizeof(T)个字节,然后将这些字节强制类型转换为T,然后使用ListInsert将其插入到线性表的尾部,直到读取到文件尾为止。

3 系统实现

3.1 开发环境

开发环境选用Windows 10上的VSCode作为编辑器,g++作为编译器,g++的版本为8.1.0。

3.2 ADT操作的实现

  • status InitList(LinkedList<T>&);

    • 该操作接受一个LinkedList<T>的引用,将其作为初始化对象进行初始化。首先,先要检查该线性表是否存在,如果存在,则将其长度设为0,将init设置为true,将head指向一个Node<T>的结构体,该结构体作为头节点。完成初始化,则返回status中的OK,否则返回相应的错误类型
    • 该操作的时间复杂度O(1),空间复杂度O(1)
  • status DestroyList(LinkedList<T>&);

    • 该操作用于销毁一个线性表。该函数接受一个LinkedList<T>的引用,将其head所指向的内存delete,然后沿着链表的next,delete所有的内存,由于C++中有构造函数和析构函数的概念,因此这里只能使用delete。将头节点的head指针置为0;同时,将该线性表设置为已销毁。如果成功,则返回status中的OK,否则返回相应的错误类型
    • 该操作的时间复杂度为O(n),空间复杂度为O(1)
  • status ClearList(LinkedList<T>&);

    • 该操作用于将一个线性表LinkedList<T>清空。该函数接受一个LinkedList<T>的引用,如果LinkedList<T>没有被初始化,则直接返回。否则将size设为0,然后沿着链表的next,将所有的Node<T>都delete掉。如果成功,则返回status中的OK,否则返回相应的错误类型
    • 该操作的时间复杂度是O(n),空间复杂度O(1)
  • bool ListEmpty(LinkedList<T>);

    • 该操作用于判断一个线性表是否为空,返回值为bool类型,当为真时说明线性表为空,否则说明线性表存在元素。如果某线性表未经初始化,那么他一定为空
    • 该操作的时间复杂度是O(1),空间复杂度O(1)
  • size_t ListLength(LinkedList<T>);

    • 该操作用于求取一个线性表的长度(实际包含元素的长度)。对于一个已经初始化的线性表,直接返回size的值。其他情况下则返回 -1(会被隐式类型转换为MAX_LONG_LONG_INT)
    • 该操作的时间复杂度是O(1),空间复杂度O(1)
  • status GetElem(LinkedList<T>, size_t i, ElemType& e);

    • 该操作用于获取线性表中的某一个元素。接受3个参数,第一个为线性表的拷贝,第二个为要获取的线性表所在的位置,第三个为变量的引用。获取元素需要从链表的一端向后遍历,知道找到相应下标的元素。获取成功的元素的值将被存放到这个变量中。如果该操作正常执行,则返回status中的OK,否则返回相应的错误
    • 该操作的时间复杂度是O(n),空间复杂度O(1)
  • size_t LocateElem(LinkedList<T>, ElemType e);

    • 该函数接受两个参数,一个是线性表的复制。一个是要定位的元素的值。该操作用于求取给定的e在线性表中的位置,可以实现为返回从左到右第一次出现的位置,位置从零开始,-1表示未找到。该函数的实现为遍历该线性表,当第一次遇到和e相等的元素时,则返回当前的循环变量
    • 该操作的时间复杂度是O(n),空间复杂度O(1)
  • status PriorElem(LinkedList<T>, T cur, T& pre_e);

    • 该操作接收三个参数:一个LinkedList<T>的拷贝、一个T的变量cur、一个T的引用pre_e,找到和cur变量相等的元素的前驱(如果存在),并且将pre_e赋值为它,否则操作失败,pre_e无定义。该操作首先判断表是否存在,如果存在则依次遍历整个线性表,判断线性表中的每个元素是否与传入的cur_e变量相等,如果满足则直接结束遍历,并且将pre_e赋值为该元素的前驱。如果成功,则返回status中的OK,否则返回相应的错误类型
    • 该操作的时间复杂度是O(n),空间复杂度是O(1)
  • status NextElem(LinkedList<T>, T cur, T& next_e);

    • 该操作接收三个参数:一个LinkedList<T>的拷贝、一个T的变量cur、一个T的引用next_e,找到和cur变量相等的元素的前驱(如果存在),并且将next_e赋值为它,否则操作失败,next_e无定义。该操作首先判断表是否存在,如果存在则依次遍历整个线性表,判断线性表中的每个元素是否与传入的cur_e变量相等,如果满足则直接结束遍历,并且将pre_e赋值为该元素的前驱。如果成功,则返回status中的OK,否则返回相应的错误类型
    • 该操作的时间复杂度是O(n),空间复杂度是O(1)
  • status ListInsert(LinkedList<T>&, size_t i, T e);

    • 该操作接收三个参数:一个LinkedList<T>的拷贝、一个size_t的变量i、一个T的变量e。用于将e元素插入到位于i位置的元素之前。该操作利用链表的特点,直接使用PriorElem获取到相应的元素的前驱结点,然后修改它前驱节点的next,以完成插入
    • 该操作的时间复杂度是O(n),空间复杂度是O(1)
  • status ListDelete(LinkedList<T>&, size_t i, ElemType& e);

    • 该操作接收三个参数:一个LinkedList<T>的拷贝、一个size_t的变量i、一个ElemType的引用e。该操作利用链表的特点,直接使用PriorElem获取到相应的元素的前驱结点,然后修改它前驱节点的next,修改为该前驱节点的下一节点的下一节点,以完成删除
    • 该操作的时间复杂度是O(n),空间复杂度是O(1)
  • status ListTraverse(LinkedList<T>, function<void(Node<T>)> cb);

    • 该操作接收一个LinkedList<T>拷贝和一个cb回调函数。依次对线性表中的每个元素执行cb函数指定的操作。该操作首先检查表是否存在、是否为空,存在且非空的话,则循环遍历整个线性表,并且对每个元素执行cb函数指定操作
    • 该操作的时间复杂度是O(n),空间复杂度是O(1)

3.3 多表系统的实现

多表系统实现了添加一张表、更改当前表两个操作(没有实现删除表)。

添加一张表

添加一张表就等价于在vector<LinkedList<T>>中添加了一个LinkedList<T>,该LinkedList<T>的所有字段都是按照默认初始化进行初始化的。因此,该线性表虽然有了内存空间但是却是一个空表,其size以及elems等关键字段都是无效的值。

更改当前表

更改当前表就等价于修改了指向vector<LinkedList<T>>的下标。该下标的取值为0至vector<LinkedList<T>>的长度。修改下标即可实现修改当前表所指向的值。从而达到修改当前表的目的。

容易可得,这两个操作的时间复杂度都为O(1)。

3.4 文件存储系统实现

通过fopen可以返回一个指针,该指针可以用来操作先前打开的文件。同时可以制定打开文件的方式,例如“r”可以用来打开一个只读文件。然后使用此文件进行读写操作,最后使用fclose销毁该指针。在写文件的时候,可以将整个elems数组以2进制的方式存入文件。在读取的时候,连续读取每次读取sizeof(T)个字节,然后将这些字节拷贝到elems里面,直到读取到文件尾为止。同时,每次读取使线性表的长度增加1个长度。

4 系统测试

4.1 演示系统测试

演示系统测试如下图所示:

该演示系统操作简单,输入对应的数字并按下回车即可。输入1-17表明运行对应的功能,且相应操作的结果会被输出到屏幕上,输入0退出系统。

4.2 测试样例

使用有效的典型的测试样例可以有效的寻找系统的错误,同时可以提高测试的覆盖率,使测试更加全面.正确的测试样例可以有效地测试系统是否正确,而错误的测试样例则可以用来测试系统的健壮性.按照如下的操作流程即可完整的测试该系统:

  • 获取3元素的下标

  • 获取1000元素的下标,错误样例

  • 获取3元素的前驱

  • 获取1元素的前驱,错误样例

  • 获取3元素的后继

  • 获取5元素的后继,错误样例

  • 删除下标为1和1000的元素

  • 遍历线性表

  • 将线性表存入文件

  • 添加一个线性表

  • 切换到新添加的线性表1,并初始化

  • 从刚存储的文件中加载线性表

  • 遍历线性表

  • 删除下标为1的元素

  • 遍历线性表

  • 切换到旧的线性表0

  • 遍历线性表

4.2 测试结果

初始化一个线性表

由图可见,初始化线性表成功。

测试线性表的长度

线性表的长度为0,符合预期结果。

然后插入1~5的元素,如下图所示,依次在0位置插入5、4、3、2、1,即可实现插入1~5元素。

为了验证我们确实插入了1~5的元素,我们使用ListTraverse来验证:如果ListTraverse输出1 2 3 4 5,则说明该操作正确。完成操作之后的截图如下,可见,该操作是正确的。

此时,测试改线性表的长度,即使用ListLength操作,得到的输出如下,列表长度为5,该结果正确且符合预期。由此可得ListInsert、ListTraverse、ListLength可以正常执行操作。

接下来获取下标为3的元素,使用GetElem来实现该操作,输入了index(下标)3之后,按下回车即可获取改下标对应的值。

如图所示,使用GetElem获得下标为3的元素,输出的值为4,因为我们在线性表中存储了1、2、3、4、5,所以下标为三的元素为4,结果正确,符合预期。如下图所示:

为了测试该系统的鲁棒性,测试获取下标为1000的元素时,该操作的行为。由于线性表中只有5个元素,因此获取下标为1000的元素直接报错。通过该测试可知该操作具有很好的容错机制。

为了测试3元素的下标,我们使用LocateElem操作,对3元素进行定位,根据前面的描述,该操作接受某元素的拷贝为参数,返回从左到右第一次出现该元素的下标,该下标从0开始。测试过程如下:

如上图所示,先后测试元素3和1000为参数的LocateElem,由于3的下标是2,因此程序输出2,结果正确且符合预期。1000不在线性表中,因此该值的下标输出为“未能找到!”,以此提醒使用者该操作无效。由截图可见,LocateElem的行为完全正确。

为了测试PriorElem的正确性,使用1和3为参数进行测试,由于元素1实际上没有前驱,因此该操作应该输出错误信息。而3的前驱为2,我们应该期望对于3进行获取前驱操作应当输出2。

如上图所示,该操作输出了正确的信息,因此可以认为PriorElem的行为是正确的。

为了测试NextElem的正确性,使用3和5为参数进行测试,由于元素5实际上没有后继,因此该操作应该输出错误信息。而3的后继为4,我们应该期望对于3进行获取前驱操作应当输出4。

如上图所示,该操作输出了正确的信息,因此可以认为NextElem的行为是正确的。

为了测试删除元素操作ListDelete的正确性,使用1和1000作为参数进行测试,将1和1000作为参数传递给ListDelete,由于下标为1的元素为2,因此执行完ListDelete(1)之后,线性表中的元素应为1、3、4、5;由于1000下标的元素不存在与线性表中,因此该操作将输出错误。

如上图可知,该操作的输出符合预期,因此可以认为该操作对应的程序无错误。为了进一步确认ListDelete对线性表的修改,使用ListTraverse来进行进一步测试,通过判断ListTraverse的输出值,查看执行ListDelete之后线性表的内容。

为了测试文件操作的可行性,使用WriteList操作。输入一个随意的文件名,例如2进行测试,文件将会被打开然后,程序将会将数据写入到打开的文件中,如果文件打开失败,会输出“File open error”。

如图所示,文件成功创建。为了验证文件内容的正确性,新建一个SqList并将该文件导入,即可检测该功能的正确性。依次进行AddList、ChangeList、InitList等操作,即可创建、切换并初始化一个新的线性表。然后运行ListTraverse操作,即可得到改线性表的所有元素。可见,这些元素和之前的线性表完全一致。

为了证明该线性表和之前的线性表不是同一个线性表,修改新的线性表并删除一个元素,为了方便演示,删除下标为1的元素。可见,下标为1的元素被成功删除,由于删除之前该线性表存储的元素是1、3、4、5,删除下标为1的元素导致线性表变为1、4、5。

由上图可知,遍历的结果和预期吻合,所以改线性表的文件操作无错误。而我们的目的是验证新的线性表不会影响旧的线性表,因此我们切换到之前的线性表,并执行遍历操作。

可见,当前的线性表是线性表0,也就是之前的旧的线性表。在该线性表上执行ListTraverse操作,即可获取所有的元素。由下图可见,所有的元素均列出,同时,没有出现和新线性表保持同步的现象,这说明在多表的情况下,线性表操作是独立的,不会互相影响。

5 实验小结

通过本次实验,我加深了对于基于链表数据结构的线性表的认识和了解。

在这次实验中,我使用C语言的风格封装了一个可以使用的线性表,同时,为了使该系统的可复用性提高,使用了C++的模板来实现了泛型。这次实验我知道了如何实现一个线性表,将课本的知识转化为可以使用的程序,同时我对C语言的错误处理、面向过程的编程有了更深的理解。通过对测试系统的实现,我学会了如何全面的测试我的程序,也知道了如何提高系统的鲁棒性。

上传的附件 cloud_download 基于链式存储结构的线性表实现.zip ( 565.29kb, 43次下载 )
error_outline 下载需要8点积分

发送私信

不慌不忙,我们来日方长

8
文章数
6
评论数
最近文章
eject