Добре дошли!

Добре дошли в нашите форуми, пълни с полезна информация. Имате проблем с компютъра или телефона си? Публикувайте нова тема и ще намерите решение на всичките си проблеми. Общувайте свободно и открийте безброй нови приятели.

Моля, регистрирайте се за да публикувате тема и да получите пълен достъп до всички функции.

Проблем с метода на Шел

Нова тема

6 декември 201411 г.

Здравейте, имам да направя стек с данни от файл и да ги сортирам по метод на Шел, но сортирането не ми се получава. Моля помогнете.

Ето го и моя код:

========================================================

#include<iostream>

#include<fstream>

#include<string>

#include<cstdlib>

#include<ctime>

using namespace std;

int br_both=0;

const int N=20;

struct opashka{

int key;

opashka *first;

opashka *next;

opashka *last;

} *start, *first = NULL, *last = NULL;

void push_stek(int a) //dobavqne na elementite v opashkata

{

opashka *p=first;

first=new opashka;

first->key=a;

first->next=p;

}

int pop_stek(int n) //Izvlichane na element ot opashka

{

if (first)

{

n=first->key;

opashka *p=first;

first=first->next;

delete p;

return 1;

}

else

return 0;

}

void Suzdavane_file() // Syzdava fail s random chisla ako nqma gotov fail

{

int chislo; //променлива за числата

srand(time(NULL)); //генерира случайни числа

ofstream file; //променлива от тип ofstream - за запис

file.open("file.txt"); //отваря файла за запис

if (file.is_open()) //проверява дали файлът е отворен

{

for(int i=0;i<N;i++) //казва колко числа да генерира

{

chislo = rand()%200; //random chislata sa v interval 1–200

file << chislo << endl; //записва 20 случайни числата във файла

}

file.close(); //затваря файла

}

else cout << "Faila ne moje da bude otvoren";

}

void Vavejdane_file() //chete i popylva spisaka ot fail, за да можем да използваме числата в програмата

{

int a;

ifstream file_1; //променлива от тип ifstream - само за четене

file_1.open("file.txt", ios::in); //otvarq faila za chetene

if(file_1!=NULL) //proverka za prazen fail - ако не е празен файлът

{

while(!file_1.eof()) // chete dokato stigne kraiq mu

{

file_1>>a; //чете числата

push_stek(a); //prochetenata stoinost se predawa na a

//слага ги в опашката

}

file_1.close(); //затваря файла

cout<<endl<<" Faila e vaveden."<<endl<<endl;

}

else //pri prazen fail ili greshka pri otvarqne

cout<<"Greshka pri otvarqne na fila! Molq vavedete otnovo ili syzdaite avtomatichno fail"<<endl;

}

void Display_stek() // pokazwa sururjanieto na steka

