求救数据结构实验 — 编程爱好者社区

主题：求救数据结构实验

yueming [专家分：60] 发布于 2005-12-28 21:46:00

我们要交实验报告了
哪位好心人给我提供几个
在下谢谢了
可以发到我的油箱里
hbcdzym@163.com
数据结构实习一

1、设有一个双链表，每个结点中除有 prior，next 及 data〔可设为正整数〕三个域之外，还有一个专门记录访问该结点次数的数据域 freq，其值在初始化时为零。每当在链表中进行一次 seach〔l，key〕时，则数据域  data 之值等于 key 的结点，其  freq 域之值将加一。并使该双链表中结点按 freq 之值的递减顺序排列，freq 值越大的结点越靠近表头。请编写符合上述要求的 seach〔l，key〕程序。

2、请写出计算两个以单链接表表示的多项式相乘的程序。

数据结构实习二

1、假设有 N 个栈共同使用一块顺序存储的空间，为简单起见可设为共同使用数组 int a〔200〕。初始状态为各栈等分备用空间。每当有某栈上溢时，按下述方法调整各栈的备用空间；将全部备用空间的 X％均分给各栈，其余（100 - X）%  按上一次调整以来各栈的增长的比例分配给各栈，请给出这 N 个栈的出、入栈算法。

2、假设以带头结点的循环链接表表示队列，并且只设一个指向队尾结点的指针，请给出进出队的完整的程序。
数据结构实习三

1、在计算机上以字符串的形式输入一个表达式，如：〔A－B〕×C/D + E^F.             假定该表达式只有 +, －，×，/ ,^ 及（）运算.  请：
        （1）先将该表达式变成后缀形式；
        （2）计算该表达式之值。
2、在计算机上以字符串的形式输入了两个任意长的整数，请编写求这两个整数的积的程序。
数据结构实习四

1、两棵二叉树称作相似的，它们要么全为空。要么不是空树但它们的左子树相似且右子树相似。请设计一个程序判断两棵二叉树是否相似。

2、请编写一个程序，确定二叉树的特征。如：每个节点的层次，从根到该节点的枝长（路径长度），子孙的个数及祖先的个数。每个节点在前序、中序、后序中的访问的序号。
数据结构实习五

以数偶的形式输入一串数据。如：(A，B)为从起始结点，其数据域之值为一大写的英文字母A，到终止结点，其数据域之值为一大写的英文字母B的无向边。请用无向图的邻接多重表存储该无向图，并注意一定要使用动态存储结构。如果该数偶代表有向边的话，请用有向图的十字链表存储该有向图，并注意也要使用动态存储结构。
已知一以动态存储结构形式存储的，以邻接多重表表示的无向图。请编写一个统一的程序，用以求解最小代价生成树问题及源点至其它顶点间的最短距离问题。可由使用者指明究竟求解哪个问题。

  数据结构实习六

1、奇偶分类。将被分类的序列进行如下操作。反复进行直至不再进行交换为止。
第一遍：比较x[i]同x[i+1](对所有奇数i);
第二遍：比较x[i]同x[i+1](对所有偶数i);
每次比较，如果x[i]>x[i+1]则交换之，继续这样作，直至不交换为止。
（1）该方法的结束条件如何?
（2）写一个C程序加以实现。
2、作为输入给定的是四个俱乐部C1，C2，C3，C4的未排好次序的成员名单。假定各个俱乐部的成员名单不超过250，请编写一个程序，给出至少属于三个俱乐部的一切人的名单，设成员名单中写的不是名字而是正整数编号。

本帖地址： http://bbs.pfan.cn/post/133147.html

回复列表（共7个回复）

沙发

yueming [专家分：60] 发布于 2005-12-28 21:49:00

能做出来的就是高手
厉害

板凳

猫与鼠 [专家分：70] 发布于 2006-02-20 12:47:00

我就写第一个吧

3 楼

zhhe0423 [专家分：0] 发布于 2006-03-26 14:56:00

请写出计算两个以单链接表表示的多项式相乘的程序。
这个我也要写的，下周就交了，能不能给我也发一份阿？
邮箱zhhe0423@gmail.com
谢谢了

4 楼

yuer868 [专家分：160] 发布于 2006-03-26 20:19:00

/*。。。。。。。。。。递归遍历。。。。。。。。。。。。。*/
#include <iostream.h>
#include <malloc.h>
typedef char elemtype;
#define NULL 0
typedef struct BiTNode{
   elemtype data;
   struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

void CreateBiTree(BiTree &T) //按先序序列建立一个二叉树
{   char c;
    cin>>c;
    if (c=='#')
        T=NULL;
    else
    {
      if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) ;

    T->data = c; // 生成根结点
    CreateBiTree(T->lchild); // 构造左子树
    CreateBiTree(T->rchild); // 构造右子树
    }

} // CreateBiTree
typedef struct Qnode
{
    BiTree data;

    struct Qnode *next;
}Qnode,*QueuePtr;
typedef struct
{
    QueuePtr frond;
    QueuePtr rear;
}LinkQueue;

int initqueue(LinkQueue &Q)//队列初始化
{
    Q.frond=Q.rear=(QueuePtr)malloc(sizeof(Qnode));
    if(!Q.frond)
        return 0;
    Q.frond->next=NULL;
    return 1;
}

