сортировка двусвязногосписка - Общие вопросы C/C++

nikzntu · 31.03.2009, 00:16

задача , отсортировать диски по году издания методом Шелла
подскажите что не так

Код:

 #include<iostream>
#include<conio.h>
#include<string.h>
#include <list>
using namespace std;

struct Disc
{
  int number,artist_quantity,year;
  char Name[20],AllArtists[256];
string Art;
};

struct elem{
  Disc data;
    elem *prev,*next;
    };
   
elem *first,*last,*cur;
char SearchName[30];
int n; 

void Add(){

    elem *el=new elem;
    cout<<"Enter Dics number:"; 
    cin>>el->data.number;
    cout<<"Enter Dics Name:"; 
    cin>>el->data.Name;
    cout<<"Enter Artist quantity:"; 
    cin>>el->data.artist_quantity;
    cout<<"Enter Artists:";
    cin>>el->data.AllArtists;
    cout<<"Enter Year:"; 
    cin>>el->data.year;
    if(first==NULL){
        el->prev=NULL;
        el->next=NULL;
        first=el;
        last=first;
     } 
  else
        if    (first->next==NULL ){
            el->prev=first ;
            el->next=NULL ;
            first->next =el ;
            last =el ;
        } 
        else {
            el->prev =last ; 
            el->next =NULL ;
            last->next =el ;
            last=el ;
        }

}
void Sort4(int n)
{
 elem *el=new elem;
elem *first,*last,*cur;
next=first;
cur=first;
prev=last;
	next=next->data.year;

cur=cur->data.year;
prev=prev->data.year;
int trash=0;
 bool f=true;
 for (int i=1; (i<=n)&&(f=true); i++)
 {
 f=false;
 for (int j=i; j<=n-i; j++)	
 {
 if (cur>next)	
 {
 trash=cur;	
 cur=next;	
 next=trash;
 f=true;
 }
 }
 for (int j=n-i-1; j>i ; j--) 	
 {
 if (cur<prev)	
 {
 trash=cur;	
cur=prev;
prev=trash;
 f=true;
 }
 }
 }
}

void show(){
    cout<<cur->data.number<<" "<<cur->data.Name<<" "<<cur->data.artist_quantity<<" "<<cur->data.AllArtists<<' '<<cur->data.year<<endl;
}



void main(){
    int i;
    cout<<"Enter Disc quantity:"; cin>>n;
    for(i=0;i<n;i++)
        Add();
    cout<<"Enter the name of artist which disk :"; 
 cur=first;
   for(i=0;i<n;i++){show();
   
        cur = cur->next;
    }
        
    getch();
}

Svetlag · 31.03.2009, 14:42

Для начала разберитесь с типами данных и объявите их: то они <elem*>, то <int>

Код:

void Sort4(int n)
{
	elem *el=new elem;
	elem *first,*last,*cur;

	next=first;
	cur=first;
	prev=last;
	
	next=next->data.year;
	cur=cur->data.year;
	prev=prev->data.year;

nikzntu · 31.03.2009, 18:21

сделал так , все равно куча ошибок вылазит

Код:

 #include<iostream>
#include<conio.h>
#include<string.h>
#include <list>
using namespace std;

struct Disc
{
  int number,artist_quantity,year;
  char Name[20],AllArtists[256];
};

struct elem{
  Disc data;
    elem *prev,*next;
    };
   
elem *first,*last,*cur;
char SearchName[30];
int n; 

void Add(){

    elem *el=new elem;
    cout<<"Enter Dics number:"; 
    cin>>el->data.number;
    cout<<"Enter Dics Name:"; 
    cin>>el->data.Name;
    cout<<"Enter Artist quantity:"; 
    cin>>el->data.artist_quantity;
    cout<<"Enter Artists:";
    cin>>el->data.AllArtists;
    cout<<"Enter Year:"; 
    cin>>el->data.year;
    if(first==NULL){
        el->prev=NULL;
        el->next=NULL;
        first=el;
        last=first;
     } 
  else
        if    (first->next==NULL ){
            el->prev=first ;
            el->next=NULL ;
            first->next =el ;
            last =el ;
        } 
        else {
            el->prev =last ; 
            el->next =NULL ;
            last->next =el ;
            last=el ;
        }

}
void Sort4()
{

elem *el=new elem;
	elem *first,*last,*cur;

	next=first;
	cur=first;
	prev=last;
	
	next=next->data.year;
	cur=cur->data.year;
	prev=prev->data.year;

int trash=0;
 bool f=true;
 for (int i=1; (i<=n)&&(f=true); i++)
 {
 f=false;
 for (int j=i; j<=n-i; j++)	
 {
 if (cur>first)	
 {
 trash=cur;	
 cur=first;	
 first=trash;
 f=true;
 }
 }
 for (int j=n-i-1; j>i ; j--) 	
 {
 if (cur<last)	
 {
 trash=cur;	
cur=last;
last=trash;
 f=true;
 }
 }
 }
}

void show(){
    cout<<cur->data.number<<" "<<cur->data.Name<<" "<<cur->data.artist_quantity<<" "<<cur->data.AllArtists<<' 

'<<cur->data.year<<endl;
}



void main(){
    int i;
    cout<<"Enter Disc quantity:"; cin>>n;
    for(i=0;i<n;i++)
        Add();
    cout<<"Enter the name of artist which disk :"; 
 cur=first;
   for(i=0;i<n;i++){show();
   
        cur = cur->next;
    }
        
    getch();
}

nikzntu · 31.03.2009, 20:19

вобщем вот так компилется , но не сортирует

Код:

если можешь посмотри функцию сорт , ошибок не выдает, но и не сортирует  #include<iostream>
#include<conio.h>
#include<string.h>
#include <list>
using namespace std;

struct Disc
{
  int number,artist_quantity,year;
  char Name[20],AllArtists[256];
};

struct elem{
  Disc data;
    elem *prev,*next;
    };
   
elem *first,*last,*cur,*trash;
char SearchName[30];
int n; 

void Add(){

    elem *el=new elem;
    cout<<"Enter Dics number:"; 
    cin>>el->data.number;
    cout<<"Enter Dics Name:"; 
    cin>>el->data.Name;
    cout<<"Enter Artist quantity:"; 
    cin>>el->data.artist_quantity;
    cout<<"Enter Artists:";
    cin>>el->data.AllArtists;
    cout<<"Enter Year:"; 
    cin>>el->data.year;
    if(first==NULL){
        el->prev=NULL;
        el->next=NULL;
        first=el;
        last=first;
     } 
  else
        if    (first->next==NULL ){
            el->prev=first ;
            el->next=NULL ;
            first->next =el ;
            last =el ;
        } 
        else {
            el->prev =last ; 
            el->next =NULL ;
            last->next =el ;
            last=el ;
        }

}
void Sort()
{


cur=cur->next;
    cur->data.year;

trash=0;
 bool f=true;
 for (int i=1; (i<=n)&&(f=true); i++)
 {
 f=false;
 for (int j=i; j<=n-i; j++)    
 {
 if (cur>first)    
 {
 trash=NULL;    
 cur=first;    
 first=trash;
 f=true;
 }
 }
 for (int j=n-i-1; j>i ; j--)     
 {
 if (cur<last)    
 {
 trash=cur;    
cur=last;
last=trash;
 f=true;
 }
 }
 }
}

void show(){
  cout<<cur->data.number<<" "<<cur->data.Name<<" "<<cur->data.artist_quantity<<" "<<cur->data.AllArtists<<' '<<cur->data.year<<endl;
}



void main(){
    int i;
    cout<<"Enter Disc quantity:"; cin>>n;
    for(i=0;i<n;i++)
        Add();
void Sort();
    cout<<"Enter the name of artist which disk :"; 
 cur=first;
   for(i=0;i<n;i++){show();
   
        cur = cur->next;
    }
        
    getch();
}

Svetlag · 01.04.2009, 14:19

В пред. своем сообщении я имела ввиду что-то вроде этого

Код:

void Sort4(int n)
{
	elem *el=new elem;
	elem *first,*last,*cur;

	elem* next=first;
	cur=first;
	elem* prev=last;
	
	int next_year=next->data.year;
	int cur_year=cur->data.year;
	int prev_year=prev->data.year;

И еще, метод Шелла по-моему больше применим к индексируемым последовательностям, а ваш алгоритм на него мало похож. Опишите на словах, что хотите сделать.
Какие ошибки еще вижу:
1.Если сравниваете год издания, то так

Код:

if (cur->data.year>first->data.year)

2.Здесь присваивается true

Код:

for (int i=1; (i<=n)&&(f=true); i++)

Надо

Код:

for (int i=1; (i<=n)&&(f); i++)

3.В этом и следующем таком жу цикле не изменяется положение сравниваемых елементов списка, т.е. нужно cur изменять примерно так. И почему сравнивается всегда с первым елемнтом first?

Код:

for (int j=i; j<=n-i; j++)    
 {
 if(cur!=NULL)
 if (cur->data.year>first->data.year)    
 {
 trash=NULL;    
 cur=first;    
 first=trash;
 f=true;
 }
 cur = cur->next;
 }

4. ошибка в вызове функции Sort

Код:

void main(){
    int i;
    cout<<"Enter Disc quantity:"; cin>>n;
    for(i=0;i<n;i++)
        Add();
    Sort();
    cout<<"Enter the name of artist which disk :"; 
 cur=first;
   for(i=0;i<n;i++){show();
           cur = cur->next;
    }       
    getch();
}

nikzntu · 01.04.2009, 21:39

В задании написано сделать сортировку методом шелла
исправил те элементы кода на про которые вы писали , но все равно не работает , видать чего-то недопонял

Код:

 #include<iostream>
#include<conio.h>
#include<string.h>
#include <list>
using namespace std;

struct Disc
{
  int number,artist_quantity,year;
  char Name[20],AllArtists[256];
};

struct elem{
  Disc data;
    elem *prev,*next;
    };
   
elem *first,*last,*cur,*trash;
char SearchName[30];
int n; 

void Add(){

    elem *el=new elem;
    cout<<"Enter Dics number:"; 
    cin>>el->data.number;
    cout<<"Enter Dics Name:"; 
    cin>>el->data.Name;
    cout<<"Enter Artist quantity:"; 
    cin>>el->data.artist_quantity;
    cout<<"Enter Artists:";
    cin>>el->data.AllArtists;
    cout<<"Enter Year:"; 
    cin>>el->data.year;
    if(first==NULL){
        el->prev=NULL;
        el->next=NULL;
        first=el;
        last=first;
     } 
  else
        if    (first->next==NULL ){
            el->prev=first ;
            el->next=NULL ;
            first->next =el ;
            last =el ;
        } 
        else {
            el->prev =last ; 
            el->next =NULL ;
            last->next =el ;
            last=el ;
        }

}
void Sort()
{	cur=cur->next;
 cur->data.year;
trash=0;
 bool f=true;
for (int i=1; (i<=n)&&(f); i++)
 { f=false;
 for (int j=i; j<=n-i; j++)    
 if (cur->data.year>first->data.year)  
 { trash=NULL;    
 cur=first;    
 first=trash;
 f=true;
 }
 for ( int j=i ; j<=n-i; j++)    
 {
 if(cur!=NULL)
 if (cur->data.year>first->data.year)    
 {
 trash=NULL;    
 cur=first;    
 first=trash;
 f=true;
 }
 cur = cur->next;
 }
 }
}

void show(){
  cout<<cur->data.number<<" "<<cur->data.Name<<" "<<cur->data.artist_quantity<<" "<<cur->data.AllArtists<<' '<<cur->data.year<<endl;
}
void main(){
    int i;
    cout<<"Enter Disc quantity:"; cin>>n;
    for(i=0;i<n;i++)
        Add();
 Sort();
    cout<<"Enter the name of artist which disk :"; 
 cur=first;
   for(i=0;i<n;i++){show();
           cur = cur->next;
    }
    getch();
}

Nomlpppp · 02.04.2009, 01:28

А что это вы делаете в функции сортировки

Код:

 trash=NULL;    
 cur=first;    
 first=trash;

Можно тогда уже так:

Код:

 cur=first;    
 first=NULL;

одно и то-же

Может вы имели в виду:

Код:

 trash=cur;    //<- 
 cur=first;    
 first=trash;

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

nikzntu · 02.04.2009, 13:13

если можете , то куньте код всей проги , что-то я не могу в шарить в чем заковірка

Svetlag · 02.04.2009, 19:14

Попробуйте

Код:

void Sort()
{	
  bool f=true;
  for (int i=1; (i<=n)&&(f); i++)
  {
    cur=first;
    elem* next = first->next;	
    f=false;
    for (int j=i-1; j<=n-i; j++) 
    {
	if(cur!=NULL && next!=NULL)
	if (cur->data.year>next->data.year)  
	{ 
      	  cur->next = next->next;
	  if(next->next!=NULL) next->next->prev = cur;
	  if(next->next==NULL) last = cur;

               next->prev = cur->prev;
  	  if(cur->prev!=NULL)	cur->prev->next = next;
	  if(cur->prev==NULL) first = next;

	  next->next = cur;				
	  cur->prev = next;

	  cur = next->next;
	  next = cur->next;
	  f=true;
	}
	else
	{
	  cur = cur->next;
	  next = cur->next;
	}
      }

      cur = last;
      elem* prev = last->prev;
      for ( j=i-1 ; j<=n-i; j++)    
      {
	if(cur!=NULL && prev!=NULL)
	if (cur->data.year<prev->data.year)  
	{ 
               cur->prev = prev->prev;
	  if(prev->prev!=NULL) prev->prev->next = cur;
	  if(prev->prev==NULL) first = cur;

	  prev->next = cur->next;
	  if(cur->next!=NULL)	cur->next->prev = prev;
	  if(cur->next==NULL) last = prev;

	  prev->prev = cur;				
	  cur->next = prev;
					
	  cur = prev->prev;
	  prev = cur->prev;
	  f=true;
	}
	else
	{
	  cur = cur->prev;			
	  prev = cur->prev;
	}
         }
       }
}

31.03.2009, 14:42	#2
Svetlag Пользователь Регистрация: 24.02.2009 Сообщений: 85	Для начала разберитесь с типами данных и объявите их: то они <elem>, то <int>* Код: `void Sort4(int n) { elem el=new elem; elem first,last,cur; next=first; cur=first; prev=last; next=next->data.year; cur=cur->data.year; prev=prev->data.year;`

01.04.2009, 14:19	#5
Svetlag Пользователь Регистрация: 24.02.2009 Сообщений: 85	В пред. своем сообщении я имела ввиду что-то вроде этого Код: `void Sort4(int n) { elem el=new elem; elem first,last,cur; elem* next=first; cur=first; elem* prev=last; int next_year=next->data.year; int cur_year=cur->data.year; int prev_year=prev->data.year;` И еще, метод Шелла по-моему больше применим к индексируемым последовательностям, а ваш алгоритм на него мало похож. Опишите на словах, что хотите сделать. Какие ошибки еще вижу: 1.Если сравниваете год издания, то так Код: `if (cur->data.year>first->data.year)` 2.Здесь присваивается true Код: `for (int i=1; (i<=n)&&(f=true); i++)` Надо Код: `for (int i=1; (i<=n)&&(f); i++)` 3.В этом и следующем таком жу цикле не изменяется положение сравниваемых елементов списка, т.е. нужно cur изменять примерно так. И почему сравнивается всегда с первым елемнтом first? Код: `for (int j=i; j<=n-i; j++) { if(cur!=NULL) if (cur->data.year>first->data.year) { trash=NULL; cur=first; first=trash; f=true; } cur = cur->next; }` 4. ошибка в вызове функции Sort Код: `void main(){ int i; cout<<"Enter Disc quantity:"; cin>>n; for(i=0;i<n;i++) Add(); Sort(); cout<<"Enter the name of artist which disk :"; cur=first; for(i=0;i<n;i++){show(); cur = cur->next; } getch(); }`

02.04.2009, 01:28	#7
Nomlpppp Пользователь Регистрация: 26.02.2009 Сообщений: 51	А что это вы делаете в функции сортировки Код: `trash=NULL; cur=first; first=trash;` Можно тогда уже так: Код: `cur=first; first=NULL;` одно и то-же Может вы имели в виду: Код: `trash=cur; //<- cur=first; first=trash;` Только такакя перестановка со списками не прокатит. Надо дорабатывать... Последний раз редактировалось Nomlpppp; 02.04.2009 в 01:34.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Сортировка Шелла и Шейкер-сортировка	AleksandrMakarov	Паскаль, Turbo Pascal, PascalABC.NET	11	11.03.2012 12:18
сортировка	CrazyRabbit	Паскаль, Turbo Pascal, PascalABC.NET	3	27.10.2008 21:04
Сортировка	Form1	Общие вопросы Delphi	3	17.06.2008 22:24
1. Сортировка Шелла по убыванию 2. Сортировка вставками по убыванию	Arkuz	Помощь студентам	1	25.09.2007 17:16

02.04.2009, 13:13	#8
nikzntu Пользователь Регистрация: 13.01.2009 Сообщений: 10	если можете , то куньте код всей проги , что-то я не могу в шарить в чем заковірка