链表、树、图相关操作汇总

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

/***********************************      链表相关操作    ***********************/
typedef struct NODE
{
    int data;
    struct NODE* next;
}NODE;

NODE* Create()
{
    NODE* head;
    head = (NODE*)malloc(sizeof(NODE));
    if (NULL == head)
        return NULL;
    head->next = NULL;

    return head;
}

void Insert(NODE**head, int dat)
{
    if (NULL == head)
        return;

    NODE* HeadList = *head;
    NODE* Next = HeadList->next;
    while (NULL != Next)
    {
        HeadList = Next;
        Next = HeadList->next;
    }

    NODE* InsertNode;
    InsertNode = (NODE*)malloc(sizeof(NODE));
    if (NULL == InsertNode)
        return;

    InsertNode->data = dat;
    InsertNode->next = Next;
    HeadList->next = InsertNode;

    return;
}

void Visit(NODE*head)
{
    if (NULL == head)
        return;

    NODE* Head = head->next;
    while (Head != NULL)
    {
        printf("%d\n",Head->data);
        Head = Head->next;
    }
    return;
}

void Delete(NODE**head, int dat)
{
    if (NULL == head)
        return;
    NODE* Head = *head;
    NODE* Next = Head->next;

    NODE* tmp;
    while (Next != NULL)
    {
        if (Next->data == dat)
        {
            tmp = Next->next;
            Head->next = tmp;
            free(Next);
            Next = tmp;
        }
        else
        {
            Head = Next;
            Next = Head->next;
        }
    }
    return;
}

/************************************** 树相关操作 ********************/
typedef struct TREE
{
    char data;
    struct TREE *left;
    struct TREE *right;
}TREE;

static int index=0;
char str[100] = "ABDH#K###E##CFI###G#J##";

TREE* CreateHead()
{
    TREE* topHead;
    topHead = (TREE*)malloc(sizeof(TREE));
    if (NULL == topHead)
        return NULL;
    topHead->data = str[index++];
    topHead->left = NULL;
    topHead->right = NULL;

    return topHead;
}

void CreateTree(TREE** tree)
{
    char tmp = str[index++];
    if ('\0' == tmp)
        return ;
    if ('#' == tmp)
        *tree = NULL;
    else
    {
        *tree = (TREE*)malloc(sizeof(TREE));
        if (NULL == *tree)
        {
            return;
        }
        (*tree)->data = tmp;

        CreateTree(&(*tree)->left);
        CreateTree(&(*tree)->right);
    }
}

void PreVisit(TREE* tree)
{
    if (NULL != tree)
    {
        printf("%c\n",tree->data);
        PreVisit(tree->left);
        PreVisit(tree->right);
    }
}
void MidVisit(TREE* tree)
{
    if (NULL != tree)
    {
        PreVisit(tree->left);
        printf("%c\n",tree->data);
        PreVisit(tree->right);
    }
}
void EndVisit(TREE* tree)
{
    if (NULL != tree)
    {
        PreVisit(tree->left);
        PreVisit(tree->right);
        printf("%c\n",tree->data);
    }
}

int Depth(TREE* tree)
{
    if (NULL == tree)
        return 0;

    int DepLeft=0,DepRight=0;
    if (tree->left)
        DepLeft = Depth(tree->left);
    else
        DepLeft = 0;

    if (tree->right)
        DepRight = Depth(tree->right);
    else
        DepRight = 0;

    return DepLeft>DepRight? DepLeft+1:DepRight+1;
}

/**************************************** 图相关操作 **********************/
/*
#define N 10
typedef struct Graph
{
    int Mutex[N][N];
    int points;
    int edges;
}Graph;

void CreateGraph(Graph* grap)
{
    printf("pls putin the points and edges!\n");
    scanf("%d %d",&grap->points,&grap->edges);

    int i,j;
    for (i=0;i<grap->points;i++)
    {
        for (j=0;j<grap->points;j++)
        {
            grap->Mutex[i][j]=0;
        }
    }
    int row = 0,col = 0;
    for(i=0;i<grap->edges;i++)
    {
        printf("pls putin the %d edges : start and end !\n",i);
        scanf("%d %d",&row,&col);
        printf("edge weight :\n");
        scanf("%d",&grap->Mutex[row][col]);
        grap->Mutex[col][row] = grap->Mutex[row][col];
    }
}

void VisitGrap(Graph grap)
{
    int begin=0,end=0;
    printf("putin the point to check:begin end!\n");
    scanf("%d %d",&begin,&end);
    printf("Mutex[%d][%d]=%d\n",begin,end,grap.Mutex[begin][end]);
}
*/

//邻接链表方法
#define MAX 100
typedef enum
{
    NoVisit=0,
    HasVisit=1
}VisitStat;

typedef enum
{
    NoExisit = 0,
    IsExisit = 1
}ExistStat;

typedef enum
{
    NoEmpty = 0,
    IsEmpty = 1
}EmptyStat;

typedef struct ListNode
{
    int pointNo;
    int wight;
    struct ListNode* next;
}ListNode;

typedef struct GNODE
{
    int pointNo;
    ListNode* listHead;
}GNODE,GPoint[MAX];

typedef struct Graph
{
    GPoint  GListNode;
    int points;
    int edges;
}GRAPH;

void CreateG(GRAPH* grap)
{
    scanf("%d %d",&grap->points,&grap->edges);

    int i;
    ListNode* tmpHead;

    for (i=0; i<grap->points;i++)
    {
        grap->GListNode[i].pointNo = i;
        tmpHead = (ListNode*)malloc(sizeof(ListNode));
        if (NULL != tmpHead)
        {
            tmpHead->next = NULL;
            grap->GListNode[i].listHead = tmpHead;
        }
    }

    int start=0,end=0,weight=0;
    ListNode* InsertNode;
    ListNode* Head;
    ListNode* Next;
    for (i=0;i<grap->edges;i++)
    {
        scanf("%d %d %d",&start,&end,&weight);

        InsertNode = (ListNode*)malloc(sizeof(ListNode));
        if (NULL == InsertNode)
            return ;
        InsertNode->pointNo = end;
        InsertNode->wight = weight;
        Head = grap->GListNode[start].listHead;
        Next = Head->next;
        while (Next != NULL)
        {
            Head = Next;
            Next = Head->next;
        }
        InsertNode->next = Next;
        Head->next = InsertNode;


        InsertNode = (ListNode*)malloc(sizeof(ListNode));
        if (NULL == InsertNode)
            return ;
        InsertNode->pointNo = start;
        InsertNode->wight = weight;
        Head = grap->GListNode[end].listHead;
        Next = Head->next;
        while (Next != NULL)
        {
            Head = Next;
            Next = Head->next;
        }
        InsertNode->next = Next;
        Head->next = InsertNode;
    }

}
typedef struct QueueNode
{
    int PonintNo;
    struct QueueNode* next;
}QueueNode;

QueueNode* CreateQueue()
{
    QueueNode* head = (QueueNode*)malloc(sizeof(QueueNode));
    if (head == NULL)
    {
        return NULL;
    }
    head->next = NULL;
}

EmptyStat EmptyQueue(QueueNode* queueHead)
{
    if (NULL == queueHead)
        return IsEmpty;
    QueueNode* Head = queueHead;
    QueueNode* Next = Head->next;
    if (NULL == Next)
        return IsEmpty;
    else
        return NoEmpty;
}

void EnterQueue(QueueNode** queue,int pointNo)
{
    if (queue == NULL)
        return;

    QueueNode* Head = *queue;
    QueueNode* Next = Head->next;
    while(Next != NULL)
    {
        if (Next->PonintNo == pointNo)
        {
            return;
        }
        Head = Next;
        Next = Head->next;
    }
    QueueNode* InsertNode = (QueueNode*)malloc(sizeof(QueueNode));
    if (NULL == InsertNode)
    {
        return;
    }
    InsertNode->PonintNo = pointNo;
    InsertNode->next = Next;
    Head->next = InsertNode;
    return;
}
QueueNode* OutQueue(QueueNode** queue)
{
    if (NULL == queue)
        return NULL;

    QueueNode* Head = *queue;
    QueueNode* Next = Head->next;
    QueueNode* tmp;
    if (NULL == Next)
        return NULL;
    tmp = Next;
    Head->next = Next->next;
    return tmp;
}

void BFS(GRAPH* grap)
{
    int VisitLog[MAX];
    int i;
    for (i=0; i<grap->points; i++)
    {
        VisitLog[i] = NoVisit;
    }

    QueueNode* OutNode;
    QueueNode* QueueHead = CreateQueue();
    EnterQueue(&QueueHead,grap->GListNode[0].pointNo);
    while(EmptyQueue(QueueHead) == NoEmpty)
    {
        OutNode = OutQueue(&QueueHead);
        if (OutNode == NULL)
        {
            return;
        }

        VisitLog[OutNode->PonintNo] = HasVisit;
        ListNode* ListHead = grap->GListNode[OutNode->PonintNo].listHead;
        ListNode* ListNext = ListHead->next;
        while (ListNext != NULL)
        {
            if (VisitLog[ListNext->pointNo] == NoVisit)
            {
                printf("(%d,%d) = %d\n",OutNode->PonintNo,ListNext->pointNo,ListNext->wight);
                EnterQueue(&QueueHead,ListNext->pointNo);
            }

            ListHead = ListNext;
            ListNext = ListHead->next;
        }
        free(OutNode);
        OutNode = NULL;
    }

}

void DFS_Trav(GRAPH* grap,int i,int* Visit)
{
    Visit[i] = HasVisit;
    ListNode* ListNext = grap->GListNode[i].listHead->next;
    while (NULL != ListNext)
    {
        if (Visit[ListNext->pointNo] == NoVisit)
        {
            printf("(%d,%d)=%d\n",i,ListNext->pointNo,ListNext->pointNo);
            DFS_Trav(grap,ListNext->pointNo,Visit);
        }
        ListNext = ListNext->next;
    }
}
void DFS(GRAPH* grap)
{
    int VisitLog[MAX];
    int i;
    for (i=0; i<grap->points; i++)
    {
        VisitLog[i] = NoVisit;
    }

    for (i=0; i<grap->points; i++)
    {
        if (VisitLog[i] == NoVisit)
        {
            DFS_Trav(grap,i,VisitLog);
        }
    }
}

void main()
{
    printf("-------------   链表相关操作  -------------\n");
    NODE* List;
    List = Create();

    int i;
    for (i=1; i<10; i++)
    {
        Insert(&List, i);
    }
    Visit(List);
    printf("----------\n");
    Delete(&List,5);
    Visit(List);

    printf("--------------  树相关操作  --------------\n");

    TREE* tree = NULL;
//    tree = CreateHead();
    CreateTree(&tree);
    PreVisit(tree);
    printf("-------\n");
    MidVisit(tree);
    printf("-------\n");
    EndVisit(tree);

    printf("Depth = %d\n",Depth(tree));

    printf("-------------------    图相关操作    --------------------------\n");
    GRAPH myGrap;
    CreateG(&myGrap);

    BFS(&myGrap);

    printf("-------DFS-----------\n");
    DFS(&myGrap);
}