1 Star 0 Fork 0

郑玉强/dataStructure

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
seq_list.hpp 8.16 KB
一键复制 编辑 原始数据 按行查看 历史
郑玉强 提交于 2024-10-06 16:23 +08:00 . 临时提交
#ifndef SEQ_LIST_HPP
#define SEQ_LIST_HPP
/* code */
#include <iostream>
#include <cstdlib>
#include <exception>
#include "linear_list.h"
using namespace std;
//模板类的实现需要和声明放在同一个头文件中
template<class TData>
class SeqList :public LinearList<TData>
{
private:
// 数据项数组
TData* mem_data_;
// 容量(最大长度)
int capacity_;
// 最后一项的数组索引
int last_index_;
public:
// C++提供了初始化列表语法,用来初始化属性
// 此方法为函数实现
SeqList() :mem_data_(NULL), capacity_(0), last_index_(-1) {}
// explicit 关键字确保这个构造函数不会被用于隐式类型转换
// 隐式转换:MyClass obj = 10; 隐式调用了 MyClass(int) 构造函数
explicit SeqList(int capacity);
// 拷贝(复制)构造函数
SeqList(const SeqList<TData>& seq_list);
// 此方法为函数实现
~SeqList()
{
if (mem_data_ != NULL)
delete[] mem_data_;
}
int capacity() const { return capacity_; }
virtual int length() const override { return last_index_ + 1; }
int search(const TData& data) const;
virtual bool getData(int pos, TData& data) const override;
// const TData& data ==> const TData * const data
virtual bool setData(int pos, const TData& data) override;
virtual bool insert(int prev_pos, const TData& data) override;
virtual bool remove(int deletion_pos, TData& data) override;
virtual bool isEmpty() const override;
bool isFull() const;
// 调整顺序表的容量
bool resetCapacity(int capacity);
void sort();
virtual void print() const override;
// 复制函数
SeqList<TData>& operator=(const SeqList<TData>& seq_list);
};
template<class TData>
SeqList<TData>::SeqList(int capacity): capacity_(capacity), last_index_(-1)
{
if (capacity < 0)
throw out_of_range("capacity < 0");
this->mem_data_ = new TData[this->capacity_];
if (!this->mem_data_)
throw bad_alloc();
}
template<class TData>
SeqList<TData>::SeqList(const SeqList<TData>& seq_list)
{
this->capacity = seq_list.capacity();
this->last_index_ = seq_list.length() - 1;
if (this->capacity_ == 0)
return;
this->mem_data_ = new TData[this->capacity()];
if (!this->mem_data_)
throw bad_alloc();
for (int pos = 1; pos <= seq_list.length(); pos++)
{
TData cur_data;
// seq_list位置pos的变量赋给cur_data
seq_list.getData(pos, cur_data);
this->mem_data_[pos - 1] = cur_data;
}
}
template<class TData>
bool SeqList<TData>::resetCapacity(int capacity)
{
if (capacity < this->length())
return false;
TData* new_mem_data = new TData[capacity];
if (new_mem_data == NULL)
throw bad_alloc();
for (int i = 0; i < this->length(); i++)
new_mem_data[i] = this->mem_data_[i];
// 释放旧的顺序表占用的堆空间
delete[] this->mem_data_;
// 调整指针指向
this->mem_data_ = new_mem_data;
this->capacity_ = capacity;
return true;
}
template<class TData>
int SeqList<TData>::search(const TData& data) const
{
for (int i = 0; i <= this->last_index_; i++)
{
if (this->mem_data_[i] == data)
return i + 1;
}
return 0; // 没找到
}
template<class TData>
bool SeqList<TData>::getData(int pos, TData& data) const
{
if (pos <= 0 || pos > this->last_index_ + 1)
return false;
data = this->mem_data_[pos - 1];
return true;
}
template<class TData>
bool SeqList<TData>::setData(int pos, const TData& data)
{
if (pos <= 0 || pos > this->last_index_ + 1)
return false;
this->mem_data_[pos - 1] = data;
return true;
}
template<class TData>
bool SeqList<TData>::insert(int prev_pos, const TData& data)
{
if (this->last_index_ == this->capacity_ - 1)
// 此时容器已满,无法执行插入操作
return false;
if (prev_pos < 0 || prev_pos > this->last_index_ + 1)
return false;
for (int i = this->last_index_; i >= prev_pos; i--)
// 向后移动一个元素位置,腾出下标prev_pos的元素
this->mem_data_[i + 1] = this->mem_data_[i];
this->mem_data_[prev_pos] = data;
this->last_index_++;
return true;
}
template<class TData>
bool SeqList<TData>::remove(int deletion_pos, TData& data)
{
if (this->last_index_ == -1)
// 容器为空
return false;
if (deletion_pos < 1 || deletion_pos > this->length())
return false;
// 返回删除元素
data = this->mem_data_[deletion_pos - 1];
for (int i = deletion_pos; i <= this->last_index_; i++)
// 各元素向前移动一位
this->mem_data_[i - 1] = this->mem_data_[i];
this->last_index_--;
return true;
}
template<class TData>
bool SeqList<TData>::isEmpty() const
{
if (this->last_index_ == -1)
return true;
return false;
}
template<class TData>
bool SeqList<TData>::isFull() const
{
if (this->last_index_ == this->capacity_ - 1)
return true;
return false;
}
template<class TData>
void bubbleSort(SeqList<TData>& seq_list)
{
int length = seq_list.length();
for (int i = 1; i <= length - 1; i++)
{
for (int j = 0; j < length - i; j++)
{
int j_ = j + 1;
TData j_data;
seq_list.getData(j_, j_data);
TData j_next_data;
seq_list.getData(j_+1, j_next_data);
if (j_data > j_next_data)
{
seq_list.setData(j_, j_next_data);
seq_list.setData(j_+1, j_data);
}
}
}
}
template<class TData>
void selectSort(SeqList<TData>& seq_list)
{
// 选择排序:从第一个元素开始,拿着每一个索引上的元素跟后面的元素依次比较,
// 小的放前面,大的放后面,以此类推。
int length = seq_list.length();
for (int i = 1; i <= length - 1; i++)
{
for (int j = i + 1; j <= length; j++)
{
TData i_data;
seq_list.getData(i, i_data);
TData j_data;
seq_list.getData(j, j_data);
if (i_data > j_data)
{
seq_list.setData(i,j_data);
seq_list.setData(j,i_data);
}
}
}
}
template<class TData>
void insertSort(SeqList<TData>& seq_list)
{
// 插入排序:将第一个元素到第N个元素看作是有序的(真实有序的,单个元素也有序),
// 把N+1索引的元素到最后一个当成是无序的。遍历无序的数据,将遍历到的元素插入有序序列中适当的位置,
// 如遇到相同数据,插在后面(维持稳定性)。
int length = seq_list.length();
int startIndex = 2; // 认为第一个元素是有序的,startIndex存储的是第一个无序数据的下标
for (int i = startIndex; i <= length; i++)
{
// 执行“排序操作”
int j = i;
TData j_data;
seq_list.getData(j, j_data);
TData j_prev_data;
seq_list.getData(j - 1, j_prev_data);
while (j > 1 && j_prev_data > j_data )
{
seq_list.setData(j, j_prev_data);
seq_list.setData(j-1, j_data);
j--;
seq_list.getData(j, j_data);
seq_list.getData(j - 1, j_prev_data);
}
}
}
template<class TData>
void quickSort(SeqList<TData>& seq_list, int i, int j)
{
// 定义两个变量记录要查找的范围
int start = i;
int end = j;
if (start > end)
return;
// 基准元素
TData baseNumber;
seq_list.getData(i,baseNumber);
TData rightNumber;
TData leftNumber;
while (start != end)
{
// 先从右边开始找
while (true)
{
seq_list.getData(end,rightNumber);
if (end <= start || rightNumber < baseNumber)
break;
end--;
}
// 再从左边开始找
while (true)
{
seq_list.getData(start, leftNumber);
if (end <= start || leftNumber > baseNumber)
break;
start++;
}
// 把end和start指向的元素进行交互
seq_list.setData(start,rightNumber);
seq_list.setData(end,leftNumber);
}
//当start和end指向了同一个元素的时候,那么上面的循环就会结束
//表示已经找到了基准数在数组中应存入的位置
//基准数归位
//就是拿着这个范围中的第一个数字,跟start或end指向的元素进行交换
seq_list.setData(i, rightNumber);
seq_list.setData(end, baseNumber);
//确定6左边的范围,重复刚刚所做的事情
quickSort(seq_list, i, start - 1);
//确定6右边的范围,重复刚刚所做的事情
quickSort(seq_list, start + 1, j);
}
template<class TData>
void SeqList<TData>::sort()
{
//bubbleSort(*this);
//selectSort(*this);
//insertSort(*this);
quickSort(*this, 1, (*this).length());
}
template<class TData>
void SeqList<TData>::print() const
{
if (this->last_index_ == -1)
{
cout << "顺序表为空" << endl;
return;
}
for (int i = 0; i <= this->last_index_; i++)
cout << "位置(从1开始)" << i + 1 << ":" << this->mem_data_[i] << endl;
}
template<class TData>
SeqList<TData>& SeqList<TData>::operator=(const SeqList<TData>& seq_list)
{
if (&seq_list == this)
return *this;
bool res = this->resetCapacity(seq_list.capacity());
if (!res)
throw length_error("seq_list length wrong");
int length = seq_list.length();
for (int i = 1; i <= length; i++)
{
TData cur_data;
seq_list.getData(i, cur_data);
this->mem_data_[i - 1] = cur_data;
this->last_index_++;
}
return *this;
}
#endif // !SEQ_LIST_HPP
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
C++
1
https://gitee.com/zheng-yuqiang_lyg_cn/data-structure.git
git@gitee.com:zheng-yuqiang_lyg_cn/data-structure.git
zheng-yuqiang_lyg_cn
data-structure
dataStructure
dev01

搜索帮助