本文最后更新于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,3,4,5$,每次均在编号 $1$(位序)处
- 遍历
- 在编号 $6$ 插入 $6$
- 分别查找并打印 $5,6,2$ 这三个元素及其位置
- 在编号 $2$ 插入 $7,8,9,10,11$
- 遍历
- 删除第一个位置的元素,并打印该元素
- 删除第一个位置的元素,并打印该元素
- 遍历
- 删除编号为 $9$ 的元素,并打印该元素,打印此时顺序表长度
- 遍历
- 清空顺序表并打印顺序表长度
- 在第 $2$ 编号处插入 $10$,结果插入成功,打印
“成功插入”
,否则打印“插入不成功”
- 依次插入 $1,2,3,4,5$,每次均在最后一个结点的后一个位置处
- 遍历
- 销毁顺序表
参考作答
- 本代码由于使用了模板函数,故定义和实现文件必须合并,统一在
sequential_list.h
内。- 本代码出于作者的习惯,所有的调用索引均从 $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
题目描述
简答题
请分析以下顺序表操作的算法,回答相应的问题:
- 遍历
ListTraverse(L)
的时间复杂度是? - 初始化
InitList(&L)
和释放DestroyList(&L)
的时间复杂度是? - 取值
GetElem(L,i,&e)
的时间复杂度是? - 查找
LocateElem(L,e)
的比较次数?时间复杂度是? - 插入
ListInsert(&L,i,e)
主要时间耗费在哪里?时间复杂度是? - 删除
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;
}
可见具有一个从 0
到 length-1
的 for
循环,其时间复杂度应为 $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)$。