Структуры данных (Линейные структуры данных)

1. Используя списковую структуру хранения, напишите программу для обработки последовательности записей, позволяющую осуществлять следующие действия: добавление элемента в упорядоченный список с сохранением упорядоченности, просмотр списка, удаление двух элементов списка, начиная с текущего. Поля записей: тип мебели (мягкая {материал основы, материал обивки, наполнитель} / корпусная {материал, наличие и тип дверец, наличие стеклянных элементов}), наименование, цвет, габаритные размеры.

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <string.h>

 

//*******************           СТРУКТУРЫ         ******************************

 

struct osnova

{

       int type;      

       union

            {struct cor

{char material[15];

char nalichiedoors[3];

char typeofdoors[15];

char nalichiestekla[15];

}corpus;

            struct sof

{char materialosn[15];

char materialobiv[15];

char napolnitel[15];

} soft;

       }tip;

       char name[15];

       char color[15];

       int size;

};

struct list

{

 struct osnova furniture;

 struct list *next;

};

//**********************    функции (прототипы)      ***************************

list* add_middle(list *begin);

struct osnova DataCreator();

void delAll(struct list* begin);

void del_2_from_this_point(struct list* begin);

void seelist(struct list* begin);

void zaderzka(void);

int menu(void);

void seenach(struct list* begin);

void save(struct list* begin);

struct list* read_all(list *begin);

 

//************************         MAIN         ********************************

int main(int argc, char *argv[])

{

int i,n;

    struct list* begin=NULL;

    int exit=1;

    char F;

    while(exit)

    {F=menu();

     switch(F)

    {

       case 1:system ("cls");printf("Add new structure in the middle\n");begin=add_middle(begin);zaderzka();break;

       case 2:system ("cls");printf("All list\n ");seenach(begin);zaderzka();break;

       case 3:system ("cls");printf("Saving...\n");save(begin);break;

       case 4:system ("cls");printf("Reading from file...\n");begin=read_all(begin);zaderzka();break;

       case 5:system ("cls");printf("Delete two elements begining from current\n");del_2_from_this_point(begin);zaderzka();break;

       case 6:system ("cls");printf("Deleting all elements\n");delAll(begin);begin=NULL;break;

   case 7:exit=0;   

   }

}

begin=NULL;

printf ("Good bye");

getch();

return 0;

 

}

//**********************      Функции       ************************************

int menu(void)

{

char s[10];

int c;

printf("\n1) Add new element in the middle\n2) Look up the list\n3) Save lists\n4) Read from file\n5) Delete two elements from this point\n6) Delete all elements\n7) EXIT\n");

do

{  printf("\nWhat do you want to do?(enter the number)\n");

 gets(s);

c=atoi(s);

 system ("cls");

}    while(c<0||c>8);

return c;

}

void seenach(struct list* begin)

{

if(!begin)

printf("There is no any structures");

else

{

seelist(begin);

printf("\n________________\n");

if(begin->next) seenach(begin->next);

}

}

void seelist(struct list* begin)

{

if(begin)

{

 if(!begin->furniture.type)

{

printf("Material :%s\n ",begin->furniture.tip.corpus.material);

printf("Availabilty of doors : %s\n ",begin->furniture.tip.corpus.nalichiedoors);

printf("Availabilty of glass : %s\n ",begin->furniture.tip.corpus.nalichiestekla);

printf("Type of doors :%s\n ",begin->furniture.tip.corpus.typeofdoors);

}

else

{

printf("Material of basis: %s\n ",begin->furniture.tip.soft.materialosn);

printf("Material of upholstery : %s\n ",begin->furniture.tip.soft.materialobiv);

printf("Filler: %s\n ",begin->furniture.tip.soft.napolnitel);

}

printf("Name : %s\n ",begin->furniture.name);

printf("Color : %s\n ",begin->furniture.color);

printf("Size : %d sm^2\n ",begin->furniture.size);

}

 

else

printf("There are no any structures\n");

 

};

void save(struct list* begin)

{

FILE *binfile;

 int number=1;  

 binfile=fopen("Mebel'.dat","wb");

 if(begin==NULL)  printf("Nothing to save \n");

 else{

       struct list *temp;

       temp=begin;

       fseek(binfile,4,SEEK_SET);

     

       fwrite(&temp->furniture,sizeof(struct osnova),1,binfile);

            while(temp->next)

            {

             temp=temp->next;

             fwrite(&temp->furniture,sizeof(struct osnova),1,binfile);

             number++;

            }

       fseek(binfile,0,SEEK_SET);

       fwrite(&number,sizeof(int),1,binfile);

       printf("Saved %d lists\n",number);

      }

 fclose(binfile);

}

list* add_middle(struct list*begin)

