|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
03.01.2011, 21:01 | #1 |
Новичок
Джуниор
Регистрация: 03.01.2011
Сообщений: 2
|
Сортировка стека
Приветствую всех ! Есть код программы, сортирующей стек методом простых вставок, а нужно исправить программу на сортировку стека методом бинарных вставок. Спасибо Заранее !
#include <iostream> #include <stdlib.h> using namespace std; #define NOTHING 0 template <class E> struct element{ E mean; element *prev; element *next; }; template <class T> class stek{ element<T> *head; element<T> *back; element<T> *tmp; int count; public: stek(){ head=NOTHING; back=NOTHING; tmp=NOTHING; count=0; } bool PushFront(T elem){ if(elem==NOTHING) return false; tmp = new element<T>; tmp->mean=elem; tmp->prev=head; tmp->next=NOTHING; if(head==NOTHING){ back=tmp; } else{ head->next=tmp; } head=tmp; count++; return true; } bool PushBack(T elem){ if(elem==NOTHING) return false; tmp = new element<T>; tmp->mean=elem; tmp->prev=NOTHING; tmp->next=back; if(back==NOTHING){ head=tmp; } else{ back->prev=tmp; } back=tmp; count++; return true; } T PopFront(){ if(head==NOTHING) return NOTHING; T res=head->mean; tmp=head; head=head->prev; if(head==back) head->next=NOTHING; delete tmp; count--; return res; } T PopBack(){ if(back==NOTHING) return NOTHING; T res=back->mean; tmp=back; back=back->next; if(head==back) back->prev=NOTHING; delete tmp; count--; return res; } bool isEmpty(){ if(count==0) return true; else return false; } void print(){ element<T> *t=back; while(t!=NOTHING){ cout<<t->mean<<" "; t=t->next; } } }; int main() { cout << "СoPTuPoBKa MeToDoM nPoCTblX BCTaBoK" << endl; stek<int> *l=new stek<int>(); int gen; srand; //генерируем одно и 2х значные случайные числа (~50/50) исключая ноль for(int i=0;i<15;i++){ gen=(rand()%10>5?rand()%100:rand()% 10); l->PushBack(gen==0?NOTHING:gen); } l->print(); cout<<endl; /* берем из основного cтека по кею, * Вытаскиваем из временного стека по элементу, * сравниваем с текущим кеем и засовываем в рез * если текущий кей меньшечем текущий элемент тм, * то засовываем сначала его, а потом все остальные, * перекидываем все обратно в тм * и переходим к следующей итерации (берем следующий элемент кей) * ВНИМАНИЕ! нельзя чтобы в исходных данных был ноль - он испульзуется * как ноль! (константа nothing) (АТД возвращает его когда не находит больше элементов) */ int key,key2; stek<int> *tm=new stek<int>(); stek<int> *res=new stek<int>(); do { key=l->PopFront(); do { key2=tm->PopFront(); if(key>=key2){ res->PushFront(key); res->PushFront(key2); //докидываем оставшиеся while(!tm->isEmpty()){ key2=tm->PopFront(); res->PushFront(key2); } } else{ res->PushFront(key2); } } while(!tm->isEmpty()); //перегоняем обратно в тм while(tm->PushFront(res->PopFront())); }while(!l->isEmpty()); while(l->PushFront(tm->PopBack())); l->print(); cin.get (); } |
03.01.2011, 21:53 | #2 |
Новичок
Джуниор
Регистрация: 03.01.2011
Сообщений: 2
|
Сортировка методом бинарных вставок:
1: void past_sort_bin(mat r[], int N) 2: { 3: int i, left, right, k, s; 4: mat x; 5: 6: for (i = 1; i < N; i++) 7: { 8: left = 0; 9: right = i; 10: 11: k = (right + left)/2; 12: 13: while (left != k) 14: { 15: if (r[k].code > r[i].code) 16: right = k; 17: else 18: left = k; 19: k = (right + left)/2; 20: } 21: 22: if (r[left].code < r[i].code) 23: { 24: if (r[i].code > r[k].code) 25: left = k+1; 26: else 27: left = k; 28: } 29: 30: x = r[i]; 31: 32: for (s = i; s > left; s--) 33: r[s] = r[s-1]; 34: 35: r[left] = x; 36: } 37: } Я просто не могу убрать оттуда простые вставки и поставить бинарные. Не понимаю как связать |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Организация стека | SoftKoc | Общие вопросы Delphi | 4 | 11.12.2010 14:02 |
С (Си). реализация стека | alex(21) | Общие вопросы C/C++ | 21 | 18.10.2010 08:54 |
Переполнение стека | Ake | Паскаль, Turbo Pascal, PascalABC.NET | 3 | 30.05.2009 22:39 |
Реализация Стека | MjRed | Общие вопросы C/C++ | 3 | 13.05.2009 12:18 |