Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

Сортировка строк и Сортировка структур на примере языка Си

Лекция



Привет, сегодня поговорим про сортировка строк, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое сортировка строк, сортировка структур на е языка си , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

Сортировка других структур данных

До сих пор мы сортировали только массивы символов. Очевидно, что приведенные выше функции можно переделать для сортировки массивов любого из встроенных типов данных, просто поменяв типы параметров и переменных. Тем не менее, обычно возникает необходимость сортировать составные типы данных, например строки, или агрегированные данные, например структуры. Большинство задач сортировки имеют дело с ключом и информацией, связанной с этим ключом. Чтобы адаптировать алгоритмы для обработки подобных данных, необходимо модифицировать код сравнения, код обмена или оба фрагмента. Сам алгоритм при этом не меняется.

Поскольку быстрая сортировка в настоящее время является одним из лучших методов сортировки общего назначения, она используется в последующих примерах. Тем не менее, тот же принцип относится и ко всем остальным методам, описанным ранее.

сортировка строк

Сортировка строк является распространенной задачей программирования. Строки легче всего сортировать, когда они хранятся в таблице строк. Таблица строк — это просто массив строк. А массив строк — это двумерный массив символов, в котором количество строк в таблице определяется размером левого измерения, а максимальная длина строки — размером правого измерения. (О массивах строк рассказывалось в главе 4.) Нижеследующая строковая версия быстрой сортировки принимает массив строк, в котором размер каждой строки ограничен десятью символами. (Можете изменить эту длину, если хотите.) Данная версия сортирует строки в лексикографическом порядке.

/* Быстрая сортировка строк. */
void quick_string(char items[][10], int count)
{
  qs_string(items, 0, count-1);
}

void qs_string(char items[][10], int left, int right)
{
  register int i, j;
  char *x;
  char temp[10];

  i = left; j = right;
  x = items[(left+right)/2];

  do {
    while((strcmp(items[i],x) < 0) && (i < right)) i++;
    while((strcmp(items[j],x) > 0) && (j > left)) j--;
    if(i <= j) {
      strcpy(temp, items[i]);
      strcpy(items[i], items[j]);
      strcpy(items[j], temp);
      i++; j--;
   }
  } while(i <= j);

  if(left < j) qs_string(items, left, j);
  if(i < right) qs_string(items, i, right);
}

Обратите внимание, что во фрагменте сравнения теперь используется функция strcmp(). Об этом говорит сайт https://intellect.icu . Эта функция возвращает отрицательное число, если первая строка лексикографически меньше второй, возвращает ноль, если строки равны, и положительное число, если первая строка лексикографически больше второй. Также следует отметить, что для обмена двух строк требуется три вызова функции strcpy().

Имейте в виду, что функция strcmp() замедляет сортировку по двум причинам. Во-первых, в программе появляется вызов функции, что всегда отнимает время. Во-вторых, сама функция strcmp() выполняет несколько сравнений, чтобы определить, какая из двух строк больше. В первом случае, если скорость очень важна, можно поместить код сравнения строк непосредственно в функцию сортировки, продублировав код функции strcmp(). Во втором случае нет никакого способа избежать сравнения строк, поскольку по определению это именно то, что требуется в данной задаче. Те же рассуждения относятся и к функции strcpy(). Обмен двух строк с помощью strcpy() включает в себя вызов функции и посимвольный обмен содержимого строк — каждая из этих операций занимает время. Накладные расходы на вызов функции можно устранить, вставив код копирования прямо в алгоритм сортировки. Однако тот факт, что обмен двух строк означает обмен отдельных символов (один за другим), изменить невозможно.

Ниже приведена простая функция main(), демонстрирующая работу функции быстрой сортировки строк quick_string():

#include <stdio.h>
#include <string.h>

void quick_string(char items[][10], int count);
void qs_string(char items[][10], int left, int right);

char str[][10] = { "один",
                   "два",
                   "три",
                   "четыре"
                 };

int main(void)
{
  int i;

  quick_string(str, 4);

  for(i=0; i<4; i++) printf("%s ", str[i]);

  return 0;
}

Сортировка структур

В большинстве прикладных программ, в которых используется сортировка, предусмотрена сортировка совокупностей данных. Например, списки почтовой рассыпки, складские базы данных и журналы сотрудников содержат наборы разнотипных данных. Как вам известно, в программах на языке С совокупности данных обычно хранятся в структурах. Хотя структура обычно содержит несколько членов, структуры, как правило, сортируются только по одному полю-члену, который используется в качестве ключа сортировки. За исключением выбора ключа, приемы сортировки структур ничем не отличаются от приемов сортировки других типов данных.

Чтобы проиллюстрировать пример сортировки структур, давайте создадим структуру под называнием address, в которой можно хранить почтовый адрес. Подобная структура может применяться в программе почтовой рассылки. Описание структуры address показано ниже:

struct address {
  char name[40];   /* имя */
  char street[40]; /* улица */
  char city[20];   /* город */
  char state[3];   /* штат */
  char zip[11];    /* индекс */
};

Поскольку представляется разумным организовать список адресов в виде массива структур, в данном примере предположим, что процедура сортировки будет сортировать массив структур типа address. Такая процедура показана ниже. Она сортирует адреса по почтовому индексу.

/* Быстрая сортировка структур типа фвкуыы. */
void quick_struct(struct address items[], int count)
{
  qs_struct(items,0,count-1);
}

void qs_struct(struct address items[], int left, int right)
{

  register int i, j;
  char *x;
  struct address temp;

  i = left; j = right;
  x = items[(left+right)/2].zip;

  do {
    while((strcmp(items[i].zip,x) < 0) && (i < right)) i++;
    while((strcmp(items[j].zip,x) > 0) && (j > left)) j--;
    if(i <= j) {
      temp = items[i];
      items[i] = items[j];
      items[j] = temp;
      i++; j--;
    }
  } while(i <= j);

  if(left < j) qs_struct(items, left, j);
  if(i < right) qs_struct(items, i, right);
}
 

На этом все! Теперь вы знаете все про сортировка строк, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое сортировка строк, сортировка структур на е языка си и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов

Из статьи мы узнали кратко, но содержательно про сортировка строк
создано: 2014-12-22
обновлено: 2021-01-10
132749



Рейтиг 9 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

Алгоритмы и теория алгоритмов

Термины: Алгоритмы и теория алгоритмов