线性表逆置实验报告

课程设计题目：线性表逆置实验

一、问题描述

试分别以顺序表和单链表作存储结构，各写一实现线性表就地逆置的算法。

二、基本要求

1. 逆置线性表。
2. 就地（空间复杂度至多）。

三、概要设计

1. 数据结构的设计

依题目要求，本实验采用顺序表和单链表。

2. 算法的设计

对于顺序表的逆置，我们使用两个指针i和j，分别从左到右和从右到左扫描，交换元素，直到相遇。

伪代码如下

void reverse() {
    for (int i = 0, j = length - 1, t; i < j; i++, j--)
        t = data[i], data[i] = data[j], data[j] = t;
}

时间复杂度	空间复杂度

对于单链表的逆置，我们使用按链表顺序对 Node 使用头插法。

伪代码如下

void reverse() {
    Node *p = first.next;
    first.next = NULL;
    for (; p;) {
        Node *s = p;
        p = s->next;
        s->next = first.next;
        first.next = s;
    }
}

时间复杂度	空间复杂度

四、详细设计

1. 设计抽象数据类型对应的C++类定义

即常规的顺序表和单链表，在此便不一一赘述了。

2. 设计每个成员函数

除上述void reverse()函数外，其余函数与常规的顺序表和单链表中的无异，在此便不一一赘述了。

3. 设计主函数

主函数主要包括设计测试数据并测试，输出逆置前和逆置后的结果。

五、运行与测试

1. 测试环境

运行环境：Windows 20H2, i7-9750H @ 2.60GHz, 16GB RAM

编译器：gcc version 8.1.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project)

编译命令：-g

运行终端：cmd

2. 在调试程序的过程中遇到的问题与解决方案

暂未发现异常。

3. 程序清单及运行结果

程序清单如下

顺序表

#include <iostream>
using namespace std;

const int MaxSize = 10; //10只是示例性的数据，可以根据实际问题具体定义
struct SeqList
{
    SeqList() { length = 0; }
    SeqList(int a[], int n)
    {
        if (n > MaxSize)
            throw "参数非法";
        for (int i = 0; i < n; i++)
            data[i] = a[i];
        length = n;
    }
    ~SeqList() {}

    void print()
    {
        for (int i = 0; i < length; i++)
            cout << data[i] << " ";
        cout << endl;
    }

    void reverse()
    {
        for (int i = 0, j = length - 1, t; i < j; i++, j--)
            t = data[i], data[i] = data[j], data[j] = t;
    }

    int data[MaxSize];
    int length;
};

int main()
{
    int a[] = {0, 1, 2, 3, 4, 5};
    SeqList l(a, 6);
    l.print();
    l.reverse();
    l.print();
    return 0;
}

运行结果（符合预期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week04\线性表逆置>SeqList.exe
0 1 2 3 4 5
5 4 3 2 1 0

单链表

#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node *next;
};

struct LinkList
{
    Node first = {-1, NULL};
    LinkList() {}
    LinkList(int a)
    {
        Node *s = new Node;
        *s = {a, NULL};
        first.next = s;
    }
    LinkList(int a[], int n)
    {
        Node *p = &first;
        for (int i = 0; i < n; i++)
        {
            Node *s = new Node;
            *s = {a[i], NULL};
            p->next = s;
            p = s;
        }
    }
    ~LinkList()
    {
        for (Node *p = first.next; p;)
        {
            Node *s = p;
            p = s->next;
            delete s;
        }
    }

    void print()
    {
        for (Node *p = first.next; p; p = p->next)
            cout << p->data << " ";
        cout << "\n";
    }

    void reverse()
    {
        Node *p = first.next;
        first.next = NULL;
        for (; p;)
        {
            Node *s = p;
            p = s->next;
            s->next = first.next;
            first.next = s;
        }
    }
};

int main()
{
    int a[] = {0, 1, 2, 3, 4, 5};
    LinkList l(a, 6);
    l.print();
    l.reverse();
    l.print();
    return 0;
}

运行结果（符合预期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week04\线性表逆置>LinkList.exe
0 1 2 3 4 5
5 4 3 2 1 0

六、总结与心得

1. 单链表的就地逆置算法，除了利用头插法外，还可以翻转指针，详见《数据机构(C++版)学习辅导与实验指导》P23的算法2-4。

七、参考资料

1. 王红梅, 胡明, 王涛. 数据结构(C++版)[M]. 2 版. 清华大学出版社, 2011.
2. 王红梅, 胡明, 王涛. 数据机构(C++版)学习辅导与实验指导[M]. 2 版. 清华大学出版社, 2011.