/ КОМПЬЮТЕРЫ И ПО / Языки программирования / C/C++

Выпуск № 961
от 09.01.2008, 19:05

Вопрос № 116.827

Здравствуйте Поздравляю с новым годом!!!!! Помогите разобраться с алгоритмоми сортировки и поиска в массивах Сортировка выбором Сортировка мет. пузырька Сортировка включением Быстрая сортировка Линейный поиск элемента Двоичный поиск элемента С уважением Vidok.

Отправлен: 04.01.2008, 07:33 Вопрос задал: Vidok (статус: Посетитель) Всего ответов: 3 Мини-форум вопроса >>> (сообщений: 0)

Отвечает: Maksim Trofimov Здравствуйте, Vidok! Ого-го...сколько навалило в новый год :) : + Сортировка включением + Быстрая сортировка Сначало код (на С): ------------------------------ #include <stdio.h> #define compGT(a,b) (a > b) typedef char T; // Тип элемента для сортировки typedef char tblIndex; // тоже самое сдесь подставить... // Сортировка включением void insertSort(T *a, tblIndex lb, tblIndex ub) { T t; tblIndex i, j; for (i = lb + 1; i <= ub; i++) { t = a[i]; for (j = i-1; j >= lb && compGT(a[j], t); j--) a[j+1] = a[j]; a[j+1] = t; } } // Выбор центрального элемента массива для соритировки tblIndex partition(T *a, tblIndex lb, tblIndex ub) { T t, pivot; tblIndex i, j, p; p = lb + ((ub - lb)>>1); pivot = a[p]; a[p] = a[lb]; i = lb+1; j = ub; while (1) { while (i < j && compGT(pivot, a[i])) i++; while (j >= i && compGT(a[j], pivot)) j--; if (i >= j) break; t = a[i]; a[i] = a[j]; a[j] = t; j--; i++; } a[lb] = a[j]; a[j] = pivot; return j; } // Быстрая сортировка void quickSort(T *a, tblIndex lb, tblIndex ub) { tblIndex m; while (lb < ub) { // сортируем методом включением, если массив мал if (ub - lb <= 12) { insertSort(a, lb, ub); return; } // найдем центр m = partition (a, lb, ub); // сначала отсортируем меньший раздел, ... if (m - lb <= ub - m) { quickSort(a, lb, m - 1); lb = m + 1; } else { // а потом, который побольше quickSort(a, m + 1, ub); ub = m - 1; } } } int main(void) { char arr[] = "kdjhbdcuhwedokwdodvucns;djks434njkdfn-=++-="; unsigned arr_len = strlen(arr); unsigned i; // массив длиной больше чем 12 элементов - будет сортировка включением quickSort(arr, 0, arr_len-1); // ну и выводим поэлементно... puts("Sorting by insertion"); for(i = 0; i < arr_len; i++) printf("%c ", arr[i]); // сделаем так, чтобы сработала быстрая сортировка strcpy(arr, "dfbcaa,3e42"); arr_len = strlen(arr); quickSort(arr, 0, arr_len-1); puts(" Sorting by quick sort"); for(i = 0; i < arr_len; i++) printf("%c ", arr[i]); return 0; } ------------------------------ Значит так. Алгоритм быстрой сортировки разбивает сортируемый массив на разделы, затем рекурсивно сортирует каждый раздел. В функции partition(arr, i, j) один из элементов массива выбирается в качестве центрального. Ключи, меньшие центрального следует расположить слева от него, те, которые больше, – справа. Индексы начинают изменяться с концов массива. Индекс i начинается слева и используется для выбора элементов, которые больше центрального, индекс j начинается справа и используется для выбора элементов, которые меньше центрального. Эти элементы меняются местами. Короче: 1) 4 2 3 5 1 //исходный массив элементов: ^ 2) 1 2 3 5 4 // поменяли местами концы массива 3) Процедура quickSort рекурсивно сортирует два подмассива {1 2} и {5 4}, в результате получается массив: 1 2 3 4 5 В качестве центрального в функции partition() выбирается элемент, расположенный в середине. Для коротких массивов вызывается функция insertSort() - cортировка включением. Из-за рекурсии и других “накладных расходов” быстрая сортировка оказывается не столь уж быстрая для коротких массивов. Поэтому, если в массиве 12 и меньше элементов, вызывается сортировка включением. Чтобы было понятней, в приложении ссылка на справочник, из которого я, кстати, и черпал :) Приложение: http://www.rapidshare.ru/525537

