上海理工大学本科课程设计报告《数据结构课程设计A》

0目  录

第1章  编译和运行情况（存在的问题） 1

第2章  解题思路 2

第3章  三组测试数据 9

第4章  短学期学习心得 11

参考文献 13

 

 

 

 

 

第1章  编译和运行情况（存在的问题）

 

 

 

第2章  解题思路

（1）建立一棵二叉树，利用插入函数和查找函数完成二叉树函数的创建工作。

#include <stdio.h>

#include <iostream>

#include <string.h>

#include <stdlib.h>

#include <stack>

#define N 200

using namespace std;

  

typedef struct tree

{

    int data;

char ch;

    struct tree *lchild,*rchild;

}Tree,BitTree,*bitree;

  

/*如果返回成功，p指向查找成功的那个节点，如果失败就返回查找路径上的最后一个节点，便于我插入*/

int SearchBST(bitree T,int key,bitree f,bitree &p)/*T为根节点，key为要查找的值，f为T的双亲，f的初值为NULL*/

{

    if(!T)

    {

        p=f;//这里必须是f而不能是NULL，因为如果查找不成功p应该指向访问的最后一个节点，这个函数可能会反复递归，所以不能保证f一定是初始值NULL

        return 0;

    }

    else

    {

        if(T->data==key)

        {

            p=T;

            return 1;

        }

        else if(T->data<key)

            return SearchBST(T->rchild,key,T,p);

        else

            return SearchBST(T->lchild,key,T,p);

    }

}

  

/*插入函数*/

int InsertBST(bitree &T,int key)//这里的T要加引用

{

    bitree p,s;

    if(!SearchBST(T,key,NULL,p))//查找不成功才会插入呀

    {

        s=new Tree[sizeof(Tree)];//注意这种new的写法

        s->data=key;//初始化

        s->lchild=s->rchild=NULL;//初始化

        if(!p)//这里必须考虑到p为空的情况，因为一开始T就是空的，现在我就让T为s

            T=s;//这里也不能写p=s，p是局部变量，函数结束就释放了，而我想改变的是T

        else if(key<p->data)

            p->lchild=s;

        else

            p->rchild=s;

        return 1;

    }

    return 0;

}

（2）前序、中序、层次非递归遍历该二叉树

前序非递归遍历，利用栈来实现；根结点进栈，之后栈非空，弹出，接着根节点的右结点进栈， 之后，左节点进栈；接着，弹出栈顶元素（输出）, 此结点的右结点进栈，之后左节点进栈，弹出栈顶元素（输出）， 直到栈为空。

void PreOrder(BitTree *bt)

{

    BitTree **s;

BitTree *p;

int top=-1;

//创建栈；

s=(BitTree **)malloc((N+1)*sizeof(BitTree *));

//初始化栈；

s[++top]=bt;

//非递归前序遍历；

while(top!=-1)

{

p=s[top--];

printf("%d",p->data);    //栈的特点，先进后出；

if(p->rchild)

s[++top]=p->rchild;

if(p->lchild)

s[++top]=p->lchild;

}

free(s);

}

中序非递归遍历，利用栈。从根节点开始循环，只要有左子节点则进栈，直到左子节点为空。接着弹出栈顶输出，判断该结点是否有右子节点，若有则进栈，若没有继续弹栈。有右子节点的情况，判断该节点是否有左子节点，有则进栈，直到左子节点为空；若该右子节点没有左子节点，则弹栈；判断弹出的节点，是否有右子节点，若有则进栈，没有继续弹栈；接着又要判断刚进栈的这个节点，是否有左子节点，有则进栈，没有则继续弹栈，栈空，是判定条件。

void InOrder(BitTree *bt)

