Операции над элементами списка

Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

ВВЕДЕНИЕ

На сегодняшний день всё большее количество людей сталкивается с компьютером, прогресс неумолимо движет нас вперёд. В данное время это обусловлено большими информационными потоками, и необходимо обеспечивать эту отрасль специалистами информационных технологий.

Одно из наиболее мощных свойств языка программирования – указатели. Указатели – одна из наиболее трудных для освоения возможностей С. Указатели предоставляют программам возможность моделировать передачу по ссылке и создавать и манипулировать динамическими структурами данных, т.е. структурами данных, которые могут нарастать и сокращаться, например, такими как связные списки, очереди, стеки и деревья.

Переменные-указатели содержат в качестве своих значений адреса памяти. Обычно переменная содержит определенное значение. С другой стороны, указатель содержит адрес переменной, которая содержит определенное значение. В этом смысле имя переменной отсылает к значению прямо, а указатель – косвенно. Ссылка на значение посредством указателя называется косвенной адресацией.

Указатель – это переменная, содержащая адрес в памяти компьютера. Если удастся осознать смысл этого простого предложения, то это и все, что необходимо знать об указателях. Указатель – это переменная, которая содержит адрес оперативной памяти.

Чтобы лучше понять указатели, рассмотрим устройство оперативной памяти компьютера. Оперативная память разделена на последовательно пронумерованные ячейки. Каждая переменная размещается в одной или нескольких последовательно расположенных отдельных ячейках памяти, адрес первой из них называется адресом переменной. Каждая ячейка в оперативной памяти занимает 1 байт или 8 бит.

ПОСТАНОВКА ЗАДАЧИ

Задание №1:

Описать функцию, которая меняет местами первый и предпоследний элемент непустой очереди.

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

Запись{inf}: цел – элементы очереди;

Промежуточные данные:

kol: цел – счетчик(номера элементов очереди);

key: сим – клавиша события;

tmp: сим – временный массив символов;

Ограничения:

нет

Задание №2:

Определить количество изолированных вершин неориентированного графа, вывести их список. Сделать выбранную вершину неизолированной.

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

Запись {v1, v2}: цел – 1-я и 2-я вершины одного ребра;

n: цел – общее количество вершин в графе.

Промежуточные данные:

i: цел – счетчик(номера элементов 1-ой очереди);

f: цел – счетчик(проверка на существование висячих вершин);

ch: сим – клавиша события;

s,s1: сим – строки, которые нужны для проверки введенных результатов;

v [10]: сим – показатель степени данной вершины.

Ограничения:

2<=n<=5;

1<=v1<=n;

1<=v2<=n;

v1<>v2.

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

Запись {v1, v2}: цел – граф после удаления одной из висячих вершин.

ОБРАБОТКА СПИСКОВ

Описание структуры списка

Линейный список - это конечная последовательность однотипных элементов (узлов), возможно, с повторениями. Количество элементов в последовательности называется длиной списка, причем длина в процессе работы программы может изменяться. Линейный список F, состоящий из элементов D1,D2,...,Dn, записывают в виде последовательности значений заключенной в угловые скобки F=, или представляют графически (рисунок 2.1).



...



Рисунок 2.1. - Изображение линейного списка

Например, F1=< 2,3,1>,F2=< 7,7,7,2,1,12 >, F3=< >. Длина списков F1, F2, F3 равна соответственно 3,6,0. В реальных языках программирования нет какой-либо структуры данных для представления линейного списка. Поэтому при работе с линейными списками важным является представление используемых в программе линейных списков таким образом, чтобы была обеспечена максимальная эффективность и по времени выполнения программы, и по объему требуемой памяти. Методы хранения линейных списков разделяются на методы последовательного и связанного хранения. При последовательном хранении элементы линейного списка размещаются в массиве d фиксированных размеров, например, 100, и длина списка указывается в переменной l, т.е. в программе необходимо иметь объявления вида

