数据结构经典算法代码实现

迪杰斯特拉算法求两点之间最短路径 堆排序 队列的循环和链式存储 二叉树及输出 广度优先搜索 赫夫曼编码 深度优先搜素 图的数组表示及普利姆算法 稀疏矩阵(三元组)及其转置 稀疏矩阵的十字链表 线索二叉树

#include 
#include 
#include 

using namespace std;

typedef char ElemType;

typedef struct BitNode
{
    ElemType data;
    struct BitNode *lchild *rchild;
}BitNode *BiTree;

typedef BiTree ElemType2;

typedef struct SStack
{
    ElemType2 data;
    struct SStack *next;
}*Stack;

void InitStack（Stack &S）
{
    S = （Stack）malloc（sizeof（SStack））;
    S -> next = NULL;
}

bool StackEmpty（Stack S）
{
    return !（S->next）;
}

ElemType2 GetTop（Stack S）
{
    if（S -> next == NULL）
    {
        cout<<“The Stack is empty!“<        return NULL;
    }
    return S->next->data;
}

void Push（Stack &S ElemType2 e）
{
    Stack p = （Stack）malloc（sizeof（SStack））;
    p -> data = e;
    p -> next = S -> next;
    S -> next = p;
}

ElemType2 Pop（Stack &S）
{
    if（!S->next）
    {
        cout<<“Delete error The stack is empty!“<        exit（0）;
    }
    Stack p = S -> next;
    S -> next = p -> next;
    ElemType2 e = p -> data;
    free（p）;
    return e;
}

void CreateBiTree（BiTree &T）   //To construct a binary tree
{
    char c;
    cin>>c;
    if（c == ‘#‘）
    {
        T = NULL;
    }
    else
    {
        T = （BiTree）malloc（sizeof（BitNode））;
        T -> data = c;
        CreateBiTree（T -> lchild）;
        CreateBiTree（T -> rchild）;
    }
}

/*
void InOrderTraverse（BiTree T）  //In Order
{
    if（T）
    {
        InOrderTraverse（T -> lchild）;
        cout<data<<“ “;
        InOrderTraverse（T -> rchild）;
    }
}*/

/*
void InOrderTraverse（BiTree T）
{
    Stack S;
    InitStack（S）;
    Push（ST）;
    BiTree p;
    while（!StackEmpty（S））
    {
        while（p = GetTop（S）） Push（S p->lchild）;
        p = Pop（S）;
        if（!StackEmpty（S））
        {
            p = Pop（S）;
            cout<< p->data <<“ “;
            Push（Sp->rchild）;
        }
    }
}
*/

void InOrderTraverse（BiTree T）
{
    Stack S;
    InitStack（S）;
    BiTree p = T;
    while（p || !StackEmpty（S））
    {
        if（p）
        {
            Push（Sp）;
            p = p->lchild;
        }
        else
        {
            p = Pop（S）;
            cout<< p->data <<“ “;
            p = p->rchild;
        }
    }
}

void PreOrderTraverse（BiTree T）  //Pre Order
{
    if（T）
    {
        cout<data<<“ “;
        PreOrderTraverse（T -> lchild）;
        PreOrderTraverse（T -> rchild）;
    }
}

void PostOrderTraverse（BiTree T） // Post Order
{
    if（T）
    {
        PostOrderTraverse（T -> lchild）;
        PostOrderTraverse（T -> rchild）;
        cout<data<<“ “;
    }
}

int main（）
{
    BiTree T;
    cout<<“Please input the data to construct a binary tree（input ‘#‘ as a flag of the end）:“<    CreateBiTree（T）;
    cout<<“PreOrderTraverse:“<    PreOrderTraverse（T）;
    cout<    cout<<“InOrderTraverse:“<    InOrderTraverse（T）;
    cout<    cout<<“PostOrder

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-02-08 22:11  数据结构经典算法\
     目录           0  2018-02-08 22:11  数据结构经典算法\二叉树及输出\
     目录           0  2018-02-08 22:11  数据结构经典算法\二叉树及输出\bin\
     目录           0  2018-02-08 22:11  数据结构经典算法\二叉树及输出\bin\Debug\
     文件      972864  2017-12-15 20:06  数据结构经典算法\二叉树及输出\bin\Debug\二叉树及输出.exe
     文件        3091  2017-12-15 20:06  数据结构经典算法\二叉树及输出\main.cpp
     目录           0  2018-02-08 22:11  数据结构经典算法\二叉树及输出\obj\
     目录           0  2018-02-08 22:11  数据结构经典算法\二叉树及输出\obj\Debug\
     文件       19664  2017-12-15 20:06  数据结构经典算法\二叉树及输出\obj\Debug\main.o
     文件        1139  2017-12-11 19:57  数据结构经典算法\二叉树及输出\二叉树及输出.cbp
     文件         143  2017-12-15 17:27  数据结构经典算法\二叉树及输出\二叉树及输出.depend
     文件         324  2017-12-15 20:06  数据结构经典算法\二叉树及输出\二叉树及输出.layout
     目录           0  2018-02-08 22:11  数据结构经典算法\图的数组表示及普利姆算法\
     目录           0  2018-02-08 22:11  数据结构经典算法\图的数组表示及普利姆算法\bin\
     目录           0  2018-02-08 22:11  数据结构经典算法\图的数组表示及普利姆算法\bin\Debug\
     文件      970507  2017-12-15 18:33  数据结构经典算法\图的数组表示及普利姆算法\bin\Debug\图的数组表示及普利姆算法.exe
     文件        2910  2017-12-15 18:29  数据结构经典算法\图的数组表示及普利姆算法\main.cpp
     目录           0  2018-02-08 22:11  数据结构经典算法\图的数组表示及普利姆算法\obj\
     目录           0  2018-02-08 22:11  数据结构经典算法\图的数组表示及普利姆算法\obj\Debug\
     文件       16013  2017-12-15 18:33  数据结构经典算法\图的数组表示及普利姆算法\obj\Debug\main.o
     文件        1193  2017-12-11 20:35  数据结构经典算法\图的数组表示及普利姆算法\图的数组表示及普利姆算法.cbp
     文件         273  2017-12-15 18:12  数据结构经典算法\图的数组表示及普利姆算法\图的数组表示及普利姆算法.depend
     文件         322  2017-12-15 18:35  数据结构经典算法\图的数组表示及普利姆算法\图的数组表示及普利姆算法.layout
     目录           0  2018-02-08 22:11  数据结构经典算法\堆排序\
     目录           0  2018-02-08 22:11  数据结构经典算法\堆排序\bin\
     目录           0  2018-02-08 22:11  数据结构经典算法\堆排序\bin\Debug\
     文件      968215  2017-12-15 19:42  数据结构经典算法\堆排序\bin\Debug\堆排序.exe
     文件        1092  2017-12-15 19:43  数据结构经典算法\堆排序\main.cpp
     目录           0  2018-02-08 22:11  数据结构经典算法\堆排序\obj\
     目录           0  2018-02-08 22:11  数据结构经典算法\堆排序\obj\Debug\
     文件       13257  2017-12-15 19:42  数据结构经典算法\堆排序\obj\Debug\main.o
............此处省略174个文件信息