{

BitTree **s;

    BitTree *p,*q;

    int top=-1;

//创建栈；

s=(BitTree **)malloc((N+1)*sizeof(BitTree *));

//非递归中序遍历；

    if(bt)

    {

        while(bt)   //一直遍历左子树直到该结点的左孩子空为止；

        {

            s[++top]=bt;   //将所有左孩子存入栈中；

            bt=bt->lchild;     //指向下一个左子树；

        }

        while(top!=-1)  //栈空时结束循环；

        {

            p=s[top--];//刚开始将最p指向左下角的左孩子，并且移向该结点的父结点；

            printf("%d",p->data);  //输出左下角的结点；

            while(p->rchild)  //遍历移动后结点有没有右结点；

            {

                s[++top]=p->rchild;   //将这个结点的右子树入栈；

                q=p->rchild;    //这个右子树结点赋给q；

                while(q->lchild)      //判断结点q有没有左子树；

                {

                    s[++top]=q->lchild;  //有左子树，将与这个结点相连的所有左子树都入栈；

                    q=q->lchild;

                }

                break;   //结束当前循环，回到第二个while循环继续刚才的步骤；

            }

        }

    }

}

层次非递归遍历，利用栈来实现。从根结点开始,只要左子节点非空,则进栈,直到左子节点为空为止。取出栈顶元素(只是取,并非弹栈),判断: 1:取出的栈顶元素是否有右子节点,或者右子节点是否被访问过,若满足条件(无右子节点,或者右子节点被访问过),则输出该结点，同时弹栈,并且记录下该访问的节点。2:取出的栈顶元素，若有右子节点，且未被访问过，则指针继续移动到右子节点，重复一开始是否又左子节点的判断。

void PostOrder(BitTree *bt)

{

BitTree **s;

BitTree *p;

    int top=-1;

//创建栈；

s=(BitTree **)malloc((N+1)*sizeof(BitTree *));

//非递归后序遍历；

    do

    {

        while(bt)     //一直遍历左子树直到该左子树的左孩子空为止；

        {

            s[++top]=bt;     //将所有左孩子存入栈中；

            bt=bt->lchild;   //指向下一个左子树；

        }

        p=NULL;

        while(top!=-1)

        {

            bt=s[top];

            if(bt->rchild==p)  //p:表示为null，或者右子节点被访问过了;

            {

                printf("%d",bt->data);   //输出结点数据域；

                top--;           //输出以后，top--；

                p=bt;  //p记录下刚刚访问的节点;

            }

            else

            {

                bt=bt->rchild;   //访问右子树结点；

                break;

            }

        }

    }while(top!=-1);

}

（3）判断该二叉树是否为二叉排序树

//判断二叉树是否是二叉排序数

int minnum=-32768,flag=1;

int isbstree(BitTree *bt)/*判断是否为二叉排序树*/

{

if (bt!=0)

{

isbstree(bt->lchild);

if(minnum>bt->data)

flag=0;

minnum=bt->data;

isbstree(bt->rchild);

return flag;

}

}

（4）如果是二叉排序树，删除指定结点的兄弟结点

/*

删除节点p，这里没有看到f节点是因为我们不对f的左右指针进行改变，而是巧妙的针对p进行一系列修改这里的删除分为三种情况

（1）左右子树都空：就直接让其父节点的相应指针置空即可

（2）只有左子树或只有右子树：让其父节点的相应指针指向自己的左孩子或者右孩子

（3）左右子树均不空：这里有两种套路，第一种就是先找到p节点中序遍历的直接前驱s，然后将p的父节点f的左指针指向自己的左子树，让s节点的右指针指向自己的右子树；第二种就是让中序遍历的直接前驱或者直接后继代替p自己，然后再删除中序遍历的直接前驱或者直接后继。本文使用第一种方法。

*/

  

int Del(bitree &p)

{

    bitree q;

    if(!p->lchild&&!p->rchild)//没有子女

    {

        q=p;

        p=NULL;

        delete q;

        return 1;

    }

    if(!p->lchild&&p->rchild)//只有右儿子

    {

        q=p;

        p=p->rchild;

        delete q;

        return 1;

    }

    if(p->lchild&&!p->rchild)//只有左儿子

    {

        q=p;

        p=p->lchild;

        delete q;

        return 1;

    }

    if(p->lchild!=NULL&&p->rchild!=NULL)//左右都有，这里采用的是第一种思路

    {

        q=p->lchild;//q此时是p左子树的根节点

        while(q->rchild)//向右探寻，这个循环结束时候，q指向p中序遍历的直接前驱结点

            q=q->rchild;

        q->rchild=p->rchild;//直接前驱节点的右指针修改为p的右子树

        q=p;//此时q回到p的位置便于我delete

        p=p->lchild;//而p修改为p的左子树，本质是p的父节点的左指针不再指向p而是指向p的左子树

        delete q;

        return 1;

    }

}

  