float d [100] ; int l;

Размер массива 100 ограничивает максимальные размеры линейного списка. Список F в массиве d формируется так:

d [0] =7; d [1] =10; l=2;

Полученный список хранится в памяти согласно схеме на рисунке 2.2.

l:	2
d:	7	10			...
	[0]	[1]	[2]	[3]		[98]	[99]
Рисунок 2.2. – Последовательное хранение линейного списка

При связанном хранении в качестве элементов хранения используются структуры, связанные по одной из компонент в цепочку, на начало которой (первую структуру) указывает указатель dl. Структура образующая элемент хранения, должна кроме соответствующего элемента списка содержать и указатель на соседний элемент хранения.

Описание структуры и указателя в этом случае может имееть вид:

typedef struct snd /* структура элемента хранения */

{ float val; /* элемент списка */

struct snd *n; /* указатель на элемент хранения */

} DL;

DL *p; /* указатель текущего элемента */

DL *dl; /* указатель на начало списка */

Для выделения памяти под элементы хранения необходимо пользоваться функцией malloc(sizeof(DL)) или calloc(l,sizeof(DL)). Формирование списка в связанном хранении может осуществляется операторами:

p=malloc(sizeof(DL));

p->val=10; p->n=NULL;

dl=malloc(sizeof(DL));

dl->val=7; dl->n=p;

В последнем элементе хранения (конец списка) указатель на соседний элемент имеет значение NULL. Получаемый список изображен на рисунке 2.3.

Рисунок 2.3. – Связное хранение линейного списка

Операции над графами

При связанном хранении каждая вершина графа представляет собой структуру graf, состоящую из двух элементов: v1,v2 - предназначены для хранения вершин графа, next - для указателя на структуру, содержащую следующую вершину графа. На первые элементы графа указывает указатель head. Для всех операций над графом используется описание:

typedef struct graf

{ int v1,v2;

struct graf* next;

} Graf;

Graf *g, *head, *temp;

Для реализации операций могут использоваться следующие фрагменты программ:

1) определить первый элемент в линейном списке (рисунок 3.1):

printf("v1=");

scanf("%d",&head->v1);

head->next=0;

NULL

head NULL

Рисунок 3.3– Создание первого элемента в графе

2) вставить дополнительный элемент после указанного узла (рисунок 3.2):

printf("v=");

scanf("%d",&g->v1);

g->next=head;

head=g;

…. .

head NULL

Рисунок 3.4– Вставка дополнительного элемента

3) печать всех элементов списка:

printf("Ребра графа: \n");

g=head;

i=0;

while(g! =NULL) {

i++;

printf("РЕБРО%d: v1=%d v2=%d\n", i,g->v1,g->v2);

g=g->next; }

4) удаление ребра:

Удалить ребро означает разрушить связь между вершинами, которые являются для данного графа концевыми.

5) удаление вершины:

if((head->v1==i) ||(head->v2==i))

head=head->next;

else{

temp=head;

g=head->next;

while(g) {

if((g->v1==i) ||(g->v2==i)) {

temp->next=g->next;

free(g);

break; }

temp=g;

g=g->next; }}

Удалить вершину означает разрушить связь со смежными ей вершинами и создать новую связь уже без этой вершины. Схема удаления вершины графа, следующей за узлом, на который указывает р находится на рисунке 3.3.

Рисунок 3.5– Схема удаления вершины графа

ВЫВОДЫ

Желание каждого программиста быть востребованным ставит перед ним определенную цель: идти в одну ногу со временем. С каждым годом это делать становиться все сложнее и сложнее, так как за определенные промежутки времени темпы развития компьютерных технологий постоянно увеличиваются. Задача, которую ставит перед собой программист при разработке нового продукта остается неизменной уже на протяжении долгого времени: получение максимального результата при минимуме затрат времени и средств. Выполнение данной задачи становится возможной только при постоянном самосовершенствовании и самообразовании программиста.

