数据结构课程设计

目录
1. 需求分析: 4
1.1问题描述: 4
1.2问题要求: 4
2. 概要设计 4
2.1抽象数据类型定义 4
2.2设计思路 4
2.2.1模块调用： 4
3详细设计 6
3.1存储结构设计 6
3.1.1顺序查找的基本思想 6
3.1.2二分法查找（折半查找）的基本思想 7
3.1.3斐波那契查找的前提是待查找的查找表必须顺序存储并且有序 9
3.1.4二叉排序树简介 10
3.2二叉排序树相关操作 11
3.3功能模块设计 20
4.运行与测试 27
5.总结 32
6.附录 32

1. 需求分析:
   1.1问题描述:
   设计一个实现①顺序查找②二分查找（折半查找）、④二叉排序树、⑤平衡二叉树、③哈希查找算法的程序，并具有人机交互界面。
   基本要求：
   （1）设计一个菜单将实现的查找算法的名字显示出来，并提示用户对查找算法进行选择；
   （2）分别实现顺序查找、二分查找（折半查找）、二叉排序树、哈希查找；
   （3）哈希函数采用除留余数发，解决冲突的方法大家任选择一种；
   （4）二叉排序树必须实现构建、查找、插入、删除四个基本操作；
   （5）输出各种排序的结果并进行比较。
   要求：如何用多种数据结构来求解问题。同时要求实现对应数据结构的所有基本操作。
   1.2问题要求:
   (1) 建立顺序表，设置关键字来实现顺序查找。
   (2) 运用上述建立的顺序表，来实现二分查找。
   (3) 建立链表结构，综合运用队列的相关知识，实现二叉树的排序。
   (4) 运用除留余数法来分配空间，线性探测法来解决冲突实现哈希查找
   (5) 在主函数中调用用户自定义函数，输出相应结果
   (6) 本程序是对几种查找算法的综合比较
2. 概要设计
   2.1抽象数据类型定义
   查询数据类型定义：
   ADT chaxun{
   数据对象：D={aij|aij属于{1，2，3…},i,j>0}
   数据关系：R={

typedef struct BSTNode
 {
   KeyType key;     //数据域
   BSTNode *lchild;
   BSTNode *rchild;
 }

3.2.2二叉排序树的插入操作
(1)如果二叉排序树T为空，则创建一个关键字为k的结点，将其作为根结点。
(2)否则将k和根结点的关键字进行比较，如果相等则返回，如果k小于根结点的关键字则插入根结点的左子树中，否则插入根结点的右子树中。
二叉排序树的插入算法：

   int InsertBST(BSTNode *p, KeyType k)
  {
     if(p==NULL)
     {
       p=(BSTNode*)malloc(sizeof(BSTNode));
       p->key=k;
       p->lchild=p->rchild=NULL;
       return 1;
     }
     else if(k==p->key)
       return 0;
     else if(k<p->key)
       return InsertBST(p->lchild, k);
     else
       return InsertBST(p->rchild, k);
  }

二叉排序树的生成 BSTNode *CreateBST(KeyType A[], int n)
{
BSTNode *bt=NULL;
int i=0;
while(i

*p只有左子树，或只有右子树。
            对于这种情况，可以直接将*p的左子树或右子树与其双亲结点*f相连，然后删除*p。
            p为f的左孩子，p的左子树非空：
                             f->lchild=p->lchild;
                             free(p);
            p为f的左孩子，p的右子树非空：
                             f->lchild=p->rchild;
                             free(p); 
            p为f的右孩子，p的左子树非空：
                             f->rchild=p->lchild;
                             free(p);
            p为f的右孩子，p的右子树非空：
                             f->rchild=p->rchild;

                             free(p);

    操作示意图如下：
                  ![这里写图片描述](https://img-blog.csdn.net/20180710145636221?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3doajcwNzIxNjg1Mw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70)                    
       (3)*p有左右子树。

方法一：设*s为*p结点在中序序列中的直接前驱，将*p的左子树改为*f的左子树，将*p的右子树改为*s的右子树。
f->lchild=p->lchild;
s->rchild=p->rchild;

                  free(p);
        操作示意图如下：
                         ![这里写图片描述](https://img-blog.csdn.net/20180710145704781?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3doajcwNzIxNjg1Mw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70)                             

方法二：用*p结点在中序序列中的直接前驱(或后继)*s代替*p，然后再从二叉排序树中将*s删除。这时如果*s为*p的直接前驱，则*s只有左子树(或者没有孩子)，则删除*s可以按照删除*p的其余两种情况处理。如果*s为*p的直接后继，则*s只有右子树(或者没有孩子)，删除*s同理可以按照删除*p的其余两种情况处理。
平衡二叉树:
平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

平衡二叉树大部分操作和二叉查找树类似，主要不同在于插入删除的时候平衡二叉树的平衡可能被改变，并且只有从那些插入点到根结点的路径上的结点的平衡性可能被改变，因为只有这些结点的子树可能变化。
平衡二叉树不平衡的情形：
把需要重新平衡的结点叫做α，由于任意两个结点最多只有两个儿子，因此高度不平衡时，α结点的两颗子树的高度相差2.容易看出，这种不平衡可能出现在下面4中情况中：
1.对α的左儿子的左子树进行一次插入
2.对α的左儿子的右子树进行一次插入
3.对α的右儿子的左子树进行一次插入
4.对α的右儿子的右子树进行一次插入

情形1和情形4是关于α的镜像对称，二情形2和情形3也是关于α的镜像对称，因此理论上看只有两种情况，但编程的角度看还是四种情形。
第一种情况是插入发生在“外边”的情形（左左或右右），该情况可以通过一次单旋转完成调整；第二种情况是插入发生在“内部”的情形（左右或右左），这种情况比较复杂，需要通过双旋转来调整。

调整措施：
①　单旋转

上图是左左的情况，k2结点不满足平衡性，它的左子树k1比右子树z深两层，k1子树中更深的是k1的左子树x，因此属于左左情况。
为了恢复平衡，我们把x上移一层，并把z下移一层，但此时实际已经超出了AVL树的性质要求。为此，重新安排结点以形成一颗等价的树。为使树恢复平衡，我们把k2变成这棵树的根节点，因为k2大于k1，把k2置于k1的右子树上，而原本在k1右子树的Y大于k1，小于k2，就把Y置于k2的左子树上，这样既满足了二叉查找树的性质，又满足了平衡二叉树的性质。
这种情况称为单旋转。

②　双旋转
对于左右和右左两种情况，单旋转不能解决问题，要经过两次旋转。

对于上图情况，为使树恢复平衡，我们需要进行两步，第一步，把k1作为根，进行一次右右旋转，旋转之后就变成了左左情况，所以第二步再进行一次左左旋转，最后得到了一棵以k2为根的平衡二叉树。
AVL树的删除操作：
同插入操作一样，删除结点时也有可能破坏平衡性，这就要求我们删除的时候要进行平衡性调整。
删除分为以下几种情况：
首先在整个二叉树中搜索要删除的结点，如果没搜索到直接返回不作处理，否则执行以下操作：
①　.要删除的节点是当前根节点T。
如果左右子树都非空。在高度较大的子树中实施删除操作。
分两种情况：
(1)、左子树高度大于右子树高度，将左子树中最大的那个元素赋给当前根节点，然后删除左子树中元素值最大的那个节点。
(2)、左子树高度小于右子树高度，将右子树中最小的那个元素赋给当前根节点，然后删除右子树中元素值最小的那个节点。
如果左右子树中有一个为空，那么直接用那个非空子树或者是NULL替换当前根节点即可。
②　、要删除的节点元素值小于当前根节点T值，在左子树中进行删除。
递归调用，在左子树中实施删除。
这个是需要判断当前根节点是否仍然满足平衡条件，
如果满足平衡条件，只需要更新当前根节点T的高度信息。
否则，需要进行旋转调整：
如果T的左子节点的左子树的高度大于T的左子节点的右子树的高度，进行相应的单旋转。否则进行双旋转。
③　、要删除的节点元素值大于当前根节点T值，在右子树中进行删除。
3.3功能模块设计
哈希表和哈希函数
在记录的存储位置和它的关键字之间是建立一个确定的对应关系（映射函数），使每个关键字和一个存储位置能唯一对应。这个映射函数称为哈希函数，根据这个原则建立的表称为哈希表(Hash Table)，也叫散列表。
以上描述，如果通过数学形式来描述就是：
若查找关键字为 key，则其值存放在 f(key) 的存储位置上。由此，不需比较便可直接取得所查记录。
注：哈希查找与线性表查找和树表查找最大的区别在于，不用数值比较。

冲突
若 key1 ≠ key2 ，而 f(key1) = f(key2)，这种情况称为冲突(Collision)。
根据哈希函数f(key)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这一映射过程称为构造哈希表。
构造哈希表
常见的构造哈希表的方法有 5 种：
（1）直接定址法
说白了，就是小学时学过的一元一次方程。
即 f(key) = a * key + b。其中，a和b 是常数。

（2）数字分析法
假设关键字是R进制数（如十进制）。并且哈希表中可能出现的关键字都是事先知道的，则可选取关键字的若干数位组成哈希地址。
选取的原则是使得到的哈希地址尽量避免冲突，即所选数位上的数字尽可能是随机的。

（3）平方取中法
取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，仅取其中的几位为地址不一定合适；
而一个数平方后的中间几位数和数的每一位都相关， 由此得到的哈希地址随机性更大。取的位数由表长决定。

（4）除留余数法
取关键字被某个不大于哈希表表长 m 的数 p 除后所得的余数为哈希地址。
即 f(key) = key % p (p ≤ m)
这是一种最简单，最常用的方法，它不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。
注意：p的选择很重要，如果选的不好，容易产生冲突。根据经验，一般情况下可以选p为素数。

（5）随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即 f(key) = random(key)。
通常，在关键字长度不等时采用此法构造哈希函数较为恰当。
解决冲突
（1）开放定址法
如果两个数据元素的哈希值相同，则在哈希表中为后插入的数据元素另外选择一个表项。
当程序查找哈希表时，如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素，程序就会继续往后查找，直到找到一个符合查找要求的数据元素，或者遇到一个空的表项。
例子
若要将一组关键字序列 {1, 9, 25, 11, 12, 35, 17, 29} 存放到哈希表中。
采用除留余数法构造哈希表；采用开放定址法处理冲突。
不妨设选取的p和m为13，由 f(key) = key % 13 可以得到下表。

需要注意的是，在上图中有两个关键字的探查次数为 2 ，其他都是1。
这个过程是这样的：
a. 12 % 13 结果是12，而它的前面有个 25 ，25 % 13 也是12，存在冲突。
我们使用开放定址法 (12 + 1) % 13 = 0，没有冲突，完成。
b. 35 % 13 结果是 9，而它的前面有个 9，9 % 13也是 9，存在冲突。
我们使用开放定址法 (9 + 1) % 13 = 10，没有冲突，完成。
2）拉链法
将哈希值相同的数据元素存放在一个链表中，在查找哈希表的过程中，当查找到这个链表时，必须采用线性查找方法。
在这种方法中，哈希表中每个单元存放的不再是记录本身，而是相应同义词单链表的头指针。
例子
如果对开放定址法例子中提到的序列使用拉链法，得到的结果如下图所示：

1、线性探查
设给出一组元素，它们的关键码为：37,25,14,36,49,68,57,11，散列表为HT[12]，表的大小m = 12，假设采用Hash(x) = x % p; // (p = 11) 11是接近m的质数，就有：
Hash(37) = 4 Hash(25) = 3 Hash(14) = 3 Hash(36) = 3 Hash(49) = 5 Hash(68) = 2 Hash(57) = 2 Hash(11) = 0
采用线性探查法处理冲突

需要加入一个元素时，使用散列函数进行计算，确定元素的桶号H0，按此桶号查看该桶，如果是所 要搜索的元素的关键码，则说明表中已有此元素，不再进行此元素的插入，否则即为冲突，再查看紧 随其后的下一个桶，如果是空桶，则搜索失败，新元素插入即可。
在闭散列的情形下不能随便物理删除表中已有的元素。因为若删除元素会影响其他元素的搜索。
散列表的装填因子
散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度
α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小
线性探查方法容易产生“堆积”问题，即不同探查序列的关键码占据了可利用的空桶，使得为寻 找某一关键码需要经历不同的探查序列的元素，导致搜索时间增加。因此，当散列表经常变动 时，好不要用闭散列法处理冲突，可以利用二次探查法可以改善上述的“堆积”问题，减少为完成 搜索所需的平均探查次数。
2、二次探查
使用二次探查法，在表中寻找“下一个”空桶的公式为： Hi = (H0 + i^2)%m, Hi = (H0 - i^2)%m, i = 1,2,3…，(m-1)/2 H0 = Hash(x)是通过散列函数Hash()对元素的关键码x进行计算得到的桶号，它是一个非负整数。 m是表的大小，它应该是一个质数。
假设数组的关键码为37,25,14,36,49,68,57,11，假设取m=19，这样可设定为HT[19]，采用散列函 数Hash(x) = x % 19 Hash(37)=18 Hash(25)=6 Hash(14)=14 Hash(36)=17 Hash(49)=11 Hash(68)=11 Hash(57)=0 Hash(11)=11
采用二次探查法处理冲突：

研究表明当表的长度TableSize为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而 且任何一个位置都不会被探查两次。因此只要表中有一半的空的，就不会有表满的问题。在搜索时
可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5；如果超出必须考虑增容。
哈希表的结构体：

typedef struct{  //哈希表线性探测再散列数据类型定义
    int key;          //关键字
    int si;       //插入成功时的次数
}HashTable1;

typedef struct Ha{   //哈希表链地址法数据类型定义
    int elem;           //数据项
    struct Ha *next2;   //指向下一个结点的指针
}HashTable2;

typedef struct{  //哈希表二次探测再散列法数据类型定义
    int elem[HashSize];     //表中储存数据元素的数组
    int count;              //表中储存数据元素的个数
    int size;              //哈希表的尺寸
}HashTable3;

创建哈希表:

void CreateHashTable1(HashTable1 *H,int *a,int num) //哈希表线性探测再散列(除留余数法)
{
    int i,d,cnt;
    for(i=0; i<HashSize; i++)     //给新哈希表初始化数据
    {
        H[i].key=0;         H[i].si=0;
    }
    for(i=0; i<num; i++)
    {
        cnt=1;
        d=a[i]%HashSize;     //构造哈希函数
        if(H[d].key==0)      //无冲突时，直接插入数据
        {
            H[d].key=a[i];
            H[d].si=cnt;
        }
        else{               //有冲突时，进行线性探测法解决冲突再插入
                do{
                    d=(d+1)%HashSize;
                    cnt++;
                }
                while(H[d].key!=0);
                H[d].key=a[i];
                H[d].si=cnt;
            }
    }
    printf("\n线性再探测哈希表已建成!\n");
}

void CreateHashTable2(HashTable2 *H,int *a,int num)
{
    int key,i;
    HashTable2 *q,*qq;
    q=NULL;
    for (i=0; i<HashSize; i++)              //对哈希表进行初始化
    {
        H[i].elem = 0;
        H[i].next2=NULL;
    }
    for (i=0; i<num; i++)
    {
        key=a[i]%HashSize;
        if(H[key].elem==0)
            H[key].elem=a[i];
        else
        {
            if(q!=NULL)     //若该位置已有数据
            {
                qq=q;
                q=q+1;
                q->elem=a[i];                //添加到已存在的结点后面
                q->next2=qq->next2;
                qq->next2=q;
            }
            else
            {
                q=(HashTable2*)malloc(sizeof(HashTable2));
                if(!q)
                {
                    printf("\n申请内存失败!请重新运行程序\n");
                    exit(1);
                }
                q->elem=a[i];                     //添加到首结点后面
                q->next2=H[key].next2;
                H[key].next2=q;
            }
        }
    }
    printf("\n链表探索哈希表已建成!\n");
}

哈希表的查找:

void SearchHash1(HashTable1 *h,int data)
{
    int d,i;
    d=data%HashSize; //哈希函数
    i=d;
    if(h[d].key==data)     //一次查找成功
        printf("\n数字%d的查找次数为：%d\n",h[d].key,h[d].si);
    else
    {
        while(i<HashSize && h[d].key!=data )
        {
            d=(d+1)%HashSize;
            i+=1;
        }
        if(i<HashSize)
            printf("\n数字%d的查找次数为：%d.\n",h[d].key,h[d].si);
        else
            printf("\n没有找到您所输入的数\n");
    }
}

int SearchHash2(HashTable2 *h,int data,int num)
{
    int d,cnt=1;
    HashTable2 *q;
    d=data%HashSize;       //哈希函数
    q=&h[d];
    if(q->elem==0)         //该位置上没有数据元素
    {
        printf("\n没有找到您要查找的数\n");
        return 0;
    }
    while(q!=NULL)
    {
        if(q->elem==data)
        {
            printf("\n数字%d的查找次数为：%d\n",data,cnt);
            return 0;
        }
        else if(q->next2!=NULL)
        {
            q=q->next2;
            cnt++;
        }
        else
        {
            printf("\n没有找到您要查找的数\n");
            return 0;
        }
    }
    return 0;   printf("\n");}

4.运行与测试
主菜单：

静态查找：
文件读取：
折半查找：

顺序查找：

动态查找：
建立二叉排序树:

查找:

插入：

删除：

平衡二叉树:

散列法查找：
读数据并输出：

线性再散列法查找：

链地址法查找：

5.总结
本次课程设计开始调试的时候经常出现很多BUG，经常容易烦躁，但是一步步修改代码，调试程序渐渐解决bug的过程也是很愉快的。在程序设计方面，逐渐感觉到模块化设计的重要性，应该分析出功能模块，然后对其细节中的共性和特性作分析。
这次的设计，让我感觉到，成功的程序设计是要建立在熟悉语言的基础之上的。每一次程序设计能大大地增加对语言的熟悉和感知，能使理论与实际应用相结合，提高了自己组织数据及编写程序的能力。培养了基本的、良好的程序设计技能以及合作能力。在上机操作的过程中，培养了我实际分析问题、编程和动手能力，使我掌握了程序设计的基本技能，提高了我适应实际和实践编程的能力。
6.附录

#include<stdio.h>
#include<stdlib.h>
#include <fstream>
#include <iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define HashSize 50
#define MAX 100
#define LH 1
#define EH 0
#define RH -1
FILE *fp;
int data[20];
int data2[20];

//********************************************************************
int Binary_Search(int key,int low,int high)//折半查找
{
    int mid;
    if(low == high)
    {
        if(data[low] == key)
            return low;
        else
            return -1;
    }
    else
    {
        mid = (low + high) / 2;
        if(mid == low)
            mid++;
            if(key < data[mid])
            return Binary_Search(key, low, mid - 1);
        else
            return Binary_Search(key, mid, high);
    }
}

void zheban()
{
    int locate;
    int key;
    if((fp=fopen("D:\\编程的文件\\查找算法性能比较\\折半查找.txt","r"))==NULL)
    {
        printf("cannot open file\n");
    }
    for(int i=0;i<20;i++)
    fscanf(fp,"%d",&data[i]);
    fclose(fp);
    printf("\n有序序列为：\n");
    for(int i=0;i<20;i++)
        printf("%d ",data[i]);
    printf("\n请输入要查找的数: ");
    scanf("%d", &key);
    if(key != -1)
    {
        locate = Binary_Search(key,0,19);
        if(locate != -1)
        {
            printf("\n值%d的位置为:%d\n\n", key, locate+1);
        }
        else
        {
            printf("没有找到%d\n", key);
        }
    }
    else
        exit(1);
    cout<<endl;
}
//************************************************************************
typedef struct
{
    int key;   //关键字
    int data;    //信息域
}Record;                                  //用给定的关键字值与表中其他元素的关键字值比较
typedef struct
{
    Record r[MAX+1];
    int length;
}SqTable;
int search(SqTable s,int k)
{
  int i;
  s.r[0].key=k;
  i=s.length;      //自几用的逆序
  while(s.r[i].key!=k)
        i--;
  return i;
}
void sunxu()
{
    SqTable s;
    int wz,i,len,x,y;
   printf("请输入表长:\n");
    scanf("%d",&len);
    s.length=len;
    printf("请输入表的各个元素:\n");
    for(i=1;i<=len;i++)
    {
        scanf("%d",&x);
        s.r[i].key=x;
    }
     printf("请输入要查找的元素:\n");
    scanf("%d",&y);
    wz=search(s,y);
    if(wz==0)
    {
        printf("不存在:\n");
    }
    else
        printf("位置为:%d",wz);
}
//************************************************************************
void fibonacci(int *f)//斐波那契数
{
    f[0] = 1;
    f[1] = 1;
    for(int i = 2;i < 20;++i)
        f[i] = f[i - 2] + f[i - 1];
}
int fibonacci_search(int *a,int key,int n)//斐波那契查找
{
    int low = 0,high = n - 1;
    int mid = 0;
    int k = 0;
    int F[20];
    fibonacci(F);
    while(n > F[k] - 1) //计算出n在斐波那契中的数列
        ++k;
    for(int i = n;i < F[k] - 1;++i) //把数组补全
        a[i] = a[high];
    while(low <= high)
    {
        mid = low + F[k-1] - 1;  //根据斐波那契数列进行黄金分割
        if(a[mid] > key)
        {
            high = mid - 1;
            k = k - 1;
        }
        else if(a[mid] < key)
        {
            low = mid + 1;
            k = k - 2;
        }
        else{
            if(mid <= high) //如果为真则找到相应的位置
                return mid;
            else
                return -1;
        }
    }
    return -1;
}
int Fibonacci()
{
    if((fp=fopen("D:\\编程的文件\\查找算法性能比较\\斐波那契.txt","r"))==NULL)
    {
        printf("cannot open file\n");
    }
    for(int i=0;i<20;i++)
        fscanf(fp,"%d",&data[i]);
    fclose(fp);
    printf("\n有序序列为：\n");
    for(int i=0;i<20;i++)
        printf("%d ",data[i]);
    printf("\n");
    int k;
    printf("\n请输入要查找的数:\n");
    scanf("%d",&k);
    int pos = fibonacci_search(data,k,20);
    if(pos != -1)
        printf("\n值%d的位置为：%d\n\n", k, pos+1);
    else
        printf("没有找到%d\n", k);
    return 0;
}
//**************************************************************************
struct node//二叉排序树
{
    int data;
    struct node  *rlink;
    struct node  *llink;
};

struct node *tree;

void inordertraverse(struct node *tree)
{
    if(tree)
    {
        inordertraverse(tree->llink);
        cout<<tree->data<<" ";
        inordertraverse(tree->rlink);
    }
}

 struct node *find(struct node *tree, int x)  //二叉排序树的查找算法
{
   int f;
   struct node *p,*q;
   p=tree;
   f=0;
   q=( struct node *)malloc(sizeof (struct node));
   while((!f)&&(p!=NULL))
   {
     if(p->data==x)
        f=1;
    else
        if(x<p->data)
            p=p->llink;
        else
            p=p->rlink;
   }
   if(f)
    q=p;
   else
    q->data=NULL;
   return(q);
}


 struct node *findparents(struct node *tree, int x)  //二叉排序树双亲节点的查找算法
{
   int f;
   struct node *p,*q,*r;
   p=tree;
   f=0;
   q=( struct node *)malloc(sizeof (struct node));
   r=( struct node *)malloc(sizeof (struct node));
   r=NULL;
   while((!f)&&(p!=NULL))
   {
       if(p->data==x)
        f=1;
       else
        {
            r=p;
            if(x<p->data)
            {
                p=p->llink;
            }
            else
            {
                p=p->rlink;
            }
        }
    }
    if(f)
        q=p;
    else
        q->data=NULL;
   return(r);
}
struct node * insertree(struct node *tree,  int x )  //插入
{
   struct node *p,*q;
   if(tree==NULL)
   {
      p= (struct node *)malloc(sizeof(struct node));
      p->data=x;
      p->rlink=NULL;
      p->llink=NULL;
      tree=p;
   }
   else
   {  p=tree;
      while(p!=NULL)
      {
         q=p;
         if (x<p->data)
            p=p->llink;
         else
            p=p->rlink;
      }
      p=(struct node *)malloc(sizeof(struct node));
      p->data=x;
      p->rlink=NULL;
      p->llink=NULL;
      if (x<q->data)
        q->llink=p;
      else
        q->rlink=p;
   }
   return tree;
}


void detree(struct node *t, struct node *f, struct node *p)  //删除
{
    struct node *q,*s;
    int boo;
    boo=0;
    if((p->llink==NULL)||(p->rlink==NULL))
    {
        if(p->llink==NULL)
        {
            if(p==t)
                t=p->rlink;
            else
            {
                s=p->rlink;
                boo=1;
            }
        }
        else
        {
            if(p==t)
                t=p->llink;
            else
            {
                s=p->llink;
                boo=1;
            }
       }
    }
    else
    {
        q=p;
        s=q->rlink;
        while(s->llink!=NULL)
        {
            q=s;
            s=s->llink;
        }
        s->llink=p->llink;
        if (q!=p)
        {
            q->llink=s->rlink;
            s->rlink=p->rlink;
        }
        if(p==t)
            t=s;
        else
            boo=1;
    }
    if (boo==1)
    {
        if(p==f->llink)
            f->llink=s;
        else
            f->rlink=s;
    }
    free(p);
}
//**************************************************************************
typedef struct BTNode
{
 int data;
 int BF;//平衡因子（balance factor）
 struct BTNode *lchild,*rchild;
}BTNode,*BTree;
void R_Rotate(BTree *p)//以p为根节点的二叉排序树进行右旋转
{
 BTree L;
 L=(*p)->lchild;
 (*p)->lchild=L->rchild;
 L->rchild=(*p);
 *p=L;//p指向新的根节点
}
void L_Rotate(BTree *p)//以p为根节点的二叉排序树进行左旋转
{
 BTree R;
 R=(*p)->rchild;
 (*p)->rchild=R->lchild;
 R->lchild=(*p);
 *p=R;
}
void LeftBalance(BTree *T)
{
 BTree L,Lr;
 L=(*T)->lchild;
 switch(L->BF)
 {
  //检查T的左子树平衡度，并作相应的平衡处理
  case LH://新节点插入在T的左孩子的左子树上，做单右旋处理
   (*T)->BF=L->BF=EH;
   R_Rotate(T);
   break;
  case RH://新插入节点在T的左孩子的右子树上，做双旋处理
   Lr=L->rchild;
   switch(Lr->BF)
   {
    case LH:
     (*T)->BF=RH;
     L->BF=EH;
     break;
    case EH:
     (*T)->BF=L->BF=EH;
     break;
    case RH:
     (*T)->BF=EH;
     L->BF=LH;
     break;
   }
   Lr->BF=EH;
   L_Rotate(&(*T)->lchild);
   R_Rotate(T);
 }
}
void RightBalance(BTree *T)
{
 BTree R,Rl;
 R=(*T)->rchild;
 switch(R->BF)
 {
  case RH://新节点插在T的右孩子的右子树上，要做单左旋处理
   (*T)->BF=R->BF=EH;
   L_Rotate(T);
   break;
  case LH://新节点插在T的右孩子的左子树上，要做双旋处理
   Rl=R->lchild;
   switch(Rl->BF)
   {
    case LH:
     (*T)->BF=EH;
     R->BF=RH;
     break;
    case EH:
     (*T)->BF=R->BF=EH;
     break;
    case RH:
     (*T)->BF=LH;
     R->BF=EH;
     break;
   }
   Rl->BF=EH;
   R_Rotate(&(*T)->rchild);
   L_Rotate(T);
 }
}
bool InsertAVL(BTree *T,int e,bool *taller)//变量taller反应T长高与否
{
 if(!*T)
 {
  *T=(BTree)malloc(sizeof(BTNode));
  (*T)->data=e;
  (*T)->lchild=(*T)->rchild=NULL;
  (*T)->BF=EH;
  *taller=true;
 }
 else
 {
  if(e==(*T)->data)//不插入
  {
   *taller=false;
   return false;
  }
  if(e<(*T)->data)
  {
   if(!InsertAVL(&(*T)->lchild,e,taller))//未插入
    return false;
   if(*taller)//以插入左子树，且左子树变高
   {
    switch((*T)->BF)
    {
     case LH://原本左子树比右子树高，需要做左平衡处理
      LeftBalance(T);
      *taller=false;
      break;
     case EH://原本左右子树等高，现因左子树增高而树增高
      (*T)->BF=LH;
      *taller=true;
      break;
     case RH://原本右子树比左子树高，现在左右子树等高
      (*T)->BF=EH;
      *taller=false;
      break;
    }
   }
  }
  else
  {
   //应在T的右子树中搜寻
   if(!InsertAVL(&(*T)->rchild,e,taller))
    return false;
   if(*taller)//插入右子树，且右子树长高
   {
    switch((*T)->BF)
    {
     case LH://原本左子树比右子树高，现在左右子树等高
      (*T)->BF=EH;
      *taller=false;
      break;
     case EH://原本左右子树等高，现在右子树变高
      (*T)->BF=RH;
      *taller=true;
      break;
     case RH://原本右子树比左子树高，现在需做右平衡处理
      RightBalance(T);
      *taller=false;
      break;
    }
   }
  }
 }
 return true;
}
bool Find(BTree T,int key)
{
 if(!T)
  return false;
 else if(T->data==key)
  return true;
 else if(T->data<key)
  return Find(T->rchild,key);
 else
  return Find(T->lchild,key);
}
void Output(BTree T)
{
 if(T)
 {
  printf("%d",T->data);
  if(T->lchild||T->rchild)
  {
   printf("(");
   Output(T->lchild);
   printf(",");
   Output(T->rchild);
   printf(")");
  }
 }
}
void pingheng()
{
 int i,n;
 printf("请输入你将要建立几个节点的二叉树:\n");
 scanf("%d",&n);
 int A[n];
 int a,b;
 for(i=0;i<n;i++)
 {
     scanf("%d",&a);
     A[i]=a;
 }
 BTree T=NULL;
 bool taller;
 for(i=0;i<sizeof(A)/sizeof(int);i++)
  InsertAVL(&T,A[i],&taller);
  printf("建立好的平衡二叉树为:\n");
 Output(T);
 printf("\n");
 printf("请输入要查找的数:\n");
 scanf("%d",&b);
 if(Find(T,b))
  printf("%d 在二叉平衡数中!\n",b);
 else
  printf("%d 不在二叉平衡数中!\n",b);
}

//********************************************************

//散列法
typedef struct{  //哈希表线性探测再散列数据类型定义
    int key;          //关键字
    int si;       //插入成功时的次数
}HashTable1;

typedef struct Ha{   //哈希表链地址法数据类型定义

    int elem;           //数据项
    struct Ha *next2;   //指向下一个结点的指针
}HashTable2;

typedef struct{  //哈希表二次探测再散列法数据类型定义
    int elem[HashSize];     //表中储存数据元素的数组
    int count;              //表中储存数据元素的个数
    int size;              //哈希表的尺寸
}HashTable3;

void CreateHashTable1(HashTable1 *H,int *a,int num) //哈希表线性探测再散列(除留余数法)
{
    int i,d,cnt;
    for(i=0; i<HashSize; i++)     //给新哈希表初始化数据
    {
        H[i].key=0;         H[i].si=0;
    }
    for(i=0; i<num; i++)
    {
        cnt=1;
        d=a[i]%HashSize;     //构造哈希函数
        if(H[d].key==0)      //无冲突时，直接插入数据
        {
            H[d].key=a[i];
            H[d].si=cnt;
        }
        else{               //有冲突时，进行线性探测法解决冲突再插入
                do{
                    d=(d+1)%HashSize;
                    cnt++;
                }
                while(H[d].key!=0);
                H[d].key=a[i];
                H[d].si=cnt;
            }
    }
    printf("\n线性再探测哈希表已建成!\n");
        printf("散列表的位置:\n");
  for(i=0;i<20;i++)
        printf("%d  ",i);
        printf("\n");
        printf("关键字:\n");
  for(i=0;i<20;i++)
    printf("%d  ",H[i].key);
    printf("\n");
}

void CreateHashTable2(HashTable2 *H,int *a,int num)
{
    int key,i;
    HashTable2 *q,*qq;
    q=NULL;
    for (i=0; i<HashSize; i++)              //对哈希表进行初始化
    {
        H[i].elem = 0;
        H[i].next2=NULL;
    }
    for (i=0; i<num; i++)
    {
        key=a[i]%HashSize;
        if(H[key].elem==0)
            H[key].elem=a[i];
        else
        {
            if(q!=NULL)     //若该位置已有数据
            {
                qq=q;
                q=q+1;
                q->elem=a[i];                //添加到已存在的结点后面
                q->next2=qq->next2;
                qq->next2=q;
            }
            else
            {
                q=(HashTable2*)malloc(sizeof(HashTable2));
                if(!q)
                {
                    printf("\n申请内存失败!请重新运行程序\n");
                    exit(1);
                }
                q->elem=a[i];                     //添加到首结点后面
                q->next2=H[key].next2;
                H[key].next2=q;
            }
        }
    }
    printf("\n链表探索哈希表已建成!\n");
}

void SearchHash1(HashTable1 *h,int data)
{
    int d,i;
    d=data%HashSize; //哈希函数
    i=d;
    if(h[d].key==data)     //一次查找成功
        printf("\n数字%d的查找次数为：%d\n",h[d].key,h[d].si);
    else
    {
        while(i<HashSize && h[d].key!=data )
        {
            d=(d+1)%HashSize;
            i+=1;
        }
        if(i<HashSize)
            printf("\n数字%d的查找次数为：%d.\n",h[d].key,h[d].si);
        else
            printf("\n没有找到您所输入的数\n");
    }
}

int SearchHash2(HashTable2 *h,int data,int num)
{
    int d,cnt=1;
    HashTable2 *q;
    d=data%HashSize;       //哈希函数
    q=&h[d];
    if(q->elem==0)         //该位置上没有数据元素
    {
        printf("\n没有找到您要查找的数\n");
        return 0;
    }
    while(q!=NULL)
    {
        if(q->elem==data)
        {
            printf("\n数字%d的查找次数为：%d\n",data,cnt);
            return 0;
        }
        else if(q->next2!=NULL)
        {
            q=q->next2;
            cnt++;
        }
        else
        {
            printf("\n没有找到您要查找的数\n");
            return 0;
        }
    }
    return 0;
    printf("\n");
}

void GetIn()
{
    if((fp=fopen("D:\\编程的文件\\查找算法性能比较\\散列法.txt","r"))==NULL)   //
    {
        printf("cannot open file\n");
    }
    for(int i=0;i<20;i++)
        fscanf(fp,"%d",&data2[i]);
    fclose(fp);
    printf("\n序列为：\n");
    for(int i=0;i<20;i++)
        printf("%d ",data2[i]);
    printf("\n");
}

void mainmenu();

void menu1()
{
    int m;
    cout<<endl;
    cout<<"\t\t|------------------静态查找---------------|"<<endl;
    cout<<"\t\t|-----------------------------------------|"<<endl;
    cout<<"\t\t|\t\t1.折半查找\t\t  |"<<endl;
    cout<<"\t\t|-----------------------------------------|"<<endl;
    cout<<"\t\t|\t\t2.顺序查找\t\t  |"<<endl;
    cout<<"\t\t|-----------------------------------------|"<<endl;
    cout<<"\t\t|\t\t3.斐波拉契查找\t\t  |"<<endl;
    cout<<"\t\t|-----------------------------------------|"<<endl;
    cout<<"\t\t|\t\t4.退出静态查找\t\t  |"<<endl;
    cout<<"\t\t|-----------------------------------------|"<<endl;
    cout<<"请选择：";
    cin>>m;
    while(m<1||m>4)
    {
        cout<<"输入有误，请重新输入！";
        cin>>m;
    }
    switch(m)
    {
        case 1:
            zheban();
            menu1();
            break;
        case 2:
            sunxu();
            menu1();
            break;
        case 3:
            Fibonacci();
            menu1();
            break;
        case 4:
            cout<<"退出静态查找！"<<endl;
            system("cls");
            mainmenu();
    }
}

void menu2()
{
    int m;
    cout<<endl;
    cout<<"\t\t|------------------动态查找---------------|"<<endl;
    cout<<"\t\t|-----------------------------------------|"<<endl;
    cout<<"\t\t|\t       1.建立二叉排序树\t\t  |"<<endl;
    cout<<"\t\t|-----------------------------------------|"<<endl;
    cout<<"\t\t|\t       2.二叉排序树查找\t\t  |"<<endl;
    cout<<"\t\t|-----------------------------------------|"<<endl;
    cout<<"\t\t|\t       3.二叉排序树插入\t\t  |"<<endl;
    cout<<"\t\t|-----------------------------------------|"<<endl;
    cout<<"\t\t|\t       4.二叉排序树删除\t\t  |"<<endl;
    cout<<"\t\t|-----------------------------------------|"<<endl;
    cout<<"\t\t|\t       5.平衡二叉树   \t\t  |"<<endl;
    cout<<"\t\t|-----------------------------------------|"<<endl;
    cout<<"\t\t|\t       6.退出动态查找\t\t  |"<<endl;
    cout<<"\t\t|-----------------------------------------|"<<endl;
    cout<<"请选择：";
    cin>>m;
    while(m<1||m>6)
    {
        cout<<"\n输入有误，请重新输入:\n";
        cin>>m;
    }
    switch(m)
    {
        case 1:
        {
            tree=(struct node*)malloc(sizeof(struct node));
            tree =NULL;
            cout<<"\n输入数字建立二叉排序树，以-1结束:"<<endl;
            while(1)
            {
                int y;
                cin>>y;
                if(-1==y)
                    break;
                tree=insertree(tree,y);
            }
            cout<<"\n中序遍历：";
            inordertraverse(tree);
            cout<<endl;
        }menu2();break;
        case 2 :                          //查找
        {
            int x;
            cout<<"\n请输入您要查找的数："<<endl;
            cin>>x;
            if(find(tree, x)->data==x)
                cout<<"\n已找到您要查找的数！"<<find(tree,x)->data<<endl;
            else
                cout<<"\n未找到您要查找的数！"<<endl;
        }menu2();break;
        case 3 :                         //插入
        {
            int x;
            cout<<"\n请输入您要插入的数"<<endl;
            cin>>x;
            insertree(tree, x );
            cout<<"\n中序遍历：";
            inordertraverse(tree) ;
            cout<<endl;
        }menu2();break;
        case 4:                            //删除
        {
            cout<<"\n请输入您要删除的数据"<<endl;
            struct node *f,*p;
            int x;
            cin>>x;
            p=find(tree, x);
            f=findparents(tree, x);
            detree(tree, f, p);
            cout<<"\n中序遍历：";
            inordertraverse(tree) ;
            cout<<endl;
        }menu2();break;
        case 5:
        {
            pingheng();
        }menu2();break;
        case 6:
            cout<<"退出动态查找！"<<endl;
    }
    system("cls");
    mainmenu();
}


void menu3()
{   int m,d,i;
    HashTable1 hash1[HashSize];
    HashTable2 hash2[HashSize];
    HashTable3 * ha;                    //定义三种类型的哈希表
    ha=(HashTable3 *)malloc(sizeof(HashTable3));
    for(i=0; i<HashSize; i++)//哈希表的初始化
    {
        ha->elem[i]=0;
        ha->count=0;
    }
    ha->size=HashSize;
    while(1)
    {
        cout<<endl;
        cout<<"\t\t|------------------散列法查找-------------|"<<endl;
        cout<<"\t\t|-----------------------------------------|"<<endl;
        cout<<"\t\t|\t   1.从文件中读出数据并输出\t  |"<<endl;
        cout<<"\t\t|-----------------------------------------|"<<endl;
        cout<<"\t\t|\t   2.线性再散列(除留余数法)建立哈希表\t  |"<<endl;
        cout<<"\t\t|-----------------------------------------|"<<endl;
        cout<<"\t\t|\t   3.链地址法建立哈希表\t\t  |"<<endl;
        cout<<"\t\t|-----------------------------------------|"<<endl;
        cout<<"\t\t|\t   4.线性再散列法(线性探测法)查找\t\t  |"<<endl;
        cout<<"\t\t|-----------------------------------------|"<<endl;
        cout<<"\t\t|\t   5.链地址法查找\t\t  |"<<endl;
        cout<<"\t\t|-----------------------------------------|"<<endl;
        cout<<"\t\t|\t   6.退出散列法查找\t\t  |"<<endl;
        cout<<"\t\t|-----------------------------------------|"<<endl;
        cout<<"请选择：";
        cin>>m;
        while(m<1||m>6)
        {
            cout<<"输入有误，请重新输入:";
            cin>>m;
        }
        switch(m)
        {
            case 1:
                GetIn();
                break;
            case 2:
                CreateHashTable1(hash1,data2,20);
                break;
            case 3:
                CreateHashTable2(hash2,data2,20);
                break;
            case 4:
                printf("请输入你查找的数据：");
                scanf("%d",&d);
                SearchHash1(hash1,d);
                break;
            case 5:
                printf("请输入你查找的数据：");
                cin>>d;
                SearchHash2(hash2,d,20);
                break;
            case 6:
                system("cls");
                mainmenu();
        }
}


}
void mainmenu()
{
    int m;
    cout<<"\t\t|-------------------菜单------------------|"<<endl;
    cout<<"\t\t|-----------------------------------------|"<<endl;
    cout<<"\t\t|\t\t1.静态查找\t\t  |"<<endl;
    cout<<"\t\t|-----------------------------------------|"<<endl;
    cout<<"\t\t|\t\t2.动态查找\t\t  |"<<endl;
    cout<<"\t\t|-----------------------------------------|"<<endl;
    cout<<"\t\t|\t\t3.散列法查找\t\t  |"<<endl;
    cout<<"\t\t|-----------------------------------------|"<<endl;
    cout<<"\t\t|\t\t4.退出\t\t\t  |"<<endl;
    cout<<"\t\t|-----------------------------------------|"<<endl;
    cout<<"请选择：";
    cin>>m;
    while(m<1||m>4) {cout<<"输入有误，请重新输入:";cin>>m;}
    switch(m)
    {
        case 1:
            menu1();
            mainmenu();
            break;
        case 2:
            menu2();
            mainmenu();
            break;
        case 3:
            menu3();
            mainmenu();
            break;
        case 4:
            cout<<"退出程序！";
            exit(0);
    }
}

int main()
{
    mainmenu();
    return 0;
}