Добре дошли!

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

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

Сортиране по метод на Шел (C++)

4 декември 201213 г.

Здравейте, приятели. Имам да правя курсов проект по Синтез и анализ на алгоритми. Който е:

Да се състави програма , която съдържа следните функции:

1)съставяне на динамично представен двусвързан списък с целочислени

данни, съдържащи се във външен файл;

2)сортиране на елементите в списъка по метода на Шел;

3)запис на изходните резултати във външен файл.

Проблема ми е, че не знам как наглася сортирането по метода на Шел да работи с двусвързан списък, без да се използва масив...

Благодаря предварително.

P.S Направил съм точка 1 и не знам как ще стане точка 2.

5 декември 201213 г.

Автор

Това е част от кода там до където съм стигнал .......

#include<fstream>
#include<string>
#include<cstdlib>
#include<ctime>
using namespace std;

const int N=2000;

struct elem{
int key;
elem *next;
elem *prev;
}
*start = NULL;

void add_b(int n)
{
elem *p=start;
start=new elem;
start->next=p;
start->prev=NULL;
start->key=n;
if(p)
p->prev=start;
}
void CreateFile()//функция за създаване на файл и запълване с рандом числа
{
	 int chislo = 0;
	 srand(time(NULL));
	 ofstream file;
	 file.open("file.txt");
		if (file.is_open())
		{
			for(int i=0;i<N;i++)	//Добавяне на рандом числа в файл
			{
				chislo = rand()%2000; //рандам числата за в интервал от 1–500
				file << chislo << endl;
			}
			file.close();
		}
	else cout << "Unable to open file";
}
void ReadFile()//функция за прочитане на файла и добавянето им във списък
{
	int b = 0 ;
	CreateFile();
	ifstream file;
	file.open("file.txt");
	if (file.is_open())
	{
		while (file >> b)
		 {
			//add(start, b);
			add_b(b);

		 }
	}
		file.close();
}
  void list()//функция за извеждане на списъка
{
if(start)
{
cout<<"\n The list:"<<endl;
elem *p=start;
while(p)
{
cout<<p->key<<"\t";
p=p->next;
}
}
else
cout<<"\n Empty list";
}
  int menu()
{

int choice;
cout<<endl;
cout<<endl;
cout<<" M E N U "<<endl;
cout<<endl;
cout<<"1.Syzdavane na fail"<<endl;
cout<<"2.Zapylvane na spisyka s chisla"<<endl;
cout<<"3.Izvejdane na spisyka"<<endl;
cout<<endl;
cout<<"Vyvedete vashiqt izbor: ";
cin>>choice;
return choice;
}



int main()
{


int choice;
do
{
choice=menu();

switch (choice)
{
case 1: CreateFile();break;
case 2: ReadFile();break;
case 3: list();break;

}
}while(choice!=0);

return 0;
}

Редактирано 5 декември 201213 г. от reallove (преглед на промените)

10 декември 201213 г.

Здравей! За да я решиш ще трябва да си набавиш алгоритъм за сортиране и да разбереш как функционира. Има го описан в Програмиране C++ част 2ра от Магдалина Тодорова. За да го накараш да работи в свързан списък без да използваш масив ще трябва да се запознаеш с член функцията iterator( ) на class List. С нея обхождаш списъка. Размяната на стойностите я правиш или с временна int променлива или с използване на указателите "prev" и "next" както ти е по удобно. Постни някакъв код на алгоритъма ако имаш нужда от помощ.

Редактирано 10 декември 201213 г. от Enhuntres (преглед на промените)

10 декември 201213 г.

Автор

Погледнах в книгата и там функциите са дадени като шаблонни. Въпросът ми е не може ли да стане без да се ползват класове? Бяха ми казали, че можело да стане с рекурсия, но и идея си нямам как може да стане.

10 декември 201213 г.

Естествено че може да стане без класове. Очевидно, смисълът да ползвате C++, а не C е имено използването на обекти, но никой не ви спира. Освен здравия ви разум и евентуално преподавателя ви по програмиране (аз ако бях - пиша двойка на всяка псевдо C++ програма.)

