数据库原理:关系模式的规范化理论 关系数据库系统设计的核心是关系型数据库设计,而关系型数据库设计的关键是设计关系型数据库的模式。关系型数据库模式的设计主要包括:数据库中应该包括多少个关系模式、每一个关系模式应该包括哪些属性、如何将这些相互关联的关系模式组建成一个完整的关系型数据库等。为构建满足业务需要、不存在异常问题的关系模式,需要在关系模式的规范化理论(简称“关系模式规范化”)的指导下进行关系型数据库的设计工作。 一、常见异常问 2024-12-01 数据库 #数据库原理
数据结构:分配排序 插入类、交换类、选择类和归并类排序方法都建立在比较关键字大小的基础上,而分配类排序不需要比较关键字的大小。分配排序,是指通过对待排序记录进行若干趟分配与收集来实现排序,是一种借助多关键字排序思想对单关键字进行排序的方法。基数排序(Radix Sorting)是最典型的分配类排序。 一、多关键字排序思想 我们先看一个具体例子。已知一副扑克牌的52张牌面的次序关系为 1♣2<♣3<...& 2024-05-26 数据结构 #数据结构
数据结构:外部排序 前述各类排序方法都是建立在关键字比较的基础上,而分配类排序不需要比较关键字的大小,它是根据关键字中各位的值,通过对待排序记录进行若干趟“分配”与“收集”来实现排序的,是一种借助于多关键字排序的思想对单关键字排序的方法。基数排序(Radix Sorting)是典型的分配类排序。 一、直接插入排序 二、折半插入排序 三、希尔排序 四、小结 五、参考 《数据结构(C语言版 第2版)》 《数据结构 自考0 2024-05-19 数据结构 #数据结构
数据结构:归并排序 归并排序(Merging Sort)就是将两个或两个以上的有序表合并成一个有序表的过程。将两个有序表合并成一个有序表的过程称为2-路归并,2-路归并是最简单、最常用的归并排序算法,也是本篇文章主要讨论的内容。 一、算法思想 2-路归并排序算法的思想是:将含有n个记录的初始序列看成是n个有序的子序列,每个子序列的长度为1。两两归并,得到⌈n/2⌉\lceil n/2 \rceil⌈n/2⌉个长度为2 2024-05-19 数据结构 #数据结构
数据结构:选择排序 选择排序的基本思想是:每趟排序,从无序区中选出关键字最小(或最大)的记录放到有序区的最后,直到整个序列有序为止。常用的选择排序算法是简单选择排序和堆排序。 一、简单选择排序 简单选择排序(Simple Selection Sort)也称作直接选择排序。 1.1、算法步骤 简单选择排序算法的步骤为: 设待排序记录存放在数组r[1…n]中。 第一趟排序,从r[1]开始,通过n-1次比较,从n个记录中 2024-05-12 数据结构 #数据结构
数据结构:交换排序 交换排序的基本思想是:每趟排序,两两比较待排序记录的关键字,若不满足排序要求就进行交换,直到整个序列有序为止。常用的交换排序算法是冒泡排序和快速排序。 一、冒泡排序 冒泡排序(Bubble Sort)是最简单的交换排序方法,它通过两两比较相邻记录的关键字,如果发生逆序,则进行交换。这样,每趟排序就能使关键字小的记录如气泡一般逐渐往上“漂浮”(左移),或者使关键字大的记录如石块一样逐渐向下“坠落”( 2024-05-05 数据结构 #数据结构
数据结构:插入排序 插入排序的基本思想是:每趟排序,将无序区中的一个记录按排序要求插入到有序区的适当位置上,直到整个序列有序为止。例如,打扑克牌在抓牌时要保证抓过的牌有序排列,则每抓一张牌,就插入到合适的位置,直到抓完牌为止,即可得到一个有序序列。 在有序区中寻找插入位置,可以选择不同的查找方法。根据查找方法的不同,有多种插入排序方法,本文将讨论常用的三种方法:直接插入排序、折半插入排序和希尔排序。 一、直接插入排序 2024-04-28 数据结构 #数据结构
数据结构:排序概述 排序是计算机程序设计中的一种重要操作,在很多领域中都有广泛的应用。比如,各种升学考试的录取工作,日常生活的各类竞赛活动等都离不开排序。为了满足不同的需求,人们设计了大量的排序算法。每种排序算法都有其各自的特点和适用场景,了解和掌握典型的、常用的排序算法,可以帮助我们编写更高效的程序。排序涉及的知识点较多,本篇主要讨论与排序相关的基本概念。 一、排序的基本概念 1.1、排序的定义 排序(Sortin 2024-04-28 数据结构 #数据结构
数据结构:散列表的查找 线性表和树表的查找方法都是以关键字的比较为基础。查找过程中只考虑各元素关键字之间的相对大小,元素在存储结构中的位置和其关键字无直接关系,查找时间与表的长度有关。当表中结点个数很多时,查找时要大量地与无效结点的关键字进行比较,致使查找速度很慢。 如果能在元素的存储位置和其关键字之间建立某种直接关系,直接由关键字找到相应的元素,那么在进行查找时,就无需进行比较或仅需做很少次的比较,查找效率能大幅提升。 2024-04-21 数据结构 #数据结构
数据结构:树表的查找之B-树和B+树 线性表和二叉排序树的查找方法,都属于内查找法。内查找法的主要特点是,以结点为单位进行查找,适用于能够存储在计算机内存中较小的文件。当文件很大时,无法全部存储到内存中,采用内查找法,需要反复地进行内、外存交换,查找效率很低,此时最好的方法是使用外查找法。 一、B-树 B-树(或B树),又称多路平衡搜索树,是一棵适用于外查找的平衡多叉树。1970年,由鲁道夫·拜尔(R.Bayer)和E·麦克雷特(E. 2024-04-14 数据结构 #数据结构