Реализация списков на основе динамических структур.

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

Заголовочный файл 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------------------------------------------");

}