Динамический контейнер массив


Это в первую очередь контейнер для быстрой сортировки и сортировки с объединением:

#include "c_arclib.cpp"
template <class T> class dynamic_array
  {
  private:
    T* array;
    T* scratch;
  public:
    int size;
    dynamic_array(int sizein)
      {
      size=sizein;
      array = new T[size]();
      }
    void print_array()
      {
      for (int i = 0; i < size; i++) cout << array[i] << endl;
      }
    void merge_recurse(int left, int right)
      {
      if(right == left + 1)
        {
        return;
        }
      else
        {
        int i = 0;
        int length = right - left;
        int midpoint_distance = length/2;
        int l = left, r = left + midpoint_distance;
        merge_recurse(left, left + midpoint_distance);
        merge_recurse(left + midpoint_distance, right);
        for(i = 0; i < length; i++)
          {
          if((l < (left + midpoint_distance)) && (r == right || array[l] > array[r]))
            {
            scratch[i] = array[l];
            l++;
            }
          else
            {
            scratch[i] = array[r];
            r++;
            }
          }
        for(i = left; i < right; i++)
          {
          array[i] = scratch[i - left];
          }
        }
      }
    int merge_sort()
      {
      scratch = new T[size]();
      if(scratch != NULL)
        {
        merge_recurse(0, size);
        return 1;
        }
      else
        {
        return 0;
        }
      }
    void quick_recurse(int left, int right) 
      {  
      int l = left, r = right, tmp;
      int pivot = array[(left + right) / 2];
      while (l <= r)
        {
        while (array[l] < pivot)l++;
        while (array[r] > pivot)r--;
        if (l <= r) 
          {
          tmp = array[l];
          array[l] = array[r];
          array[r] = tmp;
          l++;
          r--;
          }
        }
      if (left < r)quick_recurse(left, r);
      if (l < right)quick_recurse(l, right);
      }  
    void quick_sort()
      {
      quick_recurse(0,size);
      }
    void rand_to_array()
      {
      srand(time(NULL));
      int* k;
      for (k = array; k != array + size; ++k)                                             
        { 
        *k=rand();                                      
        } 
      }
  };
int main()
  {
  dynamic_array<int> d1(10);
  cout << d1.size;
  d1.print_array();
  d1.rand_to_array();
  d1.print_array();
  d1.merge_sort();
  d1.print_array();
  }


469
7
задан 1 ноября 2011 в 11:11 Источник Поделиться
Комментарии
2 ответа

Мой первый комментарий его имени плохо.

dynamic_array подразумевает, что я могу использовать оператор [] на нем и получить отдачу.

Вы владели сырые указатели в вашей структуре.

private:
T* array;
T* scratch;

Во-первых это означает, что вы должны искать РАИИ, чтобы убедиться, что эти элементы были правильно удалены.

Во-вторых, вам нужно посмотреть правило трех (или 5 в C++11), чтобы убедиться, что они правильно скопированы.

Вы владели сырые указатели в вашей структуре. Это означает, что вы должны правильно управлять объектом в качестве ресурса. Это означает, конструкций/удаление/копирование (создание и присвоение) нужно заботиться правильно.

Либо сделать это вручную или использовать стандартный контейнер, который будет делать это за вас. Я предлагаю стандартный контейнер.

void print_array()
{
for (int i = 0; i < size; i++) cout << array[i] << endl;
}

Если вы собираетесь писать print_array по крайней мере написать его так, что он может использовать другой поток (не только с std::соиь). Затем запишите оператор вывода.

std::ostream& operator<<(std::ostream& stream, dynamic_array const& data)
{
data.print_array(stream); // After you fix print_array
return stream;
}

Также обратите внимание, что метод доступа к данным, но не изменяет состояние объекта, должны быть помечены как const. Так что подпись должна быть: от Void print_array() константный

Члены действительно часть массива?

void merge_recurse(int left, int right)
int merge_sort()
void quick_recurse(int left, int right)

ОК. Предположим, что они являются сейчас.
Затем пустоты merge_recurse(инт слева, инт справа) должен быть собственный член. Не должно быть никаких причин называть это извне.

  scratch = new T[size]();
if(scratch != NULL)

нуля никогда не будет null.

Я думаю, что слияния (в merge_recurse) легче написать, чем вы делаете это:

    int index = 0;