Тука обаче тънкият момент не е с или без класове. Сортирането по метода на Шел много се улеснява, когато се прилага върху контейнери поддържащи директно индексиране (като масиви напр.) и не е съвсем тривиално върху останалите, какъвто е случая. Имайки предвид това, мисля че сте в някаква доста свързана с програмирането специалност...

За да я решиш ще трябва да си набавиш алгоритъм за сортиране и да разбереш как функционира. Има го описан в Програмиране C++ част 2ра от Магдалина Тодорова.
За да го накараш да работи в свързан списък без да използваш масив ще трябва да се запознаеш с член функцията iterator( ) на class List. С нея обхождаш списъка.
Размяната на стойностите я правиш или с временна int променлива или с използване на указателите "prev" и "next" както ти е по удобно.
Постни някакъв код на алгоритъма ако имаш нужда от помощ.

Да, ама само алгоритъмът няма да помогне. Трябва да измисли и как да итерира през интервали в свързан списък, което е изискване на сортирането на Шел.

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

11 декември 201213 г.

Ако успееш да запишеш елементите на списъка в последователни места в паметта то следния линк може да ти е полезен: http://www.cs.umd.ed...Op/pointer.html

Редактирано 11 декември 201213 г. от Enhuntres (преглед на промените)

11 декември 201213 г.

Автор

Ще извиняваш за въпроса, но ще можеш ли да ми помогнеш да ми дадеш някакво начало... Благодаря

11 декември 201213 г.

Идеята е, да заделиш голям блок от паметта (за размера сам трябва да се сетиш). В него с помощта на адресната аритметика можеш да направиш така, че елементите на списъка да са подредени един след друг през sizeof(elem) битове (това, решава проблема и със стъпката на алгоритъма). Разгледай линка, ще помогне да си го представиш.

11 декември 201213 г.

Автор

Задачата е готово, но сортирането стана много объркано....