{

struct list*temp=begin;

struct list*temp1=begin;

int num,m;

    if(begin==NULL)

     { 

        printf("There are no any structures, so we add in the beginning\n");           

        begin=(list*)malloc(sizeof(struct list)); 

        begin->next=NULL;

        temp=begin;

        temp->furniture=DataCreator();  }

     else

         {

          printf("Vvedite nomer elementa: ");

          scanf("%d", &num);

          for (;num>0;num--)

              {

                            if(temp1->next)

                             {temp1=temp1->next; }

              else

              {             m=-100; }

          }

          if(m!=-100)

          {            temp=(list*)malloc(sizeof(list));

          temp->next=temp1->next;

          temp1->next=temp;

          temp->furniture=DataCreator();

          }

          else    printf("\n Net takogo \n");

          }

 

printf("\n Done ! \n");

return begin;

}

struct osnova DataCreator()

{

struct osnova furniture;

       printf("Corpus or soft (1-soft\\0-corpus) : ");scanf("%d%*c",&furniture.type);

 if(!furniture.type)

   {printf("Enter the material of furniture: ");scanf("%s",&furniture.tip.corpus.material);

            printf("Define the availabilty of doors: ");scanf("%s",&furniture.tip.corpus.nalichiedoors);

            printf("Define is there any glass elements or not: ");scanf("%s",&furniture.tip.corpus.nalichiestekla);

            printf("Enter the type of doors: ");scanf("%s",&furniture.tip.corpus.typeofdoors);}

    else {printf("Enter the material of basis : ");scanf("%s",&furniture.tip.soft.materialosn);

            printf("Enter the material of upholstery : ");scanf("%s",&furniture.tip.soft.materialobiv);

            printf("Enter the type of filler : ");scanf("%s",&furniture.tip.soft.napolnitel);}

            printf("Enter the name of furniture: ");scanf("%s",&furniture.name);

            printf("Enter the color of furniture: ");scanf("%s",&furniture.color);

    printf("Enter the size of furniture (in the sm^2): ");scanf("%d%*c",&furniture.size);

    system ("cls");printf("Element added into the middle.\n");

 

return furniture;

};

 

void zaderzka(void)

{

 printf("\n.......................................................");

 printf("\n Push any button to continue....");

getch();

system ("cls");

 

}

 

void delAll(struct list* begin)

{

 

list*temp=begin;

if(begin)

{

while(temp->next)

{

temp=begin->next;

free(begin);

begin=temp;

}

free(temp);

}

 

printf("List is deleted\n");

}

struct list* read_all(struct list *begin)

{

FILE *binfile;

 struct list *temp=begin;

 int number,i;

 

 binfile=fopen("Mebel'.dat","rb");

 fread(&number,sizeof(int),1,binfile);

 if(temp==NULL)

                   {

                    temp=(list*)malloc(sizeof(struct list));

                    temp->next=NULL;

                    begin=temp;

                   }

 else{

 while(temp->next)temp=temp->next;}//temp=temp->next;

 fread(&temp->furniture,sizeof(struct osnova),1,binfile);

 for(i=1;i<number;i++)

      {

  

       temp->next=(list*)malloc(sizeof(struct list));

       temp=temp->next;

       fread(&temp->furniture,sizeof(struct osnova),1,binfile);

      }

      temp->next=NULL;

 

   

 fclose(binfile);

 printf(" %d from %d was readed\n",number,i);

 return begin;

}

 

void del_2_from_this_point(struct list* begin)

{

struct list*temp=begin;

struct list*temp1=begin;

int num;

 

printf("Vvedite nomer elementa : ");

scanf("%d", &num);

 

for( ;num>0; num--)

{

if(temp1->next)

temp1=temp1->next;

else

{

printf("\n Net takogo \n");

num=-100;

}

}

if(num!=-100)

{

temp1=temp->next->next->next;

free(temp->next->next);

free(temp->next);

 

temp->next=temp1;

printf("\n Done ! \n");

}

}

 

Напишите  программу для моделирования  Т-образного сортировочного узла на железной дороге, позволяющего разделять  на два направления состав, состоящий  из вагонов двух типов (на каждое направление  формируется состав из вагонов одного типа) (структура данных – стек).

С помощью списка

#include <stdio.h>

#include <stdlib.h>

#define DataType int

#define VAGON struct Element

#define STACK struct Element *

#define M 10

struct Element

{

DataType element;

struct Element *next;

};

void Obnulit (STACK *pstack); 

int Pustoi (STACK *pstack);  

int Zapolnen (STACK *pstack);      

int Top (STACK *pstack, DataType *x);  

int Pop (STACK *pstack, DataType *x); 

int Push (DataType x, STACK *pstack);  

 

int main()