Ответ отправил: Maksim Trofimov (статус: 3-ий класс) Ответ отправлен: 04.01.2008, 10:40

Отвечает: Solar Здравствуйте, Vidok! Вообще-то, неплохо иногда юзать гугл, но, тем не менее получайте (код в приложении). По нижеприведенной ссылке вы найдете практически исчерпывающую информацию по алгоритмам сортировки. Link#1 А вот ссылки на алгоритмы поиска: Link#2 Link#3 Исправлены ссылки. ----- ∙ Отредактировал: Gh0stik (А кадемик) ∙ Дата редактирования: 04.01.2008, 11:44 Приложение: 1. Сортировка выбором: for (i = 0; i < n-1; i++) { min = i; for (j = i+1; j < n; j++) { if (x[min] > x[j]) min = j; } temp = x[i]; x[i] = x[min]; x[min] = temp; } 2. Сортировка пузырьком: # define SWAP(A,B) {A=A^B;B=A^B;A=A^B;} void bubblesort(int A[], int n) { int i,j; for(i = n-1 ; i > 0 ; i--) for(j = 0 ; j < i ; j++) if( A[j] > A[j+1] ) SWAP(A[j],A[j+1]); } 3. Сортировка вставками: void insertSort(int a[],int length_a) { int i,j,value; for(i = 1; i < length_a; i++) { value = a[i]; for (j = i-1; (j >= 0) && (a[j] > value); j--) a[j+1] = a[j]; a[j+1] = value; } } 4. Быстрая сортировка: int partition (int *a, int p, int r) { int x = a[r]; int i = p - 1; int j; int tmp; for (j = p; j < r; j++) if (a[j] < x) { i++; tmp = a[i]; a[i] = a[j]; a[j] = tmp; } i++; tmp = a[r]; a[r] = a[i]; a[i] = tmp; return i; } void quicksort (int *a, int p, int r) { int q; if (p < r) { q = partition (a, p, r); quicksort (a, p, q-1); quicksort (a, q+1, r); } } 5. Линейный поиск: int LinearSearch (int A[], int L, int R, int Key) { for(i =L;i<R;i++) if (A[i] == Key) return i; return -1; // элемент не найден } 6. Бинарный поиск: int BinarySearch (int A[], int Lb, int Ub, int Key) { for(;;) // infinite loop { M = Lb + (Ub-Lb)/2; if (Key < A[M]) Ub = M - 1; else if (Key > A[M]) Lb = M + 1; else return M; if (Lb > Ub) return -1; } }

Ответ отправил: Solar (статус: 2-ой класс) Ответ отправлен: 04.01.2008, 10:57

Отвечает: Терсков Сергей Здравствуйте, Vidok! Все эти алгоритмы давно разобраны... Посмотрите здесь: algolist.manual.ru На этом сайте есть отдельные разделы освященные сортировке и поиску. Также советую почитать Д.Кнута "Искусство программирования" 3-ий том. Название его говорит само за себя - "Сортировка и поиск". Материал изложенный в ней, хотя и непрост для восприятия, но является лучшим пособием в этой области.

Ответ отправил: Терсков Сергей (статус: Практикант) Ответ отправлен: 05.01.2008, 04:21

Вопрос № 116.832

В MS Visual C++ 2005 Express Edition не могу скомпилировать программу Ошибка: Cannot open include file: 'windows.h' Установил Microsoft Platform SDK for Windows Server 2003 R2, но всеравно ошибка не проходит. Пробовал скопировать файл windows.h, но появляется ошибка: Cannot open include file: 'windef.h'

Отправлен: 04.01.2008, 09:40 Вопрос задал: Иванов Максим (статус: 2-ой класс) Всего ответов: 4 Мини-форум вопроса >>> (сообщений: 3)

Отвечает: Maksim Trofimov Здравствуйте, Иванов Максим! Не нужно компилировать... Что можно попробывать сделать?: 1) Не подключать его. Может быть его подключит другой заголовочный файл, и он знает где windows.h расположен; 2) Найти, в какой директории он расположен (может быть он не в директории include VC) и прописать полный путь к нему, например #include "C:Program FilesMicrosoft Visual Studio 8VCPlatformSDKIncludewindows.h"; 3) А регистр соблюден? Может быть Windows.h, а не windows.h ...

Ответ отправил: Maksim Trofimov (статус: 3-ий класс) Ответ отправлен: 04.01.2008, 09:54