#include<iostream>
#include<fstream>
#include<string>
#include<cstdlib>
#include<ctime>
using namespace std;
/*int find_num(elem *st, int n);		  // vra6ta stoinostta na n-iq element
void shellsort(elem *start,int n);	  // shellsort pri koeto 'n' e broq na elementite v spisaka
void call_shell_sort(elem *start);	  // izvikvane shellsort
void replace_elem(elem *&start,int b, int r);  //zamestvane na stoinostta na element nomer 'b' ot spisaka sas stoinostta na r*/
int br_both=0;  
const int N=20;
struct elem{
  int key;
  elem *next;
  elem *prev;
}
*start = NULL;
void shellsort (elem *start, int n);
void add_b(int n)
{
elem *p=start;
start=new elem;
start->next=p;
start->prev=NULL;
start->key=n;
if(p)
  p->prev=start;
}
void CreateFile()
{
	 int chislo = 0;
	 srand(time(NULL));
	 ofstream file;
	 file.open("file.txt");
	    if (file.is_open())
	    {
		    for(int i=0;i<N;i++)    //Добавяне на рандом числа в файл
		    {
			    chislo = rand()%2000; //рандам числата за в интервал от 1–500
			    file << chislo << endl;
		    }
		    file.close();
	    }
    else cout << "Unable to open file";
}
void ReadFile()
{
    int b = 0 ;
    CreateFile();
    ifstream file;
    file.open("file.txt");
    if (file.is_open())
    {
	    while (file >> b)
		 {
		    //add(start, b);
		    add_b(b);
		 }
    }
	    file.close();
}
  void list()
{
if(start)
{
  cout<<"\n The list:"<<endl;
  elem *p=start;
  while(p)
  {
   cout<<p->key<<"\t";
   p=p->next;
  }
}
else
  cout<<"\n Empty list";
}
   int find_num(elem *st, int n)    // n- nomera na koi element trqbva da stigne, vrashta stoinosta na tozi element
{
	 int br=0;
	 while(br!=n)
	 {
	    st=st->next;
	    br++;
	 }
	 return st->key;
}
void replace_num(elem *start, int n, int m)  //smenq dvete stoinostti na elementite
{
    elem *p1=start,*p2=start;
    int br1=0,br2=0,tmp;
    while(br1!=n)
    {
	    br1++;
	    p1=p1->next;
    }
    while(br2!=m)
    {
	    br2++;
	    p2=p2->next;
    }
    tmp=p1->key;
    p1->key=p2->key;
    p2->key=tmp;
}
int count_list(elem *start)//broi kolko elementa ima spisuka
{
   int count_br=0;
   while(start)
   {
	   count_br++;
	   start=start->next;
   }
   return count_br;
}
void call_shell_sort(elem *start)    //s otdelna funkciq zashtoto shell-a iska broq na elementite,koito sa ot drugata funkciq
{
    cout<<"\n Sorting is ready "<<endl;
    int n=count_list(start);
    shellsort(start,n);
}
void replace_elem(elem *&start,int b, int r)  //prisvoqva na nomera stoinost
{
    elem *p=start;
    int i=0;
    while(i!=b)
    {
	    p=p->next;
	    i++;
    }
    p->key=r;   //r - stoinostta koqto se slaga
}
void shellsort (elem *start, int n)
{
    int h, i, j, k,g;
    for (h = n; h /= 2;) {
	    for (i = h; i < n; i++) {
		    k = find_num(start,i);
		    for (j = i; j >= h && k <find_num(start,(j-h)); j -= h) {
			    g=find_num(start,(j-h));
			    replace_elem(start,j,g);
    br_both ++;
		    }
		    replace_elem(start,j,k);
	    }
    }
}
void sortlist()
{
cout<<"Sortiran spisyk:";
list();
}
int menu()
{
int choice;
cout<<endl;
cout<<endl;
cout<<" M E N U "<<endl;
cout<<endl;
cout<<"1.Syzdavane na fail"<<endl;
cout<<"2.Zapylvane na spisyka s chisla"<<endl;
cout<<"3.Izvejdane na spisyka"<<endl;
cout<<"4.Sortirane na spisyka"<<endl;
cout<<"5.Izvejdane na spisyka"<<endl;
cout<<endl;
cout<<"Vyvedete vashiqt izbor: ";
cin>>choice;
return choice;
}
int main()
{

int choice;
do
{
  choice=menu();
switch (choice)
{
case 1: CreateFile();break;
case 2: ReadFile();break;
case 3: list();break;
case 4: call_shell_sort(start);break;
case 5: sortlist();break;
}
}while(choice!=0);
return 0;
}

11 декември 201213 г.

Написаното не е ефективно като алгоритъм.

Опитай с адресите да работиш.

Така написана програмата обхожда всички елементи от началото на списъка до търсения елемент при всяко извикване на find_num .

Идеята е точно това последователно обхождане да не се случва.

11 декември 201213 г.

Автор

Да обаче като не знам как подредя числата в паметта последователно.... Някакви идеи?

11 декември 201213 г.

Ако успееш да запишеш елементите на списъка в последователни места в паметта

Това си е абсолютна жива гавра с идеята на свързания списък. За какво тогава, са му връзки към предишен и следващ елемент?

Да обаче като не знам как подредя числата в паметта последователно....
Някакви идеи?

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

Искаш идея нали - ето. Може доста да се оптимизира, но това е само за насочване. После се оправяш сам.
1. правиш си два указателя (итератори) първия сочи към първия елемент, а втория го отместваш на един текущ интервал нататък.
2. сравняваш и ако трябва разместваш двата елемента към които сочат указателите
3. отместваш двата указателя с 1
повтаряш от 2, докато втория стигне края на списъка
повтаряш от 1, докато е имало поне едно разместване
повтаряш от 1, за всички интервали.
Това, може да го разглеждаш, като едновременно сортиране по метода на мехурчето на всички "подсписъци", каквато е идеята на метода на Шел - с тази разлика, че когато е като масив, можеш да си позволиш лукса да ги сортираш един по един.

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

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

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

Това си е абсолютна жива гавра с идеята на свързания списък.

Прав си, губи се идеята на списъка. Оттеглям предложението, за записване в последователни адреси.

Редактирано 12 декември 201213 г. от Enhuntres (преглед на промените)

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

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