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

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

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

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

Кафедра ПМт

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

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

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

Группа: ПМ - 92

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

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

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

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

Дана последовательность символов s₁, s₂, s₃…. Известно, что s₁ отличен от точки и что среди s₂..s_n имеется хотя бы  одна точка. Пусть s₁,s₂..s_n – символы, предшествующие первой точке. Получить последовательность s₁, s₃, ...s_n если нечетно, и последовательность s₂, s₄…s_n если четно.  

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

Дано:  <последовательность символов> := ‘s₁’ | ‘s₂’ | … | ‘s_n’;

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

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

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

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

Результат

 если n=2m, то <последовательность символов> := ‘s₁’ | ‘s₃’ | … | ‘s_n’;

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

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. На всех тестах программа работает корректно.