{

for (opashka *p = first; p; p = p->next)

{

cout << p->key << " ";

}

int find_num(opashka *st, int n) // n- nomera na koi element trqbva da stigne, vrashta stoinosta na tozi element

{

int br=0;

while(br!=n)

{

st=st->last;

br++;

}

return st->key;

}

void replace_elem(opashka *&first, int b, int r) //prisvoqva na nomera stoinost

{

opashka *p=first;

int i=0;

while(i!=b)

{

p=p->next;

i++;

}

p->key=r; //r - stoinostta koqto se slaga

}

int count_opashka(opashka *first) //broi kolko elementa ima opashkata

{

int count_br=0; //брояч на елементите в опашката

while(first) //докато не сме стигнали края на опашката

{

count_br++; //броячът се увеличава

first=first->next; //измества указателя с една позиция надясно

}

return count_br; //връща броя на елементите в опашката

}

void shellsort (opashka *first, int N)

{

int h, i, j, k, g;

for (h = N/2; h > 0; h /= 2) {

for (i = h; i < N; i++) {

k = find_num(first,i);

for (j = i; j >= h && k <find_num(first,(j-h)); j -= h) {

g=find_num(first,(j-h));

replace_elem(first,j,g);

br_both ++;

}

replace_elem(first,j,k);

}

void call_shell_sort(opashka *first) //s otdelna funkciq zashtoto shell-a iska broq na elementite,koito sa ot drugata funkciq

{

cout<<"\n Sorting is ready "<<endl;

int n=count_opashka(first); //променлива за броя на елементите

shellsort(first,n); //викаме функцията за сортиране на елементите

}

void main()

{

int izbor,z=0;

{

if(z>0)

cout<<endl<<" Molq vavedete korekten izbor !!!"<<endl<<endl;

cout<<"<#><#><#><#><#><#> MENU <#><#><#><#><#><#><#>"<<endl;

cout<<"<#><#><#><#><#><#><#><#><#><#><#><#><#><#><#><#><#><#><#><#><#><#><#><#>"<<endl;

cout<<"<#><#> <#><#>"<<endl;

cout<<"<#><#> [1] - Syzdaifail sys sluchaini chisla <#><#>"<<endl;

cout<<"<#><#> [2] - Vavedi vhodqshtiq fail v programata ( file.txt ) <#><#>"<<endl;

cout<<"<#><#> [3] - <#><#>"<<endl;

cout<<"<#><#> [4] - Izvejdane na steka <#><#>"<<endl;

cout<<"<#><#> [5] - Shell sort <#><#>"<<endl;

cout<<"<#><#> [*] - <#><#>"<<endl;

cout<<"<#><#> [0] - Izhod <#><#>"<<endl;

cout<<"<#><#> <#><#>"<<endl;

cout<<"<#><#> ---------------------------------------------------- <#><#>"<<endl;

cout<<endl<<" Vashiqt izbor: ";

cin>>izbor;

z++;

}while(izbor<0 || izbor>=6);

cout<<endl;

z=0;

opashka *temp=start;

switch (izbor)

{

case 0: exit(0);

break;

case 1: Suzdavane_file();

main();

break;

case 2: Vavejdane_file();

main();

break;

case 4: Display_stek();

cout<<endl;

main();

break;

case 5: call_shell_sort(first);

cout<<endl;

break;

}

system("pause");

}

Цитирай

6 декември 201411 г.

То остави че връща грешка ама и ти май някакъв нов тип стек си измислил. При стека имаш достъп само до най-горния елемент, може да добавяш друг върху него или да махаш най-горния. Бедна ми е фантастиката защо трябва да се сортира по метода на Шел със стек. По метода на мехурчето ти трябват два стека за сортировката, а по Шел ще ти трябва и опашка между тях двата.

Редактирано 6 декември 201411 г. от ined (преглед на промените)

Цитирай

6 декември 201411 г.

Здравейте, имам да направя стек с данни от файл и да ги сортирам по метод на Шел, но сортирането не ми се получава. Моля помогнете.

Ето го и моя код:

Здравейте !

Проблема на програмата Ви се намира в този ред на метода int find_num(opashka *st, int n) :

st = st->last;

В следващите редове съм поставил коментарите си по кода, и грешките, които успях да открия.

...
struct opashka {
	int key;
	opashka *first; // Защо имаме това ? Доколкото разбирам, имаме едносвързан списък, а не mesh/graph или тернарно дърво ...
	opashka *next;
	opashka *last; // Отново като за *first - защо го имаме ?
}*start, *first = NULL, *last = NULL;

//...

int pop_stek(int n) // ?! Метода в този си вид е абсурден и безсмислен ...  Параметъра n не трябва да променя стойността си в тялото на метода.
// Според типичните реализации на стек, метода pop не е нужно да приема параметър. 
{
	if (first) {
		n = first->key;
		opashka *p = first;
		first = first->next;
		delete p;
		return 1; // Return 1 ?! Нали ще връщаме стойността, записана във first->key, защо винаги връщаме 1 ?!
	} else
		return 0; // Под въпрос е и до колко валидно е това. Не винаги е добра идея NULL да се смята за 0-ла. Още повече, когато ще правим сортирания 
}

//...
int find_num(opashka *st, int n)
		{
	int br = 0;
	while (br != n) {
		st = st->last; // Какво е това last ?! Никъде се попълва, никъде се въвежда и никъде не се ползва... освен тук... Това е причината за грешката Ви !
		br++;
	}
	return st->key;
}

//...

void call_shell_sort(opashka *first) //s otdelna funkciq zashtoto shell-a iska broq na elementite,koito sa ot drugata funkciq
		{
	cout << "\n Sorting is ready " << endl; // Дали не е по-добре това съобщение да се появи, след като успешно сме направили обръщение към функцията shellsort  ? Т.е. да го преместим като последен ред на текущия метод.
	int n = count_opashka(first); //променлива за броя на елементите
	shellsort(first, n); //викаме функцията за сортиране на елементите
}

void main() {
	//...
	switch (izbor) {
	case 0:
		exit(0);
		break;
	case 1:
		Suzdavane_file();
		main();
		break;
	case 2:
		Vavejdane_file();
		main();
		break;

	case 4:
		Display_stek();
		cout << endl;
		main();
		break;
	case 5:
		call_shell_sort(first);
		cout << endl;
		//Тук може да мушнете пак main(), за да може все пак да имаме шанс да извикаме програмата с опция 4 (за да видим вече наредения стек).
		break;

	}
	system("pause"); //Това, след като се уверите, че програмата върви правилно, трябва да го изтриете. Не е добра идея във вече готов код да има подобни обръщения.
}

То остави че връща грешка ама и ти май някакъв нов тип стек си измислил. При стека имаш достъп само до най-горния елемент, може да добавяш друг върху него или да махаш най-горния. Бедна ми е фантастиката защо трябава да се сортира по метода на Шел със стек. По метода на мехурчето ти трябват два стека за сортировката, а по Шел ще ти трябва и опашка между тях двата.

Защото този "стек" се ползва и за опашка и за масив... абе използваме го както си искаме . Търчим си като финикийци из него, за да търсим елементи и да вадим стойности. И това си се отразява и на самия алгоритъм - така сложността отива доволно към нещо ~N^3 ...

Поздрави !

Редактирано 6 декември 201411 г. от soundtracker (преглед на промените)

Цитирай

6 декември 201411 г.

Автор

Благодаря много. А имате ли идея как мога да разделя стека на две части с по 10 елемента. Предполагам трябва да се използва функцията count_opashka в нова функция която разделя стека от 20-те числа. Но как точно ще стане? Имате ли идея?

Цитирай

7 декември 201411 г.

Благодаря много. А имате ли идея как мога да разделя стека на две части с по 10 елемента. Предполагам трябва да се използва функцията count_opashka в нова функция която разделя стека от 20-те числа. Но как точно ще стане? Имате ли идея?

Ако ползваш "чиста" стек имплементация и искаш просто да разделиш стека в два, а не точно първата половина в единия, останалото в другия , просто докато има елементи в стека, взимаш един и редувайки се го слагаш в единия и в другия. Иначе зависи как е имплементиран стека, ако си има променлива която съхранява дължината или функция която брои - ползваш я, делиш на 2, и в два поредни цикъла взимаш и слагаш в съответния изходен стек.

ама и ти май някакъв нов тип стек си измислил.

Не е баш така. "Стек" е концепция за достъп до елементите в поредица, не закован като имплементация, освен ако не е хардуерен. Типично доказателство е примерно стека в STL, който може да използва отдолу си всякакъв контейнер, който отговаря на интерфейса и по подразбиране ползва за такъв точно дек. По някаква случайност на дека му трябват указатели към първи и последен елемент, та като гледам горе просто, може да е много грешно разбрано или преподадено обяснение.

Цитирай

7 декември 201411 г.

Да не намесваме дека, защото неговия "стек" дори и дек не е.

пробвах да ги понахвърля нещата, доста грозничко се получи - освен че е дълго има доста повтарящи се неща и може да се поразхвърля на отделни функции ама нещо ме домързя да го правя.

#include <iostream>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <time.h>

using namespace std;

int main () {
    int n, d, flag;
    stack<int> s1, s2; 
    queue<int> q;
    clock_t timer;
    
    cout<<"Enter 0 for EXIT\n";
  do {
    cout<<"\nN = "; 
    cin>>n;
    if (n<1) return 0;
    
    srand(time(NULL));
    for (int i=0; i<n; i++) {
         d = rand()%n;
         cout<<d<<" ";
         s1.push(d);
    } 
    cout<<"\nSorting...\n";
    timer=clock();
   if (n>1) {
    d =n;
    q.push(s1.top()); 
    s1.pop();
    do {
        d = d*5/11; 
        for (int i=0; i<d; i++) {
            q.push(s1.top());
            s1.pop();
        }
        while (!s1.empty()) {
           if (q.front()>s1.top()) {
              s2.push(s1.top());
              q.push(q.front());
           } else {
              s2.push(q.front());
              q.push(s1.top());
           }
           s1.pop();
           q.pop();
        }
        for (int i=0; i<d; i++) {
            s2.push(q.front());
            q.pop();
        }
        flag=0;
        for (int i=1; i<d; i++) {
            q.push(s2.top());
            s2.pop();
        }
        while (!s2.empty()) {
           if (q.front()<s2.top()){
              s1.push(s2.top());
              q.push(q.front());
              flag=1;
           } else {
              s1.push(q.front());
              q.push(s2.top());
           }
           s2.pop();
           q.pop();
        }
        for (int i=1; i<d; i++) {
            s1.push(q.front());
            q.pop();
        }
    } while (flag||d);
    s1.push(q.front()); 
    q.pop();
   } // if(n>1)
    timer=clock()-timer;
    while(!s1.empty()){
        cout<<s1.top()<<" "; 
        s1.pop();
    }
    cout<<endl<<"Time "<<timer<<"ms\n";
    
  } while(1);
}

Редактирано 14 декември 201411 г. от ined (преглед на промените)

Цитирай

7 декември 201411 г.

Да не намесваме дека, защото неговия "стек" дори и дек не е.

Имах предвид, че не е измислил нов вид стек и STL стека дето ти ползваш е на същия принцип - има отдолу си опашка. А това че е написано "нещо си" което не е ясно какво е вместо опашка е очевидно.

Редактирано 7 декември 201411 г. от flare (преглед на промените)

Цитирай

12 декември 201411 г.

Опашката си е опашка, той и вектора си има опашка само че при STL стека нямаш директен достъп до всеки елемент, а само до първия. Иначе ако списъка го кръстиш "стек" обхождайки го по указателите тогава наистина имаш достъп до всеки елемент от "стека".

Редактирано 16 декември 201411 г. от ined (преглед на промените)

Цитирай

Архивирана тема

Темата е твърде стара и е архивирана. Не можете да добавяте нови отговори в нея, но винаги можете да публикувате нова тема, в която да продължи дискусията. Регистрирайте се или влезте във вашия профил за да публикувате нова тема.