Отвечает: Mitya86 Здравствуйте, Иванов Максим! А у тебя, случаем, не в кавычках ли windows.h находится? Если да, замени их на треугольные скобки(см.пример). Надеюсь помог. Удачи! Приложение: #include <windows.h>

Ответ отправил: Mitya86 (статус: 3-ий класс) Ответ отправлен: 04.01.2008, 10:39

Отвечает: kool Здравствуйте, Иванов Максим! Поищите где у вас находится файлы windows.h и другие *.h и пропишите путь к этой папке в настройках среды Неплохо бы еще глянуть текст проги где используется windows.h Удачи! --------- I am.

Ответ отправил: kool (статус: Практикант) Ответ отправлен: 04.01.2008, 12:14

Отвечает: mega Здравствуйте, Иванов Максим! После установки SDK, найдите его группу через меню "Пуск-> Программы...", среди всего прочего, там должен быть ярлык на bat-файл, с названием "Set Envirounment" или "Set Envirounment Variables" (точно не помню), выполните его, перезапустите среду, или ребутните комп. Проблема в том, что в настройках среды после установки SDK не указаны пути поиска стандартных хидеров, библиотек, исходников и т.п. Этот батник как раз и добавляет пути до всех нужных подпапок SDK в VS. То же самое можно сделать и вручную, перейти в меню Tools->Options->Projects->VC++Directories и добавить к каждой группе списка "Show directories for" соответствующий путь из SDK. Но такой способ менее надежен, поскольку можно что-то да пропустить.

Ответ отправил: mega (статус: 3-ий класс) Ответ отправлен: 04.01.2008, 13:20 Оценка за ответ: 5 Комментарий оценки: Все помогло, спасибо!

Вопрос № 116.876

Здарвствуйте, товарищи эксперты, нужна помощь! Помогите написать программу на нахождения максимального по значению элемента списка на С++ с помощью динамических структур данных

Отправлен: 04.01.2008, 15:09 Вопрос задал: Мингараев Дмитрий (статус: Посетитель) Всего ответов: 2 Мини-форум вопроса >>> (сообщений: 0)

Отвечает: Maksim Trofimov Здравствуйте, Мингараев Дмитрий! Вот пожайлуста... Динамическая структура - односвязный список. Элементами списка являются данные типа char (чтобы сделать шаблон, не придется много исправлять). Максимальный элемент определяется методом max(). //************************************************************************ #include <iostream> //************************************************************************ class t_list { private: char data; protected: t_list(char c = 0): data(c) { } char get_char(void) { return data; } void set_char(char c) { data = c; } }; //************************************************************************ class t_singlist: public t_list { private: t_singlist *m_next; unsigned m_count; public: t_singlist(): t_list(), m_next(NULL), m_count(0) { } ~t_singlist(); t_singlist(const t_singlist &t); t_singlist operator=(const t_singlist &t); // добавить элемент void add(char c); // удалить элемент void del(unsigned index); // получить данные элемента char get(unsigned index = 0); // длина списка unsigned count(void) { return m_count; } // нахождение максимального элемента списка char max(void); }; t_singlist::t_singlist(const t_singlist &t): m_count(0), m_next(NULL) { t_singlist *tmp = (t_singlist *)&t; for(; tmp!= NULL; tmp = tmp->m_next) add(tmp->get_char()); } t_singlist t_singlist::operator=(const t_singlist &t) { if(&t!= this) { t_singlist *tmp = (t_singlist *)&t; for(; tmp!= NULL; tmp = tmp->m_next) add(tmp->get_char()); } return *this; } t_singlist::~t_singlist() { t_singlist *t = this; if(this->m_next == NULL) m_count = 0; else { while(t->m_next!= NULL) t = t->m_next; m_count--; delete t; } } void t_singlist::add(char c) { if(!count()) set_char(c); else { t_singlist *t = this; while(t->m_next!= NULL) t = t->m_next; t->m_next = new t_singlist; t->m_next->set_char(c); t->m_next->m_next = NULL; } m_count++; } void t_singlist::del(unsigned index) { t_singlist *t1 = this, *t2 = this; unsigned i; if(index < count()) { if(!index) { if(count() > 1) { set_char(this->m_next->get_char()); this->m_next = this->m_next->m_next; m_count--; } else m_count--; } else { for(i = 0; i < index; i++) t1 = t1->m_next; for(i = 0; i < index-1; i++) t2 = t2->m_next; t2->m_next = t1->m_next; m_count--; } } } char t_singlist::get(unsigned index) { if(index >= count()) return 'a'; else if(!index) return get_char(); t_singlist *t = this; for(; index!= 0; index--) t = t->m_next; return t->get_char(); } char t_singlist::max(void) { char c = get(); char t; for(unsigned i = 0; i < count(); i++) if(int(c) < int(t=get(i))) c = t; return c; } //************************************************************************ int main(void) { using namespace std; cout << " Create single list and show it's elements: "; t_singlist t; t.add('1'); t.add('2'); t.add('9'); t.add('4'); t.add('8'); cout << "Single list: "; for(unsigned i = 0; i < t.count(); i++) cout << t.get(i); cout << " Max element: " << t.max() << endl; return 0; } //************************************************************************

