数据结构之顺序表
线性表定义
线性表是由 n (n ≥ 0) 个具有相同特征的数据元素组成的有限序列。记作：(a₁, a₂, …, aᵢ₋₁, aᵢ, aᵢ₊₁, …, aₙ)
线性表相关概念
**直接前驱元素：**对于元素 aᵢ，若存在 aᵢ₋₁ 且 aᵢ₋₁ 紧邻 aᵢ，则称 aᵢ₋₁ 是 aᵢ 的直接前驱元素。
**直接后继元素：**对于元素 aᵢ，若存在 aᵢ₊₁ 且 aᵢ₊₁ 紧邻 aᵢ，则称 aᵢ₊₁ 是 aᵢ 的直接后继元素。
**前驱元素：**位于 aᵢ 之前的所有元素 (a₁, a₂, …, aᵢ₋₁) 统称为 aᵢ 的前驱元素。
**后继元素：**位于 aᵢ 之后的所有元素 (aᵢ₊₁, aᵢ₊₂, …, aₙ) 统称为 aᵢ 的后继元素。
**线性表的长度：**线性表中数据元素的个数，记为 n。
**空线性表：**不包含任何元素的线性表，长度为 0。
**位序：**元素在线性表中的位置，通常从 1 开始计数。
顺序表概念
顺序表是一种使用一组连续的存储单元依次存储线性表中的数据元素的存储结构。
顺序表特点
- 存储特性
- 元素在内存中物理地址连续
- 支持随机访问（可通过下标快速定位元素）
- 存储空间大小固定，需要预先分配
- 操作特性
- 访问和修改元素的时间复杂度为 O(1)
- 插入和删除元素的时间复杂度为 O(n)
- 需要移动其他元素以保持连续性
适用场景
- 元素数量相对固定
- 频繁随机访问
- 较少插入和删除操作
局限性
- 插入和删除操作效率低
- 需要预先分配存储空间
- 空间利用率不高
顺序表基本操作
基本操作
- 初始化操作：
SequenceList - 判空操作：
empty_sqlist - 判满操作：
is_full_sqlist - 求长度运算：
size - 查找元素操作：
search_sqlist - 插入元素操作：
insert_sqlist - 删除元素操作：
delete_sqlist - 修改元素操作：
modify_sqlist
实现代码
#ifndef SEQUENCELIST_H
#define SEQUENCELIST_H
#include <iostream>
#include <stdexcept>
const int MAX_SIZE = 100; // 顺序表最大容量
template <typename T>
class SequenceList
{
private:
T data[MAX_SIZE]; // 存储元素的数组
int length; // 当前顺序表长度
public:
// 构造函数
SequenceList();
// 判空操作
bool empty_sqlist() const;
// 判满操作
bool is_full_sqlist() const;
// 求长度运算
int size() const;
// 查找元素操作
int search_sqlist(const T& element) const;
// 插入元素操作
void insert_sqlist(int position, const T& element);
// 删除元素操作
void delete_sqlist(int position);
// 修改元素操作
void modify_sqlist(int position, const T& element);
// 获取指定位置的元素
T get_element(int position) const;
// 打印顺序表
void print() const;
};
#endif // SEQUENCELIST_H
#include "SequenceList.h"
// 构造函数
template <typename T>
SequenceList<T>::SequenceList() : length(0) {}
// 判空操作
template <typename T>
bool SequenceList<T>::empty_sqlist() const
{
return length == 0;
}
// 判满操作
template <typename T>
bool SequenceList<T>::is_full_sqlist() const
{
return length == MAX_SIZE;
}
// 求长度运算
template <typename T>
int SequenceList<T>::size() const
{
return length;
}
// 查找元素操作
template <typename T>
int SequenceList<T>::search_sqlist(const T& element) const
{
for (int i = 0; i < length; ++i)
{
if (data[i] == element)
{
return i; // 返回元素的索引
}
}
return -1; // 未找到元素
}
// 插入元素操作
template <typename T>
void SequenceList<T>::insert_sqlist(int position, const T& element)
{
// 检查插入位置是否合法
if (position < 0 || position > length)
{
throw std::out_of_range("插入位置非法");
}
// 检查顺序表是否已满
if (is_full_sqlist())
{
throw std::runtime_error("顺序表已满");
}
// 从后向前移动元素
for (int i = length; i > position; --i)
{
data[i] = data[i - 1];
}
// 插入新元素
data[position] = element;
++length;
}
// 删除元素操作
template <typename T>
void SequenceList<T>::delete_sqlist(int position)
{
// 检查删除位置是否合法
if (position < 0 || position >= length)
{
throw std::out_of_range("删除位置非法");
}
// 从前向后移动元素
for (int i = position; i < length - 1; ++i)
{
data[i] = data[i + 1];
}
--length;
}
// 修改元素操作
template <typename T>
void SequenceList<T>::modify_sqlist(int position, const T& element)
{
// 检查修改位置是否合法
if (position < 0 || position >= length)
{
throw std::out_of_range("修改位置非法");
}
data[position] = element;
}
// 获取指定位置的元素
template <typename T>
T SequenceList<T>::get_element(int position) const
{
if (position < 0 || position >= length)
{
throw std::out_of_range("位置非法");
}
return data[position];
}
// 打印顺序表
template <typename T>
void SequenceList<T>::print() const
{
for (int i = 0; i < length; ++i)
{
std::cout << data[i] << " ";
}
std::cout << std::endl;
}
// 显式实例化
template class SequenceList<int>;
#include "SequenceList.h"
int main()
{
SequenceList<int> sqlist;
// 插入元素
for (int i = 0; i < MAX_SIZE; ++i)
{
sqlist.insert_sqlist(0, i);
}
std::cout << "顺序表元素：";
sqlist.print();
// 查找元素
int index = sqlist.search_sqlist(20);
std::cout << "元素20的索引：" << index << std::endl;
// 修改元素
sqlist.modify_sqlist(0, 25);
// 删除元素
// sqlist.delete_sqlist(0);
std::cout << "修改和删除后的顺序表：";
sqlist.print();
// 获取长度
std::cout << "顺序表长度：" << sqlist.size() << std::endl;
std::cout << "是否存满：" << sqlist.is_full_sqlist() << std::endl;
return 0;
}
顺表应用案例
顺序表是一种常见的数据结构，它可以用于许多应用场景，下面列举几个常见的应用：
-
数组：顺序表可以用于实现数组，数组是一种常见的数据结构，它可以用于存储一组相同类型的数据。在顺序表中，数组的每个元素都存储在连续的内存空间中，可以通过下标来访问。
-
多项式：顺序表可以用于实现多项式，多项式是一种常见的数学概念，它可以表示为一系列项的和，每个项包含一个系数和一个指数。在顺序表中，多项式的每个项可以存储在一个元素中，可以按照指数的大小顺序排列。
y=3x^4^+5x^3^-3x^2^+x+0;
y=4x^4^+2x^3^-4x^2^+x+0; +
---------------------------------
y=7x^4^+7x^3^-7x^2^+2x+0;
-
缓存：顺序表可以用于实现缓存，缓存是一种常见的技术，用于提高数据访问速度。在顺序表中，可以将最近访问的数据存储在前面的元素中，这样可以更快地访问最近使用的数据。
-
排序：顺序表可以用于实现排序算法，排序是一种常见的算法，用于将数据按照一定的顺序排列。在顺序表中，可以使用不同的排序算法，如冒泡排序、插入排序、快速排序等。
-
数据库：顺序表可以用于实现简单的数据库，数据库是一种常见的数据存储和管理系统，用于存储和管理大量数据。在顺序表中，可以将数据存储在不同的元素中，可以使用不同的算法来实现数据的查询、插入、删除等操作。
应用注意实现
- 空间限制：顺序表需要预先分配固定大小的内存。
- 插入删除效率低：需要移动大量元素。
- 随机访问高效：支持O(1)时间复杂度的元素访问。
- 适用场景：数据量相对固定、随机访问频繁的场景。
总的来说，顺序表是一种非常常见的数据结构，可以用于许多应用场景。在实际应用中，我们需要根据具体情况选择合适的数据结构和算法，以提高程序的效率和可维护性。
多项式加法
// SequenceList.h
// 多项式的结构体
template <typename T>
struct PolyTerm
{
T coefficient; // 系数
int exponent; // 指数
PolyTerm(T coef = 0, int exp = 0);
// 比较运算符（用于排序）
bool operator<(const PolyTerm& other) const;
// 重载 operator==
bool operator==(const PolyTerm<T>& other) const;
};
template <typename T>
class Polynomial
{
private:
SequenceList<PolyTerm<T>> terms;
void sortAndMergeTerms(); // 内部排序和合并同类型
public:
Polynomial();
// 添加多项式
void addTerm(T coefficien, int exponent);
// 多项式加法
Polynomial<T> operator+(const Polynomial<T>& other) const;
// 打印多项式
void print() const;
// 获取多项式项数
int getTermCount() const;
};
// SequenceList.cpp
template<typename T>
PolyTerm<T>::PolyTerm(T coef, int exp) : coefficient(coef), exponent(exp) {}
template<typename T>
bool PolyTerm<T>::operator<(const PolyTerm &other) const
{
return exponent > other.exponent;
}
template<typename T>
bool PolyTerm<T>::operator==(const PolyTerm<T> &other) const
{
return (coefficient == other.coefficient && exponent == other.exponent);
}
template<typename T>
void Polynomial<T>::sortAndMergeTerms()
{
// 冒泡排序
for (int i = 0; i < terms.size() - 1; ++i)
{
for (int j = 0; j < terms.size() - 1; ++j)
{
PolyTerm<T> term1 = terms.get_element(j);
PolyTerm<T> term2 = terms.get_element(j + 1);
if (term1.exponent < term2.exponent)
{
terms.modify_sqlist(j, term2);
terms.modify_sqlist(j + 1 ,term1);
}
}
}
// 合并同类项
for (int i = 0; i < terms.size() - 1; ++i)
{
PolyTerm<T> currentTerm = terms.get_element(i);
PolyTerm<T> nextTerm = terms.get_element(i + 1);
if (currentTerm.exponent == nextTerm.exponent)
{
// 合并系数
currentTerm.coefficient += nextTerm.coefficient;
terms.modify_sqlist(i, currentTerm);
// 删除重复项
terms.delete_sqlist(i + 1);
// 回退一步
i--;
}
}
// 移除系数为0的项
for (int i = 0; i < terms.size() - 1; ++i)
{
if (terms.get_element(i).coefficient == 0)
{
terms.delete_sqlist(i);
i--;
}
}
}
template<typename T>
Polynomial<T>::Polynomial() {}
template<typename T>
void Polynomial<T>::addTerm(T coefficien, int exponent)
{
if (coefficien != 0)
{
terms.insert_sqlist(terms.size(), PolyTerm<T>(coefficien, exponent));
}
}
template<typename T>
Polynomial<T> Polynomial<T>::operator+(const Polynomial<T> &other) const
{
Polynomial<T> result;
// 复制当前多项式的项
for (int i = 0; i < terms.size(); ++i)
{
result.addTerm(terms.get_element(i).coefficient,
terms.get_element(i).exponent);
}
// 添加另一个多项式的项
for (int i = 0; i < other.terms.size(); ++i)
{
result.addTerm(other.terms.get_element(i).coefficient,
other.terms.get_element(i).exponent);
}
result.sortAndMergeTerms();
return result;
}
template <typename T>
void Polynomial<T>::print() const
{
if (terms.empty_sqlist())
{
std::cout << "0" << std::endl;
return;
}
for (int i = 0; i < terms.size(); ++i)
{
PolyTerm<T> term = terms.get_element(i);
T coef = term.coefficient;
int exp = term.exponent;
// 处理系数
if (coef > 0 && i > 0)
{
std::cout << "+ ";
}
// 特殊处理系数为1或-1的情况
if (std::abs(coef) == 1 && exp > 0)
{
std::cout << (coef > 0 ? "" : "-");
} else {
std::cout << coef;
}
// 处理指数
if (exp > 0)
{
std::cout << "x";
if (exp > 1)
{
std::cout << "^" << exp;
}
}
// 添加空格
if (i < terms.size() - 1)
{
std::cout << " ";
}
}
std::cout << std::endl;
}
template<typename T>
int Polynomial<T>::getTermCount() const
{
return terms.size();
}
// 显示实例化
template class SequenceList<int>;
template struct PolyTerm<int>;
template class Polynomial<int>;
// main.cpp
#include "SequenceList.h"
int main()
{
// 创建第一个多项式：3x^4 + 5x^3 - 3x^2 + x
Polynomial<int> poly1;
poly1.addTerm(3, 4);
poly1.addTerm(5, 3);
poly1.addTerm(-3, 2);
poly1.addTerm(1, 1);
// 创建第二个多项式：4x^4 + 2x^3 - 4x^2 + x
Polynomial<int> poly2;
poly2.addTerm(4, 4);
poly2.addTerm(2, 3);
poly2.addTerm(-4, 2);
poly2.addTerm(1, 1);
// 打印原始多项式
std::cout << "多项式1：";
poly1.print();
std::cout << "多项式2：";
poly2.print();
// 多项式相加
Polynomial<int> result = poly1 + poly2;
std::cout << "相加结果：";
result.print();
return 0;
}