Data Structure - List (C)-蒲公英云

Data Structure - List (C)

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击http://www.captainbed.net

/*
 * Fatal.h - by FreeMan
 */
#include <stdio.h>
#include <stdlib.h>
#define Error( Str )        FatalError( Str )
#define FatalError( Str )   fprintf( stderr, "%s\n", Str ), exit( 1 )
/*
 * List.h - by FreeMan
 */
typedef int ElementType;
#ifndef _List_H_
#define _List_H_
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
List MakeListEmpty(List L);
int IsListEmpty(List L);
int IsListLast(Position P, List L);
Position FindInList(ElementType X, List L);
void DeleteInList(ElementType X, List L);
Position FindPreviousInList(ElementType X, List L);
void InsertInList(ElementType X, List L, Position P);
void DeleteList(List L);
Position HeaderOfList(List L);
Position FirstOfList(List L);
Position AdvanceInList(Position P);
ElementType RetrieveInList(Position P);
#endif
/*
 * List.c - by FreeMan
 */
#include "List.h"
#include "..\Fatal.h"
#include <stdlib.h>
struct Node
{
    ElementType Element;
    Position    Next;
};
List MakeListEmpty(List L)
{
    if (L != NULL)
    {
        DeleteList(L);
    }
    L = malloc(sizeof(struct Node));
    if (L == NULL)
    {
        FatalError("Out of memory!");
    }
    L->Next = NULL;
    return L;
}
int IsListEmpty(List L)
{
    return L->Next == NULL;
}
int IsListLast(Position P, List L)
{
    return P->Next == NULL;
}
// Return Position of X in L; NULL if not found.
Position FindInList(ElementType X, List L)
{
    Position P;
    P = L->Next;
    while (P != NULL && P->Element != X)
    {
        P = P->Next;
    }
    return P;
}
void DeleteInList(ElementType X, List L)
{
    Position P, TmpCell;
    P = FindPreviousInList(X, L);
    if (!IsListLast(P, L))
    {
        TmpCell = P->Next;
        P->Next = TmpCell->Next;
        free(TmpCell);
    }
}
Position FindPreviousInList(ElementType X, List L)
{
    Position P;
    P = L;
    while (P->Next != NULL && P->Next->Element != X)
    {
        P = P->Next;
    }
    return P;
}
// Insert (after legal position P).
void InsertInList(ElementType X, List L, Position P)
{
    Position TmpCell;
    TmpCell = malloc(sizeof(struct Node));
    if (TmpCell == NULL)
    {
        FatalError("Out of memory!");
    }
    TmpCell->Element = X;
    TmpCell->Next = P->Next;
    P->Next = TmpCell;
}
void DeleteList(List L)
{
    Position P, Tmp;
    P = L->Next;
    L->Next = NULL;
    while (P != NULL)
    {
        Tmp = P->Next;
        free(P);
        P = Tmp;
    }
}
Position HeaderOfList(List L)
{
    return L;
}
Position FirstOfList(List L)
{
    return L->Next;
}
Position AdvanceInList(Position P)
{
    return P->Next;
}
ElementType RetrieveInList(Position P)
{
    return P->Element;
}
/*
 * ListTest.c - by FreeMan
 */
#include "List.h"
#include <stdio.h>
void PrintList(const List L)
{
    Position P = HeaderOfList(L);
    if (IsListEmpty(L))
    {
        printf("Empty list\n");
    }
    else
    {
        do
        {
            P = AdvanceInList(P);
            printf("%d ", RetrieveInList(P));
        } while (!IsListLast(P, L));
        printf("\n");
    }
}
main()
{
    List L;
    Position P;
    int i;
    L = MakeListEmpty(NULL);
    P = HeaderOfList(L);
    PrintList(L);
    for (i = 0; i < 10; i++)
    {
        InsertInList(i, L, P);
        PrintList(L);
        P = AdvanceInList(P);
    }
    for (i = 0; i < 10; i += 2)
    {
        DeleteInList(i, L);
    }
    printf("Finished deletions\n");
    for (i = 0; i < 10; i++)
    {
        if ((i % 2 == 0) == (FindInList(i, L) != NULL))
        {
            printf("Find fails\n");
        }
    }
    PrintList(L);
    DeleteList(L);
    return 0;
}
// Output:
/*
Empty list
0
0 1
0 1 2
0 1 2 3
0 1 2 3 4
0 1 2 3 4 5
0 1 2 3 4 5 6
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8 9
Finished deletions
1 3 5 7 9
*/