/*递归的查找并找到节点删掉*/

int DeleteBST(bitree &T,int key)//这里的T要加引用

{

    if(!T)

        return 0;

    else

    {

        if(T->lchild->data==key)

            return Del(T->rchild);

        else if(T->lchild->data>key)

            return DeleteBST(T->lchild->lchild,key);

        else

            return DeleteBST(T->lchild->rchild,key);

    }

}

 

（5）创建一个main函数作为程序入口，输出结果。

int main()

{

    int n,x,i;

    bitree T;

printf("请输入二叉树节点数量\n");

    while(scanf("%d",&n)!=EOF)

    {

        T=NULL;

printf("请输入节点值\n");

        for(i=0;i<n;i++)

        {

            scanf("%d",&x);

            InsertBST(T,x);

        }

BitTree *btr=T;

printf("前序遍历非递归实现：\n");

PreOrder(btr);

printf("\n");

printf("中序遍历非递归实现：\n");

InOrder(btr);

printf("\n");

printf("后序遍历非递归实现：\n");

PostOrder(btr);

printf("\n");

//判断二叉树是否是二叉排序数

     flag=isbstree(btr);  

if(flag){  

printf("这棵树是二叉排序树！\n");  

}

else{

printf("这棵树不是二叉排序树！\n");  

}

printf("\n");

        printf("chose a number you'd delete:\n");

        scanf("%d",&x);

        DeleteBST(T,x);

       PreOrder(btr);

   printf("\n");

    return 0;

    }

}

第3章  三组测试数据

（1）原始数据

1，2 1 3

2，5 2 7

3, 5 3 1 4 6 2 7

（2）预期结果

1,前：2 1 3 中： 1 2 3，层次：1 3 2

删除1，前序:2 1

2,前：5 2 7，中：2 5 7 层次： 2 7 5

删除2，前序:5 2

3,前：1 3 2 4 5 6 7，中：1 2 3 4 5 6 7 层次：2 7 6 5 4 3 1

删除4，结果不变

（3）实际结果

第一组数据结果：

 

第二组数据结果：

 

第三组测试结果：

 

.0（1）主要变量的作用

typedef struct tree

{

    int data;

char ch;

    struct tree *lchild,*rchild;

}Tree,BitTree,*bitree;

变量的作用是存储值，data存储二叉树节点的整数值，char用来存储二叉树为节点的字符值，*lchild 用来表示左子节点，*rchild表示右子节点。

（2）函数段的功能

函数的功能主要有创建二叉树、前序非递归遍历二叉树、中序非递归遍历二叉树、层次非递归遍历二叉树、判断是否是有序二叉树、删除节点的兄弟节点、程序入口main()函数。

第4章  短学期学习心得

首先非常感谢老师这学期对我们的教导，在不断实践的过程中发现，无论我们学习什么课程，概念永远是基础，所有的知识都是建立在基础概念之上的。我们要将概念熟记于心，然后构建知识框架。数据结构包括线性结构、树形结构、图状结构或网状结构。线性结构包括线性表、栈、队列、串、数组、广义表等，栈和队列是操作受限的线性表，串的数据对象约束为字符集，数组和广义表是对线性表的扩展:表中的数据元素本身也是一个数据结构。除了线性表以外，栈是重点，因为栈和递归紧密相连，递归是程序设计中很重要的一种工具。树状结构中的重点自然是二叉树和哈弗曼树了。对于二叉树的很多操作都是基于对二叉树的遍历，掌握了如何遍历，很多问题也就迎刃而解了，比如对二叉树结点的查找访问、统计二叉树中叶子结点的数目、求二叉树的深度等。哈弗曼编码也有着很广泛的应用。对于一个算法，如果我们不是很理解的话，可以手动将算法走一遍慢慢理解该算法的思想。

总之，这次的作业真的是非常锻炼自己的认真程度，很小的一个地方就可能出错并很难看出。虽然自己很努力做这份作业，但仍有不足之处，希望自己以后能再接再厉，努力突破自己。

 

 

本文链接：https://daizuozuoye8.com/?id=904

转载声明：本站发布文章及版权归原作者所有，转载本站文章请注明文章来源！