c++ - C ++将数组中的数字重新排列为升序
问题描述
所以我有一个 C++ 实验室,需要我打印出一个数组,删除一些数字,然后插入一些数字。我设法删除了正确的数字,然后在末尾插入数字,但我需要将数组按升序排序,例如:1、2、3、4。我认为这将是容易的部分,但它给我带来的麻烦比我想象的要多。我尝试使用带有嵌套 if 循环的 for 循环,该循环适用于普通数组,但我想在混合中涉及指针让我很难过。当前代码运行并执行除排序之外的所有操作。任何提示或帮助表示赞赏。代码和输出发布在下面。这是作业描述的图像
#include <iostream>
using namespace std;
class Array //The array class
{
private:
//Data members capacity, size, arr (a pointer that points to the first element of the array in the heap)v and two functions to move integers in the array.
int capacity{};
int size{};
int* arr{};
void moveTowardFront(int index);
void moveTowardEnd(int index);
public:
Array(int capacity);//parameter
~Array();//destructor
//two member function declarations
void insert(int num);
void print() const;
void remove(int num);
};
//insert method
void Array::insert(int num)
{
{
//if size is 0, then move number taken from insert call into the first element of the array and increment size before returning
if (size == 0)
{
arr[0] = num;
size++;
return;
}
int index = 0;
while (&num < &arr[index] && index < size) //while the address of the number taken from insert function call is less than the address of the element [index] in the arr array
//and the index is less than the size of the array
{
index++; //then we increment the index
}
moveTowardEnd(index); //move value of element toward the end
//after the while loop we move the value of the number taken from main insert call into the arr element [index] after it has been incremented so we don't overwrite values
arr[index] = num;
size++;
//then we increment the size of the array because a new value has been inserted
}
}
// Delete member function
void Array::remove(int num)
{
int index = 0; //start index at 0
//while number from main is not equal to the array element of index and the index is smaller than the size, we increment the index
while (num != arr[index] && index < size)
{
index++;
}
//if index is equal to the size then output the number from main and say it isn't on the list so no removal
if (index == size)
{
cout << num << " is not in the list. ";
cout << "No removal." << endl;
return;
}
//move toward front function call on index value and post-increment. Then post-decrement size
moveTowardFront(index++);
size--;
}
//print method
void Array::print() const
{
//rearrange the digits in ascending order
for (int i = 0; i < size; i++)
{
//print out values based on value of size taken from insert method
cout << *(arr+i) << " "; //arr points to first element in heap and then moves over by i to the next element for each iteration
}
}
// Helper function to move the elements of array towards end
void Array::moveTowardEnd(int index)
{
int* temp = &arr[index];
int* temp2 = &arr[size-1];
arr[index] = *temp2;
arr[size] = *temp;
return;
}
// Helper function to move the elements of array towards front
void Array::moveTowardFront(int index)
{
int* temp = &arr[index];
int* temp2 = &arr[size-1];
arr[index] = *temp2;
arr[size] = *temp;
return;
}
//Destructor to clean up by deleting the space allocated
Array::~Array()
{
delete[]arr;
}
//Parameter constructor to allocate space
Array::Array(int cap)
:capacity(cap)
{
//move space allocated by array with capacity being taken from main into the arr pointer so pointer can point to first element in heap
arr = { new int[capacity] {} };//allocating memory with the new operator
size = 0;//initialize size to 0
}
int main()
{
// Declaration of any array of capacity 20
Array array(20);
// Inserting some elements and printing array
array.insert(15);
array.insert(13);
array.insert(10);
array.insert(14);
array.insert(11);
array.insert(17);
array.insert(14);
cout << "Printing array after insertions: " << endl;
array.print();
cout << endl;
// Removing two elements and printing array
array.remove(13);
array.remove(11);
cout << "Printing array after removals: " << endl;
array.print();
cout << endl;
// Inserting two more elements and printing array
array.insert(8);
array.insert(22);
cout << "Printing array after more insertion" << endl;
array.print();
cout << endl;
// Try to remove an element, which is not in the array
array.remove(31);
return 0;
}
解决方案
有很多方法可以对数组进行排序。常用的是被称为快速排序的算法:https ://en.wikipedia.org/wiki/Quicksort
取自维基百科页面的伪代码:
algorithm quicksort(A, lo, hi) is
// first we check if the lo and hi
// are natural numbers (without this check, you
// will get an overflow error because, at some point
// the program will access something like A[-1]
// which does not exists !
if lo >= 0 && hi >= 0 then
// if the indexes are in correct order, continue
if lo < hi then
// we find the index of the pivot and...
p := partition(A, lo, hi)
// ...apply quicksort for the left side and the
// right side of the array
quicksort(A, lo, p - 1)
quicksort(A, p + 1, hi)
algorithm partition(A, lo, hi) is
// we set the pivot value to the
// final value of the array
pivot := A[hi]
// we set the pivotIndex (i) to
// the start of the array
// ! NOTICE that A[i] != pivot
// aka. A[pivotIndex] != pivotValue
i := lo - 1
// we traverse the array from the start
// to the end (inclusive) aka. we traverse
// the array in this interval: [lo, hi]
for j := lo to hi do
// if the current element is
// less than the value of the pivot
// (or equal to it), then increment the i
// and swap it with the element at i (pivotIndex)
// ! NOTICE that j is automatically incremented
if A[j] <= pivot then
i := i + 1
swap A[i] with A[j]
return i
您必须自己将伪代码翻译成 C++。他们似乎使用名称algorithm
来表示函数定义,并使用:=
运算符进行赋值,但除此之外它与 C++ 语法并没有太大的不同。他们写在一个地方swap A[i] with A[j]
,对你来说可能看起来更像:
int temp = A[i];
A[i] = A[j];
A[j] = temp;
推荐阅读
- java - 将角色分配给没有 FetchType.EAGER 的用户
- qt - 基于屏幕分辨率计算 QT 5.12 中的投影矩阵
- java - 如何在 clojure 中导入 java 类?
- c# - 传递下拉列表数据,然后在表单中显示
- visual-studio-code - 如何在本地安装 VSCode 扩展?
- charts - 生成图表时出错:Google 地球引擎中显示计算超时
- c++ - 使用 C++ 实现 Web 自动化
- javascript - WKWebView 实现 javascript remove() 但留下空行
- ios - Swift:解码 JSON 响应并将嵌套的 JSON 存储为字符串或 JSON
- python - 我想将 conafile.py 一分为二,两个文件都包含一些方法,然后将第二个 .py 文件的方法继承到 conanfile.py