int l = left;
int r = midpoint;
while((l < midpoint) && (r < right))
{
scratch[index++] = (array[l] > array[r]))
? array[l++]
: array[r++];
}
// One of the two ranges is empty.
// copy the other into the destination.
while(l < midpoint)
{
scratch[index++] = array[l++];
}
while(r < right)
{
scratch[index++] = array[r++];
}

Вам нужно только позвонить srand() один раз в приложении:

void rand_to_array()
{
srand(time(NULL));

Поставив srand() внутри структуры вы открываете его, чтобы быть вызван несколько раз. После звонка он сразу после основной (), то и не звоните сюда.

Когда вы можете использовать стандартные инструменты:

      tmp = array[l];
array[l] = array[r];
array[r] = tmp;

Можно заменить:

 std::swap(array[l], array[r]);

Я относительно уверен, что эти двое не так:

  while (l <= r)
if (l <= r)

Они должны быть:

  while (l < r)
if (l < r)

3
ответ дан 2 ноября 2011 в 12:11 Источник Поделиться

Это просто комментарий по поводу стиля кодирования. Потому что... ваш код читать невозможно. И из-за плохой стиль кодирования, вы получите меньше ответов, когда вы разместите его на таких сайтах, как этот.

Как минимум, вы должны иметь пустых строк между каждым объявлением функции или программы выглядят как одна большая жижа. В том числе и пустые строки здесь и там, внутри тела функции, чтобы указать, какие части кода, которые принадлежат вместе.

Вы должны также рассмотреть изменение стиля отступов для чего-то более обычного. Наиболее распространенная форма однозначно не отступа брекеты, но отступ содержимого между ними. Другой менее распространенный, но приемлемый стиль для отступа скобки и затем понизить содержание между ними.

Вот пример того, что ваш код будет выглядеть, используя один из самых распространенных стилей:

#include "c_arclib.cpp"

// space here

template <class T> // template specification is most often put on a row of its own
class dynamic_array
{
private:
T* array;
T* scratch;

// space here, private and public dont belong together

public:
int size;

dynamic_array (int sizein)
{
size=sizein;
array = new T[size]();
}

// space between all functions!!!

void print_array ()
{
for (int i = 0; i < size; i++) // always use braces to avoid bugs!
{
cout << array[i] << endl;
}
}

void merge_recurse (int left, int right)
{
if(right == left + 1)
{
return;
}
else
{
int i = 0;
int length = right - left;
int midpoint_distance = length/2;
int l = left, r = left + midpoint_distance;

// space here, end of variable declarations

merge_recurse(left, left + midpoint_distance);
merge_recurse(left + midpoint_distance, right);

for(i = 0; i < length; i++)
{
/* The if statement would really benefit from getting split up in several
statements. Replace the bool variable names below with something meaningful.
(I haven't bothered to look at what your code actually does). */

bool less_midpoint = l < (left + midpoint_distance);
bool equal = r == right;
bool larger = array[l] > array[r];

if(less_midpoint && (equal || larger))
{
scratch[i] = array[l];
l++;
}
else
{
scratch[i] = array[r];
r++;
}
}

for(i = left; i < right; i++)
{
array[i] = scratch[i - left];
}
} // else /* <- Write "else" or similar in a comment to indicate to what
code a brace belongs to inside a complex, long nested code */
} // merge_recurse

int merge_sort ()
{
scratch = new T[size]();
if(scratch != NULL)
{
merge_recurse(0, size);
return 1;
}
else
{
return 0;
}
}

void quick_recurse (int left, int right)
{
int l = left, r = right, tmp;
int pivot = array[(left + right) / 2];

while (l <= r)
{
while (array[l] < pivot) // always use braces to avoid bugs!
{
l++;
}
while (array[r] > pivot) // always use braces to avoid bugs!
{
r--;
}

if (l <= r)
{
tmp = array[l];
array[l] = array[r];
array[r] = tmp;
l++;
r--;
}
} // while (l <= r)

if (left < r)
{
quick_recurse(left, r);
}
if (l < right)
{
quick_recurse(l, right);
}
}

void quick_sort ()
{
quick_recurse(0,size);
}

void rand_to_array ()
{
srand(time(NULL));
int* k;

for (k = array; k != array + size; ++k)
{
*k=rand();
}
}
};

int main()
{
dynamic_array<int> d1(10);
cout << d1.size;
d1.print_array();
d1.rand_to_array();
d1.print_array();
d1.merge_sort();
d1.print_array();
}

2
ответ дан 4 ноября 2011 в 12:11 Источник Поделиться