Member 13768333 Ответов: 4

Бинарная инсекция сортировка в алфавитном порядке

Бинарная инсекция сортируется в алфавитном порядке.

У меня проблемы с кодом.
Пожалуйста, помогите мне.

Что я уже пробовал:

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

#define MAX_STRINGS 50
#define MAX_STRING_LEN 50

struct students 
{
   char studentmuber[21];
   char firstname[21777];
   char surname[21];
   char group[21];
};



void InsertionSort(char list[MAX_STRINGS][MAX_STRING_LEN]);

int main()
{
        struct students sg1[43]; 

//DT265A	�	part-time	Higher	Diploma	
//DT265A	�	12	students	


strcpy(sg1[0].studentmuber, "C17501096");
    strcpy(sg1[0].firstname, "Patrik");
    strcpy(sg1[0].surname, "Farrell");
    strcpy(sg1[0].group, "DT265A");
    
     strcpy(sg1[1].studentmuber, "C17719309");
    strcpy(sg1[1].firstname, "Iosif");
    strcpy(sg1[1].surname, "Balasca");
    strcpy(sg1[1].group, "DT265A");
    
      strcpy(sg1[2].studentmuber, "C17313136");
    strcpy(sg1[2].firstname, "Monika");
    strcpy(sg1[2].surname, "Adamczewska");
    strcpy(sg1[2].group, "DT265A");
    
    strcpy(sg1[0].studentmuber, "C17325641");
    strcpy(sg1[0].firstname, "Benjamin");
    strcpy(sg1[0].surname, "Cox");
    strcpy(sg1[0].group, "DT265A");
    
     strcpy(sg1[1].studentmuber, "C17368666");
    strcpy(sg1[1].firstname, "Immanuel");
    strcpy(sg1[1].surname, "Mahmoud");
    strcpy(sg1[1].group, "DT265A");
    
      strcpy(sg1[2].studentmuber, "C17452664");
    strcpy(sg1[2].firstname, "Mahmoud");
    strcpy(sg1[2].surname, "Almahroum");
    strcpy(sg1[2].group, "DT265A");
    
       strcpy(sg1[3].studentmuber, "C17470662");
    strcpy(sg1[3].firstname, "Ryan");
    strcpy(sg1[3].surname, "Farmar");
    strcpy(sg1[3].group, "DT265A");
    
    strcpy(sg1[4].studentmuber, "C17407044");
    strcpy(sg1[4].firstname, "Ryan");
    strcpy(sg1[4].surname, "Campbell");
    strcpy(sg1[4].group, "DT265A");
    
      strcpy(sg1[5].studentmuber, "C17484426");
    strcpy(sg1[5].firstname, "Daire");
    strcpy(sg1[5].surname, "English");
    strcpy(sg1[5].group, "DT265A");
    
    strcpy(sg1[6].studentmuber, "C17318676");
    strcpy(sg1[6].firstname, "Joseph");
    strcpy(sg1[6].surname, "Byrne");
    strcpy(sg1[6].group, "DT265A");
    
     strcpy(sg1[7].studentmuber, "C17431466");
    strcpy(sg1[7].firstname, "Janae");
    strcpy(sg1[7].surname, "Farinas");
    strcpy(sg1[7].group, "DT265A");
    
     strcpy(sg1[8].studentmuber, "C17504869");
    strcpy(sg1[8].firstname, "Alexanderu");
    strcpy(sg1[8].surname, "Cardas");
    strcpy(sg1[8].group, "DT265A");
   
    strcpy(sg1[9].studentmuber, "C17319656");
    strcpy(sg1[9].firstname, "Harry");
    strcpy(sg1[9].surname, "Bebbigton");
    strcpy(sg1[9].group, "DT265A");
    
       
    strcpy(sg1[10].studentmuber, "D17125070");
    strcpy(sg1[10].firstname, "Taif");
    strcpy(sg1[10].surname, "Beedh");
    strcpy(sg1[10].group, "DT265A");
    
    strcpy(sg1[11].studentmuber, "C17744044");
    strcpy(sg1[11].firstname, "Martynas");
    strcpy(sg1[11].surname, "Drazdziulis");
    strcpy(sg1[11].group, "DT265A");
    
    
//2. DT265C	�	part-time	Master�s	Qualifier	

//DT265C	�	10	students	

    strcpy(sg1[12].studentmuber, "C7335606");
    strcpy(sg1[12].firstname, "Daniel");
    strcpy(sg1[12].surname, "Foley");
    strcpy(sg1[12].group, "DT265C");
    
       strcpy(sg1[13].studentmuber, "C17431012");
    strcpy(sg1[13].firstname, "Joel");
    strcpy(sg1[13].surname, "Kell");
    strcpy(sg1[13].group, "DT265C");
    
    
          strcpy(sg1[13].studentmuber, "C17455002");
    strcpy(sg1[13].firstname, "Stephen");
    strcpy(sg1[13].surname, "Lynch");
    strcpy(sg1[13].group, "DT265C");
    
           strcpy(sg1[14].studentmuber, "C17438392");
    strcpy(sg1[14].firstname, "Gibson");
    strcpy(sg1[14].surname, "Neil");
    strcpy(sg1[14].group, "DT265C");
    
           strcpy(sg1[15].studentmuber, "C17458124");
    strcpy(sg1[15].firstname, "Ryan");
    strcpy(sg1[15].surname, "Machren");
    strcpy(sg1[15].group, "DT265C");
    
      strcpy(sg1[16].studentmuber, "C17407712");
    strcpy(sg1[16].firstname, "Ross");
    strcpy(sg1[16].surname, "Mac William");
    strcpy(sg1[16].group, "DT265C");
    
     strcpy(sg1[17].studentmuber, "C17744515");
    strcpy(sg1[17].firstname, "George");
    strcpy(sg1[17].surname, "Hawthorne");
    strcpy(sg1[17].group, "DT265C");
    
    strcpy(sg1[18].studentmuber, "C17744516");
    strcpy(sg1[18].firstname, "George");
    strcpy(sg1[18].surname, "Hawthornic");
    strcpy(sg1[18].group, "DT265C");
    
    
      strcpy(sg1[19].studentmuber, "C17501096");
    strcpy(sg1[19].firstname, "Patrick.");
    strcpy(sg1[19].surname, "Farrell");
    strcpy(sg1[19].group, "DT265C");
    
    
      strcpy(sg1[20].studentmuber, "C17463744");
    strcpy(sg1[20].firstname, "Ivan");
    strcpy(sg1[20].surname, "Garcia");
    strcpy(sg1[20].group, "DT265C");
    
    
      strcpy(sg1[21].studentmuber, "C17331306");
    strcpy(sg1[21].firstname, "Jerricho.");
    strcpy(sg1[21].surname, "Juliano");
    strcpy(sg1[21].group, "DT265C");
    
        strcpy(sg1[22].studentmuber, "C17740835");
    strcpy(sg1[22].firstname, "Mohammed.");
    strcpy(sg1[22].surname, "Kadiri");
    strcpy(sg1[22].group, "DT265C");
    
 //  3. DT265B	�	full-time	Master�s	Qualifier	 
// DT265B	�	14	students	 
    
     strcpy(sg1[23].studentmuber, "C17474812");
    strcpy(sg1[23].firstname, "James");
    strcpy(sg1[23].surname, "Mc Ardle");
    strcpy(sg1[23].group, "DT265B");
    
      strcpy(sg1[24].studentmuber, "C17303563");
    strcpy(sg1[24].firstname, "Richard");
    strcpy(sg1[24].surname, "Meyer");
    strcpy(sg1[24].group, "DT265B");
    
      strcpy(sg1[25].studentmuber, "C17737111");
    strcpy(sg1[25].firstname, "Dean");
    strcpy(sg1[25].surname, "Rourke");
    strcpy(sg1[25].group, "DT265B");
    
     strcpy(sg1[26].studentmuber, "C17427304");
    strcpy(sg1[26].firstname, "Meenal");
    strcpy(sg1[26].surname, "Mujahed");
    strcpy(sg1[26].group, "DT265B");
    
      
     strcpy(sg1[26].studentmuber, "D17123259");
    strcpy(sg1[26].firstname, "Tyra");
    strcpy(sg1[26].surname, "Neftzer");
    strcpy(sg1[26].group, "DT265B");
    
    
    strcpy(sg1[27].studentmuber, "C17441552");
    strcpy(sg1[27].firstname, "Conor");
    strcpy(sg1[27].surname, "O_Donell");
    strcpy(sg1[27].group, "DT265B");
    
      strcpy(sg1[28].studentmuber, "C7718445");
    strcpy(sg1[28].firstname, "Ciab");
    strcpy(sg1[28].surname, "Morrin");
    strcpy(sg1[28].group, "DT265B");
    
    
      strcpy(sg1[29].studentmuber, "C17323756");
    strcpy(sg1[29].firstname, "Gedimas.");
    strcpy(sg1[29].surname, "Petreikis");
    strcpy(sg1[29].group, "DT265C");
    
    strcpy(sg1[30].studentmuber, "C17706201");
    strcpy(sg1[30].firstname, "Jurijus");
    strcpy(sg1[30].surname, "Pacalovas");
    strcpy(sg1[30].group, "DT265B");
    
        strcpy(sg1[31].studentmuber, "C17426754");
    strcpy(sg1[31].firstname, "Eoghan");
    strcpy(sg1[31].surname, "Mellott");
    strcpy(sg1[31].group, "DT265B");
    
        strcpy(sg1[32].studentmuber, "C14045363");
    strcpy(sg1[32].firstname, "Richar");
    strcpy(sg1[32].surname, "Mayer");
    strcpy(sg1[32].group, "DT265B");
    
    
    strcpy(sg1[33].studentmuber, "C16409062");
    strcpy(sg1[33].firstname, "Brian");
    strcpy(sg1[33].surname, "Mc_Gee");
    strcpy(sg1[33].group, "DT265B");
    
     strcpy(sg1[34].studentmuber, "C17390923");
    strcpy(sg1[34].firstname, "Gleen");
    strcpy(sg1[34].surname, "Moore");
    strcpy(sg1[34].group, "DT265B");
    
     strcpy(sg1[35].studentmuber, "C17303406");
    strcpy(sg1[35].firstname, "Robert");
    strcpy(sg1[35].surname, "MC_Givney");
    strcpy(sg1[35].group, "DT265B");
    
     strcpy(sg1[36].studentmuber, "D16127812");
    strcpy(sg1[36].firstname, "Seng_Keong");
    strcpy(sg1[36].surname, "Onny_Lim");
    strcpy(sg1[36].group, "DT265B");
    
 //  4. DT8900	�	full-time	International	Master�s	Qualifier		Admission	numbers	are	as	follows:	  
//  DT8900	�	6	students
    
     
         strcpy(sg1[37].studentmuber, "C17718415");
    strcpy(sg1[37].firstname, "Jonathan");
    strcpy(sg1[37].surname, "Unsworth");
    strcpy(sg1[37].group, "DT8900");
    
         strcpy(sg1[38].studentmuber, "C17751103");
    strcpy(sg1[38].firstname, "Niall");
    strcpy(sg1[38].surname, "Williams");
    strcpy(sg1[38].group, "DT8900");
    
     strcpy(sg1[39].studentmuber, "17764691");
    strcpy(sg1[39].firstname, "Jason.");
    strcpy(sg1[39].surname, "Van Raamsdonk");
    strcpy(sg1[39].group, "DT8900");
    
     strcpy(sg1[40].studentmuber, "C17378303");
    strcpy(sg1[40].firstname, "Mariana.");
    strcpy(sg1[40].surname, "Pirtac");
    strcpy(sg1[40].group, "DT8900");
    
     strcpy(sg1[41].studentmuber, "C17433026");
    strcpy(sg1[41].firstname, "Philip.");
    strcpy(sg1[41].surname, "Toolan");
    strcpy(sg1[41].group, "DT8900");
    
     strcpy(sg1[42].studentmuber, "C17388633");
    strcpy(sg1[42].firstname, "Killian");
    strcpy(sg1[42].surname, "Pogue");
    strcpy(sg1[42].group, "DT8900");
    
    int index;
   char strings[MAX_STRINGS][MAX_STRING_LEN]={"", "Farrell","Balasca","Adamczewska","Cox","Almahroum","Farmar","Campbell","English","Byrne","Farinas","Cardas","Bebbigton","Beedh","Drazdziulis","Foley","Kell","Lynch","Neil","Machren","Mac","William","Hawthorne","Hawthornic","Farrell","Garcia","Juliano","Kadiri","Mc,Ardle","Meyer","Rourke","Mujahed","Neftzer","O_Donell","Morrin","Petreikis","Pacalovas","Mellott","Mayer","Mc_Gee","Moore","MC_Givney","Onny_Lim","Unsworth","Williams","Van,Raamsdonk","Pirtac","Toolan","Pogue","Z"};


    for (index = 0; index < MAX_STRINGS; index++)
    {
       strings[index][sizeof(strings[index]) - 1] = '\0';
        
        
    }

    InsertionSort(strings);

    printf("\nThe input set, in alphabetical order:\n");
    for (index = 1; index < MAX_STRINGS; index++)
    {
        printf("%s\n", strings[index]);
    }
    
     getch();
    
    
    
    
        return  0;
}

 int binarySearch(char stringslist[MAX_STRINGS][MAX_STRING_LEN], char item[MAX_STRINGS][MAX_STRING_LEN], int low, int high)
{
	if (high <= low)
		return (item[MAX_STRINGS][MAX_STRING_LEN] > stringslist[low][MAX_STRING_LEN])? (low + 1): low;

	int mid = (low + high)/2;

	if(item[MAX_STRINGS][MAX_STRING_LEN] == stringslist[mid][MAX_STRING_LEN])
		return mid+1;

	if(item[MAX_STRINGS][MAX_STRING_LEN] > stringslist[low][MAX_STRING_LEN])
		return binarySearch(stringslist, item, mid+1, high);
	return binarySearch(stringslist, item, low, mid-1);
}

