Написание подпрограммы поиска заданного элемента в списке и подсчета количества вхождений четных цифр в каждую строку текста (Лабораторная работа № 1)

                            МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

                            НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ

                                                         УНИВЕРСИТЕТ

                                  КАФЕДРА ПРИКЛАДНЙ МАТЕМАТИКИ

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

По дисциплине

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

 СТУДЕНТ: Вознюк А.В.

ГРУППА ПМ-95

ФАКУЛЬТЕТ: ПРИКЛАДНАЯ МАТЕМАТИКА И ИНФОРМАТИКА

ПРЕПОДАВАТЕЛЬ: Еланцева И. Л

1)  Условие задачи: Задан текст, состоящий из строк разделенных пробелом и оканчивающийся точкой.

Написать подпрограмму поиска заданного элемента в списке. Используя эту подпрограмму: подсчитать количество  вхождений четных цифр в каждую строку текста.

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

1.  Дано: L={l_i | l _i Є{‘0’, ‘1’, … , ‘9’}υ{‘a’, ‘b’, … ,’z’}υ{‘A’, ‘B’, … , ‘Z’}υ{‘  ‘}υ{‘.’},  iЄN

2.  Результат К={k _j | k _j Є{0, 1, 2,…,9} jЄN

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

В задаче можно выделить одну подзадачу: поиск и подсчет четных цифр в каждой строке:

j=1

K_j=0

i=1,

Повторять

Если  l_i≥'0' и l_i≤’9’ и (l_i/2)=0, то к_j=к_j+1

Если l_i='  ' или l_i='.' , то j=j+1, к_j=0

i=i+1,

Пока l _i≠’.’

3)  Структура

·  Внешнее представление входных данных:

В  файле Laba1.txt входные данные представлены последовательностью строк разделенных пробелом в конце точка.

·  Внутреннее представление входных данных:

Последовательность строк представлена линейным однонаправленным списком без заглавного звена.

Элемент списка представлен структурой: list1{char b; list1*next}

·  Внешнее представление выходных данных:

Выходные  данные  представлены  последовательностью целых чисел

·  Внутреннее представление выходных данных

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

struct list2

{

list2 *next;

int k;

};

4)  Алгоритм:

                              

 

                                                                                             -

 

                                                                    +

 

-

 

                                                                                                                                   +

 

                                                                                                                                           

 

                                                                                                       -

                                                                          +

 

                                                                                                           -

 

                                                               +

                       -

 

                                                              +

 

                                                        +

 

                                                                                                                                               +

                                                                                                                    -

                                                                                                                                                 +

                                                                                                                     -

5)  Текст программы:

#include <stdio.h>

struct list1

{

list1 *next;

char b;

};

struct list2

{

list2 *next;

int k;

};

void Chet(list1 *n, list2 **m)

{

 int i=0;

 list1*r;

 for(r=n; r!=NULL; r=r->next)

              {

                            if (r->b>='0' && r->b<='9' && r->b%2==0) i=i+1;

                            if(r->b==' '||r->b=='.')

              {

                                          list2 *g;

                                          g=new list2;

                                          g->k=i;

                                          g->next=NULL;

                                          if(*m==NULL) *m=g;

                                          else

                                          {

                                                         list2*f;

                                                         for(f=*m; f->next!=NULL; f=f->next);

                                                         f->next=g;

                                          }

            i = 0 ;

                            }

              }

}

#include<conio.h>

void main()

{

    clrscr();

    char a;

    list1 *q;

    list2 *F;

    F=NULL;

    FILE *fp;

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

    q = NULL;

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

    {

     list1 *g;

               g=new list1;

               g->b=a;

               g->next=NULL;

     if(q==NULL) q=g;

                                          else

                                          {

                                                         list1 *f;

                                                         for(f=q; f->next!=NULL; f=f->next);

                                                         f->next=g;

                                          }

    }

              Chet(q, &F);

              list2 *B;

    int p = 1 ;

              for(p=1,B=F; B!=NULL;p++,B=B->next)

              {

                            printf("v slove(%d) - %d\n",p,B->k);

              }

              fclose(fp);

    getch();

}

6)  Тесты:

 

7)  Вывод: По результатам данных тестов программа работает правильно.