Линейный односвязный список

Если тип определен следующим образом

typedef struct List_Item *List;

struct List_Item

{ int key;

List next;

};

то получается следующая структура данных

Такая структура называется линейным односвязным списком.

Определим некоторые операции с линейными списками.

Файл list.h

#ifndef __LIST_H

#define __LIST_H

typedef struct List_Item *List;

struct List_Item

{ int key;

List next;

};

void PrintList(List); //Печать списка

List InsertBegin(List, int); //Вставка элемента в начало списка

List FindItem(List, int); //Поиск элемента по ключу

void InsertAfter(List, int); //Вставка элемента после заданного

void DeleteAfter(List); //Удаление элемента после заданного

void FreeList(List); //Освобождение памяти

#endif

Реализация (list.cpp)

#include "list.h"

#include "stdio.h"

#include "stdlib.h"

void PrintList(List p)

{

while (p)

{

printf("%d ", p->key);

p=p->next;

}

printf("\n");

};

List InsertBegin(List p, int x)

{

//List q=(List)malloc(sizeof(List_Item));

List q=new List_Item;

q->key=x;

q->next=p;

return q;

};

List FindItem(List p, int x)

{

while (p && p->key!=x)

p=p->next;

return p;

};

void InsertAfter(List p, int x)

{

//List q=(List)malloc(sizeof(List_Item));

List q=new List_Item;

q->key=x;

q->next=p->next;

p->next=q;

};

void DeleteAfter(List p)

{

List q=p->next;

p->next=q->next;

delete q; //free(q);

};

void FreeList(List p)

{

List q;

while (p)

{

q=p;

p=p->next;

delete q; //free(q);

}

};

Тестирование (main.cpp)

#include "list.h"

#include <stddef.h>

#include <stdio.h>

int main(int argc, char* argv[])

{

List p=NULL;

for (int i=1;i<=5;i++)

p=InsertBegin(p,i);

PrintList(p);

List q=FindItem(p, 3);

InsertAfter(q,10);

PrintList(p);

q=FindItem(p, 2);

DeleteAfter(q);

PrintList(p);

FreeList(p);

getchar();

return 0;

}

Результат работы программы:

5 4 3 2 1

5 4 3 10 2 1

5 4 3 10 2