删除叶子结点中的关键字：数据结构算法详解

数据结构严蔚敏C语言版PPT课件 本资源是关于数据结构的PPT课件，作者是严蔚敏，使用C语言来编写。该课件涵盖了数据结构的基本概念、算法和实现细节。 从叶子结点中删除一个关键字的情况是： 1. 若结点N中的关键字个数＞[m/2]-1：在结点中直接删除关键字K，如图9-15(b)所示。 2. 若结点N中的关键字个数=[m/2]-1：若结点N的左(右)兄弟结点中的关键字个数＞[m/2]-1，则将结点N的左(或右)兄弟结点中的最大(或最小)关键字上移到其父结点中，而父结点中大于(或小于)且紧靠上移关键字的关键字下移到结点N，如图9-15(a)。 3. 若结点N和其兄弟结点中的关键字数=[m/2]-1：删除结点N中的关键字，再将结点N中的关键字、指针与其兄弟结点以及分割二者的父结点中的某个关键字Ki，合并为一个结点，若因此使父结点中的关键字个数＜[m/2]-1，则依此类推，如图9-15(d)。 数据结构是一门研究用计算机进行信息表示和处理的科学。它涉及到两个问题：信息的表示，信息的处理。信息的表示和组织直接关系到处理信息的程序的效率。随着应用问题的不断复杂，导致信息量剧增与信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，必须分析待处理问题中的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。 编写解决实际问题的程序的一般过程： –如何用数据形式描述问题？—即由问题抽象出一个适当的数学模型； –问题所涉及的数据量大小及数据之间的关系； –如何在计算机中存储数据及体现数据之间的关系？ –处理问题时需要对数据作何种运算？ –所编写的程序的性能是否良好？ 上面所列举的问题基本上由数据结构这门课程来回答。 数据结构的例子： 1. 电话号码查询系统：设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1,b1)，(a2,b2)，…(an,bn)，其中ai,bi(i=1，2…n)分别表示某人的名字和电话号码。本问题是一种典型的表格问题。 2. 磁盘目录文件系统：磁盘根目录下有很多子目录及文件，每个文件都有其唯一的路径和名称。 数据结构是一门综合性专业基础课，介于数学、计算机硬件、计算机软件三者之间的一门核心课程，不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。 在学习数据结构时，我们需要掌握基本概念、算法和实现细节，并且需要具备良好的逻辑思维能力和解决问题的能力。