{

STACK Napravlenie1,Napravlenie2,Uzel;

int i,A;

Obnulit(&Uzel);

Obnulit(&Napravlenie1);

Obnulit(&Napravlenie2);

printf ("Vvedite tipy vagonov (1 ili 2):\n");

for (i=1;i<=M;i++)

{scanf ("%d",&A);

if (Push(A,&Uzel)) {printf ("\t%d vagon\n",i);}

    else printf ("error\n");}

printf ("Sostavy sobrany\n");

for (i=1;i<=M&&!Pustoi(&Uzel);i++)

{

    Pop(&Uzel,&A);

    if (A==1)

    {

   Push (A, &Napravlenie1); printf ("%d vagon voshel v sostav I\n", i);

    }

    else

    if (A==2)

     {

   Push (A, &Napravlenie2); printf ("%d vagon voshel v sostav II\n", i);

    }

}

 printf ("\n\nSostav I:\n");

while (!Pustoi(&Napravlenie1))

    {Pop(&Napravlenie1,&A);

    printf("Vagon\n");}

printf ("\n\nSostav II:\n");

 

while (!Pustoi(&Napravlenie2))   

    {

    Pop(&Napravlenie2,&A);

    printf("Vagon\n");}

system("pause");

return 0;

}

 

void Obnulit (STACK *pstack)

{

*pstack = NULL;

}

 

int Pustoi(STACK * pstack)

{

if (*pstack==NULL)

return 1;

else

return 0;

}

 

int Zapolnen (STACK *pstack)

{

   if  ((VAGON *) malloc (sizeof (VAGON))==NULL) return 1;

   return 0;

}

 

int Top (STACK *pstack, DataType *x)

{

if (Pustoi (pstack)) return 0;

*x = (*pstack)->element;

    return 1;

}

 

int Pop (STACK *pstack, DataType *x)

{

VAGON *del;

if (Pustoi (pstack)) return 0;

del = *pstack;

*pstack = (*pstack)->next;

*x = del->element;

free (del);

return 1;

}

 

int Push (DataType x, STACK *pstack)

{

VAGON *ins;

ins = (VAGON *) malloc (sizeof (VAGON));

if (ins==NULL) return 0;

ins->element = x;

ins->next = *pstack;

*pstack = ins;

return 1;

}

С помощью массива

#include <stdio.h>

#include <stdlib.h>

#define MAXLENGTH 10

#define DataType int

#define STACK struct Stack

#define M 9

 

struct Stack

{

int top;

DataType elements[MAXLENGTH];

};

 

void Obnulit (STACK *pstack); 

int Pustoi (STACK *pstack);  

int Zapolnen (STACK *pstack);      

int Top (STACK *pstack, DataType *x);  

int Pop (STACK *pstack, DataType *x); 

int Push (DataType x, STACK *pstack);

 

int main()

{

STACK Napravlenie1,Napravlenie2,Uzel;;

int i;

Obnulit(&Uzel);

Obnulit(&Napravlenie1);

Obnulit(&Napravlenie2);

for (i=1; i<M; i++)

Push (i, &Uzel);

while (Pop(&Uzel, &i))

{if (i%2)

{Push(i,&Napravlenie2);

    printf("%d vagon dobavlen vo vtoroi sostav\n", i);}

    else

{Push(i,&Napravlenie1);

    printf("%d vagon dobavlen v pervyi sostav\n", i);}

    }

printf ("\nNazhmi, chtoby vernut' poezda na uzel\n\n");

system ("pause");

printf ("\n");

while (Pop(&Napravlenie2,&i)||Pop(&Napravlenie1,&i))

    {if (i%2)

    {    printf("%d vagon vo vtorom sostave\n", i);}

    else

    {printf("%d vagon v pervom sostave\n", i);}}

printf ("\n");

Obnulit(&Uzel);

Obnulit(&Napravlenie1);

Obnulit(&Napravlenie2);   

system("pause");

return 0;

}

 

void Obnulit (STACK *pstack)

{

pstack->top = -1;

}

 

int Pustoi(STACK *pstack)

{

if (pstack->top < 0)

return 1;

else

return 0;

}

 

int Zapolnen (STACK *pstack)

{

if (pstack->top==MAXLENGTH-1)

    return 1;

else

    return 0;  

}

 

int Top (STACK *pstack, DataType *x)

{

if (Pustoi (pstack)) return 0;

*x = pstack->elements[pstack->top];

return 1;

}

 

int Pop (STACK *pstack, DataType *x)

{

if (Pustoi (pstack)) return 0;

*x = pstack->elements[pstack->top];

pstack->top--;

return 1;

}

 

int Push (int x, STACK *pstack)

{

if (Zapolnen (pstack)) return 0;

pstack->top++;

pstack->elements[pstack->top] = x;

return 1;

}