【数据结构作业】2024.09.19 顺序表的实现
本文最后更新于82 天前,其中的信息可能已经过时,如有错误请发送邮件到727189340@qq.com

2024.09.19 顺序表的实现

T1

题目描述

请按照 PPT、课本给的例子,给出顺序表的数据结构定义、实现顺序表的基本操作:

  • 初始化 InitList(&L)
  • 释放 DestroyList(&L)
  • 置空 ClearList(&L)
  • 遍历 ListTraverse(L)
  • 取值 GetElem(L,i,&e)
  • 查找 LocateElem(L,e)
  • 插入 ListInsert(&L, i, e)
  • 删除 ListDelete(&L, i, &e)
  • 求表长 ListLength(L)
  • 判断表是否为空 ListEmpty(L)

main 函数一一测试这些操作。main 中:

  1. 声明一个顺序表,初始化
  2. 在该顺序表中插入$1,2,3,4,5$,每次均在编号 $1$(位序)处
  3. 遍历
  4. 在编号 $6$ 插入 $6$
  5. 分别查找并打印 $5,6,2$ 这三个元素及其位置
  6. 在编号 $2$ 插入 $7,8,9,10,11$
  7. 遍历
  8. 删除第一个位置的元素,并打印该元素
  9. 删除第一个位置的元素,并打印该元素
  10. 遍历
  11. 删除编号为 $9$ 的元素,并打印该元素,打印此时顺序表长度
  12. 遍历
  13. 清空顺序表并打印顺序表长度
  14. 在第 $2$ 编号处插入 $10$,结果插入成功,打印 “成功插入”,否则打印 “插入不成功”
  15. 依次插入 $1,2,3,4,5$,每次均在最后一个结点的后一个位置处
  16. 遍历
  17. 销毁顺序表

参考作答

  1. 本代码由于使用了模板函数,故定义和实现文件必须合并,统一在 sequential_list.h 内。
  2. 本代码出于作者的习惯,所有的调用索引均从 $0$ 开始。

定义/实现文件 sequential_list.h

#ifndef SEQUENTIAL_LIST_H
#define SEQUENTIAL_LIST_H

#include <iostream>
#include <stdexcept>

// 顺序存储线性表类
template <typename T>
class seqList
{
private:
    T* data;         // 存储元素的数组
    size_t capacity; // 数组的容量
    size_t length;   // 当前元素的个数

    // 扩展数组容量
    void expandCapacity();

public:
    // 构造函数
    seqList(size_t initialCapacity = 10);

    // 析构函数
    ~seqList();

    // 重置表为空表
    void clear();

    // 判断是否为空表
    bool isEmpty() const;

    // 返回表内元素个数
    size_t size() const;

    // 返回某个位置元素的值
    T get(size_t index) const;

    // 返回第一个与某元素位置相同的元素的位置
    int find(const T& element) const;

    // 返回某元素的前驱
    T predecessor(const T& element) const;

    // 返回某元素的后继
    T successor(const T& element) const;

    // 在某个位置前插入某个元素
    void insert(size_t index, const T& element);

    // 删除某位置的元素
    void remove(size_t index);

    // 遍历表
    void traverse() const;
};

// 构造函数:初始化容量和长度
template <typename T>
seqList<T>::seqList(size_t initialCapacity) : capacity(initialCapacity), length(0)
{
    data = new T[capacity];
}

// 析构函数:释放动态分配的内存
template <typename T>
seqList<T>::~seqList()
{
    delete[] data;
}

// 扩展数组容量,使其变为两倍
template <typename T>
void seqList<T>::expandCapacity()
{
    capacity *= 2;
    T* newData = new T[capacity];
    for (size_t i = 0; i < length; ++i)
        newData[i] = data[i];
    delete[] data;
    data = newData;
}

// 重置表为空表
template <typename T>
void seqList<T>::clear()
{
    length = 0;
}

// 判断是否为空表
template <typename T>
bool seqList<T>::isEmpty() const
{
    return length == 0;
}

// 返回表内元素个数
template <typename T>
size_t seqList<T>::size() const
{
    return length;
}

// 返回某个位置元素的值
template <typename T>
T seqList<T>::get(size_t index) const
{
    if (index >= length || index < 0)
        throw std::out_of_range("索引非法");
    return data[index];
}

// 返回第一个与某元素相同的元素的位置
template <typename T>
int seqList<T>::find(const T& element) const
{
    for (size_t i = 0; i < length; ++i)
        if (data[i] == element)
            return i;
    return -1;
}

// 返回某元素的前驱
template <typename T>
T seqList<T>::predecessor(const T& element) const
{
    int index = find(element);
    if (index <= 0)
        throw std::invalid_argument("该元素不存在或该元素无前驱");
    return data[index - 1];
}

// 返回某元素的后继
template <typename T>
T seqList<T>::successor(const T& element) const
{
    int index = find(element);
    if (index == -1 || index >= length - 1)
        throw std::invalid_argument("该元素不存在或该元素无后继");
    return data[index + 1];
}

// 在某个位置前插入某个元素
template <typename T>
void seqList<T>::insert(size_t index, const T& element)
{
    if (index > length || index < 0)
        throw std::out_of_range("索引非法");
    if (length == capacity)
        expandCapacity();
    for (size_t i = length; i > index; --i)
        data[i] = data[i - 1];
    data[index] = element;
    length++;
}

// 删除某个元素
template <typename T>
void seqList<T>::remove(size_t index)
{
    if (index < 0 || index >= length)
        throw std::out_of_range("索引非法");
    for (size_t i = index + 1; i < length; i++)
        data[i - 1] = data[i];
    length--;
}

// 遍历表
template <typename T>
void seqList<T>::traverse() const
{
    for (size_t i = 0; i < length; ++i)
        std::cout << data[i] << " ";
    std::cout << std::endl;
}

#endif // SEQUENTIAL_LIST_H

主函数 main.cpp

#include "sequential_list.h"
#include <iostream>

using namespace std;

int main()
{ // 1. 声明一个顺序表,初始化
    seqList<int> list;

    // 2. 在该顺序表中插入1,2,3,4,5,每次均在编号 1(位序)处
    for (int i = 1; i <= 5; i++)
        list.insert(0, i);

    // 3. 遍历
    list.traverse();

    // 4. 在编号 6 插入 6
    list.insert(5, 6);

    // 5. 分别查找并打印 5,6,2 这三个元素及其位置
    cout << "元素 5 的位置是:" << list.find(5) + 1 << endl;
    cout << "元素 6 的位置是:" << list.find(6) + 1 << endl;
    cout << "元素 2 的位置是:" << list.find(2) + 1 << endl;

    // 6. 在编号 2 插入 7,8,9,10,11
    for (int i = 7; i <= 11; i++)
        list.insert(1, i);

    // 7. 遍历
    list.traverse();

    // 8. 删除第一个位置的元素,并打印该元素
    cout << "第一个位置的元素是:" << list.get(0) << ",删除成功" << endl;
    list.remove(0);

    // 9. 删除第一个位置的元素,并打印该元素
    cout << "第一个位置的元素是:" << list.get(0) << ",删除成功" << endl;
    list.remove(0);

    // 10. 遍历
    list.traverse();

    // 11. 删除编号为 9 的元素,并打印该元素,打印此时顺序表长度
    cout << "编号为 9 的元素是:" << list.get(8) << ",删除成功" << endl;
    list.remove(8);
    cout << "当前顺序表的长度是:" << list.size() << endl;

    // 12. 遍历
    list.traverse();

    // 13. 清空顺序表并打印顺序表长度
    list.clear();
    cout << "当前顺序表的长度是:" << list.size() << endl;

    // 14. 在第 2 编号处插入 10,结果插入成功,打印“成功插入”,否则打印“插入不成功”
    try
    {
        list.insert(1, 10);
        cout << "成功插入" << endl;
    }
    catch (const std::out_of_range& e)
    {
        cout << "插入不成功" << endl;
    }

    // 15. 依次插入 1, 2, 3, 4, 5,每次均在最后一个结点的后一个位置处
    for (int i = 1; i <= 5; i++)
        list.insert(list.size(), i);

    // 16. 遍历
    list.traverse();

    // 17. 销毁顺序表
    return 0; // (自动调用析构函数)
}

输出

5 4 3 2 1
元素 5 的位置是:1
元素 6 的位置是:6
元素 2 的位置是:4
5 11 10 9 8 7 4 3 2 1 6
第一个位置的元素是:5,删除成功
第一个位置的元素是:11,删除成功
10 9 8 7 4 3 2 1 6
编号为 9 的元素是:6,删除成功
当前顺序表的长度是:8
10 9 8 7 4 3 2 1
当前顺序表的长度是:0
插入不成功
1 2 3 4 5

T2

题目描述

简答题

