9.27作业
顺序表
SeqList.h
#ifndef SEQLIST_H
#define SEQLIST_H
#include <iostream>
#include<memory.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
//封装一个顺序表
template <typename T>
class SeqList
{
private:
T *ptr; //指向堆区空间的起始地址
int size; //总长度
int len = 0; //当前顺序表实际长度
public:
//初始化
// 默认构造函数
SeqList() : ptr(nullptr), size(0), len(0) {}
// 构造函数接受数组和大小
SeqList(T* arr, int n) : size(n), len(n) {
ptr = new T[n];
for (int i = 0; i < n; i++) {
ptr[i] = arr[i];
}
}
// 构造函数接受字符串
SeqList(const std::string& str) {
size = str.size();
len = size;
ptr = new T[size];
for (int i = 0; i < size; i++) {
ptr[i] = static_cast<T>(str[i] - '0'); // 假设字符串是数字字符
}
}
~SeqList() {
delete[] ptr;
}
//判空
bool empty();
//判满
bool full();
//尾插
void push_back(T e);
//定义展示函数
void show();
//插入
void insert(int index);
//任意位置删除
void delete_s(int index);
//尾删: pop_back
void pop_back();
//求长度:size()
T get_len();
//获取任意位置元素:& at(int inex)
T get_index(int index);
//将顺序表进行排序:sort(bool flag)flag 为真,表示升序,否则是降序
void sort(bool flag);
};
#endif // SEQLIST_H
SeqList.cpp
#include "SeqList.h"
// 判空
template <typename T>
bool SeqList<T>::empty()
{
return this->len == 0;
}
// 判满
template <typename T>
bool SeqList<T>::full()
{
return this->len == this->size;
}
// 尾插
template <typename T>
void SeqList<T>::push_back(T e)
{
if (this->full())
{
cout << "顺序表已满,无法插入!" << endl;
return;
}
this->ptr[len++] = e;
}
// 定义展示函数
template <typename T>
void SeqList<T>::show()
{
if (this->empty()) {
cout << "顺序表为空!" << endl;
return;
}
cout << "当前顺序表中的元素分别是:";
for (int i = 0; i < this->len; i++)
{
cout << this->ptr[i] << " ";
}
cout << endl;
}
// 插入
template <typename T>
void SeqList<T>::insert(int index)
{
if (this->full())
{
cout << "表已经满了!" << endl;
return;
}
if (index > this->len + 1 || index <= 0)
{
cout << "插入位置不合理" << endl;
return;
}
T e;
cout << "请输入插入元素:";
cin >> e;
for (int i = len - 1; i >= index - 1; i--)
{
this->ptr[i + 1] = this->ptr[i];
}
this->ptr[index - 1] = e;
this->len++;
}
// 任意位置删除
template <typename T>
void SeqList<T>::delete_s(int index)
{
if (index > this->len || index <= 0)
{
cout << "删除位置不合理" << endl;
return;
}
for (int i = index; i < this->len; i++)
{
this->ptr[i - 1] = this->ptr[i];
}
this->len--;
}
// 尾删: pop_back
template <typename T>
void SeqList<T>::pop_back()
{
if (this->len == 0)
{
cout << "顺序表为空!" << endl;
return;
}
this->len--;
}
// 求长度:size()
template <typename T>
T SeqList<T>::get_len()
{
return this->len;
}
// 获取任意位置元素
template <typename T>
T SeqList<T>::get_index(int index)
{
if (index > this->len || index <= 0)
{
cout << "位置不合理" << endl;
return T(); // 返回一个默认值
}
return this->ptr[index - 1];
}
// 将顺序表进行排序:sort(bool flag)flag 为真,表示升序,否则是降序
template <typename T>
void SeqList<T>::sort(bool flag)
{
for (int i = 0; i < this->len - 1; i++)
{
for (int j = 0; j < this->len - i - 1; j++)
{
if ((flag && this->ptr[j] > this->ptr[j + 1]) || (!flag && this->ptr[j] < this->ptr[j + 1]))
{
T t = this->ptr[j];
this->ptr[j] = this->ptr[j + 1];
this->ptr[j + 1] = t;
}
}
}
}
// 显式实例化
template class SeqList<int>; // 显式实例化 int 类型的 SeqList
main.cpp
#include "SeqList.h"
int main()
{
// 使用数组创建顺序表对象
int arr[] = {1, 2, 3, 4, 5}; // 示例数组
SeqList<int> sl(arr, 5); // 使用数组初始化顺序表
sl.show();
// 或者使用字符串创建顺序表对象
// SeqList<int> sl("12345"); // 使用字符串初始化顺序表
// sl.show();
// 其他操作
int add;
cout << "请输入插入数据的位置:";
cin >> add;
sl.insert(add);
sl.show();
cout << "请输入删除数据的位置:";
cin >> add;
sl.delete_s(add);
sl.show();
int c;
cout << "是否尾删(1:YES/2:NO):";
cin >> c;
if (c == 1) {
sl.pop_back();
}
sl.show();
int l = sl.get_len();
cout << "顺序表当前长度为:" << l << endl;
int index;
cout << "请输入需要位置:";
cin >> index;
cout << index << "位置数据位:" << sl.get_index(index) << endl;
cout << "将顺序表进行排序(1:升序,0:降序):";
cin >> c;
sl.sort(c);
sl.show();
return 0;
}
栈
MyStack.h
#ifndef MYSTACK_H
#define MYSTACK_H
#include <iostream>
using namespace std;
template <typename T>
class My_stack {
private:
struct Node {
T data; // 节点数据
Node* next; // 指向下一个节点的指针
Node(T value) : data(value), next(nullptr) {} // 节点构造函数
};
Node* topNode; // 栈顶节点
int stackSize; // 栈的大小
public:
// 构造函数
My_stack();
// 拷贝构造函数
My_stack(const My_stack &other);
// 赋值运算符
My_stack& operator=(const My_stack &other);
// 析构函数
~My_stack();
// 返回栈顶元素
T& top();
// 返回栈是否为空
bool empty() const;
// 返回栈的大小
int size() const;
// 压入元素
void push(T value);
// 弹出元素
void pop();
// 交换两个栈的内容
void swap(My_stack &other);
};
// 全局函数用于交换两个栈
template <typename T>
void swap(My_stack<T> &a, My_stack<T> &b);
#endif // MYSTACK_H
MyStack.cpp
#include "MyStack.h"
// 构造函数
template <typename T>
My_stack<T>::My_stack() : topNode(nullptr), stackSize(0) {}
// 拷贝构造函数
template <typename T>
My_stack<T>::My_stack(const My_stack &other) : topNode(nullptr), stackSize(0) {
Node* current = other.topNode;
while (current) {
push(current->data);
current = current->next;
}
}
// 赋值运算符
template <typename T>
My_stack<T>& My_stack<T>::operator=(const My_stack &other) {
if (this != &other) {
// 先清空当前栈
while (!empty()) {
pop();
}
Node* current = other.topNode;
while (current) {
push(current->data);
current = current->next;
}
}
return *this;
}
// 析构函数
template <typename T>
My_stack<T>::~My_stack() {
while (!empty()) {
pop();
}
}
// 返回栈顶元素
template <typename T>
T& My_stack<T>::top() {
if (empty()) {
cout << "栈空!" << endl;
exit(EXIT_FAILURE); // 直接退出程序
}
return topNode->data;
}
// 返回栈是否为空
template <typename T>
bool My_stack<T>::empty() const {
return stackSize == 0;
}
// 返回栈的大小
template <typename T>
int My_stack<T>::size() const {
return stackSize;
}
// 压入元素
template <typename T>
void My_stack<T>::push(T value) {
Node* newNode = new Node(value);
newNode->next = topNode;
topNode = newNode;
stackSize++;
}
// 弹出元素
template <typename T>
void My_stack<T>::pop() {
if (empty()) {
cout << "栈空!" << endl;
exit(EXIT_FAILURE); // 直接退出程序
}
Node* temp = topNode;
topNode = topNode->next;
delete temp;
stackSize--;
}
// 交换两个栈的内容
template <typename T>
void My_stack<T>::swap(My_stack &other) {
std::swap(topNode, other.topNode);
std::swap(stackSize, other.stackSize);
}
// 全局函数用于交换两个栈
template <typename T>
void swap(My_stack<T> &a, My_stack<T> &b) {
a.swap(b);
}
// 显式实例化
template class My_stack<int>; // 显式实例化 int 类型的 My_stack
template void swap(My_stack<int> &a, My_stack<int> &b); // 显式实例化 swap 函数
main.cpp
#include "MyStack.h"
int main() {
My_stack<int> s;
s.push(9);
s.push(2);
s.push(6);
s.push(7);
s.push(8);
cout << "栈顶元素:" << s.top() << endl;
cout << "栈的大小:" << s.size() << endl;
s.pop();
cout << "栈顶元素:" << s.top() << endl;
My_stack<int> s1;
s1.push(1);
s1.push(2);
My_stack<int> s2;
s2 = s;
swap(s2, s1); // 交换两个栈
cout << "交换后的栈顶元素:" << s2.top() << endl;
cout << "交换后另一个栈顶元素:" << s1.top() << endl;
return 0;
}
队列
MyQueue.h
#ifndef MYQUEUE_H
#define MYQUEUE_H
#include <iostream>
#include <cstring>
using namespace std;
template <typename T>
class Queue {
private:
T* data; // 数据指针
int len; // 当前数量
int size; // 最大容量
int front; // 头索引
int rear; // 尾索引
public:
// 构造函数
Queue();
Queue(const T* d, int size);
// 析构函数
~Queue();
// 拷贝构造
Queue(const Queue &other);
// 拷贝赋值
Queue& operator=(const Queue &other);
// front函数
T MyFront();
// back函数
T back();
// empty函数
bool empty();
// size函数
int MySize();
// push函数
void push(T e);
// emplace函数
void emplace(T e);
// pop函数
T pop();
// swap函数
void swap(Queue &other);
};
#endif // MYQUEUE_H
MyQueue.cpp
#include "MyQueue.h"
// 无参构造函数
template <typename T>
Queue<T>::Queue() : len(0), size(20), front(0), rear(0) {
data = new T[size];
}
// 有参构造函数
template <typename T>
Queue<T>::Queue(const T* d, int size) : len(strlen(d)), size(size), front(0), rear(len) {
data = new T[size];
strcpy(data, d);
}
// 析构函数
template <typename T>
Queue<T>::~Queue() {
delete[] data;
}
// 拷贝构造函数
template <typename T>
Queue<T>::Queue(const Queue &other) : len(other.len), size(other.size), front(other.front), rear(other.rear) {
data = new T[size];
strcpy(data, other.data);
}
// 拷贝赋值运算符
template <typename T>
Queue<T>& Queue<T>::operator=(const Queue &other) {
if (this != &other) {
delete[] data; // 释放旧内存
len = other.len;
size = other.size;
front = other.front;
rear = other.rear;
data = new T[size];
strcpy(data, other.data);
}
return *this;
}
// MyFront函数
template <typename T>
T Queue<T>::MyFront() {
if (empty()) {
cout << "队列为空" << endl;
exit(EXIT_FAILURE);
}
return data[front];
}
// back函数
template <typename T>
T Queue<T>::back() {
if (empty()) {
cout << "队列为空" << endl;
exit(EXIT_FAILURE);
}
return data[rear - 1]; // rear指向下一个插入位置
}
// empty函数
template <typename T>
bool Queue<T>::empty() {
return front == rear && len == 0;
}
// MySize函数
template <typename T>
int Queue<T>::MySize() {
return len;
}
// push函数
template <typename T>
void Queue<T>::push(T e) {
if (len >= size) {
cout << "队列已满" << endl;
return;
}
data[rear++] = e;
len++;
}
// emplace函数
template <typename T>
void Queue<T>::emplace(T e) {
push(e); // 直接调用 push 函数
}
// pop函数
template <typename T>
T Queue<T>::pop() {
if (empty()) {
cout << "队列为空" << endl;
exit(EXIT_FAILURE);
}
len--;
return data[front++];
}
// swap函数
template <typename T>
void Queue<T>::swap(Queue &other) {
std::swap(len, other.len);
std::swap(size, other.size);
std::swap(front, other.front);
std::swap(rear, other.rear);
std::swap(data, other.data);
}
// 显式实例化
template class Queue<char>; // 显式实例化 char 类型的 Queue
main.cpp
#include "MyQueue.h"
int main() {
Queue<char> q("hello world", 20);
// 测试emplace
q.emplace('A');
q.emplace('B');
q.emplace('C');
cout << "q队首数据:" << q.MyFront() << endl;
cout << "q队尾数据:" << q.back() << endl;
cout << "q队列数据数量 " << q.MySize() << endl;
// 测试 pop
cout << "q尾删操作" << endl;
q.pop();
cout << "q队首数据:" << q.MyFront() << endl;
Queue<char> q1;
q1 = q;
cout << "q1队首数据:" << q1.MyFront() << endl;
cout << "q1队尾数据:" << q1.back() << endl;
Queue<char> q2("nihao", 20); // 创建一个最大容量为 20 的队列
cout << "交换操作" << endl;
q.swap(q2);
cout << "q队首数据:" << q.MyFront() << endl;
cout << "q队尾数据:" << q.back() << endl;
cout << "q2队首数据:" << q2.MyFront() << endl;
cout << "q2队尾数据:" << q2.back() << endl;
return 0;
}
思维导图
原文地址:https://blog.csdn.net/qq_62608227/article/details/142601495
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!