Лексикографическая сортировка числовых векторов, BC++ Опции

[KerK]

Вектор А=(А1,А2,…,Аn) считается лексикографически большим вектора В=(В1,В2,…,Вn), если существует k>=0 такое что Аi=Вi(i<=k),Ak+1>Bk+1. Составить программу лексикографической сортировки числовых векторов. При составлении программы сортировки использовать минимальную необходимую память и эффективные структуры данных.

Давал пост в разделе задачи Лексикографическая сортировка числовых векторов., мне помогли с заданием но реализация была на паскале... вот попробовал перевести в сишку... возникли вопросы.... в сишке ни разу не пробовал процедуры... правильно ли я написал? и нет под рукой книги или хелпа, хотелось бы узнать что дает в паскале команда inc, и как она должна выглядеть в С. Потом не совсем понял какая структура должна быть у программы на С. НАпример на паскале

...
...
procedure
main();
end;
Begin
End.

а как на си?

И посмотрите пожалуйста мой код.... где какие ошибки? и как продолжить главный модуль программы?

#include <conio.h>
#include <iostream.h>
#include <math.h>


void SortAt(int low_bound,int up_bound,int sort_by)
main()
{
 int i,j,t;

 if (sort_by=len+1) exit; 

 for (i=1;i=up_bound-low_bound+1;i++)
 for (j=low_bound;j=up_bound-1;j++)
  if (vv[sorted[j]][sort_by]>vv[sorted[j+1]][sort_by])
  {
  t=sorted[j];
  sorted[j]=sorted[j+1];
  sorted[j+1]=t;
  }

  i=low_bound;
  while (i<=up_bound)
  {
   j=i;
   while (i<up_bound)&&(vv[sorted[j+1]][sort_by]=vv[sorted[j]][sort_by])
   inc(j); //???????????????????
   SortAt(i,j,sort_by+1);
   i=i+1;
  }
}

 int vv[3][3];
 int sorted[3]; 

[Michael_Rybak]

Если тебе на сях надо было, ты б так и говорил, я б на сях и пример приводил.

Ну че, давай по порядку. main() - это стандартное для си название главной функции программы. Такая функция всегда есть, и всегда одна. Например:

На паскале

program a_plus_b;

var a, b: integer;
    z: array [1..5, 1..10] of integer; //просто для примера

function CalculateSum(a, b: integer): integer;
  var s: integer;
begin
  s := a + b;
  CalculateSum := s;
end;

procedure PrintResult(a, b, s: integer);
begin
  Writeln(a, ' + ', b, ' = ', s);
end;

begin
  Readln(a, b);
  PrintResult(a, b, CalculateSum(a, b));
end.

На си:

#include "stdio.h"

int a, b;
int z[5][10]; //просто для примера

int CalculateSum(int a, int b) //тип возвращаемого значения указываем *перед* именем функции
{
  int s;
  s = a + b;
  return s; //вместо CalculateSum := s просто делаем return s
}

void PrintResult(int a, int b, int s) //процедуры объявляются с ключевым словом void вместо типа
{
  printf("%d + %d = %d\n", a, b, s);
}

int main() //вместо главной пары begin-end объявляем функцию main
{
  scanf("%d %d", &a, &b);
  PrintResult(a, b, CalculateSum(a, b));
  return 0;//возвращаем 0, означающий, что программа нормально завершила работу
}

Очень внимательно изучи это код на предмет оформления и вызова процедур, да и общей структуры программы.

Теперь, что касается перевода.

1. Перенеси объявление массивов vv и sorted наверх, иначе из тела функции их не будет видно

2. Строку main() убери, и объяви функцию main отдельно, как я показал в примере выше.

3. Во всех проверках "=" записывается в си как "==". Здесь:

if (sort_by=len+1) exit;  

и здесь:

vv[sorted[j+1]][sort_by]=vv[sorted[j]][sort_by]

4. exit, означающий преждевременный выход из процедуры, в си записывается как return;

5. Вот такой цикл

for i := 1 to up_bound - low_bound + 1 do

Записывается так

for (i=1;i<=up_bound-low_bound+1;i++)

У тебя все правильно, но стоит "=" вместо "<=".

6. То же самое:

for j := low_bound to up_bound - 1 do

Записывается так:

for (j=low_bound;j<=up_bound-1;j++)

Тоже было "=", надо "<=".

7. Вот здесь:

while (j < up_bound) and (vv[sorted[j + 1], sort_by] = vv[sorted[j], sort_by]) do

Ты заменил случайно j на i. Верни И не забудь про "==" вместо "="

8. Inc(j); - это просто j++.

9. Вот здесь:

i := j + 1;

Ты тоже случайно заменил j на i. Верни.


Давай, заменяй и приходи обратно. Какой у тебя си? Может си++? И ты уверен, что ты должен осилить именно "минимальную необходимую память и эффективные структуры данных"? Намучаешься немеряно, обещаю ;)

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

#include <stdio.h>

const int MAX_N = 100;
const int MAX_LEN = 100;

int vv[MAX_N][MAX_LEN];
int n;
int len;

int LexSmaller(int x, int y)
  //вернуть 1, если vv[x] лексикографичекси меньше, чем vv[y], и 0 в противном случае
{
  for (int i = 0; i < len; ++i)
    if (...)
      return 1; //лексикографически меньше
    else if (...)
      return 0; //лексикографически больше

  //отличий не нашли, значит вектора равны; возвращаем 0
  return 0;
}

void Swap(int x, int y)
  //поменять местами векторы vv[x] и vv[y]
{
  //проходим по векторам и меняем попарно все элементы
  for (int i = 0; i < len; ++i)
  {
    //меняем местами vv[x][i] и vv[y][i]
    ...
    ...
    ...
  }
}

void ReadVectors()
{
  printf("Введите количество векторов: ");
  scanf("%d", &n);
  printf("Введите размерность (длину) векторов: ");
  scanf("%d", &len);

  for (int i = 0; i < n; ++i)
    for (int j = 0; j < len; ++j)
    {
      printf("vv[%d][%d] = ", i, j);
      scanf("%d", &vv[i][j]);
    }
}

void BubbleSort()
  //сортировка пузырьком
{
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n - 1; ++j)
      if (LexSmaller(j + 1, j) == 1) //следующий вектор лекс. меньше текущего
        //меняем их местами
        Swap(j, j + 1);  
}

void PrintResult()
{
  printf("Результат сортировки:");
  ...
  ...
  ...
}


int main()
{
  ReadVectors();
  BubbleSort();
  PrintResult();
  return 0;
}

Не заметил в названии темы ВС++. Тогда вообще хорошо, можно std::sort юзать. Там ведь есть stl (последний раз, когда я видел BC++, я не знал, что такое stl )? Впрочем, это уже другая история. Давай пока пузырьком.