Задание, выданное на летнюю практику, поставило определенные задачи:

1) Научится создавать связные структуры данных, используя указатели;

2) научится создавать и манипулировать динамическими структурами данных, такими как связные списки, очереди и стеки;

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

Решение выданного задания было реализовано с помощью языка программирования С.

С обладает множеством преимуществ. Он является современным языком программирования, включающим в себя управляющие структуры, наличие которых в языке считается желательным с точки зрения теории и практики программирования. Этот язык построен так, что позволяет естественным образом применять планирование сверху – вниз, структурный подход к программированию, модульное проектирование программ. В результате на С получаются более надежные и “прозрачные программы”.

Вот почему именно язык С был выбран автором для реализации данной задачи.

Структуры – это составные типы данных, построенные с использованием других типов. Классы в С++ являются естественным продолжением структуры struct в С. Вот почему детальное изучение этого раздела является таким необходимым для дальнейшего изучения других языков программирования. Так как прежде чем рассматривать специфику разработки классов на С++ нужно более глубоко разобраться со структурами в С.

Приложение А

ЛИСТИНГ ПРОГРАММЫ

Задание №1:

#include<stdio. h>

#include<conio. h>

#include<alloc. h>

#include<string. h>

#include<stdlib. h>

// ------------<Структура>---------

typedef struct sp

{

char inf [100] ;

struct sp *next;

} sp;

sp *g,*head,*teil;

// -----------</Структура>---------

void titl()

{

clrscr();

gotoxy(20,1);

printf("МИHИСТЕРСТВО ОБРАЗОВАHИЯ И HАУКИ УКРАИHЫ");

gotoxy(12,2);

printf("Донецкий государственный институт искусственного интеллекта");

gotoxy(27,8);

printf("Здание на летнюю практику #1");

gotoxy(35,9);

printf("по дисциплине: ");

gotoxy(17,10);

printf("\"Основы программирования и алгоритмические языки. \"");

gotoxy(50,15);

printf("Выполнил: ");

gotoxy(50,16);

printf("студент группы ПО-05г");

gotoxy(50,17);

printf("Пивоваров Артем Генадиевич");

gotoxy(50, 19);

printf("Проверил: ");

gotoxy(50, 20);

printf("асс. Мамбетова Лилия Сергеевна");

gotoxy(2,25);

printf("Для продолжения нажмите любую клавишу... ");

getch();

clrscr();

gotoxy(15,10);

printf("ЗАДАHИЕ: ");

gotoxy(10,12);

printf(" Описать функцию, которая в списке меняет местами");

gotoxy(10,13);

printf("первый и предпоследний элементы. ");

gotoxy(2,25);

printf("Для продолжения нажмите любую клавишу... ");

getch();

}

void program()

{

int kol=1;

char key;

clrscr();

printf("Введите элементы стрруктуры: \n");

head=(sp*) malloc(sizeof(sp));

g=head;

printf("Введите%i-элемент: ",kol);

scanf("%s",&g->inf);

g->next=0;

teil->next=0;

teil=head;

// --------Ввод остальных эл-тов структуры--------------

kol++;

printf("Введите%i-элемент: ",kol);

g=(sp*) malloc(sizeof(sp));

scanf("%s",&g->inf);

g->next=0;

teil->next=g;

teil=teil->next;

{

if (key! =27)

{

kol++;

printf("Введите%i-элемент: ",kol);

g=(sp*) malloc(sizeof(sp));

scanf("%s",&g->inf);

g->next=0;

teil->next=g;

teil=teil->next;

}

printf("Для прекращения ввода нажмите ESC; Для продолжения любую клавишу\n");

key=getch();

}

while (key! =27);

printf("Вы ввели такие элементы: \n");

g=head;

kol=0;

while (g! =0)

{

kol++;

printf("Эллемент%i=%s\n",kol,g->inf);

g=g->next;

}

getch();

}

void zamena()

{

char *tmp;

g=head;

while (g->next! =NULL)

{

if (g->next->next==NULL)

{

strcpy(tmp,g->inf);

strcpy(g->inf,head->inf);

strcpy(head->inf,tmp);

}

g=g->next;

}

// --------------Вывод результата----------------

g=head;

int kol=1;

printf("\nРезультат: ");

while (g! =NULL)

{

printf("\n%i-й элемент равен:%s",kol,g->inf);

kol++;

g=g->next;

}

getch();

}

void cleen()

{

g=head;

while (g! =NULL)

{

free(g);

g=g->next;

}

void main()

{

titl();

program();

zamena();

cleen();

}

Задание №2:

// --------------------------------Библиотеки--------------------------------

#include <stdio. h>

#include <conio. h>

#include <alloc. h>

#include <string. h>

#include <stdlib. h>

// --------------------------------------------------------------------------

// ===============

char *fname [12] ;

FILE *in,*out;

int n, i,j;

int v [10] ;

char s [6],s1 [6] ;

// ===============

// ***********************************

typedef struct graf

{

int v1,v2;

struct graf *next;

} Graf;

Graf *g,*head;

// ***********************************

// --------------------------------Реквизиты---------------------------------

// --------------------------------------------------------------------------

void tit()

{

clrscr();

gotoxy(20,1);

printf("МИHИСТЕРСТВО ОБРАЗОВАHИЯ И HАУКИ УКРАИHЫ");

gotoxy(12,2);

printf("Донецкий государственный институт искусственного интеллекта");

gotoxy(27,8);

printf("Здание на летнюю практику #2");

gotoxy(35,9);

printf("по дисциплине: ");

gotoxy(17,10);

printf("\"Основы программирования и алгоритмические языки. \"");

gotoxy(50,15);

printf("Выполнил: ");

gotoxy(50,16);

printf("студент группы ПО-05г");

gotoxy(50,17);

printf("Пивоваров Артем Генадиевич");

gotoxy(50, 19);

printf("Проверил: ");

gotoxy(50, 20);

printf("асс. Мамбетова Лилия Сергеевна");

gotoxy(2,25);

printf("Для продолжения нажмите любую клавишу... ");

getch();

return;

}

// --------------------------------------------------------------------------

// --------------------------------Задание-----------------------------------

// --------------------------------------------------------------------------

void work_window()

{

clrscr();

gotoxy(35,1);

printf("ЗАДАHИЕ: ");

gotoxy(12,2);

printf(" Определить количество");

gotoxy(12,3);

printf(" изолированных вершин нориентированного графа,");

gotoxy(12,4);

printf("вывести их список. Сделать выбраную вершину неизолированной! \n");

return;

}

// --------------------------------------------------------------------------

// ----------------------Ввод данных с клавиатуры---------------------------

void klava()

{

printf("\nВведите количество вершин: ");

scanf("%s",&s);

n=atoi(s);

itoa(n,s1,10);

if((n<2) ||(n>5))

printf("Ошибка! Выход из диапазона: '2<n<=5'\n");

}

while((n<2) ||(n>5) ||strcmp(s,s1));

// --------------------------------------------------------------------------

for (i=0; i<n; i++)

v [i] =0;

// --------------------------------------------------------------------------

// --------------------Ввод первого элемента списка--------------------------

// --------------------------------------------------------------------------

printf("Введите ребра графа: \n");

head=(Graf *) malloc(sizeof(Graf));

// ======================================================

{

printf("v1=");

scanf("%s",&s);

head->v1=atoi(s);

itoa(head->v1,s1,10);

if (((head->v1) <1) ||((head->v1) >n))

printf("Ошибка! Выход из диапазона: '1<v1<=n'\n");

}

while(((head->v1) <1) ||((head->v1) >n) ||strcmp(s,s1));

// ======================================================

{

printf("v2=");

scanf("%s",&s);

head->v2=atoi(s);

itoa(head->v2,s1,10);

if (((head->v2) <1) ||((head->v2) >n))

printf("Ошибка! Выход из диапазона: '1<v2<=n'\n");

}

while(((head->v2) <1) ||((head->v2) >n) ||strcmp(s,s1));

// ======================================================

head->next=NULL;

// --------------------------------------------------------------------------

// -------------------Ввод остальных элементов списка------------------------

// --------------------------------------------------------------------------

char ch=1;

while(ch! =27)

{

printf("Хотите продолжить ввод вершин? \n");

ch=getch();

if (ch! =27)

{

g=(Graf *) malloc(sizeof(Graf));

// ======================================================

{

printf("v1=");

scanf("%s",&s);

g->v1=atoi(s);

itoa(g->v1,s1,10);

if (((g->v1) <1) ||((g->v1) >n))

printf("Ошибка! Выход из диапазона: '1<v1<=n'\n");

}

while(((g->v1) <1) ||((g->v1) >n) ||strcmp(s,s1));

// ======================================================

{

printf("v2=");

scanf("%s",&s);

g->v2=atoi(s);

itoa(g->v2,s1,10);

if (((g->v2) <1) ||((g->v2) >n))

printf("Ошибка! Выход из диапазона: '1<v2<=n'\n");

}

while(((g->v2) <1) ||((g->v2) >n) ||strcmp(s,s1));

// ======================================================

g->next=head;

head=g;

}

// -------------------------------------------------------------------------

int raschet()

{

printf("Ребра графа: \n");

g=head;

i=0;

while(g! =NULL)

{

i++;

printf("РЕБРО%d: v1=%d v2=%d\n", i,g->v1,g->v2);

g=g->next;

}

// --------------------------------------------------------------------------

// --------------Просмотр графа и поиск изолированых вершин------------------

// --------------------------------------------------------------------------

g=head;

while(g! =NULL)

{

v [g->v1-1] ++;

v [g->v2-1] ++;

g=g->next;

}

int f=0;

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

printf("v [%d] =%d\n", i,v [i-1]);

printf("Изолированные вершины: ");

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

if (v [i-1] ==0)

printf("%d ", i);

else

if (v [i-1] ! =0)

f=f+1;

// ********************************************

if (f==n)

{

printf("\nИзолированных вершин HЕТ! ");

// ----------------------------Сохранение в файл------------------------------

i=0;

if ((out=fopen("1. txt", "w")) == NULL)

{

printf("Ошибка открытия входного файла! \n");

return 1;

}

g=head;

while(g! =NULL)

{

i++;

fprintf(out,"Изолированных вершин HЕТ! ");

fprintf(out,"РЕБРО%d: v1=%d v2=%d\n", i,g->v1,g->v2);

g=g->next;

}

fclose(out);

// --------------------------------------------------------------------------

getch();

exit(1);

}

else

// --------------------------------------------------------------------------

// -----------------Добавление вершины в голову списка-----------------------

// --------------------------------------------------------------------------

printf("\nКакую вершину вы хотите сделать не изолированной? \n");

// ======================================================

{

printf("Укажите вершину: ");

scanf("%s",&s);

i=atoi(s);

itoa(i,s1,10);

if ((i>n) ||(i<1) ||(v [i-1] ! =0))

printf("Ошибка! \n");

}

while((v [i-1] ! =0) ||strcmp(s,s1) ||(i>n) ||(i<1));

// ======================================================

g=(Graf *) malloc(sizeof(Graf));

g->v1=i;

g->v2=head->v1;

g->next=head;

head=g;

printf("Ребра графа после добавления одного ребра: \n");

g=head;

i=0;

while(g! =NULL)

{

i++;

printf("РЕБРО%d: v1=%d v2=%d\n", i,g->v1,g->v2);

g=g->next;

}

// ********************************************

// ----------------------------Сохранение в файл------------------------------

i=0;

if ((out=fopen("1. txt", "w")) == NULL)

{

printf("Ошибка открытия входного файла! \n");

return 1;

}

g=head;

while(g! =NULL)

{

i++;

fprintf(out," РЕБРО%d: v1=%d v2=%d\n", i,g->v1,g->v2);

g=g->next;

}

fclose(out);

}

// --------------------------------------------------------------------------

void main()

{

clrscr();

// ==============

tit();

work_window();

klava();

raschet();

// ==============

getch();

}

ВВЕДЕНИЕ

ПОСТАНОВКА ЗАДАЧИ

Задание №1:

Описать функцию, которая меняет местами первый и предпоследний элемент непустой очереди.

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

Запись{inf}: цел – элементы очереди;

Промежуточные данные:

kol: цел – счетчик(номера элементов очереди);

key: сим – клавиша события;

tmp: сим – временный массив символов;

Ограничения:

нет

Задание №2:

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

Запись {v1, v2}: цел – 1-я и 2-я вершины одного ребра;

n: цел – общее количество вершин в графе.

Промежуточные данные:

i: цел – счетчик(номера элементов 1-ой очереди);

f: цел – счетчик(проверка на существование висячих вершин);

ch: сим – клавиша события;

s,s1: сим – строки, которые нужны для проверки введенных результатов;

v [10]: сим – показатель степени данной вершины.

Ограничения:

2<=n<=5;

1<=v1<=n;

1<=v2<=n;

v1<>v2.

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

Запись {v1, v2}: цел – граф после удаления одной из висячих вершин.

ОБРАБОТКА СПИСКОВ

Описание структуры списка



...



Рисунок 2.1. - Изображение линейного списка

float d [100] ; int l;

Размер массива 100 ограничивает максимальные размеры линейного списка. Список F в массиве d формируется так:

d [0] =7; d [1] =10; l=2;

Полученный список хранится в памяти согласно схеме на рисунке 2.2.

l:	2
d:	7	10			...
	[0]	[1]	[2]	[3]		[98]	[99]
Рисунок 2.2. – Последовательное хранение линейного списка

Описание структуры и указателя в этом случае может имееть вид:

typedef struct snd /* структура элемента хранения */

{ float val; /* элемент списка */

struct snd *n; /* указатель на элемент хранения */

} DL;

DL *p; /* указатель текущего элемента */

DL *dl; /* указатель на начало списка */

p=malloc(sizeof(DL));

p->val=10; p->n=NULL;

dl=malloc(sizeof(DL));

dl->val=7; dl->n=p;

Рисунок 2.3. – Связное хранение линейного списка

Операции над элементами списка

При простом связанном хранении каждый элемент списка представляет собой структуру graf, состоящую из двух элементов: v - предназначен для хранения элемента списка, next - для указателя на структуру, содержащую следующий элемент списка. На первый элемент списка указывает указатель head. Для всех операций над списком используется описание:

typedef struct graf

{ int v;

struct graf* next;

} Graf;

Graf *g, *head, *teil;

Для реализации операций могут использоваться следующие фрагменты программ:

1) определить первый элемент в линейном списке (рисунок 2.4):

printf("v=");

scanf("%d",&head->v);

head->next=0;

teil->next=0;

teil=head;

head: NULL

Рисунок 2.4. – Создание первого элемента в списке

2) вставить дополнительный элемент после указанного узла (рисунок 2.5):

printf("v=");

scanf("%d",&g->v);

teil->next=g;

teil=teil->next;

head: NULL

Рисунок 2.5. – Вставка дополнительного элемента

3) печать всех элементов списка:

g=head;

i=0;

while(g! =NULL)

{

i++;

printf("Эллемент%d:%d\n", i,g->v1);

g=g->next;

}

Дата: 2019-07-31, просмотров: 146.

12 3 Следующая ⇒