基于姓名排序算法动态演示系统的设计与实现说明书

陕西理工学院毕业设计

基于姓名排序算法动态演示系统的设计与实现

[摘要]在有限的资源空间里,为了提高运算处理数据的速率，使用高效算法必不可少。本文以Java作为开发工

具，设计与开发了基于姓名排序算法动态演示系统。该系统实现了插入排序（链表插入排序、直接插入排序、折半插入排序等）、交换排序、选择排序、归并排序、堆排序等算法的动态演示。系统界面美观，操作简单，可作为排序可视化教学演示软件。

[关键词]Java；排序算法；动态演示

陕西理工学院毕业设计

The Design and Implementation of Dynamic Presentation

Systems based on Name Sorting Algorithm

Abstract：In the space limited resources, in order to improve the rate of operation of the data processing, the use of

efficient algorithm is essential. In this paper, Java as a development tool, designed and developed based on the name of sorting algorithm dynamic presentation systems. The system implements insertion sort (list insertion sort, insertion sort, binary insertion sort, etc.), exchange sort, selection sort, merge sort, heap sort, such as dynamic presentations algorithm. System interface is beautiful, simple operation, can be used as sort of teaching visual presentation software.

Key words: Java ; Sorting Algorithm;Dynamic Presentation

陕西理工学院毕业设计

目 录

引言 ...................................................... 1 1系统背景及意义 ........................................... 2

1.1系统背景 ................................................ 2 1.2系统目的及意义 .......................................... 2 1.3开发工具介绍 ............................................ 2

2排序算法 ................................................. 5

2.1直接插入排序 ............................................ 5 2.2折半插入排序 ............................................ 6 2.3快速排序 ................................................ 6 2.4选择排序 ................................................ 8 2.5归并排序 ................................................ 9 2.6链表插入排序 ........................................... 10 2.7堆排序 ................................................. 11 2.8基数排序（MSD） ........................................ 12

3系统设计 ................................................ 14

3.1系统模块结构 ........................................... 14 3.2 模块算法流程图 ......................................... 14

4实现 .................................................... 21

4.1 直接插入排序 ........................................... 21 4.2 折半插入排序 ........................................... 21 4.3选择排序 ............................................... 22 4.4快速排序 ............................................... 22 4.5归并排序 ............................................... 23 4.6链表插入排序 ........................................... 23 4.7堆排序 ................................................. 24 4.8基数排序（MSD） ........................................ 25

5测试 .................................................... 26 总结 ..................................................... 34 致谢 ..................................................... 35 参考文献 ................................................. 36 科技外文文献 ............................................. 37 附录A:基于姓名排序算法动态演示系统的设计与实现源代码 ..... 47 附录B:使用说明书 ......................................... 80

陕西理工学院毕业设计

引言

计算机技术的日益发展，其应用早已不局限于简单的数值运算。涉及到问题的分析、数据结构框架、以及插入、删除、排序查询等复杂的非数值处理和操作。“数据结构”是计算机程序设计的重要基础，也是计算机相关专业的一门重要基础课程和核心课程。其加强对新数据类型的研究和寻找更适用更完善的数据结构类型，也是今后数据结构研究的重要内容.抽象数据结构类型的出现，使

[1]

得在面向对象的语言中,值和变量的类型不再单一，语言中的操作可以作用于多种类型的对象。因此,要建立良好的数据结构，首先对系统按某种原则进行分解，使系统中各模块间独立性强，依赖性小，结构灵活,易于维护。然而，一个良好的分解，要依赖于抽象，只有对系统抽象到一定的程度，才能更好地分解。由于不以记录为基础的递归数据类型的出现，给许多高级应用领域提供了更好地表达复杂数据对象的方法。数据结构从一维二维向三维和多维数据结构的研究意义以及如何实现它

[2]

们等等，都是数据结构今后研究的重要内容。

[1]

数据结构基本元素内容的发展变化，为数据结构的研究开拓了一个新的方向。许多国内外学者都把数据结构的基本元素——数据，进一步扩充为知识,提出了知识的数据结构概念,这样就在更高层次上表示信息的知识代替了明显表示信息逻辑数据，把表示方法更加复杂的知识代替了较为简单的数据,开拓了数据结构研究的新方向.在原有的数据扩展到知识以后，除了基本元素结构表示的不同需要研究以外，更多地应加强对于基本元素间关系和运算以及它们的多种限定性和变化性方面的研究。总之，数据结构由于其基本元素的内容和本质的不断变化，它作为一门学科也要不断变化和适应新的要求。

各个应用领域迫切需要解决的问题，也是当前数据结构基本的研究内容之一在计算机科学与信息融为一体的今天，研究数据结构，既要从计算机技术的发展考虑，也要从信息技术的发展考虑，特别需要重视从理论到实际的转化研究。许多诸如数据工程多媒介数据库和知识工程等等新发展起

[11]

来的学科，也都大量涉及封数据结构的理论和技术, 迫切要求开拓与之对适应的数据结构。对于初学者，它对程序设计思想的建立、提升有着重要的作用，既为后续的计算机课程奠定了一个较为扎实的基础，又可提高分析问题和解决问题的能力，而排序更是“数据结构”里面的核心内容。排序算法的学习就是为以后利用计算机资源高效开发非数值处理的计算机程序打下坚定的理论、方法和技术基础。因此，本文以java为开发语言，设计开发了基于姓名排序算法动态演示系统，有助于初学者的形象直观的学习排序算法。

第 1 页 共 80 页

陕西理工学院毕业设计

1系统背景及意义

1.1系统背景

由于排序在计算机图形、计算机辅助设计、机器人、模式识别、基因排序工程及统计学等领域具有广泛应用，所以对排序的研究既有理论上的重要意义，又有实际应用价值。再加上现在信息产业的迅速发展，信息的流通量越来越大，如此庞大并且杂乱无章的信息数据十分难以管理和查询，就更加需要一种十分快捷而有效的编排手段来整理这些数据信息，让我们的工作效率得以提高[4]。 1.2系统目的及意义

随着计算机技术的发展，各种排序算法不断的被提出。排序算法在计算机科学中有非常重要的地位，且排序在人们的日常生活和学习、科研、生产等各个方面有着重要的应用，因此掌握常用的排序算法是很有必要。在以后的发展中，排序对我们的学习和生活的影响会逐渐增大，因此设计开发一个排序算法动画演示系统，以提高自己对排序算法的掌握程度,并希望该系统有助于初学者直观学习排序算法。此次毕业设计一方面使自己更好的掌握排序的知识，另一方面锻炼一下独立开发系统的能力。

1.3开发工具介绍

(1) Java语言

[8]

Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言，是由Sun Microsystems公司于1995年5月推出的Java程序设计语言和Java平台（即JavaEE, JavaME, JavaSE）的总称。Java自面世后就非常流行，发展迅速，对C++语言形成了有力冲击。Java技术具有卓越的通用性、高效性、平台移植性和安全性，广泛应用于个人PC、数据中心、游戏控制台、科学超级计算机、移动电话和互联网，同时拥有全球最大的开发者专业社群。在全球云计算和移动互联网的产业环境下，Java更具备了显著优势和广阔前景。Java分为三个体系JavaSE（J2SE）（Java2 Platform Standard Edition，java平台标准版），JavaEE(J2EE)(Java 2 Platform,Enterprise Edition，java平台企业版)，JavaME(J2ME)(Java 2 Platform Micro Edition，java平台微型版)。主要特性：

[10]

Java语言是易学的。Java语言的语法与C语言和C++语言很接近，使得大多数程序员很容易学习和使用Java。另一方面，Java丢弃了C++中很少使用的、很难理解的、令人迷惑的那些特性，如操作符重载、多继承、自动的强制类型转换。特别地，Java语言不使用指针，而是引用。并提供了自动的废料收集，使得程序员不必为内存管理而担忧。

