Сортировка - Помощь студентам

Kot070 · 23.07.2014, 09:44

элементы списка предназначены для хранения данных следующих типов: длинное целое число,
вещественное число двойной точности, строка символов(не более 50), одиночный символ.
Необходимо обеспечить сортировку по возрастанию, по убыванию и поиск заданного значения.

Помогите сделать сортировку,сортировка пузырьком в целом понятна. Сравниваем первый и следующий элемент и если первый больше то меняем их местами и все это происходит в цикле.
Проблема в том что я не могу применить эту сортировку для двусвязного списка, в сортировке ведь массивы а я не понимаю как переделать для своей ситуации.Буду очень благодарен если сделаете один случай моей сортировке а второй сам попробую разобрать

Прошу прощения за оформление
main.c

Код:

#include <stdio.h>
#include "list.h"
#include "subj.h"
#include <stdlib.h>
 
void PrintList(struct list * s)
{
    int i=0;
    struct item * e;
 
    printf("List: %p  Head: %p  Tail %p\n",s,s->first,s->last);
    e=s->first;
 
    while (e)
    {
        printf("%d\t%p\t%p\t%p\n",i,e,e->prev,e->next);
        e=e->next;
        i++;
    }
}
 
int main()
{
    struct list * l;
    struct base * b;
    int c,a,del,yn;
    
    l=(struct list *)malloc(sizeof(struct list));
    l->first=NULL;
    l->last=NULL;
    
    do
    {
         system("cls");
         printf(" choose the action:\n\n");
         printf(" 1 - add elemement to the list\n"
                " 2 - print all list\n"
                " 3 - find list elements\n"
                " 4 - sort the list\n"
                " 5 - delete one element\n"
                " 6 - clear all list\n"
                " 7 - exit\n\n"
                " your choice: ");
         c=CheckDataInt(1,7);
         
         switch (c)
         {
                case 1:
                     system("cls");
                     printf(" choose an element which you want to add:\n\n"
                            " 1 - circle;\n"
                            " 2 - kvadrat;\n"
                            " 3 - rhombus;\n"
                            " 4 - polygon;\n\n"
                            " 0 - nothing;\n\n"
                            " your choice: ");
                     a=CheckDataInt(0,4);
                     switch (a)
                     {
                            case 0:
                                 break;
                                 break;
                            case 1:
                                 b=Create(itDchislo);
                                 break;
                                 
                            case 2:
                                 b=Create(itDtoch);
                                 break;
                                 
                            case 3:
                                 b=Create(itStroka);
                                 break;
                                 
                            case 4:
                                 b=Create(itSimvol);
                                 break;
                     }
                     if (b) Input(l,b);
                     break;
                
                case 2:
                     system("cls");
                     PrintList(l);
                   //  getch();
                     break;
                     
                case 3:
                     system("cls");
                     FindObj(l);
                    // getch();
                     break;
                
                case 4:
                     system("cls");
                     Sort(l);
                    // getch();
                     break;
                     
                case 5:
                     system("cls");
                     printf(" input the number of element, which you want to delete: ");
                     scanf("%d",&del);
                     Delete(l,del);
                     printf(" successful!");
                     //getch();
                     break;
                case 6:
                     system("cls");
                     printf(" do you really want to clear list?\n\n"
                            " 1 - yes;\n"
                            " 2 - no;\n\n"
                            " your choice: ");
                     yn=CheckDataInt(1,2);
                     if (yn==1) 
                     {
                            Clear(l);
                            printf("\n successful!");
                     }
                     else printf(" \n list wasn't cleared!");
                    // getch();
                     break;
                                     
         }
    }
    while (c!=7);
    
    Clear(l);
    free(l);
    return 0;
}

Kot070 · 23.07.2014, 09:45

list.c

Код:

#include <stdlib.h>
#include "list.h"
 
void Add(struct list * s, struct item * e)
{
    if (s && e)
    {
       e->next=NULL;
       e->prev=s->last;
       
       if (s->first)
          s->last->next=e;
       else
          s->first=e;
       s->last=e;
    }
}
 
int Count(struct list * s)
{
    int i=0;
    struct item * e;
 
    if (s)
    {
       e=s->first;
       while (e!=NULL)
       {
           e=e->next;
           i++;
       }
    }
    return i;
}
 
struct item * GetItem(struct list * s, int number)
{
    int i=0;
    struct item * e;
 
    if (!s || number<0 || !s->first)
    return NULL;
    
    e=s->first;
    i=0;
    while (e)
    {
       if (i==number) return e;
       e=e->next;
       i++;
    }
    return NULL;
}
 
struct item * Remove(struct list * s, int number)
{
       struct item *p;
 
