Метод решения задачи заданной последовательности символов (Лабораторная работа № 1)

Страницы работы

Содержание работы

Министерство Образования и Науки Российской Федерации

Государственное образовательное учреждение высшего профессионального образования

Новосибирский Государственный Технический Университет

Кафедра ПМт

Лабораторная работа №1

по курсу: «Структуры данных и алгоритмы»

Факультет: ПМИ

Группа: ПМ - 92

Студентка: Райхерт Э.

Преподаватель: Еланцева И.Л.

Новосибирск-2010 год

1.  Условие задачи

Дана последовательность символов s1, s2, s3…. Известно, что s1 отличен от точки и что среди s2..sn имеется хотя бы  одна точка. Пусть s1,s2..sn – символы, предшествующие первой точке. Получить последовательность s1, s3, ...sn если нечетно, и последовательность s2, s4…sn если четно.  

2.  Анализ задачи

Дано:  <последовательность символов> := ‘s1’ | ‘s2’ | … | ‘sn’;

<sn>:= <буква>|<цифра>|<разделитель>

<буква>:=’a’|…|’z’

<цифра>:=’0’|…|’9’

<разделитель>:=’.’

Результат

 если n=2m, то <последовательность символов> := ‘s1’ | ‘s3’ | … | ‘sn’;

 если n=2m+1, тогда <последовательность символов> := ‘s2’ | ‘s4’ | … | ‘sn’;

3.  Метод решения

Мы можем выделить следующую подзадачу: удаление элементов через один элемент

      k=ph

           повторять

               t=k->next;

               k->next=k->next->next;

               k=k->next;

              delete t;

      пока

k->next!=NULL

4.  Структуры данных

Для хранения данных используется линейный, однонаправленный, нециклический список с заглавным звеном.

Этот список определяет структура list с ячейками хранения символа (elem), ссылки на следующую ячейку (next);

ph– указатель на первое звено.

nextelem

                                                              …

 ph

5.  Алгоритм программы


6.  Текстпрограммы:

#include<conio.h>

#include<stdio.h>

struct list{list*next;char elem;}*ph;list*p,*pr,*c,*k,*t;

void udal_cherod(list*ph){k=ph;

      while(k->next!=NULL){t=k->next;k->next=k->next->next;k=k->next;delete t;}

}

void main()

   {

      int i=0;char s;

FILE*fp;

fp=fopen("stroka.txt","r");

if(fp==NULL){printf("error!");}

      else

      {

      ph=new list;

      ph->next=NULL;

      p=ph;

      while(fscanf(fp,"%c",&s)!=EOF)

      {p->next=new list;p=p->next;

      p->elem=s;

      }

      p->next=NULL;

    fclose(fp);

            for(p=ph->next,pr=NULL;p->elem!='.';pr=p,p=p->next,i++);

                  c=pr;k=c;

                  while(k->next!=NULL){c=k->next;k->next=k->next->next;delete c;}

                  if(i%2==0){udal_cherod(ph);}else {udal_cherod(ph->next);}

            FILE*l;

            l=fopen("res.txt","w+");

            if(l==NULL){printf("error!");}else

            {k=ph->next;while(k!=NULL){fprintf(l,"%c",k->elem);k=k->next;}

            fclose(l);

            }

} printf("ischodnij fiele stroka.txt\nresultat file res.txt");

            getch();

}

7. Тесты на работоспособность программы:

Входные данные

Результат

1.

1234567.901,

1357

2.

a1b2c3./a/b

123

3.

a.

a

4.

abc.dk/.o

ac

5.

/yilp/.p

yl/

8. На всех тестах программа работает корректно.

Похожие материалы

Информация о работе