void InsertionSort(char list[MAX_STRINGS][MAX_STRING_LEN])
{
    char loc[MAX_STRINGS][MAX_STRING_LEN];
int j=0;
    char selected[MAX_STRINGS][MAX_STRING_LEN];

    for (int i = 1; i < MAX_STRINGS; i++)
    {    
         j = i - 1;
		selected[MAX_STRINGS][MAX_STRING_LEN] = list[i][MAX_STRING_LEN];
        
        loc[MAX_STRINGS][MAX_STRING_LEN] = binarySearch(list, selected, j, j);
        
      
        
        	while (j >= loc[MAX_STRINGS][MAX_STRING_LEN])
		{
			list[j+1][MAX_STRING_LEN] = list[j][MAX_STRING_LEN];
			j--;
		}
		list[j+1][MAX_STRING_LEN] = selected[MAX_STRINGS][MAX_STRING_LEN];
        
       
    }
}

Patrice T

- У меня проблемы с кодом.
Какая проблема ? - Куда же ?

4 Ответов

Рейтинг:
2

Jochen Arndt

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

selected[MAX_STRINGS][MAX_STRING_LEN] = list[i][MAX_STRING_LEN];
и все остальные строки, использующие размеры массива в качестве индексов. Максимально допустимый индекс равен size - 1.