[8]

Java语言是强制面向对象的。Java语言提供类、接口和继承等原语，为了简单起见，只支持类之间的单继承，但支持接口之间的多继承，并支持类与接口之间的实现机制（关键字为

[10]

implements）。Java语言全面支持动态绑定，而C++语言只对虚函数使用动态绑定。总之，Java语言是一个纯的面向对象程序设计语言。

[10]

Java语言是分布式的。Java语言支持Internet应用的开发，在基本的Java应用编程接口中有一个网络应用编程接口（java net），它提供了用于网络应用编程的类库，包括URL、URLConnection、Socket、ServerSocket等。Java的RMI（远程方法激活）机制也是开发分布式应用的重要手段。

[10]

Java语言是健壮的。Java的强类型机制、异常处理、垃圾的自动收集等是Java程序健壮性的重要保证。对指针的丢弃是Java的明智选择。Java的安全检查机制使得Java更具健壮性。 Java语言是安全的。Java通常被用在网络环境中，为此，Java提供了一个安全机制以防恶意代码的攻击。除了Java语言具有的许多安全特性以外，Java对通过网络下载的类具有一个安全防范机制（类ClassLoader），如分配不同的名字空间以防替代本地的同名类、字节代码检查，并提供安全管理机制（类SecurityManager）让Java应用设置安全哨兵。

[10]

Java语言是体系结构中立的。Java程序（后缀为java的文件）在Java平台上被编译为体系结构中立的字节码格式（后缀为class的文件），然后可以在实现这个Java平台的任何系统中运行。这种途径适合于异构的网络环境和软件的分发。

[10]

Java语言是可移植的。这种可移植性来源于体系结构中立性，另外，Java还严格规定了各个基本数据类型的长度。Java系统本身也具有很强的可移植性，Java编译器是用Java实现的，Java

第 2 页 共 80 页

陕西理工学院毕业设计

的运行环境是用ANSIC实现的。

[10]

Java语言是解释型的。如前所述，Java程序在Java平台上被编译为字节码格式，然后可以在实现这个Java平台的任何系统中运行。在运行时，Java平台中的Java解释器对这些字节码进行解释执行，执行过程中需要的类在联接阶段被载入到运行环境中。

[10]

Java是性能略高的。与那些解释型的高级脚本语言相比，Java的性能还是较优的。

[10]

Java语言是原生支持多线程的。在Java语言中，线程是一种特殊的对象，它必须由Thread类或其子（孙）类来创建。通常有两种方法来创建线程：其一，使用型构为Thread(Runnable)的构造子将一个实现了Runnable接口的对象包装成一个线程，其二，从Thread类派生出子类并重写run方法，使用该子类创建的对象即为线程。值得注意的是Thread类已经实现了Runnable接口，因此，任何一个线程均有它的run方法，而run方法中包含了线程所要运行的代码。线程的活动由一组方法来控制。Java语言支持多个线程的同时执行，并提供多线程之间的同步机制（关键字为synchronized）。

[10]

Java语言是动态的。Java语言的设计目标之一是适应于动态变化的环境。Java程序需要的类能够动态地被载入到运行环境，也可以通过网络来载入所需要的类。这也有利于软件的升级。另外，Java中的类有一个运行时刻的表示，能进行运行时刻的类型检查。

Java语言的优良特性使得Java应用具有无比的健壮性和可靠性， 这也减少了应用系统的维护费用。Java对对象技术的全面支持和Java平台内嵌的API能缩短应用系统的开发时间并降低成本。Java的编译一次，到处 可运行的特性使得它能够提供一个随处可用的开放结构和在多平台之间传递信息的低成本方式。特别是Java企业应用编程接口（Java Enterprise APIs）为企业计算及电子商务应用系统提供了有关技术和丰富的类库。

(2) JDK运行环境

[8]

JDK(Java Development Kit) 是 Java 语言的软件开发工具包(SDK)。SE(J2SE)，standard edition，标准版，是我们通常用的一个版本，从JDK 5.0开始，改名为Java SE。EE(J2EE)，enterprise edition，企业版，使用这种JDK开发J2EE应用程序，从JDK 5.0开始，改名为Java EE。ME(J2ME)，micro edition，主要用于移动设备、嵌入式设备上的java应用程序，从JDK 5.0开始，改名为Java ME。

没有JDK的话，无法编译Java程序，如果想只运行Java程序，要确保已安装相应的JRE。JDK包含的基本组件包括：

javac – 编译器，将源程序转成字节码。

jar – 打包工具，将相关的类文件打包成一个文件。 javadoc – 文档生成器，从源码注释中提取文档。 jdb – debugger，查错工具。

java – 运行编译后的java程序（.class后缀的）。

appletviewer：小程序浏览器，一种执行HTML文件上的Java小程序的Java浏览器。 Javah：产生可以调用Java过程的C过程，或建立能被Java程序调用的C过程的头文件。 Javap：Java反汇编器，显示编译类文件中的可访问功能和数据，同时显示字节代码含义。 Jconsole: Java进行系统调试和监控的工具。 (3) MyEclipse开发工具

MyEclipse企业级工作平台（MyEclipseEnterprise Workbench ，简称MyEclipse）是对EclipseIDE的扩展，利用它我们可以在数据库和JavaEE的开发、发布以及应用程序服务器的整合方面极大的提高工作效率。它是功能丰富的JavaEE集成开发环境，包括了完备的编码、调试、测试和发布功能，完整支持HTML,Struts,JSP,CSS,Javascript,Spring,SQL,Hibernate。MyEclipse 是一个十分优秀的用于开发Java, J2EE的 Eclipse 插件集合，MyEclipse的功能非常强大，支持也十分广泛，尤其是对各种开源产品的支持十分不错。MyEclipse目前支持Java Servlet,AJAX, JSP, JSF, Struts,Spring, Hibernate,EJB3,JDBC数据库链接工具等多项功能。可以说MyEclipse是几乎囊括了目前所有主流开源产品的专属eclipse开发 工具。根据官方最新消息，MyEclipse 2013

第 3 页 共 80 页

陕西理工学院毕业设计

已经正式发布！MyEclipse 2013[2]支持HTML5、JQuery和主流的Javascript 库。随着MyEclipse 2013支持Html5，你可以添加音频、视频和API元素到你的项目，从而为移动设备创建复杂的Web应用程序。你甚至还可以通过HTML5 可视化设计器设计令人难以置信的用户界面。同时，随着MyEclipse 2013支持JQuery，你可以通过插件提升性能，并添加动画效果到设计中。

第 4 页 共 80 页

陕西理工学院毕业设计

2排序算法

2.1直接插入排序

(1) 基本原理

假设待排序的n个记录{L0，L1，?，Ln}顺序存放在数组中，直接插入法在插入记录Li(i=1，2，?，n-1)时，记录被划分为两个区间[L0,Li-1]和[Li+1,Ln-1],其中，前一个子区间已经排好序，后一个子区间是当前未排序的部分，将关键码Ki与Ki-1Ki-2，?，K0依次比较，找出应该插入的位置，将记录Li插，然后将剩下的i-1个元素按关键词大小依次插入该有序序列，没插入一个元素后依然保持该序列有序，经过i-1趟排序后即成为有序序列。每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止，为了在查找插

[1]

入位置的过程中避免数组下标出界，在l[0]处设置监视哨。排序示例见图2.1。

图2.1 直接插入排序示例

(2) 算法描述

对字符串顺序链表src作直接插入排序,返回值为空。 public void insertSort(String[] src) { for (int i = 2; i < src.length; i++) { if (src[i].compareTo(src[i - 1]) < 0) { src[0] = src[i]; src[i] = src[i - 1]; int j = i - 2; for (; src[0].compareTo(src[j]) < 0; j--) { src[j + 1] = src[j]; } src[j + 1] = src[0]; } } }

(3) 时间复杂度分析

第 5 页 共 80 页

陕西理工学院毕业设计

直接插入排序算法必须进行n-1趟。最好情况下，即初始序列有序，执行n-1趟，但每一趟只比较一次，移动元素两次，总的比较次数是(n-1)，移动元素次数是2(n-1)。因此最好情况下的时间复杂度就是O(n)。最坏情况(非递增)下，最多比较i次，因此需要的比较次数是：所以，时间复

2

杂度为O(n)。 2.2折半插入排序

(1) 基本思想

是对直接插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度[2]。

(2) 算法描述

对字符串顺序链表src作折半插入排序,返回值为空。 public void binaryInsertionSort(String[] src) { for (int i = 2; i < src.length; i++) { // 将src[i]暂存在src[0] src[0] = src[i]; int low = 1, high = i - 1; while (low <= high) { int m = (low + high) / 2; if (src[0].compareTo(src[m]) < 0) {// high = m - 1; } else { low = m + 1; } } // 记录后移 for (int j = i - 1; j >= high + 1; j--) { src[j + 1] = src[j]; } // 插入 src[high + 1] = src[0]; } }

(3)时间空间复杂度

折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n^2)，与直接插入排序算法相同。附加空间O(1); 2.3快速排序

(1) 基本原理

对起泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小则可分别对两部分记录继续进行排序，以达到整个序列有序。假设待排序的序列为{ K.r[s],K.r[s+1],...,K.r[t]},首先任意选取一个记录（通常选第一个）作为支点，然后按下述原则重新排列其余记录：将所有关键字比它小的记录都安置在它的位置之前，将所有关键字较它打的记录都安置在它的位置之后。由此可以将位置i作分界线，将序列{ K.r[s],K.r[s+1],...,K.r[t]}分割成两个子序列{ K.r[s],K.r[s+1],...,K.r[i-1]}和

[11]

{ K.r[i+1],K.r[s+1],...,K.r[t]}。这个过程称一趟快速排序。排序示例见图2.2。

第 6 页 共 80 页

陕西理工学院毕业设计

图2.2 快速排序示例

(2) 算法描述

交换顺序表L中子表l[low...high]的记录，枢轴记录到位，并返回其所在位置，此时在它之前（后）的记录均不大（小）于它。

public int partition(String[] l,int low,int high) { //用字表的第一个记录轴的记录 l[0] = l[low]; //轴记录关键字 String pivotkey = l[low]; //从表的两端交替向中间扫描 while(low < high) { //将比轴记录小的记录移到低端 while(low < high && l[high].compareTo(pivotkey) >= 0) { --high; } //将比轴记录大的记录移到高端 l[low] = l[high]; while(low

第 7 页 共 80 页

陕西理工学院毕业设计

//轴记录到位 l[low] = l[0]; //返回轴的位置 return low; }

(3) 时间复杂度分析

如果每一次分划操作后，左、右两个子序列的长度基本相等，则快速排序的效率最高，其最好情况时间复杂度为O(nlog2n)；反之，如果每次分划操作所产生的两个子序列，其中之一为空序列，

2

此时，快速排序效率最低，其最坏情况时间复杂度为O(n)。如果选择左边第一个元素为主元，则快速排序的最坏情况发生在原始序列正向有序或反向有序时。快速排序的平均情况时间复杂度为O(nlog2n)。 2.4选择排序

(1) 基本原理

待排序的一组数据元素中，选出最小的一个数据元素与第一个位置的数据元素交换；然后在剩下的数据元素当中再找最小的与第二个位置的数据元素交换，循环到只剩下最后一个数据元素为止，

[12]

依次类推直到所有记录。排序示例见图2.3。

图2.3 选择排序示例

(2)算法描述

对字符串顺序链表src作选择排序，返回值为空。 public void selectSort(String[] src){ for (int i = 0; i < src.length; i++) { int j = selectMinKey(src, i); if (j != i) { String temp = src[i]; src[i] = src[j]; src[j] = temp; }}

}

(3)时间复杂度分析

该算法运行时间与元素的初始排列无关。不论初始排列如何，该算法都必须执行n-1趟，每趟执行n-i-1次关键字的比较，这样总的比较次数为：所以，简单选择排序的最好、最坏和平均情况

2

的时间复杂度都为O(n)。

第 8 页 共 80 页

陕西理工学院毕业设计

2.5归并排序

(1) 基本原理

是将两个或两个以上的有序表组合成一个有序的表。利用归并思想实现排序，假设初始序列含有n/2个长度为2或1的有序子列表；再两两归并，......，如此重复直到得到长度为n的有序列表为止；排序示例见图2.4。

图2.4 归并排序示例

(2) 算法描述

将有序顺序链表sr[i...m]和sr[m+1...n]归并为有序的sr[i...n] private void merge(String[] sr,int s,int m,int t){

String[] tmp = new String[t - s +1]; //临时数据存储 int i=s, k = 0,j = m+1; for(;i<=m && j <= t;k++) { if(sr[i].compareTo(sr[j])<0){ tmp[k] = sr[i]; i++; }else { tmp[k] = sr[j]; j++; } }//for end if(i <= m){ //将剩余的sr[i...m]复制到tmp中 for(;i <= m;i++){ tmp[k] = sr[i]; k++; }//for end }//if end if(j <= t){ //将剩余的sr[j...t]复制到tmp中 for(;j <= t;j++){ tmp[k] = sr[j]; k++; }//for end }//if end System.arraycopy(tmp, 0, sr, s, tmp.length); }

(3) 时间复杂度分析

第 9 页 共 80 页

陕西理工学院毕业设计

一趟归并排序的操作是，调用n/2h次算法merge将sr[1...n]中前后相邻且长度为h的有序段进行两两归并得到前后相邻，长度为2h的有序段并存放在Tr[1 ... n]中整个归并排序需进行log2n趟，可见需要和待排序等数量的辅助空间，其时间复杂度为O(nlogn) 2.6链表插入排序

(1) 基本原理

设数组中下标为0的分量为表头结点，并令表头结点记录的关键字取最大整数MAX，则表的插入过程描述如下：首先将静态链表中的数组下标为1的分量和表头结点构成一个循环链表，然后依次将下标为2至n的分量按记录关键字非递减有序插入到循环链表中[1]。排序示例见图2.5。

图2.5 链表插入排序示例

(2) 算法描述

对有序静态链表nodes作链表插入排序，返回值为空。 private void updateNext(Node[] nodes) { for (int i = 2; i < nodes.length; i++) { int q = 0; int p = nodes[0].getNext(); while (nodes[i].getValue().compareTo(nodes[p].getValue()) > 0) { q = p; p = nodes[p].getNext(); } nodes[q].setNext(i); nodes[i].setNext(p); } }

(3) 时间复杂度分析

第 10 页 共 80 页

陕西理工学院毕业设计

和直接插入排序相比，不同之处仅是以修改2n次指针值代替移动记录，排序过程中所需进行的关键字间的比较次数相同，因此，表插入排序的时间复杂度仍是O(n2)； 2.7堆排序

(1) 基本原理

堆含义表明，所有非终点结点的值均不大于（或不小于）其左右孩子结点；若输出堆顶的最小值之后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素中的次小值，如此反复执行，便得到一个有序序列；堆排序解决2个问题：1.如何由一个无序序列建成一个堆；2.如何在输出堆顶之后，调整剩余元素成为一个新的堆；堆调整示例见图2.6。

图2.6 堆调整示例

(2) 算法描述 已知字符串顺序链表num[s...m]中记录的关键字除num[s]之外均满足堆的定义，本函数调整num[s]的关键字，使num[s...m]成为一个大顶堆。

public void adjustHeap(String[] num, int s, int t) { int i = s; for (int j = 2 * i; j <= t; j = 2 * j) { if (j < t && num[j].compareTo(num[j + 1])<0) j = j + 1;// 找出较大者把较大者给num[i] if (num[i].compareTo(num[j])>0) break; String x = num[i]; num[i] = num[j]; num[j] = x; i = j; } }

第 11 页 共 80 页

陕西理工学院毕业设计

(3) 时间复杂度分析

堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。堆排序的最坏时间复杂度为O(nlogn)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是不稳定的，算法时间复杂度O(nlogn)。 2.8基数排序（MSD）

(1) 基本原理

是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法；MSD：先对最主要位关键字K0进行排序，将序列分成若干子序列，每个子序列中的记录都具有相同的K0值，然后分别就每个子序列对关键字K1进行排序，按K1值得不同再分成若干更小的子序列，依次重复直至每个子序列中都有相同的关键字[1]。排序示例见图2.7。

图2.7 MSD排序示例

(2) 算法描述

对字符串顺序链表data每个关键字第power的字符比较排序，返回值为空。 public void msd(String[] data, int power) { String[][] temp = new String[26][data.length]; int[] order = new int[26]; int pos = 0; int k = 0; if (power < 0) return; for (int i = 0; i < data.length; i++) { if (data[i] == null || \ break; if (power < data[i].length()) { pos = (int) data[i].charAt(power) - 97; } else { pos = 0; }

第 12 页 共 80 页

陕西理工学院毕业设计

temp[pos][order[pos]] = data[i]; order[pos]++; } ++power; for (int i = 0; i < 26; i++) { if (order[i] > 1 && power < getStringMaxLength(temp[i])) { path.setHigh(1); msd(temp[i], power);// msd in every sibling bucks } } for (int i = 0; i < 26; i++) { for (int j = 0; j < data.length; j++) { if (temp[i][j] != null) { data[k++] = temp[i][j];// regain the sorted numbers } } } }

(3) 时间复杂度分析

对于n个记录（假设每个记录含d个关键字，每个关键字的取值范围为rd个值），时间复杂度为O(d(n+rd)),其中每一趟分配的时间复杂度为O(n),辅助存储O(rd);

第 13 页 共 80 页

陕西理工学院毕业设计

3系统设计

3.1系统模块结构

根据需求分析，按功能划分8个模块，分别是：链表插入排序模块、直接插入排序模块、折半插入排序模块、选择排序模块、归并排序模块、堆排序模块、基数排序模块。排序算法动态演示系统功能模块结构图如图3.1所示。

排序算法动态演示系统

链 直 折 交 选 归 堆

表 接 半 换 择 并 排

插 插 插 排 排 排 序

入 入 入 序 序 序

排 排 排 序 序 序

图3.1 系统模块结构图

3.2 模块算法流程图

(1) 直接插入排序

直接插入排序算法流程图如图3.2所示。

开始i = 2i

图3.2 直接插入排序算法流程图

第 14 页 共 80 页

基 数 排 序 陕西理工学院毕业设计

(2) 折半插入排序

折半插入排序算法流程图如图3.3所示。

开始初始化Ni

(3) 选择排序

选择排序算法流程图如图3.4所示。

第 15 页 共 80 页

陕西理工学院毕业设计

开始初始化i

(4) 快速排序

快速排序算法流程图如图3.5所示。

第 16 页 共 80 页

陕西理工学院毕业设计

开始初始化low < highYl[0] = l[low];pivotkey = l[low];Nlow < highYlow

(5) 归并排序

归并排序算法流程图如图3.6所示。

第 17 页 共 80 页

陕西理工学院毕业设计

开始初始化Ni<=m&&j<=tYNsr[i]

(6) 堆排序

堆排序算法流程图如图3.7所示。

第 18 页 共 80 页

陕西理工学院毕业设计

开始初始化j0j=2*jYString x = num[i];num[i] = num[j];num[j] = x;i = j;N结束图3.7 堆排序算法流程图

(7) 链表插入排序

链表插入排序算法流程图如图3.8所示。

开始初始化Ni< nodes.lengthYq = 0;p=nodes[0].getNext();Nnodes[i]和nodes[p]比较Yi++q = p;p=nodes[p].getNext();nodes[q].setNext(i);nodes[i].setNext(p);结束图3.8 链表插入排序算法流程图

(8) 基数（MSD）排序

基数（MSD）排序算法流程图如图3.9所示。

第 19 页 共 80 页

陕西理工学院毕业设计

开始初始化power < 0YNi < data.lengthYNpower < data[i].length()Ypos = (int)data[i].charAt(power) - 97;pos = 0;temp[pos][order[pos]] = data[i];order[pos]++;++power;Ni < 26i++YNorder[i]>1&&power

Ni++i++Nj++N

第 20 页 共 80 页

陕西理工学院毕业设计

4实现

4.1 直接插入排序

将字符串数组封装为Vector，同时利用GUI在ContentPanel（中间JPanel）中绘制数据；将SortUtils.copyUnit()切入到排序代码中，完成数组拷贝与赋值。AccessoryPanel（右边JPanel）中加入JList，通过JList.setSelectedIndices(int[] i)完成代码跟随。将MyFactory.getAccessoryPanel().setSelectIndexs(new int[]{});该方法切入到排序代码完成排序算法每一步实现效果。实现代码如下：

public void insertSortToShow(String[] src, int index) { units = DataUtil.getUnitDataForBase(src); MyFactory.getContentPanel().setUnits(units); if (HanziToPinyin.getPingYin(src[index]).compareTo(HanziToPinyin. getPingYin(src[index - 1])) < 0) { src[0] = src[index]; //数组拷贝及代码跟随 src[index] = src[index - 1]; int j = index - 2; for (; HanziToPinyin.getPingYin(src[0]).compareTo(HanziToPinyin. getPingYin(src[j])) < 0; j--) { //找出插入位置 } src[j + 1] = src[0]; //src[0]插入到插入位置 } repaintUnit(500); }

4.2 折半插入排序

将字符串数组封装为Vector，同时利用GUI在ContentPanel（中间JPanel）中绘制数据；将SortUtils.copyUnit()切入到排序代码中，完成数组拷贝与赋值；initUnits(units,low,high)切入到排序代码中完成折半查找过程的绘制。AccessoryPanel（右边JPanel）中加入JList，通过JList.setSelectedIndices(int[] i)完成代码跟随。将MyFactory.getAccessoryPanel().setSelectIndexs(new int[]{});该方法切入到排序代码完成排序算法每一步实现效果。实现代码如下：

public void binaryInsertionSortToShow(String[] src, int index) { units = DataUtil.getUnitDataForBase(src); // 获取显示数据 MyFactory.getContentPanel().setUnits(units); //将src[i]暂存在src[0] src[0] = src[index]; //数组拷贝及代码跟随 int low = 1, high = index - 1; //--代码跟随 MyFactory.getAccessoryPanel().setSelectIndexs(new int[]{2}); // 在src[low...high]中折半查找 SortUtils.refreshUnit(units); // 初始化Units initUnits(units, low, high); // 延迟time后重绘

第 21 页 共 80 页

陕西理工学院毕业设计

repaintUnit(1000); while (low <= high) { ......找出插入位置 } MyFactory.getContentLayoutPanel().repaint(); // 记录后移 for (int j = index - 1; j >= high + 1; j--) { ......记录后移 } ......将src[0]插入到指定位置 }

4.3选择排序

将字符串数组封装为Vector，同时利用GUI在ContentPanel（中间JPanel）中绘制数据；将SortUtils.changeUnit()切入到排序代码中，完成数组拷贝与赋值。AccessoryPanel（右边JPanel）中加入JList，通过JList.setSelectedIndices(int[] i)完成代码跟随。将MyFactory.getAccessoryPanel().setSelectIndexs(new int[]{});该方法切入到排序代码完成排序算法每一步实现效果。实现代码如下：

public void selectSortToShow(String[] src, int index) throws SortPlayingException { units = DataUtil.getUnitDataForBase(src); // 获取显示数据 MyFactory.getContentPanel().setUnits(units); //--代码跟随 MyFactory.getAccessoryPanel().setSelectIndexs(new int[]{1}); int j = selectMinKeyToShow(src, index); if (j != index) { String temp = src[index]; src[index] = src[j]; src[j] = temp; //--代码跟随 MyFactory.getAccessoryPanel().setSelectIndexs(new int[]{3,4,5}); changeUnit(units, index, j); } }

4.4快速排序

将字符串数组封装为Vector，同时利用GUI在ContentPanel（中间JPanel）中绘制数据；将SortUtils.copyUnit()切入到排序代码中，完成数组拷贝与赋值。AccessoryPanel（右边JPanel）中加入JList，通过JList.setSelectedIndices(int[] i)完成代码跟随。将MyFactory.getAccessoryPanel().setSelectIndexs(new int[]{});该方法切入到排序代码完成排序算法每一步实现效果。实现代码如下：

public int partitionToShow(String[] l,int low,int high) { SortUtils.repaintUnit(500); //用字表的第一个记录轴的记录 l[0] = l[low]; //--代码跟随 MyFactory.getAccessoryPanel().setSelectIndexs(new int[]{1}); SortUtils.copyUnit(units,units.get(low),units.get(0)); //显示内存处理

第 22 页 共 80 页

陕西理工学院毕业设计

//轴记录关键字 String pivotkey = l[low]; //--代码跟随 MyFactory.getAccessoryPanel().setSelectIndexs(new int[]{2}); //从表的两端交替向中间扫描 while(low < high) { ......从表的两端交替向中间扫描 } ......将l[0]插入到指定位置 return low; }

4.5归并排序

将字符串数组封装为Vector，同时利用GUI在ContentPanel（中间JPanel）中绘制数据；将movingUnit()完成数组的移动与交换。AccessoryPanel（右边JPanel）中加入JList，通过JList.setSelectedIndices(int[] i)完成代码跟随。将MyFactory.getAccessoryPanel().setSelect- Indexs(new int[]{});该方法切入到排序代码完成排序算法每一步实现效果。实现代码如下：

private void mergeToShow(String[] sr,int s,int m,int t) { String[] tmp = new String[t - s +1]; //临时数据存储 Vector tmpUnits = new Vector(t-s+1); int curx = units.get(s).getPoint().x; int i=s, k = 0,j = m+1; //--代码跟随 MyFactory.getAccessoryPanel().setSelectIndexs(new int[]{2}); for(;i<=m && j <= t;k++) { ......将sr[i...m] 和sr[j...t]归并 }//for end if(i <= m) //将剩余的sr[i...m]复制到tmp中 { ......将剩余的sr[i...m]复制到tmp中 }//if end if(j <= t) //将剩余的sr[j...t]复制到tmp中 { .....将剩余的sr[j...t]复制到tmp中 }//if end System.arraycopy(tmp, 0, sr, s, tmp.length); //--代码跟随 MyFactory.getAccessoryPanel().setSelectIndexs(new int[]{20}); movingUnitList(units,tmpUnits,s,t); }

4.6链表插入排序

将字符串数组封装为LinkData，同时利用GUI在ContentPanel（中间JPanel）中绘制数据。将moveArrows()切入到排序代码中，完成箭头的移动；flashNext()切入到排序代码中完成next索引选择处理效果。AccessoryPanel（右边JPanel）中加入JList，通过JList.setSelectedIndices

第 23 页 共 80 页

陕西理工学院毕业设计

(int[]i)完成代码跟随。将MyFactory.getAccessoryPanel().setSelectIndexs(new int[]{});该方法切入到排序代码完成排序算法每一步实现效果。实现代码如下：

public void updateNextToShow(Node[] nodes, int i, int ibefore) { ......初始化i、q、p while (HanziToPinyin.getPingYin(nodes[i].getValue()).compareTo( HanziToPinyin.getPingYin(nodes[p].getValue())) > 0) { ......找出插入的位置 } //--代码跟随 MyFactory.getAccessoryPanel().setSelectIndexs(new int[]{8}); flashNext(linkData, q); // q next修改 nodes[q].setNext(i); linkData.getNextUnit()[q].setValue(i + \ //--代码跟随 MyFactory.getAccessoryPanel().setSelectIndexs(new int[]{9}); flashNext(linkData, i); // q next修改 nodes[i].setNext(p); linkData.getNextUnit()[i].setValue(p + \ }

4.7堆排序

将字符串数组封装为Vector，同时利用GUI在ContentPanel（中间JPanel）中绘制数据。将SortUtils.changeUnit()切入到排序代码中，完成数组拷贝与赋值。AccessoryPanel（右边JPanel）中加入JList，通过JList.setSelectedIndices(int[] i)完成代码跟随。将MyFactory.getAccessoryPanel().setSelectIndexs(new int[]{});该方法切入到排序代码完成排序算法每一步实现效果。实现代码如下：

public void adjustHeapToShow(String[] num, int s, int t) { ......初始化显示数据 int i = s; for (int j = 2 * i; j <= t; j = 2 * j) { if (j < t && HanziToPinyin.getPingYin(num[j]).compareTo( HanziToPinyin.getPingYin(num[j + 1]))<0) j = j + 1;// 找出较大者把较大者给num[i] if (HanziToPinyin.getPingYin(num[i]).compareTo(HanziToPinyin.getPingYin(num[j]))>0) break; //--代码跟随 MyFactory.getAccessoryPanel().setSelectIndexs(new int[]{7,8,9}); String x = num[i]; num[i] = num[j]; num[j] = x; SortUtils.changeUnit(units, j-1, i-1); i = j; } SortUtils.repaintUnit(0); }

第 24 页 共 80 页

陕西理工学院毕业设计

4.8基数排序（MSD）

将字符串数组封装为RadixData，同时利用GUI在ContentPanel（中间JPanel）中绘制数据。将SortUtils.copyRadixUnit()切入到排序代码中，完成单元到临时数组的拷贝动画。AccessoryPanel（右边JPanel）中加入JList，通过JList.setSelectedIndices(int[] i)完成代码跟随。将MyFactory.getAccessoryPanel().setSelectIndexs(new int[]{});该方法切入到排序代码完成排序算法每一步实现效果。实现代码如下：

public void msdToShow(String[] data, int power, int isGo,int index) { ......初始化显示数据 int pos = 0; if (power < 0) return; for (int i = 0; i < data.length; i++) { if (data[i] == null || \ break; String pyData = HanziToPinyin.getPingYin(data[i]); if (power < pyData.length()) { pos = (int) pyData.charAt(power) - 97; } else { pos = 0; } //--代码跟随 MyFactory.getAccessoryPanel().setSelectIndexs(new int[]{15}); SortUtils.copyRadixUnit(radixData, i, pos, order[pos], 0); temp[pos][order[pos]] = data[i]; radixData.setTempUnits(DataUtil.getUnitRadixTemp(temp)); SortUtils.repaintUnit(30); order[pos]++; //--代码跟随 MyFactory.getAccessoryPanel().setSelectIndexs(new int[]{16}); radixData.setOrder(DataUtil.getUnitOrder(order)); SortUtils.repaintUnit(30); } ++power; if (isGo <= 0) { msdToShowForLast(data, temp,index); } }

第 25 页 共 80 页

陕西理工学院毕业设计

5测试

在Java虚拟机中运行该系统，得到系统运行界面，导入排序数据(周生、丁模、吕学、许要、其勉、龚学、尹要、贺勉、郝生、姜模)，点击直接插入排序按钮，并点击开始按钮，进入直接插入排序过程界面，排序过程界面如图5.1所示，运行结果界面如图5.2所示。

图5.1 直接插入排序过程界面

图5.2 直接排序运行结果

点击折半插入排序按钮，并点击开始按钮，进入折半直接插入排序过程界面如图5.3所示，运行结果界面如图5.4所示。

第 26 页 共 80 页

陕西理工学院毕业设计

图5.3 折半插入排序运行状态

图5.4 折半插入排序运行结果

点击快速排序按钮，并点击开始按钮，进入快速排序过程界面如图5.5所示，运行结果界面如图5.6所示。

第 27 页 共 80 页

陕西理工学院毕业设计

图5.5 快速排序运行状态

图5.6 快速排序运行结果

点击选择排序按钮，并点击开始按钮，进入选择排序过程界面如图5.7所示，运行结果界面如图5.8所示。

第 28 页 共 80 页

陕西理工学院毕业设计

图5.7 选择排序运行状态

图5.8 选择排序运行结果

点击归并排序按钮，并点击开始按钮，进入归并排序过程界面如图5.9所示，运行结果界面如图5.10所示。

第 29 页 共 80 页

陕西理工学院毕业设计

图5.9 归并排序运行状态

图5.10 归并排序运行结果

点击堆排序按钮，并点击开始按钮，进入堆排序过程界面如图5.11所示，运行结果界面如图5.12所示。

第 30 页 共 80 页

陕西理工学院毕业设计

图5.11 堆排序运行状态

图5.12 堆排序运行结果

点击链表插入排序按钮，并点击开始按钮，进入链表插入排序过程界面如图5.13所示，运行结果界面如图5.14所示。

第 31 页 共 80 页

陕西理工学院毕业设计

图5.13 链表排序运行状态

图5.14 链表排序运行结果

点击基数（MSD）排序按钮，并点击开始按钮，进入基数（MSD）排序过程界面如图5.15所示，运行结果界面如图5.16所示。

第 32 页 共 80 页

陕西理工学院毕业设计

These data items can be divided into two types : one called early such as student gender, origin, etc., these data were no longer divided in data processing, the smallest units; Another called portfolio, the performance of students who, it can be divided into mathematics, physics, chemistry and other smaller items. Normally, in addressing the question of the practical application of each student is recorded as a basic unit for a visit and treatment.

Data objects (Data Object) or data element type (Data Element Class) is the nature of the data elements with the same pool. In a specific issue, the data elements have the same nature (not necessarily equal value elements), belonging to the same data objects (data element type), the data element is an example of such data elements. For example, traffic information systems in the transportation network, is a culmination of all the data elements category, peak a and B each represent an urban middle is the data elements of the two types of examples of the value of their data elements a and B respectively.

Data structure (Data Structure) refers to the mutual relationship that exists between one or more data elements together. In any case, between data elements will not be isolated in between them exist in one way or another, such as the relationship between the data element structure. According to the data elements of the relationship between different characteristics, usually have the following four basic categories of the structure :

(1) assembly structures. In the assembly structure, the relationship between data elements is \to the same pool.\

(2) linear structures. The structure of the data elements exist between one-to-one relationship. (3) tree structure. The structure of the data elements exist between hierarchical relationship.

(4) graphics structure. The structure of the data elements of the relationship that existed between Duoduiduo, graphics structure also known as network structure. C++Builder programming experience

1 Database programming

And the use of Delphi, Borland C++Builder BDE (Borland Database Engine) database interface, in particular its use BDE Administrator unified management database alias, the database operation has nothing to do with the location of the database documents, thus enabling database development easier operation. But in a database application procedures at the same time we have to \but as the use of BDE InstallShield, add database alias is likely allocation failure. Therefore, we can use the following methods : still in the design stage procedure using BDE alias management database for debugging, but in procedures substantially (as in the main Chuangti OnCreate event processing function) to Table components DatabaseName attributes, such as the use of similar phrases as follows : Table1->DatabaseName = ExtractFilePath (Application->ExeName); Or Table1->DatabaseName = ExtractFilePath (Application->ExeName+ \

Thus, no impact on the debugging phase, will be issued if the application procedures Table1 document on the use of databases or their current catalogue \catalogue the documents in the form of character string Register (installed in the installation process), then the procedure in the acquisition of substantially from the catalogue of payrolls, Fuzhi DatabaseName attribute to be. Anyway, you do not need to install relatively large BDE forced users.

2 the Registry visit

As in the design process we often required 9x/NT Windows Registry information visit, such as retrieval of information procedures, preservation of information. Register write a subroutine to visit necessary. When the Register to visit, the library will be directly available without always some duplication operation. The following can be used to access cosmetic Licheng, the character string type Jianzhi, and the retrieval of failure to return default value Default.

#include < Registry.hpp >

int ReadIntFromReg(HKEY Root, AnsiString Key, AnsiString KeyName, int Default) { int KeyValue;

TRegistry *Registry = new TRegistry(); Registry->RootKey = Root;

第 38 页 共 80 页

陕西理工学院毕业设计

Registry->OpenKey(Key, false); try {

KeyValue = Registry->ReadInteger(KeyName); } catch(...) {

KeyValue = Default; }

delete Registry; return KeyValue; }

void SaveIntToReg(HKEY Root, AnsiString Key, AnsiString KeyName, int KeyValue) { TRegistry *Registry = new TRegistry(); Registry->RootKey = Root; Registry->OpenKey(Key, true);

Registry->WriteInteger(KeyName, KeyValue); delete Registry; }

char *ReadStringFromReg(HKEY Root, AnsiString Key, AnsiString KeyName, char *Default) { AnsiString KeyValue;

TRegistry *Registry = new TRegistry(); Registry->RootKey = Root; Registry->OpenKey(Key, false); try {

KeyValue = Registry->ReadString(KeyName); } catch(...) {

KeyValue = (AnsiString)Default; }

delete Registry; return KeyValue.c_str(); }

void SaveStringToReg(HKEY Root, AnsiString Key, AnsiString KeyName, char *KeyValue) { TRegistry *Registry = new TRegistry(); Registry->RootKey = Root; Registry->OpenKey(Key, true);

Registry->WriteString(KeyName, (AnsiString)KeyValue); delete Registry; }

We may use the following access methods (to Windows wallpaper documents) : AnsiString WallPaperFileName =

ReadStringFromReg(HKEY_CURRENT_USER, \

3 show / hide icons task column

第 39 页 共 80 页

陕西理工学院毕业设计

Standard Windows applications generally operating in the mission mandate column on the chart shows, users can directly use the mouse clicking column logo for the mission task cut over, but some applications do not use task column signs, such as the typical Office tools, There are also procedures that can be shown or hidden customization tasks column icon, such as Winamp. We can do the procedure, as long as access Windows SetWindowLong function can drive, as follows :

// hidden task column chart :

SetWindowLong (Application->Handle. GWL_EXSTYLE, WS_EX_TOOLWINDOW); // task column shows signs :

SetWindowLong (Application->Handle. GWL_EXSTYLE, WS_EX_APPWINDOW);

4 the establishment of a simple \

A complete Windows applications typically contain a \dialog box as usual \super links. If only show simple version information,

Windows ShellAbout function shelf items have sufficient, following this line of code can be \Windows standard \

ShellAbout (Handle, ( \ ( \夏登城 版权所有！\ Application->Icon->Handle);

5 the two methods to choice catalogue

In our applications, allowing users to choose the regular catalogue, such as software manufacturers, users choose catalogue. This involves catalogue option, we may use the following methods for users to choose one of the catalogue :

(1)use SHBrowseForFolder and SHGetPathFromIDList function; Company affirms its function as follows : WINSHELLAPI LPITEMIDLIST WINAPI SHBrowseForFolder(LPBROWSEINFO lpbi); WINSHELLAPI BOOL WINAPI SHGetPathFromIDList(LPCITEMIDLIST pidl, LPSTR pszPath); LPBROWSEINFO和LPITEMIDLIST structure refer Win32 files. This method of selecting catalogues available Windows desktop all available inventory, including networks of other computers sharing catalogue neighbors, but not the new catalogue. Li Cheng allows users to choose the following directory, the directory of choice Licheng return at all trails character string.

#include < shlobj.h >

char *GetDir(char *DisplayName, HWND Owner) { char dir[MAX_PATH] = \

BROWSEINFO *bi = new BROWSEINFO; bi->hwndOwner = Owner; bi->pidlRoot = NULL; bi->pszDisplayName = NULL; bi->lpszTitle = DisplayName;

bi->ulFlags = BIF_RETURNONLYFSDIRS; bi->lpfn = NULL; bi->lParam = NULL; bi->iImage = 0;

ITEMIDLIST *il = SHBrowseForFolder(bi); if(il!=NULL) {

SHGetPathFromIDList(il, dir); } delete bi; return dir; }

第 40 页 共 80 页

陕西理工学院毕业设计

We can use the following list to be chosen from :

AnsiString at Dir = (AnsiString) GetDir ( \

(2) the use of SelectDirectory function. C++Builder the function SelectDirectory achievable catalogue of options, which showed that similar \/ \Duihuakuang, but its advantage is to use / non-use keyboard input catalogue members, and allow the creation of new directories. Its original definition as follows :

Extern package bool __fastcall SelectDirectory ( AnsiString &Directory, TSelectDirOpts Options, 103-116 HelpCtx); Licheng SelectDir allow you to choose the following directory : #include < FileCtrl.hpp >

AnsiString SelectDir(AnsiString Dir) { if(SelectDirectory(Dir, TSelectDirOpts()

<< sdAllowCreate << sdPerformCreate << sdPrompt,0)) return Dir; else return \}

for the following redeployed to the users choice catalogue : AnsiString SelectedDir = SelectDir ( \

第 41 页 共 80 页

陕西理工学院毕业设计

数据结构

计算机编程数据结构的设计，它是计算机学科的不仅是核心课程，而且已成为一种流行的选修课程等理工专业，所以学好这门课程是计算机密切相关的重要理论基础。 1 数据结构的概念

计算机数据结构是科学和技术专业课程的基础，是必不可少的核心课程。所有的计算机系统软件和应用软件的使用不同类型的数据结构。因此，如果我们要更好地利用计算机解决实际问题，只懂几种计算机编程语言是难以应付很多复杂的问题。为了有效地使用电脑，充分发挥电脑的性能，还必须学习和掌握数据结构的相关知识。 “数据结构”为学习其他计算机专业课程，如操作系统，编译原理，数据库管理系统，软件工程，人工智能等的坚实基础。 2 为什么应该从数据结构的学习？

在计算机发展初期，利用计算机设计的主要处理有条目的。当我们使用计算机来解决一个特定的问题，通过几个步骤以下的一般需求：第一是适当的抽象数学模型一个特定的问题，然后设计或选择算法的数学模型，最后进行程序调试，测试，直到他们有最终的答案。

此后，对象是整数，实型，布尔型，能量的主要设计者的程序是专注于编程技巧，而不重视的数据结构。随着计算机应用与软件和硬件开发的扩展，这方面的问题越来越重要。据统计，现在处理不占用超过90 ％的加工时间的问题。这些问题涉及到更复杂的数据结构，一般的数据元素之间的关系，不能用数学式说明。因此，关键是解决此类问题不再是数学分析和计算，而是要设计出合适的数据结构，可以有效地解决这个问题。

这种非数学模型的术语描述的不是一个数学公式，如表，树，地图数据结构。因此，可以说，数据结构课程设计主要研究了非数值计算的程序，作为一个计算机操作和对象以及它们之间的关系的问题。

本此研究的目的是了解数据的标识对象与该主题涉及的电脑实际问题的计算机处理的结构和处理。与此同时，通过算法，以提高学生能力，旨在促进学生技能的综合应用和业务素质的程序思维能力。 3 概念和术语

知识在数据结构系统的研究之前，一些基本概念和术语给出一个确切的含义。数据（Data ）是信息载体，它可以是计算机识别，存储和处理。它是计算机处理各种数据处理的应用程序的原材料。计算机科学，计算机处理的是数据对象，它可以是数字数据，可以是非数值数据。数据可以是整数、实际或是复数，主要用于工程计算，科学计算和商业性加工;非数字数据，包括字符，文字，图形，图像，声音等。

数据元素（Data Element）是数据的基本单位。在不同的条件下，数据元素可以被称为元素、节点。例如，学生信息检索系统表信息，创历史新高，八皇后问题的状态树，示教编程的问题，如一个高峰，被称为一个数据元素。有时候，从众多数据元素（数据项）数据，例如，学生信息管理系统学生每个数据元素表是一个学生记录。它包括学生的学号，姓名，性别，民族，出生日期，性能数据项。这些数据项可以被分为两种类型：条目 ;另一种叫做组合，这些数据是在数据处理的最小单元，不再划分为数学，物理，化学等小物品。通常情况下，在处理每个学生的实际应用中的问题被记录为访问和处理的基本单元。

数据对象（Data Object）或数据元素类型（数据元素类）是数据元素具有相同的性质。在一个特定的问题，该数据元素具有相同的性质（不一定相等值的元素），属于同一数据对象（数据元素类型），数据元素是这样的数据元素的示例。例如，在交通网络的交通信息系统，是所有数据元素种类，A和B中的顶点各自代表一个城市中间的是两种类型的数据元素，实例的数据元素分别是A和B的值。

数据结构（Data Structure）指的是一个或多个数据元素一起之间存在的相互关系。在任何情

第 42 页 共 80 页

陕西理工学院毕业设计

况下，数据元素之间不会被隔离在它们之间以某种方式，如数据元素结构之间的关系是存在的。根据不同的特性之间的关系的数据元素，通常具有该结构的下列四个基本类别： (1) 装配结构。在装配结构，数据元素之间的关系是“属于同一个池”，要素的关系是一个非常松散的结构。

(2) 线性结构。数据元素的结构之间1对1的关系。 (3) 树形结构。数据元素的结构之间的分层关系存在。

(4) graphics结构。 Duoduiduo ，图形结构也被称为网络结构之间存在的关系的数据元素的结构。

C + + Builder编程经验 1 数据库编程

使用Delphi ， Borland的C + + Builder中的BDE （ Borland数据库引擎）数据库接口，尤其是使用它的BDE管理员统一管理数据库别名，与数据库文件的位置、数据库操作无关，，从而使数据库开发操作更简便。但在同一时间一个数据库应用程序，我们要“释放” BDE ，数据库对于一些简单的程序可能BDE比我们自己设计的程序很大，但由于采用BDE的InstallShield ，添加数据库别名可能分配失败。因此，我们可以用下面的方法：依然在使用BDE别名管理数据库进行调试设计阶段的程序，但在程序基本上（在主要Chuangti OnCreate事件处理函数）来表元件资料库名称属性，如使用类似短语如下：表1 - >数据库名= ExtractFilePath （应用程序 - > EXENAME ） ，或表1 - >数据库名= ExtractFilePath （应用程序 - > EXENAME + “DB” ） ; 因此，在调试阶段没有影响，会使用的数据库或自己的当前目录的“DB ”的应用程序目录文档，数据库的程序都可以正常运行。你甚至可以将数据库目录文件中的字符串寄存器（安装在安装过程中）的形式，那么在收购实质上从就业的目录的程序，符纸资料库名称属性是。无论如何，你不需要安装比较大的BDE强迫用户。 2 注册表访问

由于在设计过程中，我们经常需要9x/NT的Windows注册表信息访问，如检索信息的程序，保存的信息。寄存器写一个子程序来访问必要的。下面可以cosmetic 类型Licheng，字符串类型Jianzhi，和失败返回默认值Default.。

#include < Registry.hpp >

int ReadIntFromReg(HKEY Root, AnsiString Key, AnsiString KeyName, int Default) { int KeyValue;

TRegistry *Registry = new TRegistry(); Registry->RootKey = Root; Registry->OpenKey(Key, false); try {

KeyValue = Registry->ReadInteger(KeyName); }

catch(...) {

KeyValue = Default; }

delete Registry; return KeyValue; }

void SaveIntToReg(HKEY Root, AnsiString Key, AnsiString KeyName, int KeyValue) {

第 43 页 共 80 页

陕西理工学院毕业设计

TRegistry *Registry = new TRegistry(); Registry->RootKey = Root; Registry->OpenKey(Key, true);

Registry->WriteInteger(KeyName, KeyValue); delete Registry; }

char *ReadStringFromReg(HKEY Root, AnsiString Key, AnsiString KeyName, char *Default) { AnsiString KeyValue;

TRegistry *Registry = new TRegistry(); Registry->RootKey = Root; Registry->OpenKey(Key, false); try {

KeyValue = Registry->ReadString(KeyName); }

catch(...) {

KeyValue = (AnsiString)Default; }

delete Registry;

return KeyValue.c_str(); }

void SaveStringToReg(HKEY Root, AnsiString Key, AnsiString KeyName, char *KeyValue) { TRegistry *Registry = new TRegistry(); Registry->RootKey = Root; Registry->OpenKey(Key, true);

Registry->WriteString(KeyName, (AnsiString)KeyValue); delete Registry; }

我们可以使用下面的访问方法（为Windows墙纸文件）： ReadStringFromReg(HKEY_CURRENT_USER, \3 显示/隐藏图标，任务栏

标准的Windows应用程序通常如上图所示，运行在任务的任务栏中，用户可以直接用鼠标单击，任务切换，但有些应用程序不使用任务栏的迹象，如典型的Office工具，有程序还可以显示或隐藏自定义任务栏图标，如Winamp的。我们可以做的程序，只要获得的Windows SetWindowLong函数功能可以驱动，如下所示：

// hidden task column chart :

SetWindowLong (Application->Handle.

GWL_EXSTYLE, WS_EX_TOOLWINDOW); // task column shows signs :

SetWindowLong (Application->Handle. GWL_EXSTYLE, WS_EX_APPWINDOW); 4 关于窗口中建立一个简单的on

一个完整的Windows应用程序通常包含一个“关于”窗口的版本信息。我们的窗口自定义对话

第 44 页 共 80 页

陕西理工学院毕业设计

框像往常一样的自由定制窗口，显示更多的信息，甚至包括超级链接。如果只显示简单的文本信息， 窗口ShellAbout功能架子项目有足够的，下面这行代码可以是“on”Duihuakuang，是“对”Duihuakuang和程序Windows标准可能会显示迹象，如资源利用和系统。

ShellAbout (Handle, ( \+Application->Title+ \C_str () ( \+Application->Title+ \夏登城 版权所有！\ Application->Icon->Handle); 5 两种方法来选择目录

在我们的应用程序，允许用户选择正规的目录，如软件制造商，用户选择目录。这涉及到目录选项，我们可以使用用户下面的方法来选择目录中的一个：

(1) 使用的SHBrowseForFolder和SHGetPathFromIDList功能;公司确认其功能如下： WINSHELLAPI LPITEMIDLIST WINAPI的SHBrowseForFolder（LPBROWSEINFO LPBI）; WINSHELLAPI BOOL WINAPI SHGetPathFromIDList（LPCITEMIDLIST PIDL，LPSTR pszPath）; LPBROWSEINFO和LPITEMIDLIST结构指的Win32文件。选择目录可用的Windows桌面所有可用的库存，包括其他计算机共享目录的邻居的网络，而不是新目录的这个方法。Licheng允许用户选择下面的目录，选择Licheng的目录中返回的所有路径字符串。

#include < shlobj.h >

char *GetDir(char *DisplayName, HWND Owner) { char dir[MAX_PATH] = \

BROWSEINFO *bi = new BROWSEINFO; bi->hwndOwner = Owner; bi->pidlRoot = NULL;

bi->pszDisplayName = NULL; bi->lpszTitle = DisplayName;

Bi->ulFlags = BIF_RETURNONLYFSDIRS; bi->lpfn = NULL; bi->lParam = NULL; bi->iImage = 0;

ITEMIDLIST *il = SHBrowseForFolder(bi); if(il!=NULL) {

SHGetPathFromIDList(il, dir); }

delete bi; return dir; }

我们可以用下面的列表从选择：

AnsiString at Dir = (AnsiString) GetDir ( \(2) 使用SelectDirectory功能。 C ++ BUILDER的选项功能SelectDirectory实现的目录，这表明，类似的“打开”/“保存”Duihuakuang，但其优势是使用/不使用键盘输入目录的成员，并允许创建新的目录。其最初的定义如下：

Extern package bool __fastcall SelectDirectory ( AnsiString &Directory, TSelectDirOpts Options, 103-116 HelpCtx);

Licheng SelectDir允许您选择以下目录： #include < FileCtrl.hpp >

AnsiString SelectDir(AnsiString Dir) { if(SelectDirectory(Dir, TSelectDirOpts()

<< sdAllowCreate << sdPerformCreate << sdPrompt,0))

第 45 页 共 80 页

陕西理工学院毕业设计

return Dir; else

return \}

for the following redeployed to the users choice catalogue : AnsiString SelectedDir = SelectDir ( \

第 46 页 共 80 页

陕西理工学院毕业设计

附录A:基于姓名排序算法动态演示系统的设计与实现源代码

public class HeapSort { public HeapSort() { paths = new Vector(); state = new SortWorkingState(true); } //调整堆为显示 public void adjustHeapToShow(String[] num, int s, int t) { //--代码跟随 MyFactory.getAccessoryPanel().setSelectIndexs(new int[]{0}); SortUtils.repaintUnit(100); units = DataUtil.getUnitDataForHeap(num);

MyFactory.getContentPanel().setUnits(units); int i = s; for (int j = 2 * i; j <= t; j = 2 * j) { if (j < t && HanziToPinyin.getPingYin(num[j]).compareTo(HanziToPinyin. getPingYin(num[j + 1]))<0) j = j + 1;// 找出较大者把较大者给num[i] if (HanziToPinyin.getPingYin(num[i]).compareTo(HanziToPinyin. getPingYin(num[j]))>0) break; //--代码跟随 MyFactory.getAccessoryPanel().setSelectIndexs(new int[]{7,8,9}); String x = num[i]; num[i] = num[j]; num[j] = x; SortUtils.changeUnit(units, i-1,j-1); i = j; } SortUtils.repaintUnit(0); } // 调整堆 public void adjustHeap(String[] num, int s, int t) { paths.add(new RecursionPath(s,t));

state.setSortCurState(paths.size()-1,num); int i = s; for (int j = 2 * i; j <= t; j = 2 * j) { if (j < t && HanziToPinyin.getPingYin(num[j]).compareTo(HanziToPinyin. getPingYin(num[j + 1]))<0) j = j + 1;// 找出较大者把较大者给num[i] if (HanziToPinyin.getPingYin(num[i]).compareTo(HanziToPinyin. getPingYin(num[j]))>0) break; String x = num[i]; num[i] = num[j]; num[j] = x;

第 47 页 共 80 页

本文来源：https://www.bwwdw.com/article/56ga.html