精华内容
下载资源
问答
  • 本次课程设计,程序中的数据采用“树形结构”作为其数据结构。具体采用的是“二叉排序树”,并且使用“二叉链表”来作为其存储...本课程设计实现了二叉排序树的创建、中序遍历、插入、查找和删除二叉排序树中某个结点
  • 数据结构课程设计--动态查找表 用二叉排序树实现动态查找表的虚拟数据类型
  • 动态查找表的相关操作动态查找表的相关操作
  • 设计与实现静态查找表、基于二叉排序树的动态查找表及HASH表等三种中的任意两种查找表结构及其抽象数据类型;以一本英文电子书(如英文小说,科普读物或圣经之类的社会书籍,书的篇幅不少于2万次单词)作为单词文本...

    大二时写的数据结构课程设计,好几个朋友的推荐,现在放到博客了,希望对大家有帮助!

     

     

     

    任务书

    p 设计内容

    设计与实现静态查找表、基于二叉排序树的动态查找表及HASH表等三种中的任意两种查找表结构及其抽象数据类型;以一本英文电子书(如英文小说,科普读物或圣经之类的社会书籍,书的篇幅不少于2万次单词)作为单词文本数据来源,使用上述查找表ADT,通过读取电子书而建立对应的两种查找表,以单词作为关键字,单词在书籍中出现的次数及每次出现的页码,行号等信息作为查找表数据元素属性;通过理论与实际测试结果对比分析两种查找表性能。

    p 设计要求

    (1) 静态查找表ADT要求实现Create、Destroy、Search、Traverse等操作,另外静态查找表同时要求采用某种排序算法Sort对其排序,形成无序存储与有序表存储两种物理存储,并同时实现在有序表上的二分查找Search_Bin,且作为性能对比分析的一种情形。

    (2) 动态查找表ADT要求实现InitDSTable、DestroyTable、SearchDSTable、InsertDSTable、DeleteDSTable、TraverseDSTable等操作,以二叉链表为物理存储结构。

    (3)     HASH表要求实现InitHash、DestroyHash、SearchHash、InsertHash、DeleteHash、TraverseHash等操作,设计合理的HASH函数与冲突解决办法,并在报告中分析说明选择理由。

    (4) 一个单词的多次出现可以由链表表示,形成类似于倒排索引的结构。查找表数据以文件形式保存,如果在程序重启动时能够从查找表文件恢复查找表,或界面友好,或增加了有意义的功能等,具有一定特色,则给予鼓励,酌情加分。但是,如果只实现了其中一种查找表,则综合成绩不超过75分。

     

    引言

    1.1    课题背景与意义

    数据结构在计算机科学界至今没有标准的定义。个人根据各自的理解的不同而有不同的表述方法:

    Sartaj Sahni在他的《数据结构、算法与应用》一书中称:“数据结构是数据对象,以及存在于该对象的实例和组成实 例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”他将数据对象(data object)定义为“一个数据对象是实例或值的集合”。Clifford A.Shaffer在《数据结构与算法分析》一书中的定义是:“数据结构是 ADT(抽象数据类型Abstract Data Type) 的物理实现。”

    Lobert L.Kruse在《数据结构与程序设计》一书中,将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中,抽象层是指抽象数据类型层,它讨论数据的逻辑结构及其运算,数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现。数据结构具体指同一类数据元素中,各元素之间的相互关系,包括三个组成成分,数据的逻辑结构,数据的存储结构和数据运算结构。

    在日常工作和学习中,我们会遇到统计一个文章里面所包含的单词或者词语。然而现在这样的统计软件在网络上特别多,作为一个学计算机编程的学生,我觉得有必要了解一下其核心功能以及算法实现。通过此次设计,可以对上学期学习的数据结构课程的内容做一个总结,感受真正用上学过的算法思想,这对以后的学习以及工作也有很大的帮助。

    1.2    重要意义

    一般认为,一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构;数据必须在计算机内存储,数据的存储结构是数据结构的实现形式,是其在计算机内的表示;此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。

    在许多类型的程序的设计中,数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明,系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候,确定了数据结构后,算法就容易得到了。有些时候事情也会反过来,我们根据特定算法来选择数据结构与之适应。不论哪种情况,选择合适的数据结构都是非常重要的。

        选择了数据结构,算法也随之确定,是数据而不是算法是系统构造的关键因素。这种洞见导致了许多种软件设计方法和程序设计语言的出现,面向对象的程序设计语言就是其中之一。

    1.3    课程设计的主要研究工作

           在计算机科学中,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象(数据元素)以及它们之间的关系和运算等的学科,而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。

    “数据结构”作为一门独立的课程在国外是从1968年才开始设立的。 1968年美国唐·欧·克努特教授开创了数据结构的最初体系,他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。“数据结构”在计算机科学中是一门综合性的专业基础课。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计(特别是非数值性程序设计)的基础,而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。

    计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题:信息的表示,信息的处理 。 而信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及,信息量的增加,信息范围的拓宽,使许多系统程序和应用程序的规模很大,结构又相当复杂。因此,为了编写出一个“好”的程序,必须分析待处理的对象的特征及各对象之间存在的关系,这就是数据结构这门课所要研究的问题。众所周知,计算机的程序是对信息进行加工处理。在大多数情况下,这些信息并不是没有组织,信息(数据)之间往往具有重要的结构关系,这就是数据结构的内容。数据的结构,直接影响算法的选择和效率。

    计算机解决一个具体问题时,大致需要经过下列几个步骤:首先要从具体问题中抽象出一个适当的数学模型,然后设计一个解此数学模型的算法(Algorithm),最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题,从中提取操作的对象,并找出这些操作对象之间含有的关系,然后用数学的语言加以描述。计算机算法与数据的结构密切相关,算法无不依附于具体的数据结构,数据结构直接关系到算法的选择和效率。运算是由计算机来完成,这就要设计相应的插入、删除和修改的算法 。也就是说,数据结构还需要给出每种结构类型所定义的各种运算的算法。

    数据是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。 数据元素是数据的基本单位,在计算机程序中通常作为一个整体考虑。一个数据元素由若干个数据项组成。数据项是数据的不可分割的最小单位。有两类数据元素:一类是不可分割的原子型数据元素,如:整数"5",字符 "N" 等;

    另一类是由多个款项构成的数据元素,其中每个款项被称为一个数据项。例如描述一个学生的信息的数据元素可由下列6个数据项组成。其中的出生日期又可以由三个数据项:"年"、"月"和"日"组成,则称"出生日期"为组合项,而其它不可分割的数据项为原子项。关键字指的是能识别一个或多个数据元素的数据项。若能起唯一识别作用,则称之为 "主" 关键字,否则称之为 "次" 关键字。数据对象是性质相同的数据元素的集合,是数据的一个子集。数据对象可以是有限的,也可以是无限的。

    数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。在早期,计算机主要用于科学和工程计算,进入八十年代以后,计算机主要用于数据处理。据有关统计资料表明,现在计算机用于数据处理的时间比例达到80%以上,随着时间的推移和计算机应用的进一步普及,计算机用于数据处理的时间比例必将进一步增大。

     

     

    系统需求分析与总体设计

    2.1    系统需求分析

    对单词数量不少于2万字的英文小说进行字符统计,用三种数据结构来实现,分别是基于顺序表的实现、基于动态查找表以二叉搜索树为结构来实现、基于HASH表的实现。抽象数据类型由单词、出现次数、页码、行数组成。计算结果以文本文件的形式保存到本地目录。以QT为用户界面,以C语言为编程语言。

    2.2    系统总体设计

    (1)    首先用户通过打开文件或者复制粘贴的方式把要分析的内容放在用户界面上的文本框。文本框的内容用户可以自己输入或更改,完成后通过相应的按钮进行计算并显示。由于有三种数据结构来实现,因此需要把计算内容分别显示。

    (2)    基于顺序表的实现有两种,有序存储结构和无序存储结构。给用户提供两个按钮来相应两种结构的结果输出。创建有序存储先从文本内容里面取单词,把取单词的部分写成单独的函数,以便后序继续使用此函数来取单词,减少代码量。然后从现有的存储结构里面进行查找,如果找到了则单词数目加一,否则进行插入。查找函数以折半查找算法为核心,作为与无序表性能对比分析的一种情形。为了更好的显示出两种存储结构的优缺点,在这些函数运行时进行计时,当所有单词统计出来以后,把总时间显示到界面,以便用户对比分析结果。表创建完成后进行遍历输出,输出的内容有单词内容,单词出现次数、单词出现的页码以及行数,所以以表格的形式在界面上进行显示。

    (3)    基于动态查找表以二叉搜索树为结构来实现。首先从用户输入的内容里面进行读取单词,然后在现有的数据里面进行查找,如果没有找到则进行创建。给用户提供三种遍历方式,前序、中序、后序。同样,在此部分程序运行时进行计时,最后结果在界面上显示,以便进行对比分析。

    (4)    基于HASH表的实现,以每一个单词的第一与第二个字母的ASCLL值的和作为哈希值进行创建,以线性探索来处理冲突,哈希表长度为52。在此部分程序运行时进行计时,最后把结果以表格的形式显示在界面上。

    (5)    计算并输出完成后,用户可以保存计算结果,保存的类型有txt、doc。保存位置由用户决定,用户打开对应的文件夹并输入文件名以后进行输出。

    (6)    提供搜索功能,输入单词以后进行查找,找到单词以后进行定位,并使用QT内部函数给单词染色并突出显示。

    (7)    用户界面上的所有按钮可以用对应的快捷键来控制。QT界面引用CSS样式表来设置界面颜色,总共提供四种风格。

    程序整体流程图为如下:

     

    图 2-1 系统整体运行流程图

    系统详细设计

    3.1    有关数据结构的定义

    一共有四种数据结构,顺序存储结构、二叉树存储结构、HASH表存储结构、行页数存储结构、高频词汇存储结构。

    (1)顺序存储结构

    包含单词内容、单词出现次数、行数、页数,详细如下表:

    表3-1 顺序存储结构数据类型

    数据项

    数据类型

    名称

    单词内容

    Char []

    word

    出现次数

    Int

    count

    行、页数

    row_next *

    row_head

    顺序表的逻辑结构:

    图 3-1  顺序表的逻辑结构

    (1)二叉树存储结构

    包含单词内容、单词出现次数、指向行页数的指针、指向左右结点的指针,详细如下表:

    表 3-2 二叉树存储结构数据类型

    数据项

    数据类型

    名称

    单词内容

    Char []

    word

    出现次数

    Int

    count

    行、页数

    row_next *

    row_head

    左孩子结点

    struct DtList *

    Lchild

    右孩子结点

    struct DtList *

    Rchild

     二叉树逻辑存储结构如下图:

    图 3-2 二叉树逻辑存储结构

    (1)HASH表存储结构

    包含单词内容、单词出现次数、指向行页数的指针, 详细如下表:

    表 3-3 HASH表存储结构类型

    数据项

    数据类型

    名称

    单词内容

    Char []

    word

    出现次数

    Int

    count

    行、页数

    row_next *

    row_head

    指向下一个结点的指针

    struct Link_Node *

    next

     HASH表逻辑存储结构如下图:

    (1)行页数存储结构

    包含行数、页数、指向下一个结点的指针,详细如下表:

    表 3-4 行页存储结构类型

    数据项

    数据类型

    名称

    行数

    Int

    row

    页数

    Int

    page

    指向下一个结点的指针

    struct row_next *

    next

     

    行页结构逻辑存储结构如下图:

    (1)高频词汇存储结构

    包含单词内容、出现次数,详细如下表:

    表 3-5 高频词汇存储结构类型

    数据项

    数据类型

    名称

    单词

    Char []

    word

    次数

    int

    count

     

     

    高频词汇逻辑存储结构:

     

    3.1    主要算法设计

    这部分主要描述系统中的模块实现的流程,可采用文字配合流程图的方式表示各模块的算法思想及流程。

    1. 有序存储

    首先初始化有序表,读取单词,从原有的顺序表中进行折半查找,如果找到了则进行单词数增加,并记录行页数。如果没有找到,则进行插入。流程图如下图:

    1. 无序存储

    无序表创建过程与有序表一样,只是在查找的时候不能用折半查找来实现,只能从头开始一一比较。

    1. 二叉搜索树

    二叉搜索树实现,首先获取内容取单词,创建二叉树,并在原来基础上查找结点,找到了则进行单词数目增加,并记录行页数。没有找到则进行插入。读取文件完成后进行输出,根据用户需求分别用三种遍历来输出,输出完成后计算出高频词汇,进行输出,最后记录运行总时间。流程图如下:

     

     

    1. HASH表

    HASH表实现流程基本上也一样,实现的具体函数功能有所不一样。下图是整体实现过程:

    系统实现与测试

    4.1   系统实现

    1. 结构体

    (1)  顺序存储结构

    包含单词内容、单词出现次数、指向行页数的指针

          

     1  typedef struct
     2 
     3         {
     4 
     5                char word[MAX_CHARACTER];// 存储单词,不超过50个字符
     6 
     7                int count;               // 单词出现次数
     8 
     9                row_next *row_head;      //指向行页数的指针
    10 
    11                row_next *row_tail;      //指向最后一个(方便后序插入)
    12 
    13         } ElemType;
    14 
    15  
    16 
    17         typedef struct
    18 
    19         {
    20 
    21                ElemType *elem;      // 存储空间基址
    22 
    23                int length;          // 当前长度
    24 
    25                int listsize;        // 当前分配的存储容量
    26 
    27 } SqList;

     

    (2)  搜索二叉树存储结构

    包含单词内容、单词出现次数、指向行页数的指针、指向左右结点的指针

           
     1 typedef struct
     2 
     3         {
     4 
     5             char word[MAX_CHARACTER];  // 存储单词,不超过50个字符
     6 
     7             int count;                 // 单词出现次数
     8 
     9             row_next *row_head;        //指向行页数的指针
    10 
    11             row_next *row_tail;        //指向最后一个(方便后序插入)
    12 
    13         }DtElemType;                   //数据类型
    14 
    15  
    16 
    17         typedef struct DtList
    18 
    19         {
    20 
    21             DtElemType elem;                  //存储单词
    22 
    23             struct DtList *Lchild,*Rchild;    //左孩子以及右孩子
    24 
    25 }DtList;

     

    (3)  HASH表存储结构

    包含单词内容、单词出现次数、指向行页数的指针

          
     1  typedef struct Link_Node
     2 
     3         {
     4 
     5             char word[MAX_CHARACTER];    // 存储单词,不超过50个字符
     6 
     7             int count;                   //单词出现次数
     8 
     9             row_next *row_head;          //指向行页数的指针
    10 
    11             row_next *row_tail;          //指向最后一个(方便后序插入)
    12 
    13             struct Link_Node *next;
    14 
    15         }Link_Node;
    16 
    17         
    18 
    19         typedef struct Hash_Header
    20 
    21         {
    22 
    23             Link_Node *Link_head;      //哈希表头
    24 
    25 }Hash_Header;

     

    (4)  行页数存储结构

    包含行数、页数

           
    typedef struct row_next{
    
                int row;                 //行数
    
                int page;                //页数
    
                struct row_next *next;  //指向下一个单词的行数
    
    }row_next;

     

    下面分别介绍具体实现的函数:

    1. 取单词  pickword

    参数为文件地址,字符数组,行数。从文件地址所指的文件中依次读取一个字符,一律转换为小写字符保存在目的单词数组中。目的字符数组长度定义为50个字符,如果超过了进行返回。当遇到换行符时行数增加,遇到非字母字符时读取结束,返回读取到的单词。具体过程如下图:

     

    1. HASH_founc函数

    实现HASH表时,哈希值用每一个单词的第一个字符与第二个字符的ascll码相加再与HASH表长度取余

    1. SqList_search_disorder无序表查找函数

    实现无序表时,需要进行单词的搜索,但这时候很难实现有效的查找算法,只能从表头开始一一比较。

    1. SqListBSearch顺序表二分法查找

    实现有序表时,需要进行单词的搜索,由于创建表时按照字母字典循序创建的,因此查找可以使用二分查找来实现,可以节省时间,效率高。

    1. SqListInit顺序表初始化

    构造一个空的顺序表,分配内存,并初始化表长度,表大小。

    1. Dt_Free使用栈来实现释放二叉搜索树
    2. DtListInsert二叉树插入

    首先找到插入位置,再分别判断是否有左右孩子,分情况分析最后创建结点并插入到对应位置。

    1. DtListPrint_preOrder前序遍历

    用非递归算法来实现,使用栈来实现。

    1. InOrderTraverse中序遍历

    递归算法来实现

    1. Dt_List_postOrder后序遍历

    递归算法来实现

    系统测试

     1.程序运行界面

    2.有序表开始计算

    3.无序表开始计算

    4.

    二叉搜索树中序遍历

    5.

    二叉搜索树前序遍

     

    6.二叉搜索树—后序遍

    7.HASH表

    8.搜索功能

    9.保存

     

     

    10.保存文件演示

    11.行页数

    12.结果分析

     

     13.运行时间窗口演示

    14.源代码演示窗口

    15.帮助选项

     

     

    源代码

     

      1 #ifndef FRMMAIN_H
      2 #define FRMMAIN_H
      3 
      4 #include <string.h>
      5 #include <QDialog>
      6 
      7 
      8 //函数结果状态代码
      9 #define TRUE    1
     10 #define FALSE   0
     11 #define OK      1
     12 #define ERROR   0
     13 #define OVERFLOW -2
     14 
     15 
     16 // 线性表的动态分配顺序存储结构
     17 #define LIST_INIT_SIZE 100  // 线性表存储空间的初始分配量
     18 #define LISTINCREMENT 10    // 线性表存储空间的分配增量
     19 #define HASH_TABLE_LEN  52  // HASH表长
     20 #define PAGE_LINE 26        //每个页行数
     21 
     22 
     23 const int MAX_CHARACTER = 50;       // 单词最大长度定为50(TUT.txt文中最长单词为production-education-researching)
     24 
     25 //行数结构
     26 typedef struct row_next{
     27     int row;
     28     int page;
     29     struct row_next *next;  //指向下一个单词的行数
     30 }row_next;
     31 
     32 // 顺序存储结构
     33 typedef struct
     34 {
     35     char word[MAX_CHARACTER];       // 存储单词,不超过50个字符
     36     int count;          // 单词出现次数
     37     row_next *row_head;            //行数
     38     row_next *row_tail;  //指向最后一个
     39 } ElemType;
     40 typedef struct
     41 {
     42     ElemType *elem;     // 存储空间基址
     43     int length;         // 当前长度
     44     int listsize;       // 当前分配的存储容量(以sizeof(ElemType)为单位)
     45 } SqList;
     46 
     47 
     48 // 线性存储结构
     49 typedef struct
     50 {
     51     char word[MAX_CHARACTER];       // 存储单词,不超过50个字符
     52     int count;          // 单词出现次数
     53     row_next *row_head;   //行数
     54     row_next *row_tail;   //
     55 }DtElemType;//数据类型
     56 
     57 typedef struct DtList
     58 {
     59     DtElemType elem;        //存储单词
     60     struct DtList *Lchild,*Rchild;  //左孩子以及右孩子
     61 }DtList;
     62 
     63 
     64 //HASH表结构
     65 typedef struct Link_Node
     66 {
     67     char word[MAX_CHARACTER];       // 存储单词,不超过50个字符
     68     int count;                      //计数
     69     row_next *row_head;             //行数
     70     row_next *row_tail;             //
     71     struct Link_Node *next;
     72 }Link_Node;
     73 
     74 //哈希表头
     75 typedef struct Hash_Header
     76 {
     77     Link_Node *Link_head;
     78 }Hash_Header;
     79 
     80 
     81 typedef struct High_count{
     82     char word[MAX_CHARACTER];
     83     int count;
     84 }High_count;
     85 
     86 
     87 
     88 class QLineEdit;
     89 namespace Ui {
     90 class frmMain;
     91 }
     92 
     93 class frmMain : public QDialog
     94 {
     95     Q_OBJECT
     96 
     97 public:
     98     explicit frmMain(QWidget *parent = 0);
     99     ~frmMain();
    100     int SqListInit ( SqList *L );
    101     int pickword ( FILE *f, char *fword ,int *row);
    102     int SqListInsert ( SqList *L, int i, char *fword );
    103     int SqList_insert_disorder(SqList *L,char *fword,int row);
    104     int SqListBSearch ( SqList *L, char *sword, int &i );
    105     int SqList_search_disorder(SqList *L, char *sword, int &i);
    106     void SqListPrint(SqList *L);
    107 
    108     int DtListSearch(DtList *L, char *e,DtList **i);
    109     int DtListInsert (DtList **L,char *fword,int row );
    110     int DtListPrint_preOrder(DtList **L);
    111     int Dt_Free(DtList **L);
    112     int InOrderTraverse(DtList *L);
    113     int Dt_List_postOrder(DtList *L);
    114     int DtBiao_Creat(DtList **head);
    115 
    116     int HASH_func(char *word);
    117     int hash_List_Search(Link_Node *L,char *fword,Link_Node **p );
    118     int hash_List_Insert (Link_Node **L,char *fword ,int row);
    119     void HASH_List_print(Hash_Header *L);
    120 
    121     void High_word(SqList *L);
    122 
    123 
    124 protected:
    125     bool eventFilter(QObject *obj, QEvent *event);
    126     void mouseMoveEvent(QMouseEvent *e);
    127     void mousePressEvent(QMouseEvent *e);
    128     void mouseReleaseEvent(QMouseEvent *);
    129 
    130 private slots:
    131     void on_btnMenu_Close_clicked();
    132 
    133     void on_btnMenu_Max_clicked();
    134 
    135     void on_btnMenu_Min_clicked();
    136 
    137     void on_pushButton_clicked();
    138 
    139     void on_pushButton_2_clicked();
    140 
    141     void on_pushButton_3_clicked();
    142 
    143     int OnBtnOpen();//打开文件
    144 
    145     void OnBtnSave();//保存计算结果
    146 
    147     int OnStart();//有序表--开始计算
    148 
    149     int SqList_disorder_start();//无序表--开始计算
    150 
    151     void textFind(); //查找文本
    152 
    153     void findNext(); //查找下一个
    154 
    155     void createPdf();//打印pdf
    156 
    157     void Dt_createPdf();//线性表打印pdf
    158 
    159     void hash_createPdf();//哈希表打印pdf
    160 
    161     int DtBiao_OnStart();//动态表开始计算按钮
    162 
    163     void clearTbWidget();//清空表格内容
    164 
    165     void Dt_Clear();//动态表表格清空
    166 
    167     void Dt_BtnSave();//动态表保存
    168 
    169     int DtBiao_Onstart_preOrder();//前序遍历
    170 
    171     int DtBiao_Onstart_PostOrder();//后序遍历
    172 
    173     int on_Btn_HASH_start();//HASH表开始计算按钮
    174 
    175     void hash_BtnSave();//HASH表保存
    176 
    177     void hash_Clear();//HASH表内容清空
    178 
    179 
    180 
    181 private:
    182     Ui::frmMain *ui;
    183 
    184     QPoint mousePoint;
    185     bool mousePressed;
    186     bool max;
    187     QRect location;
    188 
    189     void InitStyle();
    190 
    191     QLineEdit *lineEdit;
    192 
    193 };
    194 
    195 #endif // FRMMAIN_H

     

     

    静态表

     

      1 //函数结果状态代码
      2 #define TRUE    1
      3 #define FALSE   0
      4 #define OK      1
      5 #define ERROR   0
      6 #define OVERFLOW -2
      7 
      8 
      9 // 线性表的动态分配顺序存储结构
     10 #define LIST_INIT_SIZE 100  // 线性表存储空间的初始分配量
     11 #define LISTINCREMENT 10    // 线性表存储空间的分配增量
     12 #define HASH_TABLE_LEN  52 // HASH表长
     13 
     14 
     15 const int MAX_CHARACTER = 50;       // 单词最大长度定为50(TUT.txt文中最长单词为production-education-researching)
     16 
     17 //行数结构
     18 typedef struct row_next{
     19     int row;
     20     struct row_next *next;  //指向下一个单词的行数
     21 }row_next;
     22 
     23 // 顺序存储结构
     24 typedef struct
     25 {
     26     char word[MAX_CHARACTER];       // 存储单词,不超过50个字符
     27     int count;          // 单词出现次数
     28     row_next *row_head;            //行数
     29 } ElemType;
     30 typedef struct
     31 {
     32     ElemType *elem;     // 存储空间基址
     33     int length;         // 当前长度
     34     int listsize;       // 当前分配的存储容量(以sizeof(ElemType)为单位)
     35 } SqList;
     36 
     37 
     38 /***************************
     39 
     40   主要功能函数___顺序表的实现
     41 
     42   *************************/
     43 
     44 int frmMain::OnStart()
     45 {
     46 int j=0,pronum=0;
     47 
     48     /*计算所消耗的时间---开始时间*/
     49     DWORDstart,stop,search_began,search_end,search_time=0,Insert_began,Insert_end,Insert_time=0, order_began,order_end,search_all_Time=0,insert_all_Time=0;
     50 
     51     start = GetTickCount();
     52 
     53     FILE *f1;
     54     FILE* fp=fopen("C:\Qt\src\QUI\linshi.txt","wb");
     55 
     56     QString str=ui->plainTextEdit->toPlainText();
     57     fprintf(fp,"%s",str.toStdString().c_str());
     58     fclose(fp);
     59 
     60     SqList L;               // 建立线性表
     61     SqListInit ( &L );          // 初始化顺序表
     62 
     63     char fword[MAX_CHARACTER];    // 使用fword数组保存文件中的单词
     64     fword[MAX_CHARACTER - 1] = '\0';
     65     int i = -1;             // 设置i为插入位置
     66     int row=1;
     67     row_next *row_p;
     68     f1=fopen("QtsrcQUIlinshi.txt","r");
     69 
     70     if(f1==NULL) return 0;
     71 
     72     while ( !feof ( f1 ) )      // 读文件未结束
     73     {
     74         int judge = pickword ( f1, fword ,&row); // 从f指向的文件中提取单词到fword中
     75 
     76         if ( -1 == judge )          // 数组越界时提示并退出
     77         {
     78             printf ( "存在单词字符长度超过数组界限\n" );
     79             return -1;
     80         }
     81 
     82         search_began=GetTickCount();
     83         if ( SqListBSearch ( &L, fword, i ) )   // i返回插入位置或单词在顺序表中位置
     84         {
     85             search_end=GetTickCount();
     86 
     87             if(search_time<(search_end-search_began)){
     88                 search_time=search_end-search_began;
     89 
     90             }
     91 
     92             search_all_Time=search_all_Time+(search_end-search_began);
     93 
     94             //qDebug() << tr("search:%1 ms").arg(search_time);
     95 
     96             // 在顺序表中找到该单词
     97             L.elem[i].count++;          // 单词出现次数加1
     98 
     99             row_p=(row_next *)malloc(sizeof(row_next));
    100             row_p->row=row;
    101             row_p->next=L.elem[i].row_head->next;
    102             L.elem[i].row_head->next=row_p;
    103         }
    104         else
    105         {
    106             Insert_began=GetTickCount();
    107 
    108             // 顺序表中未找到该单词
    109             SqListInsert ( &L, i, fword );      // 在第i个位置上插入
    110             L.elem[i].row_head=(row_next *)malloc(sizeof(row_next));
    111             L.elem[i].row_head->row=row;
    112             L.elem[i].row_head->next=NULL;
    113 
    114             Insert_end=GetTickCount();
    115 
    116             if(Insert_time<Insert_end-Insert_began){
    117                 Insert_time=Insert_end-Insert_began;
    118             }
    119 
    120             insert_all_Time=insert_all_Time+(Insert_end-Insert_began);
    121         }
    122 
    123     }
    124 
    125     /****程序运行结束,计算时间并显示****/
    126     stop = GetTickCount();
    127     //printf("time: %lld ms\n", stop - start);
    128 
    129     QString str1=tr("创建时间: %1 ms").arg(stop - start);
    130     ui->TimeLine->setText(str1);
    131     str1=tr("折半:%1 ms,最长:%2 ms").arg(search_all_Time).arg(search_time);
    132     ui->Sq_search_ltimeline->setText(str1);
    133     str1=tr("插入:%1 ms,最长:%2 ms").arg(insert_all_Time).arg(Insert_time);
    134     ui->Sq_insert_timeline->setText(str1);
    135 
    136 
    137     /*****进度条****/
    138     for(i=0;i<=5;i++){
    139         //ui->progressBar->setValue(pronum);
    140         //Sleep(1);
    141         for(pronum=0;pronum<=100;pronum++){
    142             ui->progressBar->setValue(pronum);
    143             //Sleep(1);
    144         }
    145     }
    146 
    147     //
    148     ui->tableWidget->clearContents();
    149     for(j=ui->tableWidget->rowCount();j>=0;j--){
    150 
    151         ui->tableWidget->removeRow(j);
    152     }
    153 
    154     order_began=GetTickCount();
    155 
    156     // 将结果写入f2指向的文件中
    157     SqListPrint ( &L );
    158 
    159     order_end=GetTickCount();
    160 
    161     str1=tr("遍历时间 : %1 ms").arg(order_end-order_began);
    162     ui->Sq_order_line->setText(str1);
    163 
    164     i=0;
    165     while(i<ui->tableWidget->rowCount()/3){
    166        QComboBox *comBox = new QComboBox();
    167         while(L.elem[i].row_head){
    168             comBox->addItem(tr("%1").arg(L.elem[i].row_head->row));
    169             L.elem[i].row_head=L.elem[i].row_head->next;
    170         }
    171         ui->tableWidget->setCellWidget(i,2,comBox);
    172         i++;
    173     }
    174     free(L.elem);
    175     L.length=0;
    176     L.listsize=0;
    177 
    178 }
    179 
    180 int frmMain::SqList_disorder_start(){
    181 
    182     int j=0,pronum=0;
    183 
    184 
    185     /*计算所消耗的时间---开始时间*/
    186     DWORD start, stop,search_began,search_end,search_time=0,Insert_began,Insert_end,Insert_time=0,
    187             order_began,order_end,search_all_time=0,insert_all_time=0;
    188 
    189     start = GetTickCount();
    190 
    191     FILE *f1;
    192     FILE* fp=fopen("C:\Qt\src\QUI\linshi3.txt","wb");
    193 
    194     QString str=ui->plainTextEdit->toPlainText();
    195     fprintf(fp,"%s",str.toStdString().c_str());
    196     fclose(fp);
    197 
    198     SqList L;               // 建立线性表
    199     SqListInit ( &L );          // 初始化顺序表
    200 
    201     char fword[MAX_CHARACTER];          // 使用fword数组保存文件中的单词
    202     fword[MAX_CHARACTER - 1] = '\0';
    203     int i = -1;             // 设置i为插入位置
    204     int row=1;
    205     row_next *row_p;
    206 
    207     f1=fopen("QtsrcQUIlinshi3.txt","r");
    208 
    209     if(f1==NULL) return 0;
    210 
    211     while ( !feof ( f1 ) )      // 读文件未结束
    212     {
    213         int judge = pickword ( f1, fword ,&row); // 从f指向的文件中提取单词到fword中
    214 
    215         if ( -1 == judge )          // 数组越界时提示并退出
    216         {
    217             printf ( "存在单词字符长度超过数组界限\n" );
    218             return -1;
    219         }
    220 
    221         search_began=GetTickCount();
    222         if ( SqList_search_disorder ( &L, fword, i ) )   // i返回插入位置或单词在顺序表中位置
    223         {
    224             search_end=GetTickCount();
    225 
    226             if(search_time<(search_end-search_began)){
    227                 search_time=search_end-search_began;
    228             }
    229 
    230             search_all_time=search_all_time+(search_end-search_began);
    231 
    232             //qDebug() << tr("search:%1 ms").arg(search_time);
    233 
    234             // 在顺序表中找到该单词
    235             L.elem[i].count++;          // 单词出现次数加1
    236 
    237 //            row_p=L.elem[i].row_head;
    238 //            while(row_p){
    239 //                row_p=row_p->next;
    240 //            }
    241             row_p=(row_next *)malloc(sizeof(row_next));
    242             row_p->row=row;
    243             row_p->next=L.elem[i].row_head->next;
    244             L.elem[i].row_head->next=row_p;
    245         }
    246         else
    247         {
    248             Insert_began=GetTickCount();
    249 
    250             // 顺序表中未找到该单词
    251             SqList_insert_disorder ( &L,fword ,row);      // 插入
    252 
    253             Insert_end=GetTickCount();
    254 
    255             if(Insert_time<Insert_end-Insert_began){
    256                 Insert_time=Insert_end-Insert_began;
    257             }
    258 
    259             insert_all_time=insert_all_time+(Insert_end-Insert_began);
    260         }
    261 
    262     }
    263 
    264     /****程序运行结束,计算时间并显示****/
    265     stop = GetTickCount();
    266 
    267 
    268     QString str1=tr("创建时间: %1 ms").arg(stop - start);
    269     ui->TimeLine->setText(str1);
    270     str1=tr("查找:%1 ms,最长:%2 ms").arg(search_all_time).arg(search_time);
    271     ui->Sq_search_ltimeline->setText(str1);
    272     str1=tr("插入:%1 ms,最长:%2 ms").arg(insert_all_time).arg(Insert_time);
    273     ui->Sq_insert_timeline->setText(str1);
    274 
    275 
    276     /*****进度条****/
    277     for(i=0;i<=5;i++){
    278         //ui->progressBar->setValue(pronum);
    279         //Sleep(1);
    280         for(pronum=0;pronum<=100;pronum++){
    281             ui->progressBar->setValue(pronum);
    282             //Sleep(1);
    283         }
    284     }
    285 
    286     //
    287     ui->tableWidget->clearContents();
    288     for(j=ui->tableWidget->rowCount();j>=0;j--){
    289 
    290         ui->tableWidget->removeRow(j);
    291     }
    292 
    293     order_began=GetTickCount();
    294 
    295     // 将结果
    296     SqListPrint ( &L );
    297 
    298     order_end=GetTickCount();
    299 
    300     str1=tr("遍历时间 : %1 ms").arg(order_end-order_began);
    301     ui->Sq_order_line->setText(str1);
    302 
    303     i=0;
    304     while(i<ui->tableWidget->rowCount()/3){
    305        QComboBox *comBox = new QComboBox();
    306         while(L.elem[i].row_head){
    307             comBox->addItem(tr("%1").arg(L.elem[i].row_head->row));
    308             L.elem[i].row_head=L.elem[i].row_head->next;
    309         }
    310         ui->tableWidget->setCellWidget(i,2,comBox);
    311         i++;
    312     }
    313 
    314     free(L.elem);
    315     L.length=0;
    316     L.listsize=0;
    317 
    318 }
    319 
    320 /*********SqList_search_disorder**********/
    321 
    322 int frmMain::SqList_search_disorder ( SqList *L, char *sword, int &i )
    323 {
    324     if ( L->length == 0 )            // 当顺序表为空时
    325     {
    326         i = 0;                  // i返回单词插入位置
    327         return ERROR;
    328     }
    329 
    330     // 顺序表不空时,在顺序表L中查找元素sword,用i返回其在顺序表中的位置
    331     int low = 0, high = L->length - 1;
    332 
    333     while ( low <= high )
    334     {
    335         if(strcmp ( L->elem[low].word, sword )==0){
    336             i=low;
    337             return OK;
    338         }
    339         else{
    340             low++;
    341         }
    342     }
    343 
    344     return ERROR;           // 顺序表中不存在待查元素,函数返回值为0,i返回单词插入位置
    345 }
    346 
    347 /***********SqList_insert_disorder************/
    348 
    349 // 顺序表的插入
    350 int frmMain::SqList_insert_disorder( SqList *L,char *fword ,int row)
    351 {
    352     // 在顺序线性表L中第i个位置之前插入新的元素e
    353     // i的合法值为1≤i≤L.Length + 1
    354 //    if ( i < 0 || i > L->length )
    355 //    {
    356 //        //printf ( "i的值不合法!" );
    357 //        return ERROR;   // i的值不合法
    358 //    }
    359 
    360     int i=L->length;
    361 
    362     if ( L->length >= L->listsize )
    363     {
    364         // 当前存储空间已满,增加分配
    365         ElemType *newbase = ( ElemType * ) realloc ( L->elem,
    366                             ( L->listsize + LISTINCREMENT ) * sizeof ( ElemType ) );
    367 
    368         if ( !newbase )
    369             return OVERFLOW;    // 存储分配失败
    370 
    371         L->elem = newbase;       // 新基址
    372         L->listsize += LISTINCREMENT;    // 增加存储容量
    373     }
    374 
    375     ElemType *p, *q;
    376     q = &L->elem[i];
    377 
    378     strcpy ( q->word, fword );           // 复制fword中的字符到L->elem[i-1].word中
    379     L->elem[i].count = 1;            // 设置计数初值为1
    380     L->length++;                     // 表长增1
    381 
    382     L->elem[i].row_head=(row_next *)malloc(sizeof(row_next));
    383     L->elem[i].row_head->row=row;
    384     L->elem[i].row_head->next=NULL;
    385 
    386     return OK;
    387 }
    388 
    389 
    390 
    391 
    392 /****将结果显示到界面****/
    393 void frmMain::SqListPrint(SqList *L){
    394     int i=0,j=0;
    395 
    396     row_next *row_p;
    397 
    398     while(i<L->length){
    399 
    400        ui->tableWidget->insertRow(i);
    401        ui->tableWidget->setItem(i,0,new QTableWidgetItem(L->elem[i].word));
    402        ui->tableWidget->setItem(i,1,new QTableWidgetItem(QString("%1").arg(L->elem[i].count)));
    403        //ui->tableWidget->setItem(i,2,new QTableWidgetItem(QString("%1").arg(L->elem[i].row_head->row)));
    404        //ui->tableWidget->update(i,2,new QTableWidgetItem(QString("%1").arg(L->elem[i].row_head->next->row)));
    405 
    406        i++;
    407         }
    408 }
    409 
    410 
    411 // 顺序表的插入
    412 int frmMain::SqListInsert ( SqList *L, int i, char *fword )
    413 {
    414     // 在顺序线性表L中第i个位置之前插入新的元素e
    415     // i的合法值为1≤i≤L.Length + 1
    416     if ( i < 0 || i > L->length )
    417     {
    418         //printf ( "i的值不合法!" );
    419         return ERROR;   // i的值不合法
    420     }
    421 
    422     if ( L->length >= L->listsize )
    423     {
    424         // 当前存储空间已满,增加分配
    425         ElemType *newbase = ( ElemType * ) realloc ( L->elem,
    426                             ( L->listsize + LISTINCREMENT ) * sizeof ( ElemType ) );
    427 
    428         if ( !newbase )
    429             return OVERFLOW;    // 存储分配失败
    430 
    431         L->elem = newbase;       // 新基址
    432         L->listsize += LISTINCREMENT;    // 增加存储容量
    433     }
    434 
    435     ElemType *p, *q;
    436     q = &L->elem[i];
    437 
    438     for ( p = &L->elem[L->length - 1]; p >= q; p-- )   // 插入位置之后元素逐个右移
    439     {
    440         * ( p + 1 ) = *p;
    441     }
    442 
    443     strcpy ( q->word, fword );           // 复制fword中的字符到L->elem[i-1].word中
    444     L->elem[i].count = 1;            // 设置计数初值为1
    445     L->length++;                     // 表长增1
    446     return OK;
    447 }
    448 
    449 
    450 // 顺序表二分法查找
    451 int frmMain::SqListBSearch ( SqList *L, char *sword, int &i )
    452 {
    453     if ( L->length == 0 )            // 当顺序表为空时
    454     {
    455         i = 0;                  // i返回单词插入位置
    456         return ERROR;
    457     }
    458 
    459     // 顺序表不空时,在顺序表L中查找元素sword,用i返回其在顺序表中的位置
    460     int low = 0, high = L->length - 1, mid = L->length;
    461 
    462     while ( low <= high )
    463     {
    464         mid = ( low + high ) / 2;
    465         int k = strcmp ( L->elem[mid].word, sword );
    466 
    467         if ( k == 0 )           // 待查单词sword等于中间值,找到待查元素
    468         {
    469             i = mid;
    470             return OK;          // 查找成功,函数返回值为1,用i返回所查元素在顺序表中的位置
    471         }
    472         else if ( k > 0 )        // 待查单词sword小于中间值,继续在前半区间进行查找
    473         {
    474             high = mid - 1;
    475             i = low;
    476         }
    477         else                // 待查单词sword大于中间值,继续在后半区间进行查找
    478         {
    479             low = mid + 1;
    480             i = high + 1;
    481         }
    482     }
    483 
    484     return ERROR;           // 顺序表中不存在待查元素,函数返回值为0,i返回单词插入位置
    485 }
    486 
    487 int frmMain::pickword ( FILE *f, char *fword , int *row)       // 从f指向的文件中提取单词到fword中
    488 {
    489     char ch;                    // ch储存待检测字符
    490 
    491     for ( int j = 0 , flag = 0 ; !feof ( f ) ; )    // 逐个对字符进行检测,flag用于标记,为0时表示单词中无字母
    492     {
    493         if ( j >= MAX_CHARACTER )            // 判断数组是否越界
    494         {
    495             return -1;
    496         }
    497 
    498         ch = fgetc ( f );              // 获取字符
    499 
    500 
    501         if ( ch >= 'A' && ch <= 'Z' )         // 大写字符转小写保存在fword数组中
    502         {
    503             fword[j++] = ch + 32;
    504             flag = 1;
    505         }
    506 
    507         if ( ( ch >= 'a' && ch <= 'z' ) )     // 小写字符保存在fword数组中
    508         {
    509             fword[j++] = ch;
    510             flag = 1;
    511         }
    512 
    513         if(ch=='\n')
    514         {
    515             (*row)++;
    516             //return 0;
    517         }
    518 
    519         if ( '-' == ch && fword[j - 1] >= 'a' && fword[j - 1] <= 'z' )    // 若单词中带连字符,将连字符保存在fword数组中
    520         {
    521             fword[j++] = ch;
    522         }
    523 
    524 
    525 
    526         if ( ! ( ( ch >= 'A' && ch <= 'Z' ) || ( ch >= 'a' && ch <= 'z' ) || '-' == ch )
    527                 && flag == 1 )              // 过滤单词中的非字母字符
    528         {
    529             if ( fword[j - 1] == '-' )          // 排除类似于 a- 的单词
    530                 fword[j - 1] = '\0';
    531 
    532             fword[j] = '\0';                // fword数组以'\0'结尾
    533             return 0;
    534         }
    535 
    536 
    537     }
    538 }
    539 
    540 
    541 // 顺序表的初始化
    542 int frmMain::SqListInit ( SqList *L )
    543 {
    544     // 构造一个空的顺序表L
    545     L->elem = ( ElemType * ) malloc ( LIST_INIT_SIZE * sizeof ( ElemType ) );
    546 
    547     if ( !L->elem ) return OVERFLOW;     // 存储分配失败
    548 
    549     L->length = 0;
    550     L->listsize = LIST_INIT_SIZE;
    551     return OK;
    552 }

     

     

    搜索二叉树

     

      1 int frmMain::DtBiao_OnStart(){
      2 
      3     DWORD began,end;
      4 
      5     DtList *L;               // 建立线性表
      6     L=(DtList*)malloc(sizeof(DtList));//给头指针分配内存
      7     strcpy(L->elem.word," ");
      8     L->elem.count=0;
      9     L->Lchild=L->Rchild=NULL;//左右孩子初始化
     10 
     11     DtBiao_Creat(&L);        //创建二叉树
     12 
     13     began=GetTickCount();
     14     InOrderTraverse(L);     //中序遍历
     15     end=GetTickCount();
     16 
     17     QString str=tr("中序: %1 ms").arg(end-began);
     18     ui->Dt_order_line->setText(str);
     19 
     20     Dt_Free(&L);            //释放内存
     21 
     22 }
     23 
     24 int frmMain::DtBiao_Onstart_preOrder(){
     25 
     26     DWORD began,end;
     27 
     28     DtList *L;               // 建立线性表
     29     L=(DtList*)malloc(sizeof(DtList));//给头指针分配内存
     30     strcpy(L->elem.word," ");
     31     L->elem.count=0;
     32     L->Lchild=L->Rchild=NULL;//左右孩子初始化
     33 
     34     DtBiao_Creat(&L);           //创建二叉树
     35 
     36     began=GetTickCount();
     37     DtListPrint_preOrder(&L);   //前序遍历
     38     end=GetTickCount();
     39 
     40     QString str1=tr("前序: %1 ms").arg(end-began);
     41     ui->Dt_order_line->setText(str1);
     42 
     43     Dt_Free(&L);        //释放内存
     44 }
     45 
     46 int frmMain::DtBiao_Onstart_PostOrder(){
     47     DWORD began,end;
     48 
     49     DtList *L;               // 建立线性表
     50     L=(DtList*)malloc(sizeof(DtList));//给头指针分配内存
     51     strcpy(L->elem.word," ");
     52     L->elem.count=0;
     53     L->Lchild=L->Rchild=NULL;//左右孩子初始化
     54 
     55     DtBiao_Creat(&L);       //创建二叉树
     56 
     57     began=GetTickCount();
     58     Dt_List_postOrder(L);       //后序遍历
     59     end=GetTickCount();
     60 
     61     QString str1=tr("后序: %1 ms").arg(end-began);
     62     ui->Dt_order_line->setText(str1);
     63 
     64     Dt_Free(&L);    //释放内存
     65 }
     66 
     67 
     68 /*******二叉搜索树创建*********/
     69 int frmMain::DtBiao_Creat(DtList **head){
     70 
     71     DtList *L=*head;
     72 
     73     int j=0,pronum=0,y=0,flag=0;
     74 
     75     /*****tablewidget 表格内容清理******/
     76     ui->DtBiao_tableWidget->clearContents();
     77     for(j=ui->DtBiao_tableWidget->rowCount();j>=0;j--){
     78 
     79         ui->DtBiao_tableWidget->removeRow(j);
     80     }
     81 
     82 
     83     /*****进度条****/
     84     for(y=0;y<=2;y++){
     85         Sleep(1);
     86         for(pronum=0;pronum<=75;pronum++){
     87             ui->progressBar->setValue(pronum);
     88             //Sleep(1);
     89         }
     90     }
     91 
     92 
     93     /*计算所消耗的时间---*/
     94     DWORD   start_create,           /*创建哈希表开始时间*/
     95             stop_create,            /*创建哈希表结束时间*/
     96             search_began_dt,        /*搜索开始时间*/
     97             search_end_dt,          /*搜索结束时间*/
     98             search_time_dt=0,       /*搜索时间*/
     99             Insert_began_dt,        /*插入开始时间*/
    100             Insert_end_dt,          /*插入结束时间*/
    101             Insert_time_dt=0,       /*插入时间*/
    102             search_all_time=0,      /*搜索总时间*/
    103             insert_all_time=0;      /*插入总时间*/
    104 
    105     start_create = GetTickCount();
    106 
    107     FILE *f1;
    108     FILE* fp=fopen("C:\Qt\src\QUI\linshi2.txt","wb");
    109 
    110     QString str=ui->DtBiao_Plaintext->toPlainText();
    111     fprintf(fp,"%s",str.toStdString().c_str());     //把获取的内容写进本地txt文件里面
    112     fclose(fp);
    113 
    114 
    115 
    116     char fword[MAX_CHARACTER];          // 使用fword数组保存文件中的单词
    117     fword[MAX_CHARACTER - 1] = '\0';
    118     DtList *i = NULL;             // 设置i为插入位置
    119     int row=1;
    120     row_next *row_p;
    121 
    122 
    123     f1=fopen("QtsrcQUIlinshi2.txt","r");
    124 
    125     if(f1==NULL) return 0;
    126 
    127     while ( !feof ( f1 ) )      // 读文件未结束
    128     {
    129 
    130         int judge = pickword ( f1, fword ,&row); // 从f指向的文件中提取单词到fword中
    131 
    132         if(flag==0){    //根结点
    133             strcpy(L->elem.word,fword);
    134             L->elem.count=1;
    135             L->elem.row_head=(row_next *)malloc(sizeof(row_next));
    136             L->elem.row_head->row=row%PAGE_LINE;
    137             L->elem.row_head->page=row/PAGE_LINE+1;
    138             L->elem.row_head->next=NULL;
    139             L->elem.row_tail=L->elem.row_head;
    140             flag=1;
    141             continue;
    142         }else{
    143             if ( -1 == judge )          // 数组越界时提示并退出
    144             {
    145                 printf ( "存在单词字符长度超过数组界限\n" );
    146                 return -1;
    147             }
    148 
    149             if( -2 == judge ){
    150                 continue;       //如果是换行符、文件结束符(-1/255)
    151             }
    152 
    153             search_began_dt=GetTickCount();
    154             if ( DtListSearch ( L, fword, &i ) )   // i返回插入位置或单词在线性表中位置
    155             {
    156                 search_end_dt=GetTickCount();
    157 
    158                 if(search_time_dt<(search_end_dt-search_began_dt)){
    159                     search_time_dt=search_end_dt-search_began_dt;      //记录最长时间
    160                 }
    161 
    162                 search_all_time=search_all_time+(search_end_dt-search_began_dt);//记录总搜索时间
    163 
    164                 // 在线性表中找到该单词
    165                 i->elem.count++;          // 单词出现次数加1
    166 
    167                 row_p=(row_next *)malloc(sizeof(row_next));     //为新单词的行数页数分配空间
    168                 row_p->row=row%PAGE_LINE;   //获取当前总行数,并计算赋值
    169                 row_p->page=row/PAGE_LINE+1;//页数
    170                 row_p->next=NULL;
    171                 i->elem.row_tail->next=row_p;//添加到尾指针的next
    172                 i->elem.row_tail=i->elem.row_tail->next;//尾指针指向最后
    173             }
    174             else
    175             {
    176                 Insert_began_dt=GetTickCount();
    177                 // 顺序表中未找到该单词
    178                 DtListInsert ( &L,fword,row );      // 插入
    179 
    180                 Insert_end_dt=GetTickCount();
    181 
    182                 if(Insert_time_dt<(Insert_end_dt-Insert_began_dt)){
    183                     Insert_time_dt=Insert_end_dt-Insert_began_dt;//最长插入时间
    184                 }
    185                 //插入总时间
    186                 insert_all_time=insert_all_time+(Insert_end_dt-Insert_began_dt);
    187             }
    188 
    189         }
    190 
    191     }
    192 
    193     /****程序运行结束,计算时间并显示****/
    194     stop_create = GetTickCount();
    195 
    196     //qDebug() << tr("shijian:%1 ms").arg(stop - start);
    197     QString str1=tr("创建时间:%1 ms").arg(stop_create - start_create);
    198     ui->DtBiao_TimeLine->setText(str1);
    199     str1=tr("搜索:%1 ms,最长:%2 ms").arg(search_all_time).arg(search_time_dt);
    200     ui->Dt_search_ltimeline->setText(str1);
    201     str1=tr("插入:%1 ms,最长:%2 ms").arg(insert_all_time).arg(Insert_time_dt);
    202     ui->Dt_insert_timeline->setText(str1);
    203 
    204 
    205     /*****进度条****/
    206     for(y=0;y<=1;y++){
    207         Sleep(1);
    208         for(pronum=0;pronum<=100;pronum++){
    209             ui->progressBar->setValue(pronum);
    210             //Sleep(1);
    211         }
    212     }
    213 
    214 
    215 }
    216 
    217 
    218 
    219 /**free Destroy***
    220 
    221 使用栈来实现释放二叉搜索树
    222 
    223 *****************/
    224 int frmMain::Dt_Free(DtList **L){
    225     int top = -1;
    226     DtList *stack[1000], *p, *q;
    227     p = *L;
    228     if (p == NULL){
    229             free(*L);
    230             return OK;
    231     }
    232     stack[++top] = *L;
    233     while (top>-1) {
    234             p = stack[top--];
    235             q = p;
    236             if (p->Rchild)  //释放右孩子
    237                     stack[++top] = p->Rchild;
    238             if (p->Lchild)  //是放左孩子
    239                     stack[++top] = p->Lchild;
    240             free(q);    //释放头节点
    241     }
    242 
    243  return OK;
    244 }
    245 
    246 /*******二叉树搜索********/
    247 int frmMain::DtListSearch(DtList *T, char *e,DtList **i){
    248         int top = -1;
    249         DtList *stack[1000], *p;
    250         p = T;
    251         if(strcmp(p->elem.word,e)==0){
    252             *i=p;
    253             return 1;
    254         }
    255         //首元素进栈
    256         stack[++top] = T;
    257         while (top>-1) {
    258                 p = stack[top--];
    259                 if (p->Rchild) {
    260                     if (strcmp(p->Rchild->elem.word,e) == 0){
    261                         *i=p->Rchild;   //如果找到了则返回该结点地址
    262                         return 1;
    263                     }
    264                 stack[++top] = p->Rchild;//不一样则进栈
    265                 }
    266                 if (p->Lchild) {
    267                     if (strcmp(p->Lchild->elem.word,e) == 0){
    268                         *i=p->Lchild;   ////如果找到了则返回该结点地址
    269                         return 1;
    270                     }
    271                 stack[++top] = p->Lchild;//不一样则进栈
    272                 }
    273         }
    274         //free(stack);
    275 return 0;
    276 }
    277 
    278 /********二叉树插入********/
    279 int frmMain::DtListInsert(DtList **L, char *fword,int row){
    280 
    281     DtList *p=*L,*q;
    282 
    283     while(p){       //首先找到插入位置
    284         q=p;
    285         if(strcmp(p->elem.word,fword)<0){
    286 
    287             p=p->Rchild;
    288             continue;
    289         }
    290         if(strcmp(p->elem.word,fword)>0){
    291             p=p->Lchild;
    292             continue;
    293         }
    294         if(strcmp(p->elem.word,fword)==0){
    295             break;
    296         }
    297 
    298     }
    299     if(q->Lchild){      //如果有左孩子,且右孩子为空
    300         if(q->Rchild==NULL){
    301             q->Rchild=(DtList*)malloc(sizeof(DtList));
    302             q->Rchild->Lchild=q->Rchild->Rchild=NULL;
    303             strcpy(q->Rchild->elem.word,fword);
    304             q->Rchild->elem.count=1;
    305 
    306             q->Rchild->elem.row_head=(row_next *)malloc(sizeof(row_next));
    307             q->Rchild->elem.row_head->row=row%PAGE_LINE;
    308             q->Rchild->elem.row_head->page=row/PAGE_LINE+1;
    309             q->Rchild->elem.row_head->next=NULL;
    310             q->Rchild->elem.row_tail=q->Rchild->elem.row_head;
    311             return 1;
    312         }
    313     }
    314     if(q->Rchild){      //如果有右孩子,且左孩子为空
    315         if(q->Lchild==NULL){
    316             q->Lchild=(DtList*)malloc(sizeof(DtList));
    317             q->Lchild->Lchild=q->Lchild->Rchild=NULL;
    318             strcpy(q->Lchild->elem.word,fword);
    319             q->Lchild->elem.count=1;
    320 
    321             q->Lchild->elem.row_head=(row_next *)malloc(sizeof(row_next));
    322             q->Lchild->elem.row_head->row=row%PAGE_LINE;
    323             q->Lchild->elem.row_head->page=row/PAGE_LINE+1;
    324             q->Lchild->elem.row_head->next=NULL;
    325             q->Lchild->elem.row_tail=q->Lchild->elem.row_head;
    326             return 1;
    327         }
    328     }
    329     if(q->Lchild==NULL && q->Rchild==NULL){     //如果是叶子结点
    330 
    331         if(strcmp(q->elem.word,fword)<0){       //插入到左孩子
    332             q->Rchild=(DtList*)malloc(sizeof(DtList));
    333             q->Rchild->Lchild=q->Rchild->Rchild=NULL;
    334             strcpy(q->Rchild->elem.word,fword);
    335             q->Rchild->elem.count=1;
    336 
    337             q->Rchild->elem.row_head=(row_next *)malloc(sizeof(row_next));
    338             q->Rchild->elem.row_head->row=row%PAGE_LINE;
    339             q->Rchild->elem.row_head->page=row/PAGE_LINE+1;
    340             q->Rchild->elem.row_head->next=NULL;
    341             q->Rchild->elem.row_tail=q->Rchild->elem.row_head;
    342             return 1;
    343         }
    344         else{       //插入到右孩子
    345             q->Lchild=(DtList*)malloc(sizeof(DtList));
    346             q->Lchild->Lchild=q->Lchild->Rchild=NULL;
    347             strcpy(q->Lchild->elem.word,fword);
    348             q->Lchild->elem.count=1;
    349 
    350             q->Lchild->elem.row_head=(row_next *)malloc(sizeof(row_next));
    351             q->Lchild->elem.row_head->row=row%PAGE_LINE;
    352             q->Lchild->elem.row_head->page=row/PAGE_LINE+1;
    353             q->Lchild->elem.row_head->next=NULL;
    354             q->Lchild->elem.row_tail=q->Lchild->elem.row_head;
    355             return 1;
    356         }
    357     }
    358 
    359     return 0;
    360 }
    361 
    362 /*********preOrder********/
    363 int frmMain::DtListPrint_preOrder(DtList **Q){
    364     DtList *stack[1000],*p,*L=*Q;
    365     long all_count=0;
    366     int top=-1,i=0,HIGH_LENTH=100,j;
    367     High_count high_word[HIGH_LENTH],*r,*q;     //高频词汇数组
    368 
    369     while(i<HIGH_LENTH){
    370         high_word[i].count=0;       //初始化
    371         i++;
    372     }
    373 
    374     i=0;
    375     p=L;
    376     stack[++top]=L;     //首元素进栈
    377 
    378     while (top>-1) {
    379         p = stack[top--];
    380         ui->DtBiao_tableWidget->insertRow(i);//插入新行
    381         ui->DtBiao_tableWidget->setItem(i,0,new QTableWidgetItem(p->elem.word));
    382         ui->DtBiao_tableWidget->setItem(i,1,new QTableWidgetItem(QString("%1").arg(p->elem.count)));
    383         ui->DtBiao_tableWidget->setItem(i,2,new QTableWidgetItem(QString(" ( %1 , %2 )").arg(p->elem.row_head->row).arg(p->elem.row_head->page)));
    384         all_count+=p->elem.count;//所有单词求和
    385 
    386         //如果当前单词出现次数比高频词汇数组的最后一个元素大,则进行插入
    387         if(p->elem.count>high_word[HIGH_LENTH-1].count){
    388             j=0;
    389             while(j<HIGH_LENTH){
    390                 if(p->elem.count>high_word[j].count){
    391                     q=&high_word[j];
    392                     for ( r = &high_word[HIGH_LENTH-1]; r >= q; r-- )   // 插入位置之后元素逐个右移
    393                     {
    394                         * ( r + 1 ) = *r;
    395                     }
    396                     high_word[j].count=p->elem.count;
    397                     strcpy(high_word[j].word,p->elem.word);
    398                     break;
    399                 }
    400                 j++;
    401             }
    402 
    403         }
    404 //        if(i<100){
    405 //            QComboBox *comBox = new QComboBox();
    406 //            while(p->elem.row_head!=p->elem.row_tail->next){
    407 //                comBox->addItem(tr(" ( %1 , %2 )").arg(p->elem.row_head->row).arg(p->elem.row_head->page));
    408 //                p->elem.row_head=p->elem.row_head->next;
    409 //            }
    410 //            ui->DtBiao_tableWidget->setCellWidget(i,2,comBox);
    411 //        }
    412         i++;
    413         if (p->Rchild)
    414              stack[++top] = p->Rchild;//右孩子进栈
    415         if (p->Lchild)
    416              stack[++top] = p->Lchild;//左孩子进栈
    417     }
    418     ui->DtBiao_tableWidget->setItem(0,5,new QTableWidgetItem(QString("总种类:%1").arg(i)));
    419     ui->DtBiao_tableWidget->setItem(1,5,new QTableWidgetItem(QString("总单词:%1").arg(all_count)));
    420 
    421     i=0;
    422     while(i<HIGH_LENTH){//高频词汇
    423         if(high_word[i].count>1){
    424             ui->DtBiao_tableWidget->setItem(i,3,new QTableWidgetItem(high_word[i].word));
    425             ui->DtBiao_tableWidget->setItem(i,4,new QTableWidgetItem(QString("%1").arg(high_word[i].count)));
    426         }
    427        i++;
    428         }
    429 }
    430 
    431 /**********InOrder**********/
    432 int frmMain::InOrderTraverse(DtList *T){
    433     int i=0;
    434 
    435         if(T!=NULL){
    436                 InOrderTraverse(T->Rchild);
    437                 ui->DtBiao_tableWidget->insertRow(i);
    438                 ui->DtBiao_tableWidget->setItem(i,0,new QTableWidgetItem(T->elem.word));
    439                 ui->DtBiao_tableWidget->setItem(i,1,new QTableWidgetItem(QString("%1").arg(T->elem.count)));
    440                 ui->DtBiao_tableWidget->setItem(i,2,new QTableWidgetItem(QString(" ( %1 , %2 )").arg(T->elem.row_head->row).arg(T->elem.row_head->page)));
    441                 /*
    442                 if(i<500){
    443                     QComboBox *comBox = new QComboBox();
    444                     while(T->elem.row_head){
    445                         comBox->addItem(tr("%1").arg(T->elem.row_head->row));
    446                         T->elem.row_head=T->elem.row_head->next;
    447                     }
    448                     ui->DtBiao_tableWidget->setCellWidget(i,2,comBox);
    449                 }
    450                 */
    451                 InOrderTraverse(T->Lchild);
    452                 return OK;
    453         }
    454         return FALSE;
    455 }
    456 
    457 /************postOrder**************/
    458 int frmMain::Dt_List_postOrder(DtList *T){
    459     int i=0;
    460         if (T != NULL) {
    461                 Dt_List_postOrder(T->Lchild);
    462                 Dt_List_postOrder(T->Rchild);
    463                 ui->DtBiao_tableWidget->insertRow(i);
    464                 ui->DtBiao_tableWidget->setItem(i,0,new QTableWidgetItem(T->elem.word));
    465                 ui->DtBiao_tableWidget->setItem(i,1,new QTableWidgetItem(QString("%1").arg(T->elem.count)));
    466                 ui->DtBiao_tableWidget->setItem(i,2,new QTableWidgetItem(QString(" ( %1 , %2 )").arg(T->elem.row_head->row).arg(T->elem.row_head->page)));
    467 /*
    468                 if(i<500){
    469                     QComboBox *comBox = new QComboBox();
    470                     while(T->elem.row_head){
    471                         comBox->addItem(tr("%1").arg(T->elem.row_head->row));
    472                         T->elem.row_head=T->elem.row_head->next;
    473                     }
    474                     ui->DtBiao_tableWidget->setCellWidget(i,2,comBox);
    475                 }*/
    476                 return OK;
    477         }
    478 return FALSE;
    479 }

     

     

    HASH表

     

      1 /******************************
      2 
      3           HASH表实现
      4 
      5   *******************************/
      6 
      7 
      8 /***哈希表遍历****/
      9 void frmMain::HASH_List_print(Hash_Header *L){
     10 
     11     long all_count=0;
     12     int i=0,j=0,HIGH_LENTH=100,w;
     13     Link_Node *p=NULL;
     14     High_count high_word[HIGH_LENTH],*r,*q;
     15 
     16     while(i<HIGH_LENTH){
     17         high_word[i].count=0;
     18         i++;
     19     }
     20 
     21     for(i=0;i<HASH_TABLE_LEN;i++){
     22         p=L[i].Link_head;//头指针
     23         while(p){/*当p不为空时*/
     24             ui->HASH_tableWidget->insertRow(j);//给表格添加新行
     25             ui->HASH_tableWidget->setItem(j,0,new QTableWidgetItem(p->word));
     26             ui->HASH_tableWidget->setItem(j,1,new QTableWidgetItem(QString("%1").arg(p->count)));
     27             ui->HASH_tableWidget->setItem(j,2,new QTableWidgetItem(QString(" ( %1 , %2 )").arg(p->row_head->row).arg(p->row_head->page)));
     28 
     29             all_count+=p->count;//所有单词求和
     30 
     31             //如果当前单词出现次数比高频词汇数组的最后一个元素大,则进行插入
     32             if(p->count>high_word[HIGH_LENTH-1].count){
     33                 w=0;
     34                 while(w<HIGH_LENTH){
     35                     if(p->count>high_word[w].count){
     36                         q=&high_word[w];
     37                         for ( r = &high_word[HIGH_LENTH-1]; r >= q; r-- )   // 插入位置之后元素逐个右移
     38                         {
     39                             * ( r + 1 ) = *r;
     40                         }
     41                         high_word[w].count=p->count;
     42                         strcpy(high_word[w].word,p->word);
     43                         break;
     44                     }
     45                     w++;
     46                 }
     47             }
     48 
     49 //            if(j<10){
     50 //                QComboBox *comBox = new QComboBox();
     51 //                while(p->row_head!=p->row_tail->next){
     52 //                    comBox->addItem(tr(" ( %1 , %2 )").arg(p->row_head->row).arg(p->row_head->page));
     53 //                    p->row_head=p->row_head->next;
     54 //                }
     55 //                ui->HASH_tableWidget->setCellWidget(j,2,comBox);
     56 //            }
     57 
     58             j++;//给表格添加新行
     59             p=p->next;
     60         }
     61     }
     62 
     63     ui->HASH_tableWidget->setItem(0,5,new QTableWidgetItem(QString("总种类:%1").arg(j)));
     64     ui->HASH_tableWidget->setItem(1,5,new QTableWidgetItem(QString("总单词:%1").arg(all_count)));
     65 
     66     i=0;
     67     while(i<HIGH_LENTH){
     68         if(high_word[i].count>1){
     69             ui->HASH_tableWidget->setItem(i,3,new QTableWidgetItem(high_word[i].word));
     70             ui->HASH_tableWidget->setItem(i,4,new QTableWidgetItem(QString("%1").arg(high_word[i].count)));
     71         }
     72        i++;
     73     }
     74 
     75 
     76 }
     77 
     78 /***计算哈希值***
     79 
     80   取单词的第一、二字符,把他们的ASCLL值求和并对表长取余
     81 
     82 ***************/
     83 int frmMain::HASH_func(char *word){
     84 
     85     int hash=0;
     86 
     87     if(strlen(word)==1){
     88         hash=word[0]%HASH_TABLE_LEN;
     89         return hash;
     90     }else{
     91         hash=(word[0]+word[1])%HASH_TABLE_LEN;
     92         return hash;
     93     }
     94 
     95 return -1;
     96 }
     97 
     98 /***搜索哈希值对应线性表***/
     99 int frmMain::hash_List_Search(Link_Node *L, char *fword, Link_Node **p){
    100 
    101     Link_Node *q=L;
    102 
    103     while(q){
    104         if(strcmp(q->word,fword)==0){
    105             *p=q;
    106             return 1;//如果找到则返回
    107         }
    108         q=q->next;
    109     }
    110 return 0;
    111 }
    112 
    113 /****哈希表插入****
    114 
    115   以后进先出的方式
    116 
    117 ****************/
    118 int frmMain::hash_List_Insert(Link_Node **L, char *fword,int row){
    119 
    120     Link_Node *p=*L,*q;
    121 
    122     if((*L)==NULL){
    123         *L=(Link_Node*)malloc(sizeof(Link_Node));
    124         (*L)->count=1;
    125         (*L)->next=NULL;
    126         strcpy((*L)->word,fword);
    127 
    128         (*L)->row_head=(row_next*)malloc(sizeof(row_next));
    129         (*L)->row_head->row=row%PAGE_LINE;
    130         (*L)->row_head->page=row/PAGE_LINE+1;
    131         (*L)->row_head->next=NULL;
    132         (*L)->row_tail=(*L)->row_head;
    133         return 1;
    134     }else{
    135 
    136         q=(Link_Node*)malloc(sizeof(Link_Node));
    137         q->count=1;
    138 
    139         q->row_head=(row_next*)malloc(sizeof(row_next));
    140         q->row_head->row=row%PAGE_LINE;
    141         q->row_head->page=row/PAGE_LINE+1;
    142         q->row_head->next=NULL;
    143         q->row_tail=q->row_head;
    144 
    145         q->next=(*L)->next;
    146         strcpy(q->word,fword);
    147         (*L)->next=q;
    148         return 1;
    149     }
    150 
    151 return 0;
    152 
    153 }
    154 
    155 int frmMain::on_Btn_HASH_start(){
    156 
    157     /*计算所消耗的时间---*/
    158     DWORD start_create,     /*创建哈希表开始时间*/
    159           stop_create,      /*创建哈希表结束时间*/
    160           search_began_dt,  /*搜索开始时间*/
    161           search_end_dt,    /*搜索结束时间*/
    162           search_time_dt=0, /*搜索时间*/
    163           Insert_began_dt,  /*插入开始时间*/
    164           Insert_end_dt,    /*插入结束时间*/
    165           Insert_time_dt=0, /*插入时间*/
    166           search_all_time=0,/*搜索总时间*/
    167           insert_all_time=0,/*插入总时间*/
    168           order_began_hash, /*遍历开始时间*/
    169           order_end_hash;   /*遍历结束时间*/
    170 
    171     start_create = GetTickCount();//创建哈希表开始计时
    172 
    173 
    174     Hash_Header L[HASH_TABLE_LEN];//哈希表数组声明
    175 
    176     int i,j=0,pronum=0,y=0;
    177 
    178     /*哈希表数组初始化*/
    179     for(i=0;i<HASH_TABLE_LEN;i++){
    180         L[i].Link_head=NULL;
    181     }
    182 
    183     /*清空表格内容*/
    184     ui->HASH_tableWidget->clearContents();
    185     for(j=ui->HASH_tableWidget->rowCount();j>=0;j--){
    186 
    187         ui->HASH_tableWidget->removeRow(j);
    188     }
    189 
    190 
    191     /*****进度条****/
    192     for(y=0;y<=2;y++){
    193         //ui->progressBar->setValue(pronum);
    194         Sleep(1);
    195         for(pronum=0;pronum<=75;pronum++){
    196             ui->progressBar->setValue(pronum);
    197             //Sleep(1);
    198         }
    199     }
    200 
    201 
    202     FILE *f1;
    203     FILE* fp=fopen("C:\Qt\src\QUI\linshi4.txt","wb");
    204 
    205     QString str=ui->HaSH_Plaintext->toPlainText();  //从plaintext中读取用户输入的数据
    206     fprintf(fp,"%s",str.toStdString().c_str());     //把读取到的文本内容临时保存到text文件
    207     fclose(fp); //关闭文件
    208 
    209     char fword[MAX_CHARACTER];          // 使用fword数组保存文件中的单词
    210     fword[MAX_CHARACTER - 1] = '\0';    //字符串数组最后以'\0'结束
    211     Link_Node *p = NULL;             // 设置p为在HASH 表中的位置
    212     int hash_value=-1;              //hash_value 为对应单词哈希值
    213     int row=1;
    214     row_next *row_p;
    215 
    216 
    217     f1=fopen("QtsrcQUIlinshi4.txt","r");
    218 
    219     if(f1==NULL) return 0;
    220 
    221     while ( !feof ( f1 ) )      // 读文件未结束
    222     {
    223 
    224         int judge = pickword ( f1, fword ,&row); // 从f指向的文件中提取单词到fword中
    225 
    226         if ( -1 == judge )          // 数组越界时跳过该单词
    227         {
    228             continue;
    229         }
    230 
    231         if ( -2 == judge ){
    232             continue;
    233         }
    234 
    235         hash_value=HASH_func(fword);   //计算哈希值
    236 
    237         //qDebug() << tr("hash_value:%1 ms").arg(hash_value);
    238 
    239         if(hash_value==-1)      /**无单词***/
    240             return 0;
    241 
    242         search_began_dt=GetTickCount();/*搜索开始计时*/
    243 
    244         if ( hash_List_Search ( L[hash_value].Link_head, fword, &p ) )
    245         {
    246             search_end_dt=GetTickCount();/*搜索结束计时*/
    247 
    248             /*记录最长时间*/
    249             if(search_time_dt<(search_end_dt-search_began_dt)){
    250                 search_time_dt=search_end_dt-search_began_dt;
    251             }
    252             /*记录总时间*/
    253             search_all_time=search_all_time+(search_end_dt-search_began_dt);
    254 
    255             // 在HASH表中找到该单词
    256             p->count++;          // 单词出现次数加1
    257 
    258             row_p=(row_next*)malloc(sizeof(row_next));
    259             row_p->row=row%PAGE_LINE;
    260             row_p->page=row/PAGE_LINE+1;
    261             p->row_tail->next=row_p;
    262             p->row_tail=p->row_tail->next;
    263         }
    264         else
    265         {
    266             /*插入开始计时*/
    267             Insert_began_dt=GetTickCount();
    268 
    269             // HASH表中未找到该单词
    270             hash_List_Insert ( &(L[hash_value].Link_head),fword,row);      // 插入
    271 
    272             /*插入结束计时*/
    273             Insert_end_dt=GetTickCount();
    274 
    275             /*记录最长时间*/
    276             if(Insert_time_dt<(Insert_end_dt-Insert_began_dt)){
    277                 Insert_time_dt=Insert_end_dt-Insert_began_dt;
    278             }
    279 
    280             /*记录总时间*/
    281             insert_all_time=insert_all_time+(Insert_end_dt-Insert_began_dt);
    282         }
    283 
    284     }
    285     fclose(f1);//关闭文件
    286 
    287     order_began_hash=GetTickCount();/*遍历开始计时*/
    288 
    289 //    j=0;
    290 //    for(i=0;i<HASH_TABLE_LEN;i++){
    291 //        p=L[i].Link_head;
    292 //        while(p){
    293 //            ui->HASH_tableWidget->insertRow(j);
    294 //        ui->HASH_tableWidget->setItem(j,0,new QTableWidgetItem(p->word));
    295 //ui->HASH_tableWidget->setItem(j,1,newQTableWidgetItem(QString("%1").arg(p->count)));
    296 //ui->HASH_tableWidget->setItem(j,2,newQTableWidgetItem(QString("( %1 , %2 )").arg(p->row_head->row).arg(p->row_head->page)));
    297 //            j++;
    298 //            p=p->next;
    299 //        }
    300 //    }
    301 
    302     order_end_hash=GetTickCount();/*遍历结束计时*/
    303 
    304 
    305     /*****进度条****/
    306     for(y=0;y<=1;y++){
    307         Sleep(1);
    308         for(pronum=0;pronum<=100;pronum++){
    309             ui->progressBar->setValue(pronum);
    310             //Sleep(1);
    311         }
    312     }
    313 
    314     /****程序运行结束,计算时间并显示****/
    315     stop_create = GetTickCount();
    316     QString str1=tr("创建时间:%1 ms").arg(stop_create - start_create);
    317     ui->HASH_TimeLine->setText(str1);
    318     str1=tr("搜索:%1 ms,最长:%2 ms").arg(search_all_time).arg(search_time_dt);
    319     ui->hash_search_ltimeline->setText(str1);
    320     str1=tr("插入:%1 ms,最长:%2 ms").arg(insert_all_time).arg(Insert_time_dt);
    321     ui->hash_insert_timeline->setText(str1);
    322     str1=tr("遍历时间 : %1 ms").arg(order_end_hash-order_began_hash);
    323     ui->hash_order_line->setText(str1);
    324 
    325     HASH_List_print(L);
    326 /*
    327     j=0;
    328     for(i=0;i<HASH_TABLE_LEN;i++){
    329         p=L[i].Link_head;
    330         while(p){
    331             QComboBox *comBox=new QComboBox;
    332             while(p->row_head){
    333                 comBox->addItem(tr("%1").arg(p->row_head->row));
    334                 p->row_head=p->row_head->next;
    335             }
    336             ui->HASH_tableWidget->setCellWidget(j,2,comBox);
    337             j++;
    338             p=p->next;
    339         }
    340     }
    341 */
    342 }

     

     

    以上是主要的功能源码,整体源码需要的请留言。

    转载于:https://www.cnblogs.com/alimjan/p/9125919.html

    展开全文
  • 数据结构课程设计实验报告 实验一 链表部分 选题为2.4.3城市链表 1 需求分析 1创建一个带有头结点的单链表 2结点中应包含城市名和城市的位置坐标 3对城市链表能够利用城市名和位置坐标进行有关查找插入 删除更新等...
  • 数据结构课程设计实验报告 实验一 链表部分 选题为 2.4.3城市链表 1 需求分析 1 创建一个带有头结点的单链表 2 结点中应包含城市名和城市的位置坐标 3 对城市链表能够利用城市名和位置坐标进行有关查找 插入删除 ...
  • 广工 数据结构 课程设计 完整项目 动态查找表 魔王语言 报告 可执行文件
  • 设计综合运用课本第六章和第九章的平衡二叉树和静态、动态查找表知识,设计程序来实现对平衡二叉树的插入、查找、删除等操作。
  • 利用平衡二叉树实现一个动态查找表。 [基本要求] 实现动态查找表的三种基本功能:查找、插入和删除。 [选做内容] (1) 合并两棵平衡二叉树。 (2) 把一棵平衡二叉树分裂为两棵平衡二叉树,使得在一棵树中的所有关键字...
  • java课程设计

    2011-12-24 22:21:17
    考虑静态方法和动态方法???。如有可能考虑操作符重载。 2. 建立复数有序链表结构的集合 (复数不能重复,按照模的大小排序), 链表的操作有添加,删除,查找。 3. 对上面的复数链表集合, 做一个方法从文本...
  • 利用平衡二叉树实现一个动态查找表。 [基本要求] 实现动态查找表的三种基本功能:查找、插入和删除。 设计内容与步骤 [实现提示] 主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作...
  • 利用平衡二叉树实现一个动态查找表,该动态查找表应至少包括三个功能:对结点的查找、插入和删除。还可有附加功能,如:合并两棵平衡二叉树以及把一棵平衡二叉树分裂为两棵平衡二叉树,使得在一棵树中的所有关键字都...
  • 1, 利用平衡二叉树实现一个动态查找表,实现动态查找表的三种基本功能:查找,插入、删除和附加的两种功能:合并、分裂平衡二叉树。 2, 操作界面要给创建、查找、插入、删除、合并和分裂六种操作供选择。每种操作...
  • 本文实例为大家分享了学生信息管理系统设计的具体代码,供大家参考,具体内容如下 建立一个动态链表,链表中每一结点包括:学号、姓名、性别、年龄、成绩。程序能实现以下功能:  建立链表  显示链表  查找链表中...
  • 课程设计主要用动态链表写成,可以完成学生信息的生成,查找,增加,排名次,删除,保存文件等功能。还加入了创作流程图。
  • 大二的最后一个作业,等明天再过去答辩完后,我的大二也就基本告一段落。这次的课设没有怎么用心,所以也基本就是...(1) 实现动态查找表的三种基本功能:查找,插入和删除; (2) 合并两棵平衡二叉树; (3) ...

    大二的最后一个作业,等明天再过去答辩完后,我的大二也就基本告一段落。这次的课设没有怎么用心,所以也基本就是应付式的完成的,不过其中还是有挺多东西可以学的,因此就趁着刚写完,认真整理一下,方便以后学习。

    接下进入正题

    题目要求

    利用平衡二叉树实现一个动态查找表

    (1)     实现动态查找表的三种基本功能:查找,插入和删除;

    (2)     合并两棵平衡二叉树;

    (3)     把一棵平衡二叉树分裂成两棵平衡二叉树,使得在一棵树中的所有关键字都小于多等于X,另一棵树中的任一关键字都大于X。

    完成说明

    课设是基于c/c++语言编写的,开发平台选择的是vc6.0。(汗,我到现在都还只会用vc,当然也用过TC,不过那个古董级的真心用不惯),另外c语言也没学过界面,所以就只能用dos,凑合着看吧。 

    概要设计

    typedef int Status;

    typedef int ElemType;

    typedef struct BSTNode{

           ElemType data;

           int bf;

           struct BSTNode *lchild ,*rchild;

    } BSTNode,* BSTree;

     

    Status SearchBST(BSTree T,ElemType e)//查找

    void R_Rotate(BSTree &p)//右旋

    void L_Rotate(BSTree &p)//左旋

    void LeftBalance(BSTree &T)//插入平衡调整

    void RightBalance(BSTree &T)//插入平衡调整

    Status InsertAVL(BSTree &T,ElemType e,int &taller)//插入

    void DELeftBalance(BSTree &T)//删除平衡调整

    void DERightBalance(BSTree &T)//删除平衡调整

    Status Delete(BSTree &T,int &shorter)//删除操作

    Status DeleteAVL(BSTree &T,ElemType e,int &shorter)//删除操作

    void merge(BSTree &T1,BSTree &T2)//合并操作

    void splitBSTree(BSTree T,ElemType e,BSTree &T1,BSTree &T2)//分裂操作

    void PrintBSTree(BSTree &T,int lev)//凹入表显示

     

    接下来附上所有源码

    #include<stdio.h>
    #include<stdlib.h>
    //#define TRUE 1
    //#define FALSE 0
    //#define OK 1
    //#define ERROR 0
    #define LH +1
    #define EH 0
    #define RH -1

    typedef int Status;
    typedef int ElemType;
    typedef struct BSTNode{
    ElemType data;
    int bf;
    struct BSTNode *lchild ,*rchild;
    } BSTNode,* BSTree;

     


    /*
    查找算法
    */
    Status SearchBST(BSTree T,ElemType e){
    if(!T){
    return FALSE; //查找失败
    }
    else if(e == T->data ){
    return TRUE; //查找成功
    }
    else if (e < T->data){
    return SearchBST(T->lchild,e);
    }
    else{
    return SearchBST(T->rchild,e);
    }
    }


    //右旋
    void R_Rotate(BSTree &p){
    BSTree lc;
    lc = p->lchild;
    p->lchild = lc->rchild;
    lc->rchild = p;
    p = lc;

    }
    //左旋
    void L_Rotate(BSTree &p){
    BSTree rc;
    rc = p->rchild;
    p->rchild = rc->lchild;
    rc->lchild = p;
    p = rc;
    }

    void LeftBalance(BSTree &T){
    BSTree lc,rd;
    lc=T->lchild;
    switch(lc->bf){
    case LH:
    T->bf = lc->bf=EH;
    R_Rotate(T);
    break;
    case RH:
    rd=lc->rchild;
    switch(rd->bf){
    case LH: T->bf=RH; lc->bf=EH;
    break;
    case EH: T->bf=lc->bf=EH;
    break;
    case RH: T->bf=EH; lc->bf=LH;
    break;
    }
    rd->bf=EH;
    L_Rotate(T->lchild);
    R_Rotate(T);
    }
    }

    void RightBalance(BSTree &T)
    {
    BSTree rc,ld;
    rc=T->rchild;
    switch(rc->bf){
    case RH:
    T->bf= rc->bf=EH;
    L_Rotate(T);
    break;
    case LH:
    ld=rc->lchild;
    switch(ld->bf){
    case LH: T->bf=RH; rc->bf=EH;
    break;
    case EH: T->bf=rc->bf=EH;
    break;
    case RH: T->bf = EH; rc->bf=LH;
    break;
    }
    ld->bf=EH;
    R_Rotate(T->rchild);
    L_Rotate(T);
    }
    }
    //插入结点
    Status InsertAVL(BSTree &T,ElemType e,int &taller){
    if(!T){
    T= (BSTree) malloc (sizeof(BSTNode));
    T->data = e;
    T->lchild = T->rchild = NULL;
    T->bf = EH;
    taller = 1;
    }
    else{
    if(e == T->data){
    taller = 0;
    return ERROR;
    }
    if(e < T->data){
    if(!InsertAVL(T->lchild,e,taller))
    return ERROR;
    if(taller)
    switch(T->bf){
    case LH:
    LeftBalance(T);
    taller = 0;
    break;
    case EH:
    T->bf = LH;
    taller = TRUE;
    break;
    case RH:
    T->bf = EH;
    taller = FALSE;
    break;
    }
    }
    else{
    if (!InsertAVL(T->rchild,e,taller)){
    return ERROR;
    }
    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 1;
    }
    void DELeftBalance(BSTree &T){
    BSTree lc,rd;
    lc=T->lchild;
    switch(lc->bf){
    case LH:
    T->bf = EH;
    //lc->bf= EH;
    R_Rotate(T);
    break;
    case EH:
    T->bf = EH;
    lc->bf= EH;
    R_Rotate(T);
    break;
    case RH:
    rd=lc->rchild;
    switch(rd->bf){
    case LH: T->bf=RH; lc->bf=EH;
    break;
    case EH: T->bf=lc->bf=EH;
    break;
    case RH: T->bf=EH; lc->bf=LH;
    break;
    }
    rd->bf=EH;
    L_Rotate(T->lchild);
    R_Rotate(T);
    }
    }

    void DERightBalance(BSTree &T)
    {
    BSTree rc,ld;
    rc=T->rchild;
    switch(rc->bf){
    case RH:
    T->bf= EH;
    //rc->bf= EH;
    L_Rotate(T);
    break;
    case EH:
    T->bf= EH;
    //rc->bf= EH;
    L_Rotate(T);
    break;
    case LH:
    ld=rc->lchild;
    switch(ld->bf){
    case LH: T->bf=RH; rc->bf=EH;
    break;
    case EH: T->bf=rc->bf=EH;
    break;
    case RH: T->bf = EH; rc->bf=LH;
    break;
    }
    ld->bf=EH;
    R_Rotate(T->rchild);
    L_Rotate(T);
    }
    }

     

    void SDelete(BSTree &T,BSTree &q,BSTree &s,int &shorter){

    if(s->rchild){
    SDelete(T,s,s->rchild,shorter);
    if(shorter)
    switch(s->bf){
    case EH:
    s->bf = LH;
    shorter = 0;
    break;
    case RH:
    s->bf = EH;
    shorter = 1;
    break;
    case LH:
    DELeftBalance(s);
    shorter = 0;
    break;
    }
    return;
    }

    T->data = s->data;
    if(q != T)
    q->rchild = s->lchild;
    else
    q->lchild = s->lchild;
    shorter = 1;

    }
    //删除结点
    Status Delete(BSTree &T,int &shorter){
    BSTree q;
    if(!T->rchild){
    q = T;
    T = T->lchild;
    free(q);
    shorter = 1;
    }
    else if(!T->lchild){
    q = T;
    T= T->rchild;
    free(q);
    shorter = 1;
    }
    else{
    SDelete(T,T,T->lchild,shorter);
    if(shorter)
    switch(T->bf){
    case EH:
    T->bf = RH;
    shorter = 0;
    break;
    case LH:
    T->bf = EH;
    shorter = 1;
    break;
    case RH:
    DERightBalance(T);
    shorter = 0;
    break;
    }
    }
    return TRUE;
    }

    Status DeleteAVL(BSTree &T,ElemType e,int &shorter){
    int sign = 0;
    if (!T){
    return sign;
    }
    else{
    if(e == T->data){
    sign = Delete(T,shorter);
    return sign;
    }

    else if(e < T->data){
    sign = DeleteAVL(T->lchild,e,shorter);
    if(shorter)
    switch(T->bf){
    case EH:
    T->bf = RH;
    shorter = 0;
    break;
    case LH:
    T->bf = EH;
    shorter = 1;
    break;
    case RH:
    DERightBalance(T);
    shorter = 0;
    break;
    }

    return sign;
    }

    else{
    sign = DeleteAVL(T->rchild,e,shorter);
    if(shorter)
    switch(T->bf){
    case EH:
    T->bf = LH;
    shorter = 0;
    break;
    case RH:
    T->bf = EH;
    break;
    case LH:
    DELeftBalance(T);
    shorter = 0;
    break;
    }
    return sign;
    }

    }
    }
    //合并
    void merge(BSTree &T1,BSTree &T2){
    int taller = 0;
    if(!T2)
    return;
    merge(T1,T2->lchild);
    InsertAVL(T1,T2->data,taller);
    merge(T1,T2->rchild);

    }
    void split(BSTree T,ElemType e,BSTree &T1,BSTree &T2){
    int taller = 0;
    if(!T)
    return;
    split(T->lchild,e,T1,T2);
    if(T->data > e)
    InsertAVL(T2,T->data,taller);
    else
    InsertAVL(T1,T->data,taller);
    split(T->rchild,e,T1,T2);

    }
    //分裂
    void splitBSTree(BSTree T,ElemType e,BSTree &T1,BSTree &T2){
    BSTree t1 = NULL,t2 = NULL;
    split(T,e,t1,t2);
    T1 = t1;
    T2 = t2;
    return;
    }

    //构建
    void CreatBSTree(BSTree &T){
    int num,i,e,taller = 0;
    printf("输入结点个数:");
    scanf("%d",&num);
    printf("请顺序输入结点值\n");
    for(i = 0 ;i < num;i++){
    printf("第%d个结点的值",i+1);
    scanf("%d",&e);
    InsertAVL(T,e,taller) ;
    }
    printf("构建成功,输入任意字符返回\n");
    getchar();
    getchar();

    }
    //凹入表形式显示方法
    void PrintBSTree(BSTree &T,int lev){
    int i;
    if(T->rchild)
    PrintBSTree(T->rchild,lev+1);
    for(i = 0;i < lev;i++)
    printf(" ");
    printf("%d\n",T->data);
    if(T->lchild)
    PrintBSTree(T->lchild,lev+1);
    }

     

     

    void Start(BSTree &T1,BSTree &T2){

    int cho,taller,e,k;
    taller = 0;
    k = 0;
    while(1){
    system("cls");
    printf(" 平衡二叉树操作的演示 \n\n");
    printf("******************************************************************************\n");
    printf(" 平衡二叉树显示区 \n");
    printf("T1树\n");
    if(!T1 )
    printf("\n 当前为空树\n");
    else{
    PrintBSTree(T1,1);
    }

    printf("T2树\n");
    if(!T2 )
    printf("\n 当前为空树\n");
    else
    PrintBSTree(T2,1);
    printf("\n******************************************************************************\n");
    printf("T1操作:1.创建 2.插入 3.查找 4.删除 10.分裂\n");
    printf("T2操作:5.创建 6.插入 7.查找 8.删除 11.分裂\n");
    printf(" 9.合并T1,T2 0.退出\n");
    printf("******************************************************************************\n");
    printf("输入你要进行的操作:");
    scanf("%d",&cho);
    switch(cho){
    case 1:
    CreatBSTree(T1);
    break;
    case 2:
    printf("请输入要插入关键字的值");
    scanf("%d",&e);
    InsertAVL(T1,e,taller) ;
    break;
    case 3:
    printf("请输入要查找关键字的值");
    scanf("%d",&e);

    if(SearchBST(T1,e))
    printf("查找成功!\n");
    else
    printf("查找失败!\n");
    printf("按任意键返回87");
    getchar();
    getchar();
    break;
    case 4:
    printf("请输入要删除关键字的值");
    scanf("%d",&e);
    if(DeleteAVL(T1,e,k))
    printf("删除成功!\n");
    else
    printf("删除失败!\n");
    printf("按任意键返回");
    getchar();
    getchar();
    break;
    case 5:
    CreatBSTree(T2);
    break;
    case 6:
    printf("请输入要插入关键字的值");
    scanf("%d",&e);
    InsertAVL(T2,e,taller) ;
    break;
    case 7:
    printf("请输入要查找关键字的值");
    scanf("%d",&e);

    if(SearchBST(T2,e))
    printf("查找成功!\n");
    else
    printf("查找失败!\n");
    printf("按任意键返回");
    getchar();
    getchar();
    break;
    case 8:
    printf("请输入要删除关键字的值");
    scanf("%d",&e);
    if(DeleteAVL(T2,e,k))
    printf("删除成功!\n");
    else
    printf("删除失败!\n");
    printf("按任意键返回");
    getchar();
    getchar();
    break;
    case 9:
    merge(T1,T2);
    T2 = NULL;
    printf("合并成功,按任意键返回");
    getchar();
    getchar();
    break;
    case 10:
    printf("请输入要中间值字的值");
    scanf("%d",&e);
    splitBSTree(T1,e,T1,T2) ;
    printf("分裂成功,按任意键返回");
    getchar();
    getchar();
    break;
    case 11:
    printf("请输入要中间值字的值");
    scanf("%d",&e);
    splitBSTree(T2,e,T1,T2) ;
    printf("分裂成功,按任意键返回");
    getchar();
    getchar();
    break;
    case 0:
    system("cls");
    exit(0);
    }

    }


    }

    void main(){
    BSTree T1 = NULL;
    BSTree T2 = NULL;
    Start(T1,T2);
    }

    最后附上一个运行图吧,创建后的一棵平衡二叉树

     

    转载于:https://www.cnblogs.com/YESheng/p/3169637.html

    展开全文
  • 解码也是利用循环判断结构,读取输入的编码,从第一位开始,如果是零则在他的左孩子中查找,如果是一则在他的右孩子中查找,知道他的左或者右孩子为空时停止,然后再GO TO 到新的编码位置,再次重复操作。...
  • 1、 建立一个动态链表,链表中每一结点包括:学号、姓名、性别、年龄、成绩。程序能实现以下功能:建立链表显示链表查找链表中是否存在某个元素,并显示这个元素的所有信息,若没有这个元素则显示“无此记录!”的...

    1、 建立一个动态链表,链表中每一结点包括:学号、姓名、性别、年龄、成绩。程序能实现以下功能:
         建立链表
         显示链表
         查找链表中是否存在某个元素,并显示这个元素的所有信息,若没有这个元素则显示“无此记录!”的信息。
         删除链表中指定学号的结点。
         在链表中指定的位置插入一个新结点(学号不能和其他结点重复)。
    要求:程序运行中,先显示实现以上功能所构成的菜单,然后根据选项调用相应程序及显示其对应的结果,然后再显示菜单程序,直到按“退出”选项,程序执行结束。

    完整的代码如下:

    #include "stdio.h" #include "stdlib.h" typedef struct student { int id; //学号 char name[20]; //姓名 char sex; //性别(f或m) int age; //年龄 int score; //成绩 struct student *next; }student; student *head=NULL; int length; //链表的长度 void create() { student *p1,*p2; length=0; p1=(student *)malloc(sizeof(student)); p1->id=-1; if(head==NULL) head=p1; printf("请输入学生的学号、姓名、性别、年龄、成绩信息:\n"); while(1) //学号为0的时候退出 { p2=(student *)malloc(sizeof(student)); scanf("%d %s %c %d %d",&p2->id,p2->name,&p2->sex,&p2->age,&p2->score); //输入学生信息 if(p2->id==0) { printf("链表创建完成!\n"); break; } length++; //链表的长度 p1->next=p2; p2->next=NULL; p1=p1->next; } return ; } void display() { student *p=head->next; printf("链表中所有的学生信息如下:\n"); while(p!=NULL) { printf("%d %s %c %d %d\n",p->id,p->name,p->sex,p->age,p->score); p=p->next; } return ; } void search() { int num; student *p=head->next; printf("需要查找的学生学号为:"); scanf("%d",&num); while(p!=NULL) { if(p->id==num) { printf("学号为%d的学生的信息如下:\n",num); printf("%d %s %c %d %d\n",p->id,p->name,p->sex,p->age,p->score); return; } p=p->next; } if(p==NULL) printf("无此记录!\n"); return ; } void insert() { int num,i; student *p,*q; p=head; printf("请输入你要插入位置: "); scanf("%d",&num); if(num>length) { printf("找不到要插入的位置\n"); return ; } else { printf("请输入你要插入的学生的学号、姓名、性别、年龄、成绩信息:\n"); q=(student *)malloc(sizeof(student)); scanf("%d %s %c %d %d",&q->id,q->name,&q->sex,&q->age,&q->score); while(p!=NULL) { if(p->id==q->id) { printf("该学号已经存在,无法插入!\n"); return ; } p=p->next; } p=head; for(i=0;i<num;i++) p=p->next; q->next=p->next; p->next=q; length++; printf("插入成功!\n"); return ; } } void Delete() { int num; student *p,*q; q=head,p=head->next; printf("请输入要删除的学生的学号:\n"); scanf("%d",&num); while(p!=NULL) { if(p->id==num) { q->next=p->next; free(p); length--; printf("删除成功!\n"); return ; } p=p->next; q=q->next; } if(p==NULL) { printf("找不到要删除的编号!\n"); return ; } } void menu() { printf("________________________________________________________________\n"); printf("| 学生信息管理系统 |\n"); printf("| 0、 退出系统 |\n"); printf("| 1、 建立链表 |\n"); printf("| 2、 显示链表 |\n"); printf("| 3、 查找链表中的某个元素 |\n"); printf("| 4、 删除链表中指定学号的结点 |\n"); printf("| 5、 指定的位置上插入一个新结点 |\n"); printf("________________________________________________________________\n"); return ; } int main(void) { int a; menu(); while(1) { printf("请选择相应的功能:"); scanf("%d",&a); switch(a) { case 0: return 0; case 1: create(); menu(); break; case 2: if(head) { display(); menu(); } else { printf("链表为空,请先建立链表!\n"); menu(); } break; case 3: if(head) { search(); menu(); } else { printf("链表为空,请先建立链表!\n"); menu(); } break; case 4: if(head) { Delete(); menu(); } else { printf("链表为空,请先建立链表!\n"); menu(); } break; case 5: if(head) { insert(); menu(); } else { printf("链表为空,请先建立链表!\n"); menu(); } break; default: break; } } system("pause"); return 0; }

    程序说明:加入已经加入了4个学生信息head->liuwei->zhanghua->lina->liuxiang,链表的长度为4,插入的时候,输入4,将会在liuxiang的后面插入一个学生信息;输入1,将会在liuwei的后面插入一个学生信息;

    转载于:https://www.cnblogs.com/newthing/archive/2011/06/26/2157492.html

    展开全文
  • 第九章动态数据结构 C语言程序设计课程组 马迪芳 本章导学 一主要内容 动态数据结构是相对于静态数据结构来讲的它是在程序的执行过程 中动态地建立起来的以致这种数据结构的规模大小可以动态地发 生变化故称为动态...
  • 利用平衡二叉排序树实现一个动态查找表。 要求: (1)随机生成数据,根据随机数据创建平衡的BST (2)以图形方式显示该平衡的BST(注意是图形,不是图像,利用画图函数) (3)实现平衡二叉树的插入、删除、查找...

    1、任务简述:
    利用平衡二叉排序树实现一个动态查找表。
    要求:
    (1)随机生成数据,根据随机数据创建平衡的BST
    (2)以图形方式显示该平衡的BST(注意是图形,不是图像,利用画图函数)
    (3)实现平衡二叉树的插入、删除、查找功能。
    (4)操作方便。

    2、算法描述:
    1.创建BST:对于每一个随机生成的数据,我们用插入来生成BST,即每一次插入后,我们检查相应的平衡因子(左子树高度减去右子树高度),一直检查到0为止,如果出现abs(平衡高度)>=2,那么就进行一次adjust,有四种情况:RR,LL,RL,LR,下面我就这四种方式如何调整来做一个说明:
    ①RR型:新节点插入在A的右子树的右孩子上

    先序遍历结果:
    x A y B z C w

    Adjust:
    B

                                A         C 
    
                            X      y   z      w
    

    ②LL型:新节点插入在A的左子树的左孩子上

    先序遍历结果:
    z C w B y A x

    Adjust:

                                     B
                                C         A 
    
                            z      w   y      x
    

    ③RL型:新节点插入在A的右子树的左孩子上

    先序遍历结果:
    x A z C w B y

    Adjust:

                                     C
                                A         B 
    
                            X      z   w      y
    

    ④LR型:新节点插入在A的左子树的右孩子上

    y B z C w A x
    先序遍历结果:

    Adjust:

                                     C
                                B         A 
    
                            y      z    w     x
    

    2.删除节点:
    删除节点我们可以分成4种情况加以考虑:
    ①删除节点为叶子节点:
    直接删除,然后进行check和adjust。
    ②删除节点只有左孩子:
    将其左孩子直接链接该节点的父节点,然后进行check和adjust。
    ③删除节点只有右孩子:
    将其右孩子直接链接该节点的父节点,然后进行check和adjust。
    ④删除节点即有左孩子也有右孩子:
    找出其左分支最大值,或者右分支最小值,进行替换,然后删除相应的被替换的节点,然后进行check和adjust。

    3.查找节点:
    递归查找就行了,判断当前节点是不是待查数据,是的话就返回该数据,否则就进入左子树和右子树进行查找。

    3、源代码

    #include <iostream>
    #include <sstream>
    #include <math.h>
    #include "graphpainter.h"
    #include "graphpainter.cpp"
    using namespace std;
    
    typedef int number;
    
    char* int2str(int a, char* buff)
    {
    	sprintf(buff, "%d", a);
    	return buff;
    }
    
    class BSTNode
    {
    public:
    	BSTNode(number data=0, int cnt=1):data(data), count(cnt), left(NULL), right(NULL), pa(NULL), ban(0) {};
    	number data; //值
    	int count; //个数
    	BSTNode *left; //左孩子
    	BSTNode *right; //右孩子
    	BSTNode *pa; //父亲
    	int ban; //平衡因子
    	//设置左孩子,并给左孩子的父亲赋值
    	void setleft(BSTNode *p);
    	//设置右孩子,并给右孩子的父亲赋值
    	void setright(BSTNode *p);
    	//连接结点,自动判断左右,要求p一定非空
    	void setchild(BSTNode *p);
    	char* toStr(char* buff);
    	//递归重置一颗子树root上全部结点的平衡因子,返回值为树的高度
    	static int setban(BSTNode *root);
    };
    
    //平衡二叉树类
    class BBST
    {
    public:
    	BSTNode *root; //根节点
    	BBST() :root(NULL) {};
    	void _free(BSTNode *btn)
    	{
    		if (btn->left)
    			_free(btn->left);
    		if (btn->right)
    			_free(btn->right);
    		delete btn;
    	}
    	~BBST()
    	{
    		if (root)
    			_free(root);
    	}
    	/*寻找值为data的结点,如果找到则返回该点地址,否则返回NULL, last为最后搜索地址*/
    	BSTNode* Find(number data, BSTNode **last = NULL);
    	/*新增一个结点*/
    	void Add(number data);
    	/*删除一个结点*/
    	void Del(number data);
    	/*辅助函数:在插入中维护平衡因子,若仍然平衡,返回true;否则返回false,导出a,b,c结点
    	cur为当前出发的结点,a,b,c相连且a->b->c
    	*/
    	bool _checkban(BSTNode* cur, BSTNode **a, BSTNode **b, BSTNode **c);
    	/*辅助函数:在删除中维护平衡因子,若仍然平衡,返回true;否则返回false,导出a,b,c结点
    	cur为要删除的叶子结点,a,b,c相连且a->b->c
    	*/
    	bool _checkban2(BSTNode *cur, BSTNode **a, BSTNode **b, BSTNode **c);
    	BSTNode* _RR(BSTNode *a, BSTNode *b, BSTNode *c);
    	BSTNode* _LL(BSTNode *a, BSTNode *b, BSTNode *c);
    	BSTNode* _RL(BSTNode *a, BSTNode *b, BSTNode *c);
    	BSTNode* _LR(BSTNode *a, BSTNode *b, BSTNode *c);
    	/*辅助函数:调节树,利用中序遍历调节指针,返回中结点*/
    	BSTNode* _adjust(BSTNode *a, BSTNode *b, BSTNode *c);
    	/*用graphpainter库图形显示树*/
    	void show_graph();
    };
    
    void OutMenu() 
    {
    	cout << "\t\t---------------081810221朱林昊---------------\n";
    	cout << "\n\t\t--------------------AVL---------------------\n\n";  //说明该代码的实现功能
    	cout << "\t\t* * * * * * * * * * * * * * * * * * * * * * *\n"; 
    	cout << "\t\t*                                           *\n"; 
    	cout << "\t\t*         AVL菜单                          *\n"; 
    	cout << "\t\t*                                          *\n"; 
    	cout << "\t\t*          1:显示图                        *\n"; 
    	cout << "\t\t*          2:插入节点p                     *\n"; 
    	cout << "\t\t*          3:删除节点p                     *\n"; 
    	cout << "\t\t*          4:从p到p2等差插入节点           *\n"; 
    	cout << "\t\t*          5:从p到p2等差删除节点           *\n";
    	cout << "\t\t*          6:随机插入p个节点               *\n";
    	cout << "\t\t*          7:查找数据p                     *\n"; 
    	cout << "\t\t*          0:退出整个程序                  *\n"; 
    	cout << "\t\t*                                           *\n"; 
    	cout << "\t\t* * * * * * * * * * * * * * * * * * * * * * *\n"; 
    }
    
    int main()
    {
    	BBST BT;
    	char op;
    	number p, p2;
    	system("color 1E");
    	//OutMenu();  
    	while (true)
    	{
    		fflush(stdin);//清除键盘缓冲区 
     		system("cls"); 
     		OutMenu(); 
    		printf("\n");
    		printf("\t\t请您选择:");
     		op=getchar(); 
    		switch(op) 
     		{ 
     		case '1': 
      			BT.show_graph();//显示图 
      			getchar();
      			getchar();
      			break; 
     		case '2': 
     			cout << "\n请输入插入的节点:"; 
      			cin >> p;  //插入节点p 
    			BT.Add(p);
    			cout << "\n插入成功!";
    			getchar();
    			getchar();
      			break; 
     		case '3': 
     			cout << "\n请删除插入的节点:"; 
      			cin >> p; //删除节点p 
    			try
    			{
    				BT.Del(p);
    				cout << "\n删除成功!";
    			}
    			catch (invalid_argument e)
    			{
    				cout << "Can not find " << p << endl;
    			}
    			getchar();
    			getchar();
      			break; 
     		case '4': 
     			cout << "\n请输入插入的等差节点的开头和结尾:";
      			cin >> p >> p2;  //插入p到p2的等差数列 
    			for (number i = p; i <= p2; i++)
    			{
    				BT.Add(i);
    				cout << "\n插入" << i << "成功!";
    			}
    			getchar();
    			getchar();
      			break; 
     		case '5': 
     			cout << "\n请输入删除的等差节点的开头和结尾:";
      			cin >> p >> p2;  //删除p到p2的等差数列 
    			for (number i = p; i <= p2; i++)
    				try
    			{
    				BT.Del(i);
    				cout << "\n删除" << i << "成功!";
    			}
    			catch (invalid_argument e)
    			{
    				cout << "\n没有找到: " << i << endl;
    			}
    			getchar();
    			getchar();
      			break;
      		case '6':
      			cout << "\n请输入随机插入的数据个数:";
    			cin >> p;  //随机插入p个数据 
    			for (int i = 0; i < p; i++)
    			{
    				p2 = round(rand()%p);
    				BT.Add(p2);
    				cout << "随机添加:" << p2 << endl;
    			}
    			getchar();
    			getchar();
      			break;
     		case '7':
     			cout << "\n请输入待查数据:"; 
     			cin >> p; //查找数据p 
    			if (BT.Find(p))
    			{
    				cout << "数字 " << p << " 存在。" << endl;
    			}
    			else
    			{
    				cout << "数字 " << p << " 不存在。" << endl;
    			}
    			getchar();
    			getchar();
     			break;
    		case '0':
      			break; 
     		}
    	}
    	system("pause");
    	return 0;
    }
    
    void BSTNode::setleft(BSTNode *p)
    {
    	left = p;
    	if (p)
    		p->pa = this;
    }
    
    void BSTNode::setright(BSTNode *p)
    {
    	right = p;
    	if (p)
    		p->pa = this;
    }
    
    void BSTNode::setchild(BSTNode *p)
    {
    	if (data < p->data)
    		setright(p);
    	else if (data > p->data)
    		setleft(p);
    	else
    		cout << "ERROR Set Child: p==pa";
    }
    
    char* BSTNode::toStr(char* buff)
    {
    	stringstream str;
    	str.str("");
    	str << "\'";
    	str << data;
    	if (count > 1)
    	{
    		str << "(" << count << ")";
    	}
    	//str << "[" << ban << "]";
    	str << "\'";
    	str >> buff;
    	return buff;
    }
    
    int BSTNode::setban(BSTNode *root)
    {
    	int h1, h2;
    	if (!root)
    		return 0;
    	h1 = setban(root->left);
    	h2 = setban(root->right);
    	root->ban = h1 - h2;
    	return (h1 > h2 ? h1 : h2) + 1;
    }
    
    BSTNode* BBST::Find(number data, BSTNode **last)
    {
    	BSTNode *p = root, *p1 = NULL;
    	while (p)
    	{
    		if (p->data == data)
    			return p;
    		else if (p->data > data)
    		{
    			p1 = p;
    			p = p->left;
    		}
    		else if (p->data < data)
    		{
    			p1 = p;
    			p = p->right;
    		}
    	}
    	if (last)
    		*last = p1;
    	return NULL;
    }
    
    void BBST::Add(number data)
    {
    	BSTNode *p, *p1, *a, *b, *c;
    	p = Find(data, &p1);
    	if (p)
    	{
    		//Condition 1: 已经存在
    		p->count++;
    		return;
    	}
    	if (!p1)
    	{
    		//Condition 2: p为根节点,则新建根节点
    		root = new BSTNode(data);
    	}
    	else
    	{
    		p = new BSTNode(data);
    		p1->setchild(p);
    		if (!_checkban(p, &a, &b, &c))
    			_adjust(a, b, c);
    	}
    
    }
    
    void BBST::Del(number data)
    {
    	BSTNode *p, *p1, *p2, *cur, *a, *b, *c, *m;
    	//搜索
    	p = Find(data);
    	if (!p)
    		throw invalid_argument("Data not found!");
    	//如果能直接减去
    	if (p->count > 1)
    	{
    		p->count--;
    		return;
    	}
    	//只在叶子节点开始删除:用比它稍大的替换
    	p1 = p->right;
    	p2 = p;
    	while (p1)
    	{
    		p2 = p1;
    		p1 = p1->left;
    	}
    	cur = p2;
    	if (cur->right)
    	{
    		//特判:如果cur有一个右孩子,则因为cur没有左孩子,右孩子高度只能为1。
    		//则将右孩子拿上来,高度-1。
    		if (cur->pa)
    			cur->pa->setchild(cur->right);
    		p2 = cur->right;
    	}
    	else if (cur->left)
    	{
    		//特判:如果cur有一个左孩子,同理将左孩子拿上来,高度-1
    		if (cur->pa)
    			cur->pa->setchild(cur->left);
    		p2 = cur->left;
    	}
    	else
    	{
    		//此时cur为叶子结点
    		//特判:如果cur为根
    		if (!cur->pa)
    		{
    			root = NULL;
    			delete cur;
    			return;
    		}
    		else if (cur->data < cur->pa->data)
    			cur->pa->left = NULL;
    		else
    			cur->pa->right = NULL;
    	}
    	//向上调整
    
    	while (!_checkban2(p2, &a, &b, &c))
    	{
    		m = _adjust(a, b, c);
    		if (m == root)
    			break;
    		if (m->ban != 0)
    			//若为0,则高度-1,继续向上搜索
    			break;
    		p2 = m;
    	}
    	if (cur != p)
    	{
    		p->data = cur->data;
    		p->count = cur->count;
    	}
    	delete cur;
    }
    
    bool BBST::_checkban(BSTNode* cur, BSTNode **a, BSTNode **b, BSTNode **c)
    {
    	*b = cur;
    	*a = (*b)->pa; //新插入的b肯定平衡,从父亲开始判断
    	while (*a)
    	{
    		if ((*a)->data < (*b)->data)
    			//b是a的右孩子
    			(*a)->ban--;
    		else
    			(*a)->ban++;
    		if ((*a)->ban == 0)
    			//结论:0平衡因子将不会对上造成影响,不用调节
    			return true;
    		else if ((*a)->ban == 1 || (*a)->ban == -1)
    		{
    			//继续向上回溯
    			*c = *b;
    			*b = *a;
    			*a = (*a)->pa;
    		}
    		else
    			//肯定需要调节
    			return false;
    	}
    	return true;
    }
    
    bool BBST::_checkban2(BSTNode *cur, BSTNode **a, BSTNode **b, BSTNode **c)
    {
    	BSTNode *p = cur, *pp = cur->pa;
    	int oriban; //父亲结点原来的平衡因子
    	while (pp)
    	{
    		oriban = pp->ban;
    		if (p->data < pp->data)
    			//左子树高度-1
    			pp->ban--;
    		else
    			//右子树高度-1
    			pp->ban++;
    		if (oriban == 0)
    		{
    			//父亲结点高度不变,不需处理
    			return true;
    		}
    		else if (pp->ban == 0)
    		{
    			//父亲结点的高度-1,向上传递
    			p = pp;
    			pp = pp->pa;
    		}
    		else
    		{
    			//父亲结点需要进行调整
    			(*a) = pp;
    			if (pp->ban == -2)
    				(*b) = pp->right;
    			else
    				(*b) = pp->left;
    			if ((*b)->ban <= 0)
    				//对于ban==0,则既可以L调整也可以R调整
    				(*c) = (*b)->right;
    			else
    				(*c) = (*b)->left;
    			return false;
    		}
    	}
    	//全部搜索结束,不需调整
    	return true;
    
    }
    
    BSTNode* BBST::_RR(BSTNode *a, BSTNode *b, BSTNode *c)
    {
    	BSTNode *pa; //上面的根节点
    	BSTNode *x, *y, *z, *w;
    	pa = a->pa;
    	x = a->left;
    	y = b->left;
    	z = c->left;
    	w = c->right;
    	a->setright(y);
    	b->setleft(a);
    	return b;
    }
    
    BSTNode* BBST::_LL(BSTNode *a, BSTNode *b, BSTNode *c)
    {
    	BSTNode *pa; //上面的根节点
    	BSTNode *x, *y, *z, *w;
    	pa = a->pa;
    	x = a->right;
    	y = b->right;
    	z = c->left;
    	w = c->right;
    	a->setleft(y);
    	b->setright(a);
    	return b;
    }
    
    BSTNode* BBST::_RL(BSTNode *a, BSTNode *b, BSTNode *c)
    {
    	BSTNode *pa; //上面的根节点
    	BSTNode *x, *y, *z, *w;
    	pa = a->pa;
    	x = a->left;
    	y = b->right;
    	z = c->left;
    	w = c->right;
    	a->setright(z);
    	b->setleft(w);
    	c->setleft(a);
    	c->setright(b);
    	return c;
    }
    
    BSTNode* BBST::_LR(BSTNode *a, BSTNode *b, BSTNode *c)
    {
    	BSTNode *pa; //上面的根节点
    	BSTNode *x, *y, *z, *w;
    	pa = a->pa;
    	x = a->right;
    	y = b->left;
    	z = c->left;
    	w = c->right;
    	b->setright(z);
    	a->setleft(w);
    	c->setleft(b);
    	c->setright(a);
    	return c;
    
    }
    
    BSTNode* BBST::_adjust(BSTNode *a, BSTNode *b, BSTNode *c)
    {
    	BSTNode *m; //中间结点
    	BSTNode *pa = a->pa; //原始根
    	if (a->right == b&&b->right == c)
    		m = _RR(a, b, c);
    	else if (a->left == b&&b->left == c)
    		m = _LL(a, b, c);
    	else if (a->right == b&&b->left == c)
    		m = _RL(a, b, c);
    	else if (a->left == b&&b->right == c)
    		m = _LR(a, b, c);
    	//重置平衡因子
    	BSTNode::setban(m);
    	//修改根
    	if (pa)
    		//存在原根
    		pa->setchild(m);
    	else
    	{
    		//设置新根
    		root = m;
    		m->pa = NULL;
    	}
    	return m;
    }
    void BBST::show_graph()
    {
    	graphpainter GP("graphpainter\\graphpainter.exe");
    	GP.newpainter("bstgraph.txt", BT);
    	GP.setfigure("figsize", "16,8");
    	GP.setlayout("root", "0");
    	if (root == NULL)
    	{
    		GP.setbtnode('L', "0", "\'空\'");
    	}
    	else
    	{
    		//宽搜
    		int head, tail;
    		BSTNode** Q; //搜索队列
    		BSTNode* cur;
    		char buff[255], buff2[255];
    		Q = new BSTNode*[1000];
    		Q[0] = root;
    		GP.setbtnode('L', "0", root->toStr(buff));
    		head = 0;
    		tail = 0;
    		while (head <= tail)
    		{
    			cur = Q[head];
    			//加入自己结点
    			if (cur->left)
    			{
    				Q[++tail] = cur->left;
    				GP.setedge(int2str(head, buff), int2str(tail, buff2));
    				GP.setbtnode('L', int2str(tail, buff), cur->left->toStr(buff2));
    			}
    			if (cur->right)
    			{
    				Q[++tail] = cur->right;
    				GP.setedge(int2str(head, buff), int2str(tail, buff2));
    				GP.setbtnode('R', int2str(tail, buff), cur->right->toStr(buff2));
    			}
    			head++;
    		}
    	}
    	//输出
    	GP.draw();
    	GP.close();
    }//581行 
    

    4、运行结果
    在这里插入图片描述
    随机插入80个节点:
    在这里插入图片描述
    在这里插入图片描述
    显示图:
    在这里插入图片描述
    删除节点28并显示:
    在这里插入图片描述
    在这里插入图片描述
    插入100,并显示:
    在这里插入图片描述
    在这里插入图片描述
    查找数据100和210:
    在这里插入图片描述
    在这里插入图片描述
    5、总结
    性能分析:
    时间复杂度:由于插入,删除,查找的时间复杂度都为O(logn),所以可以认为本程序的时间复杂度为O(logn)。
    空间复杂度:O©。
    遇到的问题与解决方法:
    1.一开始,我删除既有左孩子又有右孩子的节点的方法是,中序遍历,然后再生成新的AVL,这样操作会让代码的时间复杂度变为O(n),空间复杂度变为O(n),因为需要对树进行中序遍历,并且存储在某一个数组里面。但是复习了老师所讲的知识,还是采用了选择左子树或者右子树最值的方法
    2.本题类的操作参考了周易同学,本来我是采用上课讲的二叉树的结构体来写的,但是那样操作过于麻烦,所以在周易同学的帮助下,我采用了类来写,可以在一定程度上减少重复代码的数量。
    心得体会:
    从结果上来看,程序代码是正确的,并且可以很好的执行插入,删除,画图等功能,不过在写删除的时候,需要进行很多次特判,所以代码有些冗长。

    关于本文的画图头文件#include “graphpainter.h”,#include "graphpainter.cpp"需要的可以在评论区留言

    展开全文
  • if(p1==NULL)//全部查找后仍没有则查找失败 { cout查找失败!"; } } 老师说要用数组链表发解决冲突,要有增加,删除,查找的功能,每次准备用类或结构体写,思路总是理不清楚、、、、
  • 此需求规格说明书对《学生信息系统》软件做了全面细致的用户需求分析,明确所要开发的软件应具有的功能、性能与界面,使系统分析人员及软件开发人员能清楚地了解用户的需求,并在此基础上进一步提出概要设计说明书和...
  • 显示对此书已购读者对该书的评价,数据库设有评价,有一个图书ID字段,根据此页显示的图书的ID查找出对应的所有评价及评价此书的顾客相应信息(昵称,评价时间) 3) 相关书籍显示 根据图书所属分类,按点击量显示同类型...
  • 3.MFC_第一个MFC程序设计.mp4 30.MFC_CButton类.mp4 31.MFC_E_FontView-1.mp4 32.MFC_E_FontView-2.mp4 33.MFC_CEdit类.mp4 34.MFC_MyPad.mp4 35.MFC_对话框_静态文本_编辑框.mp4 36.MFC_对话框_访问控件_7...
  • <pre class="ql-syntax" spellcheck="false"><span class="hljs-comment">/////////文件,继承,友元,静态数据成员(没用到),容器类,运算符重载,使用虚函数完成动态多态,模板 <span class="hljs-meta">#...
  • 一种多重链表的建立

    2016-01-09 17:38:41
    分享一个作品,简单介绍一下第一次课程设计中关键部分,一个多重链表的建立,题目是图书管理系统,用到的数据存储方式为动态链表存储,为了实现多种关键字查找的功能,我设计了一种链表的建立方式,如图。...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 192
精华内容 76
关键字:

动态查找表课程设计