Вторая проблема заключается в том, что вы не знали, как копировать массивы символов. В приведенной выше строке кода вы копируете один символ (из и в неправильное место из-за to out of bound). Вы должны скопировать каждый символ:
for (int k = 0; k < MAX_STRING_LEN; k++)
    selected[j][k] = list[i][k];
или просто использовать strcpy():
strcpy(selected[j], list[i]);
или memcpy():
memcpy(selected[j], list[i], MAX_STRING_LEN);

Следующая проблема заключается в том, что вы не поняли Сортировка вставки - Википедия[^] или не удалось, по крайней мере, использовать правильные индексы.

Там может быть больше проблем, но я не проверил весь код.

Рейтинг:
2

Rick York

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

#define TEXTSIZE  23
typedef char textitem[TEXTSIZE+1];  // I prefer four byte boundaries

typedef struct students 
{
   textitem number;
   textitem firstname;
   textitem surname;
   textitem group;
} Students;
Вы можете инициализировать структуры данных напрямую. Вот пример первых двух пунктов:
#define STUDENT_COUNT 43

Students sg1[STUDENT_COUNT] =
{
    { "C17501096", "Patrik", "Farrell", "DT265A" },
    { "C17719309", "Iosif",  "Balasca", "DT265A" },
    // and so on...
};
Другой тип и инициализация :
#define MAX_STRING_LEN 47
typedef char String[MAX_STRING_LEN+1];
String strings[MAX_STRINGS] =
{
   "", "Farrell","Balasca","Adamczewska","Cox",
  // and so on...
};
Цикл for, следующий за этим и перед вызовом InsertionSort, не нужен. Наконец, вот как должен выглядеть binarySearch :
int binarySearch( String stringslist[], String item, int low, int high )
{
    int mid;   // must be here in C

    if( high <= low )
        return strcmp( item, stringslist[low] ) > 0 ? (low + 1): low;

    mid = ( low + high ) / 2;

    if( strcmp( item, stringslist[mid] ) == 0 )
        return mid + 1;

    if( strcmp( item, stringslist[low] ) > 0 )
        return binarySearch( stringslist, item, mid+1, high );

    return binarySearch( stringslist, item, low, mid-1 );
}
Я не уверен насчет последних двух вызовов binarySearch, потому что вы поменяли порядок аргументов. Один должен быть списком, а другой-поисковым термином, и они не могут быть заменены. Главное, что вам нужно сравнить строки. То, что у вас есть, не делает этого. Я оставляю функцию сортировки вставки для вас, чтобы вы поняли. Их ключ-сравнить строки с strcmp и, как упоминал Йохен, скопировать строки с strcpy или memcpy.

Еще одна вещь. У вас было объявление mid в середине функции. Вы не можете сделать это в C, но вы можете в C++. Если бы это действительно был C++, то я бы использовал константы, а не определения. Есть и другие вещи, которые можно было бы сделать по-другому, но поскольку цель этого-изучение алгоритмов, я воздержусь от их изучения.

Рейтинг:
1

Patrice T

Не твоя загадочная проблема, но ... :

char firstname[21777];

Какое длинное имя !

Рейтинг:
0

KarstenK

Никто не будет делать вашу работу за вас, поэтому научитесь программировать с помощью какого-нибудь учебника.

Читай мой как начать домашние задания.

И вам повезло, что я дал Ан ответ на аналогичный вопрос что должно тебе помочь.

Дополнительный совет: используйте такие функции, как

FillStudent( students *student, char* number, ....

Member 13768333

У меня есть два Чара с двумя доминионами как сделать
ключевые 2Д = строк 2Д