请分析以下顺序表操作的算法,回答相应的问题:

  1. 遍历 ListTraverse(L) 的时间复杂度是?
  2. 初始化 InitList(&L) 和释放 DestroyList(&L) 的时间复杂度是?
  3. 取值 GetElem(L,i,&e) 的时间复杂度是?
  4. 查找 LocateElem(L,e) 的比较次数?时间复杂度是?
  5. 插入 ListInsert(&L,i,e) 主要时间耗费在哪里?时间复杂度是?
  6. 删除 ListDelete(&L,i,&e) 主要时间耗费在哪里?时间复杂度是?

参考作答

本文中所有涉及到函数的部分,均使用作者类定义/实现文件 sequential_list.h 中对应功能的函数代替

遍历 ListTraverse(L) 时间复杂度

遍历代码

// 遍历表
template <typename T>
void seqList<T>::traverse() const
{
    for (size_t i = 0; i < length; ++i)
        std::cout << data[i] << " ";
    std::cout << std::endl;
}

可见具有一个从 0length-1for 循环,其时间复杂度应为 $O(N)$.

初始化 InitList(&L) 和释放 DestroyList(&L) 时间复杂度是

初始化代码

// 构造函数:初始化容量和长度
template <typename T>
seqList<T>::seqList(size_t initialCapacity) : capacity(initialCapacity), length(0)
{
    data = new T[capacity];
}

释放代码

// 析构函数:释放动态分配的内存
template <typename T>
seqList<T>::~seqList()
{
    delete[] data;
}

可见与输入无关,时间复杂度为 $O(1)$.

取值 GetElem(L,i,&e) 的时间复杂度

取值代码

// 返回某个位置元素的值
template <typename T>
T seqList<T>::get(size_t index) const
{
    if (index >= length || index < 0)
        throw std::out_of_range("索引非法");
    return data[index];
}

可见与输入无关,时间复杂度为 $O(1)$。补充的,顺序表/数组可以实现随机访问,佐证其时间复杂度为 $O(1)$。

查找 LocateElem(L,e) 的比较次数与时间复杂度

查找代码

// 返回第一个与某元素相同的元素的位置
template <typename T>
int seqList<T>::find(const T &element) const
{
    for (size_t i = 0; i < length; ++i)
        if (data[i] == element)
            return i;
    return -1;
}

显然,可以分为:

情况描述比较次数时间复杂度
查找成功,最好情况查找的元素就在第一位$1$$O(1)$
查找成功,最坏情况查找的元素在最后一位$n$$O(N)$
查找成功,平均情况$\dfrac{n}{2}$$O(N)$
查找失败遍历整张表都没有找到该元素$n$$O(N)$

插入 ListInsert(&L,i,e) 主要时间耗费和时间复杂度

插入代码

// 在某个位置前插入某个元素
template <typename T>
void seqList<T>::insert(size_t index, const T &element)
{
    if (index > length || index < 0)
        throw std::out_of_range("索引非法");
    if (length == capacity)
        expandCapacity();
    for (size_t i = length; i > index; --i)
        data[i] = data[i - 1];
    data[index] = element;
    length++;
}

可见,其主要时间耗费是在

for (size_t i = length; i > index; --i)
        data[i] = data[i - 1];

此时是插入元素之后,将该位置元素后的所有元素整体向后移动一位。其时间复杂度为 $O(N)$。

删除 ListDelete(&L,i,&e) 主要时间耗费和时间复杂度

删除代码

// 删除某个元素
template <typename T>
void seqList<T>::remove(size_t index)
{
    if (index < 0 || index >= length)
        throw std::out_of_range("索引非法");
    for (size_t i = index + 1; i < length; i++)
        data[i - 1] = data[i];
    length--;
}

可见,其主要时间耗费是在

for (size_t i = index + 1; i < length; i++)
        data[i - 1] = data[i];

此时是删除元素之后,将该位置元素后的所有元素整体向前移动一位。其时间复杂度为 $O(N)$。

作者

觉得有帮助的话可以投喂煮啵,助力煮啵过上点外卖不用神卷的生活

本文作者:Flaw_Owl
看到这里的朋友们,作者十分感谢!如果你看到任何写得不清楚或是错误之处,或者是有什么希望看到的课程和内容笔记,欢迎在评论区留言!评论区可以单纯的发表文字,也可以使用 Markdown 语法,你可以参照 Markdown 官方教程发出带有格式的评论。

版权说明:本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0协议,转载请注明文章地址及作者哦
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