       p=GetItem(s,number);
       if (p)
       {
           if (p->prev)
           {
              if (p->next)
              {
                  p->next->prev=p->prev;
                  p->prev->next=p->next;
              }
              else
              {
                  s->last=p->prev;
                  p->prev->next=NULL;
              }
           }
           else
           {
              if (p->next)
              {
                  s->first=p->next;
                  p->next->prev=NULL;
              }
              else
              {
                  s->first=NULL;
                  s->last=NULL;
              }
           }
        return p;
      }
      return NULL;
      
}
 
void Delete(struct list * s, int number)
{
   struct item * e;
   e=Remove(s,number);
   if (e)
   {
     free(e);
     e=NULL;
   }
}
 
void Insert(struct list * s, struct item * e, int number)
{
    struct item * x;
 
    if (!e)
        return;
    if (number<0)
        number=0;
    x=GetItem(s,number);
    if (x)
        {
            e->prev=x->prev;
            e->next=x;
            if (!x->prev)
            {
                s->first=e;
                x->prev=e;
            }
            else
            {
                x->prev->next=e;
                x->prev=e;
            }
        }
    else Add(s,e);
}
 
void Clear(struct list * s)
{
     struct item * x, * y;
     
     if (s)
     {
         x=s->first;
         while (x)
         {
               y=x->next;
               free(x);
               x=y;
         }
         s->first=NULL;
         s->last=NULL;
     }
} 
 
int GetIndex(struct list * s, struct item * e)
{
    struct item * x;
    int i=0;
    
    if (s && e && s->first)
    {
         x=s->first;
         while (s)
         {
               if (e==x)
               return i;
               x=x->next;
               i++;
         }
    }
    return -1;
}

list.h

Код:

#include <stdlib.h>
 
struct item
{
     struct item *next;
     struct item *prev;
};
 
struct list
{
     struct item *first;
     struct item *last;
};
 
/*min basis*/
void Add(struct list * s, struct item * e);
void Delete(struct list * s, int number);
struct item * GetItem(struct list * s, int number);
 
/*large basis*/
struct item * Remove(struct list * s, int number);
void Insert(struct list * s, struct item * e, int number);
int Count(struct list * s);
void Clear(struct list * s);
int GetIndex(struct list * s, struct item * e);

Kot070 · 23.07.2014, 09:46

subj.h

Код:

#include "list.h"
 
enum ItemType {itNone, itDchislo, itDtoch, itStroka, itSimvol};
 
struct base
{
     struct item *next;
     struct item *prev;
     enum ItemType type;
     int a;
};
 
int CheckIntPos(int a);
int CheckDataInt(int a, int b);
struct base * Create(enum ItemType t);
void Print(struct base * b);
void PrintList(struct list * s);
void Input(struct list * s, struct base * b);
void FindObj(struct list * s);
void Sort(struct list * s);
void SortUp(struct list * s);
void SortDown(struct list * s);

Kot070 · 23.07.2014, 09:49

subj.c

Код:

#include "subj.h"
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct chislo
{
   struct item *next;
   struct item *prev;
   enum ItemType type;
   int a;
};
struct tochnost
{
   struct item *next;
   struct item *prev;
   enum ItemType type;
   double a;
};
struct stroka
{
   struct item *next;
   struct item *prev;
   enum ItemType type;
   char a[50];
};
struct simvol
{
   struct item *next;
   struct item *prev;
   enum ItemType type;
   char a[1];
};
void PrintChislo(struct chislo * e);
void PrintTochnost(struct tochnost * e);
void PrintStroka(struct stroka * e);
void PrintSimvol(struct simvol * e);
void InputChislo(struct chislo * b);
void InputTochnost(struct tochnost * b);
void InputStroka(struct stroka * b);
void InputSimvol(struct simvol * b);
int CheckIntPos(int a)
{
    int c;
    do
    {
         c=-1;
         fflush(stdin);
         scanf("%d",&c);
         if (c<a)
         printf(" invalid input! repeat: ");
    }
    while (c<a);
    return c;
}
int CheckDataInt(int a, int b)
{
    int c;
    do
    {
         c=-1;
         fflush(stdin);
         scanf("%d",&c);
         if (c<a || c>b)
         printf(" invalid input! repeat: ");
    }
    while (c<a || c>b);
    return c;
}
struct base * Create(enum ItemType t)
{
   struct base * b = NULL;
   switch (t)
   {
      case itDchislo:
           b=(struct base *)malloc(sizeof(struct chislo));
           break;
      case itDtoch:
           b=(struct base *)malloc(sizeof(struct tochnost));
           break;
      case itStroka:
           b=(struct base *)malloc(sizeof(struct stroka));
           break;
      case itSimvol:
           b=(struct base *)malloc(sizeof(struct simvol));
           break;
   }
   if (b) b->type=t;
   return b;
}
void Print(struct base * b)
{
   if (b)
      switch (b->type)
      {
        case itDchislo:
             PrintChislo((struct chislo *)b);
             break;
        case itDtoch:
             PrintTochnost((struct tochnost *)b);
             break;
        case itStroka:
             PrintStroka((struct stroka *)b);
             break;
        case itSimvol:
             PrintSimvol((struct simvol *)b);  
             break;
        default:
          printf("error: object type unknown!\n");
      }
   else printf("error: null pointer!\n");
}
void PrintChislo(struct chislo * e)
{
   printf("[Chislo]:\n"
          "Chislo -> %d\n",e->a);
}
void PrintTochnost(struct tochnost * e)
{
   printf("[Tochnost]:\n"
          "Chislo-> %f\n",e->a);
}
void PrintStroka(struct stroka * e)
{
   printf("[stroka]:\n"
          " stroka-> %c\n",e->a);
}
void PrintSimvol(struct simvol * e)
{
   printf("[Simvol]:\n"
          "Simvol -> %c\n",e->a);
}
void PrintList(struct list * s)
{
   int i=0;
   struct item * e;
   if (s && s->first)
   {
       e=s->first;
       while (e)
       {
          printf("%d ",i);
          Print((struct base *)e);
          e=e->next;
          printf("\n");
          i++;
       }
   }
   else printf(" error: there is no list!\n");
}
void Input(struct list * s, struct base * b)
{
     if (!s || !b)
     {
            printf("\n error: null pointer :C");
            return;
     }
     switch (b->type)
     {
        case itDchislo:
             InputChislo((struct chislo *)b);
             break;
        case itDtoch:
             InputTochnost((struct tochnost *)b);
             break;
        case itStroka:
             InputStroka((struct stroka *)b);
             break;
        case itSimvol:
             InputSimvol((struct simvol *)b);
             break;
        default:
             printf(" error: object type unknown!\n");          
     }
     Add(s,(struct item *)b);
}
void InputChislo(struct chislo * b)
{
     if (b)
     {
           printf(" input chislo: ");
           b->type=itDchislo;
     }
     else return;
}
void InputTochnost(struct tochnost * b)
{
     if (b)
     {
           printf(" input tochnoe chislo: ");
           b->type=itDtoch;
     }
     else return;
}
void InputStroka(struct stroka * b)
{
     if (b)
     {
           printf(" input stroka: ");
           b->type=itStroka;
     }
     else return;
}
void InputSimvol(struct simvol * b)
{
     if (b)
     {
           printf(" input simvol: ");
           b->type=itSimvol;
     }
     else return;
}
void Sort(struct list * s)
{
     int c;
     printf(" sort:\n"
            " 1 - up;\n"
            " 2 - down\n\n"
            " your choice: ");
     scanf("%d",&c);
     if (c==1) SortUp(s);
     if (c==2) SortDown(s);
}
void main()
{
   char str[50];
   int a;
   sprintf(str, "%d", a);
   char ch[50];
    double b; 
    gcvt(b,5,ch);
}

Kot070 · 23.07.2014, 09:49

мой вариант сортировки

Код:

void SortUp(struct list * s)
{
   int i,j,min_i,n;
     struct item * b, * a;
     
     n=Count(s);
     if (n==0)
     {
          printf(" there is nothing to sort!\n");
          return;
     }
     
      for (i=0; i<n-1; i++)
     {
         min_i=i;
         for (j=i+1; j<n; ++j)
         {
             if (((struct base *)GetItem(s,j))->a<((struct base *)GetItem(s,min_i))->a) 
             min_i=j;
         }
      if (min_i != i)
            Insert(s,Remove(s,min_i),i);
     }
}

Zenon · 23.07.2014, 23:15

В сортировке массивы с доступом по индексу, но конкретно в сортировке пузырьком эти индексы
- либо меняются на 1 - что соответствует переходу к предыдущему или следующему элементу списка
- либо начинается очередная итерация от начала массива - что соответствует переходу к первому элементу списка

от этого и пляшите

Опции темы	Поиск в этой теме
Версия для печати Отправить по электронной почте	Поиск в этой теме: Расширенный поиск

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Быстрая сортировка(сортировка Хоара). Сортировка фрагмента массива [C++]	druger	Помощь студентам	0	20.04.2012 15:49
Быстрая сортировка(сортировка хаора) с++	LustHunter	Помощь студентам	3	07.10.2011 19:37
Сортировка массива методами предсортировки и слияния, и пирамидальная сортировка.	lenny_24	Помощь студентам	2	17.04.2011 18:57
паскаль,одномерный массив,сортировка вставка,сортировка убывания,от максимального до конца	немозг	Помощь студентам	11	06.02.2010 21:57
Сортировка файлов в Explorer vs сортировка в Delphi	mutabor	Общие вопросы Delphi	11	04.09.2009 14:32

23.07.2014, 23:15	#6
Zenon Пользователь Регистрация: 03.07.2014 Сообщений: 32	В сортировке массивы с доступом по индексу, но конкретно в сортировке пузырьком эти индексы - либо меняются на 1 - что соответствует переходу к предыдущему или следующему элементу списка - либо начинается очередная итерация от начала массива - что соответствует переходу к первому элементу списка от этого и пляшите