目的:单链表应用的算法设计
内容:

这里编辑标签内容

本实验中设计的功能算法如下:
(1) CreatTable(&h):采用交互方式建立单链表h。
(2) DestroyTable(&h):销毁单链表h。
(3) DispTable(h):输出单链表h。
(4) LinkTable(h1,h2,&h):由h1和h2连接产生结果单链表h。
代码如下:

#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct
{
    ElemType data[MaxSize];
    int length;
}SqList;
typedef ElemType SqBinTree[MaxSize];
typedef struct node
{
    ElemType data;
    struct node * lchild;
    struct node * rchild;
}BTNode;
void CreateBTree(BTNode * &b,char*str)
{
    BTNode * St[MaxSize],*p;
    int top=-1,k,j=0;
    char ch;
    b=NULL;
    ch =str[j];
    while (ch!='\0')
    {
        switch(ch)
        {
        case'(':top++;St[top]=p;k=1;break;
        case')':top--;break;
        case',':k=2;break;
        default:p=(BTNode *)malloc(sizeof(BTNode));
            p->data=ch;
            p->lchild=p->rchild=NULL;
            if (b==NULL)
                b=p;
            else
            {
                switch(k)
                {
                case 1:St[top]->lchild=p;break;
                case 2:St[top]->rchild=p;break;
                }
            }
        }
        j++;
        ch=str[j];
    }
}
void DestroyBTree(BTNode *&b)
{
    if(b!=NULL)
    {
        DestroyBTree(b->lchild);
        DestroyBTree(b->rchild);
        free(b);
    }
}
BTNode *FindNode(BTNode *b,ElemType x)
{
    BTNode * p;
    if (b==NULL)
        return NULL;
    else if(b->data==x)
        return b;
    else
    {
        p=FindNode(b->lchild,x);
        if (p!=NULL)
            return p;
        else 
            return FindNode(b->rchild,x);
    }
}
BTNode *LchildNode(BTNode *p)
{
    return p->lchild;
}
BTNode *RchildNode(BTNode * p)
{
    return p->rchild;
}
int BTHeight(BTNode * b)
{
    int lchildh,rchildh;
    if (b==NULL)return(0);
    else
    {
        lchildh =BTHeight(b->lchild);
        rchildh =BTHeight(b->rchild);
        return (lchildh>rchildh)?(lchildh+1):(rchildh+1);
    }
}
void DispBTree(BTNode * b)
{
    if(b!=NULL)
    {
        printf("%c",b->data);
        if(b->lchild!=NULL || b->rchild!=NULL)
        {
            printf("(");
            DispBTree(b->lchild);
            if(b->rchild!=NULL)printf(",");
            DispBTree(b->rchild);
            printf(")");
        }
    }
}
int main()
{
    BTNode *b;
    CreateBTree(b,"A(B(D(,G)),C(E,F)");
    printf("二叉树b为:");
    DispBTree(b);
    printf("\n");
    
    printf("b的高度为:%d\n",BTHeight(b));
    if (FindNode(b,'F')==NULL)
        printf("b中不存在F\n");
    else
        printf("二叉树b中存在F节点\n");
    char a;
    while (1)
    {
        printf("请输入需要查找的节点\n");
        scanf("%c",&a);
    
        if (FindNode(b,a)==NULL)
            {
                printf("b中不存在该节点\n");
                getchar();
        }
        else
        {
            printf("二叉树b中存在该节点\n");
            getchar();
        }
    }
}

运行结果如下:

程序结构:

Last modification:December 17th, 2019 at 03:35 pm
如果觉得我的文章对你有用,可以打赏一瓶汽水钱嗷~