Ответ отправил: Maksim Trofimov (статус: 3-ий класс) Ответ отправлен: 04.01.2008, 16:07

Отвечает: Ross Здравствуйте, Мингараев Дмитрий! Решение в приложении к ответу. В отличие от предыдущего ответа здесь использована традиционная структура списка (head/tail) и шаблоны. Приложение: //односвязный список template <typename T> class single_list { class list_item { list_item* next; T data; friend class single_list; public: list_item(list_item *pnext): next(pnext) {} }; list_item* head; list_item* tail; public: //constructor single_list() { head = tail = new list_item(0); } //destructor ~single_list() { clear(); delete tail; } public: //добавляет в начало списка void add_front (const T& val); //добавляет в конец списка void add_rear (const T& val); //удаляет первый элемент void remove_front (); //удаляет последний элемент void remove_rear (); //возвращает n-ый элемент списка T get_nth (unsigned int n) const; //возвращает максимальный элемент T get_max () const; bool empty () const; void clear (); }; template <typename T> void single_list<T>::add_front(const T& val) { list_item *to_add = new list_item(head); to_add->data = val; head = to_add; } template <typename T> void single_list<T>::add_rear(const T& val) { if (empty()) add_front(val); else { list_item* i = head; for (; i->next != tail; i = i->next) ; i->next = new list_item(tail); i->next->data = val; } } template <typename T> bool single_list<T>::empty() const { return head == tail; } template <typename T> void single_list<T>::remove_front() { if (empty()) throw "List is empty"; list_item* to_remove = head; head = head->next; delete to_remove; } template <typename T> void single_list<T>::remove_rear() { if (empty()) throw "List is empty"; if (head->next == tail) { list_item *to_remove = head; head = tail; delete to_remove; } else { list_item *i = head; for (;i->next->next != tail; i = i->next) ; list_item* to_remove = i->next; i->next = i->next->next; delete to_remove; } } template <typename T> void single_list<T>::clear() { for (list_item* i= head; i != tail; ) { list_item* to_remove = i; i = i->next; delete to_remove; } head = tail; } template <typename T> T single_list<T>::get_nth(unsigned int n) const { if (empty()) throw "List is empty"; unsigned int iter = 0; for (list_item* i = head; i != tail; i = i->next) { iter++; if (iter == n) return i->data; } throw "End of list"; } template <typename T> T single_list<T>::get_max() const { if (empty()) throw "List is empty"; T max = head->data; for (list_item* i = head->next; i != tail; i = i->next) { if (i->data > max) max = i->data; } return max; } #include <iostream> using std::cout; using std::endl; void main() { single_list<int> sl; sl.add_front(11); sl.add_rear(12); sl.add_front(10); sl.add_rear(13); cout << "Maximal element: " << sl.get_max() << endl; sl.clear(); } --------- Доступно только то, что видимо (c) Б. Керниган

Ответ отправил: Ross (статус: Студент) Ответ отправлен: 04.01.2008, 16:22

Вопрос № 116.896

