C - пузырьковая сортировка массива символьных строк, затем применяется к массиву int без знака

Question

Предполагается, что программа возьмет файл, скажем data.dat, заполненный списком до 320 слов, каждое из которых будет меньше или равно 29 символам (30 с нулевым символом), и добавит каждое из этих слов в глобальный. массив. Затем я хочу отсортировать этот список по алфавиту с пузырьковой сортировкой. Я сделал это с помощью следующей функции в своем собственном файле sort.c

#include "set.h"
#include "sortAndSearch.h"
#include <stdio.h>
#include <ctype.h>
#include <string.h>

void bubbleSort(char A[][30], int num) {
int i, j;
char temp[30];

for(i = 0; i < num; i++)
    for(j = 0; j < num-1; j++)
        if(strcmp(A[i], A[i+1]) > 0){
            //swap the two array elements
            strcpy(temp, A[j]);
            strcpy(A[j], A[j+1]);
            strcpy(A[j+1], temp);
        }
}

Мне нужен набор беззнаковых целых

unsigned int Set[10];

действовать как индекс для массива имен. Таким образом, каждое беззнаковое целое имеет 32 бита, и есть 10 беззнаковых целых, в общей сложности 320 битов, и каждый бит будет ссылаться на слово. Я не уверен, как подойти к этой части.

Конечной целью является создание функций для управления наборами. Я чувствую, что могу атаковать это сам, если смогу отсортировать и проиндексировать, поскольку я сделал нечто подобное, но без использования символьных массивов. Содержимое заголовочного файла set.h, который определяет используемые функции, следует

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// defining new type(s)
typedef unsigned int Set[10];

// declaring global variable(s)
extern char names[320][30];

extern void setUnion(Set set1, Set set2, Set result);
extern void setIntersection(Set set1, Set set2, Set result);
extern void clearSet(Set set);
extern void add2Set(Set set, int value);
extern void deleteFromSet(Set set, int value);
extern int isMember(Set set, int element);
extern void printSet(Set);
extern int nameIsMember(Set set, char *);
extern void addName2Set(Set set, char *);
extern void deleteNameFromSet(Set set, char *);

А вот содержимое заголовочного файла sortAndSearch.h

void bubbleSort(char A[][30], int num);

int binarySearch(char A[][30], char *, int, int );

Answer 1

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

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

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

Answer 2

Проблема с этой частью:

for(i = 0; i < num-1; i++)
        if(strcmp(A[i], A[i+1]) > 0){
            //swap the two array elements
            strcpy(temp, A[i]);
            strcpy(A[i], A[i+1]);
            strcpy(A[i+1], temp);
        }

Там должно быть две петли для сортировки пузырьков!;-) См. здесь , например, с целыми числами.

Answer 3

Пузырьковая сортировка реализована неправильно.Должны быть внутренний цикл и внешний цикл.

Мне неясно, для чего предназначен набор из 320 битов: он не может использоваться для сортировки или для чего-либо другого, кроме каждого бита, указывающего некоторый атрибутмассива истина, например, присутствует ли он, или содержит глагол или что-то.

Answer 4

Справедливо ли было бы обобщить, что сортировка имен не зависит от операций над множествами?

Пока имена не меняются, операции набора будут работать?

Операции, которые вы перечислили, подразделяются на следующие группы:

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

extern void setUnion(Set set1, Set set2, Set result);
extern void setIntersection(Set set1, Set set2, Set result);
extern void clearSet(Set set);

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

Операции с элементами набора, они манипулируют одним битом в наборе, и опять же не очень важно, что представляют собой биты:

extern void add2Set(Set set, int value);
extern void deleteFromSet(Set set, int value);
extern int isMember(Set set, int element);

Это хорошее место для начала.

Эти операции отображаются между именами и множеством, поэтому для работы нужно больше вещей:

extern int nameIsMember(Set set, char *);
extern void addName2Set(Set set, char *);
extern void deleteNameFromSet(Set set, char *);

Я не уверен, что означает extern void printSet(Set);, печатает ли он имена из набора?

Хорошо, набор

unsigned int s[10];

, чтобы проверить немного, нам нужно преобразовать значение типа int в индекс типа int и бит внутри int. Самый простой способ - это индекс массива = (значение / 32), смещение в битах (значение% 32). Компилятор должен хорошо поработать над тем, чтобы сделать это эффективным, поэтому не беспокойтесь об эффективности.

Чтобы получить битовое значение в s: (s [(значение / 32)] & (1 << (значение% 32)) </p>

Итак, вы понимаете битовые операторы ?

~ not
& and
| or
^ xor
<< left shift
>> right shift

Это операции, которые вы будете использовать для установки, очистки и изменения битов в наборе.