int enqueue(LinkQueue &Q,BiTree &e)//入队
{
    QueuePtr p;
    p=(QueuePtr)malloc(sizeof(Qnode));
    if(!p)
        return 0;
    p->data=e;
    p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
    return 1;
}

int dequeue(LinkQueue &Q,BiTree &e)//出队
{
    if(Q.frond==Q.rear)
        return 0;
    QueuePtr p;
    p=Q.frond->next;
    e=p->data;
    Q.frond->next=p->next;
    if(Q.rear==p)
        Q.rear=Q.frond;
    free(p);
    return 1;
}

bool queueempty(LinkQueue &Q)//判断队列是不是空的
{
    if(Q.frond==Q.rear)
        return 0;
    else
        return 1;
}

bool visit(elemtype e)//访问函数
{
    if(e!='0')
    {
      cout<<e;
      return 1;
    }
    else return 0;

}

void preordertr(BiTree &T)//先序遍历
{
    if(T)
    {

        visit(T->data);
        preordertr(T->lchild);
        preordertr(T->rchild);



    }


}

void postordertr(BiTree &T)//后序遍历
{
    if(T)
    {
        postordertr(T->lchild);
        postordertr(T->rchild);
        visit(T->data);
    }
}

void inordertr(BiTree &T)//中序遍历
{
    if(T)
    {
        inordertr(T->lchild);
        visit(T->data);
        inordertr(T->rchild);

    }

}

int levelordertr(BiTree &T,LinkQueue &Q)//层序遍历
{   BiTree p;
    p=T;
    if(!T)
        return 0;

    initqueue(Q);
    if(!visit(T->data))
        return 0;
    enqueue(Q,T);
    while(queueempty(Q))
    {
        dequeue(Q,p);
        if(p->lchild)
        {
                if(!(visit(p->lchild->data)))
                    return 0;
                enqueue(Q,p->lchild);
        }
        if(p->rchild)
        {
                if(!(visit(p->rchild->data)))
                    return 0;
                enqueue(Q,p->rchild);
        }

    }

}

int depthtree(BiTree &T)//求深度
{   int left,right;
    if(!T)
        return 0;
    else
    {
        left=depthtree(T->lchild);
        right=depthtree(T->rchild);
        return (left>right?left:right)+1;
    }
}
//求树的宽度

int countnode(BiTree &T)//求树的接点数
{
    if(!T)
        return 0;
    else
        return countnode(T->lchild)+countnode(T->rchild)+1;
}

5 楼

yuer868 [专家分：160] 发布于 2006-03-26 20:19:00

//求叶子节点的个数
int leaf=0;
void count(BiTree &T)
{
    if(!T->lchild&&!T->rchild)
        leaf++;
}
void leafnode(BiTree &T)
{

    if(T)
    {
        count(T);
        leafnode(T->lchild);
        leafnode(T->rchild);
    }
}

bool iscompletetree(BiTree &T,LinkQueue &Q)//判断是否是完全二叉树、
{
    BiTree p;
    p=T;
    if(!T)
        return 0;
    initqueue(Q);
    enqueue(Q,T);
    while(queueempty(Q))
    {   dequeue(Q,p);
        if(p)
        {
              enqueue(Q,p->lchild);
              enqueue(Q,p->rchild);
        }
        if(!p)
        {
            while(queueempty(Q))
            {
                 p=T;
                 dequeue(Q,p);
                 if(p)
                 {
                     cout<<"不是完全二叉树"<<endl;
                     return 0;
                 }
            }

        }
    }
    return 1;
}
void main()
{
    cout<<"请输入字符,用#表示空接点"<<endl;
    BiTree T;
    CreateBiTree(T);
    cout<<"先序遍历的结果是："<<endl;
          preordertr(T);

    cout<<endl<<"后序遍历的结果是："<<endl;
          postordertr(T);

    cout<<endl<<"中序遍历的结果是："<<endl;
          inordertr(T);

    cout<<endl<<"层序遍历的结果是："<<endl;
          LinkQueue q;
          levelordertr(T,q);

    cout<<endl<<"树的深度是："<<endl;
          cout<<depthtree(T);

    cout<<endl<<"树的节点数是："<<endl;
           cout<<countnode(T)<<endl;
    cout<<"树的叶子节点数是："<<endl;
           leafnode(T);
    cout<<leaf<<endl;

    if(iscompletetree(T,q))
           cout<<"是完全二叉树"<<endl;

}
//这是我以前的数据结构作业借你参考下

6 楼

yuer868 [专家分：160] 发布于 2006-03-26 20:23:00

至于判断俩二叉树是否相似
你可以用递归来写
分别对左右子树进行递归

7 楼

yuer868 [专家分：160] 发布于 2006-03-26 20:27:00

1、在计算机上以字符串的形式输入一个表达式，如：〔A－B〕×C/D + E^F.             假定该表达式只有 +, －，×，/ ,^ 及（）运算.  请：
        （1）先将该表达式变成后缀形式；
        （2）计算该表达式之值。
这一题你可以用用栈来做确定进栈出栈的顺序(即运算符数字的优先级)
仔细想、想很简单的

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：求救数据结构实验

回复列表（共7个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：求救数据结构实验

回复列表 （共7个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共7个回复）