Здравствуйте, уважаемые эксперты! Очень надеюсь на вашу помощь. Необходимо решить вот такую задачу по "Си" (сам я пока ещё дуб - а времени уже нету...): "Ввести строки, в которых имеются круглые, фигурные и квадратные скобки. Проверить, правильно ли они расставлены. Результат вывести на экран. Стандартных функций работы со строками не использовать." Если можно - алгоритм решения, комментарии, ссылки и всё, что может помочь мне в данной ситуации... P.S. Также может найдётся такой добрый человек, который скинет готовый файл (...или что-нить похожее...) именно для Си/Си ++... А лучше всего - на Turbo Си ++... =))) На других языках не пишите... Всё равно нету уже времени переделывать под себя... P.P.S. Заранее благодарен всем взявшимся помочь и просто всем знающим... Очень нуждаюсь в вашей помощи... =(

Отправлен: 04.01.2008, 17:35 Вопрос задал: Tarik-fly (статус: Посетитель) Всего ответов: 3 Мини-форум вопроса >>> (сообщений: 0)

Отвечает: X-men Здравствуйте, Tarik-fly! Вот как мне представляется алгоритм программы: 1. Посчитать количество открытых и закрытых скобок (для каждого типа ( "()", "[]", "{}" ) скобок) 2. Если кол-во открытых скобок равняется количеству закрытых, то: 2.1. вызов рекурсивной функции для проверки всего выражения: 2.1.1. поиск первой открывающейся скобки. Если найдена открывающаяся скобка, то запомнить её тип и далее искать закрывающуюся скобку (разумеется этого же типа). 2.1.2. Если закрывающая скобка не была найдена, то выход из всех рекурсий и вывод ошибки. 2.1.3. Иначе (если она была найдена), то вызываем рекурсию (параметром будет подстрока между открытой и закрытой скобкой). 3. иначе (если даже количество не совпадает [см.п.2.] ), то вывод ошибки. В приложении описана часть этого алгоритма. Осталось лишь функцию дописать. Приложение: #include <iostream> #include <conio.h> #include <string> using namespace std; int main(void){ int i,j; int a,b,c,d; a=b=c=d=0; string str; cin >> str; int size = str.size(); for (i=0; i<size; i++) { if (str[i]=="(") a++; else if (str[i]==")") b++; else if (str[i]=="[") c++; else if (str[i]=="]") d++; else if (str[i]=="{") e++; else if (str[i]=="}") f++; } if (a==b && c==d && e==f){ // здесь должен быть вызов // функции, которая проверяла // бы адекватность // расставленных скобок } else cout << endl << "Error"; getch(); return 0; }

Ответ отправил: X-men (статус: 2-ой класс) Ответ отправлен: 05.01.2008, 00:50

Отвечает: Maksim Trofimov Здравствуйте, Tarik-fly! #include <stdio.h> int main(void) { char str[] = "f(ff[]lhgi{fgfg}fgfg()fgfgf)fwwss[dsdsd]sdsd[]sds{}sdd"; int i; int j = 0, k = 0, m = 0; for(i = 0; i < strlen(str)-1; i++) if(str[i] == '(' && str[i+1] == ')') j++; else if(str[i] == '{' && str[i+1] == '}') k++; else if(str[i] == '[' && str[i+1] == ']') m++; printf("String: %s () count: %d {} count: %d [] count: %d ", str, j, k, m); return 0; }

Ответ отправил: Maksim Trofimov (статус: 3-ий класс) Ответ отправлен: 05.01.2008, 03:18

Отвечает: Терсков Сергей Здравствуйте, Tarik-fly! Ваше же вопрос №115073. Приведенный код полностью удовлетворяет условиям вашей задачи. Приложение: #include <stdio.h> class stack { char *data; int size; int top; public: stack(int _size) : size(_size) { data = new char[size]; top = 0; } ~stack() { if(data) delete[] data; } void push(char c) { data[top++] = c; } char pop() { return data[(top--)-1]; } }; int main(int argc, char* argv[]) { char *str = "(x) + [{y + (c + {a})}]"; printf("String is: %s ", str); stack stk(50); const int delimiters_count = 4; char open[delimiters_count] = "([{"; char close[delimiters_count] = ")]}"; char *ptr = str; while(*ptr != ' for(int i=0; i<delimiters_count-1; i++) { if(*ptr == open[i]) stk.push(*ptr); if(*ptr == close[i]) { if(stk.pop() != open[i]) { printf("Order of following of delimiters is violated in %d place ", (ptr - str)); return 0; } } } ptr++; } printf("Order of following of delimiters is correct "); return 0; }

Ответ отправил: Терсков Сергей (статус: Практикант) Ответ отправлен: 05.01.2008, 04:48

© 2001-2007, Портал RusFAQ.ru, Россия, Москва. Авторское право: ООО "Мастер-Эксперт Про" Техподдержка портала, тел.: +7 (926) 535-23-31 Хостинг: "Московский хостер" Поддержка: "Московский дизайнер" Авторские права | Реклама на портале Версия системы: 4.69 от 06.01.2008
RusFAQ.ru | MosHoster.ru | MosDesigner.ru | RusIRC.ru Kalashnikoff.ru | RadioLeader.ru | RusFUCK.ru