線性表逆置實驗報告

課程設計題目：線性表逆置實驗

一、問題描述

試分別以順序表和單鏈表作存儲結構，各寫一實現(xiàn)線性表就地逆置的算法迟杂。

二、基本要求

逆置線性表本慕。
就地（空間復雜度至多 $O(1)$ ）排拷。

三、概要設計

1. 數(shù)據(jù)結構的設計

依題目要求间狂，本實驗采用順序表和單鏈表攻泼。

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;
}

時間復雜度	空間復雜度
$O(n)$	$O(1)$

對于單鏈表的逆置牛欢，我們使用按鏈表順序對 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;
    }
}

時間復雜度	空間復雜度
$O(n)$	$O(1)$

四淆游、詳細設計

1. 設計抽象數(shù)據(jù)類型對應的C++類定義

即常規(guī)的順序表和單鏈表傍睹，在此便不一一贅述了。

2. 設計每個成員函數(shù)

除上述void reverse()函數(shù)外犹菱，其余函數(shù)與常規(guī)的順序表和單鏈表中的無異拾稳，在此便不一一贅述了。

3. 設計主函數(shù)

主函數(shù)主要包括設計測試數(shù)據(jù)并測試腊脱，輸出逆置前和逆置后的結果访得。

五、運行與測試

1. 測試環(huán)境

運行環(huán)境：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. 在調試程序的過程中遇到的問題與解決方案

暫未發(fā)現(xiàn)異常陕凹。

3. 程序清單及運行結果

程序清單如下

順序表

#include <iostream>
using namespace std;

const int MaxSize = 10; //10只是示例性的數(shù)據(jù)悍抑，可以根據(jù)實際問題具體定義
struct SeqList
{
    SeqList() { length = 0; }
    SeqList(int a[], int n)
    {
        if (n > MaxSize)
            throw "參數(shù)非法";
        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;
}