Написание подпрограммы поиска вхождения заданного символа в текст (Лабораторная работа № 1)

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

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

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

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

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

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

Студент               Трубников А.И.

Группа                   ПМ-93

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

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

Новосибирск 2010

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

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

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

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

1.  Дано:

a₁ , a_2,   …, a_n .  nєN

a_i={s1, s2 ,s3, … ,sk} k є N

s_i={‘a’..’z’,’A’..’Z’,’0’..’9’,’.’} i=1,k

sm (Искомый символ)  a_i.

2.  Результат : d1–p1,d2–p2 ,…, dn-pn   d,p  є N или сообщение об ошибке.

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

В задаче можно выделить одну подзадачу, которая находит все  вхождения заданного символа в текст:

А)Начнем рассматримать текст с первого элемента следовательно счетчиком номера слова присвоим 1 номеру порядка в слове присвоим значение 1 и запомним начало списка :

i=1, j=1, n=1

Повторять

Если s_ij!=’ ‘ , то если s_ij==sm , то dn=i, pn=j,n=n+1, иначе j=j+1,

иначе i=i+1, j=0,

Пока

S_ij!=’.’.

3.  Структура

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

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

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

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

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

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

Выходные  данные  представлены последовательностью пар чисел, являющихся вхождениями символа в текст.

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

Полученная последовательность представлена линейным однонаправленным ациклическим списком с заглавным  звеном. Элемент списка представлен структурой:  struct listok{int slovo; int nom; listok*next;};

4.  Алгоритм решения

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

#include <stdio.h>

#include <conio.h>

#define MAX 100

struct list{char info; list*next;};

struct listok{int slovo; int nom; listok*next;};

int poisk(list*t, char sm, listok*w);

int main()

{char ch;

list *d; list *c; list *begin;listok *now;

FILE* fp;

fp=fopen("I://AND21.txt","r");

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

else{

c=new list;

begin=c;

 while(!feof(fp))

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

if (ch!='.') {d=new list; (*d).info=ch; (*c).next=d; c=d;}

else {d=new list; (*d).info=ch; (*c).next=d; c=d;(*c).next=NULL; c->info='.';

 }; };  };

fclose(fp);

printf("Enter iscomogo simvola:");

scanf("%c",&ch);

now=new listok;

if (c!=begin) poisk(begin,ch,now);

now=now->next;

FILE* in;

in=fopen("I://AND21.txt","a");

while (now!=NULL)

{ fprintf(in,"%d - %d\n",now->slovo,now->nom); now=now->next;}

fclose(in);

getch();

return 0;}

int poisk(list*t, char sm, listok*w)

{int i,j; listok*begin;

i=1;j=0; begin=w;

while(t->info!='.')

{

if (t->info==' ') {i=i+1; j=0;}

else {if (t->info==sm) {w->next=new listok; w->next->slovo=i; w->next->nom=j; w=w->next; }}

t=t->next;

j=j+1;

}

w->next=NULL;

return 0;};

6.  Тесты

Входные данные	Выходные данные	Случаи
asa das dsa qq wezsd. Поиск “s” в тексте.	1-2, 2-3, 3-2, 5-4.	Общий случай. Программа работает верно.
ddd  dddddd. Поиск “d” в тексте.	1 – 1, 1 - 2 ,1 – 3, 2 – 1, 2 – 2, 3 – 1, 3 – 2, 3 – 3, 3 – 4.	Случай, когда в тексте только одни одинаковые буквы.  Программа работает верно.
I lovebasket. Поиск “z” в тексте.	-	Случай, когда в тексте нет искомой буквы.  Программа работает верно.
. Поиск “a”  в тексте.	-	Случай, когда в тексте нет  других символов, кроме «.».

7.  Вывод

Программа работает верно при всех проведенных тестах.