Сортировка массива указателей c

Сортировка массива указателей c

Начал изучать структуры, и выпала задача, где нужно сортировать структуру по определенному полю. Использовал обычную сортировку, но она оказывается нерациональна. Можете кто-нибудь привести пример сортировки структуры через указатели? Как это вообще делается? Допустим, дана структура со студентами и ее надо отсортировать по количеству баллов за тест. Как это сделать наиболее рационально, если просто сортировка по полю считается нерациональной. Надо использовать указатели, но как это организовать?

«Не в совокупности ищи единства, но в единообразии разделения».
Козьма Прутков.

Массив указателей как тип данных и как структура данных

Если это записать в терминах контекстного определения переменных, то получим, например

Многообразие вариантов реализации массивов указателей возникает по нескольким причинам:

· c ам массив указателей, указуемые переменные и ссылки (указатели) могут быть заданы статически (в тексте программы), либо динамически созданы во время ее выполнения;

· двоякая интерпретация указателя как указателя на отдельную переменную и на массив переменных (строку), позволяет создавать одномерные СД – массивы указателей на переменные и двумерные – массивы указателей на массивы (строки) таких переменных;

· указуемые переменные могут быть «собственностью» структуры данных, однако массив указателей может ссылаться и на переменные (объекты), являющиеся составными частями других структур данных.

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

Типы данных, используемые при работе с массивами указателей

Один тип данных уже был нами упомянут – это массив указателей, переменная вида int * p []. Кроме нее используется еще одни тип вида int ** pp , который можно определить в общем виде как указатель на указатель.

Напомним, что в Си имеют место две интерпретации указателя, различить которые в тексте программы можно только по виду применяемых к указателю операций (т.е. только в контексте его использования):

· традиционной интерпретации указателя как ссылки на отдельную переменную соответствует операция косвенного обращения по указателю * pp ;

· согласно концепции адресной арифметики любой указатель может ссылаться на неограниченный массив (память) с относительной адресацией от текущего положения указателя, что поддерживается операциями индексации pp [ i ] и добавления целого к указателю – p ++, p += n .

Указатель на указатель таким образом допускает целых четыре интерпретации. При этом для каждой из них должна быть создана (инициализирована) своя структура данных. Положение усугубляется еще и тем, что за соответствием структуры данных и операциями над ней должен следить программист (компилятор этого не делает).

int a=5, b=10; int *p=&a; int **pp=&p;

Первый вариант – указатель на указатель на отдельную переменную, имеет довольно специфическое применение. Обычно от используется для передачи адреса заголовка какой-либо структуры данных при необходимости его изменения. В формальных параметрах для этой цели предпочтительнее использование ссылки на указатель (см. 6.3).

int a[10]=5, b[10]=10; int *p=a; int **pp=&p;


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

int a=5, b=10, с =15; int *p[]=<&a,&b,&c,NULL>; int **pp=p;

for (int s=0,i=0;i s=s+*pp[i];

Массив указателей на линейные массивы переменных является двумерной структурой данных и использует двойную индексацию. Функционально она является эквивалентом двумерного массива.

for (int j=0;j s=s+pp[i][j];

Статические и динамические массивы указателей

Промежуточные варианты массива указателей могут содержать как статические, так и динамические компоненты. В следующем примере статический массив указателей программно заполняется адресами элементов статического же массива (динамически формируются только сами указатели).

Читайте также:  Как отменить гиперссылку в word

Указуемые переменные могут создаваться динамически, их адреса заполняют статический массив указателей.

for (i=0; i *p = i; pd[i] = p; >

for (i=0; i // из 20 указателей типа int*

pp[i] = p; // можно pp[i]=new int; *pp[i]=i;

Массив указателей. Физический и логический порядок

При работе с массивом указателей используются два контекста:

//— Сортировка массива и массива указателей

void sort1 (double d[],int sz)<

void sort2 (double *pd[])<

for ( k=0, i=0; pd[i+1]!=NULL;i++)

if (* pd [ i ] > * pd [ i +1]) // Сравнение указуемых переменных

c = pd[i]; pd[i] = pd[i+1];pd[i+1] = c; k = 1; >

Динамический массив указателей на переменные (объекты)

Если динамический массив указателей ссылается на множество «уже известных», т.е. не им созданных и не ему принадлежащих переменных (объектов), то его уместно рассматривать как коллекцию, имеющую собственный логический порядок. В качестве примера рассмотрим функцию, которая создает массив указателей на упорядоченные по возрастанию положительные значения, взятые из массива. Как и для любого динамического массива, для массива указателей справедливы все выводы о его размерности: в данном случае она может быть вычислена заранее. Результат функции имеет тип double ** — указатель на динамический массив указателей, созданный внутри функции.

//——— Динамический массив указателей

// на упорядоченные положительные элементы исходного массива

double **create( double in[], int n)<

int i , j , m ; // Вычислить размерность

double **pp = new double *[m+1]; // Создать ДМУ

for (i=0,j=0; i // Запомнить указатель на

if (in[i]>0) pp[j++]=&in[i]; // положительный элемент

Динамический массив указателей на массивы переменных

//— Матрица произвольной размерности — массив указателей на массивы

double ** load ( char nm [], int & n , int & m )< // Размерности матрицы – по ссылке

if (fd==NULL) return NULL;

fscanf(fd,"%d%d",&n,&m); // Чтение размерностей

double **pp=new double*[n]; // Создание ДМУ по первой размерности

pp[i]=new double[m]; // Создание линейных ДМ (строк)

double sum(double **p , int n, int m )<

В данном представлении указуемые объекты – строки матрицы являются «собственностью» структуры данных. Процедура освобождения памяти из-под такой полностью динамической структуры данных происходит в два этапа: сначала в цикле уничтожаются динамические массивы – строки, а затем – сам массив указателей.

void destroy(double **pp,int n)<

В следующем примере динамический массив указателей ссылается на компоненты уже существующей структуры данных. С его помощью мы получаем логическое представление структуры данных, отличное от ее исходного физического представления.

// Простое однократное слияние — массив указателей

// на линейные массивы (части линейного массива)

vo > // любая сортировка одномерного массива

void big_sort(int A[], int N)<

int *L=new int[n],*C=new int[N]; // массив размерностей частей

L[n-1]=N-n*(n-1); // Размерность последнего массива

for (i=0; i // Сортировка частей

for (i=0; i // Слияние

for (k=-1, j=0; j // k — индекс строки с минимальным

if (L[j]==0) continue; // Пропуск слитых строк

C[i] = *B[k]; // Перенос элемента

B[k]++; // Сдвиг k- го указателя

for (i=0; i // Возвратить обратно

Представление текста. Динамический массив указателей на строки

Массив указателей может ссылаться на строки, для размещения которых используется двумерный массив символов (массив строк).

char **pc, cc[100][80];

pc = new char *[101]; // Динамический массив указателей

for ( i =0; i i ++) pc [ i ] = cc [ i ]; // на строки статического массива

Здесь используются две особенности организации двумерных массивов. Во-первых, двумерный массив интерпретируется как массив элементов первого индекса, состоящих из элементов второго индекса, в данном случае -100 массивов символов по 80 символов в каждом. Во-вторых, идентификатор двумерного массива с одним индексом интерпретируется как указатель на начало соответствующего массива элементов второго индекса, в данном случае — указатель на i-й массив из 80 символов (строку).

Читайте также:  Sb0090 creative audigy драйвер

Синтаксис операции извлечения символа из массива указателей на строки идентичен синтаксису двумерного массива символов, т.е. имеет место отмеченный выше функциональная идентичность массива указателей и двумерного массива. Первая индексация извлекает из массива i -ый указатель, вторая извлекает j -ый символ из строки, адресуемой указателем.

p[i] // указатель на i-ю строку в массиве указателей

A [ i ] // указатель на начало i -ой строки в двумерном массиве

p[i][j] // j-й символ в i-ой строке массива указателей

A [i][j] // j-й символ в i-ой строке двумерного массива

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

//— Массив указателей на отсортированные по длине слова

int my_strlen(char *p)<

char **SortedWords(char *p)<

int nw=0,k; char *q;

for (q=p; *q!=0; q++) // Подсчет количества слов по концам слов

char **qq=new char*[nw+1]; // Создать ДМУ на строки (символы строки)

if (*p!= ‘ ‘) qq[nw++]=p; // Строка начинается со слова

for (p++; *p!=0; p++) // Если начало слова —

if (p[0]!=’ ‘ && p[-1]==’ ‘) // запомнить текущий указатель в строке

k=0; // с использование собственной функции

for (int i=0; i // сравнения слов (до пробела)

char *g=qq[i]; qq[i]=qq[i+1]; qq[i+1]=g;

Проблема размерности динамического массива указателей

//——- Создание ДМУ из строк файла

char * *loadfile(FILE *fd)<

int n,sz=SIZE0; // Кол-во строк и размерность ДМУ

char **pp = new char*[sz]; // Создать ДМУ

for (n=0;fgets(str,1000,fd)!=NULL; n++)<

pp[n]=strdup(str); // Копия строки в ДМ

sz*=2; // удвоить размерность

pp[n] = NULL; // Ограничитель массива указателей

При вычислении размерности нового массива указателей в функции realloc используется размерность типа хранимого элемента – указателя sizeof(char*) , а возвращаемый адрес приводится к типу – указатель на указатель char **.

Лабораторный практикум

1. Функция получает линейный массив целых, находит в нем последовательности подряд возрастающих значений и возвращает их в динамическом массиве указателей на линейные массивы (аналог двумерного массива). В каждом из линейных динамических массивов содержится копия возрастающей последовательности, начиная с индекса 1, а под индексом 0 содержится его длина. Невозрастающие значения включаются в отдельный массив, добавляемый в конец (или начало) массива указателей.

2. Функция получает строку текста и возвращает динамический массив указателей на слова. Каждое слово копируется в отдельный массив в динамической памяти.

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

4. Функция находит в строке фрагменты, симметричные относительно центрального символа, длиной 7 и более символов (например, " abcdcba ") и возвращает динамический массив указателей на копии таких фрагментов.

5. Функция находит в строке пары фрагментов, содержащих последовательность одинаковых символов длиной более 3 (кроме пробела) и возвращает динамический массив указателей на копии таких фрагментов.

Читайте также:  Yyyy mm dd format

6. Стек моделируется при помощи динамического массива указателей на линейные массивы размерности N целых. Указатель стека – два индекса – в массиве указателей и линейном массиве. В операции push при переполнении текущего линейного массива в массив указателей добавляется новый, если операция pop переходит к предыдущему массиву, то текущий утилизуется.

7. Очередь моделируется при помощи динамического массива указателей на линейные массивы размерности N целых. Указатели на первый и последний элементы очереди – два индекса – в массиве указателей и линейном массиве. В операции добавления при переполнении текущего линейного массива в массив указателей добавляется новый, в операции извлечения – при переходе к следующему линейному массиву текущий утилизуется (указатели в массиве указателей смещаются к началу).

8. Функция читает из файла текст по словам и возвращает двухуровневый динамический массив указателей на строки, содержащие слова из исходного файла (тип данных char *** — см. 87. иерархические структуры данных). Размерность массива указателей нижнего уровня задана, каждый массив указателей ограничен NULL . Затем сортирует массивы указателей нижнего уровня, затем производит окончательную сортировкупутем однократного слияния (см. 4.6 Сортировка и поиск).

9. Функция читает из файла текст по словам и возвращает двухуровневый динамический массив указателей на строки на строки, содержащие слова из исходного файла, упорядоченные по алфавиту (тип данных char *** — см. 87. иерархические структуры данных). Размерность массива указателей нижнего уровня задана, каждый массив указателей ограничен NULL . Очередная строка вставляется с сохранением порядка, в первом цикле просматривается массив указателей первого уровня и в каждом – элемент с индексом 0 второго уровня. Если его значение больше нового, то выполянется вставка в предыдущий массив указателей нижнего уровня. Если при вставке происходит переполнение, массив создается новый массив указателей, в который копируется половина указателей текущего.

Вопросы без ответов

Содержательно сформулируйте действие, производимое функцией над массивом указателей. Напишите вызов функции для статических данных.

double * F(double *p[], int k) <

for ( int i=0; p[i]!=0; i++) ; // Текущая размерность массива указателей

if (k>=i) return NULL; // Больше текущей размерности — неудача

double *q=p[k]; // Запомнить k- ый указатель

for (; k // Сдвинуть " хвост" на 1 к началу — удалить

return q;> // k-ый и вернуть его

for (int i=0; pp[i]!=NULL;i++) printf(" %2.0lf",*pp[i]);

Функция возвращает указатель на double . Поскольку она получает массив указателей, можно предположить, что он берется оттуда. Действительно, из массива копируется указатель, номер которого задан формальным параметром. То есть функция возвращает указатель по заданному логическому номеру. Первоначально подсчитывается текущая размерность структуры данных – количество указателей в массиве. Если логический номер его превышает, возвращается NULL . И последнее. После запоминания k -го указателя все последующие указатели сдвигаются на 1 к началу, таким образом, выделенный указатель «затирается». То есть функция исключает указатель по логическому номеру и возвращает его в качестве результата. Для задания статической структуры данных сначала определяются указуемые переменные типа double , а замет массив указателей инициализируется их адресами.

void selectionSort(int * const, const int);

void swap(int * const, int * const);

const int arraySize = 10;

printf("Original state os array:
");

selectionSort(array, arraySize); //сортировать массив

printf("

Array after sort:
");

void selectionSort(int * const array, const int size)

int smallest; //индекс наименьшего элемента

//цикл до -1 элемента

smallest = i; //первый индекс оставшегося массива

//определение индекса наименьшева элемента:

for(int index = i+1; index

void swap(int * const elem1Ptr, int * const elem2Ptr)

Ссылка на основную публикацию
Сони плейстейшен нетворк вход
Игры по сети, развлечения, друзья, покупки и многое другое – ваше сетевое приключение начинается в PSN. Подключитесь к нашему сетевому...
Смарт часы фикситайм 3 отзывы
Данный товар недоступен для доставки в Ваш регион Мы всегда стремимся к лучшему, чтобы радовать своих покупателей самыми выгодными ценами....
Смарт часы эпл для детей
1 min Apple Watch — самые популярные умные часы в мире. Является ли это идеальным выбором для вашего ребенка, зависит...
Сони f3112 xperia xa
Недорогой смартфон компании Sony (22 990 рублей за Dual версию) с интересным дизайном, LTE, двумя отдельными слотами для SIM-карт, слотом...
Adblock detector