close

Вход

Забыли?

вход по аккаунту

?

4( )

код для вставкиСкачать
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОУ ВПО "НИЖНЕВАРТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ"
ЛАБОРАТОРНАЯ РАБОТА №4
По курсу
"Структуры и алгоритмы обработки данных"
Факультет Информатики и Вычислительной Техники
3 семестр
вариант № 4
Выполнил:
студент гр. 22, дневное отделение
Королёв В.О.
Проверил:
___________________Т.Б. Казиахметов
Нижневартовск, 2013
Записи. Реализация стека, очереди на статических структурах
Задание№1:
1. Cохранить в файле Num.dat несколько целых чисел больших 500 таким образом, чтобы числа записались в сортированном виде. Для этого считать (само число) -500 номером записи в файле. Удалить элементы меньшие или равные 500. Использовать вспомогательный файл. Реализовать меню: Запись в файл. Вывод записей на экран Код программы:
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <iostream>
#include <stdlib.h>
#include <windows.h>
#include <time.h>
int main()
{
setlocale( 0, "rus" );
FILE *f;
srand(time(NULL));
int i,n=100, k=500, x[n+k],y[n+k];
for (i=k;i<=(n+k);i++) x[i]=(rand()%100)+500;
for (i=0;i<=(n+k);i++) y[i]=NULL;
f=fopen("Num.dat","wb");
for (i=k;i<=n+k;i++)
{
for (int j=k;j<=n+k;j++)
{
if (x[i]==j) y[j]=x[i];
}
}
for (i=0;i<=n+k;i++) printf("%d: %d\n",i,y[i]);
int res=fwrite(y, sizeof(int),n,f);
fclose(f);
return(0);
}
1) Участок массива
Задание№2:
Создать хеш-функцию для хранения записей в файл в сортированном виде. Хеш- функцию связать с кодом первого 1 символа Фамилии. Запись состоит из полей :Фамилия, Имя. Для разрешения коллизий использовать вспомогательные файлы.
Код программы:
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <iostream>
#include <stdlib.h>
#include <windows.h>
#include <time.h>
typedef struct journal
{
char fam[64],name[64];
struct journal * next;
}jr;
void show(jr *beg)
{
jr *p=beg;
int i=1;
while (p!=NULL)
{
printf("#%d\n\tФамилия: %s\n\tИмя: %s\n",i, p->fam, p->name);
i++;
p=p->next;
}
}
void sort(jr *list)
{
jr *p=NULL;
char tmp[64];
if (list!=NULL)
{
while(list->next!=NULL)
{
p=list->next;
do
{
if (stricmp(p->fam,list->fam)<0)
{
strcpy(tmp,p->fam);
strcpy(p->fam,list->fam);
strcpy(list->fam,tmp);
}
p=p->next;
}
while(p!=NULL);
list=list->next;
}
}
};
struct fams
{
char s[64];
};
struct names
{
char s[64];
};
int h(int k)
{
return (-k*2) % 100;
};
struct hash_set
{
int num=0, hash;
};
void cleanfiles()
{
FILE *f;
char *s=new char;
for (char j='А';j<='Я';j++)
{
itoa(h(j),s,10);
strcat(s,".dat");
/*fopen(s,"wb");
fclose(f);*/
//printf("%s: Удалено\n",s);
remove(s);
}
};
int main()
{
jr *beg=NULL, *end=NULL, *p, *temp;
setlocale( 0, "rus" );
fams fa[200];
names na[200];
hash_set set[32];
int i=0,q, *mas,flag;
char ch;
srand(time(NULL));
FILE *f;
char *s=new char;
for (char j='А';j<='Я';j++)
{
set[i].hash=h(j);
//printf("%c: %d -> %d\n",j,j,h(j));
//printf("set[%d].num: %d\nset[%d].hash: %d\n\n",i,set[i].num,i,set[i].hash);
i++;
}
f=fopen("Surnames.txt","rt");
int res=fread(s, sizeof(char),1150,f);
int mass[1];
char *ptr;
ptr = strtok(s,"," );
i=0;
while (i<=140)
{
strcpy(fa[i].s, ptr);
//printf("\n%d = %s", i, fa[i].s);
ptr = strtok(NULL, ",");
i++;
}
int nof=i-1;
fclose(f);
free(s);
i=0;
f=fopen("Names.txt","rt");
res=fread(s, sizeof(char),1150,f);
ptr = strtok(s,"," );
while (i<=9)
{
strcpy(na[i].s, ptr);
//printf("\n%d = %s", i, na[i].s);
ptr = strtok(NULL, ",");
i++;
}
int non=i-1;
fclose(f);
free(s);
while (q!=5)
{
system ("cls");
printf("1-Добавление узла\n2-Удаление узла\n3-Вывод списка\n4-Сохранение\n5-Выход\n");
scanf("%d",&q);
switch (q){
case 1:
{
system ("cls");
if (beg==NULL)
{
p=(jr*)malloc(sizeof(jr));
}
else
{
p->next=(jr*)malloc(sizeof(jr));
p=p->next;
};
strcpy(p->fam,fa[rand()%nof].s);
strcpy(p->name,na[rand()%non].s);
if (beg==NULL) beg=p;
p->next=end;
printf("Элемент добавлен"); Sleep(100);
} break;
case 2:
{
system ("cls");
if (beg==NULL)
{
printf("Стек пуст\n");
getch();
break;
}
p=beg; temp=beg;
while (p->next!=end)
{
temp=p;
p=p->next;
}
temp->next=end;
if (p==beg)
{
beg=p->next;
free(p);
}
free(p);
p=beg;
if (beg==NULL) break;
while (p->next!=NULL) p=p->next;
printf("Элемент удален"); Sleep(500);
}; break;
case 3:
{
if (beg==NULL)
{
printf("Стек пуст\n");
getch();
break;
}
sort(beg);
printf("1\n");
show(beg);
printf("2\n");
p=beg; i=1;
/*while (p!=NULL)
{
printf("#%d\n\tФамилия: %s\n\tИмя: %s\n",i, p->fam, p->name);
i++;
p=p->next;
}*/
p=beg;
while (p->next!=NULL) p=p->next;
getch();
}; break;
case 4:
{
if (beg==NULL)
{
printf("Стек пуст\n");
getch();
break;
}
cleanfiles();
for (int j=0;j<=32;j++) set[j].num=0;
mas=(int *)malloc(i*sizeof(int));
p=beg; i=0;
while (p!=NULL)
{
ch=p->fam[0];
//printf("%s -> %d -> %d -> %d\n",p->fam,ch,ch*2,mas[i]);
for (int j=0;j<=32;j++)
{
//printf("symbol: %c (%d)\nset[%d].hash=%d\nset[%d].num=%d\n\n",ch,h(ch),j,set[j].hash,j,set[j].num);
if ((set[j].hash==h(ch))&&(set[j].num==0))
{
set[j].num=1;
mas[i]=h(ch);
//printf("mas[%d]=%d\n",i,mas[i]);
i++;
break;
}
if ((set[j].hash==h(ch))&&(set[j].num==1))
{
itoa(h(ch),s,10);
strcat(s,".dat");
fopen(s,"ab");
mass[0]=h(ch);
res=fwrite(mass, sizeof(int),1,f);
//printf("Записано %d в файл %s\n",mass[0],s);
fclose(f);
break;
}
}
p=p->next;
}
getch();
p=beg;
while (p->next!=NULL) p=p->next;
f=fopen("Baza.dat","wb");
res=fwrite(mas, sizeof(int),i,f);
fclose(f);
free(mas);
}
}}
p=beg;
while (beg!=NULL)
{
beg=p->next;
free(p);
p=beg;
}
return 0;
}
1) Список элементов:
2) Созданные файлы, хранящие хеш-функции
Задание№3:
Создать очередь для хранения названий городов на основе 2 -направленного связного списка. Реализовать операторы : Добавить элемент, удалить элемент, мощность множества, просмотр всех элементов, принадлежность элемента множеству.
Код программы:
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <iostream>
#include <stdlib.h>
#include <windows.h>
#include <time.h>
typedef struct spisok
{
char fam[32];
int num;
struct spisok * next;
struct spisok * prev;
} jr;
struct fams
{
char s[64];
};
int main()
{
setlocale( 0, "rus" );
srand(time(NULL));
jr *beg=NULL, *end=NULL, *p, *temp;
fams fa[5000];
int q,i=0,imax=i,del,r,flag;
FILE *f;
char *s=new char;
f=fopen("Surnames.txt","rt");
int res=fread(s, sizeof(char),1150,f);
char *ptr;
ptr = strtok(s,"," );
while (i<=140)
{
strcpy(fa[i].s, ptr);
//printf("\n%d = %s", i, fa[i].s);
ptr = strtok(NULL, ",");
i++;
}
int nof=i-1;
fclose(f);
free(s);
i=1;
printf("Введите размерность:\n");
scanf("%d",&r);
r++;
while (q!=5)
{
system ("cls");
printf("1-Добавление узла\n2-Удаление узла\n3-Принадлежность к списку\n4-Вывод списка\n5-Выход\n");
scanf("%d",&q);
switch (q)
{
case 1:
{
system ("cls");
if (beg==NULL)
{
p=(jr*)malloc(sizeof(jr));
p->prev=NULL;
strcpy(p->fam,fa[rand()%nof].s);
printf("Элемент добавлен\n"); Sleep(100);
p->num=i;
imax=i;
i++;
beg=p;
p->next=end;
}
else
{
if (imax<r)
{
p->next=(jr*)malloc(sizeof(jr));
p=p->next;
strcpy(p->fam,fa[rand()%nof].s);
printf("Элемент добавлен\n"); Sleep(100);
p->num=i;
imax=i;
i++;
if (beg==NULL) beg=p;
p->next=end;
}
else
{
p=beg;
beg=p->next;
if (beg!=NULL) beg->prev=NULL;
free(p);
p=beg;
i=1;
while (p!=NULL)
{
p->num=i;
i++;
p=p->next;
};
p=beg;
if (beg==NULL) break;
while (p->next!=NULL) p=p->next;
imax--;
p->next=(jr*)malloc(sizeof(jr));
p=p->next;
strcpy(p->fam,fa[rand()%nof].s);
printf("Элемент удален и добавлен\n"); Sleep(500);
p->num=i;
imax=i;
i++;
if (beg==NULL) beg=p;
p->next=end;
}
};
printf("imax=%d\n",imax);
if (p!=beg)
{
temp=beg;
while (temp->next!=p) temp=temp->next;
p->prev=temp;
}
}; break;
case 2:
{
if (beg==NULL)
{
printf("Список пуст\n");
getch();
break;
}
p=beg;
beg=p->next;
if (beg!=NULL) beg->prev=NULL;
free(p);
p=beg;
i=1;
while (p!=NULL)
{
p->num=i;
i++;
p=p->next;
};
p=beg;
if (beg==NULL) break;
while (p->next!=NULL) p=p->next;
imax--;
printf("imax=%d\nУдалено\n",imax); Sleep(500);
}; break;
case 3:
{
if (beg==NULL)
{
printf("Список пуст\n");
getch();
break;
}
printf("Введите номер элемента\n");
scanf("%d",&del);
flag=0;
p=beg;
while (p!=NULL)
{
if (p->num==del)
{
flag=1;
printf("Элемент принадлежит списку\n\n");
printf("Вот он: %s\n\nПредыдущий: %s\nСледующий: %s\n",p->fam,p->prev->fam,p->next->fam);
break;
}
p=p->next;
}
if (flag==0) printf("Элемента нет в списке\n");
p=beg;
while (p->next!=NULL) p=p->next;
getch();
}; break;
case 4:
{
if (beg==NULL)
{
printf("Список пуст\n");
getch();
break;
}
printf("1 - Вывод слева\n2 - Вывод справа\n");
scanf("%d",&q);
switch(q)
{
case 1:
{
p=beg;
while (p!=NULL)
{
printf("#%d\n\tФамилия: %s\n",p->num, p->fam);
p=p->next;
}
p=beg;
while (p->next!=NULL) p=p->next;
getch();
}; break;
case 2:
{
p=beg;
while (p->next!=NULL) p=p->next;
while (p!=NULL)
{
printf("#%d\n\tФамилия: %s\n",p->num, p->fam);
p=p->prev;
}
p=beg;
while (p->next!=NULL) p=p->next;
getch();
}; break;
}
}
}
}
p=beg;
while (beg!=NULL)
{
beg=p->next;
free(p);
p=beg;
}
return 0;
}
1) Добавление элемента в переполненную очередь
Документ
Категория
Рефераты
Просмотров
58
Размер файла
212 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа