- •Часть 2
- •Общие сведения Сведения об эумк
- •Методические рекомендации по изучению дисциплины
- •Рабочая учебная программа
- •Учреждение образования
- •«Белорусский государственный университет
- •Информатики и радиоэлектроники»
- •Протокол согласования учебной программы по изучаемой учебной дисциплине с другими дисциплинами специальности
- •Задачи изучения дисциплины. В результате изучения дисциплины «Основы информатики и программирования» студенты должны:
- •Содержание дисциплины
- •1. Название тем лекционных занятий, их содержание, объем в часах
- •2. Перечень тем лабораторных занятий,
- •Теоретический раздел Лекции
- •Int I; // I - счетчик членов ряда
- •X, // аргумент функции
- •Int newton(double (*f)(double), // Функция
- •1. Типы данных – простые и составные.
- •2. Агрегирование данных.
- •3. Генерация «псевдослучайных» данных.
- •4. Абстрактные типы данных.
- •5. Статические и динамические структуры данных.
- •6. Последовательности (динамические массивы).
- •7. Реализация операций над последовательностями.
- •Int nMaxSize; // Размер выделенной области памяти
- •Int nSize; // Количество элементов последовательности
- •1. Понятие стека. Операции над стеком.
- •2. Программная реализация стека на основе статического массива.
- •3. Использование стека при организации связи функций в языке Си и в операционной системе.
- •4. Понятие очереди. Операции над очередями. Кольцевая очередь. Деки.
- •5. Программная реализация очереди на основе статического массива.
- •1. Структура данных «список».
- •4. Реализация списков на основе динамических структур.
- •5. Двусвязный список и его программная реализация.
- •6. Кольцевые списки
- •7. Многосвязные (слоеные) списки
- •Фаза 1 сортировки: построение пирамиды
- •Фаза 2: собственно сортировка
- •Разделение массива
- •Общий алгоритм
- •Практический раздел
- •Контрольные работы
- •Контрольная работа №1
- •Указания по выбору варианта
- •Варианты контрольных заданий
- •Теоретическая часть (вопросы)
- •Практическая часть Контрольное задание №1. Организация распределения продукции в логистической системе
- •Исходные данные к контрольному заданию №1
4. Реализация списков на основе динамических структур.
Рассмотрим программу, реализующую односвязный линейный список. В качестве данных, сохраняемых в элементах списка, будем использовать некоторое имя и деньги.
Заголовочный файл list1.hвыглядит так:
#ifndef LISTS1_
#define LISTS1_
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <conio.h>
//////////////////////////////////////////////////////
// Данные (информация), хранящиеся в элементе списка
//////////////////////////////////////////////////////
typedef struct
{
char name[20];
double money;
} ELEMENT, *pELEMENT;
//////////////////////////////////////////////////////
// Элемент списка
//////////////////////////////////////////////////////
typedef struct
{
pELEMENT inf; // Указатель на информацию
void *next; // Указатель на следующий блок
} LIST1, *pLIST1;
//////////////////////////////////////////////////////
// Добавить в конец списка новый элемент
pLIST1 AddToLists1(pELEMENT pInf);
// Добавить в список после заданного элемента
pLIST1 AddToLists1Elem(char* pName, pELEMENT pInfNew);
// Удалить из списка заданный элемент (первый, если pName==NULL)
pLIST1 DelFromLists1(char* pName);
// Найти в списке заданный элемент
pLIST1 FindInLists1(char* pName);
// Вывести содержание списка
void PrintLists1(void);
//////////////////////////////////////////////////////
extern pLIST1 pHead;
#endif //LISTS1_
Текст программы, реализующей описанный интерфейс, может выглядеть так: (lists1.cpp):
#include "lists1.h"
//////////////////////////////////////////////////////////////////////
// Добавить в конец списка новый элемент
//////////////////////////////////////////////////////////////////////
pLIST1 AddToLists1(pELEMENT pInf)
{
pLIST1 pNew,pCur;
pELEMENT pInfNew;
pNew = (pLIST1)malloc(sizeof(LIST1));
pInfNew = (pELEMENT)malloc(sizeof(ELEMENT));
strcpy(pInfNew->name, pInf->name);
pInfNew->money = pInf->money;
pNew->inf = pInfNew;
pNew->next = NULL;
if (pHead==NULL) pHead = pNew;
else
{
pCur = pHead;
while (pCur->next!=NULL) pCur = (pLIST1)pCur->next;
pCur->next = pNew;
}
return pNew;
}
////////////////////////////////////////////////////////////////
Добавить в список после заданного элемента или в конец,если такого нет
////////////////////////////////////////////////////////////////
pLIST1 AddToLists1Elem(char* pName, pELEMENT pIN)
{
pLIST1 pNew,pCur;
pELEMENT pInfNew, pW;
pNew = (pLIST1)malloc(sizeof(LIST1));
pInfNew = (pELEMENT)malloc(sizeof(ELEMENT));
strcpy(pInfNew->name, pIN->name);
pInfNew->money = pIN->money;
pNew->inf = pInfNew;
pNew->next = NULL;
if (pHead==NULL) pHead = pNew;
else
{
pCur = pHead;
while (pCur->next!=NULL)
{
pW = pCur->inf;
if (!strcmp(pW->name, pName))
{
pNew->next = pCur->next; break;
}
pCur = (pLIST1)pCur->next;
}
pCur->next = pNew;
}
return pNew;
}
////////////////////////////////////////////////////////////////
// Удалить из списка заданный элемент (первый, если pName==NULL)
////////////////////////////////////////////////////////////////
pLIST1 DelFromLists1(char* pName)
{
pLIST1 pCur, pPrev=NULL;
pELEMENT pW;
if (pHead==NULL) return NULL;
pCur = pHead;
if (pName==NULL) // Удаление из головы списка
{
pPrev = (pLIST1)pCur->next;
free(pCur->inf); free(pCur);
pHead = pPrev;
return pPrev;
}
do
{
pW = pCur->inf;
if (!strcmp(pW->name, pName))
{
free(pW);
if (pPrev==NULL)
{
free(pHead);
pHead=NULL;
}
else
{
pPrev->next = pCur->next;
free(pCur);
}
return pPrev;
}
else
pPrev = pCur;
pCur = (pLIST1)pCur->next;
} while (pCur->next!=NULL);
pW = pCur->inf;
if (!strcmp(pW->name, pName))
{
free(pW);
pPrev->next=NULL;
free(pCur);
return pPrev;
}
else
return NULL;
}
////////////////////////////////////////////////////////////////
// Найти в списке заданный элемент
////////////////////////////////////////////////////////////////
pLIST1 FindInLists1(char* pName)
{
pLIST1 pCur;
pELEMENT pW;
if (pHead==NULL) return NULL;
pCur = pHead;
do
{
pW = pCur->inf;
if (!strcmp(pW->name, pName)) return pCur;
pCur = (pLIST1)pCur->next;
} while (pCur->next!=NULL);
pW = pCur->inf;
if (!strcmp(pW->name, pName)) return pCur;
return NULL;
}
////////////////////////////////////////////////////////////////
// Вывести содержание списка
////////////////////////////////////////////////////////////////
void PrintLists1()
{
pLIST1 pCur;
pELEMENT pW;
if (pHead==NULL) return;
pCur = pHead;
printf("\n---------- Content of the list -----------");
while (pCur->next!=NULL)
{
pW = pCur->inf;
printf("\n%-20s %.2lf", pW->name, pW->money);
pCur = (pLIST1)pCur->next;
}
pW = pCur->inf;
printf("\n%-20s %.2lf", pW->name, pW->money);
printf("\n------------------------------------------");
}