Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 06.06.2009, 16:59   #1
Many
 
Регистрация: 06.06.2009
Сообщений: 6
По умолчанию Сортировки и поиск (таблица) (Си)

Здравствуйте! Проблема такая - курсовая по информатике "Сортировки и поиск", задание - "составить программу с использованием процедур и функций для сортировки таблицы заданным методом и двоичного поиска по ключу в таблице".
Метод сортировки - метод пузырька
Структура таблицы - "тип ключа=целый, длина ключа в байтах=8, хранение данных и ключей=вместе, число элементов таблиц=8-12"

И есть курсовая работа, в которой выполнено все, кроме условия "хранение вместе"..(то есть ключ со строкой должны хранится вместе, указатели не катят..). Дописал функцию, которая в процессе сортировки выдирает из строки ключ, но подставить затем куда надо не получается.. либо уходит в бесконечный цикл либо вообще рушится программа. Код изначально не мой,только правил его.. в программировании я практически полный ламер, поэтому никак не разберусь(

Код:
#include<stdio.h>
#include<string.h>
#define MAXSTRING 100
#define MAXELEM 100
#define SIZE 2
typedef struct ln{
  int key;
  char str[MAXSTRING];
  int size;
}line;


//------------------------------file read
void readf(FILE *fl,line **st){
  int a=1;
  while ( fscanf(fl,"%d",&st[st[a]->size]->key)!=EOF ){
    fscanf(fl,"%d",&st[st[a]->size]->key);
    fgets(st[st[a]->size]->str,MAXSTRING,fl);
    st[a]->size++;
  }
  st[a]->size--;
  // for(a=0;a<=size;++a)
  // {
  // printf("%i\n",st[a].key);
  // }
}

//------------------------------bubble sort
void ssort(line **st){
  int l=0,a=1,r,k,i,j;
  int temp;
  char stemp[MAXSTRING];
  r=st[a]->size;
  while(l<r)
    {
      //printf("%i %i\n",l,r);
      for( j = 0; j<r; j++ ){
	//printf("%i\n",j);
	if(st[j]->key>st[j+1]->key)
	  {
	    temp=st[j]->key;
	    strcpy(stemp,st[j]->str);
	    st[j]->key=st[j+1]->key;
	    strcpy(st[j]->str,st[j+1]->str);
	    st[j+1]->key=temp;
	    strcpy(st[j+1]->str,stemp);
	  }
      }
      --r;
    }
}

//------------------------------binary search
void bsearch (line **st){
  int m,a=1;
  int left=0,right=st[a]->size;

  int key;

  printf("Enter key: ");
  scanf("%i",&key);
  for(;;){
    m=(left+right)/2;
    if (key<st[m]->key)	right=m - 1;
    else if ( key>st[m]->key)	left=m + 1;
    else {printf("Key is found:\n%i\t%s\n",st[m]->key,st[m]->str);return;}
    if ( left > right ){printf("Key not found\n"); return;}
  }
}

//------------------------------unsorted print(вывод сод-го файла на экран)
void unsprint(FILE *fl,line **st){
  int a=0;
  int i=1;
  char c[MAXSTRING];
  //float k;
  printf("Key  Element\n");
  fseek(fl,0,SEEK_SET);
  while ( a <= st[i]->size ){
//fscanf(fl,"%f",&k);
    fgets(c,MAXSTRING,fl);
    printf("%s\n",c);
    a++;
  }
}

//------------------------------file print(печать после действия - сортировка или рассеивание)
void sprint(line **st){
  int i,a=1;
  if ( st[a]->size > 0 ){
    printf("Key\t\tElement\n");
    for(i=0;i<=st[a]->size;i++)printf("%i\t%s\n",st[i]->key,st[i]->str);
}
  else{printf("Struct is empty\n");return;}
}

//-----------------рассеивание (перераспределяет строки)
void revers(line **st){
  int l=0,a=1,r,k,i,j;
  int temp;
  char stemp[MAXSTRING];
  r=st[a]->size;
  while(l<r)
    {
         int i;
    for(i=0; i<=r/2-1; i++){
        temp=st[i]->key;
	    strcpy(stemp,st[i]->str);
	    st[i]->key=st[r-1-i]->key;
	    strcpy(st[i]->str,st[r-1-i]->str);
	    st[r-1-i]->key=temp;
	    strcpy(st[r-1-i]->str,stemp);
	  }
      --r;
    }
}

//------------------------------menu
int menu(){
  int m;
  printf("Program menu:\n");
  printf("1 - Sort\n");
  printf("2 - Unsort\n");
  printf("3 - Line search\n");
  printf("4 - Print file\n");
  printf("5 - Print result\n");
  printf("6 - Exit\n");
 printf("\nEnter action: ");
 scanf("%d",&m);
 return m;
}

//=======================================main
int main(int argc,char *argv[]){
  char *fn;
  FILE *f;
  int i;
  int m;
  int z=0;
  line st[MAXELEM],*stadr[MAXELEM];
  for(i = 0;i < MAXELEM; ++i)stadr[i] = &st[i];

  //if ( argc < 2 ) {printf("Invalid arguments\n"); return 1;} else
  fn=argv[1];
  if( (f=fopen("test.txt","r")) == NULL ) {printf("File doesn't exists\n"); return 1;}

readf(f,stadr);
 while(1)
   {
     m=menu();
     switch(m){

     case 1:{ssort(stadr);z=1;break;}

     case 2:{revers(stadr);z=1;break;}
     
     case 3:{if ( z )bsearch(stadr);else printf("You should sort first\n");break;}

     case 4:{unsprint(f,stadr);break;}

     case 5:{if ( z ) sprint(stadr);else printf("You should sort first\n");break;}

     case 6:{fclose(f);return 0;}


         default:{printf("\nInvalide menu action\n");break;}
     }}
}
тестовым файлом может послужить любой ASCII рисунок.. пример подсоединяю.
P.S.: заранее спасибо за помощь если сможете помочь..
Вложения
Тип файла: txt test.txt (2.6 Кб, 132 просмотров)

Последний раз редактировалось Many; 06.06.2009 в 17:05.
Many вне форума Ответить с цитированием
Старый 07.06.2009, 16:46   #2
Many
 
Регистрация: 06.06.2009
Сообщений: 6
По умолчанию

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

Код:
int get_key(char *a)
{
int i=0, res;
char r[10];
while (isdigit(a[i]) && a[i]!='.')
{
r[i]=a[i];
i++;
}
r[i]='\0';
res=atoi(r);
return res;
}
Many вне форума Ответить с цитированием
Старый 07.06.2009, 18:34   #3
Many
 
Регистрация: 06.06.2009
Сообщений: 6
По умолчанию

Ну я так понял что ни у кого идей нету....
достал рабочий код, но чет он какойт не совсем прямой.. Если невозможно чтото сделать с кодом выше, помогите пожалуйста прописать менюшку в этом коде.. чтобы не сразу все печатал... а по пунктам.. сам пытался - менюшка улетает в бесконечный цикл и все( криворук я(
Код:
#include<stdio.h>
#include<string.h>
typedef struct arr arr;
struct arr{
char string[100];
};
arr arr1[100];
int size=100;
void copy_str(char a[], char b[])
{
int i;
for (i=0; b[i]!='\0'; i++)
{
a[i]=b[i];}
a[i]=b[i];
}

void ShakerSort(arr a[])
{
int i, j, k, L, R;
arr x, res[size];
L=1;
R=size-1;
k=size-1;
do{
for (j=R; j>=L; j--)
{
if (get_key(a[j-1].string)>get_key(a[j].string))
{
copy_str(x.string, a[j-1].string);
copy_str(a[j-1].string, a[j].string);
copy_str(a[j].string, x.string);
k=j;
}
}
L=k+1;
for(j=L; j<=R; j++)
{
if (get_key(a[j-1].string)>get_key(a[j].string))
{
copy_str(x.string, a[j-1].string);
copy_str(a[j-1].string, a[j].string);
copy_str(a[j].string, x.string);
k=j;
}
}
R=k-1;
}
while(L<=R);
putchar('\n');
for(i=0; i<=size-1; i++)
{
printf("%s\n", a[i].string);
}
}
int get_key(char *a)
{
int i=0, res;
char r[10];
while (isdigit(a[i]) && a[i]!='.')
{
r[i]=a[i];
i++;
}
r[i]='\0';
res=atoi(r);
return res;
}

void sort_count(arr a[])
{
int c[size], i, j, k;
arr res[size];
for (i=0; i<size; i++)
{
c[i]=0;
}
for (i=0; i<size; i++)
{
for(j=i+1; j<size; j++)
{
if (get_key(a[i].string)>get_key(a[j].string))
{
c[i]++;
}
else if (get_key(a[i].string)<=get_key(a[j].string))
{
c[j]++;
}
}
}
putchar('\n');
for (i=0; i<size; i++)
{
k=c[i];
copy_str(res[k].string,a[i].string);}
for (i=0; i<=size-1; i++)
{
printf("%s\n", res[i].string);
}
for (i=0; i<=size-1; i++)
{
    copy_str(arr1[i].string, res[i].string);
}
}
void birselsort(arr a[])
{
    int i, j, k;
    arr x;
    for (i=0; i<=size-2; i++)
    {
        copy_str(x.string, a[i].string);
        k=i;
        for(j=i+1; j<=size-1; j++)
        {
            if (get_key(a[j].string)<get_key(x.string))
            {
                k=j;
                copy_str(x.string, a[j].string);
            }
        }
        copy_str(a[k].string, a[i].string);
        copy_str(a[i].string, x.string);
    }
    for(i=0; i<=size-1; i++)
    {
        printf("%s\n", a[i].string);
    }
}
void bubblesort(arr a[])
{
    int i,j,k;
    arr x;
    for (i=1; i<=size-1; i++)
    {
        for (j=size-1; j>=i; j--)
        {
            if (get_key(a[j-1].string)>get_key(a[j].string))
            {
                copy_str(x.string, a[j-1].string);
                copy_str(a[j-1].string, a[j].string);
                copy_str(a[j].string, x.string);
            }
        }
    }
    for(i=0; i<=size-1; i++)
    {
        printf("%s\n", a[i].string, i);
    }
}
int binsort(arr a[], int key, int o)
{
    int L, R, found=0, m;
    L=0;
    R=o-1;
    while (L<R)
{
m=(L+R)/2;
if(get_key(a[m].string)<key)
{
L=m+1;
}
else{
R=m;}
}
 printf("%s\n", a[m].string);
}
main()
{
char *o, *l;
int key1, t;
arr s[size];
int x, i, cnt=0;
scanf("%d", &t);
for (x=0; x<t; x++)
{
scanf("%s", s[x].string);
}
size=x;

arr c[size];
for (i=0; i<=size-1; i++)
{
copy_str(c[i].string, s[i].string);
}
for(x=0; x<=size-1; x++)
{
printf("%s x=%d\n", c[x].string, x);
}
printf("_____________________________________________________\n");
printf("________________________SHAKERSORT___________________\n");
printf("_____________________________________________________\n");
ShakerSort(c);
for (i=0; i<=size-1; i++)
{
copy_str(c[i].string, s[i].string);
}
printf("_____________________________________________________\n");
printf("_________________________bubblesort__________________\n");
printf("_____________________________________________________\n");
bubblesort(c);
for(i=0; i<=size-1; i++)
{
    copy_str(c[i].string, s[i].string);
}
printf("_____________________________________________________\n");
printf("________________________sort_count___________________\n");
printf("_____________________________________________________\n");
sort_count(c);
putchar('\n');
printf("enter the key: ");
scanf("%d", &key1);
binsort(arr1, key1, x);
}
Many вне форума Ответить с цитированием
Старый 12.06.2009, 21:27   #4
Many
 
Регистрация: 06.06.2009
Сообщений: 6
По умолчанию

спасибо за помощь и советы, проблемы решились сами собой
Many вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
программа сортировки Valex Фриланс 3 23.04.2009 22:23
Сортировки в BP 7 ! wArRrrr Помощь студентам 2 07.10.2008 18:56
поиск кратчайшей сортировки, с минимальным кол-вом перестановок sad8c Помощь студентам 9 14.12.2007 10:23
Сортировки в БД. Шурик БД в Delphi 4 15.05.2007 17:45